Материал: 4-1

xj ≥ 0(j = 1, 2, ..., n).

Введем в рассмотрение дополнительную линейную форму

XX

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

n

X

aijxj + yi = bi(i = 1, 2, ..., m),

j=1

xj ≥ 0(j = 1, 2, ..., n), yi ≥ 0(i = 1, 2, ..., m).

Исходя из опорного плана x1 = 0, ..., xn = 0, y1 = b1, ..., ym = bm, симплексным методом можно найти оптимальный опорный план этой

задачи x1, ..., xn, y1, ..., ym. Тогда Φ(X , Y ) ≥ Φ(X, Y ). Если в данном плане y1 = 0, ..., ym = 0, то план x1, ..., xn будет оптимальным планом

исходной задачи. Действительно, для любого плана x01, ..., x0n построим план x01, ..., x0n, 0, ..., 0 и тогда Φ(X , Y ) ≥ Φ(X0, 0). Так как yi = 0, то

Φ(X , 0) ≥ Φ(X0, 0), или, что то же, F (X ) ≥ F (X0). Это и означает, что план X − оптимальный.

Для получения условий, при которых y1 = 0, ..., ym = 0, будем предполагать, что исходная задача не является бессмысленной и имеет хотя бы один план x01, ..., x0n. Пусть x1, ..., xn, y1, ..., ym опорный план дополненной задачи, в котором не все компоненты yi равны нулю.Сравним значения формы Φ(X, Y ) на указанном плане и на плане x01, ..., x0n, 0, ..., 0. Имеем

Φ(X0, 0) − Φ(X, Y ) = F (X0) − F (X) + M(y1 + ... + ym).

Ясно, что если выбрать M достаточно большим, то правая часть равенства будет положительной и тогда Φ(X0, 0) > Φ(X, Y ). Это означает, что план (X, Y ) для дополнительной задачи не может быть оптимальным, так как на плане (X0, 0) форма принимает большее значение. Каким же должно быть М? Из неравенства F (X0) − F (X) + M(y1 + ... + ym) > 0 находим, что

Выберем теперь M так, чтобы неравенство (19) выполнялось для всех опорных планов дополненной задачи, у которых хотя бы одна из компонент y отлична от нуля. Такой выбор возможен, поскольку таких планов, как и

вообще опорных, конечное число. При этом никакой опорный план с Y 6= 0 не может быть оптимальным для дополненной задачи и, следовательно, для оптимального невырожденного плана y1 = 0, ..., ym = 0. Тогда x1, ..., xn будет оптимальным планом исходной задачи.

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

В связи с этим при ручном счете удобно сохранять буквенное значение M, считая, что это число больше любого другого числа, получаемого в процессе вычислений. При машинном счете число M нужно задавать. Если оно выбрано неудачно и в оптимальном плане Y 6= 0, то M следует резко увеличить и произвести счет еще раз.

Описанный прием является частным случаем так называемого метода штрафных функций. Для проведения вычислений нам понадобились новые величины y1, ..., ym, но в окончательном решении они не должны участвовать. Поэтому мы к исходной форме добавляем "штрафную"функцию - M(y1 +...+ym). Если в план вводится какая-либо величина yi,то приходится "платить колоссальный штраф"M(y1 + ... + ym), и величина формы от этого уменьшается. Таким образом, вводить yi 6= 0 в план становится невыгодным, поэтому в оптимальном плане все yi = 0.

ЗАДАНИЕ I

Решить систему линейных уравнений методом Гаусса-Жордана.