ИсследОпераций

З а м е ч а н и е. Очевидно, что для приведения к равенству ограничения– неравенства a, x b из его левой части нужно вычесть неотрицательную до-

полнительную переменную.

5) Переход к неотрицательным переменным. Если на знак переменной x j

не наложено ограничений, то можно заменить ее разностью двух неотрицательных переменных

неотрицательности. Чтобы избавиться от такой переменной, выполним преобра-

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

Пример 3. Данную каноническую ЗЛП min z 3x1 x2 x4 ,

x1 3x2 x3 x4 4,

2x1 7x2 4x3 5x4 10, xk 0, k 1,5

свести к равносильной стандартной задаче минимизации.

Р е ш е н и е. Применяя метод Жордана-Гаусса, составляем расширенную матрицу системы ограничений и выполняем над ней последовательность жордановых исключений

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

Отсюда x1 5x3 8x4 2, x2 2x3 3x4 2 . Для построения новой ЗЛП, содержащей только свободные переменные x3, x4 , исключим базисные переменные из

целевой функции

z 3 5x3 8x4 2 2x3 3x4 2 x4 17x3 27x4 8 .

Из условий неотрицательности переменных x1 и x2 следуют ограничения

5x3 8x4 2 0, 2x3 3x4 2 0 .

Таким образом, мы получили равносильную исходной ЗЛП стандартную задачу минимизации

54

min z1 17x3 27x4 8,

5x3 8x4 2,

2x3 3x4 2, x3 0, x4 0.

З а м е ч а н и е. Рассмотренный метод позволяет каноническую ЗЛП, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, свести к равносильной ЗЛП с n m переменными.

§ 3. Понятия неограниченной и недопустимой ЗЛП. Признак существования оптимального решения ЗЛП

где D – выпуклый многогранник.

Эта задача может не иметь оптимального решения в следующих двух слу-

чаях:

1) целевая функция данной задачи на допустимом множестве принимает сколь угодно малые значения, т.е. оказывается неограниченной снизу. В этом

случае будем называть задачу (3.1) неограниченной и записывать min f x ;

x D

2) система ограничений, определяющая допустимое множество D задачи (3.1), несовместна, т.е. допустимое множество не содержит ни одной точкиD . В этом случае принято говорить о недопустимости задачи (3.1).

Приведем формулировку признака существования оптимального решения

ЗЛП.

Теорема 3.1. Если в задаче минимизации (3.1) допустимое множество D не пусто, а целевая функция ограничена снизу на множестве D , то эта задача имеет оптимальное решение.

§ 4. Основное свойство ЗЛП

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

Д о к а з а т е л ь с т в о. Докажем теорему для случая ЗЛП с ограниченным допустимым множеством (общий случай более громоздок).

Рассмотрим для определенности задачу минимизации

где D – выпуклый ограниченный многогранник. Пусть x – оптимальная точка задачи (4.1), а f x – наименьшее значение целевой функции.

Д о к а з а т е л ь с т в о проведем методом от противного. Предположим, что в каждой угловой точке xугл допустимого множества задачи (4.1) значение

f xугл , т.е. f xугл .

По теореме о представлении точек выпуклого ограниченного множества

§ 5. Геометрическое решение ЗЛП

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

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

a1x1 a2x2 a или a1x1 a2x2 a .

Как известно, каждое из этих неравенств определяет на плоскости одну из частей, на которые прямая a1x1 a2x2 a разбивает плоскость. Чтобы определить, какую

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

56

Пример. Изобразить полуплоскость, определяемую неравенством

2x1 3x2 6.

Р е ш е н и е. Построим прямую 2x1 3x2 6 (рис. 2). так как она не проходит через начало координат, то для определения задаваемой неравенством полуплоскости можно взять точку O 0,0 . Подставляя ее координаты в данное нера-

венство, получаем неверное соотношение 0 6 . Следовательно, искомая полуплоскость та, которая не содержит начала координат (на рисунке эта полуплоскость заштрихована).

x2

1 1 3

2

Рис. 2

Пусть дана допустимая ЗЛП с двумя переменными и целевой функцией f x c1x1 c2x2 .

Геометрический метод решения такой задачи состоит из следующих эта-

