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

Пусть мы имеем таблицу исходных данных задачи. Исходное решение будем строить по так называемому правилу “северо-западного угла”.

\					…			…
					…			…
					…			…
…	…		…		…	…		…	…
					…			…
…	…		…		…	…		…	…
					…			…

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

Если , то и первый столбец “закрыт”, т.е. потребности первого потребителя удовлетворены полностью. Двигаемся далее по первой строке, записывая в соседнюю клетку (1, 2) меньшее из чисел и , т.е. .

Если же , то аналогично “закрывается” первая строка и далее переходим к заполнению соседней клетки (2, 1), куда заносим . Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпываются ресурсы и потребности .

Задача.

В двух пунктах отправления А и B находится соответственно 150 и 90 т горючего. В пункты 1, 2, 3 требуется доставить соответственно 60, 70 и 110 т горючего. Стоимости перевозки тонны горючего из пункта А в пункты 1, 2, 3 составляют соответственно 6, 10 и 4 ден. ед., а из пункта В – 12, 2 и 8 ден. ед. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Решение.

Запишем исходные данные в таблицу.

1		2		3
	\		60			70			110
А	150				6			10		4
			60			70			20
В	90				12			2		8
									90

Заполнение начнем с ячейки (1, 1): , первый столбец закрыт. Переходим к ячейке (1, 2): , второй столбец закрыт; далее, переходим к клетке (1, 3): . Так как в третьем столбце оказался остаток, равный 90, то переходим к заполнению клетки (2, 3), куда заносим . Поскольку остатки по строке и столбцу равны нулю, опорное исходное решение построено. Этому плану соответствуют затраты в количестве ден. ед.

В правиле “северо-западного угла” не учитывается величина затрат , а поэтому исходное опорное решение часто может быть далеким от оптимального.

Применяют также прием “минимального элемента”, в котором учитывается величина . В этом случае построение исходного опорного решения начинают с клетки с наименьшей величиной , в данном примере – с клетки (2, 2), где . В эту клетку заносим .

1		2			3
	\			60				70				110				Остаток
А	150						6				10			4		60
				60								90
В	90						12				2				8	20
								70				20
Остаток			0			0				20

Остатки по строке и столбцу записываем в соответствующие клетки строки и столбца остатков. Столбец закрыт. Теперь переходим к клетке (1, 3), так как после наименьшим является . В клетку заносим . Затем переходим к клетке (1, 1): . Наконец, переходим к клетке (2, 3), в которую заносим .

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