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

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

2 2 ЗЛП в матричной форме

3 3 n – число переменных ЗЛП m – число ограничений ЗЛП ЗЛП в канонической форме имеет смысл при n>m ОДР – выпуклый многогранник в Решение – в опорной точке Каноническая форма

4 4 Опорные точки m базисных переменных (n-m) внебазисных (свободных) переменных Базис: Вектор базисных переменных: Число базисов (опорных точек): Значение базисных переменных: Значение свободных переменных: 0

5 5 Матричный симплекс-метод 0. Начальный базис P = E – единичная матрица 1. Текущий базис 2. Допустимость базиса

6 6 Матричный симплекс-метод 3. Оптимальность базиса - : базис оптимален, решение единственное - : базис оптимален, решение неединственное - : базис неоптимален

7 7 Матричный симплекс-метод 4. Вводимая в базис переменная 5. Выводимая из базиса переменная 6. Замена переменных

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

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

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

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

12 Базис x 3, x 4 1. Текущий базис 2. Допустимость базиса 3. Оптимальность базиса допустимый неоптимальный

13 13 Базис x 3, x 4 4. Вводимая в базис переменная 5. Выводимая из базиса переменная 6. Замена переменных

14 Базис x 4, x 2 1. Текущий базис 2. Допустимость базиса 3. Оптимальность базиса допустимый неоптимальный

15 15 Базис x 4, x 2 4. Вводимая в базис переменная 5. Выводимая из базиса переменная 6. Замена переменных

16 Базис x 1, x 2 1. Текущий базис 2. Допустимость базиса 3. Оптимальность базиса допустимый оптимальный, решение единственное

17 17 Ответ Оптимальный базис: x 1, x 2 Базисные переменные: x 1 = 4 x 2 = 2 Свободные переменные: x 3 = 0 x 4 = 0

18 18

19 19

20 20

21 21