Задача линейного программирования. Табличный симплекс-метод. Использование искусственных переменных

Рассмотрим ЗЛП

Приведем к канонической форме

Матричный вид ЗЛП

Начальный базис 0. Начальный базис P = E отсутствуют все столбцы для образования единичной матрицы

Начальный базис добавим искусственную переменную

Начальный базис чтобы искусственная переменная не влияла на решение и не присутствовала в оптимальном базисе, введем ее в целевую функцию примем

Начальный базис 0. Начальный базис P = E Базис: x 3, x 5

Базис x 3, x 5 1. Допустимость базиса 2. Оптимальность базиса допустимый неоптимальный x1x1 x2x2 x4x4 b x3x x5x5 110 f b 8>0 10>0 f

Базис x 3, x 5 3. Проверка наличия решения 4. Ввод в базис ОДР замкнута, решение есть x1x1 x2x2 x4x4 f Разрешающий столбец: x 1 x1x1 x2x2 x4x4 b x3x3 -1

Базис x 3, x 5 5. Вывод из базиса x1x1 x2x2 x4x4 b-b/x 1 x3x x5x f Разрешающая строка: x 5 Разрешающий элемент: a 51 =-2

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x1x1 x2x2 x4x4 b x3x x5x5 110 f x5x5 x2x2 x4x4 b x3x x1x f

Пересчет симплекс-таблицы Промежуточная симплекс-таблица: Разрешающий элемент: a 51 =-2 Все элементы промежуточной таблицы делятся на разрешающий элемент x5x5 x2x2 x4x4 b x3x x1x f x5x5 x2x2 x4x4 b x3x3 1/2-3/2-1/23 x1x1 1/25 f -203/2 5/23/215

Базис x 3, x 1 1. Допустимость базиса 2. Оптимальность базиса допустимый неоптимальный x5x5 x2x2 x4x4 b x3x3 1/2-3/2-1/23 x1x1 1/25 f -203/2 5/23/215 b 3>0 5>0 f -203/2 5/23/2

Базис x 3, x 1 3. Проверка наличия решения 4. Ввод в базис ОДР замкнута, решение есть x1x1 x2x2 x4x4 f -203/2 5/23/2 Разрешающий столбец: x 2 x5x5 x2x2 x4x4 b x3x3 1/2-3/2

Базис x 3, x 1 5. Вывод из базиса x5x5 x2x2 x4x4 b-b/x 2 x3x3 1/2-3/2-1/232 x1x1 1/2510 f -203/2 5/23/215 Разрешающая строка: x 3 Разрешающий элемент: a 32 =-3/2

Пересчет симплекс-таблицы Исходная симплекс- таблица: Следующая симплекс- таблица: x5x5 x2x2 x4x4 b x3x3 1/2-3/2-1/23 x1x1 1/25 f -203/2 5/23/215 x5x5 x3x3 x4x4 b x2x2 1/3-2/3-2/3-1/32 x1x1 -2/3-2/31/32/32/34 f -302/3 -5/32/32/320

Базис x 2, x 1 x5x5 x3x3 x4x4 b x2x2 1/3-2/3-2/3-1/32 x1x1 -2/3-2/31/32/32/34 f -302/3 -5/32/32/320 допустимый неоптимальный Разрешающая строка: x 2 Разрешающий элемент: a 24 =-1/3 Разрешающий столбец: x 4

Пересчет симплекс-таблицы Исходная симплекс- таблица: Следующая симплекс- таблица: x5x5 x3x3 x4x4 b x2x2 1/3-2/3-2/3-1/32 x1x1 -2/3-2/31/32/32/34 f -302/3 -5/32/32/320 x5x5 x3x3 x2x2 b x4x x1x f

Базис x 4, x 1 x5x5 x3x3 x2x2 b x4x x1x f допустимый оптимальный, решение единственное

Ответ Оптимальный базис: x 1, x 4 Базисные переменные: x 1 = 8 x 4 = 6 Свободные переменные: x 2 = 0 x 3 = 0 x 5 = 0 Значение функции: f(X) = 24 x5x5 x3x3 x2x2 b x4x x1x f

x1x1 x2x2 x4x4 b x3x x5x5 110 f x5x5 x2x2 x4x4 b x3x3 1/2-3/2-1/23 x1x1 1/25 f -203/2 5/23/215 x5x5 x3x3 x2x2 b x4x x1x f x5x5 x3x3 x4x4 b x2x2 1/3-2/3-2/3-1/32 x1x1 -2/3-2/31/32/32/34 f -302/3 -5/32/32/320