Открытая модель сводится к закрытой. Если суммарная мощность поставщика больше суммарного спроса потребителей, то вводится фиктивный потребитель, к которому присваивается спрос равный разнице между мощностью поставщиков и спросом потребителей. Стоимость перевозок единицы от поставок до фиктивного потребителя полагается равной нулю. Получается закрытая модель, которая решается ранее изложенными методиками. А если суммарная мощность поставщиков меньше суммарного спроса потребителя, то вводится фиктивный поставщик, также получается закрытая модель, которая решаема.
Например:
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 (по строкам) (по столбцам)
|
|
3 14 9 1 1 2 13 8 0 2 11 8 0 2 11 8 0
|
|
|
|
Больше нет нулей.
Это распределение не оптимально, так как во второй строке нет отмеченных нулей. Проведем минимальное число пересекающихся горизонтальных и вертикальных прямых через все отмеченные нули. Среди не зачеркнутых чисел найдя минимум, вычитаем его из всех, не зачеркнутых чисел, и прибавляем его к числам на пересечении прямых. (П6)
|
|
|
|
|
|
|
|
|
min(8,3,1,3)=1 min (7,2,2)=2; min=5
|
|
|
|
0 6 0 0
Это оптимальное решение, возможно не единственное.
А1 прикрепляется к В4 -5
А2 прикрепляется к В3 -9
А3 прикрепляется к В2 -8
А4 прикрепляется к В1 -7
Для нахождения суммарного расстояния надо сложить числа из исходной матрицы на месте нулей:
5+9+8+7=29
Максимизация целевой функции:
В этом случае задача сводится к задаче минимизации для матрицы, полученной из исходной матрицы, умноженной на -1.
Тема III. Динамическое программирование.
Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги).
Динамическое программирование применяется для решения задач мелкого масштаба (по сравнению с методами линейного программирования).