Транспортная задача

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

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

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

Математическая формулировка задачи

Пусть имеется <math>m</math> пунктов производства некоторого однородного продукта и <math>n</math> пунктов его потребления. Для каждого пункта производства <math>i=1, 2, ..., m</math> и для каждого пункта потребления <math>j=1, 2, ..., n</math> заданы следующие величины: объем производства <math>a_{i}</math> в пункте производства <math>i</math>, объем потребления <math>b_{j}</math> в пункте потребления <math>j</math>, затраты на перевозку единицы продукта <math>c_{ij}</math> от пункта производства <math>i</math> до пункта потребления <math>j</math>. Предполагается, что суммарное производство равно суммарному потреблению: <math>\sum_{i=1}^{m}a_{i}=\sum_{j=1}^{n}b_{j}</math>. Требуется составить план перевозок, позволяющий полностью вывезти продукты всех производителей, полностью обеспечивающий потребности всех потребителей и дающий минимум суммарных затрат не перевозку. Обозначим как <math>x_{ij}</math> объемы перевозок от поставщика <math>i</math> до потребителя <math>j</math>.

<math>\sum_{j=1}^{n}x_{ij}=a_{i}</math>, <math>i=1, 2, ..., m</math>

<math>\sum_{i=1}^{m}x_{ij}=b_{j}</math>, <math>j=1, 2, ..., n</math>

<math>\sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \rightarrow \min</math>

История поиска методов решения

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из <math>A_i</math> в <math>B_j</math> груза <math>X_{ij}\geqslant0</math>, а в маленькие клетки — соответствующие тарифы <math>C_{ij}</math>.

Итерационное улучшение плана перевозок

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

Метод северо-западного угла (диагональный или улучшенный)

На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из <math>A_i</math> или полностью удовлетворяется потребность <math>B_j</math>.

Метод наименьшего элемента

Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.

Алгоритм:

1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
2. Проверяются строки поставщиков на наличие строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

После нахождения опорного плана перевозок, нужно применить один из алгоритмов его улучшения, приближения к оптимальному.

• Метод падающего камня (нем.)
• Метод потенциалов.

