Линейное программирование (29-е апреля 2019)

  1. Задачи на линейное программированиеn2
    1. LP : Кратчайшее расстояние; Поиск потенциалов.
    2. LP : Максимальный поток; Поток минимальной стоимости.
    3. ILP : Паросочетание в произвольном графе минимального веса. На самом деле решится за полином.
    4. LP : Многопродуктовый поток (задача про два непересекающихся потока s1 → t1 размера f1; s2 → t2 размера f2).
      В отличии от предыдущих задач не решается иначе как "свести к LP, запустить симплекс".
    5. ILP : Задача про два непересекающихся пути (A → B, C → D). NP-трудна. Почему не следует из предыдущей?
    6. ILP : Взвешенное вершинное покрытие
    7. LP : Паросочетание в двудольном графе минимального веса. Казалось бы ILP, но решение, найденное симплекс методом обязательно будет целым.

  2. NP-трудность ILP (сведём SAT. 0 ≤ xi ≤ 1 и sum xj ≥ 1 для каждого дизъюнкта)

  3. Геометрия и алгебра симплекса
    1. Система неравенств - пересечение полупространств (полиэдр). Выпукло. Экстремум в вершине.
    2. Lm: для системы Ax = b, x ≥ 0 ∃ оптимальное решение, содержащее не более m ненулевых xi (док-во: решение системы m уравнений Ax=b и n-(m+1) x-ов равны нулю или пусто, или хотя бы прямая... пойдём по этой прямой, пока какой-нибудь x не занулится)
    3. Симплекс - перебор вершин полиэдра. Каждая вершина образована m столбцами (базисный план). Переход - перейти по любому ребру, увеличив целевую функцию
    4. Если по всем рёбрам из вершины <c,x> не возрастает, то оптимум найден. Проблема не возрастания целевой функции в симплексе - вершина, являющаяся одновременным пересечением более чем m плоскостей.

Другие решения задачи Линейного программирования

  1. Перебор базисных планов + Гаусс, C(n,m)m3: из Lm "≤ m не нулевых" следует возможность перебора, какие именно m и решение системы

  2. Обучение Перцептрона
    1. Алгоритм для Ax > 0: начинаем с x0 = 0, пока ∃ aij <xj, ai> ≤ 0, xj+1 = xj + aij
      1. Конечность числа итераций: |ai| = 1, |xk|2 = |xk-1 + aik|2 ≤ |xk-1|2 + 1 ≤ k
      2. Конечность числа итераций: x* - ответ, |x*| = 1, тогда <xk,x*> ≤ k * mini<ai,x*> и <xk,x*> ≤ |xk|
      3. Точность сходимости (проблема проявляется уже в 2D, когда ∃ ai, aj: >ai, aj;< мало)

  3. Метод эллипсоидов (Хачиян'1972), полиномиальных в худшем способ, на практике бесполезен
    1. Задача: Ax ≤ b, ищем любое решение. Начальное данное, нам дан n-мерный эллипсоид, содержащий ответ
    2. Переход: или центр эллипсоида подходит, или есть неравенство-полупространство, которое не подходит, ответ по ту сторону плоскости от центра эллипсоида, осталось выбрать меньший по объёму эллипсоиод, содержащий нужную нам половину
    3. Математика эллипсоидов: положительно опеределённая матрица (пример и связь с x2/a2 + y2/b2 = 1)
    4. Меняем систему координат, что наш эллипсоид - сфера, а плоскость x1 = 0
    5. Новый центр = (1/(n+1), 0, 0, ...), новый радиус = (n/(n+1),d,d,d...), где d = n/(n2-1)1/2
    6. Сходимость: V0 ≤ (nU)Θ(n2), Vend ≥ V0 ≤ (nU)Θ(-n3), за один шаг объём уменьшается в exp(-1/2n) раз. Итого за 2n*ln(Vend/V0) алгоритм сойдётся, O(2n*(n3+n2)*log(nU)) = O(n4*log(nU)) шагов.
    7. Общее время работы: число шагов * nm * точность вычислений = O*(n4 * nm * n2)
    8. Обобщение: метод эллипсоидов можно применить для поиска пересечения любых выпуклых множеств. Мы пользовались тем, что за t умеем проверять, лежит ли точка в выпуклом множестве и за T строить опорную плоскость, получили решение за O(n4log(nU)) шагов, каждый за O(tm + T).