線性規(guī)劃模型

1第1節(jié)線性規(guī)劃問題與模型

一、線性規(guī)劃模型

從招聘總經(jīng)理談起

2泰山工廠生產(chǎn)狀況泰山工廠可以生產(chǎn)兩種產(chǎn)品出售，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：目前生產(chǎn)現(xiàn)狀：不生產(chǎn)產(chǎn)品A，生產(chǎn)產(chǎn)品B每天30，獲利3600產(chǎn)品A產(chǎn)品B資源限量設(shè)備勞動力原材料9434510360200300利潤元/kg701203招聘總經(jīng)理！約翰：我應(yīng)聘！

在現(xiàn)有資源狀況下，我可以使利潤達(dá)到4280！方案是：生產(chǎn)A產(chǎn)品20，生產(chǎn)B產(chǎn)品24可行性：9*20+4*24=276<3604*20+5*24=2003*20+10*24=3004怎么達(dá)到的？約翰使用了運籌學(xué)中的線性規(guī)劃模型問題：如何安排生產(chǎn)計劃，使得獲利最多？步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：設(shè)備約束9X1+4X2≤360

人力約束4X1+5X2

≤200

原材料約束3X1+10X2

≤300

非負(fù)性約束X1≥0X2≥05線性規(guī)劃圖解法由數(shù)學(xué)知識可知：y=ax+b是一條直線，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一條直線，以Z為參數(shù)的一族等值線。

9x1+4x2

≤360→x1≤360/9-4/9x2

是直線x1=360/9-4/9x2

下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。6例1圖示.9080604020020406080100x1

x29x1+4x2

≤3604x1+5x2

≤2003x1+10x2

≤300ABCDEFGHIZ=70x1+120x27最優(yōu)解：X1=20

,

x2=24對應(yīng)的生產(chǎn)方案：生產(chǎn)A產(chǎn)品20

生產(chǎn)B產(chǎn)品24獲利：70*20+120*24=42808約翰就任泰山工廠總經(jīng)理！9二、線性規(guī)劃圖解法例2.某工廠在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2

約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥010例1.目標(biāo)函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標(biāo)值z=27500圖解法

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例1詳細(xì)講解其方法：11線性規(guī)劃圖解法（續(xù)）(1)分別取決策變量X1,X2

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點的坐標(biāo)代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=012線性規(guī)劃圖解法（續(xù)）（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040013線性規(guī)劃圖解法（續(xù)）（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-114線性規(guī)劃圖解法（續(xù)）（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE15線性規(guī)劃圖解法（續(xù)）重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x2≥1200，則可行域為空域，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。16線性規(guī)劃圖解法（續(xù)）

例2

某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩種原料，使得購進(jìn)成本最低？17線性規(guī)劃圖解法（續(xù)）解：目標(biāo)函數(shù)：Minf=2x1+3x2

約束條件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用圖解法。如下圖：得Q點坐標(biāo)（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q18三、線性規(guī)劃一般形式企業(yè)管理的重點內(nèi)容之一就是在各種生產(chǎn)因素和產(chǎn)品的調(diào)配問題上。一方面，在一固定階段，企業(yè)管理者所能“投入”的生產(chǎn)因素：原料、人力、設(shè)備時間是由一定限量的。在一固定期間，任何一工廠的廠房、工場、機器、一切固定資本是不會變動的，再雄厚的資本，也還是有它的限度。再從流動資本來看，原料的來源和存量，各種技工的人數(shù)和時間，在一相當(dāng)?shù)亩唐谥幸彩怯幸欢ǖ南薅取?9線性規(guī)劃一般形式另一方面，企業(yè)管理者“投入”生產(chǎn)因素時，一定有一完整的目標(biāo)。在商言商，企業(yè)管理者的目標(biāo)當(dāng)然是求最高的利潤和最低的成本。如何將受時間、空間、數(shù)量限制的“投入”生產(chǎn)因素調(diào)配“得當(dāng)”，達(dá)到最佳的境界而獲得最佳的“產(chǎn)出”量，因而獲得最大的收益。以上就是企業(yè)管理者須面對的一個問題的兩個方面。企業(yè)管理者不僅要知道如何調(diào)配手頭上有限的生產(chǎn)因素，同時要從不同的調(diào)配中，找出最佳的調(diào)配，來達(dá)到他的企業(yè)經(jīng)營目標(biāo)——最低成本、最高利潤。20線性規(guī)劃一般形式事實上，用最低的代價去追求最高的收獲，原是一種理性的要求，因此在任何理性活動中，都有一求“最佳”問題的存在。21例題3——配方問題養(yǎng)海貍鼠飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養(yǎng)要求7003020022例題3建模設(shè)抓取飼料Ix1kg;飼料IIx2kg;飼料IIIx3kg……目標(biāo)函數(shù)：最省錢minZ=2x1+7x2+4x3+9x4+5x5約束條件：3x2+2x2+x3+6x4+18x5≥700營養(yǎng)要求：

x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非負(fù)性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥023例題4：人員安排問題醫(yī)院護(hù)士24小時值班，每次值班8小時。不同時段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計：

序號時段最少人數(shù)安排人數(shù)106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x624例題4建模目標(biāo)函數(shù)：minZ=x1+x2+x3+x4+x5+x6約束條件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非負(fù)性約束：xj

≥0,j=1,2,…625歸納：線性規(guī)劃的一般模式目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+c3x3+…+cnxn約束條件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1

a21x1+a22x2+a23x3+…+a2nxn

≤(=≥)b2

…………am1x1+am2x2+am3x3+…+amnxn

≤(=≥)bn非負(fù)性約束：x1

≥0,x2≥0,…,xn≥0

26四、線性規(guī)劃的標(biāo)準(zhǔn)型一般形式目標(biāo)函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥027線性規(guī)劃的標(biāo)準(zhǔn)型

可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項非負(fù)。對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:28線性規(guī)劃的標(biāo)準(zhǔn)型1.極小化目標(biāo)函數(shù)的問題：設(shè)目標(biāo)函數(shù)為

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即Maxz=-c1x1

-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即

Minf

＝-Maxz29線性規(guī)劃的標(biāo)準(zhǔn)型2、約束條件不是等式的問題：設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進(jìn)一個新的變量s

，使它等于約束右邊與左邊之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)顯然，s

也具有非負(fù)約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn+s=bi30線性規(guī)劃的標(biāo)準(zhǔn)型

當(dāng)約束條件為

ai1x1+ai2x2+

…

+ainxn

≥bi

時，類似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

顯然，s

也具有非負(fù)約束，即s≥0，這時新的約束條件成為

ai1x1+ai2x2+…+ainxn-s=bi31線性規(guī)劃的標(biāo)準(zhǔn)型

為了使約束由不等式成為等式而引進(jìn)的變量s,當(dāng)不等式為“小于等于”時稱為“松弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。

3.右端項有負(fù)值的問題：

在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。32線性規(guī)劃的標(biāo)準(zhǔn)型例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-2x1+3x2-4x3

其次考慮約束，有2個不等式約束，引進(jìn)松弛變量x4，x5

≥0。第三個約束條件的右端值為負(fù)，在等式兩邊同時乘-1。33線性規(guī)劃的標(biāo)準(zhǔn)型通過以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：

Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***變量無符號限制的問題***：

在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj’和xj”的大小。34五、計算機求解算法單純形算法基本思想：從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找出最優(yōu)解或判定問題無界為止。從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標(biāo)函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。35求解線型規(guī)劃的算法

單純形算法且聽下回分解3637第三章運籌學(xué)優(yōu)化模型大連海事大學(xué)劉巍38第2節(jié)線性規(guī)劃求解

單純性算法

求解線性規(guī)劃的最常用算法！

39單純形算法

基本思想：從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標(biāo)函數(shù)得到改進(jìn)，如此迭代下去，直到找出最優(yōu)解或判定問題無界為止。從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標(biāo)函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。40

單純形法

引例maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X5041解：(1)、確定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=

X2=0X(1)=(0,0,30,60,24)TZ(1)=042(2)、判定解是否最優(yōu)Z=0+40X1+50X2當(dāng)X1從0↗或X2從0↗Z從0↗∴X(1)不是最優(yōu)解43(3)、由一個基可行解→另一個基可行解?！?0>40選X2從0↗，X1=0X3=30-2X20X230/2

X4=60-2X20X260/2

X5=24-2X20X224/2

X2=min(30/2,60/2,24/2)=12X2進(jìn)基變量，

X5出基變量。44B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1

②2X2=24-X5③45③×1/2

，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=

36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=60046(2)'

判斷∵40>0∴X(2)不是。(3)'

選X1從0↗，X5=0X3=6-X10

X4=

36-3X10

X2=120

X1=min(6/1,36/3,1)=6X1進(jìn)基，

X3出基。47B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=

18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=84048(2)"∵15>0∴X(3)不是(3)"

選X5從0↗，X3=0X1=6+X50

X4=

18-2X50

X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5進(jìn)基，