пов:

1. На координатной плоскости строим допустимое множество данной зада-

чи.

2. От начала координат откладываем вектор f c1,c2 . Этот вектор –

градиент целевой функции – указывает направление ее возрастания.

3. Выбрав в допустимом множестве произвольную точку, проводим через нее прямую, перпендикулярную построенному вектору f (линию уровня целе-

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

f до тех пор, пока она не перестанет пересекаться с допустимой областью. Пе-

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

нию вектора f .

З а м е ч а н и е. Если же при любом перемещении в соответствующем направлении перемещаемая прямая имеет непустое пересечение с допустимой

57

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

Пример 2. Решить ЗЛП

maxmin f x x1 x2 ,

2x1 x2 10,

x1 x2 3,x1 x2 1,

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

Для построения допустимой области изобразим на координатной плоскости граничные прямые

Отметив полуплоскости, определяемые соответствующими неравенствами, получим четырехугольник АВСД, являющийся допустимым множеством данной ЗЛП (рис. 3).

точку допустимой области проведем перпендикулярную этому вектору прямую l . Перемещая мысленно прямую l параллельно самой себе как в направле-

58

нии вектора f , так и в противоположном направлении, получаем, что наиболь-

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

В качестве оптимального решения задачи минимизации можно взять любую точку отрезка AD , например, D 3,0 . Таким образом, для данной ЗЛП

fmax 7, xmax 3,4 ; fmin 3, xmin 3,0 .

Пример 3. Решить геометрически

min f x x1 3x2 x3 x4 ,

x1 x2 3x3 2x4 2,x1 2x2 x3 x4 2,

Р е ш е н и е. В данной канонической ЗЛП разность между числом переменных и числом ограничений равна двум. Поэтому ее можно свести к эквивалентной ЗЛП с двумя переменными и, решив геометрически полученную задачу, найти решение исходной ЗЛП. Используя метод Жордана-Гаусса, преобразуем систему ограничений данной ЗЛП к равносильной системе с единичным базисом

Исключая базисные переменные x1 и x4 , получаем эквивалентную исходной ЗЛП

59

min f x 7x2 4x3 10,

x2 0, x3 0.

Построим допустимую область и градиент f 7,4 целевой функции задачи (5.2) в системе координат X2OX3 (рис. 4).

x3

Рис.4

Из рисунка заключаем, что целевая функция задачи (5.2) принимает наименьшее значение в угловой точке A , координаты которой x2 1,6 ; x3 1, 2 определяются

из системы

3x2 x3 6,x2 2x3 4.

Наименьшее значение целевой функции

fmin 7 1,6 4 1,2 10 6 .

Для отыскания оптимального решения исходной задачи подставим в (5.1) найденные значения x2 и x3 . Окончательно получаем:

fmin 6, xmin 0;1,6;1,2; 0 .

60

§ 6. Алгебраические условия угловой точки

Рассмотрим каноническую ЗЛП

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

Теорема 6.1. Точка x допустимого множества канонической задачи (6.1) тогда и только тогда будет его угловой точкой, когда она является опорным решением системы ограничений этой задачи.

Д о к а з а т е л ь с т в о. Обозначим через D допустимое множество задачи (6.1). Так как x D , все компоненты точки x неотрицательны. Не ограничивая

общности, предположим, что отличными от нуля являются первые l компонент x , так что

x x1 , x2 , ..., xl , 0, ..., 0 , где xk 0, k 1,l .

Докажем теперь обе части теоремы.

1.Необходимость. Пусть x – угловая точка множества D . Так как точка

xD , ее компоненты удовлетворяют системе (6.2), т.е.

где – такое положительное число, что все компоненты точек x1 и x2 неотрица-

тельны.

Убедимся, что x1 D и x2 D . Для этого достаточно проверить, что компо-

y y1, y2 , ..., yl , 0, ..., 0 , z z1, z2 , ..., z l, 0, ..., 0 .

Поскольку точки y и z принадлежат множеству D , их компоненты удо-

влетворяют системе (6.2), т.е.

A1 y1 A2 y2 ... Al yl B , A1z1 A2 z2 ... Al zl B .

Вычитая из первого соотношения второе, получаем