Нахождение предварительного плана перевозок

Существует много методов построения предварительного плана перевозок: диагональный, северо-западного угла, наименьшей стоимости и др.

Однако количество приближений к оптимальному плану будет значительно меньше, если для принятия предварительного плана воспользоваться методом двойного предпочтения.

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

C_kj = , (1.29)

и отметим ее.

Далее проведем такой же выбор по столбцам (строкам):

C_ik = . (1.30)

В результате все клетки матрицы стоимости разделяются на три категории: клетки с двумя отметками, с одной отметкой и без отметок.

После этого составим предварительный (опорный) план перевозок, пользуясь следующим правилом:

Основной поток перевозок направляется по маршрутам, определяемым клетками матрицы с двумя отметками; затем используются маршруты, определяемые клетками с одной отметкой.

Если с помощью этих маршрутов не удается выполнить условия (1.26), (1.27), то назначаются маршруты, определяемые клетками матрицы без отметок. Клетки матрицы, в которых есть назначения r, будем называть занятыми (загруженными). Заметим, что число занятых клеток, т.е. назначений, должно быть r=m+n-1.

Рассмотрим это высказывание. Действительно, число уравнений в условиях (1.25), (1.26) равно m+n. Выразим каждую строку условия (1.25), кроме первой, относительно неизвестного x_i ₁, стоящего в первом столбце матрицы перевозок:

x_i ₁= a_i- x_i ₂ - … -x_in, i = 2, m. (1.31)

Аналогично каждый столбец, кроме первого из (1.26), разрешим относительно неизвестного x ₁ _j, стоящего в первой строке матрицы перевозок: x ₁ _j = b_j - x ₂ _j - … -x_mj, j = 2, n. (1.32)