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

Оценка свободной ячейки A2B4 (незадействованного маршрута) отрицательная (24 =-2) , следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A2B4:

Поставьте курсор мыши в выбранную свободную ячейку A2B4. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A2B4. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A2B4 :

A2B4 , A2B2 , A3B2 , A3B4

Пусть ячейка A2B4, для которой мы строили цикл, имеет порядковый номер один.

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

Среди ячеек цикла A2B2 , A3B4 , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 20, 10 } = 10

В данном случае, это ячейка A3B4.

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A3 к потребителю B4, по которому доставляется меньше всего (10) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

От ячеек цикла с четными номерами отнимает 10. К ячейкам с нечетными номерами прибавляем 10.

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B4. По данному маршруту доставим 10 единиц продукции, по цене доставки 8 за единицу продукции. Общие затраты увеличатся на 8 * 10 ден. ед.

Сократим поставку от поставщика A2 к потребителю B2 на 10 единиц продукции, по цене доставки 11 за единицу продукции. Общие затраты уменьшатся на 11 * 10 ден. ед.

От поставщика A3 к потребителю B2 дополнительно поставим 10 единиц продукции, по цене доставки 17 за единицу продукции. Общие затраты увеличатся на 17 * 10 ден. ед.

По маршруту от поставщика A3 к потребителю B4 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 16 * 10 ден. ед.

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

Что в итоге?

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

8 * 10 - 11 * 10 + 17 * 10 - 16 * 10 = ( 8 - 11 + 17 - 16 ) * 10 = -2 * 10   ден. ед.

Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.

ГЛАВНОЕ : В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 24 * 10 = -2 * 10 = -20 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 2860 + ( - 20 ) = 2840 ден. ед. .

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

Ячейка A3B4 выйдет из базиса, мы перестали доставлять продукцию от поставщика A3 к потребителю B4

Ячейка A2B4 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A2 к потребителю B4 .

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.  (ui + vj = cij, где cij - тариф клетки AiBj)  Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.