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

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

min = { 60, 50 } = 50

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

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

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

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

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

От поставщика A1 к потребителю B4 дополнительно поставим 50 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты увеличатся на 7 * 50 ден. ед.

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

Что в итоге?

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

17 * 50 - 16 * 50 + 7 * 50 - 16 * 50 = ( 17 - 16 + 7 - 16 ) * 50 = -8 * 50   ден. ед.

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

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

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

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

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

            ячейки A1B3, общая стоимость доставки всей продукции изменилась бы на 13 * 50 = -1 * 50 = -50 ден. ед.

            ячейки A3B3, общая стоимость доставки всей продукции изменилась бы на 33 * 50 = -5 * 50 = -250 ден. ед.

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

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

Поставщик

Потребитель

Запас

B 1

B 2

B 3

B 4

A 1

70

A 2

80

A 3

110

Потребность

50

70

60

80

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