Линейное программирование, часть 3 (20 октября 2016)

  1. Формы
    1. Каноническая: Ax ≤ b
    2. Стандартная: Ax = b, x ≥ 0 (базисная стандартная: строки линейно независимы)
    3. Два сведения
  2. Вершины
    1. Вершина: геометрия (любая форма). Нет окрестности.
    2. Вершина: алгебра (стандартная форма). Столбцы положительных xi линейно независимы (иначе можно шевелить x: ∃ dx)
    3. Базисное решение: |B|=n, столбцы линейно независимы
    4. Существует оптимальное решение-вершина. Симплекс находит именно вершину.
  3. Симплекс метод для задач Ax ≤ b, x ≥ 0, cTx → max
    1. Ax + z = b, z − базисный план, z ≥ 0 (переменная не жёсткости)
    2. Поиск начального решения: Ax - (t,t,...,t) + z ≤ b, t → 0 (+1 переменная). Случай не разрешимости.
    3. Инвариант: сTx не зависит от z, x = 0, z = b ≥ 0.
    4. Пересчёт базисного плана, выбор ci > 0, случай не ограниченности решения.
    5. Выражение xi и zj друг через друга, пересчёт A, b, c подстановкой. Операции с матрицей A.
    6. Откуда можно зациклиться? Правило Блэнда.
  4. Сложность симплекса
    1. Существование теста
    2. Randomized
    3. Диаметр, гипотеза Гирша
    4. В среднем по тестам полиномиальный
− Перерыв −
  1. Двойственность
    1. Двойственная к стандартной, к канонической формам.
    2. Слабая двойственность. Доказательство.
    3. Сильная двойственность, способы доказательства: через Симплекс, через лемму Фаракша.
    4. Сложность: LP ∈ NP ∩ coNP (следует из леммы Фаракша).
  2. Метод внутренней точки, primal-dual solution
    1. Искать параллельно оба решения, минимизировать разность
    2. Записываем разность, как xT*s > 0 (прямая Ax = b, двойственная ATy + s = c)
    3. Избавляемся от неравенств: F = q ln(xTs) + ∑ ln(xjsj) ≥ n ln n (выбираем q = n + n1/2)
    4. Когда F станет меньше -2n1/2L, алгоритм сошёлся. Уменьшение функционала: аффинное преобразование системы координат, сместиться на градиент.
  3. Паросчетания
    1. Полиэдр, политоп, целочисленность.
    2. Целочисленность, симплекс находит вершину ⇒ симплекс решает ILP.
    3. Политоп задаётся набором вершин (выпуклая оболочка вершин)
    4. Тотальная унимодулярность, целочисленность полиэдра.
    5. Перебор базисных решений (вершин), восстановления значения по множеству столбцов B: обратная матрица, det A в знаменателе.
    6. Политоп паросочетания для двудольного графа. Доказательство TU.
    7. Пример следствия: в регулярном двудольном графе есть совершенное паросочетания
    8. Другой пример: mincost circulation
    9. Политоп паросочетания произвольного графа. Пример с треугольником. Добавление нечётных компонент.