Математическая модель транспортной задачи

Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы нашли начальное  решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀ = 1 * 30 + 4 * 20 + 4 * 5 + 3 * 5 + 5 * 10 = 195 ден. ед.

Общие затраты на доставку всей продукции, для начального решения , составляют 195 ден. ед. .

Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:

·  Находим потенциалы поставщиков и потребителей для имеющегося решения.

·  Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

·  Находим новое решение, как минимум, не хуже предыдущего.

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

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

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

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

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

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

A₃B₁ , A₃B₃ , A₂B₃ , A₂B₁

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

Среди ячеек цикла A₃B₃ , A₂B₁ , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 10, 20 } = 10

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

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

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

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

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

От поставщика A₂ к потребителю B₃ дополнительно поставим 10 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты увеличатся на 4 * 10 ден. ед.

Сократим поставку от поставщика A₂ к потребителю B₁ на 10 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты уменьшатся на 4 * 10 ден. ед.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

Что в итоге?

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

4 * 10 - 5 * 10 + 4 * 10 - 4 * 10 = ( 4 - 5 + 4 - 4 ) * 10 = -1 * 10   ден. ед.

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

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

Общие затраты на доставку всей продукции, для данного  решения, составляют S₀ = 195 + ( - 10 ) = 185 ден. ед. .

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

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

Ячейка A₃B₁ станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₃ к потребителю B₁ .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15