Экономико-математический практикум

/> задачи о разборчивой невесте. Решить задачу методом потенциалов и венгерским методом.
44







31 13 11 41 10 17 38 25


35 20 26 8 17 14 38 36


12 37 38 49 38 22 10 13


28 21 48 43 44 29 26 12


37 22 39 46 26 20 44 49


22 49 19 2 20 30 45 16


45 27 5 21 30 21 34 23


43 33 20 29 3 46 33 21


Решение.

1. Метод потенциалов.

Начальный вариант выбора найдем методом максимального элемента (Табл. 5.1).

Шаг 1. Максимальным элементом является с3,4=49. Назначим третьей невесте четвертого жениха. Вычеркнем третью строку.

Шаг 2. Из невычеркнутых элементов матрицы максимальным элементом является с5,8=49. Назначим пятой невесте восьмого жениха. Вычеркнем пятую строку.

Шаг 3. Из невычеркнутых элементов матрицы максимальным элементом является с6,2=49. Шестая невеста выбирает второго жениха, вычеркиваем шестую строку.

Шаг 4. Из невычеркнутых элементов матрицы максимальным элементом является с4,3=48. Четвертая невеста выбирает третьего жениха, вычеркиваем четвертую строку.

Шаг 5. Из невычеркнутых элементов матрицы максимальным элементом является с8,6=46. Восьмая невеста выбирает шестого жениха, вычеркиваем восьмую строку.

Шаг 6. Из невычеркнутых элементов матрицы максимальным элементом является с7,1=45. Седьмая невеста выбирает первого жениха, вычеркиваем седьмую строку.

Шаг 7. Из невычеркнутых элементов матрицы максимальным элементом является с1,4=41. Но четвертого жениха уже выбрала третья невеста, поэтому в клетку (1,4) поместим 0. В дальнейшем, х1,4=0 будем считать базисной переменной. Вычеркнем четвертый столбец.

Шаг 8. Из невычеркнутых элементов матрицы максимальным элементом является с1,7=38. Первая невеста назначается седьмому жениху, вычеркиваем первую строку.

Шаг 9. Из невычеркнутых элементов матрицы максимальным элементом является с2,7=38. Но седьмой жених уже выбран, поэтому в клетку (2,7) поместим 0. Х2,7=0 - базисная переменная. Вычеркнем седьмой столбец.

Шаг 10. Из невычеркнутых элементов матрицы максимальным элементом является с2,8=36. На восьмой жених уже выбран, поэтому в клетку (2,8) поместим 0. Х2,8=0 - базисная переменная. Вычеркнем восьмой столбец.

Шаг 11. Из невычеркнутых элементов матрицы максимальным элементом является с2,1=35. Но первый жених уже занят, поэтому в клетку (2,1) поместим 0. Х2,1=0 - базисная переменная. Вычеркнем первый столбец.

Шаг 12. Из невычеркнутых элементов матрицы максимальным элементом является Х2,3=26. Но третий жених уже занят, поэтому в клетку (2,3) поместим 0. Х2,3=0 - базисная переменная. Вычеркнем третий столбец.

Шаг 13. Из невычеркнутых элементов матрицы максимальным элементом является Х1,5=23. Но пятый жених уже занят, поэтому в клетку (1,5) поместим 0. Х1,5=0 - базисная переменная. Вычеркнем пятый столбец.

Шаг 14. Из невычеркнутых элементов матрицы максимальным элементом является с2,2=20. Но второй жених уже занят, поэтому в клетку (2,2) поместим 0. Х2,2=0 - базисная переменная. Вычеркнем второй столбец.

Шаг 15. Из невычеркнутых элементов матрицы максимальным элементом является с2,5=17. Вторая невеста назначается пятому жениху, вычеркиваем вторую строку.

В табл. 5.1 номер шага, на котором были получены базисные переменные, указан в скобках. После 15 шага получим пробный вариант назначения Х0: х1,7=х2,5= х3,4=х4,3=х5,8=х6,2= х7,1=х8,6=1. Это означает, что первая невеста выходит замуж за седьмого жениха, вторая невеста за пятого жениха, третья невеста за четвертого жениха, четвертая невеста за третьего жениха, пятая невеста за восьмого жениха, шестая невеста за второго жениха, седьмая невеста за первого жениха, восьмая невеста за шестого жениха.


