Симплекс метод (24-е апреля 2019)

1. Кошерный Гаусс
1. Уравнения добавляются по одному, мы поддерживаем весь класс решений
2. Особенности реализации: не переставляем столбцы, столбец b - часть матрицы A
3. Пишем код Гаусс, код восстановления решения по значениям свободным переменных [code]
4. Упр: время работы Гаусса? Ответ O(nmk), где k - число линейно независимых строк, k ≤ min(n,m)


2. Задача линейного программирования: Ax ≤ b, x ≥ 0, cx → max
1. Вид Ax ≤ B ↔ Ax ≤ B
2. Условия x ≥ 0 ↔ отсутствие условия
3. (cx → max) ↔ (cx → min)
4. (cx → max) → поиск произвольного решения (бинпоиск по ответу)


3. Кошерный вид задачи линейного программирования и Симплекс-метод
1. i < m ⇒ x_i = b_i ≥ 0, i ≥ m ⇒ x_i = 0, i < m ⇒ c_i = 0, A = EA' (EA')(x) = (b)
2. Переход: выбрать min j, c_j > 0, пытаемся увеличивать, ограничения: x_i = b_i - a_ijx_j ≥ 0, выбираем i: a_ij > 0, b_i / a_ij → min
3. Пересчитываем матрицу A: поменяли местами два столбца, row_i /= a_ii, row_j -= a_ji row_i
4. Пересчёт вектора "c", как дополнительной строки матрицы A


4. Приведение систем к кошерному виду
1. Вид Ax ≤ b, x ≥ 0.
2. Вид Ax = b, x ≥ 0.
3. Поиск начального решения (ввести фиктивную переменную, пустить симплекс, убрать фиктивную переменную)


5. Примеры
1. x₁ + 2x₂ + x₃ ≤ 3, 2x₁ + x₂ + x₃ ≤ 3, x₁ + x₂ - x₃ → max (x₁, x₂, x₃ ≥ 0)
2. x₁ - x₂ ≤ -1, x₁ + x₂ ≤ 9, 2x₁ + x₂ → max (x₁, x₂ ≥ 0)


6. Наличие решения, корректность, время работы
1. Решений нет ⇔ поиск начального не смог сделать t = 0, максимум не ограничен ⇔ в одном из переходов не было ограничивающего условия
2. В симплексе все c_i ≤ 0 ⇒ решение оптимально, можно остановиться
3. Симплекс работает конечное время т.к. набор выбранных столбцов однозначно задаёт решение, а множества столбцов не циклятся
4. Почему не циклятся? Если x_j строго увеличилось, то ок. Если x_j осталось 0, то важно правило Бленда: min j с_j > 0, для такого min i, на котором достигается ограничение на x_j


7. Другие решения задачи Линейного программирования
1. Перебор базисных планов + Гаусс
2. Метод эллипсоидов (Хачиян'1972)
3. Метод внутренней точки (Interior Point)