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

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

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

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

	9	57	301
	152	153	8
				=

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

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

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

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

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

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