Открытая (не сбалансированная) модель ТЗ.

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

 

Например:

Nj Mi
 
 
 

 

Суммарная мощность поставщиков:

40+60+50=150

Суммарный спрос потребителей:

30+40+60=130

Модель открытая(несбалансированная). Вводим фиктивный потребитель, которому присваиваем спрос: 150-130=20.

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

 

Nj Mi
 
 
 

 

 

Если суммарная мощность поставщиков меньше суммарного спроса, то вводится фиктивный поставщик, которому приписывается мощность, равная разности между спросом потребителей и мощностью поставщиков. Стоимость перевозок от фиктивного поставщика полагается равной 0. Полученная закрытая модель – решается.

2.6 Задача о назначениях.

Эта задача является частным случаем ТЗ, в этом случае число поставщиков равно числу потребителей. Мощность каждого поставщика и спрос каждого потребителя равен 1. Решается задача венгерским методом. Различают задачи:

-минимизация целевой функции;

-максимизация целевой функции;

Минимизация целевой функции:

Алгоритм решения задачи:

1) В каждой строке матрицы задачи находим минимальных элемент и вычитаем его из всех элементов строки;

2) В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.

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

4) Находим столбец с одним нулем и отмечаем этот элемент, а в строке, где находится отмеченный нуль, все остальные нули зачеркиваются.

5) Если после шагов (3) и (4) еще есть неотмеченный нули, то отмечаем любой из них, и в строке и в столбце с отмеченным нулем, все остальные нули зачеркиваются.

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

7) Если в какой- нибудь строке или столбце отсутствует отмеченный нуль, проводим минимальное число пересекающихся горизонтальных и вертикальных прямых через все отмеченные нули. Среди не зачеркнутых этими прямыми чисел находим минимум. Этот минимум вычитается из всех не зачеркнутых чисел и прибавляется ко всем числам на пересечении прямых. К полученной матрице применяется выше описанный алгоритм, начиная с шага (3).

 

Пример:

 

Существует 4 базы А1, А2 , А3 , А4 и 4 потребителя B1, B2, B3, B4. Расстояние от баз до потребителей задано матрицей:

 

 

 

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

Решение:

П1 П2 П3 П4

0 2 0 0 (по строкам) (по столбцам)

 
 
10 20 12 5 5 5 15 7 0 5 13 7 0 5 13 7 0

3 14 9 1 1 2 13 8 0 2 11 8 0 2 11 8 0

 
 
13 8 6 9 6 7 2 0 3 7 0 0 3 7 0 0 3

 
 
7 15 8 10 7 0 8 1 3 0 6 1 3 0 6 1 3

Больше нет нулей.

 

Это распределение не оптимально, так как во второй строке нет отмеченных нулей. Проведем минимальное число пересекающихся горизонтальных и вертикальных прямых через все отмеченные нули. Среди не зачеркнутых чисел найдя минимум, вычитаем его из всех, не зачеркнутых чисел, и прибавляем его к числам на пересечении прямых. (П6)

 

                                   
   
     
           
         
 
 
 
 
 
 

 
 
5 13 7 0 6 14 7 0 8 13 7 0

 
 
2 11 8 0 применим 2 11 8 0 применим 2 11 5 0 применим

 
 
7 0 0 3 алгоритм с П3,П4. 7 0 0 2 алгоритм с П3,П4 7 0 0 0 алгоритмП3,П4

 
 
0 6 1 3 0 6 0 2 0 6 0 0

min(8,3,1,3)=1 min (7,2,2)=2; min=5

 
       
   
 
 

 
13 21 7 0

 
2 11 0 0

 
7 0 0 0

0 6 0 0

       
   


Это оптимальное решение, возможно не единственное.

А1 прикрепляется к В4 -5

А2 прикрепляется к В3 -9

А3 прикрепляется к В2 -8

А4 прикрепляется к В1 -7

 

 

Для нахождения суммарного расстояния надо сложить числа из исходной матрицы на месте нулей:

5+9+8+7=29

Максимизация целевой функции:

В этом случае задача сводится к задаче минимизации для матрицы, полученной из исходной матрицы, умноженной на -1.

 

Тема III. Динамическое программирование.

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

Динамическое программирование применяется для решения задач мелкого масштаба (по сравнению с методами линейного программирования).