Геометрия задач ЛП, базисные решения, вырожденность.

Геометрические представления позволяют лучше уяснить рассмотренные свойства задач ЛП.

Размерность пространства задачи k равна разности числа переменных и числа ограничений-равенств. Поэтому для модели в стандартной форме k= , а для канонической модели k= - m. Как отмечалось раньше, значение k не зависит от формы записи модели и является фиксированным для конкретной задачи.

Очевидно, что геометрические построения возможны для k £ 3. Сначала мы рассмотрим задачи на плоскости (k= 2), а затем сделаем обобщение на многомерное пространство.

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

 

Исходная модель L =7 x 1+5 x 2→max, 1) 2 x 1+3 x 2£19, 2) 2 x 1+ x 2£13, 3) 3 x 2£12, 4) 3 x 1£17, 5) x 1³0, 6) x 2³0.

Каноническая модель L =7 x 1+5 x 2→max, 2 x 1+3 x 2+ x 3=19, 2 x 1+ x 2+ x4 =13, 3 x 2+ x5 =12, 3 x 1+ x6 =17, " xj ³0.

Чтобы решить задачу, надо сначала построить допустимое множество, а затем по целевой функции найти на нем точку или множество с максимальным значением критерия.

Допустимое множество задачи находится как пересечение допустимых множеств, построенных по отдельным условиям задачи. В нашем примере таких множеств 6.

Построение множества начинается с определения его границы. Возьмем условия неотрицательности переменных:

x ₁³0, следовательно, уравнение границы x ₁ =0 (ось х ₂) и допустимое множество – правая полуплскость (включая границу); х ₂³0, уравнение границы х ₂=0 (ось x ₁), допустимое множество – верхняя полуплоскость. Таким образом, при неотрицательности всех переменых допустимое множество задачи ЛП всегда лежит в первом квадранте.

Теперь перейдем к построению допустимых множеств по функциональным условиям. Граница по 1-му условию 2 х ₁+3 х ₂=19 (из канонической модели имеем альтернативное уравнение x ₃=0) представляет собой прямую, для построения которой достаточно нанести любые 2 точки. Например, положив х ₁=0, из уравнения получим х ₂=19/3 (точка на оси х ₂); вторую точку возьмем на оси х ₁: х ₂=0 и тогда х ₁=19/2. Чтобы определить, с какой стороны прямой выполняется условие, достаточно проверить одну точку вне границы. В качестве такой точки проще всего брать начало коодинат, в котором левая часть условия всегда равна нулю.. Наше условие 1) выполняется в этой точке, следовательно, допустимое множество – юго-западная полуплоскость. В противном случае получили бы северо-восточную полуплоскость.

Аналогично записываем уравнения границ и проводим соответствующие прямые по условию 2): из исходной модели 2 х ₁+ х ₂=13 и канонческой модели х₄ =0; по условию 3): 3 х ₂=12 и х₅ =0; по условию 4): 3 х ₁=17 и х₆ =0. Нетрудно убедиться, что каждое из этих условий выполняется с той стороны своей границы, с которой находится начало коодинат.

Находя пересечение шести построенных допустимых множеств, получаем выпуклый шестиугольник (рис. 4.2) – частный случай выпуклого многогранника.

Из бесконечного множества допустимых решений, принад­лежащих этому многоугольнику, необходимо найти то, которое дает максимум критерия. Для этого нам нужно знать “поведение“ критерия на допустимом множестве. С этой целью построим линии уровня критерия L=Const.. Так как критерий линейный, то линии уровня – это множество параллельных прямых с постоянным градиентом (направлением возрастания значений критерия). Поэтому для определения этого направления достаточно иметь 2 линии уровня. Конкретные значения L можно брать любые, но так, чтобы соответствующие прямые оказались в области уже выполненных построений.

L^*

Полагая L =14, получаем уравнение линии уровня

Рис. 10

7 х ₁+5 х ₂=14. Аналогично для L =28 имеем уравнение линии уровня 7 x ₁+5 x ₂=28. На рис. 4.2 они представлены тонкими пунктирными линиями. Теперь ясно, что критерий увеличивается в направлении, показанном стрелкой. Чтобы найти оптимальное решение, не нужно строить новые линии уровня. Достаточно мысленно перемещать прямую, параллельную линиям уровня, в направлении стрелки до тех пор пока она не выйдет на границу допустимого множества задачи. В нашем примере такое предельное положение соответствует прохождению линии уровня через точку С. Следовательно, в точке С критерий достигает максимального значения, а соответствующее решение является оптимальным. Координаты точки С – оптимальные значения переменных, можно снять с графика или для большей точности найти как решение системы 2-х уравнений границ, образующих эту точку:

