Основы исследования операций том 1 - Вагнер Г

число симплекс-итераций, которое приводило бы к решению любой задачи линейного программирования.

Рис . 4.6.Итерация 3: включение х3 в очередной базис (согласно критерию Ш.

Как и в предыдущих итерациях, пронормируем коэффициент при х3 в строке 3 путем деления обеих частей соответствующего уравнения на 7 /i2Система уравнений примет вид

При выполнении данной итерации была принята во внимание специфика вычислительной процедуры, предусмотренная критерием II. Если бы мы попытались исключить из пробного базиса переменную с отрицательным коэффициентом (таковой, согласно табл. на рис. 4.6, является х6), то переменная х3 могла бы принимать только отрицательные значения. По условию задачи это недопустимо. Следовательно, при наличии отрицательного коэффициента в той или иной строке процедура замены базиса должна выполняться с учетом соответствующего требования критерия II. Аналогично оказывается

Резюме. В кратком изложении симплексный метод состоит в следующем:

Шаг 1. Выбирается исходный базис.

Шаг 2. Используется критерий I. Если рассматриваемое пробное решение не является оптимальным, осуществляется переход к шагу 3. В противном случае вычисления прекращаются.

Шаг 3. Выполняется процедура, предписанная критерием II. Шаг 4. Сменяется базис, после чего возвращаются к шагу 2. Вычислительные процедуры, выполняемые в соответствии с сим- плекс-алгоритмом, легко интерпретировать геометрически в пространстве решений. При этом каждый пробный базис соответствует вершине выпуклого полиэдрального множества допустимых решений. Переход от одного базиса к другому геометрически выглядит как переход от одной экстремальной точки к другой (причем смежной) экстремальной точке. Таким образом, можно утверждать, что поиск оптимального решения симплексным методом заключается в после-

довательном восхождении вдоль ребер упомянутого многогранника от одной его вершины к соседней.

Оптимальность. Доказательство того, что полученное решение действительно является оптимальным, не вызывает никаких трудно-

уравнений (1) внесены следующие изменения:

С помощью простых вычислений можно показать, что на заключительной итерации мы будем иметь следующие дополнения к строкам системы уравнений (7):

Qx8 (строка 0),

9 8

+ -^-xs (строка 1),

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

при xi = х2 = xk = х5 = х7 = 0. Легко показать, что любое поло- жительно-взвешенное среднее двух полученных оптимальных базисных решений также является альтернативно допустимым оптимальным решением

__ 695

хй —• у 1

—

где w — весовой коэффициент, удовлетворяющий условию 0 < w <

равное в95/7.

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

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

4.5. ПОЛНОТА АЛГОРИТМА

При некоторых итерациях вычислительные процедуры, предписанные симплекс-критериями I и II, в части, касающейся перехода от одного базиса к другому, могут оказаться неоднозначно определенными. Например, когда в результате оценки коэффициентов

встроке 0 две или более двух переменных являются по критерию 1

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

Если, согласно критерию II, две или более двух переменных промежуточного базиса должны одновременно принять нулевые значения в силу включения в очередной базис новой переменной, из старого базиса исключению^тодлежит только одна из них. Другие из упомянутых переменных остаются в базисе, принимая при этом нулевые значения. Базис, получаемый в результате такой замены, называется вырожденным. Как показано в разд. 4.7, полное устранение неоднозначности в вычислительных процедурах сопряжено с большими трудностями теоретического характера.Шока специально не оговорены правила выбора переменных, подлежащих исключению из базиса, сходимость симплекс-алгоритма не может быть строго доказана. Однако многочисленные случаи применения симплексного метода приводят к заключению, что при решении любой практиче-

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

Если на этапе применения критерия II при выполнении какойлибо итерации обнаруживается, что ни в одну из строк переменная, включенная в очередной базис, не входит с положительным коэффициентом, то оптимальное решение является неограниченным. В этом случае значение новой базисной переменной можно (без нарушения условия неотрицательности остальных переменных) выбирать сколь угодно большим, что приводит к неограниченному возрастанию значения целевой функции.! Таким образом, сделанное ранее предположение относительно ^ограниченности оптимального значения целевой функции можно теперь отбросить. Симплексный алгоритм сам позволяет определять те случаи, когда оптимальное решение оказывается неограниченным. Чтобы учесть данное обстоятельство, формулировку критерия II следует надлежащим образом видо-

введение в рассмотрение свободных переменных (по одной свободной переменной в каждом соотношении, задающем соответствующее ограничение) и включение только этих переменных в исходный базис позволяет просто выполнить шаг 1 (т. е. построение первого пробного решения). Как было показано в гл. 2, соотношением (1) не охватываются все возможные типы ограничений, встречающихся в линейных оптимизационных моделях. Однако анализ, проведенный в гл. 3, дает основание утверждать, что[в задачах линейного программирования ограничения любого вида можно записать в

Если при этом некоторая переменная входит только в j-e соотношение, причем с коэффициентом, равным единице (как это имеет место для каждой из свободных переменных), то ее можно включить

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

*) Такая ситуация может, в частности, возникнуть в том случае, когда

г-е уравнение линейно зависит от одного или нескольких других уравнений. (Например, если г-е уравнение представляет собой сумму двух других урав-

нений.)

146 ГЛАВА 4

Запишем ограничения в виде

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

Условие А. Чтобы окончательное решение имело смысл, каждая искусственная переменная yt на заключительной симплекс-итерации должна обращаться в нуль.

Если ограничения таковы, что задача не имеет допустимых решений, удовлетворить условию А окажется невозможным: на последней симплекс-итерации по крайней мере одна из переменных yf войдет в базис с положительным значением, что означает несовместность условий задачи. Таким образом, предположение о существовании допустимого решения, сформулированное в разд. 4.4, оказывается излишним. Если задача не имеет ни одного допустимого решения, то это можно определить с помощью симплексного алгоритма^

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

Следует отметить, что большинство современных машинных программ, реализующих симплексный алгоритм, составлено таким образом, что нет необходимости представлять каждое из ограничений в форме (2). Другими словами, все содержащиеся в модели ограничения могут быть использованы в их первоначальной записи. Добавление свободных и (если это необходимо) искусственных переменных, а также выполнение условия А обеспечиваются автоматически программным путем. Для некоторых программ пользователем может даже быть задан конкретный набор переменных, предназначенный для формирования исходного базиса. Этот прием называют сдвигом стартовой точки; он служит для сокращения числа требуемых итераций. Существуют другие (аналогичного характера) приемы, позволяющие предварительно определить те переменные, которые вероятнее всего войдут в базис на заключительной итерации. Умелое применение различного рода вычислительных «трюков», ускоряющих процесс сходимости, является одним из проявлений искусства практического использования симплексного алгоритма.

1) Для простоты мы предположили, что свободные переменные нужно ввести во все ограничения.

