Алгоритм искусственного базиса

Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.

Расширенная М-задача применительно к исходной задаче записывается следующим образом:

;	(10.4)
;	(10.5)
.	(10.6)

Здесь - достаточно большое число.

Начальный опорный план задачи (10.4) – (10.6) может быть назначен непосредственно, так как в матрице условий этой задачи уже сформирована единичная подматрица, которая и составит его базис . Поэтому вектор с компонентами , и будет являться начальным опорным планом задачи (10.4) – (10.6). Переменные называются искусственными переменными.

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

Контрольные вопросы

1. Приведите описание первого алгоритма симплекс-метода.

2. Приведите описание алгоритма обратной матрицы решения ЗЛП.

3. Объясните свойство конечности симплекс-метода.

4. Дайте характеристику основным подходам в построении начального опорного плана ЗЛП.

5. В каком случае можно указать начальный опорный план ЗЛП без каких-либо вычислений.

6. Опишите алгоритм построения начального опорного плана, основанный на теореме об угловой точке.

7. Приведите постановку вспомогательной L-задачи.

8. Опишите алгоритм искусственного базиса.

9. Приведите постановку расширенной М-задачи.

10. В каких случаях используется тот или иной алгоритм построения начального опорного плана.