運(yùn)籌學(xué)課件及課后答案對偶理論

運(yùn)籌帷幄之中決勝千里之外對偶理論運(yùn)籌學(xué)課件對偶理論對偶問題對偶理論對偶單純形算法對偶問題的提出例：設(shè)某企業(yè)有m種資源，用于生產(chǎn)n種不同的產(chǎn)品，各種資源的擁有量為bi（i=1,2,…m）,又知生產(chǎn)單位第j種產(chǎn)品（j=1,2,…n）消費(fèi)第i種資源aij單位，產(chǎn)值為cj元。若用xj表示第j種產(chǎn)品的生產(chǎn)量，求產(chǎn)值最大，LP模型為：任意線性規(guī)劃問題都存在一個(gè)與之伴隨的對偶問題現(xiàn)從另一角度提出問題：假設(shè)此企業(yè)擁有資源但未生產(chǎn)，而另一企業(yè)預(yù)將上述企業(yè)擁有的資源買過來，至少應(yīng)付出多少代價(jià)，才能使前一企業(yè)愿意放棄生產(chǎn)活動(dòng)，出讓資源。若設(shè)yi表示收買該企業(yè)一單位i種資源時(shí)付出的代價(jià)。則另一線性規(guī)劃問題為：收買的企業(yè)付出的代價(jià)是該商品的價(jià)格嗎？若不是，它和原本的價(jià)格是什么關(guān)系？收購資源的企業(yè)能賺錢嗎?怎么賺？原問題與對偶問題對應(yīng)關(guān)系原問題（L）一一對應(yīng)對偶問題（D）max問題min問題有m個(gè)約束條件有m個(gè)變量第j個(gè)約束條件為≤關(guān)系第j個(gè)變量≥0第j個(gè)約束條件為≥關(guān)系第j個(gè)變量≤0第j個(gè)約束條件為等式關(guān)系第j個(gè)變量無非負(fù)約束，自由變量第j個(gè)變量≥0第j個(gè)約束條件為≥關(guān)系第j個(gè)變量≤0第j個(gè)約束條件為≤關(guān)系第j個(gè)變量無非負(fù)約束，自由變量第j個(gè)約束條件為＝關(guān)系資源向量價(jià)值向量價(jià)值向量資源向量實(shí)例對偶問題的基本性質(zhì)以下各性質(zhì)基于如下假設(shè)原問題對偶問題若是原問題的可行解，是其對偶問題的可行解，則恒有證明性質(zhì)1（弱對偶性）若是原問題的可行解，是其對偶問題的可行解，且有則是原問題的最優(yōu)解，是其對偶問題的最優(yōu)解。性質(zhì)2（最優(yōu)性）性質(zhì)2證明又因?yàn)閯t性質(zhì)3（無界性）：若原問題（對偶問題）有無界解，則其對偶問題（原問題）無可行解。性質(zhì)4（強(qiáng)對偶性，對偶定理）：若原問題有最優(yōu)解，則其對偶問題也一定有最優(yōu)解，且maxz=minw。在線性規(guī)劃問題的最優(yōu)解中，若對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之若約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。即（另外說法）：分別是原問題和對偶問題的可行解，則為最優(yōu)解的充分必要條件是性質(zhì)5（互補(bǔ)松弛性）性質(zhì)5證明化原問題和對偶問題為標(biāo)準(zhǔn)形式原問題對偶問題若則則為最優(yōu)解.為最優(yōu)解.則所以設(shè)原問題和對偶問題為原問題對偶問題性質(zhì)6（變量對應(yīng)關(guān)系）則，原問題單純形表的檢驗(yàn)數(shù)行對應(yīng)其對偶問題的一個(gè)基解。（對應(yīng)關(guān)系見表）性質(zhì)6證明設(shè)B是原問題的一個(gè)可行基，所以相應(yīng)的對偶問題為若求得原問題的以解檢驗(yàn)數(shù)為和令將它代入（*）,(**),得對偶問題性質(zhì)的趣味應(yīng)用原問題（L）對偶問題（D）第j個(gè)約束條件為嚴(yán)格的不等式對應(yīng)的第j個(gè)變量值=0第j個(gè)約束條件為等式對應(yīng)的第j個(gè)變量值≥0第j個(gè)變量值＞0對應(yīng)的第j個(gè)約束條件為等式對偶問題（D）原問題（L）第j個(gè)約束條件取嚴(yán)格的不等式對應(yīng)的第j個(gè)變量值=0第j個(gè)約束條件取等式對應(yīng)的第j個(gè)變量值≥0第j個(gè)變量值＞0對應(yīng)的第j個(gè)約束條件為等式對偶問題（D）原問題（L）第1個(gè)約束a1y*>c1

