人工變量法和兩階段法課件

人工變量法和兩階段法

對于一般的線性規(guī)劃問題，在用單純形法求解之前，總是先化為標準型。如果在系數(shù)矩陣中有一個單位陣，則可以作為初始可行基。如果約束條件的系數(shù)矩陣中不存在單位矩陣，則可以通過添加人工變量的方法，在標準型的約束方程的系數(shù)矩陣中人為地構(gòu)造一個單位陣，從而獲得初始可行基，再作進一步迭代。上周內(nèi)容回顧

在單純形迭代過程中，要求人工變量逐步從基變量被替換出，變?yōu)榉腔兞?，最后，基變量中不含有人工變量。為使人工變量被替換出成為非基變量，有1.大M法2.兩階段法1.大M法：在目標函數(shù)求最大值的線性規(guī)劃問題中，設(shè)人工變量在目標函數(shù)中的系數(shù)為-M，M為任意大的正數(shù)。只要人工變量不為零，目標函數(shù)最大值就是一個任意小的數(shù)。兩階段法

第一階段：希望人工變量等于0，為此，構(gòu)造只含人工變量的目標函數(shù)，并要求實現(xiàn)最小化。用單純形法求解上述模型，若得到W=0,則必有x6=x7=0。說明原問題存在基可行解，可以進行第二階段計算，否則原問題無可行解，應(yīng)停止計算。第二階段：將第一階段計算得到的最終表，去掉人工變量，將目標函數(shù)換為原問題的目標函數(shù)，作為第二階段計算的初始表，繼續(xù)單純形法，直至求得最優(yōu)解。無可行解在大M法中判斷:檢驗數(shù)全部小于等于零且有人工變量為基變量，則此線性規(guī)劃模型無可行解。無可行解在兩階段法中判斷:如果第一階段求解結(jié)果最優(yōu)解的目標函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原LP問題無可行解。4.1對偶模型的提出4.2原模型與對偶模型的線性規(guī)劃模型之間的關(guān)系4.3對偶模型的基本性質(zhì)4.4對偶模型的經(jīng)濟意義——影子價格4.5對偶模型最優(yōu)解和影子價格4.6對偶單純形法第4章對偶模型4.2原模型與對偶模型的線性規(guī)劃模型之間的關(guān)系定義1具有下列特點的線性規(guī)劃模型稱為對稱形式的線性規(guī)劃模型，變量均具有非負約束，其約束條件為當目標函數(shù)求最大時取“≤”、目標函數(shù)求最小時取“≥”。4.2.1對稱形式線性規(guī)劃模型的對偶模型原問題中各系數(shù)矩陣為它的對偶問題是：4.2.2一般形式的線性規(guī)劃模型與對偶模型之間的關(guān)系對于非對稱形式的線性規(guī)劃模型如何寫出其對偶模型？其思路是首先將非對稱形式轉(zhuǎn)換為對稱形式，然后再按照對應(yīng)關(guān)系寫出其對偶模型。原問題求極小------原問題約束方程有“≥”------兩邊同乘（-1），“≤”原問題約束方程有“=”------對偶問題？【例4-3】寫出下列線性回歸模型的對偶模型原問題約束方程有“=”，如何轉(zhuǎn)化？原問題：對偶問題：對稱形式線性規(guī)劃模型的對偶模型將條件2兩端同乘-1，并將條件3、4合并為等式，得原問題目標函數(shù)約束條件右端項目標函數(shù)中變量的系數(shù)約束矩陣A對偶問題目標函數(shù)目標函數(shù)中變量的系數(shù)約束條件右端項A的轉(zhuǎn)置為約束矩陣原問題(或?qū)ε紗栴})對偶問題(或原問題)目標函數(shù)maxZn個變量變量≥0變量≤0變量無限制目標函數(shù)minWn個約束約束≥約束≤約束=約束m個約束≤約束≥約束=約束右端項目標函數(shù)系數(shù)m個變量變量≥0變量≤0變量無限制目標函數(shù)系數(shù)約束右端項原模型與對偶模型之間的關(guān)系Maxw=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3≥≤≤=y1≥0,y2≤0,y3無約束設(shè)對偶變量為y1,y2,y3,對偶問題模型為：

【例4-4】寫出下列線性規(guī)劃模型的對偶模型23-51≤2≥4.3對偶模型的基本性質(zhì)對稱性弱對偶性最優(yōu)解性強對偶性（對偶定理）互補松弛性（1）原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。（2）如原問題有可行解且目標函數(shù)值無界（或具有無界解），則其對偶問題無可行解；反之對偶問題有可行解且目標函數(shù)值無界，則其原問題無可行解（注意：本點性質(zhì)的逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無可行解，反之亦然）。由弱對偶性可得出以下推論：（3）若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數(shù)值無界。試用對偶理論證明上述問題無最優(yōu)解。例已知線性規(guī)劃問題對偶問題X（0）=（0，0，0）T是原問題的一個可行解原問題對偶問題不可行若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界。y1≥0，y2≥0，不滿足該約束條件性質(zhì)3

最優(yōu)性

設(shè)是原問題的可行解，是對偶問題的可行解，當時，是最優(yōu)解。利用弱對偶定理同理可知,也是最優(yōu)解.對任何可行解，均有，故是目標函數(shù)取值最小的可行解，因而是最優(yōu)解。性質(zhì)4強對偶性（對偶定理）若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標函數(shù)最優(yōu)值相等。證：設(shè)是原問題的最優(yōu)解，它對應(yīng)的基矩陣必存在，即得到若這時是對偶問題的可行解，它使因原問題的最優(yōu)解使目標函數(shù)取值

