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

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

История

В течение долгого времени существование доказуемо эффективного сетевого симплексного алгоритма было одной из основных открытых проблем в теории сложности, даже несмотря на наличие эффективных на практике версий. В 1995 г. Орлин предоставил первый полиномиальный алгоритм со временем выполнения куда максимальная стоимость любых лезвий.[1] Потом Tarjan улучшил это до с помощью динамические деревья в 1997 г.[2] Сильно полиномиальные симплекс-алгоритмы двойной сети для той же задачи, но с большей зависимостью от количества ребер и вершин в графе, известны давно.[3]

Обзор

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

Приложения

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

Рекомендации

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

внешняя ссылка