Алгоритмы нахождения опорного решения транспортной задачи.

В настоящее время разработано несколько методов (алгоритмов) решения транспортной задачи линейного программирования. Одна группа этих методов основана на принципе последовательного улучшения плана, когда выбранный опре­деленным образом первоначальный план при помощи специальных процедур улучшается до тех пор, пока не станет оптимальным.

Алгоритм заключается в том, что сначала, строится какой-либо первоначальный допустимый план (рис.1.1), затем проверяется, является ли план оптимальным, если план оптимальный — задача решена, если не оптималь­ный— отыскивается другой, но обязательно улучшенный и вновь проверяется на оптимальность. Шаги (этапы) 2 и 3 повторяются до тех пор, пока очередной улучшенный план не будет оптимальным.

Среди группы методов последовательного улучшения плана можно выделить распределительный метод линейного программирования. Сущность этого метода заключается в том, что на основании известных линейных зависимостей между отдельными факторами составляются матрицы и в результате применения специальных правил подбираются опре­деленные сочетания факторов для получения оптимального решения.

1.3. Методы построения начального плана

Существует несколько методов построения начального плана, который иногда называют опорным решением. Наибо­лее распространенные из них: метод северо-западного угла, метод наименьшей стоимости, двойного предпочтения, по приоритету ближайших пунктов, способ Фогеля, способ Ле­бедева— Тихомирова и др. Рассмотрим простейшие из них.

Метод северо-западного угла, или диагональный, появил­ся одним из первых. Название он получил потому, что рас­пределение поставок (корреспонденций) начинается слева сверху (с северо-западного угла матрицы). Это формальный способ, приводящий к решению обычно далекому от оптимального, но зато простой и легко реализуемый на ЭВМ.

Решение удобно выполнять в табличной форме. Для это­го составляется рабочая таблица в которой в строке слева указываются поставщики (А₁, А₂,..., Аm) и их мощности, в верхней строке указываются потребители (В₁, В₂,..., В_n) и их спрос. В клетках таблицы в верхних левых углах указы­ваются единичные стоимости (С₁₁С₁₂ …….. С_mn), т. е. затраты на доставку единицы продукции от соответствующего поставщика А_i(i=1, 2,.... m) соответствующему потребителю B_j (j=1,2,..:,n).

Рассмотрим конкретный пример решения задачи. Три лесозаготовительных предприятия (А₁, A₂, А₃) заготовляют пи­ловочник в объемах соответственно 300, 600 и 500 тыс. м³ в год и поставляют четырем деревообрабатывающим пред­приятиям (В_1, В₂, В₃, В₄). Годовой объем потребления пило­вочника деревообрабатывающими предприятиями равен 450, 400, 200 и 350 тыс. м³. Стоимость доставки сырья от ЛЗП к деревообрабатывающим предприятиям представлена матри­цей стоимостей, показанной в табл.1.1. цифрами С_ij в левых верхних углах клеток рабочей таблицы.

Согласно методу северо-западного угла распределение поставок от поставщиков к потребителям начинается с клет­ки А₁B₁ Сравниваем мощность первого поставщика А₁ (300) с потребностью потребителя B₁ (450). Меньшую величину (300) помещаем в клетку А₁B₁ и вычитаем ее из обеих срав­ниваемых величин. В итоге в остатке первой строки простав­ляется 0, а в итоге первого столбца остаток 450—300=150 (табл.1.2.). Первую строку из дальнейшего рассмотрения исключаем. Поскольку остаток оказался в первом столбце, следующую поставку назначаем в соседнюю клетку А₂B₁. Сравнивая итоги второй строки (600) и первого столбца (остаток 150), устанавливаем величину поставки, равную 150. Вычтя эту поставку из сравниваемых величин, в итоге первого столбца проставляем 0, а в итоге второй строки за­писываем разницу 600—150 = 450. На третьей итерации, срав­нивая потребность потребителя второго столбца B₂=400 и остаток мощности второго поставщика А₂ = 450, меньшее зна­чение записываем в клетку А₂B₂. В остатке второго столбца остается 400—400 = 0, а второй строки 450—400 = 50, что и записываем в остаток по строке в результате третьей итера­ции. Продолжая этот процесс, распределяем поставки по всей таблице. Итог распределения поставок приведен в табл.1.2

Построение опорного плана методом северо-западного угла.

В итоге получили некоторое возможное решение. Проверка сумм ∑X_ij по строкам и столбцам показывает на допу­стимость такого плана распределения поставок и отсутствие арифметических ошибок.

Вычислим значение целевой функции. Для этого перемножим удельные стоимости доставки на соответствующие объемы и найдем сумму

Рассмотрим еще один способ составления начального плана - способ минимального элемента.

Способ минимального элемента несколько сложнее, но позволяет отыскать начальное решение очень близкое к оптимальному, а иногда и оптимальное.

Сущность его заключается в следующем.

В матрице стоимостей отыскивается клетка с минималь­ным значением C_ij и в эту клетку записывается поставка X_ij =min (a_i b_j). Если матрица содержит несколько одинако­вых минимальных значений C_ij, то выбирают любое одно.

После этого вычеркивается строка или столбец. Если a_i>b_j, вычеркивают столбец, при a_i <b_j вычеркивают стро­ку.

Далее процесс (итерации, шаги) повторяют до тех пор, пока не будут распределены все поставки.

Если матрица большая и в уме не удержать нераспреде­ленные мощности и спрос на шагах в процессе распределе­ния на части значений a_i и b_j, в конце каждого шага оста­точные величины записывают в рабочую таблицу.

Распределение поставок по методу минимального эле­мента выполняется в следующей последовательности.

Шаг 1. Находим минимальное значение стоимости C_ij. В нашем случае это будет C₂₁ = 4. В эту клетку таблицы за­писываем возможную поставку, т. е. минимальную из А₂ и В₁, Сравнивая А₂ = 600 и В₁ = 450, записываем в клетку Х₂₁ поставку 450. Вычисляем нераспределенные мощности по­ставщиков и неудовлетворенный спрос потребителей (табл.1.3).

Потребитель В₁ — удовлетворен полностью, во вспомога­тельной части таблицы проставляем 0, а столбец в дальней­ших расчетах не рассматриваем.

Потребитель В₂ неудовлетворен, его спрос остался рав­ным 400, что и записываем во вспомогательной части табли­цы.

Потребитель В₃ — неудовлетворен, спрос остался — 200.

Потребитель В₄ — неудовлетворен, спрос —350.

Поставщик А₁ — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.

Поставщик А₂ — часть мощности распределена потреби­телю В₁ но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.

Поставщик А₃ — мощность его не распределена и запи­сываем результат нераспределенной мощности 500.

Сумма нераспределенных мощностей и неудовлетворен­ного спроса по результатам первой итерации (шага) равна 950, что и записываем в итоге и это является проверкой того, что нет арифметических ошибок. Аналогично заполняется рабочая таблица по шагам.

Шаг 2. Находим минимальное значение стоимости C_ij без вычеркнутого столбца В₁ это значение С₃₃ =5. Записы­ваем в эту клетку (табл. 1.4.) возможную поставку-минимум из А₃ = 500 и В₃=200, min=200, записываем нераспределенные мощно­сти и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.

Шаг 3. Минимальный элемент А₂В₂ = 7. В эту клетку записываем минимальное значение из нераспределенной мощ­ности А₂=150 и спроса В₂=400, min=150. В результате третьего шага мощность поставщика А₂ исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спроса осталась равной 600. Продолжая аналогично, доводим рас­пределение до конца.

Шаг 4. Минимальное C_ij из оставшихся имеют клетки А₁В₂ и А₃В₂ — выбираем А₃В_2. Записываем сюда поставку 250 как минимум из значений остатка потребителя В₂ и по­ставщика А₃ и так далее.

Результат распределения по методу минимального элемента показан в табл.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 пункта назначения. В ней записано некоторое базисное решение в заштрихованных клетках x₁₁, x₁₂, x₂₃, x₂₄, x₃₂, x₄₁ и x₄₃, число которых должно быть r=m+n-1=7. При этом в каждой строке и каждом столбце таблицы должна быть как минимум одна базисная клетка.

	В1	В2	В3	В4
А1	–			· +
А2			+	–
А3
А4	+		–

Построим цикл пересчета для свободной клетки x₁₄ так, чтобы все остальные вершины лежали в базисных клетках. Такой цикл существует только один и приведен в таблице, при этом свободной клетке x₁₄ присваивается знак «+», а знаки всех последующих вершин чередуются при их обходе по циклу в одном направлении.

