Занятие Методы решения транспортной задачи
 Скачать 407.42 Kb.
|
Пример 2. Найти оптимальный план поставок, используя первоначальный план поставок (таблица 1) и матрицу оценок этого плана  0 5 −1 −40 0 0 1 4 0 −2 . 0 Решение. Поскольку матрица оценок первоначального плана поставок содержит отрицательные числа, то этот план является неоптимальным. Проведём его оптимизацию распределительным методом. Шаг 1. Необходимо выбрать клетку с наименьшей оценкой. В представленной матрице такой клеткой является клетка (1,4). Ее оценка равна минус четыре. Шаг 2. Необходимо построить первый цикл пересчета. Для этого надо, начиная с клетки (1,4), двигаться только по отмеченным клеткам и вернуться в клетку (1,4). При этом запрещается делать два последовательных шага в одной строке или в одном столбце. Например, используем такой цикл пересчета: (1,4)(3,4)(3,3)(2,3)(2,1)(1,1)(1,4). Стартовой клетке цикла присваивается знак «+». Двигаясь по циклу знаки клеток чередуются. На рис. 1 представлен цикл пересчета. Для каждой клетки указаны индекс, объем поставок и присвоенный знак.  Рис. 1. Цикл пересчета на первой итерации Среди клеток, отмеченных знаком «» (клетки (3,4); (2,3); (1,1)), выберем минимальную величину поставки: min (130, 30, 30) = 30. Далее во всех клетках со знаком «» уменьшим поставки на этот минимум, а в клетках со знаком «+» увеличим на этот минимум. Клетка (1,4) становится отмеченной. Если после такого пересчета получается одна клетка с нулевой поставкой, то она становится пустой. В нашем случае таких клеток две (1,1) и (2,3). Клетку с наибольшим тарифом переводим в разряд пустых это клетка (1,1). В клетке (2,3) останется нулевой объем поставки, но она останется отмеченной. Напомним, что должно соблюдаться правило: число отмеченных клеток равняется сумме чисел строк и столбцов минус единица. Получен новый план поставок (таблица 3). Необходимо всегда осуществлять проверку нового плана поставок: сумма поставок по строкам должна равняться спросу потребителя, а по столбцам мощностям поставщиков.  Таблица 3
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||