運(yùn)籌學(xué)第二章線(xiàn)性規(guī)劃與單純形法

運(yùn)籌帷幄之中決勝千里之外線(xiàn)性規(guī)劃與單純形法起源1939年蘇聯(lián)康托洛維奇（H.B.Kahtopob）、美國(guó)希奇柯克（F.L.Hitchcock）提出1947年，旦茨格，單純形方法1951年由庫(kù)恩（H.W.Kuhn）和塔克（A.W.Tucker），非線(xiàn)性規(guī)劃到了70年代，數(shù)學(xué)規(guī)劃發(fā)展迅速起源運(yùn)籌學(xué)問(wèn)題典型模式：給出一個(gè)目標(biāo)函數(shù)及一批約束條件,要在約束條件的限制下求目標(biāo)函數(shù)的最優(yōu)值。當(dāng)目標(biāo)函數(shù)是線(xiàn)性的，而且約束條件是線(xiàn)性的等式或不等式時(shí),稱(chēng)為線(xiàn)性規(guī)劃。當(dāng)其中有非線(xiàn)性函數(shù)時(shí)則稱(chēng)為非線(xiàn)性規(guī)劃。當(dāng)須求其整數(shù)解時(shí),則稱(chēng)為整數(shù)規(guī)劃。第一章線(xiàn)性規(guī)劃與單純形法第一節(jié)線(xiàn)性規(guī)劃及其數(shù)學(xué)模型第二節(jié)圖解法和解的性質(zhì)第三節(jié)單純形法第四節(jié)單純形法的進(jìn)一步討論第五節(jié)線(xiàn)性規(guī)劃應(yīng)用舉例本章學(xué)習(xí)目的和要求

通過(guò)本章的學(xué)習(xí)，要求學(xué)員掌握如何建立線(xiàn)性規(guī)劃模型，了解線(xiàn)性規(guī)劃的圖解法，深刻理解單純形法的解題思路，熟練掌握其運(yùn)算步驟，并能在實(shí)際問(wèn)題中加以運(yùn)用。1．已有一定數(shù)量的人力、物力、財(cái)力資源，研究如何充分合理地使用才能使完成的任務(wù)量最大。2．當(dāng)一項(xiàng)任務(wù)量確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)耗費(fèi)的資源量為最小。主要研究第一節(jié)線(xiàn)性規(guī)劃及其數(shù)學(xué)模型一、實(shí)例

【例1-1】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表1-2所示。

資源產(chǎn)品ⅠⅡ

擁有量設(shè)備128臺(tái)時(shí)原材料A4016kg原材料B0412kg每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多?表1-1用數(shù)學(xué)關(guān)系式描述這個(gè)問(wèn)題得到本問(wèn)題的數(shù)學(xué)模型為:【例1-2】靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)立方米，在兩個(gè)工廠之間有一條流量為每天200萬(wàn)立方米的支流。

化工廠1每天排放含有某種有害物質(zhì)的工業(yè)污水2萬(wàn)立方米，化工廠2每天排放的工業(yè)污水為1.4萬(wàn)立方米。從化工廠1排出的污水流到化工廠2前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。因此兩個(gè)工廠都需處理一部分工業(yè)污水。化工廠1處理污水的成本是1000元/萬(wàn)立方米,化工廠2處理污水的成本是800元/萬(wàn)立方米。問(wèn):在滿(mǎn)足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個(gè)工廠處理工業(yè)污水的總費(fèi)用最小。得到本問(wèn)題的數(shù)學(xué)模型為：【課堂練習(xí)】某廠生產(chǎn)P、Q兩種產(chǎn)品，主要消耗A、B、C三種原料，已知單位產(chǎn)品的原料消耗數(shù)量等資料如表所示。產(chǎn)品單位消耗原料PQ原料總量/噸AB品利潤(rùn)2萬(wàn)元5萬(wàn)元要求確定P、Q的產(chǎn)量，使利潤(rùn)最大。解：設(shè)P、Q的產(chǎn)量分別為x1，x2，即決策變量目標(biāo)函數(shù)？約束條件？產(chǎn)品單位消耗原料PQ原料總量/噸AB品利潤(rùn)2萬(wàn)元5萬(wàn)元問(wèn)題的數(shù)學(xué)模型為：

上述三個(gè)問(wèn)題屬于同一類(lèi)型的決策優(yōu)化問(wèn)題，它們具有下列共同特點(diǎn)：（1）每個(gè)行動(dòng)方案可用一組變量（x1，…，xn）的值表示，這些變量一般取非負(fù)值；（2）變量的變化要受某些限制，這些限制條件用一些線(xiàn)性等式或不等式表示；（3）有一個(gè)需要優(yōu)化的目標(biāo)，它也是變量的線(xiàn)性函數(shù)。

具備以上三個(gè)特點(diǎn)的數(shù)學(xué)模型稱(chēng)為線(xiàn)性規(guī)劃（LinearProgramming，簡(jiǎn)記為L(zhǎng)P）。

