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

линейного программирования; эта форма приспособлена для решения задачи с помощью модифицированного симплекс-метода.

Как отмечалось, мы получаем первоначальное решение, полагая, что переменные, соответствующие единичной матрице, равны соответ­ ствующим компонентам вектора Ь. В примере, приведенном на стр. 224,

xs 1 = 8;

X S 2 = 7.

Те столбцы Л*, которые порождают это решение, могут быть найдены из следующих уравнений:

Первый шаг в таких задачах всегда начинают с базиса В = /, кото­ рому соответствует решение Хв = В~гЬ = I^ b = b. Поскольку b не­ отрицателен, а все остальные (небазисные) переменные равны нулю, это решение удовлетворяет ограничениям на неотрицательность.

Прежде чем продолжить описание, введем некоторые важные для модифицированного симплекс-метода обозначения. Рассмотрим по­ полнение матрицы В: поместим взятые с обратным знаком коэффициен­ ты целевой функции, связанные с базисными переменными, над соот­ ветствующими столбцами матрицы В и добавим первый столбец, у ко­ торого первый элемент равен 1 , а остальные т элементов равны нулю. Обозначим эту пополненную матрицу через В*, здесь звездочка ука­ зывает, что соответствующая матрица расширена. Таким образом,

Этот расширенный базис теперь дает нам возможность вычислить те­ кущее значение целевой функции z : z —c'BxB. Таким образом, мы можем получить это значение на каждом шаге модифицированной симплекспроцедуры. По-прежнему с помощью обозначений со звездочкой для расширенных матриц (и векторов) можно показать, что

245

соответствующий столбец индексом k; именно этот столбец (перемен­

a | = В*->

at

®m+ l,~_k

4. Тот из столбцов (переменных) текущего базиса, который должен быть изъят из него, определяется при нахождении такого значения г, при котором достигается минимизация:

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

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

вы V.

2 4 6

где матрица F, приведенная далее, получена из единичной матрицы путем замены l-то столбца на столбец, состоящий из элементов вида

aih ( , „ 1 \

— |^за исключением 1-то элемента, который имеет вид — j

После получения х%. нов и В нов1 вернуться к этапу 2.

Сейчас мы кратко прокомментируем перечисленные этапы. Этап 1 дает нам допустимое решение (х = 0), с которого мы начинаем. Этап 2 проверяет предельные вклады*, связанные с единицей каждой из не­ базисных переменных. Если затраты на те ресурсы, которые такая единица забирает от других переменных (с'вВ^а*), меньше, чем прибыль (cj), то выражение свВ~га* — cj будет отрицательным, и переменную следует ввести в базис. Если таких переменных нет, то мы не можем улучшить значение целевой функции и процедура заканчивается.

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

*В значение целевой функции. — Прим, перев.

247

где р; ■— i-й столбец В. Следовательно, из последних т элементов a k на третьем этапе мы получаем нормы замещения входящей переменной каждого из элементов в текущем решении х%, т. е. вектор, состоя­ щий из элементов а к, показывает, насколько надо сдвинуть каждую из базисных переменных, чтобы ввести в решение единицу новой пе­ ременной. На этапе 4 сохраняется положительность всех перемен­ ных хв', это достигается выбором такой переменной, уходящей из ба­ зиса, которая первой достигает нуля, когда вводимая переменная на­ чинает принимать положительные значения. Для этого проверяют зна­ чения базисных переменных, поделенные на соответствующие элемен­ ты a k, которые тем самым показывают, как быстро каждая из базис­ ных переменных смещается к нулю при введении новой переменной.

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

Пример. Мы продемонстрируем сейчас применительно к примеру, приведенному на стр. 228, ход реальных вычислений и таблицы, ис­ пользуемые в модифицированном симплекс-методе:

максимизировать z = 20лу + 20ха

при условии, что Злу + 2лу + jcsi = 8,

2лу + Зха + Xsi = 7,

лу, х2, xSl, xS2 > 0.

3 2 1 0

Этап 1. Выбор единичной матрицы из Л*

.2 3 0 1.

достигается при x;si = 8, xSa — 7.

Перем енны е в текущ ем расш иренном бази се

Этап 2. По столбцам 1 и 2 матрицы Л* мы вычисляем с'вВ~1а* —

— с}, где свД-1 = [0 0] указаны в приведенной таблице. Таким обра­ зом, свВ^а*—сг = —20 и chB^al — са = —20. Получилось совпадение. Мы выбираем для нового базиса переменную лу (можно было выбрать любую из этих двух переменных).

2 4 8

3. Таким образом, мы должны вывести из базиса первую базисную пе­ ременную, а именно xsi и соответствующий ей второй столбец матри­ цы В*-, alk = а 21 = 3.

Этап 5. Подставляя соответствующие величины вместо элементов столбца 2 единичной матрицы, получаем следующую матрицу F:

Сейчас мы получили решение задачи, использовав в базисе пере­ менные хх и Xsi, переменная xsi была выведена из базиса. При усло­

249