Конспект: линейное программирование и двойственность

Понятия

Линейное программирование - максимизация линейной цели при линейных ограничениях. Слово programming здесь значит «планирование», а не написание кода.

стандартная форма:   максимизировать cᵀx  при  Ax <= b,  x >= 0

Допустимая область - пересечение полупространств, то есть выпуклый многогранник. Вершина - точка, где n ограничений обратились в равенства. Базис - набор переменных, которым разрешено быть ненулевыми; ему отвечает вершина. Дополнительная переменная - неизрасходованный остаток ресурса, превращающий неравенство в равенство.

Двойственная задача - зеркальная: ограничения становятся переменными, переменные - ограничениями, максимум - минимумом. Теневая цена - двойственная переменная: прирост оптимума от единицы ресурса.

Что унести

три исхода:  несовместна | не ограничена | конечный оптимум
оптимум конечен ⇒ он достигается в ВЕРШИНЕ (иногда на грани, но вершина среди них есть)
вершин не больше C(m, n) - перебирать нельзя, надо ходить

прямая:        максимизировать cᵀx  при Ax <= b, x >= 0
двойственная:  минимизировать  bᵀy  при Aᵀy >= c, y >= 0

слабая двойственность:  cᵀx <= bᵀy  для любых допустимых x и y
сильная:                в оптимуме значения РАВНЫ
дополняющая нежёсткость: у неизрасходованного ресурса теневая цена нулевая

Симплекс ходит по вершинам: входящую переменную выбирают по росту цели, выходящую - по правилу отношений; нет входящей - оптимум, нет выходящей - цель не ограничена. Вырожденность грозит зацикливанием, лечится правилом Блэнда.

Целость ответа даёт не метод, а структура: у вполне унимодулярной матрицы (каждый минор 0, 1 или −1) все вершины целые. Такие матрицы у потока и у двудольного паросочетания - отсюда целые потоки и теорема Кёнига. Без этого свойства требование целых значений превращает задачу в целочисленное программирование, а оно NP-трудно, и округление дробного ответа не спасает.

Три теоремы курса как одна: максимальный поток равен минимальному разрезу, максимальное паросочетание равно минимальному вершинному покрытию, дефицит Холла - всё это сильная двойственность на разных данных.

Тихие ошибки: искать оптимум перебором целых точек; забыть неотрицательность; спутать несовместность с неограниченностью; строить двойственную, не поменяв знаки; применять теневые цены к большим изменениям, хотя они верны только локально.

Куда это ведёт

Следующая глава - потоки минимальной стоимости: к пропускным способностям добавятся цены, и критерий оптимальности снова окажется двойственным - «в остаточной сети нет отрицательного цикла».