ИНСТРУКЦИЯ. Для получения решения транспортной задачи в онлайн режиме выберите размерность матрицы тарифов (количество поставщиков и количество магазинов). В новом окне выберите метод поиска опорного плана:
| · метод северо-западного угла;
· метод минимальной стоимости;
· метод Фогеля;
· метод двойного предпочтения.
| Полученное решение сохраняется в файле  Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в  Excel.
|
| Количество столбцов (магазины) 2 3 4 5 6 7 8 9 10 Количество строк (поставщики) 2 3 4 5 6 7 8 9 10
| Предложить свой начальный план
|
ПРИМЕР. Матрица тарифов (здесь количество поставщиков равно 4, количество магазинов равно 6):
Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60, потребности 30. Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).
|
|
|
|
|
| x
|
|
|
|
|
|
|
| 0
| 60 - 30 = 30
|
|
|
|
|
|
| x
|
|
|
|
|
|
|
| x
|
|
|
|
|
|
|
| 30 - 30 = 0
|
|
Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.
|
|
|
| x
|
| x
|
|
|
|
|
| x
|
|
|
|
|
|
|
| x
|
| x
|
|
|
|
|
| 0
|
| x
| 60 - 50 = 10
|
|
|
|
| 50 - 50 = 0
|
|
|
|
Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.
Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).
|
| x
|
| x
|
| x
| 40 - 40 = 0
|
| x
| x
| x
| x
|
|
|
|
| x
|
| x
| x
| x
| x
|
|
| x
| x
| x
|
|
| x
|
|
|
|
| 40 - 40 = 0
|
|
|
|
|
| |
|
|
|
|
|
| Запасы
|
|
| 3[10]
|
| 8[40]
|
| 4[30]
|
|
|
|
|
|
|
|
| 3[30]
| 0[30]
|
|
|
|
| 4[30]
|
|
|
|
|
|
|
|
|
|
| 0[50]
| 1[10]
|
|
|
| Потребности
|
|
|
|
|
|
| |
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.
| |
|
|
|
|
|
| Запасы
|
|
| 3[10]
|
| 8[40]
| 13[30]
|
|
|
|
|
|
| 4[20]
|
|
| 3[10]
| 0[30]
|
|
|
|
| 4[10]
|
| 8[20]
|
|
|
|
|
|
|
|
|
| 1[60]
|
|
|
| Потребности
|
|
|
|
|
|
| |
В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n - 1 = 6 + 4 - 1 = 9, т.е. опорный план является невырожденным.
Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов илираспределительный метод. На этом этапе правильность решения можно контролировать через функцию стоимости F(x). Если она уменьшается (при условии минимизации затрат), то ход решения верный.
2015-01-30
772
