Типовой расчет графов
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
>
Таблица Е (исходная). Строки - xi , столбцы - yj.=0
1234512010302022067986301132240487645037683
Дробим по переходу x2 - y1:
Таблица Е21=0+8=8
2345100020100301211144320245435033Таблица 21=0+6=6
1234512010302002132016301132240487645037683Продолжаем по 21:
Дробим по переходу x4 - y1:
Таблица 21Е41=6+4=10
234510002010021320130121115435033Таблица 2141=6+4=10
123451201030200213201301132244320245037683Продолжаем по Е21:
Дробим по переходу x5 - y5:
Таблица Е21Е55=8+2=10
234100010030121421012Таблица Е2155=8+3=11
2345100020100301211443202510123Продолжаем по Е21Е55:
Дробим по переходу x3 - y2:
Таблица Е21Е55Е32=10+0=10
34101004101Далее решение очевидно: 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 с.