Венгерский метод. Содержание введение 4 математическая постановка задачи 5 определение опорного плана 8

• Название: Содержание введение 4 математическая постановка задачи 5 определение опорного плана 8
• Анкор: Венгерский метод
• Дата: 08.01.2022
• Размер: 105.72 Kb.
• Имя файла: VENGERSKIJ_METOD.docx
• Тип: Задача; #326079
• страница: 3 из 5

2.3. Метод минимального элемента

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

Пример 2. Найти опорный план транспортной задачи представленной в табл. 2.5. ниже методом минимального элемента:

Таблица 2.5.

Данные примера 2

Пункты отправления	Пункты назначения					Запасы
	2	3	1	2	150
	3	4	5	1	100
	3	6	3	4	100
Потребности	140	100	70	40	0

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

(2.3)

. Модель транспортной задачи является закрытой. Следовательно, задача разрешима.

Минимальный тариф равный 1 находится в клетке . Поэтому заполняем эту клетку.

Следовательно в клетку помещаем число . Потребности пункта полностью удовлетворены. Поэтому исключаем из рассмотрения столбец и будем считать запасы пункта равными 150-70=80. Промежуточные результаты приведены в табл. 2.6.

Таблица 2.6.

Промежуточные результаты

Пункты отправления	Пункты назначения					Запасы
	2	3	1 70	2	80 [150]
	3	4	5	1	100 [100]
	3	6	3	4	100 [100]
Потребности	140 [140]	100 [100]	0 [70]	40 [40]	350

Минимальный тариф равный 1 находится в клетке . Поэтому заполняем эту клетку.

Следовательно в клетку помещаем число . Потребности пункта полностью удовлетворены. Поэтому исключаем из рассмотрения столбец и будем считать запасы пункта равными 100-40=60. Промежуточные результаты приведены в табл. 2.7.
Таблица 2.7.

Промежуточные результаты

Пункты отправления	Пункты назначения					Запасы
	2	3	1 70	2	80 [150]
	3	4	5	1 40	60 [100]
	3	6	3	4	100 [100]
Потребности	140 [140]	100 [100]	0 [70]	0 [40]	350

Таким образом, продолжая процедуру в -ом шаге получим в табл. 2.8.:

Таблица 2.8.

Результат расчетов

Пункты отправления	Пункты назначения					Запасы
	2 80	3	1 70	2	0 [150]
	3 60	4	5	1 40	0 [100]
	3	6 100	3	4	0 [100]
Потребности	0 [140]	0 [100]	0 [70]	0 [40]	350

Запишем полученный опорный план:



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