Построение опорного плана методом Фогеля

Алгоритм решения транспортной задачи

Аналитическое решение задачи

1. Построение исходного опорного плана.

2. Оценка полученного плана.

3. Переход от имеющегося опорного плана к новому опорному плану с меньшими транспортными затратами.

2.3.1 Построение опорного плана методом северо-западного угла

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:

						Запасы
Потребности

Проверим необходимое и достаточное условие разрешимости задачи.
Σa = 70 + 80 + 90 = 240
Σb = 30 + 30 + 60 + 90 + 30 = 240
Условие баланса соблюдается. Запасы равны потребностям.
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	7	4	8	3	6	70
2	5	5	4	3	8	80
3	5	6	5	8	6	90
Потребности	30	30	60	90	30

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

	1	2	3	4	5	Запасы
1	7[30]	4[30]	8[10]	3	6	70
2	5	5	4[50]	3[30]	8	80
3	5	6	5	8[60]	6[30]	90
Потребности	30	30	60	90	30

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

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

						Запасы
Потребности

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 78 + 94 + 29 + 86 = 287
∑ b = 49 + 60 + 78 + 50 + 50 = 287
Занесем исходные данные в распределительную таблицу.

						Запасы
Потребности

1. Используя метод Фогеля, построим первый опорный план транспортной задачи.
Данный метод состоит в следующем:
1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.
1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 7. Разность равна 2.
Первый минимальный элемент строки N=2 равен 6. Второй минимальный элемент строки N=2 равен 29. Разность равна 23.
Первый минимальный элемент строки N=3 равен 11. Второй минимальный элемент строки N=3 равен 19. Разность равна 8.
Первый минимальный элемент строки N=4 равен 13. Второй минимальный элемент строки N=4 равен 28. Разность равна 15.
Первый минимальный элемент столбца N=1 равен 9. Второй минимальный элемент столбца N=1 равен 30. Разность равна 21.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=3 равен 6. Второй минимальный элемент столбца N=3 равен 7. Разность равна 1.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (2). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (3).

						Запасы	Разности по строкам
Потребности
Разности по столбцам

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 9. Разность равна 4.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 36. Разность равна 7.
Первый минимальный элемент строки N=3 равен 19. Второй минимальный элемент строки N=3 равен 20. Разность равна 1.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 30. Разность равна 2.
Первый минимальный элемент столбца N=1 равен 9. Второй минимальный элемент столбца N=1 равен 30. Разность равна 21.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (1). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (1).

						Запасы	Разности по строкам
Потребности
Разности по столбцам			-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=1 равен 5. Второй минимальный элемент строки N=1 равен 10. Разность равна 5.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 38. Разность равна 9.
Первый минимальный элемент строки N=3 равен 19. Второй минимальный элемент строки N=3 равен 20. Разность равна 1.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 39. Разность равна 11.
Первый минимальный элемент столбца N=2 равен 5. Второй минимальный элемент столбца N=2 равен 20. Разность равна 15.
Первый минимальный элемент столбца N=4 равен 10. Второй минимальный элемент столбца N=4 равен 25. Разность равна 15.
Первый минимальный элемент столбца N=5 равен 18. Второй минимальный элемент столбца N=5 равен 19. Разность равна 1.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (4).

						Запасы	Разности по строкам
Потребности
Разности по столбцам	-		-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 38. Разность равна 9.
Первый минимальный элемент строки N=3 равен 19. Второй минимальный элемент строки N=3 равен 20. Разность равна 1.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 39. Разность равна 11.
Первый минимальный элемент столбца N=2 равен 20. Второй минимальный элемент столбца N=2 равен 28. Разность равна 8.
Первый минимальный элемент столбца N=4 равен 25. Второй минимальный элемент столбца N=4 равен 38. Разность равна 13.
Первый минимальный элемент столбца N=5 равен 19. Второй минимальный элемент столбца N=5 равен 40. Разность равна 21.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (5).

						Запасы	Разности по строкам
							-
Потребности
Разности по столбцам	-		-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=2 равен 29. Второй минимальный элемент строки N=2 равен 38. Разность равна 9.
Первый минимальный элемент строки N=4 равен 28. Второй минимальный элемент строки N=4 равен 39. Разность равна 11.
Первый минимальный элемент столбца N=2 равен 28. Второй минимальный элемент столбца N=2 равен 29. Разность равна 1.
Первый минимальный элемент столбца N=4 равен 38. Второй минимальный элемент столбца N=4 равен 39. Разность равна 1.
Первый минимальный элемент столбца N=5 равен 40. Второй минимальный элемент столбца N=5 равен 50. Разность равна 10.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (2).

						Запасы	Разности по строкам
							-
							-
Потребности
Разности по столбцам	-		-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=2 равен 38. Второй минимальный элемент строки N=2 равен 40. Разность равна 2.
Первый минимальный элемент строки N=4 равен 39. Второй минимальный элемент строки N=4 равен 50. Разность равна 11.
Первый минимальный элемент столбца N=4 равен 38. Второй минимальный элемент столбца N=4 равен 39. Разность равна 1.
Первый минимальный элемент столбца N=5 равен 40. Второй минимальный элемент столбца N=5 равен 50. Разность равна 10.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (4).

						Запасы	Разности по строкам
							-
							-
Потребности
Разности по столбцам	-	-	-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=2 равен 40. Второй минимальный элемент строки N=2 равен 40. Разность равна 0.
Первый минимальный элемент строки N=4 равен 50. Второй минимальный элемент строки N=4 равен 50. Разность равна 0.
Первый минимальный элемент столбца N=5 равен 40. Второй минимальный элемент столбца N=5 равен 50. Разность равна 10.
Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (5).

						Запасы	Разности по строкам
							-
							-
Потребности
Разности по столбцам	-	-	-	-

1. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Первый минимальный элемент строки N=4 равен 50. Второй минимальный элемент строки N=4 равен 50. Разность равна 0.
Первый минимальный элемент столбца N=5 равен 50. Второй минимальный элемент столбца N=5 равен 50. Разность равна 0.
Вычислив все эти разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (5).

						Запасы	Разности по строкам
							-
							-
							-
Потребности
Разности по столбцам	-	-	-	-

						Запасы
	9[49]			10[29]
			6[78]		40[16]
					19[29]
		28[60]		39[21]	50[5]
Потребности

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

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