【正文】 非基本變量 x2作為入基變量。 ? 因此，選取 x1為離基變量。 ? 新單純形表 z行的所有非基本變量系數(shù)都變成負(fù)值，求解過程結(jié)束。 ? 目標(biāo)函數(shù)的最大值為 11； ? 最優(yōu)解為： x*=(0,4,5,0,0,11)。 ? 主要運(yùn)算為轉(zhuǎn)軸變換，該變換類似解線性方程組的高斯消去法中的消元變換。 ? 基本變量下標(biāo)集為 B={1,2,…,m} ； 非基本變量下標(biāo)集為N={m+1,m+2,…,n} ； ? 當(dāng)前基本可行解為（ b1, b2, …, bm, 0, …, 0）。 ? 如果所有 cj?0，則當(dāng)前基本可行解為最優(yōu)解，計(jì)算結(jié)束。 ? 步驟 2： 選離基變量 。 ? 否則計(jì)算 ? 選取基本變量 xk為離基變量。 ? 新單純形表中各元素變換如下。 ???????????kekekekieiiabbBiababb?????????????keieikkekjieijijaaaNjBiaaaaa ,??????????keekkekjejaaNjaaa1????????????keekkekieiiaccNiaaccc16 將一般問題轉(zhuǎn)化為約束標(biāo)準(zhǔn)型 ? 有幾種巧妙的辦法可以將一般的線性規(guī)劃問題轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 ? 具體做法是，引入 松弛變量 ，利用松弛變量的非負(fù)性，將不等式轉(zhuǎn)化為等式。 ? 在求解過程中，應(yīng)當(dāng)將松弛變量與原來(lái)變量同樣對(duì)待。 ? 注意松弛變量前的符號(hào)由相應(yīng)的原不等式的方向所確定。 ? 至此，原問題已經(jīng)變換為等價(jià)的約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 129072182343244321324221311??????????????????yxxxzxxxxzyxxzyxxz18 一般線性規(guī)劃問題的 2階段單純形算法 ? 引入人工變量后的線性規(guī)劃問題與原問題并不等價(jià)，除非所有 zi都是 0 。 ? 第一階段用一個(gè)輔助目標(biāo)函數(shù) 替代原來(lái)的目標(biāo)函數(shù)。 ? 對(duì)輔助線性規(guī)劃問題用單純形算法求解。 ? 在輔助線性規(guī)劃問題最后的單純形表中，所有 zi均為非基本變量。 ? 單純形算法第一階段的任務(wù)就是構(gòu)造一個(gè)初始基本可行解。 ? 此時(shí)要用原來(lái)的目標(biāo)函數(shù)進(jìn)行求解。 ????? miizz119 退化情形的處理 ? 用單純形算法解一般的線性規(guī)劃問題時(shí)，可能會(huì)遇到退化的情形，即在迭代計(jì)算的某一步中，常數(shù)列中的某個(gè)元素的值變成 0，使得相應(yīng)的基本變量取值為 0。在這種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無(wú)限循環(huán)。 ? 按照 2階段單純形算法求解該問題將出現(xiàn)無(wú)限循環(huán)。 ? Bland提出在單純形算法迭代中，按照下面的 2個(gè)簡(jiǎn)單規(guī)則就可以避免循環(huán)。 ? 規(guī)則 2：設(shè) ? 取 xk為離基變量。 ? 選取入基變量的算法 enter(objrow) 中只要加一個(gè) break語(yǔ)句即可。必須保證在時(shí)間段 i=1,2,…,n ，有 bi的倉(cāng)庫(kù)容量可用。設(shè) cij是從時(shí)間段 i到時(shí)間段 j租用 1個(gè)單位倉(cāng)庫(kù)容量的價(jià)格，1?i?j?n。 ? 設(shè)租用時(shí)間段 i到時(shí)間段 j的倉(cāng)庫(kù)容量為 yij， 1?i?j?n。 nnnn yyyyyyy , 2232211211 ??? mxxx , 21 ?nnnn ccccccc , 2232211211 ??? mddd , 21 ?xd TminbAx?0?x?????????????????100100100000001101100011111100000001111???????????????????????A23 最大網(wǎng)絡(luò)流問題 ? 基本概念和術(shù)語(yǔ) ? （ 1） 網(wǎng)絡(luò) ? G是一個(gè)簡(jiǎn)單有向圖， G=(V,E)， V={1， 2， … ， n}。 ? 有向圖 G的每一條邊 (v,w)∈ E，對(duì)應(yīng)有一個(gè)值 cap(v,w)≥0，稱為邊的 容量 。 ? （ 2） 網(wǎng)絡(luò)流 ? 網(wǎng)絡(luò)上的 流 是定義在網(wǎng)絡(luò)的邊集合 E上的一個(gè)非負(fù)函數(shù) flow={flow(v,w)}，并稱flow(v,w)為邊 (v,w)上的 流量 。 ? ()平衡約束： ? 對(duì)于中間頂點(diǎn)：流出量 =流入量。 ? 可行流總是存在的。 0),(),(),(),(?? ???? EvwEwvvwf l o wwvf l o wfsvf l o wvsf l o wEsvEvs?? ???? ),(),(),(),(fvtf l o wtvf l o wEvtEtv?? ???? ),(),(),(),(25 ? （ 4） 邊流 ? 對(duì)于網(wǎng)絡(luò) G的一個(gè)給定的可行流 flow，將網(wǎng)絡(luò)中滿足 flow(v,w)=cap(v,w)的邊稱為 飽和邊 ；flow(v,w)cap(v,w)的邊稱為 非飽和邊 ； flow(v,w)=0的邊稱為 零流邊 ； flow(v,w)0的邊稱為非零流邊 。 ? （ 5） 最大流 ? 最大流問題即求網(wǎng)絡(luò) G的一個(gè)可行流 flow，使其流量 f達(dá)到最大。此時(shí)網(wǎng)絡(luò)的每一條邊 (v,w)除了給定容量 cap(v,w)外，還定義了一個(gè)單位流量費(fèi)用 cost(v,w)。 ? 設(shè) (v,w)是 G的一條邊。 ? 按照殘流網(wǎng)絡(luò)的定義，當(dāng)原網(wǎng)絡(luò) G中的邊 (v,w)是一條零流邊時(shí)，殘流網(wǎng)絡(luò) G*中有唯一的一條邊 (v,w)與之對(duì)應(yīng)，且該邊的容量為 cap(v,w)。 ? 當(dāng)原網(wǎng)絡(luò) G中的邊 (v,w)是一條弱流邊時(shí)，殘流網(wǎng)絡(luò) G*中有 2條邊 (v,w)和 (w,v)與之對(duì)應(yīng)，這 2條邊的容量分別為 cap(v,w) flow(v,w)和 flow(v,w)。 27 增廣路算法 ? 1 算法基本思想 ? 設(shè) P是網(wǎng)絡(luò) G中聯(lián)結(jié)源 s和匯 t的一條路。 ? 將路 P上的邊分成 2類： ? 一類邊的方向與路的方向一致，稱為 向前邊 。 ? 另一類邊的方向與路的方向相反，稱為 向后邊 。 ? 設(shè) flow是一個(gè)可行流， P是從 s到 t的一條路，若 P滿足下列條件： ? （ 1）在 P的所有向前邊 (v,w)上， flow(v,w)cap(v,w)，即 P+中的每一條邊都是非飽和邊； ? （ 2）在 P的所有向后邊 (v,w)上， flow(v,w)0，即 P中的每一條邊都是非零流邊。 ? 可增廣路是殘流網(wǎng)絡(luò)中一條容量大于 0的路。 28 ? 增流的具體做法是： ? （ 1）不屬于可增廣路 P的邊 (v,w)上的流量保持不變； ? （ 2）可增廣路 P上的所有邊 (v,w)上的流量按下述規(guī)則變化： ? 在向前邊 (v,w)上， flow(v,w)+d； ? 在向后邊 (v,w)上， flow(v,w)d。 ? 其中 d稱為可增廣量，可按下述原則確定： d取得盡量大，又要使變化后的流仍為可行流。 ? 因此 d應(yīng)該等于向前邊上的 cap(v,w)flow(v,w)與向后邊上的 flow(v,w)的最小值。 ? 增廣路定理： 設(shè) flow是網(wǎng)絡(luò) G的一個(gè)可行流，如果不存在從 s到 t關(guān)于 flow的可增廣路 P，則flow是 G的一個(gè)最大流。該算法也常稱作 Ford Fulkerson算法。G。 vectorint wt。 int ST(int v) const { return st[v]other(v)。 fo