運(yùn)籌學(xué)期末復(fù)習(xí)提綱課件

1線性規(guī)劃線性規(guī)劃問題及其數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法的進(jìn)一步討論1線性規(guī)劃線性規(guī)劃問題及其數(shù)學(xué)模型1線性規(guī)劃的概念目標(biāo)能表成求MAX或MIN達(dá)到目標(biāo)有多種方案實(shí)現(xiàn)目標(biāo)有一定條件目標(biāo)和條件都能用線性函數(shù)表示線性規(guī)劃的概念目標(biāo)能表成求MAX或MIN2例如，對(duì)于線性規(guī)劃問題其系數(shù)矩陣為則下面兩個(gè)矩陣都是該線性規(guī)劃問題的基。和還能找出其它基嗎？例如，對(duì)于線性規(guī)劃問題其系數(shù)矩陣為則下面兩個(gè)矩陣都是該線3基解：令非基變量等于0的解?；尚薪猓夯?可行解例如，對(duì)于上面的線性規(guī)劃問題，如果取x1，x2為基變量，則令非基變量x3，x4為零，約束方程組為

解之得。故我們得到基解注意到這個(gè)基解還是一個(gè)可行解。是否所有的基解都是基可行解？（選x1,x3作為基變量）基解：令非基變量等于0的解。例如，對(duì)于上面的線性規(guī)劃問題，如4解的概念解的概念5解2.3(1)(2)解2.3(1)(2)6線性規(guī)劃要注意的幾點(diǎn)圖解法對(duì)只包含兩個(gè)決策變量的線性規(guī)劃問題，可以用圖解法來求解。圖解法顧名思義就是通過作圖來求解的方法，它簡(jiǎn)單直觀、并有助于說明一般線性規(guī)劃問題求解的基本原理。線性規(guī)劃要注意的幾點(diǎn)7線性規(guī)劃的標(biāo)準(zhǔn)形式它具有如下四個(gè)特征：目標(biāo)函數(shù)求max；約束方程符號(hào)取“=”；bi非負(fù)；所有決策變量xj非負(fù)。線性規(guī)劃的標(biāo)準(zhǔn)形式它具有如下四個(gè)特征8線性規(guī)劃解的存在性線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無限集。他們有有限個(gè)頂點(diǎn)，線性規(guī)劃問題的每個(gè)基可行解對(duì)應(yīng)可行域一個(gè)頂點(diǎn)，反之亦然。若線性規(guī)劃問題有最優(yōu)解，必在某頂點(diǎn)達(dá)到。線性規(guī)劃解的存在性線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，9大M法將人工變量在目標(biāo)函數(shù)中反映出來得到如下形式的線性規(guī)劃：大M法將人工變量在目標(biāo)函數(shù)中反映出來得到如下形式的線性規(guī)劃：10因此最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為需要說明的是，如果在用大M法求解線性規(guī)劃問題時(shí)，最終表的基變量中還含有人工變量，那么這個(gè)最終表并沒有給出原來問題的基可行解，從而沒有給出原來的線性規(guī)劃問題最優(yōu)解。這時(shí)原來線性規(guī)劃問題為無可行解。用EXCEL執(zhí)行該計(jì)算過程因此最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為需要說明的是，如果在用大M法求解11故原來問題的最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值這一結(jié)果與大M法得到的結(jié)果是一致的。無可行解的判別：在用大M法求解線性規(guī)劃問題時(shí)，若最終單純形表的基變量中含人工變量；或用兩階段法求解時(shí)，第一階段最終表的基變量中含非零的人工變量，也就是第一階段最優(yōu)目標(biāo)函數(shù)值不等于零，則線性規(guī)劃問題無可行解。故原來問題的最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值這一結(jié)果與大M法得到的結(jié)果122.8單純形法小結(jié)2.8單純形法小結(jié)132線性規(guī)劃對(duì)偶理論及其應(yīng)用2線性規(guī)劃對(duì)偶理論及其應(yīng)用14規(guī)范形式的線性規(guī)劃與對(duì)偶規(guī)劃問題原問題（LP）對(duì)偶問題（DLP）

規(guī)范形式的線性15對(duì)偶規(guī)劃的基本性質(zhì)3.2.2弱對(duì)偶性定理：如果X、Y分別是原問題和對(duì)偶問題的一個(gè)可行解，則其對(duì)應(yīng)的原問題的目標(biāo)函數(shù)值不大于對(duì)偶問題的目標(biāo)函數(shù)值，也即證明：因?yàn)閄、Y分別是原問題（3.1）與對(duì)偶問題（3.2）的可行解，故：