Таблица 5.1.






31 13 11 41 10 17 38 25



0(7)

0(13)

1(8)








35 20 26 8 17 14 38 36

0(11)

0(14)

0(12)

1(15)

0(7)

0(10)
12 37 38 49 38 22 10 13



1(1)



28 21 48 43 44 29 26 12


1(4)




37 22 39 46 26 20 44 49







1(2)
22 49 19 2 20 30 45 16

1(3)





45 27 5 21 30 21 34 23

1(6)






43 33 20 29 3 46 33 21





1(5)


Суммарная эффективность, отвечающая полученному варианту выбора равна:

условных единиц эффективности

Вариант выбора проверим на оптимальность. Для этого вычислим потенциалы и оценки.



Отсюда вычислим потенциалы:



Для небазисных переменных вычислим оценки по соответствующей формуле:



И так далее расчеты по соответствующим формулам и данным приведены в таблице 5.2.


Таблица 5.2

Х0

28

13

19

41

10

44

38

29

31 13 11 41 10 17 38 25

0


0(7)

0(13)

1(8)

Оценка1

 -3 0 8

27

4

35 20 26 8 17 14 38 36

7

0(11)

0(14)

0(12)

1(15)

0(7)

0(10)

Оценка2


40
37

8

 12 37 38 49 38 22 10 13




1(1)



Оценка3

 24 -16 -11
-20 30 36 24
29 28 21 48 43 44 29 26 12



1(4)




Оценка4

 29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20






1(2)

Оценка5

 11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)





Оценка6

 42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)






Оценка7

3

 31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2




1(5)

Оценка8

 -6 -11 8 -19 16
7 17

Cреди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисный нуль 03,5 перемещается в клетку (1,7), переменная х1,7 включается в базис, а переменная х3,5 выходит из базиса. Получим новую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарная эффективность равна:

условных единиц эффективности


Таблица 5.3

Х0

28

13

19

41

10

44

38

29

31 13 11 41 10 17 38 25

0


1(7)

0(13)

0(8)

Оценка1

 -3 0 8

27

4

35 20 26 8 17 14 38 36

7

0(11)

0(14)

0(12)

0(15)

1(7)

0(10)

Оценка2


40
37

28

 12 37 38 49 38 22 10 13





1(7)


Оценка3

 44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)




Оценка4

 29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20






1(2)

Оценка5

 11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)





Оценка6

 42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)






Оценка7

3

 31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2




1(5)

Оценка8

 -6 -11 8 -19 16
7 17

Заново вычисляем потенциалы и оценки.


Отсюда вычислим потенциалы:



Для небазисных переменных вычислим оценки в таблице 5.3.

Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Строим цикл пересчета: (8,4), (2,4), (2,2), (8,2),(8,4) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисная переменная х2,2=0 перемещается в клетку (8,4), переменная х8,4 включается в базис, а переменная х2,2 выходит из базиса. (Табл. 5.4).


Таблица 5.4

Х1

28

13

19

41

10

44

38

29

31 13 11 41 10 17 38 25

0


1(7)

0(13)

0(8)

Оценка1

 -3 0 8

27

4

35 20 26 8 17 14 38 36

7

0(11)

0(12)

0(15)

1(7)

0(10)

Оценка2


40
37

28

 12 37 38 49 38 22 10 13





1(7)


Оценка3

 44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)




Оценка4

 29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20






1(2)

Оценка5

 11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)





Оценка6

 42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)






Оценка7

3

 31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2


0(14)

1(5)

Оценка8

 -6 -11 8 -19 16
7 17

Суммарная эффективность не изменилась и равна:

условных единиц эффективности

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.

Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Строим цикл пересчета: (2,4), (2,5), (5,5), (5,2),(2,2) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисная переменная х5,2=0 перемещается в клетку (2,4), переменная х2,4 включается в базис, а переменная х5,2 выходит из базиса. (Табл. 5.5).


Таблица 5.5

Х2

28

