Пример

Имеются 2 Поставщика (A₁,A₂) и 3 Потребителя (B₁,B₂,B₃) однородной продукции. Запасы Поставщиков, потребности Потребителей и стоимости перевозок единицы продукции представлены в таб.1. Найти оптимальный план перевозок.

	B1	B2	B3
А1
А2

Шаг 1. Чтобы начать решение транспортной задачи, необходимо определить, является эта задача с правильным балансом или нет. Для этого необходимо проверить выполнение условия (Е). В случае выполнения условия (Е) находим первую перевозку методом северо-западного угла, иначе сводим задачу к задаче с правильным балансом, вводя фиктивного Поставщика или фиктивного Потребителя.

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

			11
				7
10
	7

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

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

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

4.Поскольку в таблице осталась одна строка (вторая) и один столбец (третий) – это последний шаг. Удовлетворяем запросы третьего Потребителя, исчерпывая запасы второго Поставщика.

Количество заполненных клеток равно 4, m+n-1=2+3-1=4. Следовательно, найденное решение является невырожденным. Стоимость перевозок f₁=8∙10+6∙1+5∙7+7∙7=170.

Шаг 3. (Метод потенциалов)

1. Используя формулу (1) и полагая u₁=0, для заполненных клеток находят потенциалы (числа) поставщиков - u_i (i= 2,3,…m) и потребителей - v_j (j=1,2,…n).

u₁+v₁=c₁₁. 0+ v₁=8→ v₁=8.

u₁+v₂=c₁₂. 0+ v₂=6→ v₂=6.

u₂+v₂=c₂₂. u₂+ 6=5→ u₂=-1.

u₂+v₃=c₂₃. -1+ v₃=7→ v₃=-8.

vj ui
-1

2. Для проверки оптимальности полученного решения, вычисляем для незаполненных клеток оценки ∆_ij по формуле (2).

∆₁₃=u₁+v₃-c₁₃^. ∆₁₃=0+8-5=3>0.

∆₂₁=u₂+v₁-c₂₁. ∆₂₁=-1+8-4=3>0.

Найденное решение не оптимально, т.к. оценки ∆₁₃ и ∆₂₁- положительны. Для перехода к следующему базисному решению необходимо из положительных оценок выбрать – максимальную и переместить перевозку в эту клетку.. В нашем примере оценки равны, выберем первую.

3. Для правильного перемещения перевозок, чтобы не нарушить ограничений, строится цикл, т.е. замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящей через заполненные клетки. Цикл строится следующим образом: вычеркиваем все строки и столбцы, содержащие ровно одну заполненную клетку (выбранная клетка при этом считается заполненной). Все остальные заполненные клетки составляют цикл и лежат в его углах. В каждой клетке цикла, начиная с незаполненной, проставляют поочередно «+ » и «- ». Значение выбирается минимальным из клеток со знаком «- ».

vj ui
	1-	+
-1
	7+	7-

=min(1,7)=1.

Получаем новую таблицу перевозок

Стоимость перевозок f₂=f₁- ^.∆₁₃=170-1^. 3=167.

Повторяем Шаг 3, пока не получим оптимальное решение.

Находим потенциалы

vj ui

Вычисляем оценки ∆₁₂ и ∆₂₁

∆₁₂ =u₁+v₂-c₁₂=0+3-6= -3<0

∆₂₁=u₂+v₁-c₂₁=2+8-4= 6>0.

Строим цикл

vj ui
10-		1+
+		6-

=min(10,6)=6.

Получаем новую таблицу перевозок

Стоимость перевозок f₃=f₂- ^.∆₂₁=167- 6^. 6=131.

Находим потенциалы.

vj ui
-4

Вычисляем оценки ∆₁₂ и ∆₂₁

∆₁₂ =u₁+v₂-c₁₂=0+9-6= 3>0

∆₂₃=u₂+v₃-c₂₃= -4+5-7= -6<0.

Строим цикл

vj ui
4-	+
-4
6+	8-

=min(8,4)=4.

Получаем новую таблицу перевозок

Стоимость перевозок f₄=f₃- ^.∆₁₂=131- 4^. 3=119.

Находим потенциалы

vj ui
-1

Вычисляем оценки ∆₁₁ и ∆₂₁

∆₁₁ =u₁+v₁-c₁₁=0+5-8= -3<0

∆₂₃=u₂+v₃-c₂₃= -1+5-7= -3<0.

Найденная перевозка (119) – оптимальна.