Таким образом, можно по теореме утверждать, что клетка x₁₄ входит в выражение для неизвестных базисных со знаками:

.

Аналогично можно найти коэффициенты для других свободных неизвестных.

У распределительного метода существуют промежуточные базисные решения, каждое из которых постепенно приближается к оптимальному.

Найденное любым методом допустимое базисное решение вносится в матрицу перевозок и занимает r=m+n-1 клеток. Вносятся и нулевые базисные решения. Далее меняются местами базисные и свободные переменные для приближения к оптимальному решению.

Во-первых, определяется свободная неизвестная, переводимая в число базисных.

Рассмотрим способ определения свободных неизвестных, которые целесообразно перевести в число базисных на конкретном примере. Возьмем базисное решение, найденное методом северо-западного угла со стоимостью перевозок

=2×20 + 3×10 + 2×20 + 5×20 + 2×10 + 6×10 = 290.

Теперь необходимо построить циклы пересчета для всех свободных переменных (свободных клеток) и определить сумму стоимостей по циклам пересчета g_ij для всех свободных неизвестных, чтобы найти, какую из них перевести в число базисных для уменьшения целевой функции.

Определяем сумму стоимостей по циклу пересчета для каждой свободной клетки, подставляя соответствующие стоимости перевозок из базисных клеток в вершинах цикла:

х₁₃ ® g₁₃ = с₁₃ - с₂₃ + с₂₂ - с₁₂ = 2 - 5 + 2 - 3 = -4,

х₁₄ ® g₁₄ = с₁₄ - с₂₄ +с₃₃ – с₂₃ + с₂₂ - с₁₂ = 4 – 6 + 2 - 5 + 2 - 3 = -6,

х₂₁ ® g₂₁ = с₂₁ - с₁₁ + с₁₂ - с₂₂ = 3 - 2+ 3 - 2 = 2,

аналогично g₂₄ = - 8, g₃₁ = 6, g₃₂ = 4.

Выбираем те из свободных переменных, которые имеют отрицательное значение суммы стоимости по циклу пересчета. В рассматриваемом примере это х₁₃, х₁₄, х₂₄.

Во-вторых, определяется базисная переменная, переводимая в число свободных.

Для этого необходимо проанализировать цикл пересчета, соответствующий выбранной свободной неизвестной. В нашем примере это может быть цикл для переменной х₁₃.

Производя преобразования по циклу, мы должны получить нуль в одной из базисных переменных. Кроме того, необходимо учитывать, что переменные не могут принимать отрицательных значений. Поэтому выбирается та базисная переменная, которая имеет наименьшее значение из всех базисных переменных, расположенных в отрицательных вершинах цикла пересчета. В нашем примере это будет х₁₂=10.

Для получения нового допустимого базисного решения осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₁₃ на величину значений выбранной базисной переменной х₁₂=10, которая после сдвига переводится в свободные.

При этом получим новую таблицу матрицы перевозок.

Сдвиг по циклу привел к новому допустимому базисному решению:

х₁₁=20, х₁₃=10, х₂₂=30, х₂₃=10, х₃₃=10, х₃₄=10, остальные x_ij=0.

Новое решение дает значение целевой функции F=250, меньшее предыдущего, т. е. ближе к оптимальному значению.

Если в отрицательных вершинах с минимальными перевозками окажется две базисных клетки с одинаковыми значениями, то после сдвига по циклу в число свободных переводится только одна из них, а вторая остается в числе базисных с нулевыми перевозками. И в дальнейших расчетах эта клетка фигурирует как базисная со всеми их характеристиками.

Для нового базисного решения также подсчитываются суммы стоимостей по циклам пересчета для каждой свободной неизвестной: g₁₂=4, g₁₄=2, g₁₂=4, g₂₁= - 2,g₂₄= - 8, g₃₁= 2, g₂₃= 4.

Выбираются новые свободная и базисная переменные для сдвига по новым циклам, и все повторяется. Операция продолжается до тех пор, пока не получится, что все стоимости по циклам пересчета больше нуля (g_ij > 0), что является признаком оптимальности решения, полученного распределительным методом.

Для рассматриваемого примера оптимальным решением является следующее:

х₁₁=20, х₁₃=10, х₂₂=30, х₂₄=10, х₃₃=10, х₁₂=0, остальные x_ij=0. Стоимость оптимальной перевозки F=170, и уменьшить ее дальше невозможно.