線(xiàn)性規(guī)劃模型的一般形式：（1-3）（1-2）（1-1）1、變量x1，x2，…，xn稱(chēng)為決策變量2、目標(biāo)函數(shù)中變量系數(shù)cj稱(chēng)為價(jià)值系數(shù)3、bi稱(chēng)為右端常數(shù)，約束條件（1-3）稱(chēng)為非負(fù)約束4、（1-2）為技術(shù)約束，系數(shù)aij稱(chēng)為技術(shù)系數(shù)5、滿(mǎn)足全部約束條件的變量值（x1，…xn）稱(chēng)為可行解，其集合稱(chēng)為可行域，記為R；6、使目標(biāo)函數(shù)取得最大（最?。┲档目尚薪猓▁1，…xn）稱(chēng)為最優(yōu)解。

采用求和符號(hào)Σ，線(xiàn)性規(guī)劃的一般形式可以簡(jiǎn)寫(xiě)為：向量形式：式中：X=（x1，x2，…，xn）T

C=（c1，c2，…，cn）

b=（b1，b2，…，bm）T

Pj=（a1j，a2j，…，amj）T

A=（aij）m×n

矩陣和向量形式：二、線(xiàn)形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（其中常數(shù)b1，b2，…，bm≥0（若bi<0，兩邊乘-1））。

線(xiàn)性規(guī)劃標(biāo)準(zhǔn)形式的特點(diǎn)：1.目標(biāo)函數(shù)限定求最大值2.技術(shù)約束條件全部是等式約束LP標(biāo)準(zhǔn)形式的矩陣式？LP標(biāo)準(zhǔn)形式的向量式？將一般形式線(xiàn)性規(guī)劃模型化為標(biāo)準(zhǔn)型的方法:（1）目標(biāo)函數(shù)將一般形式線(xiàn)性規(guī)劃模型化為標(biāo)準(zhǔn)型的方法:（2）不等式約束方程x1+x2≤0→x1+x2+x3=0x3非負(fù)松弛變量x1+x2≥0→x1+x2–x4=0x4非負(fù)剩余變量將一般形式線(xiàn)性規(guī)劃模型化為標(biāo)準(zhǔn)型的方法:（3）無(wú)約束決策變量xk令其中【例1-4】把LP問(wèn)題

化為標(biāo)準(zhǔn)形式解：在三個(gè)技術(shù)約束中，分別加入松弛變量x3，x4，x5，問(wèn)題化為標(biāo)準(zhǔn)形式：

化為標(biāo)準(zhǔn)形式【例1-5】把LP問(wèn)題

一、圖解法（決策變量個(gè)數(shù)n=2）【例1-6】

求下列問(wèn)題的最優(yōu)解。

第二節(jié)圖解法及解的性質(zhì)可行解圖形的確定目標(biāo)值在（4，2）點(diǎn)，達(dá)到最大值14等值線(xiàn)與最優(yōu)解的確定（1）無(wú)窮多最優(yōu)解(多重最優(yōu)解)（2）無(wú)界解（3）無(wú)可行解通過(guò)圖解法，可觀察到線(xiàn)性規(guī)劃的解還可能出現(xiàn)的幾種情況（對(duì)應(yīng)方案）：目標(biāo)函數(shù)maxz=2x1+4x2

無(wú)窮多最優(yōu)解

無(wú)界解!

當(dāng)存在相互矛盾的約束條件時(shí)，線(xiàn)性規(guī)劃問(wèn)題的可行域?yàn)榭占＠?無(wú)可行解的情形增加的約束條件可行域?yàn)榭占?，無(wú)可行解。圖解法得到的啟示1.求解線(xiàn)性規(guī)劃問(wèn)題時(shí)，解的情況有：唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解。2.若線(xiàn)性規(guī)劃問(wèn)題的可行域存在，則可行域是一凸集。3.若線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解存在，則最優(yōu)解一定在某個(gè)頂點(diǎn)可達(dá)到。4.解題思路是：先找出凸集的任一頂點(diǎn)，計(jì)算Z值，比較相鄰頂點(diǎn)Z值，如大，轉(zhuǎn)到相鄰頂點(diǎn)，一直到找出使Z值最大的頂點(diǎn)為止。二、線(xiàn)性規(guī)劃問(wèn)題的解的概念1.可行解2.基3.基可行解4.可行基二、線(xiàn)性規(guī)劃問(wèn)題的解的概念滿(mǎn)足約束條件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的可行解其中使目標(biāo)函數(shù)達(dá)最大值的可行解為最優(yōu)解。1.可行解LP問(wèn)題二、線(xiàn)性規(guī)劃問(wèn)題的解的概念2.基，基向量，基變量設(shè)系數(shù)矩陣

A=(P1,P2,…,Pn)的秩為m，若非B=(Pj1,Pj2,…,Pjm)奇異，則稱(chēng)B是LP問(wèn)題的一個(gè)基，稱(chēng)Pjk(1≤k≤m)為基向量；xjk(k=1,2,…,m)為相應(yīng)于Pjk的基變量，其余稱(chēng)為非基變量。二、線(xiàn)性規(guī)劃問(wèn)題的解的概念設(shè)基B=（，，…，），稱(chēng)對(duì)應(yīng)的變量，，…，為基變量，其它的變量稱(chēng)為非基變量。令非基變量等于0，從方程組可唯一解出基變量的值，從而得到一個(gè)解，稱(chēng)為基解；若基解各個(gè)分量非負(fù)，即它又是可行解，則稱(chēng)之為基可行解，對(duì)應(yīng)的基稱(chēng)為可行基。3.基解，基可行解，可行基二、線(xiàn)性規(guī)劃問(wèn)題的解的概念3.基解，基可行解，可行基可行解是約束方程組的解，并且滿(mǎn)足非負(fù)條件；基解是約束方程組具有特定性質(zhì)的解，它至多有m個(gè)非0分量，但未必滿(mǎn)足非負(fù)性。基可行解同時(shí)具有兩者的性質(zhì)。二、線(xiàn)性規(guī)劃問(wèn)題的解的概念約束方程組(1-5)具有的基解的數(shù)目最多是個(gè)，一般基可行解的數(shù)目要小于基解的數(shù)目。不同解之間的關(guān)系3.基解，基可行解，可行基【例1-7】它的系數(shù)矩陣為：

A的子矩陣（P3，P4，P5）正好是單位矩陣，這種形式的方程組稱(chēng)為典式，或稱(chēng)為對(duì)x3，x4，x5的解出形式。以（P3，P4，P5）為基，令非基變量x1=x2=0，則基變量正好等于右端常數(shù)值，得到基可行解X=（0，0，8，20，12）T。所有基解見(jiàn)表1-3序號(hào)B的選擇基解是否可行解對(duì)應(yīng)頂點(diǎn)12345678910（P1，P2，P3）（P1，P2，P4）（P1，P2，P5）（P1，P3，P4）（P1，P3，P5）（P1，P4，P5）（P2，P3，P4）（P2，P3，P5）（P2，P4，P5）（P3，P4，P5）(14/5，3，-4/5，0，0)T(2，3，0，4，0)T(3，5/2，0，0，2)T不是基(4，0，4，0，12)T(8，0，0，-20，12)T(0，3，2，14，0)T(0，-10，-12，0，-28)T(0，4，0，12，-4)T(0，0，8，20，12)T×√√

√×√××√

Q3Q2

Q1

Q4

O基可行解至多有個(gè)

二、線(xiàn)性規(guī)劃問(wèn)題的解的概念3.基解，基可行解，可行基三、LP解的性質(zhì)定理1

線(xiàn)性規(guī)劃的可行域R是凸集。定理2

線(xiàn)性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)。定理3

若可行域有界，線(xiàn)性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。線(xiàn)性規(guī)劃問(wèn)題求解：采用“枚舉法”找所有基可行解，然后一一比較，最終必然能找到最優(yōu)解。但當(dāng)n,m較大時(shí)，這種辦法是行不通的，所以要繼續(xù)討論如何有效尋找最優(yōu)解的方法。本課程將主要介紹單純形法。第三節(jié)單純形法

（重點(diǎn)）一、單純形法的基本原理和思路二、單純形法的求解方法三﹑單純形法的計(jì)算步驟一﹑單純形法的基本原理和思路基本原理：1）可行域是凸集；2）基可行解與可行域頂點(diǎn)一一對(duì)應(yīng)；3）若可行域有界，目標(biāo)函數(shù)一定可在頂點(diǎn)達(dá)最優(yōu)?？尚杏駾基可行解最優(yōu)解

根據(jù)原理可知：要求線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解，只要在可行域的頂點(diǎn)中找出最優(yōu)解頂點(diǎn)。思路：首先求出一個(gè)頂點(diǎn)(基可行解)，并判斷是否是最優(yōu)解，如果是求解結(jié)束，如果不是就進(jìn)行下一步；第二步轉(zhuǎn)換到另一個(gè)頂點(diǎn)(另一個(gè)基可行解)，并判斷是否是最優(yōu)解，如果是求解結(jié)束，如果不是就重復(fù)進(jìn)行第二步，直至目標(biāo)函數(shù)達(dá)到最優(yōu)。具體工作：(1)如何求出初始基可行解？(2)如何判斷一個(gè)基可行解是否是最優(yōu)？(3)如何從一基可行解轉(zhuǎn)換到另一更優(yōu)的基可行解？一﹑單純形法的基本原理和思路二﹑單純形法的求解方法1.確定初始基可行解，只要找出初始可行基。(1)

直接觀察法：從系數(shù)矩陣A

中直接觀察出一個(gè)初始基（2）化標(biāo)準(zhǔn)型法

