運籌學第二章線性規(guī)劃與單純形法

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

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

【例1-1】某工廠在計劃期內要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗，如表1-2所示。

資源產品ⅠⅡ

擁有量設備128臺時原材料A4016kg原材料B0412kg每生產一件產品Ⅰ可獲利2元，每生產一件產品Ⅱ可獲利3元，問應如何安排計劃使該工廠獲利最多?表1-1用數學關系式描述這個問題得到本問題的數學模型為:【例1-2】靠近某河流有兩個化工廠，流經第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。

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

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

具備以上三個特點的數學模型稱為線性規(guī)劃（LinearProgramming，簡記為LP）。

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

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

C=（c1，c2，…，cn）

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

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

A=（aij）m×n

矩陣和向量形式：二、線形規(guī)劃問題的標準形式稱為線性規(guī)劃問題的標準形式（其中常數b1，b2，…，bm≥0（若bi<0，兩邊乘-1））。

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

化為標準形式解：在三個技術約束中，分別加入松弛變量x3，x4，x5，問題化為標準形式：

化為標準形式【例1-5】把LP問題

一、圖解法（決策變量個數n=2）【例1-6】

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

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

無窮多最優(yōu)解

無界解!

當存在相互矛盾的約束條件時，線性規(guī)劃問題的可行域為空集。例如:無可行解的情形增加的約束條件可行域為空集，無可行解。圖解法得到的啟示1.求解線性規(guī)劃問題時，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解。2.若線性規(guī)劃問題的可行域存在，則可行域是一凸集。3.若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解一定在某個頂點可達到。4.解題思路是：先找出凸集的任一頂點，計算Z值，比較相鄰頂點Z值，如大，轉到相鄰頂點，一直到找出使Z值最大的頂點為止。二、線性規(guī)劃問題的解的概念1.可行解2.基3.基可行解4.可行基二、線性規(guī)劃問題的解的概念滿足約束條件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，稱為線性規(guī)劃問題的可行解其中使目標函數達最大值的可行解為最優(yōu)解。1.可行解LP問題二、線性規(guī)劃問題的解的概念2.基，基向量，基變量設系數矩陣

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

A的子矩陣（P3，P4，P5）正好是單位矩陣，這種形式的方程組稱為典式，或稱為對x3，x4，x5的解出形式。以（P3，P4，P5）為基，令非基變量x1=x2=0，則基變量正好等于右端常數值，得到基可行解X=（0，0，8，20，12）T。所有基解見表1-3序號B的選擇基解是否可行解對應頂點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基可行解至多有個

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

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

線性規(guī)劃問題的基可行解X對應于可行域D的頂點。定理3

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

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

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

直接觀察法：從系數矩陣A

中直接觀察出一個初始基（2）化標準型法

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

xi

=bi

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

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

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

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

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

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

當某些δj＞0時，xj

增加會使目標函數值增加，我們就要從中確定一個非基變量xj換到基變量中。

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

,0,…,0

)T

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

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

或根據(2.9)可如下確定換出變量：令確定xl為換出變量。因為①pj

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

線性無關；②存在基可行解。①pj

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

線性無關，它們是一組基；②存在基可行解。X(1)是一個基可行解。構造一個新基可行解??！4﹒基變換的系數矩陣法以下列形式的約束方程組進行討論。m×m單位矩陣是基，

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

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

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

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

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

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

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

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

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

i行)－(經過①變換以后的第l

行乘以aik)。變換以后系數矩陣各元素的變換關系式：顯然b’是基變量的取值，肯定非負，θ經過變換后的新增廣矩陣為：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的系數列向量構成m×m單位矩陣，它是可行基。于是得到一個基可行解X(1)：X(1)=(b1′,…,bl-1′

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

將約束方程組與目標函數組成n+1個變量，m+1個方程的方程組。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將上述方程組寫成增廣矩陣

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將上述方程組寫成增廣矩陣

將

z看作不參與基變換的基變量，它與x1，x2，…，xm的系數構成一個基。采用初等行變換將c1

c2…cm

變換為零，使其對應的系數矩陣為單位矩陣。可得：01

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

。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計算表1—1：XB列中填入基變量，這里是x1，x2，…，xm；CB列中填入基變量的價值系數，它們與基變量對應；b列中填入約束方程組右端的常數；

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

規(guī)則計算后填入；最后一行稱為檢驗數行，對應各非基變量。非基變量檢驗數δj

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

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

擁有量設備128臺時原材料A4016kg原材料B0412kg每生產一件產品Ⅰ可獲利2元，每生產一件產品Ⅱ可獲利3元，問應如何安排計劃使該工廠獲利最多?

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化標準型(1)確定初始基可行解：由標準型中的約束方程組可知變量x3，x4，x5

，所對應的系數向量構成3×3單位矩陣為一基?？傻贸跏蓟尚薪釾(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

的情況

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

【課堂練習】

【作業(yè)】

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

一、人工變量法【例1-8】求下列LP問題的最優(yōu)解1、問題引入人工變量法基本思想：加入人工變量，構造一個單位矩陣作為初始可行基，假定人工變量在目標函數中的系數為-M(M為任意大的正數)，再通過單純形迭代將它們逐個地從基變量中替換出來。若經過基的變換，基變量中不再含有非零的人工變量，這表示原問題有解。若在最終表中當所有Cj-zj≤0，而基變量中還有某個非零人工變量，這表示無可行解。分為：大M法兩階段法【例1-8】求下列LP問題的最優(yōu)解2.大M法解：標準化后可見沒有初始單位可行基，加人工變量大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[]所有的檢驗數都小于或等于零，但人工變量x5仍未從基變量中退出，這表明原問題無可行解?！?

MaxZ（X）=x1+2x2x1+x2+x3=510x1+7x2-x4=70x1，…，x4≥0+x5-Mx5，x5【例1-9】回顧1、單純形方法求解步驟2、求minz的情況有兩種處理方式：一種方式是令z1=－z，轉化為求maxz1；另一種是直接計算。最優(yōu)性檢驗條件改為：所有δj≥0；換入變量確定法則改為：如果則xk為換入變量。加人工變量時，目標函數改為+Mx。單純形法的其它要點完全無須改變?！纠?-10】用大M法求解如下線性規(guī)劃問題解：在上述問題的約束條件中加入松弛變量、剩余變量和人工變量，得到其中M是一個任意大的正數。建立單純形表：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.兩階段法用計算機求解含有人工變量的線性規(guī)劃問題時，只能用很大的數代替M，這就可能造成計算上的錯誤。引入兩階段法求解。

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

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

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

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

0不需要處理xj=

x’jxj=xj1

–xj2xj

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

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

=min(bi/aik)=θ

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