第一講線性規(guī)劃及其對偶問題運籌學(xué)

運籌學(xué)主要內(nèi)容第一講線性規(guī)劃及其對偶問題第二講線性規(guī)劃建模第三講非線性規(guī)劃:無約束問題第四講非線性規(guī)劃:約束極值問題第五講原始對偶算法與拉格朗日松弛算法第五講對策論（博弈論）第六講信息經(jīng)濟學(xué)（機制設(shè)計）第六講決策論第七講整數(shù)規(guī)劃擴展第八講智能算法第一講線性規(guī)劃及其對偶問題1線性規(guī)劃問題及其數(shù)學(xué)模型2線性規(guī)劃問題的圖解法3單純形法4對偶問題5EXCEL求解線性規(guī)劃6靈敏度分析1線性規(guī)劃問題及其數(shù)學(xué)模型(1)線性規(guī)劃問題例1、生產(chǎn)組織與計劃問題A,B各生產(chǎn)多少,可獲最大利潤?可用資源煤勞動力倉庫AB123202單位利潤4050306024解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1，x2可以建立如下的數(shù)學(xué)模型：Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件2.9m鋼筋架子100個，每個需用2.1m各1，原料長7.4m1.5m求：如何下料，使得殘余料頭最少。解：首先列出各種可能的下料方案；計算出每個方案可得到的不同長度鋼筋的數(shù)量及殘余料頭長度；確定決策變量；根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)；根據(jù)不同長度鋼筋的需要量確定約束方程。例2、合理下料問題設(shè)按第i種方案下料的原材料為xi根組合方案123456782.9m211100002.1m021032101.5m10130234合計7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料長7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料頭0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m例3、運輸問題工廠123庫存?zhèn)}121350222430庫334210需求401535運輸單價求：運輸費用最小的運輸方案。解：設(shè)xij為i倉庫運到j(luò)工廠的原棉數(shù)量其中：i

＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13=

50x21+x22+x23=

30x31+x32+x33=

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0s.t(2)線性規(guī)劃問題的特點決策變量：(x1…xn)T

代表某一方案，

決策者要考慮和控制的因素非負；目標(biāo)函數(shù)：Z=?(x1

…xn)為線性函數(shù)，求Z極大或極小;約束條件：可用線性等式或不等式表示.具備以上三個要素的問題就稱為線性規(guī)劃問題。目標(biāo)函數(shù)約束條件(3)線性規(guī)劃模型一般形式隱含的假設(shè)比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比可加性：每個決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij,bi,cj為確定值2線性規(guī)劃問題的圖解法定義1：滿足約束(2)的X=(X1…Xn)T稱為線性規(guī)劃問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(1)的可行解稱為線性規(guī)劃問題的最優(yōu)解。例1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t解：(1)、確定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域(2)、求最優(yōu)解最優(yōu)解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20s.t解：(1)、確定可行域與上例完全相同。(2)、求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解：BC線段最優(yōu)解：BC線段B點：X(1)=(6,12)C點：X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)MaxZ=1200

X1615

