計(jì)算機(jī)算法設(shè)計(jì)與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-文庫吧資料
2024-10-22 14:35本頁面
【正文】 v∈ V(v≠s,t)有：頂點(diǎn) v的流出量－頂點(diǎn) v的流入量 =0。 sv2v5tv4v13/75/62 / 24 /94/84/62 / 32 / 52/51/1v31/32021年 11月 12日 37 ?可行流 ?滿足下述條件的流 flow稱為 可行流 ： ?容量約束： 對(duì)每一條邊 (v,w)∈ E， 0≤flow(v,w)≤cap(v,w)。 ?這樣的有向圖 G稱作一個(gè) 網(wǎng)絡(luò) 。 ?G中有兩個(gè)特殊的頂點(diǎn) s和 t，稱為 源點(diǎn) s和 匯點(diǎn) t。 ?有向圖 G的每一條邊 (v,w)∈ E，對(duì)應(yīng)有一個(gè)值cap(v,w)≥0，稱為邊的 容量 。 規(guī)則 2：設(shè) ，取 xk為離基變量。 ? Bland提出在單純形算法迭代中可以避免循環(huán)的 2個(gè)簡單規(guī)則。 ? 如果選取退化的基本變量為離基變量，則作轉(zhuǎn)軸變換前后的目標(biāo)函數(shù)值不變。 ?此時(shí)要用原來的目標(biāo)函數(shù)進(jìn)行求解。 ?如果在輔助線性規(guī)劃問題最后的單純形表中， zi不全為 0，則原線性規(guī)劃問題沒有可行解，從而原線性規(guī)劃問題無解。 ?對(duì)輔助線性規(guī)劃問題用單純形算法求解。 ?例如，一個(gè)一般線性規(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階段單純形算法 ?第一階段： ?用一個(gè)輔助目標(biāo)函數(shù) 替代原來的目標(biāo)函數(shù)。 單純形算法 2021年 11月 12日 27 ? ?? ?? ?????????????????????????elieilejieijijeieiileelleljejleleeaaaaaaadoeNje a c hf o rbabbdolBie a c hf o rn t sc o n s 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)型。 ? 單純形算法的基本思想就是從一個(gè)基本可行解出發(fā)，進(jìn)行一系列的 基本可行解的變換，每次變換都使基本可行解的目標(biāo)值不小于（通常是大于）前一次迭代中的目標(biāo)值 。 ? 整個(gè)問題的解可以從最后一張單純形表的常數(shù)列中讀出 。 ? 不斷重復(fù)上述過程，直到新單純形表中 z行的所有非基本變量系數(shù)都變成負(fù)值為止。 2021年 11月 12日 23 單純形算法 ?第 3步：轉(zhuǎn)軸變換（主元操作） ?將入基變量與離基變量互調(diào)位臵。 ? 應(yīng)該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位臵后，仍滿足約束條件。 ? 受限的增加量可以用入基變量所在列的元素（稱為 主元素 ）來除主元素所在行的 “ 常數(shù)列 ” 元素而得到。 ? 如果入基變量所在列的所有元素都是負(fù)值，則目標(biāo)函數(shù)無界，已經(jīng)得到了問題的無界解。 ? 在單純形表中考察由第 1步選出的入基變量所相應(yīng)的列。 ?本例中，選取 x3作為入基變量。 ?選出使目標(biāo)函數(shù)增加的非基本變量作為 入基變量 。 2021年 11月 12日 16 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?設(shè)不等式約束形式為： ?引入一個(gè)松弛變量 s： ?使用 來表示與第 i個(gè)不等式關(guān)聯(lián)的松弛變量： ?等式左邊的變量稱為基
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1