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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 Пересчет симплекс-таблицы Промежуточная симплекс-таблица: Разрешающий элемент: 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

17 Базис 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

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

19 Базис 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

20 Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: Разрешающий элемент заменяется на 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

21 Пересчет симплекс-таблицы Исходная симплекс- таблица: Промежуточная симплекс-таблица: 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

22 Пересчет симплекс-таблицы Промежуточная симплекс-таблица: Разрешающий элемент: 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

23 Базис 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

24 Ответ Оптимальный базис: 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