В настоящее время разработано несколько методов (алгоритмов) решения транспортной задачи линейного программирования. Одна группа этих методов основана на принципе последовательного улучшения плана, когда выбранный определенным образом первоначальный план при помощи специальных процедур улучшается до тех пор, пока не станет оптимальным.
Алгоритм заключается в том, что сначала, строится какой-либо первоначальный допустимый план (рис.1.1), затем проверяется, является ли план оптимальным, если план оптимальный — задача решена, если не оптимальный— отыскивается другой, но обязательно улучшенный и вновь проверяется на оптимальность. Шаги (этапы) 2 и 3 повторяются до тех пор, пока очередной улучшенный план не будет оптимальным.
|
Среди группы методов последовательного улучшения плана можно выделить распределительный метод линейного программирования. Сущность этого метода заключается в том, что на основании известных линейных зависимостей между отдельными факторами составляются матрицы и в результате применения специальных правил подбираются определенные сочетания факторов для получения оптимального решения.
1.3. Методы построения начального плана
Существует несколько методов построения начального плана, который иногда называют опорным решением. Наиболее распространенные из них: метод северо-западного угла, метод наименьшей стоимости, двойного предпочтения, по приоритету ближайших пунктов, способ Фогеля, способ Лебедева— Тихомирова и др. Рассмотрим простейшие из них.
Метод северо-западного угла, или диагональный, появился одним из первых. Название он получил потому, что распределение поставок (корреспонденций) начинается слева сверху (с северо-западного угла матрицы). Это формальный способ, приводящий к решению обычно далекому от оптимального, но зато простой и легко реализуемый на ЭВМ.
|
Решение удобно выполнять в табличной форме. Для этого составляется рабочая таблица в которой в строке слева указываются поставщики (А1, А2,..., Аm) и их мощности, в верхней строке указываются потребители (В1, В2,..., Вn) и их спрос. В клетках таблицы в верхних левых углах указываются единичные стоимости (С11С12 …….. Сmn), т. е. затраты на доставку единицы продукции от соответствующего поставщика Аi(i=1, 2,.... m) соответствующему потребителю Bj (j=1,2,..:,n).
Рассмотрим конкретный пример решения задачи. Три лесозаготовительных предприятия (А1, A2, А3) заготовляют пиловочник в объемах соответственно 300, 600 и 500 тыс. м3 в год и поставляют четырем деревообрабатывающим предприятиям (В1, В2, В3, В4). Годовой объем потребления пиловочника деревообрабатывающими предприятиями равен 450, 400, 200 и 350 тыс. м3. Стоимость доставки сырья от ЛЗП к деревообрабатывающим предприятиям представлена матрицей стоимостей, показанной в табл.1.1. цифрами Сij в левых верхних углах клеток рабочей таблицы.
Согласно методу северо-западного угла распределение поставок от поставщиков к потребителям начинается с клетки А1B1 Сравниваем мощность первого поставщика А1 (300) с потребностью потребителя B1 (450). Меньшую величину (300) помещаем в клетку А1B1 и вычитаем ее из обеих сравниваемых величин. В итоге в остатке первой строки проставляется 0, а в итоге первого столбца остаток 450—300=150 (табл.1.2.). Первую строку из дальнейшего рассмотрения исключаем. Поскольку остаток оказался в первом столбце, следующую поставку назначаем в соседнюю клетку А2B1. Сравнивая итоги второй строки (600) и первого столбца (остаток 150), устанавливаем величину поставки, равную 150. Вычтя эту поставку из сравниваемых величин, в итоге первого столбца проставляем 0, а в итоге второй строки записываем разницу 600—150 = 450. На третьей итерации, сравнивая потребность потребителя второго столбца B2=400 и остаток мощности второго поставщика А2 = 450, меньшее значение записываем в клетку А2B2. В остатке второго столбца остается 400—400 = 0, а второй строки 450—400 = 50, что и записываем в остаток по строке в результате третьей итерации. Продолжая этот процесс, распределяем поставки по всей таблице. Итог распределения поставок приведен в табл.1.2
|
Построение опорного плана методом северо-западного угла.
В итоге получили некоторое возможное решение. Проверка сумм ∑Xij по строкам и столбцам показывает на допустимость такого плана распределения поставок и отсутствие арифметических ошибок.
Вычислим значение целевой функции. Для этого перемножим удельные стоимости доставки на соответствующие объемы и найдем сумму
Рассмотрим еще один способ составления начального плана - способ минимального элемента.
Способ минимального элемента несколько сложнее, но позволяет отыскать начальное решение очень близкое к оптимальному, а иногда и оптимальное.
Сущность его заключается в следующем.
В матрице стоимостей отыскивается клетка с минимальным значением Cij и в эту клетку записывается поставка Xij =min (ai bj). Если матрица содержит несколько одинаковых минимальных значений Cij, то выбирают любое одно.
|
После этого вычеркивается строка или столбец. Если ai>bj, вычеркивают столбец, при ai <bj вычеркивают строку.
Далее процесс (итерации, шаги) повторяют до тех пор, пока не будут распределены все поставки.
Если матрица большая и в уме не удержать нераспределенные мощности и спрос на шагах в процессе распределения на части значений ai и bj, в конце каждого шага остаточные величины записывают в рабочую таблицу.
Распределение поставок по методу минимального элемента выполняется в следующей последовательности.
Шаг 1. Находим минимальное значение стоимости Cij. В нашем случае это будет C21 = 4. В эту клетку таблицы записываем возможную поставку, т. е. минимальную из А2 и В1, Сравнивая А2 = 600 и В1 = 450, записываем в клетку Х21 поставку 450. Вычисляем нераспределенные мощности поставщиков и неудовлетворенный спрос потребителей (табл.1.3).
Потребитель В1 — удовлетворен полностью, во вспомогательной части таблицы проставляем 0, а столбец в дальнейших расчетах не рассматриваем.
Потребитель В2 неудовлетворен, его спрос остался равным 400, что и записываем во вспомогательной части таблицы.
Потребитель В3 — неудовлетворен, спрос остался — 200.
Потребитель В4 — неудовлетворен, спрос —350.
Поставщик А1 — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.
Поставщик А2 — часть мощности распределена потребителю В1 но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.
Поставщик А3 — мощность его не распределена и записываем результат нераспределенной мощности 500.
Сумма нераспределенных мощностей и неудовлетворенного спроса по результатам первой итерации (шага) равна 950, что и записываем в итоге и это является проверкой того, что нет арифметических ошибок. Аналогично заполняется рабочая таблица по шагам.
Шаг 2. Находим минимальное значение стоимости Cij без вычеркнутого столбца В1 это значение С33 =5. Записываем в эту клетку (табл. 1.4.) возможную поставку-минимум из А3 = 500 и В3=200, min=200, записываем нераспределенные мощности и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.
Шаг 3. Минимальный элемент А2В2 = 7. В эту клетку записываем минимальное значение из нераспределенной мощности А2=150 и спроса В2=400, min=150. В результате третьего шага мощность поставщика А2 исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спроса осталась равной 600. Продолжая аналогично, доводим распределение до конца.
Шаг 4. Минимальное Cij из оставшихся имеют клетки А1В2 и А3В2 — выбираем А3В2. Записываем сюда поставку 250 как минимум из значений остатка потребителя В2 и поставщика А3 и так далее.
Результат распределения по методу минимального элемента показан в табл.1.5.
Вычисляем значение целевой функции полученного начального решения:
R= 10* 300 + 4 *450 + 7 *150 + 8 *250 + 5*200+ 12*50 = 9450 тыс. руб.
Видим, что это решение целесообразнее, чем полученное методом северо-западного угла. Но это не значит, что полученное решение оптимальное.
Таблица1.5.
25.Алгоритм распределительный метод решения транспортной задачи.
Распределительный метод использует исходное базисное решение, полученное методом северо-западного угла или наименьшей стоимости, и заключается в преобразовании матрицы перевозок таким образом, что каждый последующий пересчет таблицы приближается к оптимальному решению.
Для преобразования таблицы используется понятие цикла.
Циклом в матрице называется ломаная с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющая требованиям:
– замкнутости;
– в каждой вершине должно встречаться два звена.
Если в любом цикле вершинам приписать при обходе в одном направлении поочередно знаки «+» и «–», то в каждой строке (столбце) число положительных вершин будет равно числу отрицательных.
При решении задач используется операция сдвига по циклу. Эта операция заключается в увеличении элементов в положительных вершинах и уменьшении в отрицательных на одно и то же число.
Например, для свободной клетки с координатами (3,3) левой матрицы строится цикл, приведенный на рисунке, и осуществляется сдвиг по циклу на величину 8. В результате получаются новые значения перевозок, приведенные на правой матрице. Клетки, не являющиеся вершинами цикла, при этом остаются без изменений.
Для оптимизации решения важно знать, с каким коэффициентом выбранная свободная неизвестная входит в выражение для базисных неизвестных. Это определяется следующим правилом:
– коэффициент равен 0, если соответствующая базисная клетка не является вершиной цикла пересчета данной свободной клетки;
– коэффициент равен 1, если базисная клетка является положительной вершиной цикла пересчета данной свободной клетки;
– коэффициент равен –1, если базисная клетка является отрицательной вершиной пересчета данной свободной клетки.
Например, матрица перевозок имеет 4 пункта отправления и 4 пункта назначения. В ней записано некоторое базисное решение в заштрихованных клетках x11, x12, x23, x24, x32, x41 и x43, число которых должно быть r=m+n-1=7. При этом в каждой строке и каждом столбце таблицы должна быть как минимум одна базисная клетка.
В1 | В2 | В3 | В4 | |
А1 | – | · + | ||
А2 | + | – | ||
А3 | ||||
А4 | + | – |
Построим цикл пересчета для свободной клетки x14 так, чтобы все остальные вершины лежали в базисных клетках. Такой цикл существует только один и приведен в таблице, при этом свободной клетке x14 присваивается знак «+», а знаки всех последующих вершин чередуются при их обходе по циклу в одном направлении.
Таким образом, можно по теореме утверждать, что клетка x14 входит в выражение для неизвестных базисных со знаками:
.
Аналогично можно найти коэффициенты для других свободных неизвестных.
У распределительного метода существуют промежуточные базисные решения, каждое из которых постепенно приближается к оптимальному.
Найденное любым методом допустимое базисное решение вносится в матрицу перевозок и занимает r=m+n-1 клеток. Вносятся и нулевые базисные решения. Далее меняются местами базисные и свободные переменные для приближения к оптимальному решению.
Во-первых, определяется свободная неизвестная, переводимая в число базисных.
Рассмотрим способ определения свободных неизвестных, которые целесообразно перевести в число базисных на конкретном примере. Возьмем базисное решение, найденное методом северо-западного угла со стоимостью перевозок
=2×20 + 3×10 + 2×20 + 5×20 + 2×10 + 6×10 = 290.
Теперь необходимо построить циклы пересчета для всех свободных переменных (свободных клеток) и определить сумму стоимостей по циклам пересчета gij для всех свободных неизвестных, чтобы найти, какую из них перевести в число базисных для уменьшения целевой функции.
Определяем сумму стоимостей по циклу пересчета для каждой свободной клетки, подставляя соответствующие стоимости перевозок из базисных клеток в вершинах цикла:
х13 ® g13 = с13 - с23 + с22 - с12 = 2 - 5 + 2 - 3 = -4,
х14 ® g14 = с14 - с24 +с33 – с23 + с22 - с12 = 4 – 6 + 2 - 5 + 2 - 3 = -6,
х21 ® g21 = с21 - с11 + с12 - с22 = 3 - 2+ 3 - 2 = 2,
аналогично g24 = - 8, g31 = 6, g32 = 4.
Выбираем те из свободных переменных, которые имеют отрицательное значение суммы стоимости по циклу пересчета. В рассматриваемом примере это х13, х14, х24.
Во-вторых, определяется базисная переменная, переводимая в число свободных.
Для этого необходимо проанализировать цикл пересчета, соответствующий выбранной свободной неизвестной. В нашем примере это может быть цикл для переменной х13.
Производя преобразования по циклу, мы должны получить нуль в одной из базисных переменных. Кроме того, необходимо учитывать, что переменные не могут принимать отрицательных значений. Поэтому выбирается та базисная переменная, которая имеет наименьшее значение из всех базисных переменных, расположенных в отрицательных вершинах цикла пересчета. В нашем примере это будет х12=10.
Для получения нового допустимого базисного решения осуществляем сдвиг по циклу пересчета выбранной свободной переменной х13 на величину значений выбранной базисной переменной х12=10, которая после сдвига переводится в свободные.
При этом получим новую таблицу матрицы перевозок.
Сдвиг по циклу привел к новому допустимому базисному решению:
х11=20, х13=10, х22=30, х23=10, х33=10, х34=10, остальные xij=0.
Новое решение дает значение целевой функции F=250, меньшее предыдущего, т. е. ближе к оптимальному значению.
Если в отрицательных вершинах с минимальными перевозками окажется две базисных клетки с одинаковыми значениями, то после сдвига по циклу в число свободных переводится только одна из них, а вторая остается в числе базисных с нулевыми перевозками. И в дальнейших расчетах эта клетка фигурирует как базисная со всеми их характеристиками.
Для нового базисного решения также подсчитываются суммы стоимостей по циклам пересчета для каждой свободной неизвестной: g12=4, g14=2, g12=4, g21= - 2,g24= - 8, g31= 2, g23= 4.
Выбираются новые свободная и базисная переменные для сдвига по новым циклам, и все повторяется. Операция продолжается до тех пор, пока не получится, что все стоимости по циклам пересчета больше нуля (gij > 0), что является признаком оптимальности решения, полученного распределительным методом.
Для рассматриваемого примера оптимальным решением является следующее:
х11=20, х13=10, х22=30, х24=10, х33=10, х12=0, остальные xij=0. Стоимость оптимальной перевозки F=170, и уменьшить ее дальше невозможно.