21
34
23
43
33
20
29
3
46
33
21
Рішення.
1. Метод потенціалів.
Початковий варіант вибору знайдемо методом максимального елемента (Табл. 5.1).
Крок 1. Максимальним елементом є з 3,4 = 49. Призначимо третьої нареченій четвертого нареченого. Викреслимо третій рядок. p> Крок 2. З невикреслених елементів матриці максимальним елементом є з 5,8 = 49. Призначимо п'ятої нареченій восьмого нареченого. Викреслимо п'ятий рядок. p> Крок 3. З невикреслених елементів матриці максимальним елементом є з 6,2 = 49. Шоста наречена вибирає другого нареченого, викреслюємо шосту рядок. p> Крок 4. З невикреслених елементів матриці максимальним елементом є з 4,3 = 48. Четверта наречена вибирає третього нареченого, викреслюємо четвертий рядок.
Крок 5. З невикреслених елементів матриці максимальним елементом є з 8,6 = 46. Восьма наречена вибирає шостого нареченого, викреслюємо восьмий рядок. p> Крок 6. З невикреслених елементів матриці максимальним елементом є з 7,1 = 45. Сьома наречена вибирає першого нареченого, викреслюємо сьомий рядок. p> Крок 7. З невикреслених елементів матриці максимальним елементом є з 1,4 = 41. Але четвертого нареченого вже вибрала третя наречена, тому в клітку (1,4) помістимо 0. У Надалі, х 1,4 = 0 будемо вважати базисної змінної. Викреслимо четвертий стовпець. p> Крок 8. З невикреслених елементів матриці максимальним елементом є з 1,7 = 38. Перша наречена призначається сьомого нареченому, викреслюємо перший рядок. p> Крок 9. З невикреслених елементів матриці максимальним елементом є з 2,7 = 38. Але сьомий наречений вже вибраний, тому в клітку (2,7) помістимо 0. Х 2,7 = 0 - базисна змінна. Викреслимо сьомий стовпець. p> Крок 10. З невикреслених елементів матриці максимальним елементом є з 2,8 = 36. На восьмий наречений вже вибраний, тому в клітку (2,8) помістимо 0. Х 2,8 = 0 - базисна змінна. Викреслимо восьмий стовпець. p> Крок 11. З невикреслених елементів матриці максимальним елементом є з 2,1 = 35. Але перший наречений вже зайнятий, тому в клітку (2,1) помістимо 0. Х 2,1 = 0 - базисна змінна. Викреслимо перший стовпець. p> Крок 12. З невикреслених елементів матриці максимальним елементом є Х 2,3 = 26. Але третій наречений вже зайнятий, тому в клітку (2,3) помістимо 0. Х 2,3 = 0 - базисна змінна. Викреслимо третій стовпець. p> Крок 13. З невикреслених елементів матриці максимальним елементом є Х 1,5 = 23. Але п'ятий наречений вже зайнятий, тому в клітку (1,5) помістимо 0. Х 1,5 = 0 - базисна змінна. Викреслимо п'ятий стовпець. p> Крок 14. З невикреслених елементів матриці максимальним елементом є з 2,2 = 20. Але другий наречений вже зайнятий, тому в клітку (2,2) помістимо 0. Х 2,2 = 0 - базисна змінна. Викреслимо другий стовпець. p> Крок 15. З невикреслених елементів матриці максимальним елементом є з 2,5 = 17. Друга наречена призначається п'ятого нареченому, викреслюємо другий рядок. p> У табл. 5.1 номер кроку, на якому були отримані базисні змінні, зазначений у дужках. Після 15 кроку отримаємо пробний варіант призначення Х 0 : х 1,7 = х 2,5 = х 3,4 = х 4,3 = х 5,8 = х 6,2 = х 7,1 = х 8,6 = 1. Це означає, що перша наречена виходить заміж за сьомого нареченого, друга наречена за п'ятого нареченого, третя наречена за четвертого нареченого, четверта наречена за третього нареченого, п'ята наречена за восьмого нареченого, шоста наречена за другого нареченого, сьома наречена за першого жениха, восьма наречена за шостого нареченого. br/>
Таблиця 5.1.
В
31
13
11
41
10
17
38
25
0 ( 7 )
0 (13)
1 ( 8)
В
