Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Венгерский метод решения задачи о назначенияхАлгоритм нахождения оптимального назначения максимальной стоимости 1 шаг. В каждом столбце выбрать максимальный элемент. 2 шаг. Пересчитать все элементы каждого столбца по правилу: новое значение элемента столбца = максимальный элемент столбца – старое значение элемента столбца. 3 шаг. Если в каждой строке и в каждом столбце имеется нуль, то переходим к шагу 5. 4 шаг. В каждой строке выбрать минимальный элемент и из каждого элемента строки вычесть соответствующие минимальное значение. 5 шаг. В полученной матрице найти строку или столбец с одним нулем. 6 шаг. Строку и столбец, находящиеся на пересечении выбранного нулевого элемента из дальнейшего рассмотрения исключить. Данный нулевой элемент выделить. 7 шаг. В оставшейся матрице найти строку или столбец с одним нулевым значением. Данный нулевой элемент выделить. Строку и столбец, на пересечении которых находится найденный нулевой элемент, вычеркнуть из дальнейшего рассмотрения. 8 шаг. Процесс повторять до тех пор, пока все работы не будут распределены между работниками (при этом выбираются только нулевые назначения). 9 шаг. Если распределить работы не удается, то после шага 4 в полученной матрице минимальным количеством вертикальных и горизонтальных прямых вычеркиваются все нули матрицы. 10 шаг. В оставшейся матрице найти минимальный элемент. 11 шаг. К элементам, лежащим на пересечении вертикальных и горизонтальных прямых, найденный минимальный элемент прибавить. 12 шаг. Из всех невычеркнутых элементов матрицы найденный минимальный элемент вычитается. 13 шаг. Повторить шаги 5–8. Алгоритм определения назначения минимальной стоимости отличается от описанного двумя первыми шагами. На первом шаге в каждом столбце выбирается минимальный элемент, который вычитается из всех элементов столбца (шаг 2). Задача 1 На автомойку приехали три машины: Ауди, Пежо и ВАЗ. На автомойке есть три поста, на каждом из которых можно обслужить любую из этих трех машин, но за различную плату (см. таблицу). Стоимость мойки автомобиля
Распределить машины между постами с максимальным доходом для автосервиса. Решение Определим максимальный элемент в каждом столбце.
Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это вторая строка и второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.
В оставшейся матрице в каждой строке и в каждом столбце остались только нулевые значения. Это означает, что данная задача имеет два варианта решения. 1 вариант.
Выделенные нули определяют оптимальное решение: на посту 1 моются машины Ауди, на втором посту– Пежо, на третьем – ВАЗ. Суммарный доход 3 + 7 + 8 = 18 у.е. 2 вариант.
Выделенные нули определяют оптимальное решение: на посту 1 моются машины ВАЗ, на втором посту– Пежо, на третьем – Ауди. Суммарный доход 6 + 7 + 5 = 18 у.е. Задача 2 Время опоздания трех сотрудников на работу (в минутах) в зависимости от коллективов представлено в таблице. Распределить работников в коллективы таким образом, чтобы суммарное время опозданий было минимальным.
Решение Определим минимальный элемент в каждом столбце.
Вычтем из элементов столбца минимальный элемент столбца. Определим минимальные элементы по строкам.
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это первая, третья строка и первый, второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.
В оставшейся матрице в каждой строке имеется по одному нулю, расположенные в первом и третьем столбце. Таким образом, данная задача имеет один вариант решения.
Выделенные нули определяют оптимальное решение: в первом коллективе должен работать первый сотрудник, во втором – второй, в третьем коллективе третий сотрудник. Суммарное время опоздания: 4 + 2 + 3 = 9 минут. Задача 3 Производительность (тыс. шт.) работников предприятия на соответствующих работах представлена в виде матрицы.
Распределить работы среди претендентов с максимальной суммарной производительностью для предприятия. Решение Определим максимальный элемент в каждом столбце.
Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.
Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.
В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это третья строка и второй и четвертый столбцы. Выберем элемент (4,4) и вычеркнем четвертую строку и четвертый столбец. Элемент (4,4) выделим.
В оставшейся матрице во втором столбце все элементы ненулевые, а, следовательно, в данной матрице нельзя распределить работы между претендентами. Преобразуем таблицу 3, вычеркнув все нули минимальным количеством вертикальных и горизонтальных прямых.
В оставшейся матрице минимальное значение равно единице. К элементам, лежащим, на пересечении вертикальных и горизонтальных прямых, прибавим минимальное значение, а из невычеркнутых вычтем.
В полученной матрице третья строка и четвертый столбец содержат один нуль. Выберем элемент (4,4) и вычеркнем четвертую строку и четвертый столбец. Элемент (4,4) выделим.
В оставшейся матрице в третьей строке и втором столбце имеется один нуль. Выберем ячейку (3,3) и вычеркнем третью строку и третий столбец. Элемент (3,3) выделим.
В полученной матрице первая строка имеет два нулевых значения, вторая только один, поэтому данная задача имеет только одно решение.
Выделенные нули определяют оптимальное решение: первого работника необходимо назначить на вторую работу, второго – на первую, третьего – на третью, четвертого – на четвертую работу. Суммарная производительность: 7 + 6 + 7 + 8 = 28 тыс. шт. Задача коммивояжера Задача коммивояжера решается в случае, когда необходимо посетить n городов по одному разу и вернуться в исходный город. Расстояние между любыми двумя городами i и j известно и равно ci,j (¥, если между городами нет дороги). Цель задачи – найти кратчайший маршрут (гамильтонов контур минимальной длины). Для точного решения задачи коммивояжера необходимо исследовать все возможные маршруты (все гамильтоновы контуры). Для задачи с n городами общее число гамильтоновых контуров равно (n – 1)! При большом n это число довольно велико, поэтому часто приходится ограничиваться поиском приближенно оптимальных решений. В настоящее время существует значительное число приближенных методов решения задачи коммивояжера. Одним из наиболее простых является метод ближайшего соседа (ближайшего непосещенного города). Данный метод целесообразно применять при количестве городов более 40. Качество решения зависит от выбора начальной вершины, поэтому замкнутые контуры необходимо строить для каждой вершин, рассматриваемой как начальной. Одним из наиболее распространенных методов решения задачи коммивояжера является метод ветвей и границ. Метод ближайшего соседа Алгоритм решения включает следующие шаги. 1 шаг. Выбрать первую вершину. 2 шаг. Для выбранной вершины найти наиболее близкую к ней. Если данная вершина уже вошла в маршрут, то она блокируется, и выбирается следующая по степени близости. 3 шаг. Повторять шаг 2 до тех пор, пока маршрут (путь) не пройдет через все вершины. 4 шаг. Выбрать вторую вершину и повторить шаги 2–3. 5 шаг. Процесс считается законченным, когда гамильтоновы контуры построены для всех вершин, выбранных в качестве начальных. 6 шаг. Рассчитать длину каждого из полученных маршрутов и выбрать минимальное значение. Задача Решить задачу коммивояжера со следующей матрицей расстояний.
Символ ¥ на главной диагонали означает фактический запрет на переход вида i ® i (из города в него же). Решение Решение задачи начнем с рассмотрения первой вершины в качестве начальной. Наиболее близкой к ней вершиной является четвертая. Расстояние между первым и четвертым городом 8 км. Наиболее близкой к четвертой вершине является пятая и шестая. Так как данные вершины еще не входили в маршрут, то далее следует рассматривать два варианта. 10 5 8 1 4
10 6
Для пятой вершины наиболее близкой является первая, которая уже вошла в маршрут. Поэтому выбираем следующую по близости вершину – третью. Для шестой вершины ближайшим соседом является вторая, которую и выбираем для проходящего через нее пути.
1 7 9 10 5 3 1 4 10 6 2
Ближайшей к третьей вершине является шестая (первая, четвертая и пятая вошли в путь). Ко второй – третья (четвертая и шестая вошли в маршрут).
1 4 5 1 13 9 13 4 15 10 5 3 6 1 4 3 7 10 6 2 3 5 3
4 6
Следующей по степени близости к шестой вершине является вторая; к третьей – пятая. Данные вершины были последними в цепи городов, которые необходимо посетить, поэтому для создания замкнутого маршрута вернемся в первый город. 1 4 5
1 13 13 4 9 15 3 21 10 5 3 6 2 1 1 4 3 7 4 7 10 6 2 3 5 1
4 6
Суммарное расстояние для пути: 1 – 4 – 5 – 3 – 6 – 2 – 1 Z = 8 + 10 + 9 + 15 + 3 + 21 = 64 км. 1 – 4 – 6 – 2 – 3 – 5 – 1 Z = 8 + 10 + 3 + 7 + 4 + 7 = 39 км.
Для других вершин замкнутые контуры построены на рисунках. 2 6 2 4 5 6 а) 3 10 10 8 9 11 3 8 10 7 12 19 2 6 4 5 1 3 2
Суммарное расстояние: 2 – 6 – 4 – 5 – 1 – 3 – 2 Z = 3 + 8 + 10 + 7 + 12 + 19 = 59 км. б) 5 4 6
10 5 3 4 7 8 10 3 7 3 5 1 4 6 2 3
Суммарное расстояние: 3 – 5 – 1 – 4 – 6 – 2 – 3 Z = 4 + 7 + 8 + 10 + 3 + 7 = 39 км.
в) 4 5 2 4 8 9 3 8 10 7 10 3 11 13 4 5 1 2 6 3 4
Суммарное расстояние: 4 – 5 – 1 – 2 – 6 – 3 – 4 Z = 10 + 7 + 10 + 3 +11 + 13 = 54 км. г) 4 6 5 3 10 3 7 4 7 8 4 6 2 3 5 1 4
Суммарное расстояние: 4 – 6 – 2 – 3 – 5 – 1 – 4 Z = 10 + 3 + 7 + 4 + 7 + 8 = 39 км.
д) 5 4 6
10 5 3 7 8 10 3 7 4 5 1 4 6 2 3 5
Суммарное расстояние: 5 – 1 – 4 – 6 – 2 – 3 – 5 Z = 7 + 8 + 10 + 3 + 7 + 4 = 39 км.
е) 6 6 2 4 5 6
3 10 10 8 9 11 3 5 10 7 12 15 6 2 4 5 1 3 6
Суммарное расстояние: 6 – 2 – 4 – 5 – 1 – 3 – 6 Z = 3 + 5 + 10 + 7 + 12 + 15 = 52 км. Оптимальными маршрутами следования будут: 1 – 4 – 6 – 2 – 3 – 5 – 1; 3 – 5 – 1 – 4 – 6 – 2 – 3; 4 – 6 – 2 – 3 – 5 – 1 – 4; 5 – 1 – 4 – 6 – 2 – 3 – 5. Для всех этих маршрутов общее расстояние обхода всех городов является минимальным и составляет 39 км. Метод ветвей и границ Метод ветвей и границ относится к комбинаторным оптимизационным методам. Он предполагает направленный перебор вариантов и в ряде случае позволяет уйти от полного перебора. Метод основан на разбиении всего множества решений задачи на подмножества (ветвление) и оценивании стоимости решения на каждом подмножестве. Рассмотрим общую идею и алгоритм решения задачи коммивояжера методом ветвей и границ с помощью алгоритма Литтла. Пусть W – множество всех замкнутых маршрутов, проходящих через все города по одному разу. Такие маршруты называют гамильтоновыми контурами. Для каждого маршрута известна его длина. Основная идея метода состоит в том, что вначале находят нижнюю границу длин всех гамильтоновых контуров W0, т.е. число, не большее, чем длина любого гамильтонова контура (нижняя оценка длины маршрута ). Это число может быть найдено до того, как найден сам наиболее короткий маршрут. Далее все множество гамильтоновых контуров разбивается на два подмножества таким образом, чтобы любой контур в первом множестве содержал некоторую дугу (i, j), т.е. переход из города i в город j; второе множество состоит из контуров, эту дугу не содержащих. Для каждого из этих подмножеств определяются нижние границы длины входящих в них гамильтоновых контуров (нижняя оценка длины маршрута) аналогично тому, как это определялось для всего множества. Для дальнейшего рассмотрения выбирается подмножество с меньшей оценкой. Это подмножество в свою очередь подвергается ветвлению на два, для каждого из которых определяется нижняя оценка длины маршрута. Из всех не исследованных к данному моменту подмножеств (т. е. таких, которые еще не были подвергнуты разбиению, или ветвлению ) для дальнейшего рассмотрения выбирается подмножество с меньшей оценкой и т. д. пока не будет определен гамильтонов контур минимальной длины. Параллельно расчетам строится дерево ветвления. Рассмотрим основные шаги решения. 1 шаг. Осуществить приведение матрицы по строкам: определить минимальный элемент каждой строки и вычесть из элементов строк найденный минимальный элемент. 2 шаг. Осуществить приведение матрицы по столбцам: определить минимальный элемент в каждом столбце и вычесть из элементов столбцов найденный минимальный элемент. 3 шаг. Найти константу приведения (j0) как сумму найденных минимальных элементов строк и столбцов. Константа приведения j0 является нижней границей длины для множества гамильтоновых контуров. 4 шаг. Для каждого нуля приведенной матрицы определить его «степень» как сумму минимальных элементов строки и столбца, содержащих этот нуль. 5 шаг. Нулевой элемент с наибольшей степенью задает дугу (t0, j0), по которой проводится разбиение множества гамильтоновых контуров (t0 – строка, а j0 – столбец, на пересечении которых находится выбранный нулевой элемент). В множество включаются все контуры, содержащие эту дугу, в множество – не содержащие ее. 6 шаг. Матрицу, описывающую множество , получаем из приведенной матрицы путем вычеркивания строки to и столбца jo. На дереве ветвления обозначаем, что рассматриваются контуры, включающие дугу (t0, j0). Вводя в маршрут дугу (to, jo), следует заблокировать все изолированные контуры, которые могут содержать эту дугу. Для блокировки в соответствующую клетку матрицы вводится «¥». В частности, значение элемента (jo, to) в матрице заменяем на ¥, так как рассматриваются маршруты, содержащие переход из города t0 в j0, а значит, обратный переход из города jo в to уже невозможен. 7 шаг. Выполнить приведение матрицы множества по строкам и столбцам и определить нижнюю границу этого множества по формуле: , где – сумма минимальных элементов, используемых для приведения матрицы множества . 8 шаг. Матрицу множества получаем из исходной матрицы, рассматриваемой на шаге 4, заменой элемента (to, jo) на ¥. 9 шаг. Для полученной матрицы множества определить константу приведения ( ) и нижнюю границу множества по формуле , выполнить приведение матрицы. 10 шаг. Дальнейшему ветвлению подвергается подмножество, имеющее меньшее значение нижней границы. 11 шаг. Для выбранного множества повторить шаги 4–9. 12 шаг. Процесс считается завершенным, когда остается матрица размера 2х2. Для данной матрицы в гамильтонов контур включаются связи, соответствующие нулевым элементам. 13. шаг. Найти длину полученного гамильтонова контура и сравнить ее с оценками (нижними границами) еще не исследованных множеств. Если все нижние границы не исследованных множеств больше или равны длине найденного контура, задача считается решенной. В противном случае следует продолжить ветвление с множества, имеющего наименьшую нижнюю границу. Задача Решить методом ветвей и границ задачу коммивояжера со следующей матрицей расстояний (эта же задача решалась в предыдущем параграфе методом ближайшего соседа).
Решение Осуществим приведение матрицы по строкам, определив минимальное значение в каждой строке (ui).
Вычтем минимальные элементы из соответствующих строк и определим сумму минимальных значений.
Осуществим приведение матрицы по столбцам, определив минимальное значение в каждом столбце (ni).
Вычтем минимальные элементы из соответствующих столбцов и определим сумму минимальных значений.
. Константа приведения: Найдем степени нулей для приведенной матрицы. Для этого выберем минимальные элементы в строке и столбце, где расположен нуль, и просуммируем их.
Наибольшая степень нулевого элемента равна девяти и соответствует связи (3,5). Разобьем множество гамильтоновых контуров на два подмножества и . Матрицу множества получаем вычеркиванием третьей строки и пятого столбца приведенной матрицы. Элемент (5,3) заменим на ¥.
Сделаем приведение полученной матрицы по третьему столбцу (нет нулевого элемента) и определим нижнюю границу множества.
Матрицу множества получим путем замены элемента (3,5) на ¥.
Осуществим приведение матрицы по третьей строке (нет нулевого элемента) и определим нижнюю границу множества.
.
Отобразим проделанные действия на дереве ветвления. W0 j0 = 37
(3,5)
Для дальнейшего исследования выбираем множество , т. к. ему соответствует меньшая нижняя граница: < . Множество подвергаем дальнейшему ветвлению Находим степени нулей матрицы множества .
Ячейка (5,1) содержит наибольшую степень нуля. Разобьем множество < |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |