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

А 5-е ограничение и ось х₂ ^хз, ^х$, ^х\ ^х2, ^х4, ^х5, ^хб, ^х7

В 3-е ограничение и ось х₂ х_ь х₆ х₂, х₃, х₄, х₅, х₇, х₈

С 3-е и 4-е ограничения х₆, х-/ Х\, х₂, х₃, х₄, х₅, х₈

Б 4-е и 2-е ограничения х₇, х$ х_{, х₂, х_}, х₄, х₆, х_я

Е 2-е и 1-е ограничения х₅, ^х4 ^хь ^х2> ^хг> ^хб, ^хт, ^хв

Р 1-е и 5-е ограничения х₄> х₃, х_й х_и х₂, х₅, х₆, х₇

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

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

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

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

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

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

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

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

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

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

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

4. Величины С_ь /= \,..., т из третьего столбца равны соответ­ствующим коэффициентам Су при базисных переменных в кано­ническом представлении целевой функции.

5. Значения базисных переменных А_ю, /= \,..., т берутся в со­ответствии с опорным решением. Столбец А_ю иногда называют столбцом свободных членов (имея в виду, что он формируется из правых частей исходной системы ограничений).

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

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

т _

(^-С_у)=ЕС^-С,, у=а1,...Д _(14Л7)

где Ср ]= 1,..., 8 — коэффициенты при соответствующих переменных в выражении для целевой функции в каноническом представлении; С₀ = 0.

Оо -с

68. Первая симплекс-таблица задачи 14.5

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

Назначение двух последних столбцов симплекс-таблицы будет пояснено ниже. Нулевой элемент индексной строки (2" ₀ — С₀) равен значению целевой функции на данной итерации симплекс-метода.

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