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

Название метода произошло от понятия симплекса. Напомним, что m-симплексом называют выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m. В данном случае можно считать, что система расширенных базисных столбцов {а^j1 ,а^j2,..., а^jm}, рассматриваемых как точки в R^m+1, порождает (m -1)-мерный симплекс в пространствеR^m+1.

*Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное множество.

В заключение настоящего пункта обобщим изложенные вопросы и приведем схему алгоритма симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и повторяемый конечное число раз I-этап (стандартную итерацию).

0-этап. Нахождение допустимого базисного плана(см. п. 1.4.5). Результатом 0-этапа является допустимый базисный план х(β⁽¹⁾), а также соответствующие ему матрица A(β⁽¹⁾) и вектор b(β⁽¹⁾), которые будут использованы на первой итерации. Полагаем номер текущей итерацииq равным 1 и переходим к I-этапу.

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

1°. Проверка оптимальности текущего базисного плана:осуществляется просмотр строки оценок а₀(β^(q)). Возможны два варианта:

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

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

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

2°. Определение столбца, выводимого из базиса. Рассматривается ведущий столбеца^l(β^(q)) Возможны два варианта:

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

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

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

Рис.1.5

1.4.2. Табличная реализация симплекс-метода. С точки зрения обеспечения рациональности и наглядности вычислительного процесса выполнение алгоритма симплекс-метода удобно оформлять в виде последовательности таблиц. В различных источниках приводятся разные модификации симплекс-таблиц, отличающиеся друг от друга расположением отдельных элементов. Однако это не должно вызывать смущения у читателя, так как все они базируются на одних и тех же принципах. Остановимся на структуре таблицы, показанной на рис. 1.5.*

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

Симплекс-таблица Т^(q), изображенная на рис. 1.5, соответствует допустимому базису КЗЛП β^(q)), получаемому наq-й итерации. Столбец N(β^(q)) содержит номера базисных столбцов (в той последовательности, в которой они входят в базис), столбец b(β^(q)) —компоненты вектора ограничений относительно текущего базиса β^(q),A(β^(q)) — компоненты матрицы задачи относительно текущего базиса β^(q). Наконец, в строке а₀(β^(q)) находятся текущие оценки столбцов, а ячейка b₀(β^(q)) содержит значение целевой функции, достигаемое для текущего плана.

Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение нестолько как удобная форма организации ручного счета, сколько как основа для реализации данного алгоритма в рамках программного обеспечения ЭВМ.

1.4.3. Пример решения ЗЛП симплекс-методом. Рассмотрим на конкретном примере процесс решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:

Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно получить разложение по данным столбцам вектора ограничений с положительными коэффициентами. Последнее означает, что столбцы {5, 2, 3} образуют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица Δ(β⁽¹⁾) и обратная по отношению кнейΔ^-1(β⁽¹⁾):

Используя их, по формуле (1.26) получаем

-84	0	0	-88	0
1/3	0	0	1/3	1
=	2	1	0	3	0	;
-2/3	0	1	-4/3	0

Используя полученные значения A(β⁽¹⁾) и b(β⁽¹⁾), заполняем симплекс-таблицу T⁽¹⁾, соответствующую первой итерации (q=1).

Поскольку строка оценок a₀(β⁽¹⁾) в первом и четвертом столбцах содержит отрицательные элементы (a_0,1(β⁽¹⁾) = -84, a_0,4(β⁽¹⁾) = -88), план х(β⁽¹⁾) = (0,14,17/3,0,4) не является оптимальным, и значение целевой функции f(x(β⁽¹⁾)) = -226 может быть улучшено. Следуя рекомендации п.1˝ алгоритма симплекс-метода, полагаем номер вводимого в очередной базис столбца l = 4 (т.к. |-88| > |-84|). Рассматриваем ведущий столбец (выделен пунктирной рамкой)

Он содержит два положительных элемента. Применяя рекомендацию п. 2" алгоритма, получаем λ₁= 4/(1/3) =12, λ₂=14/3,и, стало быть r = 2. Следовательно, столбец с номером N₂(β⁽¹⁾) = 2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи N(β⁽²⁾) = {5, 4, 3}. Элемент a_2,3(β⁽¹⁾) является ведущим (обведен кружком). Применив формулы (1.28)-(1.31), переходим к симплекс-таблице, соответствующей второй итерации T⁽²⁾, и полагаем индекс текущей итерацииq = 2.

В ходе выполнения второй итерации опять-таки определяются вводимый столбец а¹, выводимый а⁴ и ведущий элемент a_2,1(β⁽²⁾). Перейдя к итерации q = 3, имеем таблицу T⁽³⁾.

Как видно из T⁽³⁾, строка оценок содержит только неотрицательные значения, поэтому достигнутый базис N(β⁽³⁾) = {5, 1, 3} является оптимальным. В итоге мы получаем, что вектор х^* =(7, 0, 31/3, 0, 5/3) является оптимальным планом (точкой максимума) задачи (1.34)-(1.35), максимальное значение целевой функции равно f* =f(х*)=362, а решение КЗЛП имеет вид ((7, 0, 31/3, 0, 5/3); 362).

1.4.4. Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).