Проверка сбалансированности запасов и потребностей.

В соответствии с теоремой 6.1 проверяется условие сбалансированности запасов поставщиков и потребностей потребителей.

Если транспортная задача открытого типа, то

а) если суммарная потребность потребителей превышает суммарные запасы складов-поставщиков, то вводится фиктивный склад-поставщик, запас которого определяется по формуле (6.8).

б) если суммарные запасы складов-поставщиков превышают суммарную потребность потребителей, то вводится фиктивный потребитель, потребность которого определяется по формуле (6.9).

При этом стоимости перевозок для каждой фиктивной пары склад-поставщик – потребитель принимаются, как правило, равными нулю.

2. Разработка исходного опорного плана.

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

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

Рассматривается незаполненная левая верхняя («северо-западная») клетка таблицы поставок. Данная ячейка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате или будут удовлетворены все потребности, или исчерпаны запасы поставщика. Если удовлетворены потребности, то остальные клетки этой колонки вычеркиваются и в последующих распределениях не участвуют.

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

Затем рассматривается очередная незаполненная левая верхняя ячейка, и итерации повторяются.

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

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

В таблице поставок отыскивается клетка с минимальной стоимостью перевозок:

. (6.12)

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

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

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

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

После того, как будет найден опорный план, по нему вычисляют значение целевой функции (6.6).

3. Проверка вырожденности опорного плана.

В соответствии с теоремой 6.2 проверяется вырожденность найденного плана. Если опорный план вырожденный, т.е.

, (6.13)

(где N – число заполненных клеток в таблице поставок) тогда вводится k фиктивных поставок:

, (6.14)

т.е. в любых k незаполненных клетках таблицы поставок вписывают нулевые значения проектных параметрам x_ij