第1個(gè)變量x1*=0第2個(gè)約束a2y*>c2

第2個(gè)變量x2*=0………第k個(gè)約束aky*=ck

第k個(gè)變量xk*≥0…………第n個(gè)約束any*>cn第n個(gè)變量xn*=0第1個(gè)變量y*＞0第1個(gè)約束a1x1*+a2x2*+…akxk*+…+anxn*=b化簡得，akxk*=b.Min=2x1＋3x2＋5x3＋2x4＋3x5原問題（L）x1＋x2＋2x3＋x4＋3x5≥42x1－x2＋3x3＋x4＋x5≥3xj≥0,j=1,2,…,5Maxz=4y1＋3y2對偶問題（D）y1＋2y2≤2y1－y2≤32y1＋3y2≤5y1＋y2≤23y1＋y2≤3

y1,y2≥0對偶問題（D）原問題（L）第1個(gè)約束y1*

＋2y2*

=2第1個(gè)變量x1*≥0第2個(gè)約束y1*

－y2*

＜3第2個(gè)變量x2*=0第3個(gè)約束2y1*

＋3y2*

＜5第3個(gè)變量x3*=0第4個(gè)約束y1*

＋y2*

＜2第4個(gè)變量x4*=0第5個(gè)約束3y1*

＋y2*

=3第5個(gè)變量x5*≥0第1個(gè)變量y1*＞0第1個(gè)約束x1*＋x2*＋2x3*＋x4*＋3x5*=4第2個(gè)變量y2*＞0第2個(gè)約束2x1*－x2*＋3x3*＋x4*＋x5*=3原問題變量在基B下的劃分基變量XB非基變量XN松弛變量XS原問題單純形表中的檢驗(yàn)向量0CN-CBB－1N-CBB－1對偶問題的基解松弛變量YS1松弛變量YS2-Y最優(yōu)單純形表原問題L對偶問題D原問題L一般形式MaxZ=2x1＋3x2x1＋2x2≤84x1≤164x2≤12x1,x2≥0原問題L標(biāo)準(zhǔn)形MaxZ=2x1＋3x2x1＋2x2＋x3=84x1

＋x4=164x2＋x5=12x1,x2,x3,x4,x5≥0x3,x4,x5是松弛變量Min=8y1＋16y2＋12y3y1＋4y2≥22y1＋4y3≥4y1,y2,y3≥0對偶問題D的最優(yōu)解：y1*=3/2y2*=1/8y3*=0影子價(jià)格隨具體情況而異：在完全市場經(jīng)濟(jì)條件下，當(dāng)某種資源的市場價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)該買進(jìn)該資源用于擴(kuò)大生產(chǎn)；當(dāng)某種資源的市場價(jià)格高于影子價(jià)格時(shí)，企業(yè)應(yīng)該把該資源賣掉。所以，影子價(jià)格具有市場調(diào)節(jié)作用。對偶單純形算法基本思想算法過程算例原問題對偶問題基本思想單純形算法對偶單純形算例

cj-15-24-500cBxBby1y2y3y4y50y4-20[-6]-1100y5-1-5-2-101

Cj-zj-15-24-500-24y21/3011/6-1/600y5-1/3-50[-2/3]-1/31

Cj-zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2

Cj-zj-15/200-7/2-3/2例：用對偶單純形法求解解：將問題化為下式，以得到對偶問題的初始可行基

cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4[-2]1-301

Cj-zj-2-3-4000x4-10[-5/2]1/21-1/2-2x121-1/23/20-1/2

Cj-zj0-4-10-1-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5

