Определение. Циклом пересчета в транспортной задаче называется замкнутый многоугольник, одна из вершин которого совпадает со свободной клеткой, для которой образуется цикл, а остальные – заполненными. Вершины соединяются замкнутой ломаной линией, отрезки которой образуют угол 90°. Любой цикл имеет четное число вершин, каждую из которых отмечают знаком. Свободной клетке, для которой выбран цикл, приписывается знак +, остальные знаки чередуются.
На рисунке 6 дан пример цикла, в вершинах его указаны номера строк и столбцов клеток, в которых лежат эти вершины.
Рис. 6. Цикл транспортной задачи для клетки (1.5)
Свободной клетке, с которой начинается цикл, т.е. клетке (1.5), присваивают знак +, затем знаки чередуются.
Определение. Алгебраической суммой стоимостей (АСС) свободной клетки называется сумма тарифов перевозок, находящихся в клетках вершин цикла пересчета, взятых с соответствующими знаками в вершинах цикла.
Подсчитаем алгебраическую сумму стоимостейАСС свободной клетки (А1,В5) транспортной задачи, заданной таблицей 2.7.
|
|
.
Теорема. Если все алгебраические суммы стоимостейсвободных клеток данного базисного решения транспортной задачи неотрицательны, то базисное решение оптимально.
Для того, чтобы улучшить план, применим симплексный метод. Для этого преобразуем свободное неизвестное с наибольшей по величине отрицательной АСС в базисную переменную, то есть в заполненную клетку.
Преобразование достигается с помощью сдвига по циклу пересчета:
1. Находим минимальное из чисел, лежащих в отрицательных вершинах цикла. Обозначим это число D.
2. К числам в положительных вершинах прибавляют D, из чисел в отрицательных вершинах вычитают D.
3. Значения неизвестных клеток старой таблицы (матрицы перевозок), в которых не находились вершины цикла пересчета, переписываются в новую таблицу без изменения. Матрица тарифов остается постоянной.
Приведенный метод решения транспортной задачи называется распределительным методом.