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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18

19

20

21