所以對(duì)偶規(guī)劃的基本性質(zhì)3.2.2弱對(duì)偶性定理：證明：因?yàn)閄、Y16推論一：原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是起原問題目標(biāo)函數(shù)值的上界。推論二：如果原問題存在無界解，則對(duì)偶問題一定無可行解；反之，如果對(duì)偶問題存在無界解，原問題也一定不存在可行解。注意，該推論的逆反定理并不成立。注意，該推論的逆反定理并不成立。推論三：如果原問題無解，且對(duì)偶問題有可行解，則對(duì)偶問題具有無解解，；反之，如果對(duì)偶問題無解，且原問題有可行解，則對(duì)偶問題具有無界解。推論一：原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的17最優(yōu)性定理

18互補(bǔ)松弛定理互補(bǔ)松弛定理19約束方程也分為兩種情況：

，約束條件比較松；

，約束條件比較緊；yi>=0,分為兩種情況：yi>0，約束條件比較松；yi=0，約束條件比較緊；互補(bǔ)松弛定理的解釋變量同其對(duì)偶問題的約束方程之間至多只能夠有一個(gè)取松弛的情況，當(dāng)其中一個(gè)取松弛的情況時(shí)，另外一個(gè)比較緊，即取嚴(yán)格等號(hào)。約束方程也分為兩種情況：yi>=0,分為兩種情況：互補(bǔ)20例已知下面的LP1和LP2為一組對(duì)偶規(guī)劃，且已知LP1的最優(yōu)解為X=（1.5，1）’。試運(yùn)用互補(bǔ)松弛定理求出對(duì)偶問題的最優(yōu)解Y。生產(chǎn)計(jì)劃問題（LP1）資源定價(jià)問題（LP2）例已知下面的LP1和LP2為一組對(duì)偶規(guī)劃，且已知LP1的最優(yōu)21解：由X=（1.5，1）’得聯(lián)立求解得：

解：由X=（1.5，1）’得聯(lián)立求解得：22解：由X=（1.5，1）’得聯(lián)立求解得：

解：由X=（1.5，1）’得聯(lián)立求解得：23解：由X=（1.5，1）’得聯(lián)立求解得：

解：由X=（1.5，1）’得聯(lián)立求解得：24靈敏度分析靈敏度分析25

約束條件右端向量b的變化

263目標(biāo)規(guī)劃3目標(biāo)規(guī)劃27目標(biāo)規(guī)劃基本概念（1）偏差變量d+：正偏差變量，表示決策值超出目標(biāo)值的部分d-：負(fù)偏差變量，表示決策值未達(dá)到目標(biāo)值的部分按定義有：d+

≥0，

d-≥0，d+?d-=0（2）絕對(duì)約束和目標(biāo)約束絕對(duì)約束（硬約束）：必須嚴(yán)格滿足的約束條件目標(biāo)約束（軟約束）：目標(biāo)規(guī)劃特有

（3）優(yōu)先因子（P）和權(quán)系數(shù)（W）

優(yōu)先因子用P1，P2，…，Pl表示，規(guī)定Pl>>Pl+1，表示Pl比Pl+1有更大的優(yōu)先權(quán)。（4）目標(biāo)函數(shù)決策值=目標(biāo)值min{f(d++d-)}決策值<目標(biāo)值min{f(d+)}決策值>目標(biāo)值min{f(d-)}目標(biāo)規(guī)劃基本概念（1）偏差變量28目標(biāo)規(guī)劃模型的建立例4.1某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。已知有關(guān)數(shù)據(jù)見表4-1。問如何安排生產(chǎn)使獲得的總利潤(rùn)最大？表4-1目標(biāo)規(guī)劃模型的建立例4.1某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。已29設(shè)x1、x2分別表示計(jì)劃生產(chǎn)產(chǎn)品甲、乙的產(chǎn)量，它的數(shù)學(xué)模型為：它的最優(yōu)解為x1=4，x2=3，最大目標(biāo)函數(shù)值為62。maxz=8x1+10x2

2x1+x2≤11st.x1+2x2≤10x1,x2≥0但企業(yè)的經(jīng)營(yíng)目標(biāo)不僅是利潤(rùn)，企業(yè)還考慮了以下問題：（1）根據(jù)市場(chǎng)信息，產(chǎn)品甲開始出現(xiàn)滯銷現(xiàn)象，故考慮產(chǎn)品甲的產(chǎn)量應(yīng)不超過產(chǎn)品乙；（2）超過計(jì)劃供應(yīng)的原材料需高價(jià)采購(gòu)，應(yīng)避免過量消耗；（3）應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班；（4）應(yīng)盡可能達(dá)到并超過計(jì)劃利潤(rùn)指標(biāo)56元。設(shè)x1、x2分別表示計(jì)劃生產(chǎn)產(chǎn)品甲、乙的產(chǎn)量，它的數(shù)學(xué)模型為30例4.2例4.1的決策者經(jīng)過綜合考慮，決策者的目標(biāo)分別為：首先原材料使用限額不能突破；其次產(chǎn)品甲的產(chǎn)量不大于產(chǎn)品乙；再次充分利用設(shè)備臺(tái)時(shí)，不希望加班；最后利潤(rùn)額不少于56元。問應(yīng)如何安排生產(chǎn)？解：原材料使用限額的約束是絕對(duì)約束，其他三個(gè)約束是屬于目標(biāo)約束，分別賦予這三個(gè)目標(biāo)的優(yōu)先因子為P1，P2，P3。這問題的數(shù)學(xué)模型為：2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1,x2,di-,di+≥0i=1,2,3min{P1

d1+,P2(d2-+d2+),P3

d3-

}s.t.例4.2例4.1的決策者經(jīng)過綜合考慮，決策者的目標(biāo)分別為31目標(biāo)規(guī)劃模型的一般形式：

Min﹛Pl（∑（wlk-dk-+

wlk+dk+））,l=1,2…,L﹜k=1K∑ckjxj+dk--dk+=gk，k=1，2，…，Kj=1n∑aijxj≤（=，≥）bi，i=1，2，…，mj=1nxj≥0,j=1，2，…，ndk-，dk+≥0,k=1，2，…，KS.t.32目標(biāo)規(guī)劃模型的一般形式：Min﹛Pl（∑（w目標(biāo)規(guī)劃模型的一般形式：

Min﹛Pl（∑（wlk-dk-+

wlk+dk+））,l=1,2…,L﹜k=1K∑ckjxj+dk--dk+=gk，k=1，2，…，Kj=1n∑aijxj≤（=，≥）bi，i=1，2，…，mj=1nxj≥0,j=1，2，…，ndk-，dk+≥0,k=1，2，…，KS.t.33目標(biāo)規(guī)劃模型的一般形式：Min﹛Pl（∑（w當(dāng)總產(chǎn)量=總銷量，稱為產(chǎn)銷平衡問題當(dāng)總產(chǎn)量≠總銷量，稱為產(chǎn)銷不平衡問題4運(yùn)輸問題當(dāng)總產(chǎn)量=總銷量，稱為產(chǎn)銷平衡問題當(dāng)總產(chǎn)量≠總銷量，稱34產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型如下

運(yùn)輸問題含有m×n個(gè)變量，m+n個(gè)約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較特殊，對(duì)應(yīng)變量xij的系數(shù)向量，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零模型中只有個(gè)相互獨(dú)立的約束方程。因此，運(yùn)輸問題的任一基可行解都有m+n-1個(gè)基變量。產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型如下運(yùn)輸問題含有m×n個(gè)變量，35運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法362)沃格爾法列罰數(shù)行罰數(shù)25130116213012321212017635200122)沃格爾法列罰數(shù)行罰數(shù)2513011621301232376

314331σ11=

c11-c13+c23-c21=3-3+2-1=1解的最優(yōu)性檢驗(yàn)1)閉回路法6314331σ11=c11-c13+c23-c21=338對(duì)偶變量法（位勢(shì)法）63

34130310-1-529121-11012vj

ui基變量：cij=ui+vj非基變量：σij=cij–(ui+vj)對(duì)偶變量法（位勢(shì)法）6334130310-1-5291239產(chǎn)銷不平衡運(yùn)輸問題

1.一般產(chǎn)銷不平衡運(yùn)輸問題1)總產(chǎn)量>總銷量假想一銷地Bn+1，令銷量為

