Содержание
- 2. Условия 1. Сеть ориентирована и связана. 2. По крайней мере один узел является источником. 3. По
- 3. Применения: Работа распределительных сетей компании (включает в себя определение плана доставки товара от поставщиков (заводов, и
- 4. Формулирование модели В ориентированной и связанной сети n узлов включая минимум один узел источник и минимум
- 5. Цель: минимизация совокупной стоимости прохождения через сеть, при условии удовлетворении спроса. Суммирование ведется только по существующим
- 6. Необходимо иметь нижнюю границу Lij > 0 для потока по каждой арке i? j. Когда это
- 7. Если значения bi, данные для некоторых приложений нарушают это условие, обычно говорят, что либо предложение либо
- 8. Пример: Сеть распределения. Количества дают значения bi, cij, и uij. Значения bi даны в квадратных скобках
- 9. Задача распределения, сформулированная как задача потока минимальной стоимости.
- 10. Каждая переменная имеет два ненулевых коэффициента, 1 и -1. Эта модель повторяется в каждой задаче о
- 11. СЕТЕВОЙ СИМПЛЕКС-МЕТОД Сетевой симплекс-метод (вариант симплекс-метода) для решения задачи о потоке минимальной стоимости. Он проходит через
- 12. Использование техники верхней границы: для эффективного использования ограничения пропускной способности дуг xij ≤ uij. Таким образом,
- 13. Чтобы отобразить поток xij = uij через удаленную дугу, мы сдвигаем количество потока, идущее от узла
- 14. Скорректированная сеть в случае когда метод верхней границы привел к замене xAB = 10 на xAB
- 15. дугу A? B заменяют на дугу B? A (с величиной потока yAB), для новой дуги назначаем
- 16. Как правило, задача минимальной стоимости потока, включает больше дуг, чем узлов ? функциональные ограничения это небольшая
- 17. Связь между ОД решениями и допустимыми связующими деревьями Самое важное понятие сетевого симплекс-метода - сетевое представление
- 18. Любой полный набор n - 1 базисных дуг образует связующее дерево. ОД решения могут быть получены
- 19. Допустимое связующее дерево: его решение по ограничениям узла удовлетворяет всем другим ограничениям (0 ≤ xij ≤
- 20. Так как значения базисных переменных удовлетворяют ограничению неотрицательности и одному соответствующему ограничению пропускной способностью дуги (xCE
- 21. Исходное допустимое связующее дерево и его решение.
- 22. Выбор введенной переменной Это выбор небазисной переменной, которая при увеличении с нуля улучшит Z самыми быстрыми
- 23. Влияние на поток добавления дуги A? C с потоком θ в исходное допустимое связующее дерево.
- 24. влияние на стоимость добавления дуги A? C с потоком θ к исходному допустимому связующему дереву
- 25. Влияние на Z (общая стоимость потока) от добавления потока θ к дуге A?C : единичная стоимость/раз
- 26. Влияние на стоимость от добавления дуги B? A с потоком к исходному допустимому связующему дереву.
- 27. Добавление этой дуги создает неориентированный цикл BA-AD-DE-CE-BC, поэтому поток увеличивается на θ для дуг A? D
- 28. ∆Z = 2θ + 3θ = 5θ = 5, при θ = 1, поэтому xED –
- 29. Влияние на стоимость добавления дуги E? D с потоком θ в исходное допустимое связующее дерево.
- 30. Нахождение уходящей базисной переменной и следующее ОД решение После выбора вводимой базисной переменной определяется уходящая базисная
- 31. Дуги, поток которых не изменяется на θ (не входят в неориентированный цикл), - только дуга B?C,
- 32. Второе допустимое связующее дерево и его решение.
- 33. Вычисления для выбора вводимой базисной переменной в Итерации 2
- 34. Итерация 2: Начиная с допустимого связующего дерева и учитывая единичную стоимость cij, мы переходим к расчетам
- 35. Третье допустимое связующее дерево и его решение.
- 36. Скорректированная сеть с единичными стоимостями в конце итерации 2.
- 37. Уходящая базисная переменная xCE полученная достижением верхней границы (80). Используя метод верхней границы, xCE заменена на
- 38. Calculations for selecting the entering basic variable for iteration 3
- 39. fourth (and final) feasible spanning tree and its solution.
- 40. Increasing the entering basic variable from zero causes its upper bound to be reached first before
- 41. Calculations for the optimality test at the end of iteration 3
- 42. adjusted network with unit costs at the completion of iteration 3.
- 43. Optimal flow pattern in original network for the Distribution Co. example.
- 45. Скачать презентацию