Cj-zj00-3/5-8/5-1/5否算法框圖初始正則解檢查可行是則停止得最優(yōu)解選出基變量檢查是否無可行解是則停止否無最優(yōu)解選入基變量計(jì)算檢驗(yàn)數(shù)靈敏度分析靈敏度分析研究的問題單純行表中基的位置：為清楚起見，把新單純行表中的基對應(yīng)的初始單純行表中的那些向量抽出來單獨(dú)列一塊，記為B，初始單純行表為：初始解非基變量基變量bBN0…0單純行法的迭代過程實(shí)際上是對約束方程的系數(shù)矩陣實(shí)施行的初等變換，由線代知道，對矩陣基可行解基變量非基變量0…0實(shí)施行的初等變換時(shí)，當(dāng)B變?yōu)镮時(shí)，I將變?yōu)閯t，上述矩陣將變?yōu)樾聠渭冃斜韺憺椋红`敏度分析的步驟：1。將參數(shù)的改變計(jì)算反應(yīng)到最終單純形表上：具體方法是，按下列公式計(jì)算由參數(shù)的變化而引起的最終單純形表上有關(guān)數(shù)字的變化：2。檢查原問題是否仍為可行解；3。檢查對偶問題是否仍為可行解；4。按下表所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟：原問題對偶問題結(jié)論（繼續(xù)計(jì)算的步驟）可行解可行解非可行解非可行解可行解非可行解可行解非可行解仍為問題最優(yōu)解單純形法繼續(xù)求最優(yōu)解對偶單純形法繼續(xù)求最優(yōu)解引入人工變量，用新表計(jì)算將cj的改變反應(yīng)到最終單純形表上,只能出現(xiàn)上頁表中所示的前兩種情形。例：已知LP問題用單純形法求解得最終單純形表如下：

cj21000cBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/2（表1）試確定：a）當(dāng)目標(biāo)函數(shù)變?yōu)樽顑?yōu)解會如何變化；b）當(dāng)目標(biāo)函數(shù)變?yōu)榍蟮淖兓秶?，使最?yōu)解不變。a)將cj的改變反應(yīng)到最終單純形表（1）上,得表（2）

cj51.5000cBxBbx1x2x3x4x50x315/20015/4-15/25x17/21001/4-1/21.5x23/2010-1/4[3/2]

Cj-zj000-7/81/4（表2）表（2）中變量x5的檢驗(yàn)數(shù)為正，繼續(xù)迭代得表（3）

cj51.5000cBxBbx1x2x3x4x50x315051005x1411/301/600x5102/30-1/61

Cj-zj0-1/60-5/60（表3）即新解為b)將cj的改變反應(yīng)到最終單純形表（1）上,得表（4）

cj2＋1000cBxBbx1x2x3x4x50x315/20015/4-15/22＋x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/4-1/2+1/2（表4）二、分析bi變化的影響bi的變化在實(shí)際問題中表明可用資源的數(shù)量發(fā)生變化，將bi的改變反應(yīng)到最終單純形表上,只引起基變量列數(shù)字變化。所以靈敏度分析的步驟為：1）按公式算出將其加到基變量列的數(shù)字上；2）因?yàn)槠鋵ε紗栴}仍為可行解，故只需檢查原問題是否為可行解。例：上例中：a）當(dāng)?shù)诙€(gè)約束條件的右端項(xiàng)增大到32最優(yōu)解會如何變化；b）當(dāng)?shù)诙€(gè)約束條件變?yōu)榍蟮淖兓秶?，使表中基為最?yōu)基解：a）將其加到表（1）的最終單純形表的基變量b這一列數(shù)字上得表（5）

cj21000cBxBbx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2

Cj-zj000-1/4-1/2（表5）表（5）中原問題為非可行解，故用對偶單純形法繼續(xù)計(jì)算得表（6）

cj21000cBxBbx1x2x3x4x50x315051002x15110010x420－401－6

Cj-zj0－100-2（表6）即新解為解：b）將其加到表（1）的最終單純形表的基變量b這一列數(shù)字上得表（7）

cj21000cBxBbx1x2x3x4x50x3(15/2)+5/40015/4-15/22x1(7/2)+1/41001/4-1/21x2(3/2)-1/4010-1/43/2

Cj-zj000-1/4-1/2（表7）表中基為最優(yōu)基的條件為：所以有：三、增加一個(gè)變量的分析增加一個(gè)變量在實(shí)際問題中表明增加一種新產(chǎn)品。靈敏度分析的步驟為：1）計(jì)算2）計(jì)算3）若只需將和的值直接反映到最終單純形表中，原最優(yōu)解不變，若則按單純形表繼續(xù)迭代計(jì)算。例：在前例中，若增加一個(gè)變量x6，有試分析最優(yōu)解的變化。解：將其反映到表（1）的最終單純形表中，得表（8）

cj21000cBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/2（表8）3x6-70[2]1所以，用單純形法繼續(xù)計(jì)算，得表（9）

cj21000cBxBbx1x2x3x4x50x35/407/213/8-9/42x17/21001/4-1/23x63/401/20-1/83/4

Cj-zj0-1/20-1/8-5/43x60010（表9）即新解為四、分析aij變化的影響假如xj在最終表中為基變量，則aij的變化將使最終表中的B-1變化，因此，有可能出現(xiàn)原問題與對偶問題均為非可行解的情況。例：在前例中，若x2系數(shù)向量p2變?yōu)樵嚪治鲎顑?yōu)解的變化。解：先將其作為一個(gè)新的變量x2/,列入最終單純形表中，得表（10）

cj21300cBxBbx1x2X/2x3x40x315/20011/215/42x17/2101/201/41x23/201-1/20-1/4

Cj-zj003/20-1/40x5-15/2-1/23/2-1/2（表10）因x2已變化為x/2，故用單純形法算法將x/2替換出基變量中的x2，并在下一個(gè)表中不再保留x2，得表（11）

cj23000cBxBbx1x/2X3x4x50x3-90014-242x121001/2-23x/23010-1/23

Cj-zj0001/2-5（表11）因表（11）中原問題與其對偶問題均為非可行解，所以通過引入人工變量，將原問題轉(zhuǎn)化為可行解，再用單純形法繼續(xù)計(jì)算。表（11）的第一行可寫成因?yàn)?，右端?xiàng)為負(fù)值，故先將等式兩端乘“－1”，再加上人工變量x6，得將上式替換表（11）的第一行，得表（12）

cj23000cBxBbx1x/2X3x4x5-Mx6900-1-4-242x121001/2-23x/23010-1/23

Cj-zj00-M-4M+1/2-5+24M（表12）-Mx61000用單純形法迭代，得表（13）

cj23000cBxBbx1x/2X3x4x50x53/800-1/24-1/612x111/410-1/121/303x/215/8011/800

Cj-zj00-5/24-2/30（表13）-Mx61/241/12-1/8-M+5/24即新解為五、增加一個(gè)約束條件的分析增加一個(gè)約束條件，在實(shí)際問題中相當(dāng)于增添一道工序。分析的方法是先將原問題的最優(yōu)解變量取值代入這個(gè)新增的約束條件中，如滿足，說明新增約束未起到限制作用，原最優(yōu)解不變。否則，將新增約束直接反映到最終單純形表中，再進(jìn)行分析。例：前例中增添一個(gè)約束條件試分析最優(yōu)解變化。解：先將原問題最優(yōu)解變量值代入，因?yàn)橛泄剩瑢⒓s束條件寫成，并取x6為基變量，直接反映到最終單純形表中，得表（14）

cj21000cBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/2（表14）0x600010x612320000迭代，得表（15）

cj21000cBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/2（表15）0x600010x6-3/2000-1/4[-3/2]0為使x1,x2列系數(shù)變換為單位向量，對表（14）進(jìn)行行的變換，表（15）中1，2，3行同表（14）中1，2，3行不變，表（15）中第4行由初等行變換“4行－3×2行－2×3行”得到，用對偶單純形法計(jì)算，得表（16）

cj21000cBxBbx1x2x3x4x50x3150015/202x141001/301x20010-1/20

Cj-zj000-1/60（表16）0x6-5-1/31-2/30x510001/61-1/3即新解為

參數(shù)線性規(guī)劃靈敏度分析研究：（1）當(dāng)模型中參數(shù)aij、bi、cj改變到某一數(shù)值時(shí)對最優(yōu)解的影響；（2）這些參數(shù)在什么范圍內(nèi)變化時(shí)最優(yōu)解不變。參數(shù)線性規(guī)劃研究：當(dāng)這些參數(shù)超出這個(gè)范圍時(shí)，最優(yōu)解將怎么變化。例：前例中，第三個(gè)約束條件的右端項(xiàng)不斷增大時(shí)，分析最優(yōu)解將怎么變化。解：令則問題等價(jià)于參數(shù)線性規(guī)劃求解步驟：（1）令求解，得最終單純形表（表0）

cj21000cBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2

Cj-zj000-1/4-1/2（表0）（2）將參數(shù)的變化反映到最終單純形表中。