Представление задачи линейного программирования на плоскости

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 27Следующая ⇒

Рассмотрим случай основной задачи линейного программирования, когда число переменных x_j превышает количество уравнений ограничений на 2, то есть n-m = 2. В этом случае задача линейного программирования приобретает наглядную геометрическую интерпретацию и для ее решения можно воспользоваться графическим методом.

Выделим из всей совокупности x_j две переменных, которые назовем свободными переменными. Используя уравнения-ограничения (3.6), выразим остальные переменные, называемые базисными, через свободные.

Пусть в качестве свободных переменных выбраны переменные x ₁ и x ₂. Тогда базисные переменные будут связаны со свободными следующими соотношениями

Построим координатные оси O x ₁ и O x ₂. Каждая точка координатной оси соответствует определенному значению одной из свободных переменных. Отметим штриховкой те полуоси, на которых переменные x ₁ и x ₂ принимают неотрицательные значения. Так переменная x ₁ принимает неотрицательные значения вправо от оси O x ₂, а переменная x ₂ - вверх от оси O x ₁. Очевидно, в первом квадрате переменные x ₁ и x ₂ будут неотрицательными.

По условию задачи все остальные переменные также должны быть неотрицательными, то есть x ₃³0, x ₄³0,..., x_n ³0 или

Рис.3.1

Если положить x ₃= 0, то есть взять предельно допустимое значение x ₃, то уравнение

b ₃ + a ₃₁ x ₁ + a ₃₂ x ₂ = 0

в координатах x 1O x 2 представляет собой уравнение прямой. Каждая точка прямой соответствует x ₃=0. Область, лежащая по одну сторону этой прямой, будет соответствовать положительным значениям x 3, а по другую сторону - отрицательным. Отметим штриховкой ту область, где переменная x ₃ принимает положительное значение.

Аналогичным образом построим прямые x ₄= 0,..., x_n = 0 и опре­делим области, где переменные x ₄>0, x ₅>0,..., x_n >0. Тогда область (многоугольник), каждая точка которых соответствует неотрицательным значениям переменных x ₁, x ₂,..., x_n и будет областью допустимых значений.

Приступим теперь к поиску оптимального решения. Выразим целевую функцию через свободные переменные:

где

g₀ = c₃b₃ +... + c_nb_n

g₁ = c₁ + c₃a₃₁ +... + c_na_n1

g₂ = c₂ + c₃a₃₂ +... + c_na_n2

Положим значение L (x) = G ₁.

Тогда уравнение

представляет собой уравнение прямой в координатах x ₁O x ₂. Она пересекает координатные оси в точках

Определив эти точки, построим прямую (3.11).

Изменим значение целевой функции до G ₂. Очевидно, уравнение

также является уравнением прямой. Изменение целевой функции от G ₁ до G ₂ соответствует перемещению прямой параллельно самой себе.

При решении задачи ЛП графическим способом для построения исходной прямой удобно положить L (x) = g₀.

Тогда из (3.10) следует, что

.

(3.13)

Назовем прямую L ₀(x) основной прямой. Так как она проходит через начало координат, то для ее построения необходимо найти еще одну точку. Очевидно, уравнению (3.13) удовлетворяет также и точка (g₂, -g₁). Перемещение основной прямой параллельно самой себе в направлении определяемом вектором, направленным из начала координат в точку (-g₁, -g₂) будет соответствовать уменьшению значения целевой функции L (x). Точка x*, принадлежащая области допустимых решений и наиболее удаленная от начала координат в направлении перемещения прямой целевой функции и будет оптимальным решением задачи линейного программирования.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов