Метод двойного предпочтения

1) Метод минимального элемента

Суть метода – из всех тарифов перевозок с_ij выбирают минимальный и в эту клетку помещают наименьшее значение А_i или В_j. Затем из рассмотрения исключают строку (столбец), где запасы (потребности) израсходованы, или строку (столбец) если запасы поставщика удовлетворили потребности потребителя. Из оставшейся части таблицы снова выбирают клетку с минимальным с_ij и процесс распределения запасов продолжается до тех пор, пока все запасы не будут распределены, а все потребности не будут удовлетворены.

Например:

Таблица 4 – Пример распределения методом

минимального элемента

2) Аппроксимация Фогеля.

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

3) Способ двойного предпочтения.

Применяется при больших таблицах, когда перебор всех элементов затруднен.

Суть метода – в каждом столбце помечают знаком V клетку с наименьшим тарифом. Затем тоже самое проделывают с каждой строкой. В результате некоторые клетки оказываются помеченными дважды VV.

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

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

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

Как видно из всего сказанного, каждый план имеет свои преимущества и недостатки, которые учитываются при каждом конкретном случае выбора.

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

Литература: 2, 35-39 с.

Контрольные вопросы:

1. Какие методы оптимизации опорных планов вы узнали?

2. Какой из них предпочтительнее на Ваш взгляд?

3. Какой самый сложный?