計(jì)算機(jī)算法設(shè)計(jì)與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-文庫吧在線文庫
【正文】 許一條負(fù)費(fèi)用的增大回路，即判定殘流網(wǎng)絡(luò)中是否存在負(fù)費(fèi)用圈。 步驟 1： 如果不存在最小費(fèi)用路，則計(jì)算結(jié)束，已經(jīng)找到最小費(fèi)用流； 否則用最短路算法在殘流網(wǎng)絡(luò)中找從 s到 t的最小費(fèi)用可增廣路，轉(zhuǎn)步驟 2。 ?基本思想是，從一個(gè)空流開始，不斷在殘流網(wǎng)絡(luò)中尋找從源 s到匯 t的最小費(fèi)用路，然后沿最小費(fèi)用路增流，通過一系列增流過程構(gòu)造出一個(gè)最大流，即為最小費(fèi)用流。 ?增大回路（圈）： 一條關(guān)于 f的增大回路是一個(gè)頂點(diǎn)為 v0,v1,… vk=v0的有向回路 p，滿足路 p上所有邊的剩余容量大于 0。 （ 3）接下來，從 s向 X中的每一個(gè)頂點(diǎn)都增加一條有向邊，從 Y的每一個(gè)頂點(diǎn)都向 t增加一條有向邊。 ?圖匹配問題描述：設(shè) G=(V,E)是一個(gè)圖。 ? 不同的選擇策略導(dǎo)致不同的預(yù)流推進(jìn)算法。 2021年 11月 12日 47 預(yù)流推進(jìn)算法 ? G的每一中間頂點(diǎn)滿足流出量小于或等于流入量。 } } 2021年 11月 12日 45 預(yù)流推進(jìn)算法 ? 增廣路算法的特點(diǎn)是找到增廣路后，立即沿增廣路對網(wǎng)絡(luò)流進(jìn)行增廣。 ? 因此 d應(yīng)該等于向前邊上的 cap(v,w)flow(v,w)與向后邊上的flow(v,w)的最小值。 ? 另一類邊的方向與路的方向相反，稱為 向后邊 。設(shè) (v,w)是 G的一條邊。 ?式中 f 稱為這個(gè) 可行流的流量 ，即源的凈輸出量 (或匯的凈輸入量 )。一般情況下，滿足 s沒有入邊， t沒有出邊。在這種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無限循環(huán)。 ?這個(gè)線性規(guī)劃問題稱為原線性規(guī)劃問題所相應(yīng)的輔助線性規(guī)劃問題。這表明目標(biāo)函數(shù)不可能再增加了，求解過程結(jié)束。 ? 如果選出的列中有一個(gè)或多個(gè)元素為正數(shù)，要弄清是哪個(gè)數(shù)對入基變量值的增加限制更大。 injjij bxa ???101??? ??sxabsnjjiji01??? ??? ? innjjijiin xxabxinx ?2021年 11月 12日 17 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?一個(gè)例子 最大化： 滿足約束： 0,10834124272353253232532???????????xxxxxxxxxxx532 23 xxxz ????2021年 11月 12日 18 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?引入松弛變量 ， ， ，得到標(biāo)準(zhǔn)型： 最大化： 滿足約束： 4x1x 6x532 23 xxxz ????0,83410421223765432153263245321????????????xxxxxxxxxxxxxxxxx2021年 11月 12日 19 標(biāo)準(zhǔn)型的元組表示 ?標(biāo)準(zhǔn)型的元組表示： ?N表示非基本變量下標(biāo)的集合； ?B表示基本變量下標(biāo)的集合； ?b表示由等式約束中的常數(shù)項(xiàng)組成的列向量； ?c表示目標(biāo)函數(shù)中非基本變量系數(shù)組成的行向量； ?v表示目標(biāo)函數(shù)中的常數(shù)項(xiàng)； ? 是一個(gè)矩陣，由所有等式約束中非基本變量 前系數(shù)的負(fù)值確定 ),( vcbABNBif orxabxxcvzNjjijiiNjjj?????????)( ijaA?2021年 11月 12日 20 單純形表 ?標(biāo)準(zhǔn)型線性規(guī)劃的單純形表： x2 x3 x5 z 0 1 3 2 x1 7 3 1 2 x4 12 2 4 0 x6 10 4 3 8 532 23 xxxz ????0,83410421223765432153263245321????????????xxxxxxxxxxxxxxxxx2021年 11月 12日 21 單純形算法 ?第 1步： 選 取 入基變量 。 ?這一類特殊的標(biāo)準(zhǔn)型線性規(guī)劃問題稱為 約束標(biāo)準(zhǔn)型線性規(guī)劃問題 。 2021年 11月 12日 11 單純形及單純形算法 ?如果有 個(gè)變量，每個(gè)約束定義了 維空間中的一個(gè)半空間，這些半空間的交集形成的可行區(qū)域稱作單純形。 2021年 11月 12日 5 線性規(guī)劃問題及表示 ?問題表示 設(shè) 、 、 、 分別表示支出在修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及汽油稅廣告上的千美元數(shù) 目標(biāo)：最小化表達(dá)式 滿足約束： 1x 2x 3x 4x4321 xxxx ???5010082 4321 ????? xxxx1000025 4321 ???? xxxx2521053 4321 ???? xxxx0, 4321 ?xxxx2021年 11月 12日 6 線性規(guī)劃問題及表示 ?一般線性規(guī)劃問題表示 . )(,2,10)(,1)(,1)(,2,1321211211111njxmmmmmkbxammmtbxamibxajnjkjkjnjtjtjnjijij???????????????????????? )(mi nma x1??njjj xc2021年 11月 12日 7 ? 滿足約束條件 ()()式的一組變量值稱為線性規(guī)劃問題的一個(gè) 可行解 。主要政策有修路、槍械管理、農(nóng)業(yè)補(bǔ)貼以及增加公共運(yùn)輸?shù)钠投悺? ? 有些情況下 可能不存在最優(yōu)解 。 ?在每一約束方程中選擇一個(gè)這樣的變量，并以它作為變量求解該約束方程。 ?在求解過程中，應(yīng)當(dāng)將松弛變量與原來變量同樣對待。 ? 在單純形表中考察由第 1步選出的入基變量所相應(yīng)的列。 2021年 11月 12日 23 單純形算法 ?第 3步：轉(zhuǎn)軸變換（主元操作） ?將入基變量與離基變量互調(diào)位臵。 單純形算法 2021年 11月 12日 27 ? ?? ?? ?????????????????????????elieilejieiji
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1