Разработка исходного опорного плана.
Проверка сбалансированности запасов и потребностей.
В соответствии с теоремой 6.1 проверяется условие сбалансированности запасов поставщиков и потребностей потребителей.
Если транспортная задача открытого типа, то
а) если суммарная потребность потребителей превышает суммарные запасы складов-поставщиков, то вводится фиктивный склад-поставщик, запас которого определяется по формуле (6.8).
б) если суммарные запасы складов-поставщиков превышают суммарную потребность потребителей, то вводится фиктивный потребитель, потребность которого определяется по формуле (6.9).
При этом стоимости перевозок для каждой фиктивной пары склад-поставщик – потребитель принимаются, как правило, равными нулю.
Для отыскания исходного опорного плана используют метод северо-западного угла, метод минимальной стоимости и др.
Метод «северо-западного угла»
Рассматривается незаполненная левая верхняя («северо-западная») клетка таблицы поставок. Данная ячейка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате или будут удовлетворены все потребности, или исчерпаны запасы поставщика. Если удовлетворены потребности, то остальные клетки этой колонки вычеркиваются и в последующих распределениях не участвуют.
Если исчерпаны запасы поставщика, то зачеркиваются остальные клетки соответствующей строки, и они не участвуют в последующих распределениях.
Затем рассматривается очередная незаполненная левая верхняя ячейка, и итерации повторяются.
Не смотря на простоту, данный метод не учитывает стоимость перевозок, и поэтому исходный план может оказаться далеким от оптимального. Данный недостаток позволяет устранить метод минимальной стоимости.
Метод «минимальной стоимости»
В таблице поставок отыскивается клетка с минимальной стоимостью перевозок:
. (6.12)
При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Данная клетка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате либо будут удовлетворены потребности, либо исчерпаны запасы.
Если удовлетворены потребности, то остальные клетки этой колонки вычеркиваются и в последующих распределениях не участвуют.
Если исчерпаны запасы поставщика, то зачеркиваются остальные клетки соответствующей строки, и они не участвуют в последующих распределениях.
Затем из всех незаполненных клеток находится очередная клетка с минимальной стоимостью, итерации повторяются.
После того, как будет найден опорный план, по нему вычисляют значение целевой функции (6.6).