13

19

41

10

44

38

29

31 13 11 41 10 17 38 25

0


1(7)

0(13)

0(8)

Оценка1

 -3 0 8

27

4

35 20 26 8 17 14 38 36

7

0(11)

0(12)

0(15)

1(7)

0(10)

Оценка2


40
37

28

 12 37 38 49 38 22 10 13





1(7)


Оценка3

 44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)




Оценка4

 29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20






1(2)

Оценка5

 11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)





Оценка6

 42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)






Оценка7

3

 31 37 -3 40 21 23

43 33 20 29 3 46 33 21
21


0(14)

1(5)

Оценка8

 6 11 20
29
26 29

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.

Отрицательных оценок нет. Назначение Х2 оптимально, обозначим его через Х2*.

Суммарная эффективность, отвечающая полученному варианту назначения равна:

условных единиц эффективности

Назначение Х2 оптимально. Итак, оптимальный вариант назначения имеет вид:

х1,4=1 (первая невеста выберет четвертого жениха),

х2,7=1 (вторая невеста выберет седьмого жениха),

х3,5=1 (третья невеста выбрала пятого жениха),

х4,3=1 (четвертая невеста выбрала третьего жениха),

х5,8=1 (пятая невеста выберет восьмого жениха),

х6,2=1 (шестая невеста выберет второго жениха),

х7,1=1 (седьмая невеста выберет первого жениха),

х8,6=1 (восьмая невеста выберет шестого жениха).

При этом варианте назначений получим максимальную эффективность единиц эффективности.

Венгерский метод.

Предварительный этап. Исходная матрица C:


31 13 11 41 10 17 38 25
35 20 26 8 17 14 38 36
12 37 38 49 38 22 10 13
28 21 48 43 44 29 26 12
37 22 39 46 26 20 44 49
22 49 19 2 20 30 45 16
45 27 5 21 30 21 34 23
43 33 20 29 3 46 33 21

Шаг 1. Обозначим через наибольший элемент столбца матрицы (r1=45, r2=49, r3=48, r4=49, r5=44, r6=46, r7=45, r8=49). Каждый элемент -го столбца вычтем из , результаты вычислений будем помещать на место вычитаемого. Аналогичные преобразования проводим в остальных столбцах. Получим неотрицательную матрицу , в каждом столбце которой есть хотя бы один нуль.


C1 =

14

36

37

8

34

29

7

24

10

29

22

41

27

32

7

13

33

12

10

0

6

24

35

36

17

28

0

6

0

17

19

37

8

27

9

3

18

26

1

0

23

0

29

47

24

16

0

30

0

22

43

28

14

25

11

23

2

16

28

20

41

0

12

25

Шаг 2. Преобразуем матрицу . Для этого обозначим через минимальный элемент строки , который последовательно вычтем из элементов той же строки, результаты поместим на место уменьшаемого. Наименьший элемент первой строки матрицы равен 7. Проведем вычисления для элементов первой строки: (d11=7, d12=29, d13=30, d14=1, d15=27, d16=22, d17=0, d18=17). Такие же вычисления проведем для остальных строк, получим неотрицательную матрицу , в каждом столбце и каждой строке которой есть хотя бы один нуль.


D=

7

29

30

1

27

22

0*

17

3

22

15

34

20

25

0

6

33

12

10

0*

6

24

35

36

17

28

0*

6

0

17

19

37

8

27

9

3

18

26

1

0*

23

0*

29

47

24

16

0

30

0*

22

43

28

14

25

11

23

2

16

28

20

41

0*

12

25

Основной этап. После второго шага предварительного этапа получим неотрицательную матрицу , эквивалентную матрице эффективностей :

П.1. В первом столбце матрицы отметим звездочкой 0*7,1 ,во втором столбце – 06,2 , в третьем столбце – 04,3, в четвертом столбце – 0*3,4 , в шестом столбце – 08,6, в седьмом столбце – 01,7 , в восьмом столбце – 05,8. Нули в пятом столбце – 04,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 04,3,. Число звездочек равно семи, что меньше размерности матрицы (8), переходим к п.2.


D= + + + +
+ + +

7

29

30

