$AlexLat$

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

Рассмотрим наряду с исходной задачей (2.1) - (2.3) в канонической форме следующую расширенную задачу (М-задачу):

                                                                (5.1)

                                                                         (5.2

                                                                             (5.3)

Здесь М>0 – достаточно большое число.

Начальный опорный план задачи (5.1) - (5.3) имеет вид

Переменные  называются искусственными переменными.

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

В соответствии с вышеизложенным имеем: требуется решить задачу (2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х₉ и рассмотрим расширенную М-задачу

                                  (5.4)

при условиях

                 (5.5)

, где .

где М – сколь угодно большая положительная величина.

Как и в L-задаче, добавление только одной искусственной переменной  (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А_4, А_5, А_6, А_7.