Поиск максимального потока минимальной стоимости

  • 11 дек. 2013 г.
  • 716 Слова
УДК 513.19, 519.1


ПОИСК МАКСИМАЛЬНОГО ПОТОКА МИНИМАЛЬНОЙ СТОИМОСТИ

Введение


Бурное развитие теории конечных графов обусловлено прогрессом компьютерной техники, необходимостьюсоздания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
Рассмотрение задачи «Поиска максимальногопотока минимальной стоимости» обуславливается тем, что эта задача очень актуальна и может быть широко применяема на практике, особенно в задачах о перевозках, транспортировке.

Постановка задачи

Цельюявляется проектирование приложения для решения задачи нахождения максимального потока минимальной стоимости.
Задача о поиске максимального потока минимальной стоимости сводится к решениюклассической транспортной задачи, задачи об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.
Для классической транспортной задачи выделяют два типа задач:критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Но решение задачи о нахождении максимального потокаминимальной стоимости будет решено методами, построенными на теории графов.
Вы владелец некоторого завода, выпускающего «товар», и недавно Вам посчастливилось заключить контракт с одной крупной фирмой,находящейся в другом городе на поставку товаров в их розничную сеть. Так как он находится очень далеко (во Владивостоке), товары придется доставлять авиаперевозкой. В ходе телефонных переговоров партнер поинтересовался:«а на какой объем поставок в день мы можем рассчитывать?». Вы задумались. У Вас есть собственные грузовики (дальнобойщики) осуществляющие транспортировку. Аэропорт находится далековато. Просмотревнакопленную статистику перевозок, Вы выявили, что в собственной области при транспортировке есть некоторые ограничения: на дорогах стоят пункты досмотра...
tracking img