如果所有約束條件都是“≤”形式的不等式，則可以利用化標(biāo)準(zhǔn)型的方法，在每個(gè)約束條件的左端加上一個(gè)松弛變量。重新對(duì)xj及aij進(jìn)行編號(hào)，可得下列方程組：從中可得單位矩陣以B作為可行基。將(2.3)移項(xiàng)得令xm+1=…=xn=0則

xi

=bi

(i=1，2，…m)又因bi≥0(標(biāo)準(zhǔn)型中規(guī)定)，則得一初始基可行解X=(b1,b2,…,bm,0,…,0)T（2）化標(biāo)準(zhǔn)型法

當(dāng)所有約束條件都是“≥”形式的不等式或等式約束時(shí)，如果不存在單位矩陣，就采用人工變量法:①對(duì)不等式約束左端減去一個(gè)非負(fù)的剩余變量，再加上一個(gè)非負(fù)的人工變量；②對(duì)等式約束左端再加上一個(gè)非負(fù)的人工變量。這樣就可以得到一個(gè)單位矩陣，即總能得到一個(gè)初始可行基。具體方法下節(jié)介紹。（3）人工變量法設(shè)線(xiàn)性規(guī)劃問(wèn)題的約束條件是分別對(duì)各約束方程加人工變量xn+1,xn+2,…,xn+m可得（3）人工變量法2.最優(yōu)性檢驗(yàn)與解的判別線(xiàn)性規(guī)劃問(wèn)題的求解結(jié)果唯一最優(yōu)解無(wú)窮多最優(yōu)解無(wú)界解無(wú)可行解如何判別？線(xiàn)性規(guī)劃問(wèn)題的求解結(jié)果唯一最優(yōu)解無(wú)窮多最優(yōu)解無(wú)界解無(wú)可行解如何判別？

由上述初始基可行解確定的討論，可知約束方程組變成下面的形式：2.最優(yōu)性檢驗(yàn)與解的判別由初始基可行解開(kāi)始進(jìn)行從一個(gè)基可行解到另一個(gè)更優(yōu)基可行解的求解過(guò)程中，每一次求基可行解時(shí)，約束方程組都化成上述形式。為了便于討論，把它記成一般形式。轉(zhuǎn)換迭代過(guò)程中的一般形式為：把(2.7)式代入目標(biāo)函數(shù)中可得一般形式：令于是再令則

假設(shè)X(0)=(b1′,b2′,…,bm′,0,…,0)T

是一個(gè)基可行解，則有下列判斷定理：1.最優(yōu)解：如果對(duì)一切j=m+1，…，n有δj≤0，則X(0)為最優(yōu)解(注意，這里是針對(duì)目標(biāo)函數(shù)求極大而言的)。2.無(wú)窮多最優(yōu)解：如果對(duì)一切j=m+1，…，n

有δj≤0，又存在δm+k=0，則線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。3.無(wú)界解：如果有一個(gè)δm+k﹥0，且對(duì)i=1,…,m有ai,m+k≤0，則線(xiàn)性規(guī)劃問(wèn)題有無(wú)界解(無(wú)最優(yōu)解)?；儞Q：在單純形法求解中，如果得到了某一個(gè)基可行解，并判斷了它不是最優(yōu)解，就要從該基變換成另一個(gè)更優(yōu)的基并求出新的基可行解。方法：第一步確定換入非基變量；第二步確定換出基變量；第三步將所確定的一對(duì)變量對(duì)應(yīng)的系數(shù)列向量對(duì)換得到新的基，求出新的基可行解。3.基變換(1)換入變量的確定再看(2.8)式其中

當(dāng)某些δj＞0時(shí)，xj

增加會(huì)使目標(biāo)函數(shù)值增加，我們就要從中確定一個(gè)非基變量xj換到基變量中。

方法：把δj值最大者所對(duì)應(yīng)的變量換入。即若則對(duì)應(yīng)的變量xk為換入變量,這樣的迭代速度最快。設(shè)B＝(p1,p2,…,pm)是一個(gè)基，與之對(duì)應(yīng)的基可行解為X(0)=(x1(0),x2(0),…,xm(0)

,0,…,0

)T

。pm+1,pm+2,…,pm+t,…,pn為非基向量。設(shè)確定pm+t

為換入非基向量。于是其中βim+t為一組不全為0的數(shù)(j=1，…，m)。(1)換出變量的確定不妨設(shè)θ為一正數(shù)，則有恒等式

或根據(jù)(2.9)可如下確定換出變量：令確定xl為換出變量。因?yàn)棰賞j

(j=1，…，m,j≠l)，pm+t

線(xiàn)性無(wú)關(guān)；②存在基可行解。①pj

(j=1，…，m,j≠l)，pm+t

線(xiàn)性無(wú)關(guān)，它們是一組基；②存在基可行解。X(1)是一個(gè)基可行解。構(gòu)造一個(gè)新基可行解！！4﹒基變換的系數(shù)矩陣法以下列形式的約束方程組進(jìn)行討論。m×m單位矩陣是基，

