Методы определения опорного плана тз.

Метод северо-западного направления (северо-западного угла).

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

Пример. На 3 базы поступил однородный груз в количествах, соответственно равных 140, 180, 160 единиц. Этот груз требуется перевезти в 5 пунктов назначения соответственно в количествах 60, 70, 120, 130 и 100 единиц. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице.

	2	3	4	2	4	140
	8	4	1	4	1	180
	9	7	3	7	2	160
	60	70	120	130	100	480

Найти план перевозок ТЗ методом северо-западного направления.

Решение.

Здесь число пунктов отправления m=3, а число пунктов назначения n=5. Следовательно, опорный план задачи определяется числами, стоящими в 5+3-1=7 заполненных клетках.

Заполнение таблицы начнем с клетки для неизвестного , т.е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта больше, чем потребности пункта , то полагаем , записываем это значение в соответствующей клетке транспортной таблицы и временно исключаем из рассмотрения столбец , считая при этом запасы пункта равными 80.

Рассмотрим первые из оставшихся пунктов отправления и назначения . Запасы пункта больше потребностей пункта . Положим , запишем это значение в соответствующей клетке транспортной таблицы и временно исключим из рассмотрения столбец . В пункте запасы считаем равными 10 ед. Снова рассмотрим первые из оставшихся пунктов отправления и назначения . Потребности пункта больше оставшихся запасов пункта . Положим и исключим из рассмотрения строку . Значение запишем в соответствующую клетку транспортной таблицы и считаем потребности пункта равными 110 ед.

Теперь перейдем к заполнению клетки для неизвестного и т.д. Через 6 шагов остается один пункт отправления с запасом груза 100 ед. и один пункт назначения с потребностью 100 ед.

Соответственно имеется одна свободная клетка, которую и заполняем, полагая . Заносим это значение в клетку транспортной таблицы.

	2 60	3 70	4 10	2	4	140
	8	4	1 110	4 70	1	180
	9	7	3	7 60	2 100	160
	60	70	120	130	100	480

В результате получаем опорный план

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет:

.

Метод минимального тарифа (минимального элемента).

Среди тарифов находится наименьший. Клетка с выбранным тарифом заполняется величиной, равной максимально возможному объёму груза с учетом ограничений по строке и столбцу (если таких клеток несколько, то выбирают любую из них). Из оставшихся тарифов вновь находится наименьший, и процесс продолжается до тех пор, пока не будет распределен весь груз. Этот метод, как правило, позволяет найти опорный план ТЗ, при котором общая стоимость перевозок груза меньше, чем при плане, найденном для данной клетки с помощью метода северо-западного угла. Поэтому наиболее целесообразно опорный план ТЗ находить методом минимального элемента.

Пример 2.

Найти опорный план ТЗ в примере 1 методом минимального элемента.

Решение.

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

	2 60	3	4	2 80	4	140
	8	4	1 120	4	1 60	180
	9	7 70	3	7 50	2 40	160
	60	70	120	130	100	480

В результате получим опорный план

При данном плане перевозок общая стоимость перевозок составляет:

.

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

На каждой операции по всем столбцам и по всем строкам находят разности между двумя записями в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце таблицы условий задач. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой эта разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

В методе Фогеля используются штрафы, взимаемые за неудачный выбор маршрута – это разности между уровнями затрат на перевозку. Как правило, применение метода Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план.

Пример 3.

Найти опорный план ТЗ в примере 1 методом аппроксимации Фогеля.

Решение.

Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке транспортной таблицы. Так, в строке минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3-2=1. Точно так же разность между минимальными элементами в столбце равна 4-2=2. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу . В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки и столбца . Таким образом, эту клетку следует заполнить. Заполнив её, тем самым мы удовлетворим потребности пункта . Поэтому исключим из рассмотрения столбец , и будем считать запасы пункта равными 140-60=80 ед. После этого определим следующую клетку для заполнения. Снова найдём разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и второй дополнительной строке транспортной таблицы. Как видно из этой таблицы, наибольшая указанная разность соответствует столбцам и . Минимальный тариф в этих столбцах записан в клетке, которая находится на пересечении строки и столбца . Следовательно, заполняем эту клетку. Поместив в неё число 120, тем самым предполагаем, что потребности в пункте удовлетворены, а запасы в пункте стали равными 180-120=60 ед. Исключим из рассмотрения столбец и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки и столбца , строки и столбца , строки и столбца , строки и столбца , строки и столбца . В результате получим опорный план

При этом общая стоимость перевозок такова:

.

								Разности по строкам
	2 60	3	4	2 80	4	140		0	1	1	1	-	-
	8	4 60	1 120	4	1	180		0	0	3	0	0	-
	9	7 10	3	7 50	2 100	160		1	1	5	0	0	0
	60	70	120	130	100	480
Разности по столбцам	6	1	2	2	1
	-	1	2	2	1
	-	1	-	2	1
	-	1	-	2	-
	-	3	-	3	-