X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域無界無有限最優(yōu)解無有限最優(yōu)解可行域無上界例4、MaxZ=3X1+2X2-X1-X21X1,X20無可行域無可行解-1X2-1X10s.tX20X10-X1-X21直觀結(jié)論線性規(guī)劃問題的解有四種情況唯一最優(yōu)解無窮多最優(yōu)解無有限最優(yōu)解無可行解若線性規(guī)劃問題有解，則可行域是一個凸多邊形（或凸多面體）；若線性規(guī)劃問題有最優(yōu)解，則唯一最優(yōu)解對應(yīng)于可行域的一個頂點；無窮多個最優(yōu)解對應(yīng)于可行域的一條邊；3單純形法3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式3.2線性規(guī)劃問題的基本解3.3單純形法的基本思想3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)約束條件(1)線性規(guī)劃模型一般形式價值系數(shù)決策變量技術(shù)系數(shù)右端常數(shù)(2)線性規(guī)劃模型標(biāo)準(zhǔn)形式價值向量決策向量系數(shù)矩陣右端向量(3)線性規(guī)劃模型矩陣形式對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:(4)一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化目標(biāo)函數(shù)目標(biāo)函數(shù)為極小化約束條件分兩種情況：大于、小于決策變量可能存在小于零的情況3.2線性規(guī)劃問題的基本解(1)解的基本概念定義在線性規(guī)劃問題中，約束方程組(2)的系數(shù)矩陣A(假定)的任意一個階的非奇異(可逆)的子方陣B(即)，稱為線性規(guī)劃問題的一個基陣或基。基陣非基陣基向量非基向量基變量非基變量令則定義在約束方程組(2)中，對于一個選定的基B，令所有的非基變量為零得到的解，稱為相應(yīng)于基B的基本解。定義在基本解中，若該基本解滿足非負約束，即，則稱此基本解為基本可行解，簡稱基可行解；對應(yīng)的基B稱為可行基?；窘庵凶疃嘤衜個非零分量?；窘獾臄?shù)目不超過個。若B滿足下列條件，稱為最優(yōu)基稱為最優(yōu)解例現(xiàn)有線性規(guī)劃問題試求其基本解、基本可行解。解:(1)首先將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型引入松弛變量x3和x4(2)求基本解由上式得可能的基陣由于所有|B|≠0，所以有6個基陣和6個基本解。對于基陣令則對于基陣令則為基本可行解，B13為可行基為基本可行解，B12為可行基對于基陣令則對于基陣令則對于基陣令則對于基陣令則為基本可行解，B24為可行基為基本可行解，B34為可行基0ABCDE所以，本問題存在6個基本解，其中4個為基可行解.(2)幾點結(jié)論若線性規(guī)劃問題有可行解,則可行域是一個凸多邊形或凸多面體(凸集),且僅有有限個頂點(極點);線性規(guī)劃問題的每一個基可行解都對應(yīng)于可行域上的一個頂點(極點);若線性規(guī)劃問題有最優(yōu)解,則最優(yōu)解必可在基可行解(極點)上達到;線性規(guī)劃問題的基可行解(極點)的個數(shù)是有限的,不會超過個.上述結(jié)論說明:線性規(guī)劃的最優(yōu)解可通過有限次運算在基可行解中獲得.3.3單純形法(1)單純形法的引入(2)表格單純形法4線性規(guī)劃的對偶理論4.1對偶問題4.2對偶問題的基本性質(zhì)4.3影子價格4.4對偶單純形法4.1對偶問題(1)對偶問題的提出例1、生產(chǎn)組織與計劃問題A,B各生產(chǎn)多少,可獲最大利潤?可用資源煤勞動力倉庫AB123202單位利潤4050306024Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件如果因為某種原因，不愿意自己生產(chǎn)，而希望通過將現(xiàn)有資源承接對外加工來獲得收益，那么應(yīng)如何確定各資源的使用價格？Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件兩個原則所得不得低于生產(chǎn)的獲利要使對方能夠接受設(shè)三種資源的使用單價分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350通過使用所有資源對外加工所獲得的收益W=30y1+60y2+24y3根據(jù)原則2，對方能夠接受的價格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對偶問題，y1,y2,y3稱為影子價格(2)對偶問題的形式定義設(shè)原線性規(guī)劃問題為則稱下列線性規(guī)劃問題為其對偶問題，其中yi(i=1,2,…,m)稱為對偶變量。上述對偶問題稱為對稱型對偶問題。原問題簡記為(P)，對偶問題簡記為(D)對偶關(guān)系對應(yīng)表原問題對偶問題目標(biāo)函數(shù)類型MaxMin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項系數(shù)與右邊項的對應(yīng)關(guān)系右邊項系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與

0

對偶問題約束類型變量

0約束

的對應(yīng)關(guān)系無限制＝原問題約束類型與

0對偶問題變量類型約束

變量

0的對應(yīng)關(guān)系＝無限制4.2對偶問題的基本性質(zhì)定理1對偶問題的對偶就是原問題MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0對偶的定義對偶的定義定理2(弱對偶定理)分別為(P),(D)的可行解，則有CbX，yXy證明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb推論2、(P)有可行解,但無有限最優(yōu)解，則(D)無可行解。定理3、yX,分別為(P),(D)的可行解，且XyC=b,則它們是(P),(D)

的最優(yōu)解。證明：對任X，有CXby=CXX最優(yōu)推論1、(P),(D)都有可行解，則必都有最優(yōu)解。定理4(主對偶定理)若一對對偶問題(P)和(D)都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：(1)當(dāng)X*和Y*為原問題和對偶問題的一個可行解有原問題目標(biāo)函數(shù)值對偶問題目標(biāo)函數(shù)值所以原問題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對偶問題有下界，也存在有限最優(yōu)解。(2)當(dāng)X*為原問題的一個最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過引入松弛變量Xs,將問題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令令所以Y*是對偶問題的可行解，對偶問題的目標(biāo)函數(shù)值為X*是原問題的最優(yōu)解，原問題的目標(biāo)函數(shù)值為推論：若一對對偶問題中的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對對偶問題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個都無可行解；一個問題無界，則另一問題無可行解。定理5

若X,Y分別為(P),(D)的可行解，則X,Y為最優(yōu)解的充要條件是同時成立證:(必要性）原問題對偶問題y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于04.3影子價格對偶單純形法的基本思想從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行(正則解)，但它對應(yīng)著一個對偶基可行解（檢驗數(shù)非正），所以也可以說是