x1,x2,…,xm是基變量?？傻没尚薪釾(0)=(b1,b2,…,bm,0,…,0)T。

如果X(0)不是最優(yōu)，則需作基變換。設(shè)xk為確定的換入變量，顯然θ為（？）在迭代過(guò)程中θ可表示為于是可確定xl為換出變量。

下面就要把xk，xl所對(duì)應(yīng)的向量pk=(a1k,a2k,…,amk)T

和pl=(0,…,1,…,0)T

進(jìn)行交換，并且要把pk變?yōu)閱挝幌蛄俊?2.10)式的增廣矩陣為

我們將通過(guò)系數(shù)矩陣的增廣矩陣進(jìn)行初等變換來(lái)實(shí)現(xiàn)基變換。交換步驟：①將(2.11)式中第l行除以alk

；②將(2.11)式中xk列的各元素，除了alk

變換為1以外，其它都應(yīng)變?yōu)?。第i

行(i≠l)的變換是：將用(第

i行)－(經(jīng)過(guò)①變換以后的第l

行乘以aik)。變換以后系數(shù)矩陣各元素的變換關(guān)系式：顯然b’是基變量的取值，肯定非負(fù)，θ經(jīng)過(guò)變換后的新增廣矩陣為：1…-a1k／alk…0

a1m+1′…0…a1n

′

0…+1／alk…0alm+1′…1…aln′·················0…-amk／alk…1amm+1′…0…amn′

(2.12)················x1…xl…xm

xm+1…xk…xnbb1′bl′bm′﹒﹒新的基可行解：

由(2.12)式可知x1

，…，xk

，…，xm的系數(shù)列向量構(gòu)成m×m單位矩陣，它是可行基。于是得到一個(gè)基可行解X(1)：X(1)=(b1′,…,bl-1′

,0,bl+1′…,bm′,0,…,bl′,0…,0)T把元素alk稱(chēng)為主元素，它所在的列稱(chēng)為主列，它所在的行稱(chēng)為主行。初始基可行解的確定，其方法如下：(1)直接觀察(2)加松弛變量(3)加非負(fù)的人工變量畫(huà)單純形表，最優(yōu)性檢驗(yàn)與解的判斷基變換(1)確定換入變量(2)確定換出變量迭代（旋轉(zhuǎn)運(yùn)算）三﹑單純形法的計(jì)算步驟1.單純形表

將約束方程組與目標(biāo)函數(shù)組成n+1個(gè)變量，m+1個(gè)方程的方程組。01

0…0

a1m+1…a1n

001…0a2m+1…a2n·················000…1amm+1…amn

－z

x1

x2…xm

xm+1…xnbb1b2bm﹒1c1

c2…cm

cm+1…cn

0將上述方程組寫(xiě)成增廣矩陣

x1+a1m+1xm+1+…+a1nxn＝b1

x2+a2m+1xm+1+…+a2nxn＝b2·····················

xm+amm+1xm+1+…+amnxn＝bm－z+c1x1+c2x2+…+cmxm

+cm+1xm+1+…+cnxn＝001

0…0

a1m+1…a1n001…0a2m+1…a2n·················000…1amm+1…amn

－zx1x2…xmxm+1

…xnbb1b2bm﹒1c1c2…cmcm+1

…cn

0將上述方程組寫(xiě)成增廣矩陣

將

z看作不參與基變換的基變量，它與x1，x2，…，xm的系數(shù)構(gòu)成一個(gè)基。采用初等行變換將c1

c2…cm

變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣?？傻茫?1

0…0

a1m+1……………a1n

001…0a2m+1……………a2n·················000…1amm+1……………amn

－zx1x2…xmxm+1……………xnbb1b2bm﹒－∑cibi100…0cm+1－∑ciaim+1…cn

－∑ciain

m

i=1m

i=1m

i=1根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表：非基變量檢驗(yàn)數(shù)δj

。cjc1…cmcm+1…cnθiCBXBbx1…xmxm+1…xnc1c2·cmx1x2·xmb1b2·bm10·0…………00·1a1m+1a2m+1·amm+1…………a1na2n·amnθ1θ2·θm－zm－∑cibii=10…0cm+1－

m∑ciaim+1i=1cn－

m∑ciaini=1計(jì)算表1—1：XB列中填入基變量，這里是x1，x2，…，xm；CB列中填入基變量的價(jià)值系數(shù)，它們與基變量對(duì)應(yīng)；b列中填入約束方程組右端的常數(shù)；

cj行中填入變量的價(jià)值系數(shù)c1，c2，…cn；θi列中的數(shù)字是在確定換入變量后，按θ

規(guī)則計(jì)算后填入；最后一行稱(chēng)為檢驗(yàn)數(shù)行，對(duì)應(yīng)各非基變量。非基變量檢驗(yàn)數(shù)δj

