Cтраница 2
Рассмотрим транспортную задачу, в которой в качестве поставщиков выступают только пункты 5i, i е G, а в качестве потребителей - пункты ф, j е Я. Тогда, пользуясь методом северо-западного угла, можно построить опорный план такой задачи, содержащий не более s t - 1 положительных компонент. Аналогично, рассматривая транспортную задачу для второй группы поставщиков и потребителей, построим опорный план, включающей не более ( т - s) ( п - t) - 1 перевозок. Совокупность всех введенных перевозок образует опорный план исходной транспортной задачи (6.1), содержащий не более ( т - s) ( n - t) - i s t - 1 перевозок. [16]
Для определения опорного плана существует несколько методов. Три из них - метод северо-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассматриваются ниже. [17]
Заметим, что число итераций для получения решения транспортной задачи существенно зависит от начального решения. Так как при использовании метода северо-западного угла внимание на стоимости не обращается, то и сам начальный план в общем случае будет далек от оптимального. [18]
При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. [19]
Доказано, что оптимальные планы являются ациклическими, поэтому и первоначальный план также должен удовлетворять этому требованию. Заметим, что планы, полученные с помощью методов северо-западного угла и наименьшей стоимости, ациклические. Однако если план оказался вырожденным, то при его пополнении требование ацикличности необходимо учитывать. [20]
Как и при решении задачи линейного программирования симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Этот план, как уже отмечалось выше, находят методом северо-западного угла, методом минимального элемента или методом аппроксимации Фогеля. Сущность этих методов состоит в том, что опорный план находят последовательно за п - - т - 1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. [21]
Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок, а именно: на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу ( если таких клеток несколько, то следует выбрать любую из них), и рассмотреть пункты назначения и отправления, соответствующие выбранной клетке. Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом. Следует отметить, что этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем общая стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла. [22]