Скорректированная таблица с назначениями для нулевых клеток

	I			II			III			IV
A		0			0			7			8
B		0			0			2			0
C		3			1			0			3
D		9			0			2			0

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В — к потребителю II, с базы С—к потребителю III и с базы D — к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. Тем не менее в любом оптимальном решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных распределения назначений представлены ниже.

Таблица 2.36 Первое альтернативное оптимальное решение

Таблица 2.37 Второе альтернативное оптимальное решение

	I			II			III			IV					I			II			III			IV
A		0			0			7			8			A		0			0			7			8
B		0			0			2			0			B		0			0			2			0
C		3			1			0			3			C		3			1			0			3
D		9			0			2			0			D		9			0			2			0

Минимальную дальность перевозок для каждого из трех решений можно вычислить из исходной таблицы:

Решение 1: 68 + 60 + 35 + 45 = 208 миль;

Решение 2: 68 + 63 + 35 + 42 = 208 миль;

Решение 3: 72 + 56 +35 + 45 = 208 миль.

Общая дальность перевозок для всех трех решений одинакова.

Примечание: в задачах большей размерности, чем задача из примера 2.7, убедиться в том, что проведенное в соответствии с пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":

1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.

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

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

4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.