。單純形表(1)按數(shù)學(xué)模型確定初始可行基和初始基可行解，建立初始單純形表。(2)計(jì)算各非基變量xj的檢驗(yàn)數(shù)，檢查檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)則已得到最優(yōu)解，可停止計(jì)算。否則轉(zhuǎn)入下一步(3)在δj＞0,j=m+1,…,n中，若有某個(gè)δk對(duì)應(yīng)xk的系數(shù)列向量Pk≤0，則此問(wèn)題是無(wú)界，停止計(jì)算。否則，轉(zhuǎn)入下一步。2、單純形法的求解步驟(4)根據(jù)max(δj＞0)=δk，確定xk為換入變量，按θ規(guī)則計(jì)算(5)以alk為主元素進(jìn)行迭代(即用高斯消去法或稱(chēng)為旋轉(zhuǎn)運(yùn)算)，把xk所對(duì)應(yīng)的列向量將XB列中的xl換為xk，得到新的單純形表。重復(fù)(2)～(5)，直到終止。

【例1-7】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如下表1-4所示。資源產(chǎn)品ⅠⅡ

擁有量設(shè)備128臺(tái)時(shí)原材料A4016kg原材料B0412kg每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多?

maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0maxz＝2x1+3x2+0x3+0x4+0x5x1＋2x2＋x3＝84x1＋x4＝164x2＋x5＝12x1﹐x2﹐x3﹐x4﹐x5≥0化標(biāo)準(zhǔn)型(1)確定初始基可行解：由標(biāo)準(zhǔn)型中的約束方程組可知變量x3，x4，x5

