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




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

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

 

1.Построение первоначального плана

   
 

 

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

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, и уменьшить ее дальше невозможно.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2018-01-30 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: