Реферат: Решение задач линейной оптимизации симплекс – методом
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.
Рассмотрим наряду с исходной задачей (2.1) - (2.3) в канонической форме следующую расширенную задачу (М-задачу):
(5.1)
(5.2)
. (5.3)
Здесь М>0 – достаточно большое число.
Начальный опорный план задачи (5.1) - (5.3) имеет вид
Переменные 
называются искусственными переменными.
Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой известен. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план задачи (2.1) - (2.3), либо убедиться в ее неразрешимости, если оказывается неразрешимой М-задача.
В соответствии с вышеизложенным имеем: требуется решить задачу (2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х9 и рассмотрим расширенную М-задачу
(5.4)
при условиях
(5.5)
, где 
.
где М – сколь угодно большая положительная величина.
Как и в L-задаче, добавление только одной искусственной переменной 
(вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А 4, А 5, А 6, А 7.
6. Решение М-задачи II алгоритмом симплекс-метода
Описание II алгоритма
Второй алгоритм (или метод обратной матрицы ) симплекс метода основан на ином способе вычисления оценок 
векторов условий А j , чем в первом алгоритме.
Рассматривается задача линейного программирования в канонической форме(2.1) - (2.3). Пусть Х – опорный план с базисом 
. Все параметры, необходимые для оценки плана на оптимальность и перехода к лучшему плану, можно получить, преобразовывая от шага к шагу элементы матрицы 
.
Действительно, зная обратную матрицу 
, можно получить базисные составляющие опорного плана:
и вычислить оценки векторов условий относительно текущего базиса
, (6.1)
предварительно определив вектор-строку 
по формуле
или
. (6.2)