【正文】 2x3x4x5x62x5x2x1214（1）把表中缺少的項(xiàng)目填上適當(dāng)?shù)臄?shù)或式子。：班次時(shí)間（日夜服務(wù)）最少護(hù)士人數(shù)16 －－10 點(diǎn)60210 －－ 14 點(diǎn)70314 －－ 18 點(diǎn)60418 －－ 22 點(diǎn)50522 －－ 2 點(diǎn)2062 －－ 6 點(diǎn)30每班護(hù)士在輪班開始時(shí)向病房報(bào)到，連續(xù)工作八小時(shí)。,B39。= B1b，系數(shù)矩陣N39。= CN CB N39。設(shè)A、B、C設(shè)備每小時(shí)出租的價(jià)格分別為yyy3元，也許有人會(huì)馬上回答，租金定得愈高，收益愈大，故必是最佳決策。 由此建立了另一個(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 。這就是互為對(duì)偶關(guān)系：若D是P的對(duì)偶問題，則P也是D的對(duì)偶問題。= CN CB B1N≤0, XS的檢驗(yàn)數(shù)σS39。性質(zhì)2 最優(yōu)性： 若 X* 和 Y* 分別是 P 和 D 的可行解且 CX* = bT Y* ， 則X*，Y*分別是問題 P和D 的最優(yōu)解。綜上所述，對(duì)于給定的原問題和對(duì)偶問題，則下面三種情況必有其一：① 都有最優(yōu)解② 都無可行解③ 一個(gè)無可行解，而另一個(gè)問題有無界解。 0， 即Y*是對(duì)偶問題的可行解，且滿足 CX* = CB b ′ =CB (B1 b) = CB B1b = Y*T b= b TY* 由最優(yōu)性有Y*是對(duì)偶問題的最優(yōu)解。又有z = CX =CB B1b= YTb= w，表明這對(duì)互補(bǔ)的基解代入各自目標(biāo)函數(shù)值相等。當(dāng)yimi 時(shí)，企業(yè)愿意購進(jìn)這種資源，可獲單位純利為yi－mi，即有利可圖；當(dāng)yimi 時(shí)，企業(yè)愿意有償轉(zhuǎn)讓這種資源，可獲單位純利為mi－yi，否則企業(yè)無利可圖，甚至虧損。一般說來對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用。也就是說，求解線性規(guī)劃問題時(shí)，在保持檢驗(yàn)數(shù)全非正的前提下，可以從原問題的一個(gè)基解（一般不是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值減少，當(dāng)?shù)皆瓎栴}出現(xiàn)可行解時(shí)，即找到了該問題的最優(yōu)解，這就是對(duì)偶單純形法。注意：（1）用對(duì)偶單純形法求解線性規(guī)劃問題時(shí)，當(dāng)約束條件為≥時(shí)，不必引入人工變量，可使計(jì)算簡(jiǎn)化。而在線性規(guī)劃問題中的靈敏度分析是指研究基礎(chǔ)數(shù)據(jù)發(fā)生波動(dòng)后對(duì)最優(yōu)解的影響，即分析問題中一個(gè)或多個(gè)參數(shù)發(fā)生變化時(shí)，最優(yōu)解將如何改變；或者分析參數(shù)在一個(gè)怎樣的范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。若不滿足，則繼續(xù)迭代，直到找到最優(yōu)解為止。時(shí)，最終表中對(duì)應(yīng)的系數(shù)列向量變?yōu)?B1Pj180。解：當(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í)，滿足要求。即(△b)180。因此有可能把個(gè)別參數(shù)的變化直接在計(jì)算得到的最優(yōu)解的單純形表上體現(xiàn)出來。第六節(jié) 靈敏度分析廣義靈敏度分析又稱敏感性分析或優(yōu)化后分析，是對(duì)系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。利用初等行變換將[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)解。由對(duì)偶理論可以知道，單純表中同時(shí)反映原問題與對(duì)偶問題的互補(bǔ)的基解，故可以從求對(duì)偶問題最優(yōu)解的角度求解原問題的最優(yōu)解。當(dāng)產(chǎn)品的產(chǎn)值大于隱含成本時(shí)，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排該項(xiàng)產(chǎn)品，否則用這些資源來生產(chǎn)其它產(chǎn)品更有利，即不在生產(chǎn)計(jì)劃中安排該項(xiàng)產(chǎn)品。圖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無變化，對(duì)應(yīng)y2=0，設(shè)備B的影子價(jià)格為0；當(dāng)b3增加1個(gè)單位時(shí)，對(duì)應(yīng)y3=，.影子價(jià)格還是一種機(jī)會(huì)成本。證明：最終表中Xj的檢驗(yàn)數(shù)滿足σj=zjcj= CB B1Pjcj，記YT=CB B1即zjcj= YTPjcj,所以即(zjcj)在對(duì)偶問題的約束條件中相當(dāng)于剩余變量。 CT 又因?yàn)閟 S′ = CBB1 = Y * T 163。，分析最優(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)解。σS39。 將下列問題作為原問題，寫出其對(duì)偶問題。（2）競(jìng)爭(zhēng)性原則，即在上述不吃虧原則下，盡量降低出租設(shè)備的總租金，即求總租金w=12y1+16y2+15y3 的最小值，以便爭(zhēng)取更多用戶。我們已經(jīng)建立了對(duì)應(yīng)的線性規(guī)劃問題如下，用LP1表示：LP1是一個(gè)關(guān)于資源合理利用的問題，即如何安排生產(chǎn)計(jì)劃使得既能充分利用現(xiàn)有資又能使總利潤最大。=(y1,y2,...,ym)=YT,即YT = CB B1。單純形表的迭代計(jì)算實(shí)際上是對(duì)約束方程組的增廣矩陣進(jìn)行初等行變換的過程，由線性代數(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]。它們?cè)诔跏急碇械脑鰪V矩陣分別表示為b,B,N,I（I為單位矩陣），而在最終表中的增廣矩陣分別為b39。加工單位產(chǎn)品所需工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。1 ，并指出其中的基可行解和最優(yōu)解。解：用xij表示第i年初投放到第j個(gè)項(xiàng)目的資金數(shù)（注意只有6個(gè)決策變量x11,x12,x21,x23,x31,x34），則建立如下線性規(guī)劃模型：用單純形法求得：綜上投資組合方案如下：方案年初12341202031010單位：萬元第三年末本利和的最大值=58萬元。下面舉例說明如何將實(shí)際問題歸結(jié)為線性規(guī)劃問題的數(shù)學(xué)模型。通過以上各例，我們歸納出利用最終單純形表判斷線性規(guī)劃問題解的類型的方法如下：解的類型最終表的特征無可行解有非0的人工變量有可行解唯一最優(yōu)解無非0的人工變量，非基變量的檢驗(yàn)數(shù)全為負(fù)數(shù)無窮多最優(yōu)解無非0的人工變量，非基變量的檢驗(yàn)數(shù)全非正，且有某個(gè)非基變量的檢驗(yàn)數(shù)為0，同時(shí)該變量對(duì)應(yīng)的系數(shù)列至少有一個(gè)正系數(shù)無界解無非0的人工變量，有某個(gè)非基變量的檢驗(yàn)數(shù)為正數(shù)，但該變量對(duì)應(yīng)的系數(shù)列全為非正數(shù)能夠用單純形法求解的線性規(guī)劃問題應(yīng)首先化為標(biāo)準(zhǔn)形式，并可選擇一個(gè)單位矩陣作為基，常稱之為廣義標(biāo)準(zhǔn)形式。四、單純形法小結(jié)用最終單純形表判斷解的類型 用單純形法求解下列問題。采用大M法求解線性規(guī)劃模型時(shí)，當(dāng)模型中各個(gè)系數(shù)與M的值非常接近或相差甚遠(yuǎn)時(shí)，若用手工計(jì)算，不會(huì)出現(xiàn)問題。這種人為添加的變量稱為人工變量，由此構(gòu)成的可行基稱為人工基，這種用人工變量作橋梁的求解方法稱為人工變量法。⑥將aik′稱為主元素或主元，常用方括號(hào)[ ]標(biāo)記，利用主元進(jìn)行迭代，即通過矩陣的初等行變換，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即主元aik′變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③ 步。） ①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。 +165。所以只有CX(0)= CX(r) 。 z2 ，∴ z1 = z2 = z0 ，即 X1 、 X2也為最優(yōu)解。證明：設(shè) X0=(x10, x20,xm mdm ，0，,Pm線性相關(guān)，即有d1P1+d2P2+當(dāng)km時(shí)，則必定可再找出mk個(gè)列向量與P1,P2, X為基可行解若A的秩為m，則X的正分量的個(gè)數(shù)k163。,0)T，若X為基可行解，顯然，由基可行解定義可知x1, x2,C，即C為凸集。證明：設(shè) max z=CX st. AX=b X179。，列出全部基、基解、基可行解，并指出最優(yōu)解。不失一般性，設(shè)基為將B中每個(gè)列向量即P1,P2,… ,Pm稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量(常記為XB)，除基本量以外的其它變量稱為非基變量(常記為XN)?！?.5. =xq39。當(dāng)約束條件為“≤”時(shí)，例如2 x1+2 x2≤12，可令x3=122 x12 x2,得2 x1+2 x2+x3=12,顯然x3≥0。再與周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值比較是否比這個(gè)值更優(yōu)。解 用圖解法求解時(shí)該問題的可行域是空集，如圖15所示。 解 用圖解法求解，如圖13所示，沿優(yōu)化方向平移時(shí)目標(biāo)函數(shù)等值線與可行域在整個(gè)線段上相切，即該問題的最優(yōu)解為此線段上的所有點(diǎn)。 用圖解法求例1的最優(yōu)解。全部可行解的集合稱為可行域．特別的，能使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為最優(yōu)解。通常用 z=f(x1，x2，…，xn)表示，按優(yōu)化目標(biāo)分別在這個(gè)函數(shù)前面加上max或min；（3）約束條件，即決策變量取值時(shí)受到各種可用資源的限制，通常表示為含決策變量的等式或不等式。該廠的目標(biāo)是在各種設(shè)備允許的情況下，使總的利潤收入z=2 x1+3 x2為最大。第1章 線性規(guī)劃與單純形法 .生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃論要解決的問題。對(duì)于B、C設(shè)備也可列出類似的不等式：4 x1≤16；5 x2≤15。通常用x1，x2，…，xn表示；（2）目標(biāo)函數(shù)，即問題要達(dá)到的目標(biāo)要求，表示為決策變量的函數(shù)。于是線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫成()一個(gè)線性規(guī)劃問題有解，是指能找出一組xj(j＝1,...,n)的值既滿足()中的約束條件，又滿足決策變量的取值要求，此時(shí)稱X=(x1,x2,...,xn)T為該問題的可行解。圖解法的步驟是：先在平面直角坐標(biāo)系中畫出約束條件所確定的可行域；再對(duì)任意確定的z，畫出目標(biāo)函數(shù)所代表的一族直線（常稱為目標(biāo)函數(shù)等值線）；最后沿優(yōu)化方向平移目標(biāo)函數(shù)等值線，確定最優(yōu)解（如果有的話）。 用圖解法求解下列線性規(guī)劃問題。 用圖解法求解下列線性規(guī)劃問題。(4) 解題思路：先找出凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值。=z，即轉(zhuǎn)化為2. 約束條件為不等式。=xp,代入模型，顯然xp39。并引入松弛變量x4, x5,按照上述方法將問題化為如下標(biāo)準(zhǔn)形式：二、 線性規(guī)劃的基可行解的概念 已知線性規(guī)劃的標(biāo)準(zhǔn)形式： ()A=(aij)為約束方程組的mn階系數(shù)矩陣(設(shè)nm)，則稱B是線性規(guī)劃問題的一個(gè)基矩陣（簡(jiǎn)稱為基）。最優(yōu)基 對(duì)應(yīng)于基最優(yōu)解的基稱為最優(yōu)基。定理1 若線性規(guī)劃問題存在可行域，則其可行域一定是凸集。0， ∴ X 206。