Транспортная задача с ограничениями на пропускную способность
Сетевая модель
Задача коммивояжера
Задача о назначениях
Метод Гомори
Симплекс-метод
Распределительный метод
Метод потенциалов
Метод Фогеля
Открытые и закрытые задачи
Новое на сайте
Задачи параметрического программирования
Критерий Манна-Уитни
Интервалы возрастания и убывания функции
Коэффициент контингенции
Коэффициент конкордации
Смешанное произведение векторов
Метод Фибоначчи

Решение транспортной задачи

Инструкция. Для получения решения транспортной задачи в онлайн режиме выберите размерность матрицы тарифов (количество поставщиков и количество магазинов). В новом окне выберите метод поиска опорного плана:
  • метод северо-западного угла;
  • метод минимальной стоимости;
  • метод Фогеля;
  • метод двойного предпочтения.
Полученное решение сохраняется в файле Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в Excel.
Количество столбцов (магазины)
Количество строк (поставщики)
Предложить свой начальный план
Пример. Матрица тарифов (здесь количество поставщиков равно 4, количество магазинов равно 6):
1 2 3 4 5 6 Запасы
1 3 20 8 13 4 100 80
2 4 4 18 14 3 0 60
3 10 4 18 8 6 0 30
4 7 19 17 10 1 100 60
Потребности 10 30 40 50 70 30
Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60, потребности 30. Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).
3 20 8 13 4 x 80
4 4 18 14 3060 - 30 = 30
10 4 18 8 6 x 30
7 19 17 0 1 x 60
10 30 40 50 70 30 - 30 = 0 0

Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.
3 20 8 x 4 x 80
4 4 18 x 3 0 30
10 4 18 x 6 x 30
7 19 17 0 1 x 60 - 50 = 10
10 30 40 50 - 50 = 0 70 0 0

Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.
Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).
3 x 8 x 4 x 40 - 40 = 0
x x x x 3 0 0
x 4 x x x x 0
x x x 0 1 x 0
0 0 40 - 40 = 0 0 0 0 0

1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13 4[30] 100 80
2 4 4 18 14 3[30] 0[30] 60
3 10 4[30] 18 8 6 0 30
4 7 19 17 0[50] 1[10] 100 60
Потребности 10 30 40 50 70 30

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.
1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[30] 4 100 80
2 4 4[20] 18 14 3[10] 0[30] 60
3 10 4[10] 18 8[20] 6 0 30
4 7 19 17 0 1[60] 100 60
Потребности 10 30 40 50 70 30

В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n - 1 = 6 + 4 - 1 = 9, т.е. опорный план является невырожденным.
Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов или распределительный метод. На этом этапе правильность решения можно контролировать через функцию стоимости F(x). Если она уменьшается (при условии минимизации затрат), то ход решения верный.
Все права защищены и охраняются законом. Copyright © ООО Новый семестр 2006-2013 Линейное программирование онлайн