15.8. СИМПЛЕКСНЫЙ МЕТОД

Требуется отыскать неотрицательные значения А,3>0 (5 = 1,2, .

z = c1X1 + c2X2+ ... +спХп (1)

при условии

^1Ра) + ^Р<г>+...+Япр<п) = р. (2)

Допустимое решение удовлетворяет условию (2), но не должно обязательно максимизировать также и выражение (1). В соответствии со свойством 1 раздела 15.7, такие решения образуют выпуклое множество Г. Множество Г имеет экстремальные точки Е(1\ Е(2\ .. .,E(h\ и оптимальное допустимое решение, максимизирующее выражение z в соответствии со свойствами (2) того же раздела, совпадает с одной или с большим числом экстремальных точек Е{1\ Ei2\ . . ., Eih\ Следовательно, чтобы решить задачу линейного программирования, необходимо сосредоточить внимание на экстремальных точках, порождающих множество Г. При этом нужно иметь в виду две возможности: либо максимум достигается только в одной экстремальной точке, которая в этом случае есть единственное решение задачи; либо максимум достигается в нескольких экстремальных точках, и в этом случае существует бесконечное множество решений во всех точках % выпуклой оболочки, порожденной этими несколькими экстремальными точками.

Свойство III раздела 15.7 заставляет обратить внимание на еще одну особенность экстремальных точек множества Г, а именно на число положительных весов вектора % = (А^, .. ., Хп) экстремальной точки. Это число может быть меньше т\ тогда имеющие положительные веса векторы р(Г) (г = 1, 2, .. ., к) будут линейно независимы (к < га). Более полезен другой случай, когда число положительных весов равно как раз т: тогда линейно независимые значения р(г) (г = 1,2, . ..,га) образуют базис га-мер-

т

ного пространства, и всякое p(s) можно представить в виде p(s) = 2 ?rsP(r).

r= 1

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

% — Я2, ..., 0, 0, ..

где Кг > 0 (г — 1,2,..., т). Тогда значения р(г) — линейно независимы, и

т

Р=2М>(г> (К > °) (3)

Т— 1

И

m

p(s)=2 *rsP(r) (* = 1,2, ...,n). (4)

Г= 1

Выражение z принимает при этом соответствующее (не обязательно максимальное) значение:

m

*о=2 СА- (5)

г= 1

Введем переменные

771

zs = 2 сЛз (s=l. 2, . (6)

г= 1

После этого будем искать новое допустимое решение в одной из экстремальных точек множества Г. Для этого выбрасываем р(г), где г выбрано из значений 1, 2, ..., т, и включаем p(s), где s берется из числа значений (т+ 1), (га+ 2), ..., п. Подстановка должна быть такой, чтобы значение переменной z превысило значение z0. Таким образом, перебирая одну за другой все экстремальные точки множества Г, мы приближаемся к максимуму z, то есть к оптимальному допустимому решению (или к одному из бесконечного числа таких решений).

Задача, состоит в следующем: как выбрать г, подлежащее исключению, и 5, подлежащее включению. Пусть 0 —некоторый постоянный коэффициент. На основе уравнений (3) и (4) можно записать, что

т т

Р=2 V-0р<г> + ерш = 3 (К-Р<г>+0p(s)- (7)

r=i r=1

В качестве 0 возьмем Q = 'kr/xrs, так что г-ж член в уравнении (7) исчезает, и остается только т членов. При условии, что 'кТ — 0яГ5>О и 0>О, совокупность коэффициентов уравнения (7) представит новое допустимое решение, и, в соответствии с уравнениями (5) и (6), новое значение z определяется уравнением:

m

ст (К-Є*„) + 0с8 = + 0(cs — zs). (8)

г=1

Следовательно, если 0 > 0 и cs > za, то, судя по уравнению (8), проделанная нами подстановка позволила получить улучшенное решение (zo > zo)- Значит, выбирать г и s нужно так, чтобы

б = Т^>0' и cs-zs> 0, (9)

S

где г —любое число в ряду (1,2, . ..,иг), кроме г. При выборе г и s должно удовлетворяться два условия: 1)

По крайней мере одно -zs = т?г + 2, . .., п) должно быть положительным; при этом выбирается s для наибольшего cs — zs > 0, и удовлетворяется последняя часть условий (9). 2)

По крайней мере одно ъз xrs (г = 1, 2, .

При этих условиях мы получаем улучшенное решение, исключив р<г) и включив p в исходную систему линейно независимых точек р(г) (г = 1,2, . . ., т). Более того, новая система также линейно независима, так как она снова соответствует экстремальной точке множества Г. Чтобы удостовериться в этом, предположим, что точки пронумерованы так, что мы исключаем р*1) и добавляем р^^И-1), то есть что г = 1, s = m-\-l. Тогда, в соответствии с уравнением (4), если новая система р<2>, р<3>, . . р(™-И) линейно зависима, то

т

p(m+l)=2 ®Km+l)P(r)

г= і

И

т

р(™+1) = 2 ^pCr).

r= 2

Вычтем первое равенство из второго:

т

Zl(m+l)P(1) = S Х,(т+1))

г—2 .

Но исходная система была линейно независимой, и р*1) не может представлять собой линейную комбинацию остальных точек системы, как теперь указано. Невозможно и жі(т+і) = 0» Так как г — 1 выбиралось из числа положительных xr(m-j-i). Значит, новая система не представляет собой линейно зависимую систему; она линейно независима.

Следовательно, можно прийти к выводу, что, если удовлетворяются условия (1) и (2), то в таком случае можно улучшить первоначальный выбор % и значение z0; мы получаем новое допустимое решение, также соответствующее экстремальной точке множества Г, и большую величину z0. Полученное решение явится отправной точкой для повторения тех же операций. Весь процесс итерации от выбранной исходной точки может быть повторен сначала; при этом возвращения к ранее полученным решениям никогда не происходит, так как значение z на каждом шаге возрастает. Если не считать рассматриваемого далее случая вырождения, необходимость в прекращении процесса может возникнуть лишь по той причине, что на каком-то шаге перестают удовлетворяться условия (1) и (2). А это значит, что максимальное допустимое решение уже получено.