Линейное программирование − 1 (13-е марта 2024)

1. Гаусс
   1. Воспоминание: привести матрицу к трапецевидному виду
   2. Новый вид задачи: вектора добавляются по одному, поддерживать базис
   3. Особенности реализации: не переставляем столбцы, столбец b − часть матрицы A
   4. Код Гаусса, код восстановления решения по значениям свободным переменных {unknown_variable:code}/linear_sk₂019.cpp.html
   5. Время работы Гаусса: O(nmk), где k − число линейно независимых строк, k ≤ min(n,m)
   
   
2. Задача линейного программирования: Ax ≤ b, x ≥ 0, cx → max
   1. Вид Ax ≤ B ↔ Ax = B (x ≤ b ⇒ x+y=b, вводим новые переменные)
   2. Условия x ≥ 0 ↔ отсутствие условия (x_i=v_i-u_i, вводим новые переменные)
   3. (cx → max) ↔ (cx → min)
   
   
3. Задачи на линейное программирование
   1. LP : Максимальный поток; Поток минимальной стоимости.
   2. ILP : Паросочетание в произвольном графе минимального веса. На самом деле решится за полином.
   3. LP : Многопродуктовый поток (задача про два непересекающихся потока s₁ → t₁ размера f₁; s₂ → t₂ размера f₂).
      В отличии от предыдущих задач не решается иначе как "свести к LP, запустить симплекс".
   4. ILP : Задача про два непересекающихся пути (A → B, C → D). NP-трудна. Почему не следует из предыдущей?
   5. ILP : Взвешенное вершинное покрытие
   6. LP : Паросочетание в двудольном графе минимального веса. Казалось бы ILP, но решение, найденное симплекс методом обязательно будет целым.
   7. LP : Кратчайшее расстояние; Поиск потенциалов.
   
   
4. Геометрическая интерпретация и экспоненциальное решение
   1. Пересечение полупространств, полиэдр, максимум в вершине ⇒ перебор вершин
   2. Перебор базисных планов + Гаусс
   
   
5. ♥ Кошерный вид задачи линейного программирования и Симплекс-метод
   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
   
   
6. Приведение систем к кошерному виду
   1. Вид Ax ≤ b, x ≥ 0.
   2. Вид Ax = b, x ≥ 0.
   3. Поиск начального решения (ввести фиктивную переменную, пустить симплекс, убрать фиктивную переменную)
   
   
7. Наличие решения, корректность, время работы
   1. Решений нет ⇔ поиск начального не смог сделать t = 0, максимум не ограничен ⇔ в одном из переходов не было ограничивающего условия
   2. В симплексе все c_i ≤ 0 ⇒ решение оптимально, можно остановиться
   3. Симплекс работает конечное время т.к. набор выбранных столбцов однозначно задаёт решение, а множества столбцов не циклятся
   4. Почему не циклятся? Если x_j строго увеличилось, то ок. Если x_j осталось 0, то важно правило Бленда: min j с_j > 0, для такого min i, на котором достигается ограничение на x_j