2 x^* ₁+3 x^* ₂=19,

2 x^* ₁+ x^* ₂=13.

Отсюда имеем: х^* ₁=5, х^* ₂=3. Значения остальных переменных вычисляются однозначно из канонической модели после подстановки в ее уравнения х^* ₁и х^* ₂. В результате получаем оптимальное решение задачи: х^* ₁=5, х^* ₂=3, х^* ₃= х^*₄ =0, х^*₅ =3, х^*₆ =2 и, следовательно, L^*= 50.

Таким образом, чтобы добиться максимальной прибыли в 50 единиц, необходимо производить 5 изделий первого типа и 3 изделия второго типа. При этом будут полностью использованы ресусы 1-го и 2 -го вида (х^* ₃= х^*₄ =0), а по ресурсам 3-го и 4-го вида образуются остатки в количестве 3 и 2 соответственно (х^*₅ =3, х^*₆ =2). Задача имеет единственное оптимальное решение, так как линия уровня L= 50 соприкасается с допустимым множеством только в одной точке.▲

 

Очевидно, что при данном допустимом множестве задача всегда будет иметь решение независимо от коэффициентов целевой функции, потому что в любом случае будет существовать предельное положение линии уровня критерия. Однако оптимальное решение может быть и не единственным.

Пусть в нашем примере при тех же ограничениях изменились коэффициенты критерия:

L ₁=4 x ₁+6 x ₂→ max.

Так как условия не изменились, то допустимое множество остается прежним. Если повторить построение линий уровня, то они будут параллельны стороне BC (коэффициеты при перемен-ных в критерии и 1-м ограничении пропорциональ-ны). Поэтому в предельном положении линия уровня критерия совпадает с границей по 1-му ограничению (рис. 4.3). В таком случае получим множество (бесконечное) оптимальных решений, лежащее на стороне BC, каждому из которых соответствует одно и то же максимальное значение критерия L ₁.

Приведенные построения подтверждают высказанное ранее утверждение о том, что на ограниченном допустимом множестве (выпуклом многограннике) задача всегда разрешима.

Теперь выясним, что будет, если допустимое множество неограниченно. Не конкретезируя модель, рассмотрим поведение двух целевых функций на одном неограниченном множестве (рис. 4.4). Направление улучшения критериев показано стрелками. Здесь мы видим разное поведение критериев, приводящее к различным результатам.

а) Значение критерия L ₁ улучшается в направлении неограничености множества и, следовательно, критерий неограничен на допустимом множестве, то есть он может улучшаться до бесконечности – допустимые решения есть, а оптимального нет.

б) Улучшение критерия L ₂ ограничено на допустмом множестве, следовательно, решение существует (в этом примере оно единственное, но, очевидно, возможны и множественные решения на неограниченном множестве).

Рассмотрим другой случай (рис. 4.5). Пересечение допустимых множеств, порождаемых тремя функциональными ограничениями задачи и условиями неотрица-тельности переменных, оказывается пустым. Следовательно, допустимых решений нет и задача неразрешима.

Результаты геометрического анализа задачи ЛП в двумерном простанстве легко обобщаются на многомерное пространство. Вместо прямых границами множеств будут гиперплоскости, а непустым допустимым множством задачи – выпуклый многогранник или выпуклое многогранное множество. Для нахождения решения мысленно перемещаем гиперплоскость уровня критерия в направлении его улучшения пока имеютя общие точки с допустимым множеством. Если достигается предельное положение, то задача разрешима. При этом гиперплоскость может касаться только одной вершины множества – задача имеет единственное решение,ребра или грани допустимого множества – существует множество решений соответственно на ребре или грани, которые полностью определяются своими крайними точками (вершинами). При отсутствии предельного положения критерий неограниченно улучшается и задача неразрешима.

Таким образом, если задача ЛП разрешима, то оптимальное решение обязательно достигается в вершине допустимого множества. Поэтому оптимальное решение следует искать не на всей границе, а только в вершинах допустимого множества.