Сетевой симплексный алгоритм

В математической оптимизации сетевой симплексный алгоритм является области теории графов в специализацией симплексного алгоритма . Алгоритм обычно формулируется в виде задачи потока с минимальной стоимостью . Сетевой симплексный метод работает очень хорошо на практике, обычно в 200–300 раз быстрее, чем симплексный метод, применяемый к общей линейной программе тех же размеров. ^{[ нужна ссылка ]}

История [ править ]

Долгое время существование доказуемо эффективного сетевого симплексного алгоритма было одной из основных открытых проблем теории сложности, хотя были доступны эффективные на практике версии. В 1995 году Орлин представил первый полиномиальный алгоритм со временем выполнения $O(V^{2}E\log(VC))$ где $C$ — максимальная стоимость любого ребра. ^[1] Позже Тарьян улучшил это до $O(VE\log V\log(VC))$ с использованием динамических деревьев в 1997 году. ^[2] Давно известны сильно полиномиальные дуальные сетевые симплекс-алгоритмы для решения той же задачи, но с большей зависимостью от числа ребер и вершин в графе. ^[3]

Обзор [ править ]

Сетевой симплексный метод представляет собой адаптацию алгоритма простого симплекса с ограниченной переменной. Базис представлен как корневое остовное дерево базовой сети, в котором переменные представлены дугами, а симплексные множители - потенциалами узлов. На каждой итерации входная переменная выбирается некоторой стратегией ценообразования, основанной на двойственных множителях (потенциалах узлов), и образует цикл с дугами дерева. Уходящая переменная — это дуга цикла с наименьшим увеличивающимся потоком. Замена входной дуги на выходящую и реконструкция дерева называется поворотом. Когда ни одна неосновная дуга не может быть использована, оптимальное решение достигнуто.

Приложения [ править ]

Сетевой симплексный алгоритм можно использовать для решения многих практических задач, в том числе: ^[4]

Проблема перевалки
Транспортная проблема Хичкока
Проблема с назначением
Цепи и антицепи в частично упорядоченных множествах.
Система отдельных представителей
Покрытия и паросочетания в двудольных графах
Проблема поставщика провизии

Ссылки [ править ]

^ Орлин, Джеймс Б. (1 августа 1997 г.). «Симплекс-алгоритм простой сети с полиномиальным временем для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. дои : 10.1007/BF02614365 . hdl : 1721.1/2584 . ISSN 0025-5610 . S2CID 3107792 .
^ Тарьян, Роберт Э. (1 августа 1997 г.). «Динамические деревья как деревья поиска с помощью эйлеровых туров в применении к сетевому симплексному алгоритму». Математическое программирование . 78 (2): 169–177. дои : 10.1007/BF02614369 . ISSN 0025-5610 . S2CID 18977577 .
^ Орлин, Джеймс Б .; Плоткин, Серж А.; Тардос, Ева (июнь 1993 г.), «Полиномиальные симплексные алгоритмы двойной сети», Mathematical Programming , 60 (1–3): 255–276, CiteSeerX 10.1.1.297.5730 , doi : 10.1007/bf01580615 , S2CID 5838223
^ Хватал, Васек (1983). «20» . Линейное программирование . Макмиллан. стр. 320–351 . ISBN 9780716715870 .

Внешние ссылки [ править ]

Решение сетевых проблем, раздел 14, стр. B-113, показан пример выполнения.

[1] Орлин, Джеймс Б. (1 августа 1997 г.). «Симплекс-алгоритм простой сети с полиномиальным временем для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. дои : 10.1007/BF02614365 . hdl : 1721.1/2584 . ISSN 0025-5610 . S2CID 3107792 .

[2] Тарьян, Роберт Э. (1 августа 1997 г.). «Динамические деревья как деревья поиска с помощью эйлеровых туров в применении к сетевому симплексному алгоритму». Математическое программирование . 78 (2): 169–177. дои : 10.1007/BF02614369 . ISSN 0025-5610 . S2CID 18977577 .

[3] Орлин, Джеймс Б .; Плоткин, Серж А.; Тардос, Ева (июнь 1993 г.), «Полиномиальные симплексные алгоритмы двойной сети», Mathematical Programming , 60 (1–3): 255–276, CiteSeerX 10.1.1.297.5730 , doi : 10.1007/bf01580615 , S2CID 5838223

[4] Хватал, Васек (1983). «20» . Линейное программирование . Макмиллан. стр. 320–351 . ISBN 9780716715870 .

[1]

[2]

[3]

[4]