Алгоритм построения решения.

1) Проверить выполнение условия закрытости задачи:

2) Построить исходное опорное решение задачи методом минимального тарифа (или методом северо-западного угла).

а) Согласно методу минимального тарифа, грузы распределяются в первую очередь в те клетки, в которых находятся минимальный тариф .

Клетка называется занятой, если . Клетки с (пустые)– незанятые.

б) Количество занятых клеток должно быть равно рангу матрицы ограничений задачи

. (5)

.

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

в) Применить метод вычеркивания, чтобы проверить, что построенное решение – опорное.

Метод вычеркивания: последовательно вычеркиваем строки (столбцы), содержащие только одну занятую клетку. Если в результате все строки и столбцы будут вычеркнуты, то соответствующее решение – опорное.

Проверяем:

,

,

,

Исходное решение – опорное.

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

г) Рассчитать стоимость перевозки:

3) Построить систему потенциалов в занятых клетках.

Потенциалы и находят из равенства для занятых клеток:

, (6)

считая, например,

. (7)

							-2

							-2

4) Проверить построенное решение на оптимальность.

Построенное опорное решение является оптимальным, если для незанятых клеток

, (8)

Результаты вычислений записываем в правом нижнем углу незанятых клеток.

			-2
							-2
	-4
			-2

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

-клетка максимальной неоптимальности.

5) Строим цикл.

а) Начинаем цикл с клетки с наибольшим положительным значением , помечаем ее знаком «+» в левом верхнем углу.

					+
			-2
							-2
	-4
			-2

б) Строим цикл с вершинами в занятых клетках (за исключением клетки с максимальным ), и звеньями, лежащими вдоль строк и столбцов, при этом:

– число вершин четное;

– в каждой строке (столбце) имеются две вершины.

Получается замкнутый многоугольник.

Замечание. Метод вычеркивания требовался для проверки возможности образования циклов в таблице.

в) Чередуем знаки «-» и «+» у вершин цикла.

	-				+
			-2
							-2
	-4
	+				-
50			-2

6) Перейти к новому опорному решению.

а) У вершин построенного многоугольника со знаком «-» выбрать минимальный груз . В примере .

б) Перераспределить груз:

– прибавить к грузам, стоящим у вершим со знаком «+»,

– отнять от грузов, стоящих у вершин со знаком

«-».

-				+
90-60			-2	+60
	-4
+				-
50+60			-2	60-60

В результате перераспределения получаем новое опорное решение.

Повторяем алгоритм.

Проверяем условие (5):

.

Рассчитаем стоимость перевозки:

Построим систему потенциалов в занятых клетках.

		-2

Проверим построенное решение на оптимальность.

Запишем в левом нижнем углу незанятых клеток результаты вычислений .

			-7
			-7		-5
		-2

-клетка максимальной неоптимальности. Решение не оптимально.

Строим цикл.

	-	2			+	2
			-7
	+				-
	1
			-7		-5
		-2

Переходим к новому опорному решению.

. Перераспределяем груз.

-	2			+	2
30-30			-7	60+30
+				-
+30	1			100-30

Получаем новое опорное решение.

Повторяем алгоритм.

Проверяем условие (5):

.

Рассчитаем стоимость перевозки:

Построим систему потенциалов в занятых клетках и запишем в левом нижнем углу незанятых клеток результаты вычислений .

	-1		-7
			-6		-4
		-2

Построенное опорное решение является оптимальным, так как для всех незанятых клеток

.

Ответ: , .