Линейное программирование + Конец SA (3 марта 2025)

1. Суффиксный автомат
   1. Написание алгоритма
   2. Оценка размера автомата: 2n вершин; (2n-1) + (n-1) = 3n-2 рёбер
   3. Задача: Перебор всех вхождений строки в текст за O(|s| + |answer|)
   4. LCP обратной строки в суффиксном автомате: LCA в дереве суффссылок.
   5. [skipped] Задача: найти максимальный общий подпалиндром двух строк с автоматом, но без сжатого бора
   
   
2. Гаусс
   1. Воспоминание: привести матрицу к трапецевидному виду
   2. Новый вид задачи: вектора добавляются по одному, поддерживать базис
   3. Особенности реализации: не переставляем столбцы, столбец b − часть матрицы A
   4. Код Гаусса, код восстановления решения по значениям свободным переменных [code]
   5. Время работы Гаусса: O(nmk), где k − число линейно независимых строк, k ≤ min(n,m)
   
   
3. Задача линейного программирования: 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)
   
   
4. Геометрическая интерпретация и экспоненциальное решение
   1. Пересечение полупространств, полиэдр, максимум в вершине ⇒ перебор вершин
   2. Перебор базисных планов + Гаусс
   3. План на норм решение: взять какую-то вершину и двигаться от неё в сторону улучшения целевой функции.
   
   
5. Задачи на линейное программирование
   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 : Кратчайшее расстояние; Поиск потенциалов.
   
   
6. ♥ Кошерный вид задачи линейного программирования и Симплекс-метод
   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
   
   
7. Приведение систем к кошерному виду
   1. Вид Ax ≤ b, x ≥ 0.
   2. Вид Ax = b, x ≥ 0.
   3. Поиск начального решения (ввести фиктивную переменную, пустить симплекс, убрать фиктивную переменную)
   
   
8. Наличие решения, корректность, время работы
   1. Решений нет ⇔ поиск начального не смог сделать t = 0, максимум не ограничен ⇔ в одном из переходов не было ограничивающего условия
   2. В симплексе все c_i ≤ 0 ⇒ решение оптимально, можно остановиться
   3. Симплекс работает конечное время т.к. набор выбранных столбцов однозначно задаёт решение, а множества столбцов не циклятся
   4. Почему не циклятся? Если x_j строго увеличилось, то ок. Если x_j осталось 0, то важно правило Бленда: min j с_j > 0, для такого min i, на котором достигается ограничение на x_j