Решение с помощью теории графов

Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока <math>C_{ij}</math>.

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за <math>O(v^2e^2)</math> операций. (<math>e</math> — количество рёбер, <math>v</math> — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка <math>O(ve)</math> операций.

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

Обобщения

Транспортная задача в сетевой постановке

В этом варианте пункты не делятся на пункты отправления и пункты потребления, все пункты равноправны, но производство задается положительным числом, а потребление — отрицательным. Перевозки осуществляются по заданной сети, в которой дуги могут соединять любые пункты, включая производитель — производитель, потребитель — потребитель.

Задача решается слегка измененным методом потенциалов, практически тем же, что и классическая постановка.

Транспортная задача с ограничениями пропускной способности

Вариант транспортной задачи в сетевой постановке, при котором задается максимальная пропускная способность некоторых дуг.

Задача решается слегка усложненным методом потенциалов.

Многопродуктовая транспортная задача

Вариант транспортной задачи, в которой присутствует несколько продуктов (пункты могут производить/потреблять несколько продуктов). Для некоторых дуг задается ограничение на пропускную способность (без этого ограничения задача распадается на отдельные задачи по продуктам).

Задача решается симплекс-методом (используется разложение Данцига-Вулфа, в качестве подзадач используются однопродуктовые транспортные задачи).

Ссылки

• [imcs.dvgu.ru/lib/nurmi/linpro/buka/node7.html Транспортная задача]
• [algolist.manual.ru/maths/graphs/maxflows/ Алгоритмы нахождения максимального потока]
• kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2

Литература

• Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969. — 368 с.

Отрывок, характеризующий Транспортная задача

– Вы графа Ильи Андреевича сын? Моя жена очень дружна была с вашей матушкой. По четвергам у меня собираются; нынче четверг, милости прошу ко мне запросто, – сказал губернатор, отпуская его.
Прямо от губернатора Николай взял перекладную и, посадив с собою вахмистра, поскакал за двадцать верст на завод к помещику. Все в это первое время пребывания его в Воронеже было для Николая весело и легко, и все, как это бывает, когда человек сам хорошо расположен, все ладилось и спорилось.
Помещик, к которому приехал Николай, был старый кавалерист холостяк, лошадиный знаток, охотник, владетель коверной, столетней запеканки, старого венгерского и чудных лошадей.
Николай в два слова купил за шесть тысяч семнадцать жеребцов на подбор (как он говорил) для казового конца своего ремонта. Пообедав и выпив немножко лишнего венгерского, Ростов, расцеловавшись с помещиком, с которым он уже сошелся на «ты», по отвратительной дороге, в самом веселом расположении духа, поскакал назад, беспрестанно погоняя ямщика, с тем чтобы поспеть на вечер к губернатору.
Переодевшись, надушившись и облив голову холодной подои, Николай хотя несколько поздно, но с готовой фразой: vaut mieux tard que jamais, [лучше поздно, чем никогда,] явился к губернатору.
Это был не бал, и не сказано было, что будут танцевать; но все знали, что Катерина Петровна будет играть на клавикордах вальсы и экосезы и что будут танцевать, и все, рассчитывая на это, съехались по бальному.
Губернская жизнь в 1812 году была точно такая же, как и всегда, только с тою разницею, что в городе было оживленнее по случаю прибытия многих богатых семей из Москвы и что, как и во всем, что происходило в то время в России, была заметна какая то особенная размашистость – море по колено, трын трава в жизни, да еще в том, что тот пошлый разговор, который необходим между людьми и который прежде велся о погоде и об общих знакомых, теперь велся о Москве, о войске и Наполеоне.
Общество, собранное у губернатора, было лучшее общество Воронежа.
Дам было очень много, было несколько московских знакомых Николая; но мужчин не было никого, кто бы сколько нибудь мог соперничать с георгиевским кавалером, ремонтером гусаром и вместе с тем добродушным и благовоспитанным графом Ростовым. В числе мужчин был один пленный итальянец – офицер французской армии, и Николай чувствовал, что присутствие этого пленного еще более возвышало значение его – русского героя. Это был как будто трофей. Николай чувствовал это, и ему казалось, что все так же смотрели на итальянца, и Николай обласкал этого офицера с достоинством и воздержностью.
Как только вошел Николай в своей гусарской форме, распространяя вокруг себя запах духов и вина, и сам сказал и слышал несколько раз сказанные ему слова: vaut mieux tard que jamais, его обступили; все взгляды обратились на него, и он сразу почувствовал, что вступил в подобающее ему в губернии и всегда приятное, но теперь, после долгого лишения, опьянившее его удовольствием положение всеобщего любимца. Не только на станциях, постоялых дворах и в коверной помещика были льстившиеся его вниманием служанки; но здесь, на вечере губернатора, было (как показалось Николаю) неисчерпаемое количество молоденьких дам и хорошеньких девиц, которые с нетерпением только ждали того, чтобы Николай обратил на них внимание. Дамы и девицы кокетничали с ним, и старушки с первого дня уже захлопотали о том, как бы женить и остепенить этого молодца повесу гусара. В числе этих последних была сама жена губернатора, которая приняла Ростова, как близкого родственника, и называла его «Nicolas» и «ты».
Катерина Петровна действительно стала играть вальсы и экосезы, и начались танцы, в которых Николай еще более пленил своей ловкостью все губернское общество. Он удивил даже всех своей особенной, развязной манерой в танцах. Николай сам был несколько удивлен своей манерой танцевать в этот вечер. Он никогда так не танцевал в Москве и счел бы даже неприличным и mauvais genre [дурным тоном] такую слишком развязную манеру танца; но здесь он чувствовал потребность удивить их всех чем нибудь необыкновенным, чем нибудь таким, что они должны были принять за обыкновенное в столицах, но неизвестное еще им в провинции.
Во весь вечер Николай обращал больше всего внимания на голубоглазую, полную и миловидную блондинку, жену одного из губернских чиновников. С тем наивным убеждением развеселившихся молодых людей, что чужие жены сотворены для них, Ростов не отходил от этой дамы и дружески, несколько заговорщически, обращался с ее мужем, как будто они хотя и не говорили этого, но знали, как славно они сойдутся – то есть Николай с женой этого мужа. Муж, однако, казалось, не разделял этого убеждения и старался мрачно обращаться с Ростовым. Но добродушная наивность Николая была так безгранична, что иногда муж невольно поддавался веселому настроению духа Николая. К концу вечера, однако, по мере того как лицо жены становилось все румянее и оживленнее, лицо ее мужа становилось все грустнее и бледнее, как будто доля оживления была одна на обоих, и по мере того как она увеличивалась в жене, она уменьшалась в муже.


Николай, с несходящей улыбкой на лице, несколько изогнувшись на кресле, сидел, близко наклоняясь над блондинкой и говоря ей мифологические комплименты.
Переменяя бойко положение ног в натянутых рейтузах, распространяя от себя запах духов и любуясь и своей дамой, и собою, и красивыми формами своих ног под натянутыми кичкирами, Николай говорил блондинке, что он хочет здесь, в Воронеже, похитить одну даму.
– Какую же?
– Прелестную, божественную. Глаза у ней (Николай посмотрел на собеседницу) голубые, рот – кораллы, белизна… – он глядел на плечи, – стан – Дианы…
Муж подошел к ним и мрачно спросил у жены, о чем она говорит.
– А! Никита Иваныч, – сказал Николай, учтиво вставая. И, как бы желая, чтобы Никита Иваныч принял участие в его шутках, он начал и ему сообщать свое намерение похитить одну блондинку.
Муж улыбался угрюмо, жена весело. Добрая губернаторша с неодобрительным видом подошла к ним.
– Анна Игнатьевна хочет тебя видеть, Nicolas, – сказала она, таким голосом выговаривая слова: Анна Игнатьевна, что Ростову сейчас стало понятно, что Анна Игнатьевна очень важная дама. – Пойдем, Nicolas. Ведь ты позволил мне так называть тебя?
– О да, ma tante. Кто же это?
– Анна Игнатьевна Мальвинцева. Она слышала о тебе от своей племянницы, как ты спас ее… Угадаешь?..
– Мало ли я их там спасал! – сказал Николай.
– Ее племянницу, княжну Болконскую. Она здесь, в Воронеже, с теткой. Ого! как покраснел! Что, или?..
– И не думал, полноте, ma tante.
– Ну хорошо, хорошо. О! какой ты!
Губернаторша подводила его к высокой и очень толстой старухе в голубом токе, только что кончившей свою карточную партию с самыми важными лицами в городе. Это была Мальвинцева, тетка княжны Марьи по матери, богатая бездетная вдова, жившая всегда в Воронеже. Она стояла, рассчитываясь за карты, когда Ростов подошел к ней. Она строго и важно прищурилась, взглянула на него и продолжала бранить генерала, выигравшего у нее.
– Очень рада, мой милый, – сказала она, протянув ему руку. – Милости прошу ко мне.
Поговорив о княжне Марье и покойнике ее отце, которого, видимо, не любила Мальвинцева, и расспросив о том, что Николай знал о князе Андрее, который тоже, видимо, не пользовался ее милостями, важная старуха отпустила его, повторив приглашение быть у нее.
Николай обещал и опять покраснел, когда откланивался Мальвинцевой. При упоминании о княжне Марье Ростов испытывал непонятное для него самого чувство застенчивости, даже страха.
Отходя от Мальвинцевой, Ростов хотел вернуться к танцам, но маленькая губернаторша положила свою пухленькую ручку на рукав Николая и, сказав, что ей нужно поговорить с ним, повела его в диванную, из которой бывшие в ней вышли тотчас же, чтобы не мешать губернаторше.
– Знаешь, mon cher, – сказала губернаторша с серьезным выражением маленького доброго лица, – вот это тебе точно партия; хочешь, я тебя сосватаю?
– Кого, ma tante? – спросил Николай.
– Княжну сосватаю. Катерина Петровна говорит, что Лили, а по моему, нет, – княжна. Хочешь? Я уверена, твоя maman благодарить будет. Право, какая девушка, прелесть! И она совсем не так дурна.
– Совсем нет, – как бы обидевшись, сказал Николай. – Я, ma tante, как следует солдату, никуда не напрашиваюсь и ни от чего не отказываюсь, – сказал Ростов прежде, чем он успел подумать о том, что он говорит.
– Так помни же: это не шутка.
– Какая шутка!
– Да, да, – как бы сама с собою говоря, сказала губернаторша. – А вот что еще, mon cher, entre autres. Vous etes trop assidu aupres de l'autre, la blonde. [мой друг. Ты слишком ухаживаешь за той, за белокурой.] Муж уж жалок, право…
– Ах нет, мы с ним друзья, – в простоте душевной сказал Николай: ему и в голову не приходило, чтобы такое веселое для него препровождение времени могло бы быть для кого нибудь не весело.
«Что я за глупость сказал, однако, губернаторше! – вдруг за ужином вспомнилось Николаю. – Она точно сватать начнет, а Соня?..» И, прощаясь с губернаторшей, когда она, улыбаясь, еще раз сказала ему: «Ну, так помни же», – он отвел ее в сторону: