Вопрос14

ОСНОВНЫЕ ЭЛЕМЕНТЫ СИМПЛЕКС-МЕТОДА

Для перехода к аналитическому описанию направленного no-Hi mi оптимального решения общей задачи линейного програм-мнропания дадим аналитическое описание вершин области допу-ниммх значений. Выше мы уже отмечали, что каждой грани ijoll области отвечает нулевое значение одной из переменных Дополнительной или основной). Поскольку (в рассматриваемой

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

67. Характеристика вершин области допустимых значений задачи 14.5

всегда может бы и, приравнена к нулю, так как 5-е ограничение из системы (14.15) и этой области можно удовлетворить, подобрав соответствуют'! неотрицательное значение избыточной переменной х3. Поэтом \ в пределах области допустимых значений искусственные перс меиные можно исключать из рассмотрения.

Нетрудно заметить следующую особенность: в рассматривае­мой задаче имеется пять ограничений (не считая условий нео трицательности) и семь основных, остаточных и избыточных пе­ременных; количество ненулевых переменных, не считая искус ственную, в каждой вершине равно именно пяти, а количество нулевых (7 — 5) ~ 2. В общем случае, если в задаче т ограничении и п основных, остаточных и избыточных переменных, то каждой вершине области допустимых значений соответствует т ненулс вых переменных и (п-т) нулевых. Как уже указывалось ранее, такое решение называется допустимым базисным решением, а не­нулевые переменные в нем — базисными.

Посмотрим теперь, как меняется допустимое базисное реше ние (далее будем говорить просто «базисное») при переходе от данной вершины области допустимых значений к соседней. Ис кусственные переменные, как уже отмечалось, мы не будем при нимать во внимание. Из таблицы 67 видно, что при таком пере­ходе только пара переменных меняется местами. Например, при переходе от вершины А к вершине В переменная х^ переходит н базис, а переменная х3 выводится из базиса. Это свойство сосед­них вершин и было положено в основу вычислительного алго­ритма симплекс-метода.

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

Горону роста целевой функции (если задача решается на мак-

В каноническом представлении исходное (опорное) решение лачи определяется элементарно: все основные и избыточные ременные приравниваются к нулю, а остаточные и искусствен-це приравниваются к правым частям соответствующих ограни-пий. Поскольку такое решение включает ненулевые значения скусственных переменных, на первых шагах алгоритма они не лжны исключаться из рассмотрения. Отметим также, что по-ольку при этом Xi = х2 = 0, опорное решение соответствует на­лу координат. Далее общее число ограничений обозначим сим-Лом т, а общее число переменных на данном шаге алгоритма — 1мволом п. Таким образом, для рассматриваемой демонстраци-шои задачи на первом шаге т = 5, я « 8.

IBce расчеты удобно проводить в так называемых симплексных аблицах, первая из которых (табл. 68) соответствует опорному

мнению.

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

канонического представления).

1. Первая строка таблицы содержит коэффициенты Cj, Jpl,...,8 при неизвестных в каноническом представлении целе­вой функции (14.14).

2. Первый столбец — это просто сплошная (от 1 до т) нумера­ция переменных, попавших в базис. Этот столбец сохраняется

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

3. Второй столбец содержит список базисных переменных.

4. Величины Q, '= 1,--,т из третьего столбца равны соответ-• i мующим коэффициентам Су при базисных переменных в кано­ническом представлении целевой функции.

5. Значения базисных переменных А$>, i~ l,...,m берутся в со-«чистствии с опорным решением. Столбец An иногда называют

[столбцом свободных членов (имея в виду, что он формируется из правых частей исходной системы ограничений).

6. В качестве коэффициентов замещения Аи берутся соответ-i i кующие коэффициенты при переменных из системы ограниче­ний в канонической форме (смысл термина «коэффициент заме­щения» будет подробно анализироваться в гл. 16).

7. Элементы индексной строки вычисляются по формуле

(14.17)

1=1

где Q,y™ 1,...,8 —коэффициенты при соответствующих переменных в выражении ДЛЯ целевой функции в каноническом представлении; Q = 0.

аметим, что принятое в каноническом представлении целе-функции буквенное обозначение коэффициента при искус-нных переменных сохранено в симплекс-таблице. В связи с например, второй элемент индексной строки равен вели-е (-800-40М).

азначение двух последних столбцов симплекс-таблицы будет нено ниже. Нулевой элемент индексной строки (7$- Со) равен •нию целевой функции на данной итерации симплекс-метода, терационная процедура симплекс-метода сводится к после-цельному преобразованию симплекс-таблиц, что (после ис-■чения искусственных переменных —см. ниже) соответствует ледовательному переходу от одной вершины симплекса к дру-. На каждой итерации выполняется несколько шагов; рас-трим их подробнее.

Шаг 1. Оценка решения, представленного данной таблицей, на мальность и, если оптимум не достигается, поиск переменной, мой в базис.

Указанные операции осуществляются на основе анализа всех ментов индексной строки, соответствующих небазисным пе-Менным. Если все эти элементы неотрицательны в задачах на ксимум (неположительны в задачах на минимум), то данное ре-•ние оптимально и соответственно вычислительный процесс пре-щается. В противном случае в задачах на максимум ищется ^больший по абсолютной величине отрицательный элемент (в ачах на минимум — наибольший положительный элемент), '.временная, вводимая в базис, соответствует именно этому эле-юнту. Соответствующий столбец называется ключевым {главным, ^решающим) столбцом. В таблице 68 такой столбец выделен за-нением.

Для понимания смысла действий на первом шаге следует 1есть, что каждый элемент индексной строки, взятый с обрат­им знаком, показывает, насколько изменяется значение целе->й функции при изменении соответствующей переменной на ■иницу. Значит, если в задачах на максимум все рассматривае­те элементы индексной строки неотрицательны, то при вве-рнии любой небазисной переменной в базис (то есть при при­дании ей какого-либо положительного значения) значение це-Бвой функции либо не возрастет (если соответствующий эле-чгпт равен нулю), либо даже уменьшится (если элемент Положителен). Это и означает, что мы достигли оптимума — Ьльше нет возможности увеличить значение целевой функ­ции. Если же среди элементов индексной строки есть отрица­тельные (случай максимизации целевой функции), то это озна-чиет, что, придавая соответствующей небазисной переменной положительное значение (вводя ее в базис), мы можем повы-ить значение целевой функции; при этом чем больше элемент и абсолютной величине, тем быстрее будет расти целевая фун-

кция с ростом переменной. Именно поэтому при решении чи на максимум каждая очередная итерация начинается с bi ра наибольшего по модулю отрицательного значения элемеш | индексной строки.

В рассматриваемом примере вводимой в базис является пе|х менная х2 (см. первую симплекс-таблицу). Геометрически это <н начает, что мы движемся по оси х2 от начала координат (где и ременная х2 равна нулю) к вершине А (см. рис. 17).

Шаг 2. Определение выводимой из базиса переменной.

Рассмотрим сначала геометрическую интерпретацию этого шага.

При движении по оси х2 от начала координат первой встречи ется вершина А. В ней сходятся грани АВ и AF, а значит, в ней нулевой является не только переменная щ, но и переменная \N Следовательно, именно переменная х$ должна быть выведена и i базиса (см. табл. 67).

Общее правило выбора выводимой из базиса переменной фор мулируется следующим образом: выводиться должна переменили текущего базиса, которая раньше других обращается в нуль при возрастании вводимой в базис переменной. Для ее определении следует разделить значения элементов столбца Аю на cootbci ствующие положительные элементы ключевого столбца Ащ. В рас­сматриваемом примере результаты деления показаны в предпос леднем столбце первой симплекс-таблицы. Ту строку, в котором результат деления оказался минимальным, называют ключевой (главной, разрешающей) строкой; базисная переменная, располп женная в этой строке, подлежит выводу из базиса (в рассматрп ваемом примере — переменная ,v8; в таблице 68 ключевая строка выделена затенением). Элемент симплекс-таблицы, лежащий на пересечении ключевого столбца и ключевой строки, называю! ключевым (главным, разрешающим) элементом.

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

хц = А50 - Аьгх2 + 400 - 40*2, (14.18)

где Asq~ базисное значение переменной лг8 (см. первую симплекс-таблицу); Ац — коэффициент замещения базисной переменной д:к на небазисную переменную х2.

Формула (J4.18) достаточно наглядно иллюстрирует смысл термина «коэффициент замещения». Из нее прямо следует, что именно при

Х2 = А50/А52 = 400/40 = 10

(14.19)

(ременная х8 обращается в нуль (замещается вводимой пере­стой х2). Аналогичные формулы можно записать и для других зисных переменных. Их совместный анализ и приводит к ука-шому алгоритму.

Описанная процедура позволяет сразу найти значение новой иеной переменной. Действительно, коль скоро выгодно дос-и. максимально допустимого значения вводимой в базис пере-иной (в данном случае х2), то искомое значение определится рмулой (14.19). Дальнейшее увеличение х2 нарушит условие угрицательности переменной *8, что следует из формулы .18).

Шаг 3. Частичная замена базиса.

Суть этого шага состоит в исключении из базиса переменной, •гоящей в ключевой строке, и записи на ее место новой пере-Ънной, стоящей в ключевом столбце.

Шаг 4. Расчет всех элементов новой симплекс-таблицы.

Расчет новых значений элементов ключевой строки проводит-

по формуле

А?' — ключевой элемент.

В рассматриваемом примере (табл. 68) А™ =40. Соответствен­но новые элементы ключевой строки будут равны:

^0=400/40=10; А$Х=Ъ\ ^52=^0/40=1; Л$3=-1/40=-0,25; А^4=0; А^0; ^6=0; ^7=0; ^=1/40=0,025.

Вычисление новых значений элементов в остальных строках симплекс-таблицы, включая индексную, производится по фор­муле

Где Аи — значения злемента преобразуемой /-й строки, расположенного в клю-

Г| к.1

Чевом столбце; А\ у- — элементы преобразованной ключевой строки.

Для примера проведем вычисления элементов 2-й строки:

^20 =12000-50 10-11500; ^^-5-500-5; ^2=50-50-1-0; Лгз=0-50-(-0,025)=1,25; ^4 =0-50-0=0; 4fo*l-50-0-I; ^26=0-50 0=0; ^7 = 0-50-0=0; ^28 =0-50-0,025=-1,25.

После всех преобразований все коэффициенты замещении расположенные в ключевом столбце, кроме ключевого эдемам* должны быть равны нулю; ключевой элемент будет равен I результате получим новую симплекс-таблицу (табл.69). В мне таблице, как и в последующих, ключевая строка и ключами столбец выделены.

Анализ второй и последующих таблиц проводится по том || схеме. Кроме того, в этих таблицах проводится анализ разлит, ния искусственных переменных. Если на данной итерации какни либо искусственная переменная перешла в число небазисных, ш она должна быть исключена из дальнейшего рассмотрения. Флъ тически это делается путем вычеркивания из полученной сими лекс-таблицы столбца, соответствующего искусственной пс|« менной, ставшей небазисной. В целях упорядочения итерациин ной процедуры симплекс-метода такое вычеркивание целесооь разно считать самостоятельной итерацией. Для рассмгп риваемого примера вычеркивание единственной искусственно!! переменной х8, ставшей небазисной, зафиксировано в переход от таблицы 69 к таблице 70.

Преобразование таблиц заканчивается, если на очередны) итерации достигается оптимальное решение (см. выше описанш шага 1). Четвертая и пятая (последняя) симплекс-таблицы дли рассматриваемого примера приведены в таблицах 71, 72.

Контроль вычислений можно осуществлять следующим обра зом.

1. Логический контроль изменения значений целевой функ ции: в задачах на максимум эти значения от итерации к итерации должны возрастать (не убывать), в задачах на минимум — убы вать (не возрастать).

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

3. Расчет дополнительного столбца симплекс-таблиц (м табл. 68—72 это последний столбец), в котором размещают конт­рольные суммы, определяемые по формуле,

В первой симплекс-таблице в этот столбец заносят суммы ко эффициентов по строке, включая столбец А®. При переходе к новой таблице эти коэффициенты пересчитываются по общим правилам (см. описание шага 4), причем эти пересчитанные зна­чения должны совпадать с суммами коэффициентов по соответ­ствующим строкам новой таблицы.