計算機算法設(shè)計與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流(編輯修改稿)
2024-11-12 14:35 本頁面
【文章內(nèi)容簡介】 t r a ir e m a i n i n gt h eoft n t sc o e f f i ci e nt h eC o m p u t eaaaaadoeNje a c hf o rabbxa r i a b l evb a s i e wf o re q u a t i o nt h eoft n t sc o e f f i ci e nt h eC o m p u t eelvcbABNP I V O T1110987.615432.1),,(??? ?? ? ? ?? ? ? ?),,(201918.1716151413.12????????????????????????????vcbABNr et u r nelBBleNNa r i a b l esvn o n b a s i candb a s i cofs et sn ewC o m p u t eaccacccdoeNjea c hf o rbcvvf u n ct i o no b j ect i v et h eC o m p u t eelelejejjee?? 單純形算法的主元操作 2021年 11月 12日 28 單純形算法描述 ?????????????iieiiieeje l s eabt h e naifdoBii n d e xe a c hf o rcw h i c hf o rNei n d e xanc h o o s edoch a sNji n d e xs o m ew h i l ecbAS I M P L E XI N I T I A L I Z EvcbABNcbAS I M P L E X760540302),(),,(1),(),(160151413112),,(),,(11109821 niiilixxxr e t u r nxe l s ebxt h e nBiifdontoif o relvcbABNP I V O TvcbABNe l s eu n b o u n d e dr e t u r nt h e nifi n i m i z e smt h a tBli n d e xanc h o o s e???????????2021年 11月 12日 29 2階段單純形算法 ?首先通過引入 松弛變量 ，將一般線性規(guī)劃問題的不等式約束轉(zhuǎn)化為等式約束，構(gòu)造成標(biāo)準(zhǔn)型。 ?再引入 m個 人工變量 ，記為 zi，構(gòu)造成約束標(biāo)準(zhǔn)型。 ?例如，一個一般線性規(guī)劃問題： 4321 3m a x xxxxz ????12907218243243214231???????????xxxxxxxxxxx4,3,2,10 ?? ix i2021年 11月 12日 30 2階段單純形算法 ?上例中引入松弛變量和人工變量后，約束條件變?yōu)椋? 129072182343244321324221311??????????????????yxxxzxxxxzyxxzyxxz2021年 11月 12日 31 2階段單純形算法 ?第一階段： ?用一個輔助目標(biāo)函數(shù) 替代原來的目標(biāo)函數(shù)。 ?這個線性規(guī)劃問題稱為原線性規(guī)劃問題所相應(yīng)的輔助線性規(guī)劃問題。 ?對輔助線性規(guī)劃問題用單純形算法求解。 ?單純形算法第一階段的任務(wù)就是構(gòu)造一個初始基本可行解。 ?如果在輔助線性規(guī)劃問題最后的單純形表中， zi不全為 0，則原線性規(guī)劃問題沒有可行解，從而原線性規(guī)劃問題無解。 ?????miizz12021年 11月 12日 32 2階段單純形算法 ?第二階段： ?第二階段的目標(biāo)是求解由第一階段導(dǎo)出的問題。 ?此時要用原來的目標(biāo)函數(shù)進行求解。 2021年 11月 12日 33 ? 用單純形算法解一般的線性規(guī)劃問題時，可能會遇到退化的情形，即在迭代計算的某一步中，常數(shù)列中的某個元素的值變成 0，使得相應(yīng)的基本變量取值為 0。 ? 如果選取退化的基本變量為離基變量，則作轉(zhuǎn)軸變換前后的目標(biāo)函數(shù)值不變。在這種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無限循環(huán)。 ? Bland提出在單純形算法迭代中可以避免循環(huán)的 2個簡單規(guī)則。 規(guī)則 1：設(shè) ，取 xe為入基變量。 規(guī)則 2：設(shè) ，取 xk為離基變量。 ? ?0|m in ?? jcje??????????????? ieialelabablkie 0m i n|m i n2021年 11月 12日 34 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡(luò)流問題 三、最小費用流問題 2021年 11月 12日 35 基本概念和術(shù)語 ?網(wǎng)絡(luò) ?G是一個簡單有向圖， G=(V,E)， V={1， 2， … ， n}。 ?有向圖 G的每一條邊 (v,w)∈ E，對應(yīng)有一個值cap(v,w)≥0，稱為邊的 容量 。如果 (v,w)∈ E，則假定 cap(v,w)＝ 0。 ?G中有兩個特殊的頂點 s和 t，稱為 源點 s和 匯點 t。一般情況下，滿足 s沒有入邊， t沒有出邊。 ?這樣的有向圖 G稱作一個 網(wǎng)絡(luò) 。 2021年 11月 12日 36 基本概念和術(shù)語 ?網(wǎng)絡(luò)流 ?網(wǎng)絡(luò)上的 流 是定義在網(wǎng)絡(luò)的邊集合 E上的一個非負(fù)函數(shù) flow={flow(v,w)}，并稱 flow(v,w)為邊 (v,w)上的流量 。 sv2v5tv4v13/75/62 / 24 /94/84/62 / 32 / 52/51/1v31/32021年 11月 12日 37 ?可行流 ?滿足下述條件的流 flow稱為 可行流 ： ?容量約束： 對每一條邊 (v,w)∈ E， 0≤flow(v,w)≤cap(v,w)。 ?平衡約束 ： 對于中間頂點：流出量 =流入量。即對每個v
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1