I. Определение исходного опорного решения.

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

Первоначально выбираются клетки с минимальной стоимостью каждой строке, потом в каждом столбце. Найденные клетки помечаются точками.

В результате все клетки матрицы стоимости будут разделены на 3 категории:

1) клетки с двумя точками (оценками),

2) клетки с одной оценкой,

3) клетки без оценок.

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

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