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

Презентация:



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

Задача линейного программирования. Матричный симплекс-метод.
Задача линейного программирования. Табличный симплекс-метод.
Задача линейного программирования. Двойственная задача, двойственный симплекс-метод.
Симплекс-метод Лекции 6, 7. Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором.
Линейное программирование Двойственность в линейном программировании.
Решение задачи линейного программирования методом последовательного улучшения плана ( Симплексный методом )
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 17. Тема: Графический метод и симплекс-метод задачи.
Симплекс-метод Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной.
1/ 23 Это развёрнутая форма записи Это развёрнутая форма записи Линейная целевая функция Линейные ограни- чения Условия неотрицательности переменных.
Основная задача линейного программирования Симплекс-метод.
Симплекс-метод. Сущность метода Симплекс-метод – универсальный метод решения задач линейного программирования. Суть метода: целенаправленный перебор.
Симплекс-метод. Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй.
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
1 Математические методы Математические методы Теоретический учебный материал по дисциплине.
Прямая и двойственная задачи и их решение симплекс-методом Лекции 8, 9.
Математика Экономико-математические методы Векслер В.А., к.п.н.
Л.Н. Кривдина СИНТЕЗ ЦИФРОВЫХ РЕГУЛЯТОРОВ НА ОСНОВЕ ЛИНЕЙНЫХ МАТРИЧНЫХ НЕРАВЕНСТВ.
Просмотр Теоретического материала Гирич СН 1 Ввод задачи Гирич СН 3 Пользователь Отчет решения задачи Теоретический материал Целевая функция; система неравенств.
Массив-это упорядоченная последовательность однотипных элементов.
Транксрипт:

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

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

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

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

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

Базис x 3, x 4 1. Допустимость базиса 2. Оптимальность базиса допустимый неоптимальный x1x1 x2x2 b x3x3 -33 x4x f210 b 3>0 5>0 f2>01>0

Базис x 3, x 4 3. Проверка наличия решения 4. Ввод в базис x1x1 x2x2 b x3x3 -3

Базис x 3, x 4 5. Вывод из базиса x1x1 x2x2 b-b/x 1 x3x3 -3

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: Разрешающий элемент заменяется на 1 x3x3 x2x2 b x1x1 1 x4x4 f x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: Разрешающий столбец (кроме разрешающего элемента) без изменений x3x3 x2x2 b x1x1 1 x4x4 -2 f2 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: Разрешающая строка (кроме разрешающего элемента) меняет знак x3x3 x2x2 b x1x x4x4 -2 f2 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x3x3 x2x2 b x1x x4x4 -24 f2 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x3x3 x2x2 b x1x x4x f2 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x3x3 x2x2 b x1x x4x f2 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x3x3 x2x2 b x1x x4x f2-6 x1x1 x2x2 b x3x3 -33 x4x f210

Пересчет симплекс-таблицы Промежуточная симплекс-таблица: Разрешающий элемент: a 31 =-3 Все элементы промежуточной таблицы делятся на разрешающий элемент x3x3 x2x2 b x1x1 -1/3 1 x4x4 2/3-4/33 f-2/31/32 x3x3 x2x2 b x1x x4x f2-6

Базис x 1, x 4 1. Допустимость базиса 2. Оптимальность базиса допустимый неоптимальный x3x3 x2x2 b x1x1 -1/3 1 x4x4 2/3-4/33 f-2/31/32 b 1>0 3>0 f-2/30

Базис x 1, x 4 3. Проверка наличия решения 4. Ввод в базис x3x3 x2x2 b x1x1 -1/3-1/3

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

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: Разрешающий элемент заменяется на 1 Разрешающий столбец без изменений Разрешающая строка меняет знак x3x3 x4x4 b x1x1 -1/3 x2x2 -2/31-3 f1/3 x3x3 x2x2 b x1x1 -1/3 1 x4x4 2/3-4/33 f-2/31/32

Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: x3x3 x4x4 b x1x1 2/3-1/3 x2x2 -2/31-3 f2/31/3-11/3 x3x3 x2x2 b x1x1 -1/3 1 x4x4 2/3-4/33 f-2/31/32

Пересчет симплекс-таблицы Промежуточная симплекс-таблица: Разрешающий элемент: a 12 =-4/3 Все элементы промежуточной таблицы делятся на разрешающий элемент x3x3 x4x4 b x1x1 -1/21/4 x2x2 1/21/2-3/49/4 f-1/2-1/411/4 x3x3 x4x4 b x1x1 2/3-1/3 x2x2 -2/31-3 f2/31/3-11/3

Базис x 1, x 2 1. Допустимость базиса 2. Оптимальность базиса допустимый оптимальный, решение единственное x3x3 x4x4 b x1x1 -1/21/4 x2x2 1/21/2-3/49/4 f-1/2-1/411/4 b 1/4>0 9/4>0 f-1/2

Ответ Оптимальный базис: x 1, x 2 Базисные переменные: x 1 = 1/4 x 2 = 9/4 Свободные переменные: x 3 = 0 x 4 = 0 Значение функции: f(X) = 11/4 x3x3 x4x4 b x1x1 -1/21/4 x2x2 1/21/2-3/49/4 f-1/2-1/411/4