2.4. Геометрическая интерпретация задачи

max(min)/(X)= с\Хх + с2х 2 + ?•? + спхп (2.18)

при ограничениях а\\Х\ + аі2л:2 +... + ainxn < Ъ\

(2.19)

(2.20)

ат1х1 + ат2х2 + ...

«21*1 + а22*2 + ••• + а2п*п ^ Ъ2

Рассмотрим эту задачу на плоскости, т.е. при га = 2. Пусть система неравенств (2.19), (2.20) совместна (имеет хотя бы одно решение):

«11*1 + «12*2 ^ Ъъ

«21*1 + «22*2 ? Ь2>

«ml*l + «т2*2 ^ Ьт, xi > 0; дс2 > 0.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой ацХі + а^*2 =

і = 1, т. Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми Х\ = 0, л;2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.

Если в системе ограничений (2.19) - (2.20) га = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого «il*l + «(2*2 + «гз*з ~ Ь» а условия неотрицательности — полупространства с граничными плоскостями соответственно Xj — 0 (j—1,2,3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе (2.19) - (2.20) га > 3, тогда каждое неравенство определяет полупространство га-мерного пространства с граничной гиперплоскостью ацхі + а<2*2 + •••+ сцпхп = і = 1, т., а условия неотрицательности — полупространства с граничными гиперплоскостями Xj = 0, j = 1, га.

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

Таким образом, геометрически ЗЛП (2.19)-(2.20) представляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наибольшее (наименьшее) значение, причем допустимыми решениями являются все точки многогранника решений.

Если в ЗЛП ограничения заданы в виде неравенств с двумя переменными, она может быть решена графически.

Этап 1. Сначала на координатной плоскости хі0х2 строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям. Далее строится вектор-градиент линейной функции f(X) в какой-нибудь точке х0 , принадлежащей допустимой области:

Этап 2. Прямая cixi+c2x2= f(x0), перпендикулярная вектору-градиенту, передвигается в направлении этого вектора в случае максимизации f(X) до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой максимума f(X).

Этап 3. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(X), найденное в получаемой точке, является максимальным.

В случае минимизации f(X) прямую с^х\ + с2х2 = f(x0)

надо двигать в направлении, противоположном вектору-градиенту. Ясно, что если прямая при своем движении не покидает допустимой области, то соответствующий максимум или минимум f(X) не существует.

L. Пример 6. Решить графическим методом следующую ЗЛП: max f(X) = ЗОЛГІ + 60x2

+ 3x2 < 21 Злгі + 2X2 < 21 Зхі + x2 > 18 Xl,2 * 0.

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

Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой х\ + 3*2 ~~ 21=0. Построим прямую по двум точкам (0; 7) и (21; 0), которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим ее цифрой I.

Множество решений строгого неравенства — одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости.

Аналогичным образом построим области решения двух других неравенств

3*! + 2*2 - 21 = 0; xi = 0, х2 = 10,5;

х2 = 0, = 7.

(на рисунке прямая II);

3*! + 2*2 - 21 < 0 при xi = х2 = 0, - 21 < 0 выполняется, берется нижняя полуплоскость.

+ *2 - 18 = 0; xi = 0, х2 = 18;

х2 = 0, = 6.

(на рисунке прямая III);

3*i + *2 - 18 < 0 при *i = *2 = 0, - 18 < 0 выполняется, берется нижняя полуплоскость.

Заштрихуем общую область для всех неравенств, обозначим вершины многоугольника латинскими буквами и определим их координаты, решая систему уравнений двух пересекающихся соответствующих прямых. Например, определим координаты точки С, являющейся точкой пересечения второй и третьей прямой:

4" 2^2 ~ 21) = =

3*! + *2 = 18.

Вычислим значение целевой функции в этой точке: /(X)=30*I + 60*2 = 150 + 180 = 330.

Аналогично поступим для других точек, являющихся вершинами замкнутого выпуклого многоугольника OABCD, представляющего собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения: т. 0(0;0), т. А(0;7), т. В(3;6), т. С(5;3), т. D(6;0).

Этап 2. Приравняем целевую функцию постоянной величине а: 30*! + 60*2 = а.

Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть а=0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению 30*i + 60*2 = 0. В качестве одной из этих точек удобно взять точку 0(0;0), а так как при *i=2 *2=-1, то в качестве второй точки возьмем точку G(2;-l).

Через ЭТИ две ТОЧКИ проведем ЛИНИЮ уровня f(X) = 30*1 + + 60*2 = 0 (пунктирная прямая на рис. 2.4).

Этап 3. Для определения направления движения к оптимуму построим вектор-градиент V, координаты которого

являются частными производными функции f{X), т.е.

В нашем случае движение линии уровня будем осуществлять до ее пересечения с точкой В; далее она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции. Отсюда легко записать решение исходной ЗЛП: max ДХ) =450 и достигается при *i=3; Х2=б.

Если поставить задачу минимизации функции f(X) = = ЗОдгі + 60*2 при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору-градиенту V. Как это видно на рис. 2.4, минимум целевой функции достигается в точке 0(0;0), следовательно, можно записать min f(X) = 0 и достигается при, х\— 0; дг2= 0. Л

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

Если область допустимых решений является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной и ЗЛП не будет иметь решений; в этом случае условно можно записать, что, например, max f(X) = +оо .

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