，所對(duì)應(yīng)的系數(shù)向量構(gòu)成3×3單位矩陣為一基。可得初始基可行解X(0）=(0，0，8，16，12)T，生成單純形表cj23000θiCBXBbx1x2x3x4X5000x3x4x581612140204100010001

表1－1：δj解：cj23000θiCBXBbx1x2x3x4x5000x3x4x581612140204100010001

000表1－1：δj23cj23000θiCBXBbx1x2x3x4x5000x3x4x58161214020[4]100010001－

000表1－1：δj2343cj23000θiCBXBbx1x2x3x4x5003x3x4x22163140001100010－1/201/4－

000表1－2：基可行解X(1)=(0，3，2，16，0)Tδj2-3/424

cj23000θiCBXBbx1x2x3x4x5000x3x4x58161214020[4]100010001－

000表1－1：δj2343cj23000θiCBXBbx1x2x3x4x5003x3x4x22163[1]40001100010－1/201/424－2000－3/4基可行解X(1)=(0，3，2，16，0)T表1－2：δjcj23000θiCBXBbx1x2x3x4x5203x1x4x22831000011－40010－1/221/4－

000表1－3：基可行解X(2)=(2，3，0，8，0)Tδj－21/4412cj23000θiCBXBbx1x2x3x4x5203x1x4x22831000011－40010－1/2[2]1/4－412

00－201/4表1－3：基可行解X(2)=(2，3，0，8，0)Tδjcj23000θiCBXBbx1x2x3x4x5203x1x5x24421000010－21/21/41/2－1/8010

000表1－4：最優(yōu)解X(3)=(4，2，0，0，4)T

，z=14δj－3/2－1/8求minz

的情況

這時(shí)可以有兩種處理方式：一種方式是令z1=－z，轉(zhuǎn)化為求maxz1，另一種是直接計(jì)算。最優(yōu)性檢驗(yàn)條件改為：所有σj≥0；換入變量確定法則改為：如果則xk為換入變量。單純形法的其它要點(diǎn)完全無(wú)須改變。單純形法小結(jié)求解過(guò)程確定初始基可行解判斷是否是最優(yōu)解是，求解結(jié)束；（或者無(wú)最優(yōu)解）否。確定換入換出變量基變換，得到新的可行基轉(zhuǎn)入第二步，重復(fù)。

【課堂練習(xí)】

【作業(yè)】

p441.1(1)(2)1.2(1)只變換成標(biāo)準(zhǔn)型，不求解。用單純形方法求解第四節(jié)單純形法的進(jìn)一步討論

一、人工變量法【例1-8】求下列LP問(wèn)題的最優(yōu)解1、問(wèn)題引入人工變量法基本思想：加入人工變量，構(gòu)造一個(gè)單位矩陣作為初始可行基，假定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M(M為任意大的正數(shù))，再通過(guò)單純形迭代將它們逐個(gè)地從基變量中替換出來(lái)。若經(jīng)過(guò)基的變換，基變量中不再含有非零的人工變量，這表示原問(wèn)題有解。若在最終表中當(dāng)所有Cj-zj≤0，而基變量中還有某個(gè)非零人工變量，這表示無(wú)可行解。分為：大M法兩階段法【例1-8】求下列LP問(wèn)題的最優(yōu)解2.大M法解：標(biāo)準(zhǔn)化后可見(jiàn)沒(méi)有初始單位可行基，加人工變量大M法然后用單純形法求解初始單純形表3500-Mb00-M412181030221000100013500-Mb00-M412181030221000100013+3M5+2M000初始單純形表3500-Mb00-M412181030221000100013+3M5+2M000初始單純形表3500-Mb00-M412181030221000100014-63+3M5+2M000初始單純形表3500-Mb00-M412181030221000100014-63+3M5+2M000初始單純形表3500-Mb30-M412610002210-3010001第一次迭代3500-Mb30-M412610002210-301000105+2M-3-3M00第一次迭代3500-Mb30-M412610002210-301000105+2M-3-3M00第一次迭代3500-Mb30-M412610002210-3010001-6305+2M-3-3M00第一次迭代3500-Mb30-M412610002210-3010001-

6

305+2M-3-3M00第一次迭代3500-Mb30546310000113-1.50100-10.5

4

2-004.50-M-2.5第二次迭代3500-Mb30546310000113-1.50100-10.5

4

2-004.50-M-2.5第二次迭代3500-Mb305226100001010-1/31/31/21/3-1/30000-1.5-M-1第三次迭代最優(yōu)解X(3)=(2，6，2，0，0)T

，z=36

MaxZ（X）=x1+2x2x1+x2≤510x1+7x2≥70x1，x2≥0[]所有的檢驗(yàn)數(shù)都小于或等于零，但人工變量x5仍未從基變量中退出，這表明原問(wèn)題無(wú)可行解?！?

MaxZ（X）=x1+2x2x1+x2+x3=510x1+7x2-x4=70x1，…，x4≥0+x5-Mx5，x5【例1-9】回顧1、單純形方法求解步驟2、求minz的情況有兩種處理方式：一種方式是令z1=－z，轉(zhuǎn)化為求maxz1；另一種是直接計(jì)算。最優(yōu)性檢驗(yàn)條件改為：所有δj≥0；換入變量確定法則改為：如果則xk為換入變量。加人工變量時(shí)，目標(biāo)函數(shù)改為+Mx。單純形法的其它要點(diǎn)完全無(wú)須改變。【例1-10】用大M法求解如下線(xiàn)性規(guī)劃問(wèn)題解：在上述問(wèn)題的約束條件中加入松弛變量、剩余變量和人工變量，得到其中M是一個(gè)任意大的正數(shù)。建立單純形表：cj-31100MMiCBXBbx1x2x3x4x5x6x70x4111-211000Mx63-4120-110Mx71-2010001j000-3+6M1-M1-3MM1113/21cj-31100MMiCBXBbx1x2x3x4x5x6x70x4103-20100-1Mx610100-11-21x31-2010001j000-11-M3M-1M1-1-單純形表2cj-31100MMiCBXBbx1x2x3x4x5x6x70x4123001-22-51x210100-11-21x31-2010001j000-1M-1M+1134--單純形表3cj-31100MMiCBXBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3j0001/3M-1/3M-2/31/3最優(yōu)解X=(4,1,9,0,0,0,0)，minZ=-2。單純形表43.兩階段法用計(jì)算機(jī)求解含有人工變量的線(xiàn)性規(guī)劃問(wèn)題時(shí)，只能用很大的數(shù)代替M，這就可能造成計(jì)算上的錯(cuò)誤。引入兩階段法求解。

第一階段，不考慮原問(wèn)題是否存在基可行解；給原線(xiàn)性規(guī)劃問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。即

再利用單純形法求解上述模型，若ω最優(yōu)值為0，則原問(wèn)題有解，可進(jìn)行第二階段計(jì)算。否則原問(wèn)題無(wú)可行解。3.兩階段法

第一階段，不考慮原問(wèn)題是否存在基可行解；給原線(xiàn)性規(guī)劃問(wèn)題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。再利用單純形法求解上述模型，若ω最優(yōu)值為0，則原問(wèn)題有解，可進(jìn)行第二階段計(jì)算。否則原問(wèn)題無(wú)可行解。3.兩階段法

第二階段，將第一階段計(jì)算得到的最終表，除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表。各階段的計(jì)算方法與前面的單純形法相同?！纠?-10】用兩階段法求解線(xiàn)性規(guī)劃問(wèn)題解：添加人工變量，給出第一階段的數(shù)學(xué)模型為:用單純形法求解得到的最后結(jié)果為：此時(shí)，得到的最優(yōu)解為=0，X=（0，1，1，12，0，0，0），它是原LP問(wèn)題的基可行解，因此可以進(jìn)行第二階段的計(jì)算。cj0000011iCBXBbx1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-20100000000011j第二階段的初始單純形表為：cj0000011iCBXBbx1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2010000-10001-31100011j原LP問(wèn)題的基可行解X=（0，1，1，12，0，0，0），Z=2cj-31100iCBXBbx1x2x3x4x5-3x141001/3-2/31x210100-11x390012/3-4/3j0001/31/3最優(yōu)解X=(4,1,9,0,0,0,0)，minZ=-2。最終單純形表二、退化在單純形法計(jì)算中用θ規(guī)則確定換出變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，這就出現(xiàn)了退化解。這時(shí)換出變量xl=0，迭代后目標(biāo)函數(shù)值不變。這時(shí)不同基表示為同一頂點(diǎn)。有人構(gòu)造了一個(gè)特例，當(dāng)出現(xiàn)退化時(shí)，進(jìn)行多次迭代，而基從B1,B2，…又返回到B1，即出現(xiàn)計(jì)算過(guò)程的循環(huán)，便永遠(yuǎn)達(dá)不到最優(yōu)解。盡管實(shí)際計(jì)算過(guò)程中循環(huán)現(xiàn)象極少出現(xiàn)，但還是有可能發(fā)生的。如何解決這問(wèn)題?先后有人提出了“攝動(dòng)法”，“字典序法”。1974年由勃蘭特(Bland)提出一種簡(jiǎn)便的規(guī)則，簡(jiǎn)稱(chēng)勃蘭特規(guī)則：(1)選取cj?zj＞0中下標(biāo)最小的非基變量xk為換入變量，即k=min(j｜c(diǎn)j?zj＞0)(2)當(dāng)按θ規(guī)則計(jì)算存在兩個(gè)和兩個(gè)以上最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。按勃蘭特規(guī)則計(jì)算時(shí)，一定能避免出現(xiàn)循環(huán)。二、退化LP問(wèn)題：三、檢驗(yàn)數(shù)的幾種表現(xiàn)形式初始基：移項(xiàng)得：其中令所以檢驗(yàn)數(shù)檢驗(yàn)數(shù)的幾種表現(xiàn)形式標(biāo)準(zhǔn)型Maxz=CXMinz=CX檢驗(yàn)數(shù)AX=b,X0AX=b,X00000初始基可行解的確定，其方法如下：畫(huà)單純形表，最優(yōu)性檢驗(yàn)與解的判斷基變換迭代（旋轉(zhuǎn)運(yùn)算）(1)直接觀察(2)加松弛變量(3)加非負(fù)的人工變量(1)確定換入變量(2)確定換出變量單純形法的求解步驟單純形法總結(jié)線(xiàn)性規(guī)劃模型標(biāo)準(zhǔn)化處理變量xj

0不需要處理xj=

x’jxj=xj1

–xj2xj

0xj無(wú)約束約束條件b0不處理b<0兩端同乘–1加松弛變量xsi=加人工變量xai減去松弛變量xsi，加上人工變量xai目標(biāo)函數(shù)maxZ不需要處理minZ令Z’=Z加入變量的系數(shù)松弛變量xsi：0人工變量xai

：–M初始基可行解的確定，其方法如下：畫(huà)單純形表，最優(yōu)性檢驗(yàn)與解的判斷基變換迭代（旋轉(zhuǎn)運(yùn)算）(1)直接觀察(2)加松弛變量(3)加非負(fù)的人工變量(1)確定換入變量(2)確定換出變量單純形法的求解步驟單純形法計(jì)算表初始基可行解的確定，其方法如下：畫(huà)單純形表，最優(yōu)性檢驗(yàn)與解的判斷基變換迭代（旋轉(zhuǎn)運(yùn)算）(1)直接觀察(2)加松弛變量(3)加非負(fù)的人工變量(1)確定換入變量(2)確定換出變量單純形法的求解步驟目標(biāo)函數(shù)求Max的線(xiàn)性規(guī)劃是否否是唯一最優(yōu)解LP問(wèn)題引人松弛變量`人工變量,列出單純形表非基變量檢驗(yàn)數(shù)j≤0對(duì)任一j>0有aij≤0令k=max{j}Xk為入基變量對(duì)所有aik≥0計(jì)算min(θi)

=min(bi/aik)=θ

lXl為出基變量換基迭代1.Xk替代Xl2.對(duì)主元行3.對(duì)主元列4.對(duì)其它行列變換無(wú)最優(yōu)解無(wú)可行解基變量含有非零人工變量非基變量檢驗(yàn)數(shù)為零多重最優(yōu)解打印結(jié)果結(jié)束是是第五節(jié)線(xiàn)性規(guī)劃應(yīng)用舉例求解問(wèn)題目標(biāo)可量化，且為線(xiàn)性函數(shù)存在多種方案及相關(guān)數(shù)據(jù)目標(biāo)可在約束條件下實(shí)現(xiàn)，且約束條件可用線(xiàn)性等式或者不等式實(shí)現(xiàn)第五節(jié)線(xiàn)性規(guī)劃應(yīng)用舉例合理利用線(xiàn)材問(wèn)題：如何下料使用材最少。配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)。投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大。產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大。勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿(mǎn)足工作的需要?！纠?-11】合理利用線(xiàn)材問(wèn)題。現(xiàn)要做100套鋼架，每套需用長(zhǎng)為2.9m，2.1m和1.5m的元鋼各一根。已知原料長(zhǎng)7.4m，問(wèn)應(yīng)如何下料，使用的原材料最