Аппроксимация Фогеля: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Нет описания правки
(нет различий)

Версия от 07:39, 3 мая 2011

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

Пример

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

Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1 7 8 1 2 160
A2 4 5 9 8 140
A3 9 2 3 6 170
Потребности 120 50 190 110 470

Решение

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

Пункты отправления Пункты назначения Запасы Разности по строкам
B1 B2 B3 B4
A1 7 8 1 2 160 1 6 - - - -
A2 4 5 9 8 140 1 1 1 1 1 0
A3 9 2 3 6 170 1 1 1 7 - -
Потребности 120 50 190 110 470
Разности по столбцам 3 3 2 4
3 3 2 -
5 3 6 -
5 3 - -
0 0 - -
- 0 - -

Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5-4=1. Точно так же разность между минимальными элементами в столбце В4 равна 6-2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 и будем считать запасы пункта А1 равными 160—110=50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы. Как видно из этой таблицы, наибольшая указанная разность соответствует строке А1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее с столбцом В3. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте А1 полностью исчерпаны, а потребности в пункте В3 стали равными 190-50=140 ед. Исключим из рассмотрения строку А1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки A3 и столбца B3, строки A3 и столбца B2, строки A2 и столбца B1, строки А2 и столбца B2. В результате получим опорный план:

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

S = 1*50 + 2*110 + 4*120 + 5*20 + 2*30 + 3*140 = 1330.

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

См. также

Литература