Оптимизация плана.
Проверка допустимого плана на оптимальность заключается в соблюдении условий 8 и 9. Если данные условия не соблюдаются для клеток Xij 0, то значение потенциала отрицательно, что и определяет потенциальную клетку. Следует скорректировать допустимый план. Корректировка плана состоит в перемещении в потенциальную клетку с наименьшим по модулю потенциалом какую-нибудь загрузку.
Перемещение производится при условии сохранения количества и - по строке и столбцу. Производя перемещение, следует повторить процесс определения потенциала до тех пор, пока условия 8 и 9 не будут соблюдены. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний. Из наличия потенциальных клеток можно сделать вывод, что составленный план не является оптимальным.
Выявленные клетки являются резервом улучшения плана, а превышение суммы индексов над расстоянием потенциалом в таблице 7 они размещены в нижнем правом углу клетки и выделены другим цветом. Улучшение неоптимального плана сводится к перемещению загрузки в потенциальную клетку матрицы. Цепочку возможных перемещений определяют для потенциальной клетки с наибольшим значением потенциала строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна из е вершин находилась в данной клетке, а все остальные вершины в занятых клетках.
Знаком отмечают в цепочке е нечтные вершины, считая вершину в клетке с наибольшим потенциалом, а знаком - чтные вершины. Наименьшая загрузка в вершинах 18 ездок, уменьшая загрузку в вершинах со знаком - и увеличивая е в вершинах со знаком получают улучшенный план. Дальнейшие расчты по его оптимизации производятся аналогично. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.
В результате всех вычислений имеем конечный оптимальный план возврата порожняка в таблице 8. ТАБЛИЦА 8. Оптимальный план возврата порожняка. Пункт назначения образов. порожнякаПункт назначенияВспом. Индек. Б1Б2Б3Б4Б5Б6Б7Б8Потребность в перевозкахUi Vi5-1763-363А106651127842141578А20051386 31718318А35121841413114121018А4816078151 513125151220А5-2 911363011640136А6-3315123810123224Наличи е порожняка66 18201230121818194194 После составления оптимального плана возврата порожняка произведм проверку клеток на потенциальность.
Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов. А1Б2 u1 v2 0-1 -1 l1-21 А2Б2 u2 v2 0-1 -1 l2-213 А1Б4 u1 v4 06 6 l1-48 А2Б7 u2 v7 06 6 l2-77 . А3Б8 u3 v8 53 8 l3-810 А4Б8 u4 v8 83 11 l4-812 . А6Б1 u6 v1 -35 2 l6-82 А6Б8 u6 v8 -33 0 l6-82. п.4.3.