16. Нахождение первоначального базисного распределения поставок (метод северо-западного угла).

17. Решение транспортной задачи методом потенциалов.

Идея метода потенциалов, его экономическая интерпретация. Пусть каждый из пунктов производства продукции вносит за перевозку единицы груза (неважно куда) какую-то сумму ; в свою очередь, каждый из пунктов потребления также вносит за перевозку единицы груза (все равно, откуда) сумму ; эти платежи передаются некоторому третьему лицу («перевозчику»).

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

, (3.9)

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

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

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

В [3] доказано, что признаком оптимальности плана является выполнение двух условий.

1. Для всех базисных клеток: . (3.10)

2. Для всех свободных клеток: . (3.11)

План, обладающий такими свойствами, называется потенциальным, а соответствующие ему платежи ( , ) – потенциалами пунктов и .

Процедура построения потенциального (оптимального плана) состоит в следующем.

В качестве первого приближения к оптимальному берется любой опорный план. Для этого плана потенциалы ( , ), соответствующие базисным клеткам, подчиняются условию: сумма потенциалов (псевдостоимость) равна стоимости перевозки единицы груза (3.10). Уравнений всего m+n-1, а число неизвестных равно m+n. Следовательно, потенциал одного пункта можно задать произвольно (например, равным нулю). После этого из m+n-1 уравнений можно найти остальные потенциалы, а по ним вычислить псевдостоимости (3.9) для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей (3.11), то план оптимален. Если нет, то план может быть улучшен переносом перевозок по циклу.

Циклом в транспортной таблице называют несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90^о. В каждой строке и в каждом столбце транспортной таблицы не может быть более чем две клетки (вершины) цикла.

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

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