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