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