3.2 Метод минимальной стоимости

Алгоритм метода минимальной стоимости:

1. Находим ячейку таблицы с наименьшей стоимостью.

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

3. Повторяем шаг 1 и шаг 2 до тех пор, пока все запасы ресурсов не закончатся.

Решение методом минимальной стоимости (смотреть рисунок 6).

											запасы
		36		49		32		45	7	28	7
	4	29		37	21	50		33		41	25
		42	12	30		38		46	1	34	13
		35		43		26		39		47	1
					1
		48		31	3	44	8	27		40	19
									8
спрос	4		12		25		8		16

Рисунок 6 – Решение методом минимальной стоимости

Сосчитаем общие затраты при данном распределении:

W =7*28+4*29+21*50+12*30+34+26+3*44+8*27+8*40=2450 [мс]

3.3 Метод аппроксимации Фогеля

Алгоритм решения методом аппроксимации Фогеля:

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

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

3. Затем заново рассчитываем штрафы, не учитывая строки (или столбцы) закончившимся ресурсом и т.д.

Решение методом аппроксимации Фогеля (смотреть рисунок 7).

										ШТРАФЫ
	36		49	7	32		45		28	7	4		4	4	4	4	4	-	-
4	29		37	5	50		33	16	41	25	4		4	4	4	4	9	-	-
	42	1	30	12	38		46		34	13	4		4	4	4	4	4	-	-
	35		43	1	26		39		47	1	9		-	-	-	-	-	-	-
	48	11	31		44	8	27		40	19	4		4	4	9	-	-	-	-
4		12		25		8		16		65
6		1		6		6		6
7		1		6		6		6
-		1		6		6		6
-		1		6		-		6
-		7		6		-		6
-		-		6		-		6
-		-		6		-		-
-		-		12		-		-
ШТРАФЫ

Рисунок 7 – Решение методом аппроксимации Фогеля

Сосчитаем общие затраты при данном распределении:

W = 7*32+4*29+5*50+41*16+30+12*38+26+31*11+27*8=2315[мс]

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