Нахождение начального опорного плана методом Фогеля

Данный метод состоит из ряда однотипных шагов (этапов), на каждом из которых:

• для каждой линии (по строкам и столбцам) определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность (жирным шрифтом);

• в линии с наибольшей разностью заполняется максимально возможным значением клетка, соответствующая минимальному тарифу;

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

Когда в процессе заполнения таблицы, на каком-то этапе незаполненными оказываются только клетки в одной линии, то их необходимо заполнить в порядке увеличения тарифов.

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

Пример 2.4

По данным примера 2.1 найти начальный опорный план методом Фогеля.

Решение

Воспользуемся распределительной таблицей закрытой модели ТЗ (табл. 2.3).

На первом этапе максимальная разность «4» принадлежит столбцу . Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (2,4) и. Столбецисключаем, а в хранилищепри этом останется 90–40=50 т топлива.

На втором этапе максимальная разность «3» принадлежит строкам и. Выбираем любую из них, например, строку. Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и. Столбецисключаем, а в хранилищепри этом останется 70–10=60 т топлива.

На третьем этапе максимальная разность «2» принадлежит столбцам и. Выбираем любой из них, например, столбец. Заполняем клетку с минимальным тарифом в этом столбце. Это клетка (3,1) и. Исключаем по своему усмотрению либо третьего поставщика, либо первого потребителя. Пусть исключили первого потребителя. Тогда в хранилищеосталось 50–50=0 т топлива.

На четвертом этапе максимальная разность «3» принадлежит строке . Заполняем клетку с минимальным тарифом в этой строке. Это клетка (3,3) и. Строкуисключаем, а потребителюнедостает 40–0=40 т топлива.

На пятом этапе максимальная разность «2» принадлежит строке и столбцу. Выбираем любую из этих линий, например, строку. Заполняем клетку с минимальным тарифом в этой строке. Это клетка (1,5) и. Строкуисключаем, а потребителюнедостает 70–50=20 т топлива.

Т.к. незаполненные клетки остались в одной линии (в строке клетки (1,2) и (1,3)), то заполняем их в порядке увеличения тарифов, т.е. сначала заполним клетку (1,3):, затем клетку (1,2) и.

Итак, в распределительной таблице найден невырожденный (число занятых клеток k=m+n–1=3+5–1=7) начальный опорный план (табл. 2.6).

Таблица 2.6

													Этапы
													1	2	3	4	5
			5		4		3		6		0	70	3	3	1	1	1
				20		40				10
			4		3		5		1		0	90	1	3	1	2	2
				50				40
			2		4		1		5		0	50	1	1	1	3	–
		50				0
		50		70		40		40		10
Э т а п	1	2		1		2		4		0
	2	2		1		2		–		0
	3	2		1		2		–		–
	4	–		1		2		–		–
ы	5	–		1		2		–		–

или . Значение целевой функции на найденном начальном опорном плане (транспортные издержки для этого плана):

( усл. ден. ед.)