Файл: Сирл, С. Матричная алгебра в экономике.pdf

*Иначе говоря, первый ресурс полностью исчерпан. — Прим, перге.

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

250

уже достигли оптимального решения. Расчет с применением модифи­ цированного симплекс-метода теперь завершается при положительных значениях после возвращения к этапу 2.

Этап 2. с'вВ~г = [4 4], так что с'вВ~га%г — cSx = 4 и свВ ^ а ^ — cS2= = 4. Поскольку ни одно из значений не отрицательно, целевую функ­ цию нельзя улучшить; оптимальное решение получено. Приведем по­ следнюю таблицу:

х1 и х2\ г всегда будет оставаться в расширенном базисе и соответствен­ но первый столбец всегда будет содержать одну единицу и т нулей.

1На самом деле линейное программирование предлагает и другой способ обращения матрицы. Этот метод разбирается в упражнениях 8 и 9 данной главы.

251

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

хг = 0, х2 = 0; хх = д, х2 = 0; хх = 2, х2 = 1.) На этом процесс

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

в) МИНИМИЗАЦИОННЫЙ ВАРИАНТ МОДИФИЦИРОВАННОГО СИМПЛЕКСМЕТОДА

Этапы 1, 3, 4, 5 и 6 модифицированного симплекс-алгоритма, приведенные в разделе б параграфа 5, совпадают с этими же этапами при решении задачи на минимизацию. Введение искусственных пере­ менных дает возможность использовать на первом этапе решение, со­ ответствующее единичной матрице, а этапы 3, 4, 5 и 6 не связаны с це­ левой функцией. Этап 2, однако, подвергается следующим изменениям:

2'. Используя по очереди все небазисные столбцы а* матрицы А*, вычислите набор скалярных величин свВ^а*—cj, гдес^ —коэффициент затрат, соответствующий этой переменной (столбцу.) Выберите наи­ большее положительное значение, т. е. тах[с&8_1а; —- су>0] для опре­ деления переменной, которая должна войти в базис, и пометьте соот­ ветствующий столбец индексом k\ именно он войдет в базис. Если среди вычисленных значений нет положительных, значит текущее решение оптимально.

Этап 2' должен обеспечить убывание целевой функции на каждой итерации. Поскольку отыскивается минимум, то это именно то направ­ ление, которое нам нужно. Когда среди значений свВ^а*—сх уже нет положительных, больше нет возможности понизить значение целевой функции и текущее решение оптимально.

Теперь мы можем продемонстрировать минимизационный вариант модифицированного симплекс-метода при решении задачи из примера

252

Значение z получают из выражения 10000 X 70 + 10000 X 150; т. е. 2 = с'вХв (затраты по каждой из базисных переменных, умноженные на использованные их значения). Далее выполняют этап 2':

ев В - ' = [10000 10000];

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

a-ik —а 2Д = 0,5. Таким образом, xdl и соответствующий ему второй столбец’ В* будут удалены.

Новый базис включает хх и xd2- При этом мы все еще не находимся в области допустимых решений. Новая таблица имеет вид:

2 5 3