I этап. Условная оптимизация
1-й шаг: k = 1. На первом шаге с задаваемым сечением , из состояний и возможен только один вариант перехода вконечное состояние . Поэтому в вершинах и записываемсоответственно издержки 12 и 9. Ребра и обозначаемстрелкой, направленной в вершину - . 2-й шаг: k = 2. Второй шаг оптимизации задается сечением по вершинам . Из состояний и , возможен единственный переход в вершины , и соответственно, поэтому в вершинах и записываем суммарные издержки 25 и 19 на первых двух шагах перехода в конечное состояние . Из вершины возможны два варианта перехода: в вершинy или вершину . При переходе сумма издержек составляет 12 + 10 = 22, на переходе сумма составляет 13 + 9 = 22. Из двух вариантов суммарных издержек выбираем наименьшую (22) и обозначаем стрелкой условно оптимальный переход , . 3-й шаг: k = 3. На третьем шаге сечение проходит через вершины , , , . Из вершин и возможен единственный переход в вершины соответственно. Суммарные издержки для состояния равны 19 + 11 = 30, для состояния равны 25+11=36. Из вершины возможны два варианта перехода: в вершину издержки равны 25 + 11 = 36; в вершину 22 + 14 = 36. Для вершины возможен переход в вершину (22 + 15 = 37) и в вершину (19 + 19 = 38). Выбираем для вершин и наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 4-й шаг: k = 4. На четвертом шаге сечение проходит через вершины , , , , Из вершин и возможен единственный переход в вершины соответственно. Суммарные издержки для состояния равны 30 + 19 = 49, для состояния равны 36+9=45. Из вершины возможны два варианта перехода: в вершину издержки равны 36 + 12 = 48; в вершину 36 + 15 = 51. Для вершины возможен переход в вершину (36 + 13 = 49) и в вершину (37 + 18 = 55). Выбираем для вершин и наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. Для вершины возможен переход в вершину (30 + 18 = 48) и в вершину (37 + 14 = 51). Выбираем для вершины наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 5-й шаг: k = 5. На пятом шаге сечение проходит через вершины , , , , Из вершины возможен единственный переход в вершину . Суммарные издержки для состояния равны 45 + 8 = 53. Из вершины возможны два варианта перехода: в вершину издержки равны 45+13 = 58; в вершину 48 + 14 = 62. Для вершины возможен переход в вершину (48 + 14 = 62) и в вершину (49 + 21 = 70). Выбираем для вершин и наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. Для вершины возможен переход в вершину (48+ 13 = 61) и в вершину (49 + 12 = 61). Выбираем для вершины наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. Для вершины возможен переход в вершину (49 + 17 = 66) и в вершину (48 + 16 = 64). Выбираем для вершины наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 6-й шаг: k = 6. На шестом шаге сечение проходит через вершины , , , , Из вершины возможен единственный переход в вершину . Суммарные издержки для состояния равны 53 + 10 = 63. Из вершины возможны два варианта перехода: в вершину издержки равны 53+14 = 67; в вершину 58 + 13 = 71. Для вершины возможен переход в вершину (58 + 12 = 70) и в вершину (62 + 20 = 82). Выбираем для вершин и наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. Для вершины возможен переход в вершину (61+ 12 = 73) и в вершину (62 + 11 = 73). Выбираем для вершины наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. Для вершины возможен переход в вершину (64 + 16 = 80) и в вершину (61+ 13 = 74). Выбираем для вершины наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 7-й шаг: k = 7. На седьмом шаге сечение проходит через вершины , , , . Из вершины возможен переход в вершину (63 + 15 = 78) и в вершину (67 + 12 = 79). Для вершины возможен переход в вершину (67 + 13 = 80) и в вершину (70 + 19 = 89). Для вершины возможен переход в вершину (70 + 13 = 83) и в вершину (73 + 12 = 85). Для вершины возможен переход в вершину (73 + 15 = 88) и в вершину (74 + 14 = 88). Выбираем для вершин , , , наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 8-й шаг: k = 8. На восьмом шаге сечение проходит через вершины , , . Из вершины возможен переход в вершину (78 + 11 = 89) и в вершину (80 + 18 = 98). Для вершины возможен переход в вершину (80 + 10 = 90) и в вершину (83 + 10 = 93). Для вершины возможен переход в вершину (83 + 12 = 95) и в вершину (88 + 10 = 98). Выбираем для вершин , , наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 9-й шаг: k = 9. На девятом шаге сечение проходит через вершины , . Из вершины возможен переход в вершину (89 + 10 = 99) и в вершину (90 + 10 = 100). Для вершины возможен переход в вершину (90 + 10 = 100) и в вершину (95 + 15 = 110). Выбираем для вершин , наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход. 10-й шаг: k = 10. На девятом шаге сечение проходит через точку . Из вершины возможен переход в вершину (99 + 9 = 108) и в вершину (100 + 13 = 113). Минимальные возможные суммарные издержки равны 108. В результате получим граф условно оптимальных переходов, представленный на рис. 2.1.1. Рис 2.1.1. Сетевая модель связи расходов операций
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (213)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |