Распределительный метод решения транспортной задачи

Определение. Циклом пересчета в транспортной задаче называется замкнутый многоугольник, одна из вершин которого совпадает со свободной клеткой, для которой образуется цикл, а остальные – заполненными. Вершины соединяются замкнутой ломаной линией, отрезки которой образуют угол 90°. Любой цикл имеет четное число вершин, каждую из которых отмечают знаком. Свободной клетке, для которой выбран цикл, приписывается знак +, остальные знаки чередуются.

На рисунке 6 дан пример цикла, в вершинах его указаны номера строк и столбцов клеток, в которых лежат эти вершины.

Рис. 6. Цикл транспортной задачи для клетки (1.5)

Свободной клетке, с которой начинается цикл, т.е. клетке (1.5), присваивают знак +, затем знаки чередуются.

Определение. Алгебраической суммой стоимостей (АСС) свободной клетки называется сумма тарифов перевозок, находящихся в клетках вершин цикла пересчета, взятых с соответствующими знаками в вершинах цикла.

Подсчитаем алгебраическую сумму стоимостейАСС свободной клетки (А₁,В₅) транспортной задачи, заданной таблицей 2.7.

.

Теорема. Если все алгебраические суммы стоимостейсвободных клеток данного базисного решения транспортной задачи неотрицательны, то базисное решение оптимально.

Для того, чтобы улучшить план, применим симплексный метод. Для этого преобразуем свободное неизвестное с наибольшей по величине отрицательной АСС в базисную переменную, то есть в заполненную клетку.

Преобразование достигается с помощью сдвига по циклу пересчета:

1. Находим минимальное из чисел, лежащих в отрицательных вершинах цикла. Обозначим это число D.

2. К числам в положительных вершинах прибавляют D, из чисел в отрицательных вершинах вычитают D.

3. Значения неизвестных клеток старой таблицы (матрицы перевозок), в которых не находились вершины цикла пересчета, переписываются в новую таблицу без изменения. Матрица тарифов остается постоянной.

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