1

27

22

0*

17

3

22

15

34

20

25

0’

6

33

12

10

0*

6

24

35

36

17

28

0*

6

0’

17

19

37

 +

8

27

9

3

18

26

1

0*

23

0*

29

47

24

16

0’

30

0*

22

43

28

14

25

11

23

2

16

28

20

41

0*

12

25

ε=2

П.2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находится в четвертой строке пятого столбца 04,5 , во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0'4,5 , 0'2,7 , 0'6,7. Переходим к пункту 3.

П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.

П.2. Незанятых нулей нет, переходим к п.5.

П.5. Среди незанятых элементов находим минимальный, который обозначим через , ε=d3,5=6. Преобразуем матрицу : незанятые элементы уменьшим на 6; дважды занятые увеличим на 6; остальные элементы оставим без изменения. Получим матрицу , в которой имеется один незанятый нуль, переходим к четвертому абзацу п.2.



+ + + +
+ + +

D1=

7

29

24

1

21

22

0*

17

3

22

9

34

14

25

0’

6

 +

33

12

4

0*

0’

24

35

36

23

34

0*

12

0’

23

25

43

 +

8

27

3

3

12

26

1

0*

23

0*

23

47

18

16

0’

30

0*

22

37

28

8

25

11

23

2

16

22

20

35

0*

12

25

П.2. Незанятый нуль находится в третьей строке пятого столбца 03,5 . Помечаем штрихом 0'3,5. Во второй строке седьмого столбца находится нуль со штрихом. Помечаем штрихом 0'2,7 и считаем седьмой столбец незанятым, знак «+» сверху снимаем, а вторую строку объявляем занятой и помечаем знаком «+» справа.



+ + + +
+ + +

D2=

7

29

24

1

21

22

0*

17

3

22

9

34

14

25

0’

6

 +

33

12

4

0*

0’

24

35

36

23

34

0*

12

0’

23

25

43

 +

8

27

3

3

12

26

1

0*

23

0*

23

47

18

16

0’

30

0*

22

37

28

8

25

11

23

2

16

22

20

35

0*

12

25

П.5. Переходим к пункту 2. Помечаем звездочкой 0*6,5, штрихом 0'8,3, 0'2,7. В третьей нет , следовательно, переходим к пункту 4, ε=d6,4=7 после преобразований, получим матрицу D3



 + + + +
+ + +

D3=

7

29

24

1

21

22

0*

17

3

22

9

34

14

25

0’

6

 +

33

12

4

0*

0’

24

35

36

23

34

0*

12

0’

23

25

43

 +

8

27

3

3

12

26

1

0*

23

0*

23

47

18

16

0’

30

0*

22

37

28

8

25

11

23

2

16

22

20

35

0*

12

25


П.4. Строим цепочку из нулей. Начиная от только что отмеченного штрихом нуля (0’2,7), идем по строке до 5,2 цепочка состоит из двух элементов Ц: 07,2, 0’5,2. В матрице такие цепочки обозначают так . После преобразования получим новый набор нулей со звездочкой (), который содержит на одну звездочку больше, чем предыдущий набор.

Проводим следующие пересчеты.


 +

+

 +

+ + +

D3=

 25 0 0* 27 19 16 20 32 +

3 43 2 7 23 14 5 0* +

6 32 0 23 20 5 18 7 +

0* 36 10

0

 0 5 2 17

0

0'

 9 19 5 45 19 12 +

15 24 10 7

0’

 0* 5 5

22 0* 13 8 9 15 22 9

6 32 0 20 7 34 0* 8 +

Процесс окончен, так как число нулей со звездочкой равно размерности матрицы эффективности.



Оптимальный вариант выбора (1,2)(2,7)(3,8)(4,1)(5,4),(6,6),(7,5),(8,3). Это значит, что первая невеста выберет второго жениха, вторая невеста седьмого жениха, третья –восьмого, четвертая первого, пятая четвертого, шестая – шестого, седьмая невеста пятого жениха, а восьмая невеста выберет третьего жениха.

При этом максимальная суммарная эффективность (суммарная продолжительность жизни всех семей) равна: (единиц эффективности)