【正文】 ，其結(jié)構(gòu)尺寸如圖11所示。：班次時間（日夜服務）最少護士人數(shù)16 －－10 點60210 －－ 14 點70314 －－ 18 點60418 －－ 22 點50522 －－ 2 點2062 －－ 6 點30每班護士在輪班開始時向病房報到，連續(xù)工作八小時。加工單位產(chǎn)品所需工序時間及其它各項數(shù)據(jù)見下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。設A工序可分別在設備A1或A2上完成，有BBB3三種設備可用于完成B工序。表1x1x2x3x4x5x46(b)(c)(d)10x5113(e)01cjzj(a)1200表2x1x2x3x4x5x1(f)(g)211/20x54(h)(i)11/21cjzj07(j)(k)(l)設最優(yōu)解為X*，當C變?yōu)闀r，最優(yōu)解為，求證：。（1）把表中缺少的項目填上適當?shù)臄?shù)或式子。1112a211CBXBbx1x2x3x4x5x62x5x2x1214表112cj ，其中x4，x5，x6是松弛變量。 ：（1）R1=｛(x1,x2)|x12+2x22≤2｝（2）R2=｛(x1,x2)|x12－2x2+3≥0,x2≥0,|x1|≤1｝（3）R3=｛(x1,x2)|x1x2≥1,x1≥1,x2≥0｝。 ，并指出其中的基可行解和最優(yōu)解。本章的學習重點是單純形法的步驟，難點是單純形法的原理及如何就一些簡單的實際問題建立線性規(guī)劃模型。解：用xij表示第i年初投放到第j個項目的資金數(shù)（注意只有6個決策變量x11,x12,x21,x23,x31,x34），則建立如下線性規(guī)劃模型：用單純形法求得：綜上投資組合方案如下：方案年初12341202031010單位：萬元第三年末本利和的最大值=58萬元。問如何才能既滿足需要，又能使總的用料最少？解：設變量xj為使用第 j 種方式下料的圓鋼根數(shù)。P為50kg。已知產(chǎn)品的規(guī)格要求、單價和原材料的供應量、單價。下面舉例說明如何將實際問題歸結(jié)為線性規(guī)劃問題的數(shù)學模型。一般而言，一個經(jīng)濟、管理問題只有滿足以下條件時，才能建立對應的線性規(guī)劃模型。將經(jīng)濟管理領域的實際問題抽象為數(shù)學模型，這是一項極具創(chuàng)造性和技巧性的工作，既要求能熟練地掌握運用有關(guān)的數(shù)學知識，又要求對所研究經(jīng)濟對象的本質(zhì)有深刻的理解，同時還需要相關(guān)方面的專業(yè)人員的互相配合和通力合作。0基變量中有非零的人工變量某非基變量檢驗數(shù)為零且有恰當?shù)摩葻o可行解無窮多最優(yōu)解某一бj≥0但系數(shù)列aik≤0無界解令бk=max{бj}xk為換入變量，對所有aik0計算θ 最小比值對應的變量xl為換出變量，alk為主元素1．xk替換xl2．列出新的單純形表，用矩陣的初等行變換①將主元素化為1②將主元素列的其它系數(shù)化為0第五節(jié) 線性規(guī)劃應用舉例學習運籌學的目的在于應用，而應用的第一步就是建立與實際問題對應的數(shù)學模型，正如緒論中曾經(jīng)講述的。通過以上各例，我們歸納出利用最終單純形表判斷線性規(guī)劃問題解的類型的方法如下：解的類型最終表的特征無可行解有非0的人工變量有可行解唯一最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全為負數(shù)無窮多最優(yōu)解無非0的人工變量，非基變量的檢驗數(shù)全非正，且有某個非基變量的檢驗數(shù)為0，同時該變量對應的系數(shù)列至少有一個正系數(shù)無界解無非0的人工變量，有某個非基變量的檢驗數(shù)為正數(shù)，但該變量對應的系數(shù)列全為非正數(shù)能夠用單純形法求解的線性規(guī)劃問題應首先化為標準形式，并可選擇一個單位矩陣作為基，常稱之為廣義標準形式。 用單純形法求解下列問題。解：在圖解法中已看到本例有無窮多最優(yōu)解，用單純形法求解時，先化為標準形式列單純形表如下cj22000CBBbX1X2X3X4X5θ0X3122210060X416[4]001040X51505001σj220000X340[2]11/2012X141001/400X515050013σj 0201/202X22011/21/402X141001/400X55005/25/41σj00100表中所有檢驗數(shù)均非正且無人工變量，得到最優(yōu)解X(1)=(4,2,0,0,5)T,zmax=12,進一步由于非基變量x4的檢驗數(shù)等于0，取x4作為換入變量，繼續(xù)用單純形法計算如下：cj22000CBBbX1X2X3X4X5θ2X22011/21/402X141001/40160X55005/2[5/4]14σj001002X2301001/52X13101/201/50X4400214/5σj00100表中所有檢驗數(shù)均非正且無人工變量，得到另一個最優(yōu)解X(2)=(4,2,0,0,5)T,zmax=12,連接X(1)和X(2)的線段上的點也都是最優(yōu)解。故該問題有無界解。四、單純形法小結(jié)用最終單純形表判斷解的類型 用單純形法求解下列問題。為此人們已經(jīng)提出了三種避免出現(xiàn)死循環(huán)的方法，即攝動法、字典序法或最小下標法。當任取一個對應的變量為換出變量時，則下一張表中有基變量的值等于0，這種現(xiàn)象稱為退化。先修改第一階段的最終表，再繼續(xù)計算：Cj2302X121023X21011σj001因此該問題有唯一最優(yōu)解：三、關(guān)于退化解的說明 在用單純形法計算時，可能出現(xiàn)以下兩種情況： 出現(xiàn)若干正檢驗數(shù)大小相同且都是最大。若求得wmin=0，則表明已知問題有可行解，進入第二階段，否則表明已知問題無可行解，計算結(jié)束。第一階段的作用是判斷原線性規(guī)劃問題是否存在可行解。在這種情況下，可采用下面的兩階段法進行計算。采用大M法求解線性規(guī)劃模型時，當模型中各個系數(shù)與M的值非常接近或相差甚遠時，若用手工計算，不會出現(xiàn)問題。本例引入人工變量后轉(zhuǎn)化為：再用單純形法繼續(xù)計算如下：Cj230MMCBBbX1X2X3X4X5θMX43111103MX541[2]0012σj2+2M3+3MM00MX41[1/2]0111/223X221/21001/24σj1/2+M/20M03/23M/22X12102213X2101111σj0011M1M在最終單純形表中，檢驗數(shù)全非正，且人工變量取值全為0，因此該問題有唯一最優(yōu)解：注意： 若表中所有sj 163。對應的約束方程組為：為使兩個方程組等價，常稱為罰因子（其中M為任意大的正數(shù)）。解：先標準化為但是A中沒有單位矩陣，在A中人為的增加兩列此時A有單位子矩陣，選擇該單位矩陣作為基，常稱為人工基。這種人為添加的變量稱為人工變量，由此構(gòu)成的可行基稱為人工基，這種用人工變量作橋梁的求解方法稱為人工變量法。下一節(jié)將解決線性規(guī)劃問題化為標準形時，約束條件的系數(shù)矩陣中不存在單位矩陣，應如何構(gòu)造初始可行基。利用初等行變換將[5]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表18）表18cj23000CBBbX1X2X3X4X5θ0X36[2]0102/530X4164001043X2301001/5σj20003/5注意表中x1為換入變量；依照比值的計算規(guī)則，只有x1的正系數(shù)才有對應的比值，即故變量x3為換出變量，從而元素2為主元（用[]標記），再將[2]變?yōu)?，此列其它系數(shù)變?yōu)?，得到新的單純形表（見表19）表19cj23000CBBbX1X2X3X4X5θ2X13101/201/50X4400214/53X2301001/5σj00101/5表19中所有檢驗數(shù)均非正，得到最優(yōu)解X=(3,3,0,4,0)T,zmax=15,進一步由于非基變量的檢驗數(shù)全小于0，該問題是唯一最優(yōu)解。.解：先標準化其約束條件的系數(shù)矩陣為A中有3階單位矩陣，選其為基B=(P3,P4,P5)。⑥將aik′稱為主元素或主元，常用方括號[ ]標記，利用主元進行迭代，即通過矩陣的初等行變換，把xk所對應的列向量變?yōu)閱挝涣邢蛄?，即主元aik′變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③ 步。⑤根據(jù)max{sj｜sj＞0}=sk原則，確定xk為換入基的變量，簡稱為換入變量(或進基變量)，再按比值q的選取規(guī)則計算：q=min{bi′/aik′| aik′＞0}=bl′/ aik′ 確定xBl為換出基的變量，簡稱換出變量（或出基變量）。 0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。③計算各非基變量xj的檢驗數(shù)sj= Cj CBPj，若所有sj≤0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下一步。） ①將線性規(guī)劃問題化成標準型。下面介紹用單純形表計算線性規(guī)劃問題的步驟。一個含有n個決策變量m個約束條件的標準線性規(guī)劃問題，對應的單純形表中第一行稱為價值行，用Cj表示，列出每個決策變量在目標函數(shù)中的系數(shù)；第二行稱為變量行，列出n個決策變量；最后一行稱為檢驗數(shù)行，列出每個決策變量的檢驗數(shù)（易見基變量的檢驗數(shù)為0）；第一列稱為基價值列，用CB表示，列出每個基變量在目標函數(shù)中的系數(shù)；第二列稱為基列（或基變量列），用B或XB表示,列出m個基變量；第三列稱為基解列，用b表示，即每個基變量的取值；最后一列稱為比值列；而中心位置m行n列的矩陣為約束條件的系數(shù)矩陣，注意基變量對應的系數(shù)矩陣是m階的單位矩陣。注意：線性規(guī)劃問題出現(xiàn)無可行解的情形將在后面進行討論。 +165。+165。, 0)T ，且前m個分量為正值。 從一個基可行解轉(zhuǎn)換為另一個基可行解且系數(shù)矩陣取前m列的單位矩陣為基，則基可行解為X（0）=(x10, x20,bm)T注意：用這個方法確定初始基可行解，必須保證約束條件全是“≤” 。引入松弛變量xsi ( i=1,2,…,m )化為標準形式：此時系數(shù)矩陣為：取后m列對應的單位矩陣為基，得到初始基可行解：X=( 0,0,一、單純形法的解題思路 因為線性規(guī)劃問題若有最優(yōu)解，則一定可以在基可行解中找到，所以用單純形法求解線性規(guī)劃的基本思想是：先找到一個初始基可行解，若不是最優(yōu)解，則設法轉(zhuǎn)換到另一個基可行解，并使目標函數(shù)值不斷增大，直到找到最優(yōu)解為止（如果有的話）。第三節(jié) 單純形法1947年，美國學者George Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線性規(guī)劃的推廣奠定了基礎。所以只有CX(0)= CX(r) 。并且將X(r)代替(1)式中的所有X(i),這就得到: 由此得到 CX(0)≤ CX(r)。 證明：設X(1)，X(2)，…， X(k)是可行域D的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最大值Z＊＝C X(0)。從而必然會找到一個基可行解為最優(yōu)解。 z2 ，∴ z1 = z2 = z0 ，即 X1 、 X2也為最優(yōu)解。,xn0)T 是線性規(guī)劃模型的一個最優(yōu)解， z0=zmax=CX0 若X0非基可行解，即非頂點，只要取d為充分小的正數(shù)，則必能找出X1= X0d ，X2 = X0 +d ，即X1 、 X2為可行解，z1=CX1=CX0Cd=zmaxCd ，z2=CX2=CX0+Cd