Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Решение задачи методом потенциалов




Существует две группы методов получения оптимального плана транспортной задачи.

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

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача:

Двойственная задача:

План Х=(хij) транспортной задачи будет являться оптимальным, если существует система m+n чисел αi, βj, называемых потенциалами, удовлетворяющих условиям:

max ( ai + bj)

αi + βj = cij для занятых клеток, где xij> 0, i=1,m

αi + βj ≤ cij для незанятых клеток, где xij = 0. j=1,n

Потенциалы αi и βj являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу αi + βj = cij.

Введем обозначение оценки свободной клетки таблицы

ij = αi+ βj – cij.

Если среди оценок ∆ij нет положительных (задача поставлена на минимум), то опорный план является минимальным.

Алгоритм оценки оптимальности плана методом потенциалов включает следующие этапы.

· Построение первого опорного плана.

· Проверка вырожденности плана. Потенциалы αi и βj могут быть рассчитаны только для невырожденного плана.

· Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем производимого груза по всем занятым клеткам таблицы

· Проверка условий оптимальности. Определяем потенциалы αi и βj. Для каждой занятой клетки таблицы записываем уравнение αi + βj = cij(i=1,m; j=1,n). Получим систему (m+n-1) уравнений с (m+n) переменными.

Так как число переменных больше числа уравнений (m+n>m+n-1), то система является неопределенной и имеет бесконечное число решений. Поэтому одному из неизвестных потенциалов αi, βj задают произвольное значение, например, для одного из столбцов (отправителей)принимают потенциал αi равный нулю. При этом целесообразно нулю приравнивать потенциал того столбца, в котором имеется загруженная клетка с наибольшим тарифом. Остальные потенциалы определяют по загруженным клеткам.

Определяем оценки свободных клеток ∆ij.

Если ij ≤ 0 (задача решается на минимум целевой функции) либо все ij ≥ 0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки ij> 0 (задача поставлена на минимум) или i< 0 (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза.

· Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача построена на минимум), из отрицательных – наибольшую по отрицательной величине (если задача построена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз. Заполняя выбранную клетку необходимо измерить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом.

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

Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-».

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

Полученный новый опорный план проверяется на оптимальность, т.е. возвращаемся к четвертому этапу алгоритма.

Примечания.

1. Если в минусовых клетках построенного цикла находится два (или несколько) одинаковых минимальных значения хij, то при перераспределении объемов груза освобождаются две (или несколько) клеток и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наименьшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (m+n-1).

2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю (∆ij=0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

F(Xk) = F(Xk-1) - γ∆ij (задача поставлена на минимум)

F(Xk) = F(Xk-1) + γ∆ij (задача поставлена на максимум)

Где γ – величина перемещаемого по циклу груза;

∆ij - оценка свободной клетки, в которую направляется груз при переходе к новому плану;

F(Xk) – значений целевой функции на k-й итерации;

F(Xk-1) – значение целевой функции на предыдущей итерации.

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

         
  304      
  403 1201 302  
      1203 1307

План не вырожденный; F(x)=1690

Проверяем полученный план на оптимальность и находим оценки свободных клеток (согласно алгоритму)

Составляем уравнения для определения потенциалов (для каждой загруженной клетки).

α1+ β1 =4; α2+ β1 =3; α2+ β2 =1; α2+ β3 =2; α3+ β3 =3; α3+ β4 =7.

Полагая, что α3=0, то получаем: β4 =7; β3 =3; α2=-1; β2 =2; β1 =4; α1=0.

Получаем следующую таблицу.

bj ai         αi
  304       α1=0
  403 1201 302   α2=-1
      1203 1307 α3=0
βj β1 =4 β2 =2 β3 =3 β4 =7  

Далее вычисляем оценки свободных клеток и выполнения условия ij< αi + βj – cij

Для клетки (1,2): 0 + 2 - 7 = -5

Для клетки (1,3): 0 + 3 - 2 = 1

Для клетки (1,4): 0 + 7 - 3 = 4

Для клетки (2,4): -1 + 7 - 4 = 2

Для клетки (1,2): 0 + 4 - 5 = -1

Для клетки (1,2): 0 + 2 - 6 = -4

Наличие положительных оценок свидетельствует о том, что план не оптимален и его можно улучшить.

Для свободной клетки, имеющей максимальную положительную оценку- +4 (клетка 1,4) строим контур (цикл) перераспределения груза, так, чтобы вершины контура лежали в загруженных клетках.

 

bj ai         αi
  30     +43  
          -1
           
βj          

 

Нарисуем этот цикл. Для каждой клетки указаны ее индексы и объем поставок.

 

 

+
-
(1.1) (1.4)

-  
-  
(2.3)

 

 


+
(3.4)

(2.1)
+    
(3.3)

 

 


Стартовой клетке (1,4) припишем знак «+». Двигаясь по циклу, чередуем знаки. Среди поставок со знаком «-» (это клетки (1,1),(2,3),(3,4)) найдем минимальную: min(30,30,130) =30. После этого в клетках со знаком «-» уменьшим поставки на этот минимум, а в клетках со знаком «+» увеличим на этот минимум. Клетка (1,4) становится отмеченной (загруженной).

Если получена одна клетка с нулевой поставкой, то она становится пустой. У нас таких клеток две – (1,1),(2,3). Поэтому пустой объявим только одну из них с наибольшим тарифом– клетку (1,1). В клетку (2,3) будет сделана нулевая поставка, и она останется отмеченной. Это делается для выполнения соотношения: число отмеченных клеток = число столбцов + число строк – 1. Получаем новый план поставок.

 

 

bj ai         Αi  
          -4
      0 +2 4   -1
           
Βj          

 

Для нового плана находим оценки строк и столбцов. Затем получим матрицу оценок клеток:.

План является неоптимальным, так как оценка клетки (2,4) больше нуля. Строим для нее цикл пересчета: (2,4) – (3,4) – (3,3) – (2,3) – (2,4) и получаем новый план:

 

 

Bj Ai         ai  
          -4
  70       -3
  +1 5        
bj          

 

Для нового плана находим оценки строк и столбцов. Затем получаем матрицу оценок клеток:.

План является неоптимальным, так как оценка клетки (3,1) больше нуля. Строим для нее цикл пересчета: (3,1) - (2,1) - (2,4) - (3,4) - (3,1).

 

-
+
+
-
(2.4)
(3.4)
(3.1)
(2.1)

 

 


min (70,100) = 70. В клетках с «+» поставки увеличиваются на 70, а в клетках с «-» поставки уменьшаются на 70. Клетка (2,1) становится пустой. Новый план поставок:

Bj Ai         ai  
          -4
          -3
           
bj          

 

Находим оценки срок и столбцов. Получаем матрицу оценок:

Матрица оценок не содержит положительных чисел. Получен оптимальный план поставок. Суммарные затраты на перевозку груза равны: 3*30+1*120+4*70+5*70+3*150+7*30=1500.

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

Поставщик А1 должен поставить 30 единиц груза потребителю В4. Поставщик А2 должен поставить 120 единиц груза потребителю В2 и 70 единиц груза потребителю В4.. Поставщик А3 должен поставить 70 единиц груза потребителю В1, 150 единиц груза потребителю В3, 30 единиц груза потребителю В4.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...