2015-02-04
483
В соответствии с теоремой 6.1 проверяется условие сбалансированности запасов поставщиков и потребностей потребителей.
Если транспортная задача открытого типа, то
а) если суммарная потребность потребителей превышает суммарные запасы складов-поставщиков, то вводится фиктивный склад-поставщик, запас которого определяется по формуле (6.8).
б) если суммарные запасы складов-поставщиков превышают суммарную потребность потребителей, то вводится фиктивный потребитель, потребность которого определяется по формуле (6.9).
При этом стоимости перевозок для каждой фиктивной пары склад-поставщик – потребитель принимаются, как правило, равными нулю.
2. Разработка исходного опорного плана.
Для отыскания исходного опорного плана используют метод северо-западного угла, метод минимальной стоимости и др.
Метод «северо-западного угла»
Рассматривается незаполненная левая верхняя («северо-западная») клетка таблицы поставок. Данная ячейка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате или будут удовлетворены все потребности, или исчерпаны запасы поставщика. Если удовлетворены потребности, то остальные клетки этой колонки вычеркиваются и в последующих распределениях не участвуют.
|
|
|
Если исчерпаны запасы поставщика, то зачеркиваются остальные клетки соответствующей строки, и они не участвуют в последующих распределениях.
Затем рассматривается очередная незаполненная левая верхняя ячейка, и итерации повторяются.
Не смотря на простоту, данный метод не учитывает стоимость перевозок, и поэтому исходный план может оказаться далеким от оптимального. Данный недостаток позволяет устранить метод минимальной стоимости.
Метод «минимальной стоимости»
В таблице поставок отыскивается клетка с минимальной стоимостью перевозок:
. (6.12)
При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Данная клетка заполняется минимальным значением от возможного объема поставок и объема потребностей. В результате либо будут удовлетворены потребности, либо исчерпаны запасы.
Если удовлетворены потребности, то остальные клетки этой колонки вычеркиваются и в последующих распределениях не участвуют.
Если исчерпаны запасы поставщика, то зачеркиваются остальные клетки соответствующей строки, и они не участвуют в последующих распределениях.
Затем из всех незаполненных клеток находится очередная клетка с минимальной стоимостью, итерации повторяются.
После того, как будет найден опорный план, по нему вычисляют значение целевой функции (6.6).
|
|
|
3. Проверка вырожденности опорного плана.
В соответствии с теоремой 6.2 проверяется вырожденность найденного плана. Если опорный план вырожденный, т.е.
, (6.13)
(где N – число заполненных клеток в таблице поставок) тогда вводится k фиктивных поставок:
, (6.14)
т.е. в любых k незаполненных клетках таблицы поставок вписывают нулевые значения проектным параметрам xij:
, (6.15)
где S – множество пар индексов (i, j) свободных переменных, соответствующих незаполненным клеткам.
