【正文】 解：當(dāng)λ1=λ2=0時(shí)，對(duì)應(yīng)的最終表為：cj23000CBBbX1X2X3X4X52X13101/201/50X4400214/53X2301001/5σj00101/5（1）分析λ1的影響當(dāng)λ2=0時(shí)，將λ1反映到最終表得到cj2+λ13000CBBbX1X2X3X4X52+λ1X13101/201/50X4400214/53X2301001/5σj0011/2λ101/5+1/5λ1為使表中解為最優(yōu)解，條件是當(dāng)時(shí)，滿足要求。若基變量的取值沒有負(fù)數(shù)，則原問題的基解是可行解；若檢驗(yàn)數(shù)沒有正數(shù)，則對(duì)偶問題的基解是可行解。（5）增加新工序：即增加一個(gè)約束條件，直接反映到最終表中。時(shí)，最終表中對(duì)應(yīng)的系數(shù)列向量變?yōu)?B1Pj180。即(△b)180。=B1（b+△b） = B1 b+ B1△b = b180。（1）cj的變化：利用公式計(jì)算或直接反映到最終表中，即重新計(jì)算檢驗(yàn)數(shù)。若不滿足，則繼續(xù)迭代，直到找到最優(yōu)解為止。因此有可能把個(gè)別參數(shù)的變化直接在計(jì)算得到的最優(yōu)解的單純形表上體現(xiàn)出來(lái)。當(dāng)線性規(guī)劃問題中的一個(gè)或者幾個(gè)參數(shù)變化時(shí)，可以用單純形從頭計(jì)算，看最優(yōu)解有無(wú)變化，這樣做思路簡(jiǎn)單，但計(jì)算很麻煩。通常將需要進(jìn)行分析的參數(shù)分成三組：cj ——目標(biāo)函數(shù)系數(shù)的變化，即市場(chǎng)條件的改變； bi ——約束右端項(xiàng)的變化，即資源擁有量的改變；Pj ——約束左端系數(shù)的變化，即工藝技術(shù)條件的改變。而在線性規(guī)劃問題中的靈敏度分析是指研究基礎(chǔ)數(shù)據(jù)發(fā)生波動(dòng)后對(duì)最優(yōu)解的影響，即分析問題中一個(gè)或多個(gè)參數(shù)發(fā)生變化時(shí)，最優(yōu)解將如何改變；或者分析參數(shù)在一個(gè)怎樣的范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。第六節(jié) 靈敏度分析廣義靈敏度分析又稱敏感性分析或優(yōu)化后分析，是對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度的分析。對(duì)后一種情況的判斷準(zhǔn)則是：當(dāng)某個(gè)基變量的取值br小于0時(shí)，這一行所有的系數(shù)都非負(fù)即arj≥0(j=1,2,...,n)，此時(shí)不妨假設(shè)對(duì)應(yīng)的第r行的約束方程為：因?yàn)閍rj≥0(j=m+1,...,n),且br0,所有不可能存在滿足xj≥0(j=1,2,...,n)的解。因此對(duì)偶單純形法一般不單獨(dú)使用，而主要應(yīng)用于下一節(jié)將要介紹的靈敏度分析中。注意：（1）用對(duì)偶單純形法求解線性規(guī)劃問題時(shí)，當(dāng)約束條件為≥時(shí)，不必引入人工變量，可使計(jì)算簡(jiǎn)化。利用初等行變換將[5]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表28）表28cj12161500CBBby1y2y3y4y50y42[2]401015Y33/52/50101/5σj616003θ34注意表中y4為換出變量；依照比值的計(jì)算規(guī)則故變量y1為換入變量，從而元素2為主元（用[]標(biāo)記），再將[2]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表29）表29cj12161500CBBby1y2y3y4y512Y111201/2015Y31/504/511/51/5σj04033表29中所有基變量的取值均非負(fù)，得到最優(yōu)解Y=(1,0,1/5)T,Wmin=15,進(jìn)一步由于非基變量的檢驗(yàn)數(shù)全小于0，該問題有唯一最優(yōu)解。 0，即保證對(duì)偶問題為可行解。二、對(duì)偶單純形法的計(jì)算步驟 化線性規(guī)劃問題的約束條件為≤形式，且引入松弛變量建立初始單純形表；若所有右端常數(shù)項(xiàng)bi≥0，則最優(yōu)解已經(jīng)達(dá)到，否則令，即選取bl所對(duì)應(yīng)的變量為換出基的變量（簡(jiǎn)稱換出變量）；計(jì)算比值，并選取所對(duì)應(yīng)的變量為換入基的變量（簡(jiǎn)稱為換入變量）；稱為主元素或主元，常用方括號(hào)[ ]標(biāo)記，利用主元進(jìn)行迭代，即通過(guò)矩陣的初等行變換，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即主元aik變?yōu)?，同列中其它元素變?yōu)?，轉(zhuǎn)第2 步。也就是說(shuō)，求解線性規(guī)劃問題時(shí)，在保持檢驗(yàn)數(shù)全非正的前提下，可以從原問題的一個(gè)基解（一般不是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值減少，當(dāng)?shù)皆瓎栴}出現(xiàn)可行解時(shí)，即找到了該問題的最優(yōu)解，這就是對(duì)偶單純形法。由對(duì)偶理論可以知道，單純表中同時(shí)反映原問題與對(duì)偶問題的互補(bǔ)的基解，故可以從求對(duì)偶問題最優(yōu)解的角度求解原問題的最優(yōu)解。單純形法可以解釋為：在保持原問題可行性的前提下，使目標(biāo)函數(shù)值不斷增大，向?qū)ε紗栴}可行解的方向迭代。第五節(jié) 對(duì)偶單純形法一、對(duì)偶單純形法的基本思路對(duì)偶單純形法是求解線性規(guī)劃的另一種基本方法。一般說(shuō)來(lái)對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。當(dāng)產(chǎn)品的產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排該項(xiàng)產(chǎn)品，否則用這些資源來(lái)生產(chǎn)其它產(chǎn)品更有利，即不在生產(chǎn)計(jì)劃中安排該項(xiàng)產(chǎn)品。用影子價(jià)格解釋檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。由對(duì)偶問題的互補(bǔ)松弛性知在最優(yōu)配置下，若資源bi未得到充分利用，則影子價(jià)格yi為0；若影子價(jià)格yi大于0，則表明該資源bi在生產(chǎn)中已經(jīng)耗費(fèi)。當(dāng)yimi 時(shí)，企業(yè)愿意購(gòu)進(jìn)這種資源，可獲單位純利為yi－mi，即有利可圖；當(dāng)yimi 時(shí)，企業(yè)愿意有償轉(zhuǎn)讓這種資源，可獲單位純利為mi－yi，否則企業(yè)無(wú)利可圖，甚至虧損。圖21是本章LP1用圖解法求解時(shí)的情形，圖中陰影線部分為問題可行域，點(diǎn)(3,3)是最優(yōu)解，代入目標(biāo)函數(shù)的zmax=，對(duì)應(yīng)y1=，即設(shè)備A的影子價(jià)格為1；類似的當(dāng)b2增加1個(gè)單位時(shí)，z無(wú)變化，對(duì)應(yīng)y2=0，設(shè)備B的影子價(jià)格為0；當(dāng)b3增加1個(gè)單位時(shí)，對(duì)應(yīng)y3=，.影子價(jià)格還是一種機(jī)會(huì)成本。影子價(jià)格是一種邊際價(jià)格。 若原問題是非可行解，而對(duì)偶問題是可行解，則相應(yīng)解代入目標(biāo)函數(shù)后有z：一對(duì)互補(bǔ)的基解代入目標(biāo)函數(shù)原問題可行解非可行解對(duì)偶問題可行解最優(yōu)解zzmax非可行解zzmax不確定第四節(jié) 影子價(jià)格從上節(jié)對(duì)偶問題的基本性質(zhì)看出，在單純形法的每一步迭代中有一對(duì)互補(bǔ)的基解，代入目標(biāo)函數(shù)有其中bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，表示第i種資源的擁有量；而對(duì)偶變量yi的意義表示對(duì)一個(gè)單位的第i種資源的估價(jià)，這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作出的估價(jià)，為區(qū)別起見稱為第i種資源的影子價(jià)格（shadow price）.資源的市場(chǎng)價(jià)格只隨市場(chǎng)的供求關(guān)系變化，在企業(yè)內(nèi)通常是穩(wěn)定的；而它的影子價(jià)格則有賴于資源的利用情況。又有z = CX =CB B1b= YTb= w，表明這對(duì)互補(bǔ)的基解代入各自目標(biāo)函數(shù)值相等。證明：最終表中Xj的檢驗(yàn)數(shù)滿足σj=zjcj= CB B1Pjcj，記YT=CB B1即zjcj= YTPjcj,所以即(zjcj)在對(duì)偶問題的約束條件中相當(dāng)于剩余變量。因此互補(bǔ)松弛性也稱為“由松得緊性”。性質(zhì)5 互補(bǔ)松弛性證明：注意：通常把最優(yōu)解中的非零變量稱為松變量，而為0變量稱為緊變量；將最優(yōu)解代入約束條件中成為嚴(yán)格不等式的稱為松約束，而成為嚴(yán)格等式的稱為緊約束。 0， 即Y*是對(duì)偶問題的可行解，且滿足 CX* = CB b ′ =CB (B1 b) = CB B1b = Y*T b= b TY* 由最優(yōu)性有Y*是對(duì)偶問題的最優(yōu)解。 CT 又因?yàn)閟 S′ = CBB1 = Y * T 163。 C令 CBB1 = Y* T，有 Y*T A 179。即 s = C CB B1 A 163。綜上所述，對(duì)于給定的原問題和對(duì)偶問題，則下面三種情況必有其一：① 都有最優(yōu)解② 都無(wú)可行解③ 一個(gè)無(wú)可行解，而另一個(gè)問題有無(wú)界解。，分析最優(yōu)解的情況。即若原問題無(wú)可行解，則對(duì)偶問題可能無(wú)可行解，也可能有無(wú)界解，也可以統(tǒng)稱為對(duì)偶問題無(wú)最優(yōu)解。也可以敘述為，若對(duì)偶問題有無(wú)界解，則原問題無(wú)可行解。性質(zhì)2 最優(yōu)性： 若 X* 和 Y* 分別是 P 和 D 的可行解且 CX* = bT Y* ， 則X*，Y*分別是問題 P和D 的最優(yōu)解。 ，兩者分別添加松弛變量和剩余變量后為：用單純形法和兩階段法求得兩個(gè)問題的最終單純形表分別見表24和表25表24cj原問題變量原問題的松弛變量CBBbX1X2X3X4X50X13101/201/50X4400214/53X2301001/5σj00101/5Y4Y5Y1Y2Y3對(duì)偶問題的剩余變量對(duì)偶問題表25cj對(duì)偶問題變量對(duì)偶問題的剩余變量CBBbY1Y2Y3Y4Y516Y111201/2015Y31/504/511/51/5σj04033X3X4X5X1X2原問題的松弛變量原問題變量從這兩張表中可以清楚地看出兩個(gè)問題變量之間的對(duì)應(yīng)關(guān)系，使得我們只需要求解其中一個(gè)問題，從最優(yōu)解的單純形表中同時(shí)可以得到另一個(gè)問題的最優(yōu)解。常稱CB B1為單純形乘子，記作YT，即YT=CB B1，則YT滿足下列關(guān)系：從而說(shuō)明最終表中檢驗(yàn)數(shù)行的相反數(shù)恰好是對(duì)偶問題的一個(gè)可行解，將這個(gè)解YT代入對(duì)偶問題的目標(biāo)函數(shù)值，有w=YTb= CB B1b= CB XB=z。= CB CB B1B。= CN CB B1N≤0, XS的檢驗(yàn)數(shù)σS39。σS39。：第三節(jié) 對(duì)偶問題的基本性質(zhì) 在本節(jié)討論中，設(shè)原問題和對(duì)偶問題是如下對(duì)稱形式的：下面將利用單純形法計(jì)算的矩陣描述，分析單純形法的迭代過(guò)程中體現(xiàn)的原問題和對(duì)偶問題之間變量的對(duì)應(yīng)關(guān)系，再介紹對(duì)偶問題的基本性質(zhì)。 寫出下列問題的對(duì)偶問題。這就是互為對(duì)偶關(guān)系：若D是P的對(duì)偶問題，則P也是D的對(duì)偶問題。 將下列問題作為原問題，寫出其對(duì)偶問題。在對(duì)稱形式下，二者的聯(lián)系與區(qū)別如下：（1）原目標(biāo)求極大值，對(duì)偶目標(biāo)求極小值；（2）原約束的個(gè)數(shù)=對(duì)偶變量的個(gè)數(shù)，原變量的數(shù)=對(duì)偶約束的個(gè)數(shù)，而且原約束決定對(duì)偶變量，原變量決定對(duì)偶約束；（3）原約束全≤方向，對(duì)偶約束全≥方向；（4）原目標(biāo)的系數(shù)對(duì)應(yīng)對(duì)偶約束的右端常數(shù)，原約束的右端常數(shù)對(duì)應(yīng)對(duì)偶目標(biāo)的系數(shù)；（5）原系數(shù)矩陣與對(duì)偶系數(shù)矩陣互為轉(zhuǎn)置；（6）原變量與對(duì)偶變量都是非負(fù)取值。二、對(duì)稱形式的對(duì)偶問題將滿足下列條件的線性規(guī)劃問題及其對(duì)偶問題稱為具有對(duì)稱形式（或典式）：具有對(duì)稱形式的原問題和對(duì)偶問題，滿足變量均為非負(fù)數(shù)，當(dāng)目標(biāo)函數(shù)求極大值時(shí)約束條件均取≤（簡(jiǎn)稱為“大目標(biāo)小約束”），而當(dāng)目標(biāo)函數(shù)求極小值時(shí)約束條件均取≥號(hào)（簡(jiǎn)稱為“小目標(biāo)大約束”）。 由此建立了另一個(gè)線性規(guī)劃數(shù)學(xué)模型（用LP2表示）為：從以上兩個(gè)問題可以看出每一個(gè)線性規(guī)劃求 max z的 LP1必然有與之相伴而生的另一個(gè)線性規(guī)劃問題求 min w的 LP2，理論上將LP1稱為“原問題”，簡(jiǎn)記為P ；將LP2稱為“對(duì)偶問題”(dual problem)，簡(jiǎn)記為D 。（2）競(jìng)爭(zhēng)性原則，即在上述不吃虧原則下，盡量降低出租設(shè)備的總租金，即求總租金w=12y1+16y2+15y3 的最小值，以便爭(zhēng)取更多用戶。例如生產(chǎn)出一件Ⅰ型產(chǎn)品，需耗用A設(shè)備2小時(shí)，B設(shè)備4小時(shí)，這些資源可換得租金2y1+4y2。在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代，常山廠的最佳決策顯然應(yīng)符合以下兩條：設(shè)A、B、C設(shè)備每小時(shí)出租的價(jià)格分別為yyy3元，也許有人會(huì)馬上回答，租金定得愈高，收益愈大，故必是最佳決策。我們已經(jīng)建立了對(duì)應(yīng)的線性規(guī)劃問題如下，用LP1表示：LP1是一個(gè)關(guān)于資源合理利用的問題，即如何安排生產(chǎn)計(jì)劃使得既能充分利用現(xiàn)有資又能使總利潤(rùn)最大。這對(duì)于下面要介紹的對(duì)偶問題和靈敏度分析很有用處。注意以上討論中的最終單純形表可相應(yīng)替換為單純形法迭代過(guò)程中任何一步的單純形表。= CN CB N39。=(y1,y2,...,ym)=YT,即YT = CB B1。=0 CB B39。= B1，其中B1是初始表中基變量在最終表對(duì)應(yīng)的系數(shù)矩陣。= B1b，系數(shù)矩陣N39。單純形表的迭代計(jì)算實(shí)際上是對(duì)約束方程組的增廣矩陣進(jìn)行初等行變換的過(guò)程，由線性代數(shù)知道，對(duì)矩陣施行初等行變換等價(jià)于在矩陣的左側(cè)乘以可逆矩陣，當(dāng)行變換使B變?yōu)镮時(shí)，相當(dāng)于在對(duì)應(yīng)矩陣的左側(cè)乘以可B1，于是[b,B,N,I]變?yōu)閇B1b,I, B1N, B1]。σj0σN39。IN39。,B39。它們?cè)诔跏急碇械脑鰪V矩陣分別表示為b,B,N,I（I為單位矩陣），而在最終表中的增廣矩陣分別為b39。不失一般性假設(shè)線性規(guī)劃問題形如：引入松弛變量后化為為敘述的方便，將變量分成三組：在初始單純形表中基變量為松弛變量用XS表示，經(jīng)過(guò)若干次迭代后對(duì)應(yīng)的最終單純形表中基變量用XB表示（注意XS和XB可以有公共變量），若存在既不在XS也不在XB中的其它變量則用XN表示。每一個(gè)線性規(guī)劃必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，這就是對(duì)偶問題。