Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Задача о потоке минимальной стоимости

Содержание

Условия1. Сеть ориентирована ​​и связана. 2. По крайней мере один узел является источником. 3. По крайней мере один узел является стоком. 4. Остальные узлы – передающие узлы. 5. Поток дуги допускается в направлении, указанном стрелкой, максимальный
Задача о потоке минимальной стоимостиСтоит на центральном месте среди моделей сетевой оптимизации. Условия1. Сеть ориентирована ​​и связана. 2. По крайней мере один узел является Применения:Работа распределительных сетей компании (включает в себя определение плана доставки товара от Формулирование моделиВ ориентированной и связанной сети n узлов включая минимум один узел Цель: минимизация совокупной стоимости прохождения через сеть, при условии удовлетворении спроса. Суммирование Необходимо иметь нижнюю границу Lij > 0 для потока по каждой арке Если значения bi, данные для некоторых приложений нарушают это условие, обычно говорят, Пример: Сеть распределения. Количества дают значения bi, cij, и uij. Значения bi Задача распределения, сформулированная как задача потока минимальной стоимости. Каждая переменная имеет два ненулевых коэффициента, 1 и -1. Эта модель повторяется СЕТЕВОЙ СИМПЛЕКС-МЕТОДСетевой симплекс-метод (вариант симплекс-метода) для решения задачи о потоке минимальной стоимости. Использование техники верхней границы: для эффективного использования ограничения пропускной способности дуг xij Чтобы отобразить поток xij = uij через удаленную дугу, мы сдвигаем количество Скорректированная сеть в случае когда метод верхней границы привел к замене xAB дугу A? B заменяют на дугу B? A (с величиной потока yAB), Как правило, задача минимальной стоимости потока, включает больше дуг, чем узлов ? Связь между ОД решениями и допустимыми связующими деревьями Самое важное понятие сетевого Любой полный набор n - 1 базисных дуг образует связующее дерево. ОД Допустимое связующее дерево: его решение по ограничениям узла удовлетворяет всем другим ограничениям Так как значения базисных переменных удовлетворяют ограничению неотрицательности и одному Исходное допустимое связующее дерево и его решение. Выбор введенной переменной Это выбор небазисной переменной, которая при увеличении с нуля Влияние на поток добавления дуги A? C с потоком θ в исходное допустимое связующее дерево. влияние на стоимость добавления дуги A? C с потоком θ к исходному допустимому связующему дереву Влияние на Z (общая стоимость потока) от добавления потока θ к дуге Влияние на стоимость от добавления дуги B? A с потоком к исходному допустимому связующему дереву. Добавление этой дуги создает неориентированный цикл BA-AD-DE-CE-BC, поэтому поток увеличивается на θ ∆Z = 2θ + 3θ = 5θ = 5, при θ = Влияние на стоимость добавления дуги E? D с потоком θ в исходное допустимое связующее дерево. Нахождение уходящей базисной переменной и следующее ОД решение  После выбора вводимой Дуги, поток которых не изменяется на θ (не входят в неориентированный цикл), Второе допустимое связующее дерево и его решение. Вычисления для выбора вводимой базисной переменной в Итерации 2 Итерация 2: Начиная с допустимого связующего дерева и учитывая единичную стоимость cij, Третье допустимое связующее дерево и его решение. Скорректированная сеть с единичными стоимостями в конце итерации 2. Уходящая базисная переменная xCE полученная достижением верхней границы (80). Используя метод верхней Calculations for selecting the entering basic variable for iteration 3 fourth (and final) feasible spanning tree and its solution. Increasing the entering basic variable from zero causes its upper bound to Calculations for the optimality test at the end of iteration 3 adjusted network with unit costs at the completionof iteration 3. Optimal flow pattern in original network for theDistribution Co. example. This means that the current BF solution passed the optimality test, so
Слайды презентации

Слайд 2 Условия
1. Сеть ориентирована ​​и связана. 2. По крайней мере

Условия1. Сеть ориентирована ​​и связана. 2. По крайней мере один узел

один узел является источником. 3. По крайней мере один узел

является стоком. 4. Остальные узлы – передающие узлы. 5. Поток дуги допускается в направлении, указанном стрелкой, максимальный поток задается пропускной способностью дуги. Поток в двух направлениях (пары дуг направлены в противоположные стороны). 6. Сеть имеет достаточно дуг с достаточной пропускной способностью, чтобы обеспечить прохождение потока из источника в сток. 7. Стоимость потока через каждую дугу пропорционально количеству потока, где известна стоимость на единицу потока. 8. Цель: минимизация совокупной стоимости прохождения через сеть, при условии удовлетворения спроса. (Альтернативная цель: максимизировать общую прибыль).

Слайд 3 Применения:
Работа распределительных сетей компании (включает в себя определение

Применения:Работа распределительных сетей компании (включает в себя определение плана доставки товара

плана доставки товара от поставщиков (заводов, и т.д.) к

промежуточным складам, а затем к клиентам.

Слайд 4 Формулирование модели
В ориентированной и связанной сети n узлов

Формулирование моделиВ ориентированной и связанной сети n узлов включая минимум один

включая минимум один узел источник и минимум один узел

сток. Переменные решения:
Xij = поток через дугу i? j,
Данная информация включает:
cij = стоимость на единицу потока через i? j,
uij = пропускная способность по дуге i? j,
bi = поток сети из узла i.
Значение bi зависит от природы узла i, где:
bi > 0 если узел i источник,
bi < 0 если узел i сток,
bi = 0 если узел i – передающий узел.

Слайд 5 Цель: минимизация совокупной стоимости прохождения через сеть, при

Цель: минимизация совокупной стоимости прохождения через сеть, при условии удовлетворении спроса.

условии удовлетворении спроса. Суммирование ведется только по существующим дугам,

формулировка задачи линейного программирования:
Минимизировать

согласно
Для каждого узла i, и 0 ≤ xij ≤ uij, для каждой дуги i?j. Первое суммирование в ограничениях узла представляет общий поток из узла i, второе суммирование представляет общий поток в узел i, разница – это поток сети, исходящий из этого узла.

Слайд 6 Необходимо иметь нижнюю границу Lij > 0 для

Необходимо иметь нижнюю границу Lij > 0 для потока по каждой

потока по каждой арке i? j. Когда это имеет

место, используем трансляцию переменных xij’= xij- Lij, with xij’+ Lij подставленных для xij в модель, чтобы преобразовать модель обратно в упомянутый формат с ограничениями неотрицательности. Нет гарантии, что задача будет иметь допустимое решение, частично это зависит от того, какие дуги представлены в сети и от пропускных способностей дуг. Главное условие:


Свойство допустимых решений: необходимое условие чтобы задача потока с минимальной стоимостью с движением стоимости имела допустимое решение: общий поток генерируемый в источниках = общему потоку в узлах стоках.

Слайд 7 Если значения bi, данные для некоторых приложений нарушают

Если значения bi, данные для некоторых приложений нарушают это условие, обычно

это условие, обычно говорят, что либо предложение либо спрос

представляют собой верхние границы, а не точные величины. Нужно добавить либо фиктивный сток чтобы поглотить избыточное предложение (при cij = 0 к этому узлу добавляются дуги от всех источников) или должен быть добавлен фиктивный источник, чтобы создать поток для избыточного спроса (при
cij = 0 от этого узла добавляются дуги ко всем узлам стокам). Для многих приложений, bi и uij будут иметь целые значения, и реализация задачи потребует, чтобы количество потока xij было целым числом. Этот результат гарантирован и без введения ограничения целочисленности для переменные благодаря следующему свойству: Свойство целочисленного решения : для задачи минимальной стоимости потока, где каждая bi и uij имеют целые значения, все базисные переменные в каждом базисном допустимом решении (в том числе оптимальном) также имеют целые значения.

Слайд 8 Пример: Сеть распределения. Количества дают значения bi, cij,

Пример: Сеть распределения. Количества дают значения bi, cij, и uij. Значения

и uij. Значения bi даны в квадратных скобках около

узлов, так что узлы источники (поставщики) (bi > 0) , A и B (два завода компании), узлы стоки (bi <0) - D и E (два склада), и один передающий узел
(bi = 0) - C (распределительный центр). Значения cij показаны рядом с дугами. Все дуги, за исключением двух имеют пропускные способности, превышающие суммарный поток (90), поэтому uij = ∞ для всех практических целей. Две дуги-исключения A? B, где
uAB = 10, и дуга C? E, для которой uCE = 80. Модель линейного программирования:
Минимизировать Z = 2xAB + 4xAC + 9xAD + 3xBC + xCE + 3xDE + 2xED,
согласно
xAB + xAC + xAD = 50
-xAB + xBC = 40
- xAC - xBC + xCE = 0
- xAD + xDE - xED = - 30
-xCE - xDE + xED = - 60 и xAB ≤ 10, xCE ≤ 80, xij ≥ 0.

Слайд 9 Задача распределения, сформулированная как задача потока минимальной стоимости.

Задача распределения, сформулированная как задача потока минимальной стоимости.

Слайд 10 Каждая переменная имеет два ненулевых коэффициента,
1 и

Каждая переменная имеет два ненулевых коэффициента, 1 и -1. Эта модель

-1. Эта модель повторяется в каждой задаче о минимальной

стоимости потока, эта особая структура приводит к целочисленному свойству решений. Любое ограничение узла является избыточным (так как сумма всех этих ограничений уравнений дает нули с обеих сторон (предполагая, что допустимые решения существуют, так что сумма значений bi сводится к нулю), так что отрицательные уравнения = сумма остальных уравнений. С помощью всего лишь n – 1 ограничений узла (не избыточных), эти уравнения дают только n - 1 базисные переменные для ОД решения. Сетевой симплекс-метод рассматривает xij ≤ uij ограничения как зеркальное отражение ограничений неотрицательности, поэтому базисные переменные общего числа = n –1 ? прямое соответствие между n - 1 дугами остового дерева и
n - 1 базисными переменными.

Слайд 11 СЕТЕВОЙ СИМПЛЕКС-МЕТОД
Сетевой симплекс-метод (вариант симплекс-метода) для решения задачи

СЕТЕВОЙ СИМПЛЕКС-МЕТОДСетевой симплекс-метод (вариант симплекс-метода) для решения задачи о потоке минимальной

о потоке минимальной стоимости. Он проходит через те же

основные шаги при каждой итерации: поиск введенных базисных переменных, определение уходящих базисных переменных, и нахождение нового ОД решения, чтобы перейти от текущего ОД решения к смежному - лучшему (выполняет эти шаги используя специальную структуру сети без необходимости использования симплекс таблицы).

Слайд 12 Использование техники верхней границы: для эффективного использования ограничения

Использование техники верхней границы: для эффективного использования ограничения пропускной способности дуг

пропускной способности дуг xij ≤ uij. Таким образом, вместо

того, чтобы рассматривать эти ограничения как функциональные ограничения, они рассматриваются, как ограничения неотрицательности. Поэтому, они рассматриваются т только тогда, когда определена уходящая базисная переменная. Введненая базисная переменная увеличивается от нуля, уходящая базисная переменная - первая базисная переменная, которая достигает либо нижней границы (0) либо верхней границы (uij).Небазисная переменная на ее верхней границе xij = uij заменяется на xij = uij – yij, так yij = 0 становится небазисной переменной. yij имеет свою важную интерпретацию в сети. Всякий раз, когда yij становится базисной переменной со строго положительным значением (≤ uij), это значение можно рассматривать как поток от узла j к узлу i (в "неправильном" направлении по дуге i ? j), что, в действительности отменяет количество ранее назначенного потока
(xij = uij) от узла i к узлу j. Таким образом, когда xij uij заменяется на xij = uij – yij, мы также заменяем реальную дугу i? j на обратную дугу j? i, где эта новая дуга имеет пропускную способность uij(максимальное количество потока xij = uij, которое можно отменить) и единичную стоимость cij (так как каждая единица отмененного потока сохраняет cij).

Слайд 13 Чтобы отобразить поток xij = uij через удаленную

Чтобы отобразить поток xij = uij через удаленную дугу, мы сдвигаем

дугу, мы сдвигаем количество потока, идущее от узла i

к узлу j путем уменьшения bi на uij и увеличивая bj на uij. Если yij станет уходящей базисной переменной, достигнув верхней границы, тогда yij = uij заменяется на yij = uij - xij где xij = 0 – новая небазисная переменная, поэтому процесс описанный выше будет обратным (заменяем дуги j? i на дугу i? j и т.д.) до исходной конфигурации.
Сетевой симплекс метод генерирует последовательность ОД решений, предположим, что xAB стала базисной уходящей переменной для некоторой итерации, достигнув верхней границы 10. Следовательно, xAB = 10 заменяется на xAB = 10 - yAB, и yAB = 0 становится новой небазисной переменной.

Слайд 14 Скорректированная сеть в случае когда метод верхней границы

Скорректированная сеть в случае когда метод верхней границы привел к замене

привел к замене xAB = 10 на xAB =

10 - yAB.

Слайд 15 дугу A? B заменяют на дугу B? A

дугу A? B заменяют на дугу B? A (с величиной потока

(с величиной потока yAB), для новой дуги назначаем пропускную

способность 10 и единичную стоимость -2. Для того, чтобы учесть xAB = 10, мы также уменьшаем bA с 50 до 40 и увеличиваем bB с 40 до 50. Начинаем с yAB = 0 (xAB = 10) в качестве небазисной переменной. Следующая итерация покажет, что xCE достигла верхней границы 80 и заменяется на xCE = 80 - yCE, и так далее, а затем на следующей итерации yAB достигает верхней границы 10. Все эти операции выполняются непосредственно в сети, поэтому нам не нужно использовать ярлыки xij или yij для потоков дуги или отслеживать, какие дуги являются реальными, а какие - обратными (кроме случаев, когда мы записываем окончательное решение) . Использование метода верхней границы оставляет ограничения узла (поток из - поток в = bi) только в качестве функциональных ограничений.

Слайд 16 Как правило, задача минимальной стоимости потока, включает больше

Как правило, задача минимальной стоимости потока, включает больше дуг, чем узлов

дуг, чем узлов ? функциональные ограничения это небольшая часть

того, что было бы, если бы были включены ограничения пропускных способностей дуг. Время для вычисления симплекс-методом быстро увеличивается с увеличением числа функциональных ограничений, но с ростом числа переменных (или числа границ ограничений на эти переменные)увеличивается достаточно медленно. Метод верхней границы обеспечивает огромную экономию времени вычислений. Этот метод не используется для задач минимальной стоимости потока, где нет ограничений пропускных способностей дуг.


Слайд 17 Связь между ОД решениями и допустимыми связующими деревьями Самое

Связь между ОД решениями и допустимыми связующими деревьями Самое важное понятие

важное понятие сетевого симплекс-метода - сетевое представление ОД решений.

С n узлами, каждое ОД решение имеет (n-1) базисную переменную, где каждая базисная переменная xij представляет поток через дугу i? j. Эти (n - 1) дуги называют базисными дугами. (Дуги, соответствующие небазисным переменным xij = 0 или yij = 0 называют небазисными дугами). Базисные дуги никогда не образуют неориентированных циклов (это свойство обеспечивает то, что полученные решения будут являться средним другой пары допустимых решений, что нарушает одно из общих свойств ОД решений).

Слайд 18 Любой полный набор n - 1 базисных дуг

Любой полный набор n - 1 базисных дуг образует связующее дерево.

образует связующее дерево. ОД решения могут быть получены путем

решения связующих деревьев следующим образом: 1. Для дуг, не входящих в связующее дерево (небазисные дуги), соответствующими переменными (xij or yij) = 0. 2. Для дуг в связующем дереве (базисные дуги), решим для соответствующих переменных (xij or yij) систему линейных уравнений, предоставляемую ограничениями узла. (Сетевой симплекс метод находит новое ОД решение, начиная с текущего, гораздо более эффективно, без решения этой системы уравнений с нуля). В процессе решения не принимаем во внимание ограничения неотрицательности и ограничения пропускных способностей дуг для базисных переменных ? полученное связующее дерево может быть или не быть допустимо в отношении этих ограничений, что приводит к следующему определению.

Слайд 19 Допустимое связующее дерево:
его решение по ограничениям узла

Допустимое связующее дерево: его решение по ограничениям узла удовлетворяет всем другим

удовлетворяет всем другим ограничениям (0 ≤ xij ≤ uij

or 0 ≤ yij ≤ uij). Фундаментальная теорема сетевого симплекс-метода: базисные решения – решения связующего дерева (и наоборот), и эти ОД решения являются решениями для допустимых связующих деревьев (и наоборот). Сеть, получившаяся в результаты замене xAB = 10 by xAB = 10 - yAB. Одно связующее дерево для этой сети является то, где дуги A? D, D? E, C ? E, и B ? C. в качестве базисных дуг. Процесс нахождения решений связующего (остовного) дерева: Слева находятся ограничения узла после замены xAB на 10 - yAB , где базисные переменные выделены жирным шрифтом. Справа, начиная сверху и двигаясь вниз, шаги для установки или вычисления значений переменных.

Слайд 20




Так как значения базисных переменных удовлетворяют

Так как значения базисных переменных удовлетворяют ограничению неотрицательности и одному

ограничению неотрицательности и одному соответствующему ограничению пропускной способностью дуги

(xCE ≤ 80), связующее дерево будет допустимым связующим деревом, так что у нас есть ОД решение. Мы используем это решение в качестве исходного ОД решения. Числа данные рядом с дугами представляют потоки (значения xij), а не едигичную стоимость cij. (Скобки вокруг потоков, а не вокруг стоимости).

Слайд 21 Исходное допустимое связующее дерево и его решение.

Исходное допустимое связующее дерево и его решение.

Слайд 22 Выбор введенной переменной Это выбор небазисной переменной, которая при

Выбор введенной переменной Это выбор небазисной переменной, которая при увеличении с

увеличении с нуля улучшит Z самыми быстрыми темпами. Это

делается без симплекс таблицы. Небазисная переменная xAC в нашем исходном ОД решении, т. е. не небазисная дуга A? C. Повышение xAC от нуля до некоторого значения θ означает, что дуга A? C с потоком θ должна быть добавлена к сети. Добавление небазисной дуги к связующему дереву всегда создает уникальный неориентированный цикл (AC–CE–DE–AD).Поток увеличился на θ для других дуг, которые имеют то же направление, что и A ? C в цикле (дуга C? E), в то время как поток сети уменьшается на θ для других дуг, направление которых противоположно A? C в цикле (дуги D? E и A? D). Последний, новый поток отменяет поток θ в противоположном направлении. На дуги , которые не в цикле (дуга B ? C) новом поток не повлияет. (влияние изменения значения xAC на другие переменные в решении получены для начального допустимого связующего дерева).

Слайд 23 Влияние на поток добавления дуги A? C с

Влияние на поток добавления дуги A? C с потоком θ в исходное допустимое связующее дерево.

потоком θ в исходное допустимое связующее дерево.


Слайд 24 влияние на стоимость добавления дуги A? C с

влияние на стоимость добавления дуги A? C с потоком θ к исходному допустимому связующему дереву

потоком θ к исходному допустимому связующему дереву


Слайд 25 Влияние на Z (общая стоимость потока) от добавления

Влияние на Z (общая стоимость потока) от добавления потока θ к

потока θ к дуге A?C : единичная стоимость/раз ,

изменения в потоке для каждой дуги. Общий прирост Z ∆Z = cACθ + cCEθ + cDE(-θ) + cAD(-θ) = 4θ + θ -3θ -9θ= -7θ.
Присваивание θ = 1 дает скорость изменения Z по мере увеличения xAC, ∆Z = -7, когда θ = 1. Цель: минимизация Z, большая скорость уменьшения Z за счет увеличения xAC очень желательна, поэтому xAC становится главным кандидатом чтобы быть введенной базисной основной переменной. Прежде чем сделать окончательный выбор вводимых базисных переменных, тот же анализ, проводится для других небазисных переменных. Единственные другие небазисные переменные yAB и xED соответствуют двум другим небазисным дугам B? A и E? D.


Слайд 26 Влияние на стоимость от добавления дуги B? A

Влияние на стоимость от добавления дуги B? A с потоком к исходному допустимому связующему дереву.

с потоком к исходному допустимому связующему дереву.


Слайд 27 Добавление этой дуги создает неориентированный цикл BA-AD-DE-CE-BC, поэтому

Добавление этой дуги создает неориентированный цикл BA-AD-DE-CE-BC, поэтому поток увеличивается на

поток увеличивается на θ для дуг A? D и

D? E , но уменьшается на θ для двух дуг в противоположном направлении, C? E иB? C. Эти увеличения потока, θ и-θ, являются множителями для значений cij . Z = -2θ + 9θ + 3θ + 1(-θ) + 3(-θ) = 6θ =6, при θ = 1. Z увеличивается, а не уменьшается, когда yAB (поток через обратную дугу B A) увеличивается от нуля, исключает эту переменную в качестве кандидата для вводимой базисной переменной. (Повышение yAB от нуля означает уменьшение xAB, поток через дугу A? B, от его верхней границы 10). Аналогичный результат получен для последней небазисной дуги E? D. Добавление этой дуги с потоком θ к исходному допустимому связующему дереву создает неориентированный цикл ED-DE, так что поток увеличивается на θ для дуги D? E, ни на какие другие дуги это больше не влияет.

Слайд 28 ∆Z = 2θ + 3θ = 5θ =

∆Z = 2θ + 3θ = 5θ = 5, при θ

5, при θ = 1, поэтому xED – кандидат

на вводимые базисные переменные.



Таким образом, отрицательное значение xAC означает, что xAC становится введенной базисной переменной для первой итерации. Если есть больше, чем одна небазисная переменная с отрицательным значением Z, то выбираем переменную с большим абсолютным значением. (Если нет небазисных переменных с отрицательным значением Z, текущее ОД решение является оптимальным). Вместо выявления неориентированных циклов и т.д., сетевой симплекс методом получает эти значения Z с помощью алгебраической процедуры, и является более эффективным (особенно для больших сетей).

Слайд 29 Влияние на стоимость добавления дуги E? D с

Влияние на стоимость добавления дуги E? D с потоком θ в исходное допустимое связующее дерево.

потоком θ в исходное допустимое связующее дерево.


Слайд 30 Нахождение уходящей базисной переменной и следующее ОД решение

Нахождение уходящей базисной переменной и следующее ОД решение После выбора вводимой

После выбора вводимой базисной переменной определяется уходящая базисная переменная

и следующее ОД решение. Итерация 1: так как xAC является вводимой базисной переменной, поток θ через дугу A? C должен быть увеличен с нуля, насколько это возможно, пока одна из базисных переменных достигает своей нижней грани (0) или верхней границы (uij) . Для тех дуг, поток которых увеличивается с θ (дуги A? C и C? E), необходимо учитывать только верхние границы (uAC =∞ and uCE = 80 ) :




Для тех дуг, поток которых уменьшается с θ (дуги D? E и A? D), необходимо учитывать только нижнюю границу 0 :

Слайд 31 Дуги, поток которых не изменяется на θ (не

Дуги, поток которых не изменяется на θ (не входят в неориентированный

входят в неориентированный цикл), - только дуга B?C, могут

быть проигнорированы, так как по мере увеличения θ граница не будет достигнута. Для пяти дуг, xDE должна быть уходящей базисной переменной, поскольку она достигает границы наименьшего значения θ (10). Задаем θ = 10 , это дает поток через базисные дуги в следующем ОД решении:



Если уходящая базисная переменная достигла верхней границы, то нужна корректировка метода верхней грани. Так как была достигнута нижняя граница 0, больше ничего не нужно делать.



Слайд 32 Второе допустимое связующее дерево и его решение.

Второе допустимое связующее дерево и его решение.

Слайд 33 Вычисления для выбора вводимой базисной переменной в Итерации

Вычисления для выбора вводимой базисной переменной в Итерации 2

Слайд 34 Итерация 2: Начиная с допустимого связующего дерева и

Итерация 2: Начиная с допустимого связующего дерева и учитывая единичную стоимость

учитывая единичную стоимость cij, мы переходим к расчетам для

выбора вводимой базисной переменной. Во второй колонке таблицы указан уникальный неориентированный цикл, который создается путем добавления небазисных дуг в первой колонке для этого связующего дерева, и 3-я колонка показывает влияние на затраты, вызванные изменениями в потоках в этом цикле из-за добавления потока θ = 1 к неосновной дуге. Дуга ED имеет наибольшее отрицательное значение ∆Z, поэтому xED – вводимая базисная переменная. Поток θ через арку E ? D сделан как можно большим, в то же время удовлетворяя следующим границам потока:






Так как xCE накладывает наименьшие верхние границы (20) на θ, xCE становится уходящей базисной переменной. Назначение θ = 20 в приведенных выше выражениях для xED, xAD, иxAC ? поток через базисные дуги для следующего ОД решения (при xBC = 50 не зависит от θ).

Слайд 35 Третье допустимое связующее дерево и его решение.

Третье допустимое связующее дерево и его решение.

Слайд 36 Скорректированная сеть с единичными стоимостями в конце итерации

Скорректированная сеть с единичными стоимостями в конце итерации 2.

Слайд 37 Уходящая базисная переменная xCE полученная достижением верхней границы

Уходящая базисная переменная xCE полученная достижением верхней границы (80). Используя метод

(80). Используя метод верхней границы, xCE заменена на 80

- yCE, где yCE = 0 - новая небазисная переменная. Исходная дуга C? E с cCE = 1 and uCE = 80 заменяется на обратную дугу E?C с cEC1 и uEC = 80 . Значения bE и bC также корректируется путем прибавления 80 к bE и вычитания 80 из bC. Получившаяся скорректированная сеть, небазисные дуги показаны пунктирными линиями и числа около всех дуг единичная стоимость. Итерация 3: расчеты приводят к выбору yAB (обратная дуга B? A) в качестве вводимой базисной переменной, как показано в таблице. Затем добавить столько потка через дугу B? A сколько это возможно, удовлетворяя границам потока ниже:




Наименьшая верхняя граница (10) на θ накладывается yAB, так что эта переменная становится уходящей базисной переменной. Устанавливая θ = 10 в этих выражений для xAC и xBC (наряду с неизменными значениями xAC = 10 и xED = 20), получим ОД следующее решение. Как и 2-го, оставив основной переменной (ЯБ), полученные здесь переменная достигнув верхней границы.Ввод основных переменных ЯБ также стал оставляя основную переменную на той же итерации!
Smallest upper bound (10) on θ is imposed by yAB, so this variable becomes the leaving basic variable. Setting θ = 10 in these expressions for xAC and xBC (along with unchanged values of xAC = 10 and xED = 20) then yields the next BF solution. As with iteration 2, the leaving basic variable (yAB) obtained here by the variable reaching its upper bound. The entering basic variable yAB also became the leaving basic variable on the same iteration!

Слайд 38 Calculations for selecting the entering basic variable for

Calculations for selecting the entering basic variable for iteration 3

iteration 3


Слайд 39 fourth (and final) feasible spanning tree and its

fourth (and final) feasible spanning tree and its solution.

solution.


Слайд 40 Increasing the entering basic variable from zero causes

Increasing the entering basic variable from zero causes its upper bound

its upper bound to be reached first before any

other basic variables reach a bound. Arc B? A now needs to be replaced by a reverse arc A? B (because of the leaving basic variable reaching an upper bound) already is a reverse arc! The reverse arc for a reverse arc is simply the original real arc. Therefore, the arc B? A (with cBA = 2 and uBA = 10) is replaced by arc A? B (with cAB = -2 and uAB = 10), which is the arc between nodes A and B in original network, and a generated net flow of 10 is shifted from node B (bB=50? 40) to node A (bA 40? 50). Variable yAB =10 is replaced by 10 - xAB, with xAB = 0 as the new nonbasic variable.
Passing the Optimality Test: Algorithm will find the next entering basic variable with the usual calculations. However, none of the nonbasic arcs gives a negative value of Z, so an improvement in Z cannot be achieved by introducing flow through any of them.

Слайд 41 Calculations for the optimality test at the end

Calculations for the optimality test at the end of iteration 3

of iteration 3


Слайд 42 adjusted network with unit costs at the completion
of

adjusted network with unit costs at the completionof iteration 3.

iteration 3.


Слайд 43 Optimal flow pattern in original network for the
Distribution

Optimal flow pattern in original network for theDistribution Co. example.

Co. example.


  • Имя файла: zadacha-o-potoke-minimalnoy-stoimosti.pptx
  • Количество просмотров: 117
  • Количество скачиваний: 0