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

Рассмотрим задачу линейного программирования в стандарт­ной форме. Известен так называемый геометрический метод решения задачи линейного программирования. Поясним суще­ство этого метода для имеющего наглядное представление слу­чая двух свободных и любого числа базисных переменных.

Б удем считать переменные х1 и х₂ свободными, а остальные переменные — базисными. Разрешим систему р = п — 2 линей­ных алгебраических уравнений (7.5) относительно переменных x₃,х₄, ..., x_п, т. е. выразим базисные переменные x3,x4, ..., х_п через свободные переменные х1 и х₂. Получим новую систему, состоящую из р линейных уравнений:

где каждая базисная переменная

Рассмотрим плоскость, заданную осями координат х1 и х₂ (рис. 7.2, а), и изобразим на ней область допустимых решений Х^а. Поскольку каждая переменная хi (i = 1,2, .. . ,n) неотри­цательна, допустимые решения должны лежать в неотрицатель­ном квадранте плоскости (х1, х₂), образованном двумя осями ко­ординат х1 = 0, х₂₌ 0. Положим хз = 0. Из первого уравнения системы линейных уравнений (7.6) получаем уравнение прямой

Рис. 7.2. Область допустимых решений: а — имеется единственное оптимальное решение; б — допустимых решений нет

линии Допустимые решения должны ле­жать не ниже этой прямой линии в полуплоскости Поло­жительное направление в каждой полуплоскости обозначено на рис. 7.2, а стрелкой.

Выполним то же самое для остальных базисных переменных x4, ... ,x_п. В результате будут построены n — 2 прямые линии хз = 0, Х4 = 0, ..., х_п = 0, каждая из которых определяет допу­стимую полуплоскость где может лежать решение зада­чи линейного программирования. Таким образом, область допу­стимых решений Х^а представляет собой многоугольник, явля­ющийся общей частью всех допустимых полуплоскостей Xi > 0 (i = 1,2, ...,n).

В зависимости от того, как пересекаются друг с другом до­пустимые полуплоскости, может получиться много разнообраз­ных форм области допустимых решений, где будет иметься един­ственное оптимальное решение (см. рис. 7.2, а) или много оп­тимальных решений. Может оказаться, что допустимое множе­ство Х^а пусто (см. рис. 7.2, б). Это означает, что система линей­ных уравнений (7.5) несовместна при неотрицательных значени­ях переменных Хi.

П ерейдем к поиску оптимального решения задачи линейного программирования, считая, что оно существует. Выразим кри­терий оптимальности у = f(х) через свободные переменные х1 и х₂:

и ли в более простой форме

о тбросив постоянное слагаемое уо, не влияющее на оптимальные значения переменных. Построим на плоскости (x1, х₂) так назы­ваемую опорную прямую

При параллельном перемещении опорной прямой величина уо будет изменяться (возрастать или убывать). Величина этого из­менения зависит от коэффициентов Y1 ^и Y2 при переменных х1 и х₂.

Б удем перемещать опорную прямую в сторону увеличения значения уо. В некоторой точке А* функция уо может достичь своего максимального значения (см. рис. 7.2, а). Назовем эту точку опорной. Координаты опорной точки определяют опти­мальные значения переменных по которым из уравне­ний (7.6) можно найти оптимальные значения остальных пере­менных задающих оптимальное решение

исходной задачи линейного программирования, и оптимальное значение целевой функции

П ример 7.3. Рассмотрим задачу линейного программирова­ния в стандартной форме, где требуется максимизировать зна­чение целевой функции

max, при наличии ограничений:

1. Выберем переменные х1 и Х2 в качестве свободных. Выра­зим через них критерий оптимальности у и все остальные базис­ные переменные Х3, Х4, Х5, х6.

1. Положим все базисные переменные равными нулю и по­строим на плоскости (х1,х₂) прямые линии: х3 = 0, х4 = О, x5 = 0, x6 = 0 (см. рис. 7.2, а). Построим множество допустимых значений Х^а, которое составляет общую часть шести неотрица­тельных полуплоскостей

2. Построим на плоскости (х1, х₂) опорную прямую уо = х1 + 2х₂= 0 и станем перемещать ее параллельно самой себе в направлении увеличения уо- Линии уровня функции у о = х1 + 2x2 показаны на рис. 7.2, а штрихпунктиром.

3. Функция уо достигает максимального значения у0=8 в опорной точке A* с координатами Из уравнений (7.7) получаем итоговое оптимальное решение задачи: х1= 4,

В изображенном на рис. 7.2, а случае оптимальный вариант решения единственен, причем оптимальные значения переменных В общем случае оптималь­ных вариантов решения может быть бесконечно много, если мак­симум критерия оптимальности достигается не в одной опорной точке, а на отрезке, параллельном опорной прямой (рис. 7.3, а), на прямой или на луче. Оптимальный вариант решения может и не существовать даже тогда, когда имеется бесконечно много допустимых решений (рис. 7.3, б).

Итак, оптимальное решение общей задачи линейного про­граммирования (если оно существует) достигается при такой

совокупности значений переменных x1, x₂ .., х_п, где, по край­ней мере, две переменные равны нулю (являются координатами точки пересечения двух допустимых полуплоскостей), а осталь­ные неотрицательны. Область допустимых решений образует в n-мерном пространстве выпуклый многогранник, называемый симплексом.