В математической оптимизации , то сеть симплекс алгоритм является графиком теоретико специализация симплексного алгоритма . Алгоритм обычно формулируется в терминах задачи о потоках с минимальными затратами . Сетевой симплексный метод очень хорошо работает на практике, обычно в 200–300 раз быстрее, чем симплексный метод, применяемый к общей линейной программе тех же размеров. [ необходима цитата ]
История [ править ]
В течение долгого времени существование доказуемо эффективного сетевого симплексного алгоритма было одной из основных открытых проблем в теории сложности, даже несмотря на то, что были доступны эффективные на практике версии. В 1995 году Орлин представил первый полиномиальный алгоритм со временем выполнения, где максимальная стоимость любых ребер. [1] Позже Тарьян улучшил это до использования динамических деревьев в 1997 году. [2] Сильно полиномиальные симплекс-алгоритмы двойственной сети для той же проблемы, но с большей зависимостью от количества ребер и вершин в графе, были известны дольше. [3]
Обзор [ править ]
Сетевой симплекс-метод является адаптацией простого симплекс-алгоритма с ограниченными переменными. Базис представлен как корневое связующее дерево базовой сети, в которой переменные представлены дугами, а симплексные множители - потенциалами узлов. На каждой итерации входящая переменная выбирается некоторой стратегией ценообразования, основанной на двойных множителях (потенциалах узлов), и формирует цикл с дугами дерева. Уходящая переменная - это дуга цикла с наименьшим увеличивающим потоком. Замена входящей дуги на выходящую и реконструкция дерева называется опорной точкой. Когда не остается подходящей для входа неосновной дуги, оптимальное решение было достигнуто.
Приложения [ править ]
Сетевой симплексный алгоритм может использоваться для решения многих практических задач, включая [4]
- Проблема перевалки
- Транспортная проблема Хичкока
- Проблема с присвоением
- Цепи и антицепи в частично упорядоченных наборах
- Система отличных представителей
- Покрытия и паросочетания в двудольных графах
- Проблема поставщика
Ссылки [ править ]
- ^ Орлин, Джеймс Б. (1997-08-01). «Полиномиальный простой сетевой симплекс-алгоритм для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. DOI : 10.1007 / BF02614365 . ЛВП : 1721,1 / 2584 . ISSN 0025-5610 .
- ^ Тарджан, Роберт Э. (1997-08-01). «Динамические деревья как деревья поиска с помощью обходов Эйлера, применяемые к сетевому симплексному алгоритму». Математическое программирование . 78 (2): 169–177. DOI : 10.1007 / BF02614369 . ISSN 0025-5610 .
- ^ Орлин, Джеймс Б .; Плоткин, Серж А .; Тардос, ЕВА "полиномиальных алгоритмов двойной сети Simplex" (июнь 1993),, математическое программирование , 60 (1-3): 255-276, CiteSeerX 10.1.1.297.5730 , DOI : 10.1007 / bf01580615
- ^ Chvatal, Васьки (1983). «20» . Линейное программирование . Макмиллан. С. 320–351 . ISBN 9780716715870.
Внешние ссылки [ править ]
- Решение сетевых проблем Раздел 14, стр. B-113 показывает пример выполнения.
