Линейное программирования и симплекс метод (6 октября 2016)

  1. [10 минут] LP и ILP
    1. Задача линейного программирования (LP) в общем виде
    2. Задача целочисленного линейного программирования (ILP) в общем виде
    3. NP-полнота ILP
    4. LP решается за полином: метод Эллипсоидов, метод внутренней точки, симплекс-метод

  2. [15 минут] Примеры задач
    1. LP : Кратчайшее расстояние; Поиск потенциалов.
    2. LP : Максимальный поток; Поток минимальной стоимости.
    3. LP : Многопродуктовый поток (задача про два непересекающихся потока s1 → размера f1; s2 → t2 размера f2).
      В отличии от предыдущих задач не решается иначе как "свести к LP, запустить симплекс".
    4. ILP : Паросочетание в произвольном графе минимального веса. На самом деле решится за полином.
    5. ILP : Задача про два непересекающихся пути. NP-трудна. Почему не следует из предыдущей?
    6. ILP : Взвешенное вершинное покрытие
    7. LP : Паросочетание в двудольном графе минимального веса. Казалось бы ILP, но решение, найденное симплекс методом обязательно будет целым.
  3. [15 минут] Канонический вид и сведения
    1. Канонический вид: Ax = b, x ≥ 0
    2. Сведение неравенства к равенству
    3. Сведение знаковой переменной к беззнаковой
    4. Канонический базисный вид: A = (E|C). n уравнений, m переменных, m ≥ n, x1..n = linear(xn+1, ..., xm)
    5. Приведение к каноническому базисному виду: Гаусс. Вообще LP не проще Гаусса ;-)
− Перерыв −
  1. [45 минут] Симплекс метод
    1. [Сведение к базисному каноническому виду] + [Поиск начального решения] + [Поиск улучшения начального решения до оптимального]
    2. Поиск начального решения: решим LP, A(x-y) = b, x ≥ 0, y ≥ 0, ∑y → min, у этой LP уже есть начальное решение Гауссом.
    3. Lm: Пусть A − матрица n линейно независимых уравнений над m переменными (m ≥ n) ⇒ ∃ решение задачи LP с не более чем n ненулевыми компонентами.
    4. Док-во: пусть есть хотя бы n+1 ненулевой x; найдём вектор dx : A * dx = 0 and dx != 0; найдём вещественное t : x + dx*t >= 0, и один из x занулился
    5. Будем поддерживать инвариант "ненулевые x-ы соответствуют только столбцам E" и постепенно улучшать решение. Начальное решение удовлетворяет инварианту.
    6. Фаза улучшения: попытаться одну нулевую переменную сделать не нулевой, при этом одна ненулевая занулится.
    7. Псевдокод
    8. Решение за C(m,n)n3 перебором базисных планов.