由此得到可見是對偶問題的最優(yōu)解。原問題與對偶問題的解和目標函數(shù)值之間的關(guān)系原問題關(guān)系對偶問題目標函數(shù)最優(yōu)解無界解無可行解最優(yōu)解無可行解無界解Z*=W*性質(zhì)5互補松弛性設(shè)X*和Y*分別原問題和對偶問題的可行解，那么Y*XS*=0和YS*X*=0，當且僅當X*，Y*是最優(yōu)解。AX*≤bAX*+XS*=bXS*=b-AX*Y*（b-AX*)=0Y*XS*=0充分必要條件Y*（b-AX*)=0(Y*A-C)X*=0對偶變量不為0，原問題相應(yīng)約束式是等式原問題約束為不等式，相應(yīng)對偶變量為0最優(yōu)解點

已知線性規(guī)劃問題【例4-5】已知線性規(guī)劃模型（1）寫出該模型的對偶模型（2）已知原模型的最優(yōu)解為：X=（2，2，4，0）T根據(jù)對偶理論，直接求對偶模型的最優(yōu)解。（1）對偶模型是：（2）已知原模型的最優(yōu)解為：X=（2，2，4，0）T根據(jù)對偶理論，直接求對偶模型的最優(yōu)解。（2）根據(jù)原模型的最優(yōu)解為X=（2，2，4，0）T將其代入原問題的約束條件，得原模型的松弛變量：

x5=0，x6=0，x7=1，x8=0約束條件

(3)為嚴格不等式，由互補松弛定理知：y3*=0由原模型的最優(yōu)解為X=（2，2，4，0）T，根據(jù)互補松弛定理知：y5=0，y6=0，y7=0，求解上面的方程組得：y1*=4/5，y2*=3/5，y3*=0,y4*=1設(shè)對偶模型的剩余變量為y5，y6，y7，y8，當某約束條件的右端常數(shù)增加一個單位時（假設(shè)原問題的最優(yōu)基不變），原問題的目標函數(shù)最優(yōu)值增加的數(shù)量。目標函數(shù)Z=CBB-1b和檢驗數(shù)CN-CBB-1N中都有乘子Y=CBB-1,Y的經(jīng)濟意義？設(shè)B是的最優(yōu)解，則該基所對應(yīng)最優(yōu)解的目標函數(shù)值

Z*=CBB-1b=Y*b由此4.4對偶模型的經(jīng)濟意義——影子價格當某個右端常數(shù)bibi+1時第i種資源的影子價格是第i個約束條件的右端常數(shù)增加一個單位時，目標函數(shù)增加的數(shù)量

在【例4-1】中，當原問題和對偶問題都取得最優(yōu)解時，這一對線性規(guī)劃對應(yīng)的目標函數(shù)值相等，即有：

其中X*=（75，15）T，是原問題的最優(yōu)解，

y*=（5，0，0.5）T是對偶問題最優(yōu)解。若甲原料供應(yīng)量能增加一個單位，即右端常數(shù)向量b=(90，490，240)T中的b1從90個單位增加到91個單位，則目標函數(shù)值的變化量為：

對偶變量的意義——代表在資源最優(yōu)利用條件下對單位第種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格（shadowprice)。

y1*=5描述了在生產(chǎn)最優(yōu)安排下，原料甲的變動給總利潤帶來的影響。

1．資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。2．影子價格是一種邊際價格。在式中，。說明的值相當于在資源得到最優(yōu)利用的生產(chǎn)條件下，每增加一個單位時目標函數(shù)的增量。影子價格的經(jīng)濟意義3．資源的影子價格實際上又是一種機會成本.

在純市場經(jīng)濟條件下,當資源的市場價格低于影子價格時，可以買進這種資源用于擴大生產(chǎn)；相反當市場價格高于影子價格時，就會賣出這種資源獲利。隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)，因此影子價格具有市場調(diào)節(jié)的作用。4．在對偶問題的互補松弛性質(zhì)中有

這表明生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。5．從影子價格的含義上考察單純形表的檢驗數(shù)的經(jīng)濟意義?！趈種產(chǎn)品的產(chǎn)值或者利潤—生產(chǎn)第j中產(chǎn)品所消耗各項資源的影子價格的總和。（即隱含成本）可見，產(chǎn)品產(chǎn)值或者利潤>隱含成本可生產(chǎn)該產(chǎn)品；否則，不安排生產(chǎn)?！獧z驗數(shù)的經(jīng)濟意義6．一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種估價直接涉及到資源的最有效利用。經(jīng)濟學(xué)研究如何管理自己的稀缺資源原問題的最終單純形表中松弛變量的檢驗數(shù)對應(yīng)對偶問題的最優(yōu)解。如何從單純形表中找到影子價格？4.5對偶模型最優(yōu)解和影子價格4.5.1對偶模型的最優(yōu)解對偶模型與原模型單純形表之間的關(guān)系設(shè)B是原問題的一個基，

A=(B,N),原問題可改寫為其相應(yīng)的對偶問題為對偶問題原問題的單純形表XBXNXS取YS1為對偶問題的非基變量,即有YS1=0,故可得對偶問題的一個基解.Y=CBB-1