Математические методы исследования операций в экономике (стр. 10 из 37)

Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц T₁ и Т₂^(q). Таблица T₁ (рис. 1.7) является общей для всех итераций и служит для получениястроки оценок текущего базисного плана a₀(β^(q)). Если обозначить через δ_i(β^(q)) (i Î 0 : m) строки матрицы Δ^-1(β^(q)), то из (1.26), в частности, следует, что

Как видно из рис. 1.7, T₁ состоит из трех блоков:

-

в центре содержится матрицаА;

-

в левом блоке таблицы на каждой итерации дописываются нулевые строки матрицы Δ^-1(β^(q))для текущего базиса;

- нижний блок, расположенный под матрицейА, на каждой итерации дополняется строкой оценок текущего плана, вычисленной по формуле (1.42).

Симплекс-таблица Т₂^(q), изображенная на рис. 1.8, соответствует допустимому базису КЗЛП β^(q), получаемому наq-й итерации. Столбец N(β^(q)) содержит номера базисных столбцов (в последовательности вхождения в базис); столбец b(β^(q)) — компоненты вектора ограничений относительно текущего базиса β^(q); Δ^-1(β^(q)) — матрица, обратная по отношению к матрице расширенных столбцов текущего базиса β^(q); графа а^l содержит расширенный вектор условий, вводимый в базис на текущей итерации, а следующая графа — координаты а^l(β^(q))этого же столбца в текущем базисе β^(q).

По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.

0-этап. Нахождение допустимого базисного плана.

1. Для поиска допустимого базиса может быть применен метод минимизации невязок, рассмотренный в п. 1.4.5. При этом для решения вспомогательной задачи используется процедурамодифицированного симплекс-метода. В результате 0-этапа мы получаем допустимый базисный план x(β⁽¹⁾) и соответствующие ему матрицу Δ^-1(β⁽¹⁾)и вектор b(β⁽¹⁾).

2. Заполняем центральную часть таблицы T₁, содержащую матрицу А.

3. Содержимое матрицы Δ^-1(β⁽¹⁾)и вектора b(β⁽¹⁾), полученных на этапе поиска допустимого базисного плана, переносится в таблицу T₂⁽¹⁾.

4. Полагаем номер текущей итерацииq равным 1 и переходим к I-этапу.

1-этап. Стандартная итерация алгоритма — выполняется для очередного базисного плана x(β^(q)).

1°. Проверка оптимальности текущего базисного плана. Содержимое нулевой строки таблицы T₂^(q) — δ₀(β^(q)) переписывается в соответствующую графу таблицы T₁. По формуле (1.42) рассчитываем и заполняем строку a₀(β^(q)). Осуществляем просмотр строки оценок a₀(β^(q)). Возможны два варианта:

1΄. a₀(β^(q))≥0 —план, соответствующий текущему базису задачи, оптимален. Вычислительный процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х* =x(β^(q)) и оптимальное значение целевой функцииf(х*)=f(x(β^(q))).

1". В строке оценок a₀(β^(q))существует по меньшей мере один элемент a_0,j(β^(q))<0, т. е. имеющий отрицательную оценку. Следовательно, план x(β^(q)) —неоптимален. Выбирается номер l, соответствующий элементу, имеющему минимальную (максимальную по абсолютной величине) отрицательную оценку:

l-й столбец матрицы A становится ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.

2°. Определение столбца, выводимого из базиса. Переписываем ведущий столбец а^l из таблицы T₁ в текущую таблицу Т₂^(q). По формуле а^l(β^(q)) = Δ^-1(β^(q))а^l заполняем соответствующий столбец в таблицеТ₂^(q). Возможны два варианта:

2'. Для всехiÎ 1: mа_i,l(β^(q))≤0. Делается вывод о неограниченности целевой функции и завершается вычислительный процесс.

2". Существует по крайней мере один индексiÎ 1: m, для которого а_i,l(β^(q))>0. Согласно правилу (1.27) определяются место r и номерN_r(β^(q)) для столбца, выводимого из базиса. Переходим к пункту 3° алгоритма.

3°. Пересчет относительно нового базиса элементов столбца bи матрицыΔ^-1. Переход к новому базисуβ^(q+1), который получается введением в базис β^(q) столбца а^l и выводом из него столбца а^r, осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:

Полагаем номер текущей итерацииq: =q+l и переходим к первому пункту алгоритма.

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

1.5.2. Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5,2,3}. Для него уже были вычислены Δ^-1(β^(q)) и b(β^(q)), поэтому заполнение начальных таблиц T₁ и Т₂⁽¹⁾ не представляет труда.

На первой итерации мы переписываем нулевую строку

из Т₂⁽¹⁾ вT₁ и, умножив ее на матрицу A, получаем строку оценок

Так какa₀(β⁽¹⁾) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β⁽¹⁾, и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l =4.

Переписываем столбец

из таблицы T₁ в Т₂⁽¹⁾ и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ^-1(β^(q)), расположенную в таблице Т₂⁽¹⁾ слева, на а⁴.

После заполнения таблицы Т₂⁽¹⁾ данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов b_i(β⁽¹⁾) и a_i,l(β⁽¹⁾) для {iÎ1:m| a_i,l(β⁽¹⁾)>0} и определив минимальное из них, находим, что r =2. Следовательно, столбец с номером N₂(β^(q)) =2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N(β⁽²⁾) ={5, 4, 3}. Элементa_2,3(β⁽¹⁾) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к симплекс-таблице, соответствующей второй итерации Т₂⁽²⁾, и полагаем индекс текущей итерацииq = 2.