Теория

  1. Метод Гаусса
    1. Приведение матрицы A к виду EA'. Не переставляя в явном виде столбцы. Массив p[0..m-1]
    2. Основная операция Do(i,j) - поставить на позицию (i,j) единицу, а весь остаток j-го столбца обнулить.
    3. x = (b,0)
    4. Аффинное пространство решений.
    5. Добавление нового уравнения в систему за O(N2).
  2. Линейное программирование
    1. Канонический вид: Ax = b, x >= 0
    2. Приведение к каноническому виду (1) Ax < b => Ax + z = b (2) x = u - v, u >= 0, v >= 0
    3. Док-во того, что если есть M линейно независимых уравненией, то в оптимальном решении N-M переменных точно равны 0.
    4. Решение за O(C(N,M)*N3) = перебор всех базисных планов
    5. Simplex метод
      1. Приведение матрицы A к виду EA' (а заодно делаем так, что строки линейнонезависимы)
      2. Поиск начального решения, если b < 0 = Simplex метод
      3. Переход к новому плану: увеличиваем x[j], целевая функция улучшается: dc[j] = c[j] - Sum(a[i][j] * c[p[i]]) > 0.
      4. Если увеличивать можно бесконечно, max = infinity, иначе какое-то x[p[i]] уменьшится до нуля.
      5. Какое i уменьшится до нуля? min из b[i] / a[i][j] по a[i][j] > 0.
      6. Далее Do(i, j). И не забыть поменять массив p[].
    6. Быстрый Simplex метод
      1. dc[j] = c[j] - Sum(a[i][j] * c[p[i]]), можно пересчитывать одновременно с матрицей A. Теперь пару (i,j) можно найти за O(N+M).
      2. В Do(i, j) сперва за O(M) выбрали все K ненулевых элементов в строке. За O(KL) сделали изменение матрицы, где L число a[l,j] != 0.
    7. Решение задач с помощью Simplex-а
      1. Min = Max.
      2. Если нет условия 0 <= x, его можно не добавлять.
      3. Если есть условие 0 <= x <= c, то это на самом деле одно условие.
      4. Flow - матрица получает (V-2) x E.
      5. MinCostFlow - добавляем еще одно уравнение, что поток равен K, минимизируем вес.
      6. Задачка с чемпионата Урала timus : 1833
      7. Триатлон timus : 1062

Практика

  1. 110304a1 : 6A (поток обыкновенный)
  2. 110304a1 : 6B (mincost поток - задача о назначениях)
  3. timus : 1764 (маленькая задача ЛП)
  4. timus : 1833 (задача с последнего чемпионата Урала)
  5. timus : 1062 (еще одна задача ЛП)