Метод северо-западного угла

Рассмотрим «северо-западный угол» незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая:

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

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

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

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

Пример построения опорного плана методом северо-западного угла

Найти опорный план транспортной задачи:

	1	2	3
1	15	20		35	20	0	0
2		0	30	30	30	30
	15	20	30	=
	0	20	30
	0	0	30
	0	0	0

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

Метод минимальной стоимости

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

Пример построения опорного плана методом минимальной стоимости

Опорный план, построенный по методу минимальной стоимости.

	1	2	3
1	⁹	5⁷	30¹	35	5	5	5
2	15²	15³	⁸	30	30	15	0
	15	20	30	=
	15	20	0
	0	20	0
	0	5	0

Метод потенциалов

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке цикла совершает поворот на . Знаком «+» отмечают те вершины, в которых перевозки увеличиваются, а знаком «-» - те вершины цикла, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым, а стоимость плана может меняться.

Ценой цикла называется изменение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком «+», а в отрицательных со знаком «-».

Идея метода потенциалов состоит в следующем [1,3]. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные – в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить больше единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план найден.

Для нахождения циклов с отрицательной ценой вводится система платежей и определяются величины , называемые «псевдостоимостями» перевозок единицы груза из пункта i в пункт j. При этом цена цикла пересчета для каждой свободной клетки равна , если платежи , определять из условия

для всех базисных клеток (i,j).