Другие предметы \ Исследование операций и методы оптимизации

Задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления, страница 3

W=19*14+4*2+10*5+11*3+7*7+4*17+4*19+7*15+21*2+13*10=827

Венгерский метод

В каждой строке находим минимальный элемент, эту стоимость обнуляем и в эти ячейки записываем максимально возможное количество единиц груза. Затем выписываем количество недостающих единиц груза, невязки. Далее ищем ненулевую ячейку с минимальным элементом как в строке, так и в столбце. Обнуляем эту стоимость и отнимаем от элементов из строки и столбца, где она находится, а к остальным элементам прибавляем, пересчитываем невязки. Цикл повторяем до тех пор, пока все невязки не будут нулевыми. Затем в полученную таблицу подставляем количество единиц груза из первой таблицы (т.е. северо-западного угла).

0	25	18	19	23	23	0
23					23	0
0	17	16	24	0	25	0
10				15	25	0
29	0	7	15	22	25	14
	11				25	14
0	20	17	23	10	27	27
					27	27
33	11	11	11	34	100=100
0	0	11	11	19

0	32	11	26		30		23		0
23
0	24	9	31		0		25		0
10					15
22	0	0	8		15		25		3
	11	11
0	27	17	30		17		27		27

33	11	11	11		34		100=100
0	0	0	11		19
0	40	19	18	38		23		0
23
0	32	17	23	0		25		0
10				15
14	0	0	0	7		25		0
	11	11	3
0	35	24	22	25		27		27

33	11	11	11	34		100=100
0	0	11	8	19

0	47	26	25	31	23	0
23					23	0
0	39	24	30	0	25	0
10				15	25	0
7	0	0	0	0	25	0
	11	11	3	0	25	0
0	42	31	29	18	27	27
					27	27
33	11	11	11	34	100=100
0	0	11	8	19

1 2 3 4

Скачать файл