Заполнение таблиц, отвечающих последующим итерациям, происходит в соответствии с описанным выше первым алгоритмом.
Таблица 4.2
Решение исходной задачи(2.12) - (2.13)получено за 3 итерации. Оптимальный план ее равен
Найденное решение
Вернемся к задаче (1.2.1), (1.2.2) со старыми переменными
и
Таким образом, для получения максимальной цены (142750 руб.) всей продукции необходимо произвести:
- 450 тыс.л. бензина А из полуфабрикатов в следующих количествах:
- Алкитата
- Крекинг-бензина
- Бензина прямой перегонки
- Изопентона
-
- Алкитата
- Крекинг-бензина
- Бензина прямой перегонки
- Изопентона
- 300 тыс.л. бензина В из полуфабрикатов в следующих количествах:
- Алкитата
- Крекинг-бензина
- Бензина прямой перегонки
- Изопентона
5. Формирование М-задачи
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.
Рассмотрим наряду с исходной задачей (2.1) - (2.3) в канонической форме следующую расширенную задачу (М-задачу):
Здесь М>0 – достаточно большое число.
Начальный опорный план задачи (5.1) - (5.3) имеет вид
Переменные
Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой известен. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план задачи (2.1) - (2.3), либо убедиться в ее неразрешимости, если оказывается неразрешимой М-задача.
В соответствии с вышеизложенным имеем: требуется решить задачу (2.12), (2.13), записанную в канонической форме. Введем искусственную неотрицательную переменную х9 и рассмотрим расширенную М-задачу
при условиях
где М – сколь угодно большая положительная величина.
Как и в L-задаче, добавление только одной искусственной переменной
6. Решение М-задачи II алгоритмом симплекс-метода
Описание II алгоритма
Второй алгоритм (или метод обратной матрицы) симплекс метода основан на ином способе вычисления оценок
Рассматривается задача линейного программирования в канонической форме(2.1) - (2.3). Пусть Х – опорный план с базисом
Действительно, зная обратную матрицу
и вычислить оценки векторов условий относительно текущего базиса
предварительно определив вектор-строку
или
Здесь
Оценки
Как и в I алгоритме, вектор, подлежащий исключению из базиса, определяется величиной
Таким образом при втором алгоритме на каждом шаге запоминаются базисные компоненты
Здесь
Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk – разрешающий столбец, строка l – разрешающая строка.