Как решать транспортную задачу(ТЗ)

Как решать транспортную задачу(ТЗ)

Суть ТЗ: есть несколько складов и несколько заказчиков. Есть некоторый абстрактный продукт (задаваемый количеством единиц этого продукта) который содержится на складах и который надо доставить, в требуемом количестве, заказчикам. Задана так же стоимость провоза одной единицы продукта со склада к заказчику. Причем стоимость провоза может различаться в зависимости от того, с какого склада и к какому заказчику везут товар. Нужно найти оптимальную стратегию перевозок, при которой выполняются все три условия:

1. полностью удовлетворяется потребность заказчиков в продукте

2. партия продукта полностью вывозится со всех складов (т.е. после перевозок – все склады пусты)

3. стоимость перевозок наименьшая.

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

Пример

Таблица перевозок:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

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

Например: провоз 10 единиц продукта со второго слада ко второму заказчику будет стоить 10*6=60 у.е.

На таблице, факт того что мы везем 10 единиц продукта со второго слада ко второму заказчику записывается так:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Для 110 единиц – стоимость провоза 110*6=660 у.е.

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Для 110 единиц – стоимость провоза 110*6=660 у.е.

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

Увозя N единиц товара к заказчику, мы должны (мысленно, или явно указывая это в табл.) отнять число N от числа товара на соответствующем складе и от числа требуемого количества товара у соответствующего заказчика.

Т.е. например заказчик требует 50 единиц товара, склад содержит 60 единиц товара, посылаем этому заказчику с этого склада 30 единиц, после этого мы должны учитывать, что теперь заказчику нужно привезти откуда то еще 20 единиц, а на соответствующем складе осталось 30 единиц.

Важные ограничения:

(1*)Нельзя вывозить товара со склада больше, чем там есть на самом деле.

(2*)Нельзя привозить заказчику товара больше, чем ему надо.

Т.е. нельзя делать так:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Потому что 20+110 = 130. 130 < 120 (больше, чем есть на складе)

Нельзя делать так:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Потому что 60+50+100=210 > 40 (больше чем надо заказчику)

Однако вполне допустимы такие перевозки:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Есть несколько методов построения стратегий перевозок

Метод северо-западного угла

1)Берем самую верхнюю левую пустую ячейку.

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

2)Фигачим туда максимально возможное число так, что бы не нарушить (1*) и (2*).

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Повторяем точно так же для всех остальных незаполненных верхних левых ячеек:

Фигачим 40 потому что на складе осталось именно 40 (60-20=40), а заказчику все равно надо больше.

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим ноль, потому что на складе больше нифига нет (60-20-40=0)

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим ноль, потому что на складе по прежнему нифига нет

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 0 потому что первый заказчик уже получил все что хотел (20=20)

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 70 т.к. заказчику нужно для полного счастья еще 70 единиц (70+40=110), и на складе эти 70 единиц как раз есть (120-0=120<70)

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигичим 40 т.к. заказчику нужно для полного счастья 40 единиц (0+40=40), и на складе эти 40 единиц как раз есть (120-0-70=50<40)

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 10 т.к. это все что осталось на втором складе, а заказчику все равно надо больше.

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 0 потому что первый заказчик уже получил все что хотел

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 0 потому что второй заказчик уже получил все что хотел

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 0 потому что третий заказчик уже получил все что хотел

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Фигачим 100 потому что заказчику надо 100, и на складе как раз есть 100 единиц

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

В итоге получаем таблицу:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

При решении можно не писать все эти промежуточные таблицы, а написать сразу эту итоговую.

Расшифровка таблицы:

1-ый заказчик получает все 20 единиц с первого склада

2-ой заказчик получает 40 единиц с 1-го склада, 70 со второго.

3-ий заказчик получает 40 единиц со 2-го склада

4-ый заказчик получает 10 единиц со второго склада и 100 с третьего склада

С 1-го склада перевезли 20 единиц первому заказчику, 40 – второму заказчику

Со 2-го склада перевезли 70 ед. 2-му заказчику, 40 ед. 3-ему заказчику, 10 ед. 4-ому заказчику

С 3-го склада перевезли 100 ед. 4-ому заказчику

Общая стоимость всех перевозок:

(1*20+2*40+5*0+3*0)+(1*0+6*70+5*40+2*10)+(6*0+3*0+7*0+4*100) = 20+80+420+200+20+400=1140

Алгоритм «план минимума по строке»

1)Берем строку.

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

2)Ищем среди пустых ячеек этой строки ячейку с наименьшей стоимостью перевозки.

1<2<3<5

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

3)Так же, как и в прошлом алгоритме, фигачим туда максимально возможное число так, что бы не нарушить (1*) и (2*).

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Повторяем так, пока не кончится весь товар на соответствующем этой строке складе

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

2<3<5

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

3<5

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Затем переходим к следующей строке.

1<2<5<6

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

2<5<6

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

5<6

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

И последняя строка

3<4<6<7

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

4<6<7

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

6<7

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Общая стоимость всех перевозок:

(1*20+2*40)+(5*10+2*110)+(3*70+7*30) = 790

Алгоритм «план минимума по столбцу»

Алгоритм во многом аналогичен минимуму по строке:

1)Берем столбец

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

3) Фигачим туда максимально возможное число так, что бы не нарушить (1*) и (2*).

4) Повторяем так, пока полностью не удовлетворим требования заказчика.

5) Переходим к след. столбцу.

Итоговая таблица для данного алгоритма:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Общая стоимость всех перевозок:

1*20+(2*40+3*70)+5*40+(2*80+4*30) = 790

Алгоритм «план минимального элемента»

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

2)Фигачим туда максимально возможное число так, что бы не нарушить (1*) и (2*).

3)Повторить 1,2 пока не увезем весь товар со складов и не удовлетворим все требования заказчиков

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Итог:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Общая стоимость всех перевозок:

1*20+2*40+2*110+3*70+5*10+7*30=790

Метод потенциалов

1) Определяется начальный опорный план перевозок любым из вышеперечисленных способов.

2) Для каждой строки и каждого столбца вводятся и рассчитываются потенциалы и соответственно.

Вот как это выглядит в таблице (в качестве начального опорного плана взята итоговая таблица, полученная в ходе выполнения алгоритма «план минимального элемента»):

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Для расчета коэффициента используется формула

где - стоимость перевозки, записанная в i-строке, j-ом столбце.

Расчет потенциалов начинается с того что элемент предполагают равным нулю:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Дальше решаются уравнения для тех которые соответствуют ненулевым ячейкам:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Далее мы видим, что по формуле больше ничего подсчитать нельзя, так как остальные элементы первой строки = 0

Начинаем искать ненулевой элемент в таблице который можно зафигачить в одну из формул

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

Такой элемент всего один:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Далее ищем подходящий элемент для формулы

Вот подходящий элемент:

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4

Теперь можем найти

Номер склада	Количество товара на складе	Потребность потребителя 1	Потребность потребителя 2	Потребность потребителя 3	Потребность потребителя 4
										-1

И, наконец, находим последний потенциал

Номер склада

Количество товара на складе

Потребность потребителя 1

Потребность потребителя 2

Потребность потребителя 3

Потребность потребителя 4

Дата добавления: 2015-09-29