Метод аппроксимации Фогеля при решении ТЗ.

При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

Пример (4):

Найти опорный план примера (1) методом аппроксимации Фогеля. Исходные данные приведены в таблице 5.

Таблица 5.

Пункты отправления	Пункты назначения				Запасы
	7	8	1	2	160
	4	5	9	8	140
	9	2	3	6	170
Потребности	120	50	190	110	470

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

Так, в строке минимальный тариф равен 4, а следующий за ним равен 5, разность между ними . Точно так же разность между минимальными элементами в столбце равна . Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу . В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки
и столбца . Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта . Поэтому исключим из рассмотрения столбец и будем считать запасы пункта равными единиц.

Таблица 6.

Пункты отправления	Пункты назначения	Запасы	Разности по строкам
	7	8										1 50	2 110	160	1	6
	4 120	5 20	9	8	140	1	1	1	1	1	0
	9	2 30	3 140	6	170	1	1	1	7
Потреб-ности	120	50	190	110	470
Разн-ость по столб-цам	3	2	2	4
	3	3	2
	5	3	6
	5	3
		0
		0

После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы 6. Как видно из этой таблицы, наибольшая указанная разность соответствует строке .Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом . Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте полностью исчерпаны, а потребности в пункте стали равными единиц. Исключим из рассмотрения строку и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки и столбца , строки и столбца строки и столбца строки и столбца В результате получим опорный план:

При этом плане общая стоимость перевозок такова:

.

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: