Типовой расчет графов - (реферат)
p>Задача 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 с.
7. Зангвилл У. И. Нелинейное программирование: Пер. с англ. /Под ред. Е. Г. Гольштейна. -М. : Сов радио, 1973. - 312 с.
8. Зуховицкий С. И. , Авдеева Л. И. Линейное и выпуклое программирование (справочное руководство). -М. : Наука, 1964. -348 с.
9. Исследование операций. Методологические основы и математические методы: Пер. с англ. / Под ред. И. М. Макарова, И. М. Бескровного. -М. : Мир, 1981. - Т. 1. -712 с. 10. Исследование операций. Модели и применение: Пер. с англ. / Под ред. И. М. Макарова, И. М. Бескровного. -М. : Мир, 1981. - Т. 1. -712 с.
11. Лазарев В. Г. , Лазарев Ю. В. Динамическое управление потоками информации в сетях связи. -М. : Радио и связь, 1983. - 216 с.
12. Мартин Дж. Системный анализ передачи данных. : Пер с англ. / Под ред. В. С. Лапина. -М. : Мир, 1975. - М. 2. - 431 с.
13. Монаков В. М. , Беляева Э. С. , Краснер Н. Я. Методы оптимизации. Пособие для учителя. -М. : Просвещение, 1978. - 175с.
14. Муртаф Б. Современное линейное программирование: Теория и практика. Пер. с англ. /Под ред. И. А. Станевичуса. - М. : Мир, 1984. - 224 с.
15. Рокафеллор Р. Выпуклый анализ: Пер. с англ. /Под ред. А. Д. Иоффе, В. М. Тихомирова. -М. : Мир, 1973. - 469 с.
16. Сухарев А. Г. , Тимохов А. В. , Федоров В. В. Курс методов оптимизации. - М. : Наука, Физматгиз, 1986. - 326 с.
17. Ху Т. Целочисленное программирование и потоки в сетях: Пер. с англ. /Под ред. А. А. Фридмана. - М. : Мир, 1974. -419 с.
18. Фиакко А. , Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации: Пер. с англ. /Под ред. Е. Г. Гольштейна. -М. :- Мир, 1972. - 240 с.
19. Филлипс Д. , Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. / Под ред. Б. Г. Сушкова. - М. : Мир, 1984. - 496 с.
20. Юдин Д. Б. , Гольштейн Е. Г. Линейное программирование. Теория и конечные методы, - М. :- Физматгиз, 1963. - 775 с.
