Линейное программирование − 2 (20-е марта 2024)

1. Паросочетание (произвольный граф)
   1. Задача поиска чётного простого пути min веса
   
   
2. Примеры (один на симплекс, другой на поиск начального решения; цель = закрепеление симплекса вторым проходом)
   1. x₁ + 2x₂ + x₃ ≤ 3, 2x₁ + x₂ + x₃ ≤ 3, x₁ + x₂ - x₃ → max (x₁, x₂, x₃ ≥ 0)
   2. x₁ - x₂ ≤ -1, x₁ + x₂ ≤ 9, 2x₁ + x₂ → max (x₁, x₂ ≥ 0)
   
   
3. Обучение Перцептрона
   1. Формулировка: нейрон/перцептрон, отделимость точек плоскостью, форма ∀i <a_i,x> >0
   2. Алгоритм для Ax > 0: начинаем с x₀ = 0, пока ∃ a_ij <x_j, a_i> ≤ 0, x_j+1 = x_j + a_ij
   3. Конечность числа итераций: |a_i| = 1, |x_k|² = |x_k-1 + a_ik|² ≤ |x_k-1|² + 1 ≤ k
   4. Конечность числа итераций: x^* − ответ, |x^*| = 1, тогда <x_k,x^*> ≤ k * min_i<a_i,x^*> и <x_k,x^*> ≤ |x_k|
   5. Точность сходимости (проблема проявляется уже в 2D, когда ∃ a_i, a_j: <a_i, a_j> мало)
   
   
4. Сведения разных форм LP, частные случаи LP (m уравнений, n неизвестных)
   1. (cx → max) ↔ (cx → min)
   2. (cx → max) → поиск произвольного решения (бинпоиск по ответу)
   3. Ax = b, x ≥ 0 ⇒ m ≤ n (линейно независимые строки)
   4. Ax ≥ b ⇒ m ≥ n (линейно независимые столбцы)
   
   
5. ♥ Ax ≤ b для малых n − пересечение полуплоскостей, полупространств.
   1. Решение для n=1 за O(m)
   2. Рандомизированное решение для n=2 за O(m)
   3. Рандомизированное решение за O(m×n!)