線性規(guī)劃完整版本

PAGEPAGE24第一章線性規(guī)劃及單純形方法主要內(nèi)容線性規(guī)劃的模型、標(biāo)準(zhǔn)型、圖解法、解、單純形法、大M法、兩階段法講授重點(diǎn)線性規(guī)劃問題的解、單純形法、大M法、兩階段法教學(xué)方法講授式、啟發(fā)式本章知識(shí)結(jié)構(gòu)圖第一節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型一、問題的提出在生產(chǎn)和經(jīng)營(yíng)等管理工作中，需要經(jīng)常進(jìn)行計(jì)劃或規(guī)劃，即：在現(xiàn)有各項(xiàng)資源條件的限制下，如何確定方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)?？慈缦聝蓚€(gè)例子：例1美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A,B的臺(tái)時(shí)、調(diào)試時(shí)間、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1—1所示。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)為最大。表1—1IⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152l15245利潤(rùn)(元)21例2捷運(yùn)公司擬在下一年度的l～4月的4個(gè)月內(nèi)需租用倉庫堆放物資。已知各月份所需倉庫面積數(shù)列于表1—2。倉庫租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見表1—3。租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積數(shù)和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m月份1234所需倉庫面積：15102012表1-3單位：元／lOOm2合同租借期限1個(gè)月2個(gè)月31個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)2800450060007300二、線性規(guī)劃問題的數(shù)學(xué)模型例1中先用變量x1和x2分別表示美佳公司制造家電I和Ⅱ的數(shù)量。這時(shí)該公司可獲取的利潤(rùn)為(2x1+x2)元，令z=2x1+x2，因問題中要求獲取的利潤(rùn)為最大，即maxz。家電Ⅰ、Ⅱ的制造件數(shù)受設(shè)備A、B和調(diào)試工序能力的能力限制，同時(shí)家電Ⅰ、Ⅱ制造數(shù)量不可能為負(fù)值。由此例1的數(shù)學(xué)模型可表為：目標(biāo)函數(shù)約束條件例2中若用變量xij表示捷運(yùn)公司在第i(i=1，…，4)個(gè)月初簽訂的租借期方ｊ(ｊ＝1，…，4)個(gè)月的倉庫面積的合同(單位為lOOm２)。因5月份起該公司不需要租借倉庫，故ｘ24，x33,x34,x42,x43,x44均為零。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型：目標(biāo)函數(shù)min z＝ 2800(xll+x2l+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300x14約束條件這個(gè)模型中的約束條件分別表示當(dāng)月初簽訂的租借合同的面積數(shù)加上該月前簽訂的未到期的合同的租借面積總和，應(yīng)不少于該月所需的倉庫面積數(shù)。上述兩個(gè)例子表明，規(guī)劃問題的數(shù)學(xué)模型由三個(gè)要素組成：(1)變量，或稱決策變量，是問題中要確定的未知量，它用以表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制；(2)目標(biāo)函數(shù)，它是決策變量的函數(shù)，按優(yōu)化目標(biāo)分別在這個(gè)函數(shù)前加上max或min；(3)約束條件，指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃(LinearProgramming,LP)的數(shù)學(xué)模型。假定線性規(guī)劃問題中含n個(gè)變量，分別用xj(j＝1，…，n)表示，在目標(biāo)函數(shù)中xj的系數(shù)為cj(cj通常稱為價(jià)值系數(shù))，xj的取值受m項(xiàng)資源的限制，用bi(i=1,...m)表示第i種資源的擁有量，用aij表示變量xj取值為1個(gè)單位時(shí)所消耗或含有的第i種資源的數(shù)量，通常稱aij為技術(shù)系數(shù)或工藝系數(shù)。則上述線性規(guī)劃問題的數(shù)學(xué)模型可表示為：(1.2)上述模型的簡(jiǎn)寫形式為：（1.3）用向量形式表達(dá)時(shí)，上述模型可寫為：（1.4）式（1.4）中用矩陣和向量形式來表示可寫為：A稱為約束方程組(約束條件)的系數(shù)矩陣。變量xj的取值一般為非負(fù)，即xj≥0；從數(shù)學(xué)意義上可以有xj≤0。又如果變量xj表示第j種產(chǎn)品本期內(nèi)產(chǎn)量相對(duì)于前期產(chǎn)量的增加值，則xj的取值范圍為(-∞，+∞)，稱xj，取值不受約束，或xj無約束。三、LP的標(biāo)準(zhǔn)形式由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的差別，線性規(guī)劃問題可以有多種表達(dá)式。為了便于討論和制定統(tǒng)一的算法，規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式的線性規(guī)劃模型中，目標(biāo)函數(shù)為求極大值(有些書上規(guī)定是求極小值)，約束條件全為等式，約束條件右端常數(shù)項(xiàng)bi全為非負(fù)值，變量xj的取值全為非負(fù)值。對(duì)不符合標(biāo)準(zhǔn)形式(或稱非標(biāo)準(zhǔn)形式)的線性規(guī)劃問題，可分別通過下列方法化為標(biāo)準(zhǔn)形式。目標(biāo)函數(shù)為求極小值，即為:因?yàn)榍蟮葍r(jià)于求，令z’＝-z，即化為：2．右端項(xiàng)bi<0時(shí)，只需將等式或不等式兩端同乘(-1)，則等式右端項(xiàng)必大于零。3．約束條件為不等式。當(dāng)約束條件為“≤”時(shí)，如6xl+2x2≤24，可令x3＝24-6x1-2x2：或6x1+2x2+x3＝24，顯然x3≥0。當(dāng)約束條件為“≥”時(shí)，如有l(wèi)0x1+12x2≥18，可令x4＝l0x1+12x2-18或l0xl+12x2-x4＝18，x4≥0。x3和x4是新加上去的變量，取值均為非負(fù)，加到原約束條件中去的目的是使不等式轉(zhuǎn)化為等式，其中x3，稱為松弛變量，x4一般稱為剩余變量，但也有稱松弛變量的。松弛變量或剩余變量在實(shí)際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。4．取值無約束的變量。如果變量x代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)與上一年計(jì)劃數(shù)之差，顯然x的取值可能是正也可能為負(fù)，這時(shí)可令x＝x’-x”，其中x’≥0，x”≥0，將其代入線性規(guī)劃模型即可。5．對(duì)x≤0的情況，令x’＝-x，顯然x’≥0。將下述線性規(guī)劃化為標(biāo)準(zhǔn)形式解上述問題中令，其中，并按上述規(guī)則，該問題的標(biāo)準(zhǔn)形式為：第二節(jié)圖解法基本概念：可行解：一個(gè)線性規(guī)劃問題有解，是指能找出一組xj(j=1，…，)滿足約束條件，稱這組xj為問題的可行解。通常線性規(guī)劃問題總是含有多個(gè)可行解，稱全部可行解的集合為可行域，可行域中使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為最優(yōu)解。對(duì)不存在可行解的線性規(guī)劃問題，稱該問題無解。對(duì)模型中只有２個(gè)變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解。一、圖解法的步驟圖解法的步驟可概括為：在平面上建立直角坐標(biāo)系；圖示約束條件，找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。下面通過上述例1來具體說明。先將例1的數(shù)學(xué)模型重列如下：1.以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸畫出直角平面坐標(biāo)系，適當(dāng)選取單位坐標(biāo)長(zhǎng)度。由變量的非負(fù)約束條件(1.5d)知，滿足該約束條件的解(對(duì)應(yīng)坐標(biāo)系中的一個(gè)點(diǎn))均在第Ⅰ象限內(nèi)。2.圖示約束條件，找出條件可行域。約束條件（1.5a）5x≤15決定的區(qū)域，見圖1-1。類似滿足約束條件(1.5a)～(1.5d)的點(diǎn)如圖1-2所示，圖中凸多邊形所包含的區(qū)域(用陰影線標(biāo)示)是例l線性規(guī)劃問題的可行域。圖1-1圖1-23．圖示目標(biāo)函數(shù)。由于z是一個(gè)要求定的目標(biāo)函數(shù)值，隨z的變化，z=2xl+x2是斜率為(-2)的一族平行的直線，見圖1-3，圖中向量P代表目標(biāo)函數(shù)值z(mì)的增大方向。圖1-3圖1-44．最優(yōu)解的確定。因最優(yōu)解是可行域中使目標(biāo)函數(shù)值達(dá)到最優(yōu)的點(diǎn)，將圖1-2和圖1-3合并得到圖1-4，可以看出，當(dāng)代表目標(biāo)函數(shù)的那條直線由原點(diǎn)開始向右上方移動(dòng)時(shí)，z的值逐漸增大，一直移動(dòng)到目標(biāo)函數(shù)的直線與約束條件包圍成的凸多邊形相切時(shí)為止，切點(diǎn)就是代表最優(yōu)解的點(diǎn)。因?yàn)樵倮^續(xù)向右上方移動(dòng)，z值仍然可以增大，但在目標(biāo)函的直線上找不出一個(gè)點(diǎn)位于約束條件包圍成的凸多邊形內(nèi)部或邊界上。本例中目標(biāo)函數(shù)直線與凸多邊形的切點(diǎn)是Q2，該點(diǎn)坐標(biāo)可由求解直線方程6x1+2x2=24和x1+x2＝5得到，為(x1,x2)＝(3.5，1.5)。將其代入目標(biāo)函數(shù)得z＝8.5，即美佳公司應(yīng)每天制造家電Ⅰ3.5件，家電Ⅱ1.5件能獲利最大。二、LP求解的幾種可能結(jié)局例1用圖解法得到的最優(yōu)解是唯一的。但對(duì)線性規(guī)劃問題的求解還可能出現(xiàn)下列結(jié)局：1．無窮多最優(yōu)解。如將例1中的目標(biāo)函數(shù)改變?yōu)閙axz＝3x1+x2，則表示目標(biāo)函數(shù)的直線族恰好與約束條件(1.5b)平行。當(dāng)目標(biāo)函數(shù)向優(yōu)化方向移動(dòng)時(shí)，與可行域不是在一個(gè)點(diǎn)上，而是在QlQ2線段上相切，見圖1-5。這時(shí)點(diǎn)Q1、Q2及Q1、Q2之間的所有點(diǎn)都使目標(biāo)函數(shù)z達(dá)到最大值，即有無窮多最優(yōu)解，或多重最優(yōu)解。2．無界解。如果例1中只包含約束條件(1.5a)，這時(shí)可行域可伸展到無窮，即變量x13．無解，或無可行解。例如下述線性規(guī)劃模型：maxz=2x1+x2見圖1-7，其模型的約束條件之間存在矛盾。圖1-5圖1-6圖1-7三、由圖解法得到的啟示1．求解線性規(guī)劃問題時(shí)，解的情況有：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。2．若線性規(guī)劃問題的可行域存在，則可行域是一個(gè)凸集。3．若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一(如果有無窮多的話)一定是在可行域凸集的某個(gè)頂點(diǎn)上得到。4．解題思路是，先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過程，一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。在單純形法原理一節(jié)中，將對(duì)2、3兩點(diǎn)進(jìn)行證明，并建立起凸集頂點(diǎn)的代數(shù)概念特征，然后通過代數(shù)計(jì)算實(shí)現(xiàn)第4點(diǎn)的解題思路。思考題代表目標(biāo)函數(shù)的直線和其移動(dòng)方向如何確定？作業(yè)課后習(xí)題1－2，5-6實(shí)踐作業(yè)相關(guān)建模練習(xí)第三節(jié)單純形法原理—、LP問題解的概念線性規(guī)劃問題可行解滿足上述約束條件(1.7)、(1.8)的解X＝(x1，…，xn)T，稱為L(zhǎng)P問題的可行解。全部可行解的集合稱為可行域。最優(yōu)解使目標(biāo)函數(shù)(1.6)達(dá)到最大值的可行解稱為最優(yōu)解?；O(shè)A為約束方程組(1.7)的m×n階系數(shù)矩陣，(設(shè)n>m)，其秩為m，B是矩陣A中的一個(gè)m×m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個(gè)基。不失一般性，設(shè)B中的每一個(gè)列向量Pj(j=1，…，m)稱為基向量，與基向量Pj對(duì)應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的變量稱為非基變量?；庠诩s束方程組(1.7)中，令所有非基變量xm+1=xm+2=…=xn＝0，又因?yàn)橛校鶕?jù)克萊姆規(guī)則，由m個(gè)約束方程可解出m個(gè)基變量的唯一解XB=(x1，…，xm)T下。將這個(gè)解加上非基變量取0的值有X=(x1，x2…，xm,0,…,0)T，稱X為線性規(guī)劃問題的基解。顯然在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)m，故基解的總數(shù)不超過個(gè)?；尚薪鉂M足變量非負(fù)約束條件(1.8)的基解稱為基可行解?？尚谢鶎?duì)應(yīng)于基可行解的基稱為可行基。njjjbxP1(1.10)將式(1.9)代入式(1.10)得：所以由于集合中任意兩點(diǎn)連線上的點(diǎn)均在集合內(nèi)，所以C為凸集。引理線性規(guī)劃問題的可行解X＝(x1,…,xn)為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。證(1)必要性。由基可行解的定義顯然。(2)充分性。若向量p1,p2,…,pk線性獨(dú)立，則必有k≤m；當(dāng)k＝m時(shí)，它們恰好構(gòu)成一個(gè)基，從而X＝(xl，x2,…,xm，0，…，0)為相應(yīng)的基可行解。當(dāng)k<m時(shí)，則一定可以從其余列向量中找出(m-k)個(gè)與p1,p2，…，pk構(gòu)成一個(gè)基，其對(duì)應(yīng)的解恰為X，所以據(jù)定義它是基可行解。定理2線性規(guī)劃問題的基可行解X對(duì)應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn)。證本定理需要證明：X是可行域頂點(diǎn)X是基可行解。下面采用的是反證法，即證明：X不是可行域的頂點(diǎn)X不是基可行解。下面分兩步來證明。(1)X不是基可行解X不是可行域的頂點(diǎn)。不失一般性，假設(shè)X的前m個(gè)分量為正，故有(1.11)由引理知p1，…，pm，線性相關(guān)，即存在一組不全為零的數(shù)(i＝1，…，m)，使得有δ1P1+δ2P2+…+δmPm=0(1.12)(1.12)式乘上一個(gè)不為零的數(shù)μ得：μδ1P1+μδ2P2+…+μδmPm=0(1.13)(1.13)+(1.11)得：(x1+μδ1)P1+(x2+μδ2)P2+…+(xm+μδm)Pm=0(1.11)-(1.13)得：(x1-μδ1)P1+(x2-μδ2)P2+…+(xm-μδm)Pm=0令=［(x1+μδ1)P1,(x2+μδ2)P2,…,(xm+μδm)Pm,0,…,0］=［(x1-μδ1)P1,(x2-μδ2)P2,…,(xm-μδm)Pm,0,…,0］又μ可以這樣來選取，使得對(duì)所有i＝1，…，m有≥0由此∈C，∈C，又X＝+，即X不是可行域的頂點(diǎn)。(2)X不是可行域的頂點(diǎn)X不是基本可行解。不失一般性，設(shè)X＝(xl，x2，…，xr，o，…，o)不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另外兩個(gè)不同點(diǎn)Y和Z，有X=aY+(1-a)Z(0<a<1)，或可寫為：xj＝ayj+(1-a)zj(0<a<1;j=1，…,n)因a>O，1-a>0，故當(dāng)xj=0時(shí)，必有yj=zj=0因有(1.14)(1.15)(1.14)-(1.15)得因不全為零，故線形相關(guān)，即X不是基可行接解。定理3若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。證設(shè)是線性規(guī)劃的一個(gè)最優(yōu)解,njjjxcCXZ10)0(是目標(biāo)函數(shù)的最大值。若不是基可行解，由定理2知不是頂點(diǎn)，一定能在可行域內(nèi)找到通過的直線上的另外兩個(gè)點(diǎn)(njjjxcCXZ10)0(C(+μδ)=C+CC(-μδ)=C-C因C為目標(biāo)函數(shù)的最大值，故有≥C+C≥C-C由此Cμδ=0，即有C(+μδ)=C=C(-μδ)。如果(+μδ)或(-μδ)仍不是基可行解，按上面的方法繼續(xù)做下去，最后一定可以找到一個(gè)基可行解，其目標(biāo)函數(shù)值等于C，問題得證。四、單純形法迭代原理由上述定理3可知，如果線性規(guī)劃問題存在最優(yōu)解，一定有一個(gè)基可行解是最優(yōu)解。因此單純形法迭代的基本思路是：先找出一個(gè)基可行解，判斷其是否為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解為止。1.確定初始基可行解對(duì)標(biāo)準(zhǔn)型的線性規(guī)劃問題在約束條件(1.16)式的變量的系數(shù)矩陣中總會(huì)存在一個(gè)單位矩陣（1.18）當(dāng)線性規(guī)劃的約束條件均為≤號(hào)時(shí)，加上松弛變量的系數(shù)矩陣即為單位矩陣。對(duì)約束條件為≥或＝的情況，為便于找到初始基可行解，可以構(gòu)造人工基，人為產(chǎn)生一個(gè)單位矩陣，這將在本章第五節(jié)中討論。(1.18)式中,稱為基向量，同其對(duì)應(yīng)的變量稱為基變量，模型中的其它變量稱為非基變量。在(1.16)式中令所有非基變量等于零，即可找到一個(gè)解因有b≥0，故X滿足約束(1.17)，是一個(gè)基可行解。2.從一個(gè)基可行解轉(zhuǎn)換為相鄰的基可行解定義：兩個(gè)基可行解稱為相鄰的，如果它們之間變換且僅變換一個(gè)基變量。設(shè)初始基可行解中的前m個(gè)為基變量，即=代入約束條件(1.16)有（1.19）寫出(1.19)系數(shù)矩陣的增廣矩陣因是一個(gè)基，其它向量，可用這個(gè)基的線性組合來表示，有=或-=0（1.20）將(1.20)式乘上一個(gè)正的數(shù)θ>0得：θ(=)=0（1.21）(1.19)+(1.21)式并經(jīng)過整理后有（1.22）由(1.22)式找到滿足約束方程組的另一個(gè)點(diǎn)，有 =θ其中是的第j個(gè)坐標(biāo)的值。要使是一個(gè)基本可行解，因規(guī)定θ>0，故應(yīng)對(duì)所有i=1，…，m存在≥0(1.23)令這m個(gè)不等式中至少有一個(gè)等號(hào)成立。因?yàn)楫?dāng)時(shí)，(1.23)式顯然成立，故可令θ=min故是一個(gè)可行解。又因與變量對(duì)應(yīng)的向量，經(jīng)重新排列后加上b列有如下形式矩陣(不含b列)和增廣矩陣(含b列)因，故由上述矩陣元素組成的行列式不為零,是一個(gè)基。在上述增廣矩陣中進(jìn)行行的初等變換，將第行乘上，再分別乘以加到各行上去，則增廣矩陣左半部變成為單位矩陣，又因,故由此是同相鄰的基可行解，且由基向量組成的矩陣仍為單位矩陣。3.最優(yōu)性檢驗(yàn)和解的判別將基本可行解和分別代入目標(biāo)函數(shù)得（1.25）(1.25)式中因?yàn)榻o定，所以只要有，就有。通常簡(jiǎn)寫為，它是對(duì)線性規(guī)劃問題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo)志。(1)當(dāng)所有的時(shí)，表明現(xiàn)有頂點(diǎn)(基可行解)的目標(biāo)函數(shù)值比起相鄰各頂點(diǎn)(基可行解)的目標(biāo)函數(shù)值都大，根據(jù)線性規(guī)劃問題的可行域是凸集的證明及凸集的性質(zhì)，可以判定現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。(2)當(dāng)所有的，又對(duì)某個(gè)非基變量，且按(1.24)式可以找到，這表明可以找到另一頂點(diǎn)(基可行解)目標(biāo)函數(shù)值也達(dá)到最大。由于該兩點(diǎn)連線上的點(diǎn)也是可行域內(nèi)的點(diǎn)，且目標(biāo)函數(shù)值相等，即該線性規(guī)劃問題有無窮多最優(yōu)解。反之，當(dāng)所有非基變量的時(shí)，線性規(guī)劃問題具有唯一最優(yōu)解。(3)如果存在某個(gè)，由式(1.23)看出對(duì)任意的，均有，因而的取值可無限增大不受限制。由式(1.25)看到也可無限增大，表明線性規(guī)劃有無界解。思考題如何利用原理構(gòu)造算法？作業(yè)課后習(xí)題3，9，10實(shí)踐作業(yè)相關(guān)建模練習(xí)第四節(jié)單純形法計(jì)算步驟單純形法的計(jì)算步驟如下：第1步：求初始基可行解，列出初始單純形表。對(duì)非標(biāo)準(zhǔn)型的線性規(guī)劃問題首先要化成標(biāo)準(zhǔn)形式。由于總可以設(shè)法使約束方程的系數(shù)矩陣中包含一個(gè)單位矩陣，以此作為基求出問題的一個(gè)初始基可行解。為檢驗(yàn)一個(gè)基可行解是否最優(yōu)，需要將其目標(biāo)函數(shù)值與相鄰基可行解的目標(biāo)函數(shù)值進(jìn)行比較。為了書寫規(guī)范和便于計(jì)算，對(duì)單純形法的計(jì)算設(shè)計(jì)了一種專門表格，稱為單純形表(見表1-5)。迭代計(jì)算中每找出一個(gè)新的基可行解時(shí)，就重畫一張單純形表。含初始基可行解的單純形表稱初始單純形表，含最優(yōu)解的單純形表稱最終單純形表。表1-5cjc1…cm…cj…cncB基bx1…xm…xj…xnc1c2cmx1x2xmb1b2bm100…………001…………a1ja2jamj…………x1nx2nxmncj-zj0…0……單純形表結(jié)構(gòu)為：表的第2列～3列列出基可行解中的基變量及其取值。接下來列出問題中所有變量，基變量下面列是單位矩陣，非基變量xj，下面數(shù)字是該變量系數(shù)向量Pj表為基向量線性組合時(shí)的系數(shù)。因p1,...,pm是單位向量，故有表1-5最上端的一行數(shù)是各變量在目標(biāo)函數(shù)中的系數(shù)值，最左端一列數(shù)是與各基變量對(duì)應(yīng)的目標(biāo)函數(shù)中的系數(shù)值CB。對(duì)xj只要將它下面這一列數(shù)字與CB中同行的數(shù)字分別相乘，再用它上端cj值減去上述乘積之和有(1.26)對(duì)j＝1，…，n，將分別按(1.26)式求得的檢驗(yàn)數(shù)，或?qū)憺橛浫氡淼淖钕旅嬉恍?。?步：最優(yōu)性檢驗(yàn)。如表中所有檢驗(yàn)數(shù)，且基變量中不含有人工變量時(shí)，表中的基可行解即為最優(yōu)解，計(jì)算結(jié)束（對(duì)基變量中含人工變量時(shí)的解的最優(yōu)性檢驗(yàn)將在下一節(jié)中討論）。當(dāng)表中存在時(shí)，如有，則問題為無界解，計(jì)算結(jié)束；否則轉(zhuǎn)下一步。第3步：從一個(gè)基可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表。1.確定換入基的變量。只要有檢驗(yàn)數(shù)，對(duì)應(yīng)的變量就可作為換入基的變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，一般從中找出最大一個(gè)其對(duì)應(yīng)的變量，作為換入基的變量(簡(jiǎn)稱換入變量)。2.確定換出基的變量。根據(jù)上一節(jié)中確定θ的規(guī)則，對(duì)幾列由式(1.24)計(jì)算得到(1.27)確定，是換出基的變量(簡(jiǎn)稱換出變量)。元素決定了從一個(gè)基可行解到相鄰基可行解的轉(zhuǎn)移去向，取名主元素。3.用換入變量替換基變量中的換出變量，得到一個(gè)新的基(p1，…，pl-1，pk，pl+1,…,pm)。對(duì)應(yīng)這個(gè)基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫出一個(gè)新的單純形表(表l-6)。在這個(gè)新的表中的基仍應(yīng)是單位矩陣，即應(yīng)變換成單位向量。為此在表l—5中進(jìn)行行的初等變換，并將運(yùn)算結(jié)果填入表1—6相應(yīng)格中。(1)將主元素所在L行數(shù)字除以主元素alk，即有(1.28)(2)將表1-6中剛計(jì)算得到的第L行數(shù)字乘上(-aik)加到表1-5的第i行數(shù)字上，記入表1-6的相應(yīng)行。即有(1.29)表1-6……………基b……………1……0……0…0……0……1…0……1……0…Cj-Zj0……0……0…Cj-ZjCj-Zj由于表1-8中還存在大于零的檢驗(yàn)數(shù)，故重復(fù)上述步驟得表1-9。表1-9中所有，且基變量中不含人工變量，故表中的基可行解為最優(yōu)解，代入目標(biāo)函數(shù)得。表1-9Cj-Zj思考題如何在大于或等于的約束下構(gòu)造初始單位陣？作業(yè)課后習(xí)題4，8實(shí)踐作業(yè)相關(guān)建模練習(xí)第五節(jié)單純形法的進(jìn)一步討論一、人工變量法若化為標(biāo)準(zhǔn)形后的約束條件的系數(shù)矩陣中不存在單位矩陣。如例6用單純形法求解線性規(guī)劃問題解先將其化成標(biāo)準(zhǔn)形式有這種情況下，可以通過添加兩列單位向量，使連同約束條件中的向量P4構(gòu)成單位矩陣是人為添加上去的，它相當(dāng)于在上述問題的約束條件(1.32b)中添加變量約束條件(1.32c)中添加變量，變量相應(yīng)稱為人工變量。由于約束條件(1.32b)(1.32c)在添加人工變量前已是等式為使這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零。為此，令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負(fù)值，用“-M”代表?！?M”稱為“罰因子”，即只要人工變量取值大于零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最優(yōu)。因而添加人工變量后，例6的數(shù)學(xué)模型形式就變成為：該模型中與對(duì)應(yīng)的變量為基變量，令非基變量等于零，即得到初始基可行解，并列出初始單純形表，在單純形法迭代運(yùn)算中，M可當(dāng)作一個(gè)數(shù)學(xué)符號(hào)一起參加運(yùn)算。檢驗(yàn)數(shù)中含M符號(hào)的；當(dāng)M的系數(shù)為正時(shí)，該檢驗(yàn)數(shù)為正，當(dāng)M的系數(shù)為負(fù)時(shí)，該項(xiàng)檢驗(yàn)數(shù)為負(fù)。例6添加人工變量后，用單純形法求解的過程見表1-10。表1-10-30100-M-MCB基b0x441111000-Mx61-2[1]-10-110-Mx790310001Cj-Zj-2M-34M10-M000x4330211-100x21-21-10-110-Mx76[6]0403-31Cj-Zj6M-304M+103M-4M00000010301000-31100Cj-Zj0030-M--M+00000101001010Cj-Zj000-M二、兩階段法用大M法處理人工變量，在用手工計(jì)算求解時(shí)不會(huì)碰到麻煩。但用電子計(jì)算機(jī)求解時(shí),對(duì)M就只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字。如果線性規(guī)劃問題中的等參數(shù)值與這個(gè)代表M的數(shù)相對(duì)比較接近，或遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值上的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問題分兩個(gè)階段來計(jì)算，稱兩階段法。兩階段法的第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)(一般取1)，在保持原問題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。顯然在第一階段中，當(dāng)人工變量取值為。時(shí)，目標(biāo)函數(shù)值也為0。這時(shí)候的最優(yōu)解就是原線性規(guī)劃問題的一個(gè)基可行解。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問題無可行解。當(dāng)?shù)谝浑A段求解結(jié)果表明問題有可行解時(shí)，第二階段是在原問題中去除人工變量，并從此可行解(即第一階段的最優(yōu)解)出發(fā)，繼續(xù)尋找問題的最優(yōu)解。例6用兩階段法求解時(shí)，第一階段的線性規(guī)劃問題可寫為：用單純形法求解的過程見表1-1l。表1-1100000-1-1CB基b0x441111000-1x61-21-10-110-1x790310001Cj-Zj2400-1000x4330211-100x21-21-10-110-Mx7660403-31Cj-Zj60403-400000010301000-31100Cj-Zj00000-1-1第二階段是將表1—11中的人工變量除去，目標(biāo)函數(shù)改為：再從表1-ll中的最后一個(gè)表出發(fā)，繼續(xù)用單純形法計(jì)算，求解過程見表1-12。表1-12→-30100基b0x4000010x230100-3x11100Cj-Zj003000000101001010Cj-Zj000三、單純形法計(jì)算中的幾個(gè)問題1.目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判別。有些書中規(guī)定求目標(biāo)函數(shù)值的極小化作為線性規(guī)劃的標(biāo)準(zhǔn)形式，這時(shí)只需以所有檢驗(yàn)數(shù)作為判別表中解是否最優(yōu)的標(biāo)志。2.退化。按最小比值來確定換出基的變量時(shí)，有時(shí)出現(xiàn)存在兩個(gè)以上相同的最小比值，從而使下一個(gè)表的基可行解中出現(xiàn)一個(gè)或多個(gè)基變量等于零的退化解。退化解的出現(xiàn)原因是模型中存在多余的約束，使多個(gè)基可行解對(duì)應(yīng)同一頂點(diǎn)。當(dāng)存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)，盡管可能性極其微小。為避免出現(xiàn)計(jì)算的循環(huán)，1974年勃蘭特(Bland)提出了一個(gè)簡(jiǎn)便有效的規(guī)則：(1)當(dāng)存在多個(gè)時(shí)，始終選取下標(biāo)值為最小的變量作為換入變量；(2)當(dāng)計(jì)算值出現(xiàn)兩個(gè)以上相同的最小比值時(shí)，始終選取下標(biāo)值為最小的變量作為換出變量。3.無可行解的判別。本章第三節(jié)單純形法迭代原理中，講述了用單純形法求解時(shí)如何判別問題結(jié)局屬唯一最優(yōu)解、無窮多最優(yōu)解和無界解。當(dāng)線性規(guī)劃問題中添加人工變量后，無論用人工變量法或兩階段法，初始單純形表中的解因含非零人工變量，故實(shí)質(zhì)上是非可行解。當(dāng)求解結(jié)果出現(xiàn)所有時(shí)，如基變量中仍含有非零的人工變量(兩階段法求解時(shí)第一階段目標(biāo)函數(shù)值不等于零)，表明問題無可行解。例7用單純形法求解線性規(guī)劃問題解在圖解法一節(jié)中已看出本例無可行解?，F(xiàn)用單純形法求解，在添加松弛變量和人工變量后，模型可寫成以為基變量列出初始單純形表，進(jìn)行迭代計(jì)算，過程見表1-13。表中當(dāng)所有時(shí)，基變量中仍含有非零的人工變量,故例7的線性規(guī)劃問題無可行解。表1-13→2100-M基b02[1]1100-M6220-11Cj-Zj2+2M1+2M0-M02211100-M200-2-11Cj-Zj0-1-2-2M-M0四、單純形法小結(jié)1．步驟2.各種解的情況，即算法終止規(guī)則。思考題比較兩階段法和大M法。作業(yè)課后習(xí)題7，11，12實(shí)踐作業(yè)相關(guān)建模練習(xí)第六節(jié)應(yīng)用舉例一般來講，一個(gè)經(jīng)濟(jì)、管理問題要滿足下列條件，才能歸結(jié)為線性規(guī)劃的模型：①要求解的問題的目標(biāo)能用某種效益指標(biāo)度量大小程度，并能用線性函數(shù)描述目標(biāo)的要求；②為達(dá)到這個(gè)目標(biāo)存在多種方案；③要達(dá)到的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的，這些條件可用線性等式或不等式描述。下面通過一些例子來說明如何將一些實(shí)際問題歸結(jié)為線性規(guī)劃的數(shù)學(xué)模型。例8混合配料問題某糖果廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中A、B、C含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如表1-15所示。問該廠每月生產(chǎn)這三種牌號(hào)糖果各多少kg，使該廠獲利最大。試建立這個(gè)問題的線性規(guī)劃的數(shù)學(xué)模型。甲乙丙原料成本(元／kg)每月限制用量(kg)ABC≥60％≤20％≥30％≤50％≤60％2.001.501.00200025001200加工費(fèi)(元／kg)售價(jià)(元／kg)0.503.400.402.850.302.25解用i=1，2，3分別代表原料A，B，C，用j＝1，2，3分別代表甲、乙、丙三種糖果，為生產(chǎn)第j種糖果耗用的第i種原料的kg數(shù)。該廠的獲利為三種牌號(hào)糖果的售價(jià)減去相應(yīng)的加工費(fèi)和原料成本，三種糖果的生產(chǎn)量x甲，x乙，x丙分別為：x甲=x1l+x21+X31x乙=x12+x22+X32x丙=x13+X23+X33三種糖果的生產(chǎn)數(shù)量受到原材料月供應(yīng)量和原料含量成份的限制由此例8的數(shù)學(xué)模型可歸結(jié)為：例9方案選擇生產(chǎn)中經(jīng)常碰到這類問題：機(jī)器要維修或更新，工具要修理或新購，某種原材料的暫時(shí)短缺，或等待到貨，影響生產(chǎn)，或用另外的價(jià)格更昂貴的材料代替，等等。往往出現(xiàn)這種情況，若想快些，省一些時(shí)間，直接費(fèi)用的支出就要多一些；想少花些錢，時(shí)間要等得長(zhǎng)一些，就要增加其它有關(guān)費(fèi)用的支出。應(yīng)如何綜合考慮，使總的費(fèi)用為最小?？紤]以下例子。如某廠計(jì)劃期分為n個(gè)階段(一個(gè)階段可以是三天、五天、十天或一個(gè)月等)。在第j(j＝1，…，n)個(gè)階段，生產(chǎn)上要用rj個(gè)專用工具。到階段末，凡在這個(gè)階段內(nèi)使用過的工具都應(yīng)送去修理后才能再使用。修理可分兩種方式進(jìn)行，一種稱為慢修，就是等某種規(guī)格工具積壓到一定批量后集中修，這樣費(fèi)用便宜些(每修一個(gè)需b元)，時(shí)間長(zhǎng)一些(需p個(gè)階