- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Лабораторная работа 14. Задача о назначении. Венгерский метод
Постановка задачи о назначении.
Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию
L(X)= c11 x11 +...+ c1n x1n +...+ cn1 xn1 +...+ cnn xnn (14.1)
и удовлетворяет систему ограничений
xi1 + ... + xin = 1, i=1...,n (14.2)
x1j + ... + xnj = 1, j=1...,n (14.3)
xij = 0 или 1, і,j=1...,n (14.4)
где сіj — расходы, связанные с использованием і-го исполнителя для выполнения j-ї работы (і,j=1...,n). Элементы сіj образуют матрицу расходов C.
Задача (14.1)–(14.4) Решается венгерским методом, что основывается на том факте, что вычитание числа ai, i=1...,n, от каждого элемента і-го строки и числа bj, j=1...,n, от каждого элемента j-го столбца матрицы расходов C не изменяет множества оптимальных назначений. В этом понимании можно говорить, что указанные действия превращают матрицу расходов C в эквивалентную ей. В алгоритме, что дается ниже, матрицы, эквивалентные исходной матрице расходов C, называются просто матрицами расходов.
Алгоритм венгерского метода.
1. Отнимаем в матрице C от каждого элемента і-го строки минимальный элемент этой строки (i=1...,n).
2. Отнимаем от каждого элемента j-го столбца преобразованной матрицы расходов его минимальный элемент (j=1...,n). В результате выполнения двух пунктов каждая строка и каждый столбец матрицы расходов имеют по крайней мере один 0.
3. Просматриваем последовательно строки матрицы расходов, начиная с первого. Если строка имеет лишь один необозначенный 0, помечаем его отметкой * но зачеркиваем (с помощью отметки ^) остальных нулей в этом же столбце. 0 считается обозначенным, если он имеет отметку *. Повторяем эти действия, пока каждая строка не будет иметь необозначенных нулей, или будет иметь их по крайней мере два.
4. Действия п. 3 повторяем для всех столбцов матрицы расходов.
5. Действия п.п. 3 и 4 повторяем последовательно (если необходимо) пока не случится один из трех возможных случаев:
i) каждая строка имеет назначение (имеет 0 с отметкой *);
ii) есть по крайней мере два необозначенных нуля в некоторых строках и некоторых столбцах матрицы расходов;
iii) нет необозначенных нулей и полное назначение еще не получено (число нулей с отметкой * меньше n).
6. В случае и) задача об оптимальных назначениях развязана: xij, что отвечают 0*, равняются 1, остальные — 0, конец. В случае ii) произвольно выбираем один из необозначенных нулей, помечаем его отметкой *, зачеркиваем остальных нулей в той же строке и в том же столбце и возвращаемся к п. 3. В случае iii) переходим к п. 7.
7. Помечаем отметкой # строки, для которых не полученное назначение (в которых нет 0*). Такие строки считаем обозначенными, остальные — необозначенными. Аналогично называются и столбцы матрицы расходов.
8. Помечаем отметкой # еще необозначенные столбцы, которые имеют зачеркнутый 0 (обозначен отметкой ^) в обозначенных строках.
9. Помечаем отметкой # еще необозначенные строки, которые имеют назначение (то есть 0*) в обозначенных столбцах.
10. Повторяем действия п.п. 8 и 9 до тех пор, пока больше нельзя будет пометить ни одну строку и столбец матрицы расходов.
11. Вычеркиваем (с помощью отметки &) необозначенные строки и обозначенные столбцы матрицы расходов.
12. Находим минимальный невычеркнутый элемент матрицы расходов, отнимаем его от элементов каждой из невычеркнутых строк, добавляем к элементам всех вычеркнутых столбцов и переходим к п. 3. При этом отметки элементов матрицы расходов (* но ^) теряют свою силу.
Замечание.
1. Если в задаче об оптимальных назначениях (14.1)–(14.4) целевую функцию (14.1) нужно максимизировать, то для ее решения можно применить венгерский метод, заменив матрицу C на –C.
2. За определением в задаче об оптимальных назначениях матрица расходов квадратная. Если матрица C не является квадратной, то она превращается к такой добавлением необходимого числа дополнительных строк или столбцов с соответствующими элементами cij=0. В 1-м случае работы, что получили оптимальные назначения в дополнительных строках, остаются без исполнителей. В 2-м — исполнители, которые получили оптимальные назначения в дополнительных столбцах, остаются без работы.
Программное обеспечение.
Обучающий модуль, с помощью которого задача об оптимальных назначениях решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
Решить венгерским методом задачи об оптимальных назначениях, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи с матрицами расходов C:
1) |
3 |
4 |
2 |
8 |
1 |
7 |
3 |
2) |
6 |
2 |
15 |
2 |
4 |
9 |
5 |
|
2 |
3 |
13 |
9 |
1 |
6 |
2 |
|
12 |
11 |
1 |
13 |
8 |
11 |
13 |
|
12 |
4 |
12 |
5 |
3 |
1 |
4 |
|
3 |
2 |
12 |
9 |
10 |
14 |
1 |
|
5 |
6 |
1 |
7 |
11 |
8 |
6 |
|
7 |
1 |
3 |
4 |
5 |
6 |
8 |
|
11 |
4 |
10 |
10 |
5 |
13 |
7 |
|
8 |
9 |
14 |
3 |
11 |
18 |
12 |
|
9 |
6 |
11 |
12 |
7 |
1 |
2 |
|
1 |
7 |
5 |
6 |
15 |
16 |
2 |
|
2 |
4 |
8 |
5 |
9 |
3 |
10 |
|
13 |
10 |
4 |
7 |
10 |
16 |
17 |
3) |
5 |
17 |
5 |
12 |
11 |
6 |
4 |
4) |
21 |
7 |
2 |
12 |
15 |
2 |
17 |
|
10 |
9 |
6 |
10 |
12 |
16 |
4 |
|
23 |
15 |
24 |
20 |
12 |
5 |
11 |
|
9 |
3 |
2 |
8 |
13 |
14 |
8 |
|
17 |
24 |
4 |
17 |
2 |
22 |
15 |
|
13 |
1 |
7 |
11 |
7 |
18 |
19 |
|
19 |
7 |
8 |
1 |
13 |
14 |
4 |
|
1 |
7 |
12 |
8 |
3 |
1 |
5 |
|
15 |
6 |
6 |
14 |
19 |
3 |
16 |
|
3 |
11 |
13 |
9 |
14 |
20 |
21 |
|
23 |
6 |
5 |
19 |
15 |
11 |
19 |
|
10 |
2 |
6 |
6 |
15 |
15 |
22 |
|
16 |
18 |
22 |
22 |
1 |
1 |
7 |
5) |
2 |
4 |
5 |
10 |
4 |
6 |
8 |
6) |
7 |
9 |
4 |
6 |
4 |
12 |
3 |
|
3 |
6 |
4 |
13 |
6 |
7 |
9 |
|
2 |
4 |
4 |
7 |
8 |
8 |
5 |
|
4 |
7 |
10 |
5 |
10 |
4 |
5 |
|
4 |
5 |
6 |
5 |
12 |
7 |
3 |
|
6 |
5 |
12 |
4 |
7 |
5 |
4 |
|
3 |
6 |
8 |
4 |
6 |
6 |
7 |
|
7 |
4 |
13 |
6 |
6 |
7 |
5 |
|
5 |
10 |
9 |
3 |
8 |
5 |
4 |
|
10 |
8 |
5 |
2 |
8 |
9 |
10 |
|
6 |
9 |
5 |
10 |
9 |
6 |
7 |
|
11 |
9 |
4 |
8 |
4 |
5 |
4 |
|
7 |
4 |
3 |
6 |
2 |
5 |
4 |
Решить венгерским методом задачи об оптимальных назначениях, для которых заданны матрицы эффективностей:
7) |
6 |
7 |
8 |
9 |
10 |
12 |
5 |
8) |
12 |
4 |
8 |
9 |
12 |
4 |
5 |
|
2 |
3 |
4 |
8 |
9 |
16 |
8 |
|
6 |
5 |
10 |
7 |
3 |
6 |
8 |
|
9 |
6 |
3 |
6 |
8 |
9 |
3 |
|
3 |
10 |
4 |
12 |
5 |
6 |
10 |
|
5 |
7 |
6 |
7 |
10 |
7 |
8 |
|
11 |
12 |
16 |
5 |
7 |
8 |
12 |
|
4 |
8 |
18 |
8 |
6 |
2 |
3 |
|
6 |
7 |
4 |
6 |
7 |
2 |
1 |
|
12 |
9 |
2 |
10 |
8 |
4 |
5 |
|
12 |
5 |
7 |
12 |
9 |
4 |
5 |
|
3 |
10 |
3 |
5 |
4 |
3 |
8 |
|
4 |
6 |
8 |
4 |
3 |
6 |
7 |
9) |
6 |
3 |
5 |
4 |
6 |
7 |
8 |
10) |
4 |
3 |
5 |
4 |
8 |
9 |
10 |
|
5 |
2 |
4 |
3 |
8 |
9 |
10 |
|
7 |
6 |
2 |
5 |
12 |
13 |
4 |
|
4 |
3 |
3 |
5 |
4 |
6 |
7 |
|
6 |
5 |
1 |
6 |
7 |
8 |
9 |
|
7 |
5 |
3 |
2 |
1 |
4 |
5 |
|
7 |
4 |
6 |
10 |
4 |
7 |
3 |
|
8 |
6 |
6 |
10 |
12 |
5 |
4 |
|
4 |
3 |
10 |
8 |
5 |
3 |
2 |
|
12 |
7 |
8 |
7 |
4 |
8 |
9 |
|
3 |
8 |
12 |
6 |
3 |
6 |
12 |
|
4 |
8 |
9 |
6 |
7 |
4 |
3 |
|
5 |
9 |
4 |
7 |
8 |
9 |
1 |
Ответы:
1) L(x*)= 16. 2) L(x*)= 24. 3) L(x*)= 25. 4) L(x*)= 38. 5) L(x*)= 24.
6) L(x*)= 25. 7) L(x*)= 81. 8) L(x*)= 73. 9) L(x*)= 60. 10) L(x*)= 68.