LP (20-е мая 2019)

  1. Упражнения
    1. Даны k n-мерных сфер. Найти ∀ точку пересечения.
    2. Даны k n-мерных конусов. Найти ∀ точку пересечения в предположении, что она ∃ и имеет координаты до 1020.
    3. Запишите двойственную в общем виде для задачи Ax ≥ b, x ≥ 0, ctx → max
    4. Запишите двойственную к x1 + x2 ≤ 2, 3x1 + x2 ≤ 5, x1 + 3x2 ≤ 5, 2x1 + 3x2 → max. Нарисуйте обе задачи.
    5. Если у задачи нет решений, или максимум не ограничен, что с двойственной задачей?

  2. Частные случаи LP (m уравнений, n неизвестных)
    1. Ax = b, x ≥ 0 ⇒ m ≤ n (линейно независимые строки)
    2. Ax ≥ b для случая m ≤ n (через двойственность)
    3. Ax ≥ b ⇒ m ≥ n (линейно независимые столбцы)
    4. ♥ Ax ≤ b для малых n − пересечение полуплоскостей, полупространств. Рандомизированное решение за O(m×n!).

  3. Алгебра
    1. Унимодулярная матрица. Минор. Тотальная унимодулярность (TU).
    2. Ax = b, Ax ≤ b, целочисленность решений для TU матрицы A.
    3. Тотальная унимодулярность матрицы инцидентности двудольного графа.

  4. Паросочетания
    1. Запись задачи в LP
    2. [skipped] Двойственная задача.
    3. ♥ Поиск паросочетания и взвешенного паросочетания в двудольном графе через симплекс.

  5. [skipped] Матричные игры
    1. [skipped] Детерминированные стратегии. Вероятностные стратегии.
    2. [skipped] Оптимальная вероятностная стратегия: mini(∑aijxj) → max
    3. [skipped] Записываем задачу через LP для первого и второго игроков. Проверяем, что задача второго двойственна задаче первого.
    4. [skipped] ♥ Теорема Нэша для матричных игр (сильная теорема двойственности для уже записанных задач LP)