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),где Кг > 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, .
. ., т) должно быть положительным; при этом г выбирается (из числа г, для которых xrs положительно) так, чтобы минимизировать Q = 'kr/xrs и удовлетворить два первых ограничения системы (9).При этих условиях мы получаем улучшенное решение, исключив р<г) и включив 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). А это значит, что максимальное допустимое решение уже получено.
Нетрудно заметить, что либо перестает удовлетворяться условие (2), и все значения #rs<0, так что величина z становится бесконечной, либо перестает удовлетворяться условие (2), и все cs — zs<0, в этом случае фиксируется некоторый конечный максимум z, то есть экстремальная точка h является искомым оптимальным допустимым решением.Итеративный метод неприменим на практике лишь в том случае, если на каком-то шаге допустимое решение % имеет менее ш положительных весов. Это — случай вырождения. Выход из этого затруднения (позволяющий применять симплексный метод во всех без исключения случаях) предложен Чарнесом [1] и приводится в книге Чарнеса, Купера и Гендерсона [2].
Отметим, наконец, что любая двойственная задача линейного программирования также может быть приведена к канонической «симплексной» форме уравнений (1) и (2). Следовательно, двойственную задачу также можно решать симплексным методом. Однако ясно, что прямая и ее двойственная задачи столь тесно между собой связаны (например, значение максимума в одной совпадает со значением минимума в другой), что можно рассчитывать при однократном применении этого метода получить сразу решения обеих задач. И, действительно, дело обстоит именно так, что иллюстрируется на частном примере, приведенном в разделе 15.9. При использовании симплексного метода Ь этом примере на последнем шаге, когда достигнут некоторый конечный максимум, все cs — zs < 0. Противоположные по знаку величины (то есть ze—cs), полученные окончательно для дополняющих переменных, являются оптимальными значениями переменных в решении двойственной задачи.
Еще по теме 15.8. СИМПЛЕКСНЫЙ МЕТОД:
- Глава 13. Гипотетико-дедуктивный метод
- Методы культурологических исследований:
- 8 СОВРЕМЕННЫЕ МЕТОДЫ КОНТРОЛЯ ЗАГРЯЗНЯЮЩИХ ВЕЩЕСТВ В ОКРУЖАЮЩЕЙ ПРИРОДНОИ СРЕДЕ
- ВСТУПИТЕЛЬНАЯ СТАТЬЯ
- 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
- 15.8. СИМПЛЕКСНЫЙ МЕТОД
- 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
- 17.7. ПАРАДОКС РИКАРДО
- 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА