Шпаргалка по "Логистике"

Графический способ решения задачи линейного  программирования

 

Чтобы представить себе принципиальную сторону задачи линейного программирования, обратимся к геометрической интерпретации. Пусть число уравнений m на два меньше числа переменных n (n-m=k=2). Такой частный случай даёт возможность геометрической интерпретации задачи линейного программирования на плоскости.

Мы знаем, что n линейно  независимых уравнений (3.1.1) всегда можно разрешить относительно каких-то m базисных переменных, выразив их через остальные, свободные, число которых равно n-m=k (в нашем случае k=2). Предположим, что свободные переменные – это x₁ и x₂ (если это не так, то всегда можно заново перенумеровать переменные), а остальные: x₃, x₄, …, x_n – базисные. Тогда вместо m уравнений (3.1.1) мы получим тоже m уравнений, но записанных в другой форме, разрешённых относительно x₃, x₄,

 

 

 

Будем изображать пару значений свободных переменных точкой с координатами x₁, x₂, изображённых на рис.1. Так как переменные x₁, x₂ должны быть неотрицательными, то допустимые значения свободных переменных лежат только выше оси Ox₁ (на которой x₂=0) и правее оси Ox₂ (на которой x₁=0). Это мы отметим штриховкой, обозначающей «допустимую» сторону каждой оси. Теперь построим на плоскости x₁Ox₂ область допустимых решений или же убедимся, что её не существует. Базисные переменные x₃, x₄, …, x_n тоже должны быть неотрицательными и удовлетворять уравнениям (14). Каждое такое уравнение ограничивает область допустимых решений.

 

 

Рис. 1

 

Действительно, положим в  первом уравнении (14) x₃=0; получим уравнение прямой линии:

 

 

На этой прямой x₃=0; по одну сторону от неё x₃>0, по другую – x₃<0. Отметим штриховкой ту сторону (полуплоскость), где x₃>0 (рис. 2). Пусть эта сторона оказалась правее и выше прямой x₃=0. Значит, вся область допустимых решений лежит в первом координатном угле, правее и выше прямой x₃=0. Аналогично поступим и со всеми остальными условиями (14). Каждое из них изобразится прямой со штриховкой, указывающей «допустимую» полуплоскость, где только и может лежать решение (рис. 3).

 

Рис. 2

Рис. 3

 

 

Таким образом, мы построили n прямых: две оси координат (Ox₁ и Ox₂) и n-2 прямых x₃=0, x₄=0, …, x_n=0. Каждая из них определяет «допустимую» полуплоскость, где может лежать решение. Часть первого координатного угла, принадлежащая одновременно всем этим полуплоскостям, и есть область допустимых решений. На рис. 3 показан случай, когда области допустимых решений существует, т.е. система уравнений (14) имеет неотрицательные решения. Заметим, что этих решений – бесконечное множество, так как любая пара значений свободных переменных, взятая из область допустимых решений, «годится», а из x₁ и x₂ могут быть определены и базисные переменные.

Может оказаться, что область  допустимых решений не существует, и значит, уравнения (14) несовместимы в области неотрицательных значений. Такой случай показан на рис. 4, где нет области, лежащей одновременно по «нужную» сторону от всех прямых. Значит, задача линейного программирования не имеет решения.

 

Рис. 4

 

Предположим, что область  допустимых решений существует, и  мы её построили. Как же теперь найти среди них оптимальное?

Для этого дадим геометрическую интерпретацию условию (13) LÞmax. Подставив выражения (13) в формулу (14), выразим L через свободные переменные x₁, x₂. после приведения подобных членов получим:

 

где ¡₁, ¡₂ – какие-то коэффициенты, ¡₀ – свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным x₁, x₂, он мог и появится. Однако мы его тут же и отбросим: ведь максимум линейной функции L достигается при тех же значениях x₁, x₂, что и максимум однородной линейной функции (без свободного члена):

 

 

Посмотрим, как изобразить геометрически условие L’Þmax. Положим сначала L’=0, т.е. и построим на плоскости x₁Ox₂ прямую с таким уравнением; очевидно, она проходит через начало координат (рис. 5)

 

Рис. 5

 

Назовём её «опорной прямой». Если мы будем придавать L’ какие-то значения C₁, C₂, C₃, …, прямая будет перемещаться параллельно самой себе; при перемещении в одну сторону L’ будет возрастать, в другую – убывать. Отметим на рис. 5. стрелками, поставленными у опорной рамой, то направление, в котором L’ возрастает. На рис. 5. это оказалось направление «направо - вверх», но могло быть и наоборот: всё зависит от коэффициентов g₁, g₂. теперь изобразим опорную прямую и область допустимых решений на одном чертеже (Рис. 6). Давайте будем мысленно двигать опорную прямую параллельно самой себе в направлении стрелок (возрастания L’). Когда L’ достигнет максимума? Очевидно, в точке A (крайней точке области допустимых решений в направлении стрелок). В этой точке свободные переменные принимают оптимальные значения x₁^*,x₂^*, а из них можно по формулам (14) найти и оптимальные значения всех остальных (базисных) переменных x₃^*, x₄^*, …, x_n^*. Заметим, что максимум L’ достигается в одной из вершин области допустимых решений, где, по крайней мере, две из базисных переменных (в нашем случае это x₃ и x₅) обращаются в нуль. Могло бы обращаться в нуль и больше базисных переменных, если бы через точку А проходило более двух прямых x_i=0.

А может ли оказаться, что  оптимального решения не существует? Да, может, если в области допустимых решений функция L’ (а значит и L) не ограничена сверху. Пример такого ненормального  случая показан на рис. 7(в разумно  поставленных задачах обычно такого недоразумения не возникает).

 

Рис. 6

 

 

Рис. 7

 

На рис. 6. оптимальное  решение существовало и было единственным. А сейчас рассмотрим, когда оптимальное  решение существует, но не единственно (их бесконечное множество). Это случай, когда максимум L’ достигается не в одной точке А, а на целом отрезке АВ, параллельном опорной прямой (рис. 8). Итак, мы рассмотрели в геометрической интерпретации случай n-m=k=2 и убедились в следующем: оптимальное решение (если оно существует) всегда достигается в одной из переменных x₁, x₂, …, x_n равны нулю. Оказывается, аналогичное правило справедливо и в случае n-m=k>2 (только геометрическая интерпретация теряет в этом случае свою наглядность). Обойдёмся без доказательства, просто сформулируем это правило.

 

Рис. 8

 

Оптимальное решение задачи линейного программирования (если оно существует) достигается при такой совокупности значений переменных x₁, x₂, …, x_n, где, по крайней мере, k из них обращаются в нуль, а остальные неотрицательны.

При k=2 такая совокупность значений изображается точкой на плоскости, лежащей в одной из вершин многоугольника допустимых решений. При k=3 многоугольник допустимых решений представляет собой уже не многоугольник, а многогранник, и оптимальное решение достигается в одной из его вершин. При k>3 геометрическая интерпретация теряет наглядность, но всё же геометрическая терминология остаётся удобной. Мы будем продолжать говорить о «многограннике допустимых решений» в k-мерном пространстве, а оптимальное решение (если оно существует) будет достигаться водной из вершин этого многогранника, где, по крайней мере, k переменных равны нулю, а остальные – неотрицательны. Будем для краткости называть такую вершину «опорной точкой», а вытекающее из неё решение «опорным решением».