Аппроксимация Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).
Пример
правитьИспользуя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице (опорный план этой задачи ранее был найден методом минимального элемента).
| Пункты отправления | Пункты назначения | Запасы | |||
| 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. В результате получим опорный план:
При этом плане общая стоимость перевозок такова:
Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным.
См. также
правитьЛитература
править- Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9