,運(yùn)價(jià)c=0產(chǎn)銷不平衡運(yùn)輸問題1.一般產(chǎn)銷不平衡運(yùn)輸問題1)總產(chǎn)量>405整數(shù)規(guī)劃5.1整數(shù)規(guī)劃實(shí)例及一般模型5.2分支定界法5.30-1整數(shù)規(guī)劃5.4指派問題5整數(shù)規(guī)劃5.1整數(shù)規(guī)劃實(shí)例及一般模型41整數(shù)規(guī)劃的類型純整數(shù)規(guī)劃：xj全部是整數(shù)混合整數(shù)規(guī)劃：xj部分是整數(shù)0-1型整數(shù)規(guī)劃：xj=0或1整數(shù)規(guī)劃的類型純整數(shù)規(guī)劃：xj全部是整數(shù)42整數(shù)線性規(guī)劃問題解的特點(diǎn)整數(shù)規(guī)劃的可行解集合是它的松弛問題可行解集合的一個(gè)子集，即整數(shù)規(guī)劃的可行解一定是其松弛問題的可行解（反之不然）整數(shù)規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值不會(huì)優(yōu)于其松弛問題最優(yōu)解的目標(biāo)函數(shù)值若松弛問題的可行解滿足整數(shù)約束，則它也是整數(shù)規(guī)劃的可行解整數(shù)規(guī)劃問題的最優(yōu)解不能由其松弛問題最優(yōu)解經(jīng)過簡(jiǎn)單取整得到整數(shù)線性規(guī)劃問題解的特點(diǎn)整數(shù)規(guī)劃的可行解集合是它的松弛問題可43如用“舍入取整法”可得到4個(gè)點(diǎn)即(2，2),(2，3),(3，2),(3，3)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。松弛問題最優(yōu)解整數(shù)規(guī)劃最優(yōu)解例不能通過舍入取整地方法，由松弛問題的解得到整數(shù)規(guī)劃的最優(yōu)解如用“舍入取整法”可得到4個(gè)點(diǎn)即(2，2),(2，3),446動(dòng)態(tài)規(guī)劃6.1動(dòng)態(tài)規(guī)劃的基本概念6.2最優(yōu)化原理6.3經(jīng)濟(jì)管理問題舉例6動(dòng)態(tài)規(guī)劃6.1動(dòng)態(tài)規(guī)劃的基本概念45多階段決策過程動(dòng)態(tài)規(guī)劃的分類：離散確定型離散隨機(jī)型連續(xù)確定型連續(xù)隨機(jī)型決策1狀態(tài)1決策2狀態(tài)2決策n狀態(tài)3……狀態(tài)n多階段決策過程動(dòng)態(tài)規(guī)劃的分類：決策1狀態(tài)1決策2狀態(tài)2決策n461、階段，階段數(shù)階段變量：k;階段數(shù)記作n。無后效性：如果某階段的狀態(tài)給定，這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響

3、決策某階段狀態(tài)確定后，為確定下一階段的狀態(tài)，所作出的決定（選擇）。決策變量：uk(sk)表示第k階段狀態(tài)為sk時(shí)的決策

允許決策集合：Dk(sk)動(dòng)態(tài)規(guī)劃的基本概念2、狀態(tài)每個(gè)階段開始時(shí)所處的自然狀態(tài)或客觀條件狀態(tài)變量：sk狀態(tài)集合：Sk1、階段，階段數(shù)無后效性：如果某階段的狀態(tài)給定，這階段以后474、策略：由決策組成的序列稱為策略。p1,n{u1(s1),u2(s2),…

,un(sn)}允許策略集合：P1,n最優(yōu)策略：p*1,n子策略：5、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)6、效益(指標(biāo))函數(shù):Vkn(sk,pkn(sk))階段效益函數(shù)：wk(sk,uk(sk))最優(yōu)效益函數(shù)：fk(sk)最優(yōu)策略:pkn*全過程的最優(yōu)效益函數(shù)4、策略：全過程的最優(yōu)效益函數(shù)48標(biāo)號(hào)法求解最短路問題07681614141621202226所以最短路為A—B1—C2—D2—E，最短路長(zhǎng)為26。標(biāo)號(hào)法求解最短路問題0768161414162120222649最優(yōu)化原理動(dòng)態(tài)規(guī)劃的基本方程（逆序法）：fk(sk)表示從第k階段狀態(tài)sk到終點(diǎn)F的最短距離如果一個(gè)策略是最優(yōu)策略，則其子策略也一定是最優(yōu)策略；如果兩段子策略都是最優(yōu)策略，則連起來是否是最優(yōu)策略呢？動(dòng)態(tài)規(guī)劃的基本方程（順序法）：最優(yōu)化原理動(dòng)態(tài)規(guī)劃的基本方程（逆序法）：fk(sk)表507網(wǎng)絡(luò)優(yōu)化模型

圖與網(wǎng)絡(luò)的基本概念最短路徑問題最大流問題最小費(fèi)用最大流問題

7網(wǎng)絡(luò)優(yōu)化模型 圖與網(wǎng)絡(luò)的基本概念51圖與網(wǎng)絡(luò)的基本概念5、連通圖：圈：無向圖G=（V,E）中起點(diǎn)和終點(diǎn)重合的鏈稱為圈初等、簡(jiǎn)單圈：沒有重復(fù)點(diǎn)的圈稱為初等圈，沒有重復(fù)邊的圈稱為簡(jiǎn)單圈。(v1,e1,v2,e6,v4,e3,v3,e5,v1

)圖與網(wǎng)絡(luò)的基本概念5、連通圖：圈：無向圖52圖與網(wǎng)絡(luò)的基本