V1= A1Б1 – U1 = 5-0= 5; V7 = A1Б7 – U1 = 14-0=14; V8 = A1Б8 – U1= 15-0 =15

……………………… ………………………… …………………………

U5= A5Б1 – V1 = 9-5= 4; V3 = A5Б3 – U5 = 13-4= 9; U4= A4Б3 – V3 = 15-9 =6;

После расчёта индексов проверяем незанятые клетки на потенциальность.

п.4.2.3. Определение потенциальных клеток. Незанятые клетки, для которых получилось, что Ui + Vj >lij – называются потенциальными. Проверяем незанятые клетки на потенциальность. Проверка сводится к сравнению расстояний каждой незанятой клетки с суммой соответствующих ей индексов.

А1Б2 = u1 + v2 = 0-3 = -3 < ( l1-2=1);

А1Б3 = u1 + v3 = 0+9 = 9 > ( l­1-3­=7) -- 2 ;

;

А2Б8 = u2 + v8 = 16+15= 31> ( l2-8=3)-- 28 ;

.;

А6Б8 = u6 + v8 = 11+15= 26> ( l6-8=2)-- 24 .

По данным вычислений построим таблицу 7.

4.1.5. Оптимизация плана. Проверка допустимого плана на оптимальность заключается в соблюдении условий: {8} и {9}. Если данные условия не соблюдаются для клеток Xij =0, то значение потенциала отрицательно, что и определяет потенциальную клетку. Следует скорректировать допустимый план. Корректировка плана состоит в перемещении в потенциальную клетку с наименьшим по модулю потенциалом какую-нибудь загрузку. Перемещение производится при условии сохранения количества “+” и “-“ по строке и столбцу. Производя перемещение, следует повторить процесс определения потенциала до тех пор, пока условия {8} и {9} не будут соблюдены. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.

Из наличия потенциальных клеток можно сделать вывод, что составленный план не является оптимальным. Выявленные клетки являются резервом улучшения плана, а превышение суммы индексов над расстоянием – потенциалом (в таблице 7 они размещены в нижнем правом углу клетки и выделены другим цветом). Улучшение неоптимального плана сводится к перемещению загрузки в потенциальную клетку матрицы.

Цепочку возможных перемещений определяют: для потенциальной клетки с наибольшим значением потенциала строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы одна из её вершин находилась в данной клетке, а все остальные вершины в занятых клетках. Знаком “+” отмечают в цепочке её нечётные вершины, считая вершину в клетке с наибольшим потенциалом, а знаком “-“ – чётные вершины. Наименьшая загрузка в вершинах 18 ездок, уменьшая загрузку в вершинах со знаком “-“ и увеличивая её в вершинах со знаком “+” получают улучшенный план. Дальнейшие расчёты по его оптимизации производятся аналогично. Признаком оптимальности является отсутствие клеток, в которых сумма индексов будет больше расстояний.

В результате всех вычислений имеем конечный оптимальный план возврата порожняка в таблице 8.

ТАБЛИЦА 8. Оптимальный план возврата порожняка.