Линейное программирование. Лекция 6

Краткое напоминание: целочисленные полиэдры и комбинаторные задачи, тотальная унимодулярность и тотальная двойственная целочисленность. Доказательство тотальной двойственной целочисленности политипа паросочетаний в графе общего вида. Условия дополняющей нежесткости в паре линейно двойственных программ. Задача о кратчайших путях в направленном графе, запись в виде линейной программы, потенциалы вершин и приведенные длины. Прямо-двойственный алгоритм поиска кратчайшего пути. 

Страница лекции на сайте Computer Science клуба