транспортная задача метод двойного предпочтения

Ответ от Linus Torvald's[гуру]
ыыы.. . похожа на упрощенный вариант транспортной задачи)
Методы решения
Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей ее можно решить проще (для задач малой размерности) .
Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза, а в маленькие клетки — соответствующие тарифы .
[править] Итерационное улучшение плана перевозок
[править] Нахождение опорного плана
Затем требуется определить опорный план и путем последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла» (нем.) , «наименьшего элемента» , двойного предпочтения и аппроксимацией Фогеля (нем.) .
[править] Метод северо-западного угла (диагональный)
На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность .
[править] Метод наименьшего элемента
Одним из способов решения задачи является метод минимального (наименьшего) элемента Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.
Алгоритм:
Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел.
Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.
[править] Итерации
После нахождения опорного плана перевозок, нужно применить один из алгоритмов его улучшения, приближения к оптимальному.
Метод падающего камня (нем. )
Метод потенциалов (нем.) .
[править] Решение с помощью теории графов
Затем рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока .
К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.
Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.
Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.
Алгоритм mincost maxflow можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма mincost maxflow происходит не более чем за операций. ( — количество рёбер, — количество вершин. ) При случайно подобраных данных обычно требуется гораздо меньше — порядка операций.
При решении несбалансированную транспортной задачи, применяют прием, позволяющий сделать ее сбалансированной. Для этого вводят фиктивные пункты назначения или отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.

Ответ от 3 ответа[гуру]