Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Лабораторная работа 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.