Реферат: Типовой расчет графов
Вес найденного совершенного паросочетания = 12.
Задача 11 Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины xi и yj).
Таблица Е (исходная). Строки - xi , столбцы - yj. å=0
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 2 | 01 | 03 | 02 | 02 |
| 2 | 06 | 7 | 9 | 8 | 6 |
| 3 | 01 | 1 | 3 | 2 | 2 |
| 4 | 04 | 8 | 7 | 6 | 4 |
| 5 | 03 | 7 | 6 | 8 | 3 |
Дробим по переходу x2 - y1:
Таблица Е21 å=0+8=8
| 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 3 | 01 | 2 | 1 | 1 | 1 |
| 4 | 4 | 3 | 2 | 02 | 4 |
| 5 | 4 | 3 | 5 | 03 | 3 |
Таблица 
21 å=0+6=6
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 2 | 01 | 03 | 02 | 00 | |
| 2 | ¥ | 1 | 3 | 2 | 01 | 6 |
| 3 | 01 | 1 | 3 | 2 | 2 | |
| 4 | 04 | 8 | 7 | 6 | 4 | |
| 5 | 03 | 7 | 6 | 8 | 3 |
Продолжаем по 21:
Дробим по переходу x4 - y1:
Таблица 21Е41 å=6+4=10
| 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 2 | 1 | 3 | 2 | 01 | |
| 3 | 01 | 2 | 1 | 1 | 1 |
| 5 | 4 | 3 | 5 | 03 | 3 |
Таблица 2141 å=6+4=10
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 2 | 01 | 03 | 02 | 00 | |
| 2 | ¥ | 1 | 3 | 2 | 01 | |
| 3 | 01 | 1 | 3 | 2 | 2 | |
| 4 | ¥ | 4 | 3 | 2 | 02 | 4 |
| 5 | 03 | 7 | 6 | 8 | 3 |
Продолжаем по Е21:
Дробим по переходу x5 - y5:
Таблица Е21Е55 å=8+2=10
| 2 | 3 | 4 | ||
| 1 | 00 | 01 | 00 | |
| 3 | 01 | 2 | 1 | |
| 4 | 2 | 1 | 01 | 2 |
Таблица Е2155 å=8+3=11
| 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 3 | 01 | 2 | 1 | 1 | |
| 4 | 4 | 3 | 2 | 02 | |
| 5 | 1 | 01 | 2 | ¥ | 3 |
Продолжаем по Е21Е55:
Дробим по переходу x3 - y2:
Таблица Е21Е55Е32 å=10+0=10
| 3 | 4 | |
| 1 | 01 | 00 |
| 4 | 1 | 01 |
Далее решение очевидно: x1 - y3 и x4 - y4. Это не увеличит оценку.
В итоге имеем совершенное паросочетание с минимальным весом:
Прадерево разбиений:
Литература
1. Грешилов А.А. Как принять наилучшее решение в реальных условиях:-М.:Радио и связь, 1991.-320с.:ил.
2. Беллман Р. Динамическое программирование: Пер. с англ./Под ред. Н.Н. Воробьева.-М.: ИЛ, 1960.-400 с.
3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: Пер с англ./Под ред. А.А. Первозванского.-М.: Наука, 1965.-458 с.
4. Вентцель Е.С. Исследование операций.-М.: Сов. радио, 1972.-551 с.
5. Вильямс Н.Н. Параметрическое программирование в экономике (методы оптимальных решений):-М.:Статистика, 1976.-96с.
6. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании:-М.: Сов радио, 1966.- 524 с.