X4出基。49B4=(P1P5P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=

9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975500(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)51maxZ=CX當(dāng)LP的數(shù)學(xué)模型為矩陣型AX=b時，

X0兩個重要公式：XB=B-1b-B-1NXNZ=CBB-1b+(CN-CBB-1N)XN當(dāng)XN=0時，B-1b0X=Z=CBB-1b52當(dāng)LP的數(shù)學(xué)模型為一般型時兩個重要公式形如：5310…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amn設(shè)A=B=(P1P2…Pm)=I54當(dāng)Xj=0(j=m+1,…,n)時,551.5.2

單純形法原理56此時，B=(P1P2…Pm)對應(yīng)的基本可行解為(1)(1)57定理1：對解X(1)

，若檢驗數(shù)j(j=m+1,…,n)全部

0，則X(1)為最優(yōu)解。定理2：對X(1)，若有某個非基變量Xm+k→m+k>0且相應(yīng)的Pm+k=(a1m+k,…,amm+k)T

0，則原問題無有限最優(yōu)解。58定理2證明Xi=bi-aijxjJ=m+1n令非基變量Xm+k=(﹥0)X(2)

=(b1-a1m+k,…,bm-amm+k,0,…,,…,0)TAX(2)

=bX(2)0Z=Z0+m+k

當(dāng)時

Z59例：Z=30X1+20X2-X1+3X2+X3=10-3X1+2X2+X4=15初始基B1=(P3P4)X(1)=(0,0,10,15)TZ(1)=0Z=0＋30X1+20X2X3=10-(-X1+3X2)X4=15-(-3X1+2X2)60選中X1從0↗，X2=0X3=10-(-X1)0

X4=15-(-3X1)0

求X1，X1→+,Z→+61換基迭代公式：(1)、決定換入變量：maxj=m+k，則Xm+k為換入變量j>0(2)、決定換出變量：bi-aim+kXm+k0

(i=1,2,…,m)Xm+kbiaim+k(aim+k>0)62θ=minaim+k>0=biaim+kbrarm+k則Xr為換出變量。63定理3：經(jīng)單純形法得到的X(2)

=(b1-a1m+k,…,bm-

amm+k,0,…,,…,0)T是基本可行解，且Z(2)﹥

Z(1)

64證明：設(shè)Xr=Xm,

Xm=0,Xm+k==bmAmm+k(﹥0)X(1)中P1,…

Pm線性無關(guān)，下證P1,…

Pm-1,Pm+k線性無關(guān)。若否，因為P1,…

Pm線性無關(guān)則Pm+k=a1m+kP1+…+amm+kPm①而Pm+k=l1P1+…+lm-1Pm-1②65

①-②(a1m+k-

l1)P1+…+(am-1m+k-

lm-1)Pm-1+amm+kPm=0P1,…,Pm線性相關(guān)，矛盾。X(2)是基本解，且是可行解

66單純形法基本步驟(1)、定初始基，初始基本可行解(3)、若有k>0，Pk全

0，停，沒有有限最優(yōu)解；否則轉(zhuǎn)(4)(2)、對應(yīng)于非基變量檢驗數(shù)j全

0。

若是，停，得到最優(yōu)解；若否，轉(zhuǎn)(3)。67θ=minaim+k>0=biaim+kbrarm+k定Xr為換出變量，arm+k為主元。由最小θ比值法求：maxj=m+k→Xm+k換入變量j>0(4)、68轉(zhuǎn)(2)m+k0

…………a1m+k0arm+k1amm+k0初等行變換Pm+k=…………(5)、以arm+k為中心，換基迭代69證明可用歸納法（略）X(1)X(2)X(3)X’XX在邊界上X在內(nèi)部X＝X’

+(1-)X(2)

(0

1)X’＝X(1)

+(1-)X(3)

X(1)(1-)X(2)(1-)X(3)X=++(0

1)70證明：設(shè)X(1),…,X(k)

為可行域頂點，若X*不是頂點，但

maxZ=CX*

X*=定理2：可行域有界，最優(yōu)值必可在頂點得到μ

iX(i)ki=1μ

i=1ki=10μi1CX*=μ

iC

X(i)ki=1μ

iCX(m)ki=1=CX(m)[設(shè)CX(m)＝Max(C

X(i))]1ik71Z(1)

=Cibii=1mZ(2)

=Ci(bi-aim+k)+Cm+ki=1m

=Cibi-+Cm+ki=1mCiaim+ki=1m

=Cibi+[Cm+k-Ciaim+k]i=1m

i=1mZ(2)-

Z(1)=(Cm+k-Zm+k)=

m+k﹥0

721.5.3

單純形表

C1C2…

CmCm+1…

Cm+k…CnX1X2…XmXm+1…

Xm+k…XnCBXBZ000

…0m+1…m+k…

nC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………734050000X1X2X3X4X5CBXB04050000θ0X33012100150X460

3

2010300X5240(2)00112XB60040000-250X36(1)010-160X4363001-11250X21201001/284000-4001540X161010-10X41800-31250X21201001/274XB97500-35/2-15/2040X11510-1/21/200X5900-3/21/2150X215/2013/4-1/40本問題的最優(yōu)解X=(15,15/2,0,0,9)T

Z=97575幾點說明：(1)、例maxZ=X1+2X2X1

4X2

3X1+2X2

8

X1,X20

X1+X3=

4X2+X4=

3X1+2X2+X5=

8

X1…X507612000X1X2X3X4X5CBXB0120000X34101000X430(1)0100X5812001CBXB6100-200X34101002X23010100X52

(1)00-21(接下表)7712000X1X2X3X4X5

CBXB80000-10X32001(2)-12X23010101X12100-21CBXB80000-10X41001/21-1/22X2201-1/201/21X14

1010078X(1)=(2,3)Z(1)=8X(2)=(4,2)Z(2)=8無窮多解全部解：X=α+(1-α)

(0α1)243279(2)、例：求minZ=X1-X2+X3-3X5X2+X3-X4+2X5=6X1+2X2-2X4=52X2+X4+3X5+X6=8X1…X60801-110-30X1X2X3X4X5X6CBXB110-403-501X36011-1201X15120-2000X68020131CBXB-7/30-2/3014/305/31X32/30-1/31-5/30-2/31X15120-200-3X58/3

02/301/311/3CBXB-41/300405/31X33/21/601-20-2/3-1X25/21/210-100-1X51-2/300111/381判定定理1：基本可行解X，當(dāng)全部j0時，X為最優(yōu)解。判定定理2：對可行基B，當(dāng)某k<0，且Pk=(a1k…amk)T

0，則原問題無有限最優(yōu)解。

換入變量：maxj=j

=m+k→Xm+kj<082(3)、maxZ=10X1+

12X23X1+4X264X1+X223X1+2X23X1,X20831012000X1X2X3X4X5

XB01012000θi

X363(4)1003/2

X42410102/1

X53320013/2

XB1810-300θi

X23/23/411/4002

X41/213/40-1/4102/13

X50

(3/2)0-1/2010

XB1800-8/30-2/3

X23/2011/20-1/2

X41/2005/61-13/6

X1010-1/302/384退化解X*=(0,3/2,0,1/2,0)TZmax=1885例：maxZ=-3/4X4+20X5-1/2X6+6X7

X1+1/4X4-8X5-X6+9X7=0X2+1/2X4-12X5-1/2X6+3X7=0

X3+X6=1X1…X70(P1P2P3)(P4P2P3)(P4P5P3)(P6P5P3)(P6P7P3)(P1P7P3)(P1P2P3)86(4)例：maxZ=4X1+X2-X1+X2

2X1-4X2

4X1-2X2

8X1,X2087

41000

X1X2X3X4X5CBXB

0410000

X32-111000

X44(1)-40100X581-200188160170-400X360-31104X141-40100X540(2)0-11500009/2-17/20

X312001-1/23/24

X112100-121

X22010-1/21/289本問題無界。X1X2OZ=0901.5.4初始基本可行解的求法(一)、大M法：判定無解條件：當(dāng)進(jìn)行到最優(yōu)表時，仍有人工變量在基中，且≠0，則說明原問題無可行解。91例1：maxZ=6X1+4X22X1+3X2

1004X1+2X2

120X1=14X2

22X1X2

092maxZ=6X1+4X22X1+3X2+X3=1004X1+2X2+X4=120X1=14X2-X5=

22X1…X5

093maxZ=6X1+4X2-MX6-MX72X1+3X2+X3=1004X1+2X2+X4=120X1+X6=14X2-X5+X7=

22X1…X7

09464000-M-MX1X2X3X4X5X6X7CBXB-36M

M+6M+400-M000X310023100000X4120

4

201000-MX614(1)000010-MX7220100-101CBXB84-22M0M+400-M6-M00X37203100-200X4640

2010-406X1141000010-MX7220(1)00-10195CBXB172

0

0004

6-M4-M0X360010(3)-2-30X420

0

0012-4-26X11410000104X2220100-101CBXB180

00-4/300-M-10/3-M0X52001/301-2/3-10X4160

0-2/310-8/306X11410000104X224011/300-2/3-296(二)、兩階段法：原問題maxZ=Cjxjj=1nxj0j=1naijxj=bi(i=1,2,…,m)97作輔助問題minW=yii=1mXj，yi0j=1naijxj+yi

=bi(i=1,2,…,m)解題過程：第1階段：解輔助問題當(dāng)進(jìn)行到最優(yōu)表時，①、若W=0,則得到原問題的一個基本可行解，轉(zhuǎn)入第2階段。②、若W>0,則判定原問題無可行解。98兩階段法原理：(1)、輔助問題的基本可行解X(0)

為最優(yōu)解，對應(yīng)最小值=0

則X(0)

的前n個分量是原問題的基本可行解。99

設(shè)X(0)=(X1(0)…Xn(0),

y1(0)…yn(0))T

使aijxj(0)+yi(0)≡

bi(i=1,2,…,n)nj=1∵=0,∴y1(0)=…=

yn(0)=0

aijxj(0)≡

bi(i=1,…,m)∴nj=1證明：100(2)、原問題有可行解時，輔助問題最優(yōu)值=0

。證明：若原問題有可行解X(0)=(X1(0),

…,Xn(0)