Метод «больших штрафов». Выполнение условия А можно обеспечить различными вычислительными приемами. Несмотря на то что эти приемы для специалистов в области исследования операций, вообще говоря, представляют определенный интерес, мы не будем углубляться в их изучение и ограничимся изложением одного простого и весьма грубого подхода.

Добавим к подлежащей максимизации целевой функции сумму всех искусственных переменных г/^ с общим коэффициентом, значение которого выберем достаточно большим:

пт

Коэффициент М имеет смысл отрицательной удельной прибыли.

Начнем реализацию алгоритма с исключения из (4) всех переменных yt. С помощью формулы (3) получим

Если существует хотя бы одно допустимое решение, то сам метод оптимизации автоматически приводит к тому, что в итоге все переменные yt обращаются в нуль. (Следует, кстати, отметить, что если на некоторой итерации одна из переменных г/, оказывается исключенной из базиса, то при последующих итерациях необходимость в использовании этой переменной отпадает, т. е. при всех дальнейших вычислениях данная переменная не принимается во внимание.)

Предлагаемый метод можно пояснить с помощью простого при-

Введем теперь искусственные переменные у\ и г/2 и положим М = 10. В результате будем иметь

Приступая к вычислениям в соответствии с симплексным алгоритмом, прежде всего исключим из (12) yt и у2 путем вычитания строк 1 и 2, умноженных на 10 (М = 10), из строки 0:

Нахождение оптимального решения для рассматриваемой модели предлагается читателю.

4.6. ОБЛАСТЬ ПРИМЕНИМОСТИ

Многие задачи линейного программирования сводятся к минимизации некоторой линейной функции. Как установлено в разд. 3.2, задача минимизации переходит в задачу максимизации, если изменить знаки при всех коэффициентах в выражении для целевой функции. По отношению к полученной таким образом линейной форме критерий I (максимизация) по-прежнему оказывается применимым. Однако для целей дальнейшего рассмотрения представляется целесообразным сформулировать критерий I и на тот случай, когда решается задача минимизации при сохранении целевой функции в ее первоначальном виде.

С и м п л е к с - к р и т е р и й I ( м и н и м и з а ц и я ) . Если в строкеJJ имеются небазисные переменные, коэффициенты при которых положительны, то следует выбрать переменную (обозначим ее через Xj) с наибольшим положительным коэффициентом. В случае когда все небазисные переменные строки ,0 имеют отрицательные или нулевые коэффициенты, оптимальное решение можно считать полученным.

Данную процедуру можно пояснить с помощью примера. Рассмотрим следующую тривиальную задачу линейного программирования:

Можно приступить к решению этой задачи, изменив вначале как знаки в выражении (1), так и «смысл» оптимизации, т. е. написав вместо (1):

женным в предыдущем разделе, мы начали бы итерационный процесс

В этом случае был бы применим критерий I (минимизация) и на самой первой итерации переменная xt была бы выбрана в качестве базисной, так как в строке 0 коэффициент при х^ равен -\-2.

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

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

1)симплексный алгоритм применим ко всем линейным оптимизационным моделям;

2)ответ, полученный в результате заключительной итерации, является точным решением задачи.

Мы пока не установили, может ли симплексный метод привести

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