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