3. 2. Метод наименьшей стоимости.

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

В данном случае заполнение таблицы начинается с клетки с координатами D1, для которой мы имеем значение стоимости перевозки С11=1. Ставим в эту клетку 64 и тем самым выполняем полностью заявки 1-го района, и исключаем из рассмотрения первый столбец. У АТС D все номера уже использованы, поэтому эту строку мы исключаем из дальнейшего рассмотрения.

Отыскиваем наименьшую стоимость в таблице, заполняем соответствующую клетку (С2, 48 номеров) и исключаем из рассмотрения второй столбец. У АТС C все номера уже использованы, поэтому эту строку мы исключаем из дальнейшего рассмотрения.

Отыскиваем наименьшую стоимость в оставшихся клетках таблицы, заполняем соответствующую клетку (B3, 44 номера). У АТС B все номера уже использованы, поэтому эту строку мы исключаем из дальнейшего рассмотрения.

У района 3 осталось 76 неудовлетворенных заявок. Отыскиваем во 3-ем столбце наименьшую из оставшихся стоимостей (клетка А3) и удовлетворяем потребности 3-его района из АТС А (76 номеров). И исключаем из рассмотрения 3-ий столбец.

Отыскиваем наименьшую стоимость в оставшихся клетках таблицы, заполняем соответствующую клетку (А5, 34 номера).Так как заявки 5-го района полностью удовлетворены, то исключаем из рассмотрения 5-ый столбец.

Отыскиваем наименьшую стоимость в оставшихся клетках таблицы, заполняем соответствующую клетку (А4, 10 номеров). Исключаем из рассмотрения 1-ую строку, т.к. на АТС А не осталось свободной номерной емкости.

В 4-ом районе остались не удовлетворенными 30 заявок, которые мы присваиваем фиктивной строке в клетку Е4.

Окончательный вид опорного плана по методу наименьшей стоимости приведен в таблице 3.

Общий объём перевозок для этого плана составит:

S=4*76+4*10+3*34+2*40+3*44+1*48+1*64+0*30=770

Табл.3

	1	2	3	4	5	Ресурсы
A	2	3	4 76	4 10	3 34	120
B	2	2 40	3 44	4	3	84
C	2	1 48	3	2	3	48
D	1 64	2	3	4	5	64
E	0	0	0	0 30	0 0	30
Заявки	64	88	120	40	34

3.3. Метод Фогеля.

В большинстве случаев этот способ делает опорный план ,наиболее близкий к оптимальному. Использовать этот метод рекомендуется при расчётах вручную.

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

Алгоритм метода включает следующие основные этапы:

1. Вычисление разностей в каждой строке и в каждом столбце матрицы между наименьшей стоимостью и ближайшей к ней по величине (табл.4). Разности по строкам записываются справа в столбце разностей, разности по столбцам - внизу в строке разностей.

В данном примере, для строки А разность равна А5-А6=1-0=1 и т.д.

2. Находим из всех разностей максимальную. В примере это 3(строка В) (если их несколько, то берём любую из них).

3. Помещаем в клетку, где находится наименьшая стоимость перевозки(В6=0) в строку с наибольшей разностью максимально возможного количества ресурсов(5). Поскольку при этом все запросы пункта 6 удовлетворены то этот столбец из дальнейшего рассмотрения исключаем.

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

5. Найдём минимальный элемент в строке или столбце с максимальной разностью и поместим в эту клетку максимально возможное количество ресурса. Затем возвращаемся к этапу 4.

Общая стоимость этого плана

S=4*116+3*4+2*80+3*4+1*8+2*40+1*64+0*30=800

Табл.4

	1	2	3	4	5	ресурсы
A	2	3	4 116	4	3 4	120	1	1	0	0	1	1
B	2	2 80	3 4	4	3	84	0	0	1	1	0	--
C	2	1 8	3	2 40	3	48	1	1	2	--	--	--
D	1 64	2	3	4	5	64	1	1	--	--	--	--
Е	0	0	0	0	0 30	30	0	0	0	0	0	0
За	64	88	120	40	34
	1	1	0	2	0
	1	1	0	--	0
	--	1	0	--	0
	--	1	1	--	0
	--	--	1	--	0
	--	--	4	--	3