運(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例如，對于線性規(guī)劃問題其系數(shù)矩陣為則下面兩個矩陣都是該線性規(guī)劃問題的基。和還能找出其它基嗎？例如，對于線性規(guī)劃問題其系數(shù)矩陣為則下面兩個矩陣都是該線3基解：令非基變量等于0的解?；尚薪猓夯?可行解例如，對于上面的線性規(guī)劃問題，如果取x1，x2為基變量，則令非基變量x3，x4為零，約束方程組為

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

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

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

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

，約束條件比較松；

，約束條件比較緊；yi>=0,分為兩種情況：yi>0，約束條件比較松；yi=0，約束條件比較緊；互補(bǔ)松弛定理的解釋變量同其對偶問題的約束方程之間至多只能夠有一個取松弛的情況，當(dāng)其中一個取松弛的情況時，另外一個比較緊，即取嚴(yán)格等號。約束方程也分為兩種情況：yi>=0,分為兩種情況：互補(bǔ)20例已知下面的LP1和LP2為一組對偶規(guī)劃，且已知LP1的最優(yōu)解為X=（1.5，1）’。試運(yùn)用互補(bǔ)松弛定理求出對偶問題的最優(yōu)解Y。生產(chǎn)計(jì)劃問題（LP1）資源定價問題（LP2）例已知下面的LP1和LP2為一組對偶規(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）絕對約束和目標(biāo)約束絕對約束（硬約束）：必須嚴(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)使獲得的總利潤最大？表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)營目標(biāo)不僅是利潤，企業(yè)還考慮了以下問題：（1）根據(jù)市場信息，產(chǎn)品甲開始出現(xiàn)滯銷現(xiàn)象，故考慮產(chǎn)品甲的產(chǎn)量應(yīng)不超過產(chǎn)品乙；（2）超過計(jì)劃供應(yīng)的原材料需高價采購，應(yīng)避免過量消耗；（3）應(yīng)盡可能充分利用設(shè)備臺時，但不希望加班；（4）應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(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è)備臺時，不希望加班；最后利潤額不少于56元。問應(yīng)如何安排生產(chǎn)？解：原材料使用限額的約束是絕對約束，其他三個約束是屬于目標(biāo)約束，分別賦予這三個目標(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個變量，m+n個約束方程。其系數(shù)矩陣的結(jié)構(gòu)比較特殊，對應(yīng)變量xij的系數(shù)向量，其分量中除第i個和第m+j個為1以外，其余的都為零模型中只有個相互獨(dú)立的約束方程。因此，運(yùn)輸問題的任一基可行解都有m+n-1個基變量。產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型如下運(yùn)輸問題含有m×n個變量，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對偶變量法（位勢法）63

34130310-1-529121-11012vj

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

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

,運(yùn)價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ī)劃的可行解集合是它的松弛問題可行解集合的一個子集，即整數(shù)規(guī)劃的可行解一定是其松弛問題的可行解（反之不然）整數(shù)規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值不會優(yōu)于其松弛問題最優(yōu)解的目標(biāo)函數(shù)值若松弛問題的可行解滿足整數(shù)約束，則它也是整數(shù)規(guī)劃的可行解整數(shù)規(guī)劃問題的最優(yōu)解不能由其松弛問題最優(yōu)解經(jīng)過簡單取整得到整數(shù)線性規(guī)劃問題解的特點(diǎn)整數(shù)規(guī)劃的可行解集合是它的松弛問題可43如用“舍入取整法”可得到4個點(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個點(diǎn)即(2，2),(2，3),446動態(tài)規(guī)劃6.1動態(tài)規(guī)劃的基本概念6.2最優(yōu)化原理6.3經(jīng)濟(jì)管理問題舉例6動態(tài)規(guī)劃6.1動態(tài)規(guī)劃的基本概念45多階段決策過程動態(tài)規(guī)劃的分類：離散確定型離散隨機(jī)型連續(xù)確定型連續(xù)隨機(jī)型決策1狀態(tài)1決策2狀態(tài)2決策n狀態(tài)3……狀態(tài)n多階段決策過程動態(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時的決策

允許決策集合：Dk(sk)動態(tài)規(guī)劃的基本概念2、狀態(tài)每個階段開始時所處的自然狀態(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)號法求解最短路問題07681614141621202226所以最短路為A—B1—C2—D2—E，最短路長為26。標(biāo)號法求解最短路問題0768161414162120222649最優(yōu)化原理動態(tài)規(guī)劃的基本方程（逆序法）：fk(sk)表示從第k階段狀態(tài)sk到終點(diǎn)F的最短距離如果一個策略是最優(yōu)策略，則其子策略也一定是最優(yōu)策略；如果兩段子策略都是最優(yōu)策略，則連起來是否是最優(yōu)策略呢？動態(tài)規(guī)劃的基本方程（順序法）：最優(yōu)化原理動態(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)重合的鏈稱為圈初等、簡單圈：沒有重復(fù)點(diǎn)的圈稱為初等圈，沒有重復(fù)邊的圈稱為簡單圈。(v1,e1,v2,e6,v4,e3,v3,e5,v1

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