單純形法圖解法及原理

會(huì)計(jì)學(xué)1單純形法圖解法及原理2決策變量：Xi為第i班開(kāi)始上班的人數(shù)i=1,…,6目標(biāo)函數(shù)：MinZ=X1+X2+X3+X4+X5+X6約束條件：

X6+X1>=60X1+X2>=70X2+X3>=60X3+X4>=50X4+X5>=20X5+X6>=30Xi>=0,1=1,…,6第1頁(yè)/共35頁(yè)3線性規(guī)劃模型隱含的假設(shè)：比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比?？杉有裕好總€(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞俊＿B續(xù)性：每個(gè)決策變量取連續(xù)值。確定性：線性規(guī)劃中的參數(shù)aij,bi,ci為確定值。

第2頁(yè)/共35頁(yè)4第二節(jié)單純形法原理----圖解法圖解法：是用畫圖的方式求解線性規(guī)劃的一種方法。只能用于求解兩個(gè)變量的LP問(wèn)題第3頁(yè)/共35頁(yè)51）作出可行域2）作出一條目標(biāo)函數(shù)的等值線3）平行移動(dòng)目標(biāo)函數(shù)的等值線，求出最優(yōu)解圖解法基本步驟：第4頁(yè)/共35頁(yè)6例1.數(shù)學(xué)模型

maxZ=50x1+30x2s.t.4x1+3x21202x1+x2

50x1,x2

0第5頁(yè)/共35頁(yè)7x2504030201010203040x14x1+3x2120由4x1+3x2120x10x20圍成的區(qū)域第6頁(yè)/共35頁(yè)8x2504030201010203040x12x1+x2504x1+3x2120可行域同時(shí)滿足：4x1+3x21202x1+x2

50x10x20的區(qū)域——可行域第7頁(yè)/共35頁(yè)9x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問(wèn)題的解集合。該問(wèn)題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形第8頁(yè)/共35頁(yè)10x2504030201010203040x1可行域目標(biāo)函數(shù)是以Z作為參數(shù)的一組平行線x2=

Z/30-（5/3）x1第9頁(yè)/共35頁(yè)11x2504030201010203040x1可行域當(dāng)Z值不斷增加時(shí)，該直線x2=

Z/30-（5/3）x1沿著其法線方向向右上方移動(dòng)。第10頁(yè)/共35頁(yè)12x2504030201010203040x1可行域當(dāng)該直線移到Q2點(diǎn)時(shí)，Z（目標(biāo)函數(shù)）值達(dá)到最大：MaxZ=50*15+30*20=1350此時(shí)最優(yōu)解=（15，20）Q2（15，20）有唯一最優(yōu)解

第11頁(yè)/共35頁(yè)13例2解線性規(guī)劃有唯一最優(yōu)解

第12頁(yè)/共35頁(yè)14對(duì)于線性規(guī)劃問(wèn)題，我們定義：可行解：滿足全部約束條件的決策向量XRn。可行域：全部可行解構(gòu)成的集合。（它是n維歐氏空間Rn

中的點(diǎn)集，而且是一個(gè)“凸多面體”)最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值（最大值或最小值，并且有界）的可行解。無(wú)界解：若求極大化則目標(biāo)函數(shù)在可行域中無(wú)上界；若求極小化則目標(biāo)函數(shù)在可行域中無(wú)下界。

第13頁(yè)/共35頁(yè)15有無(wú)窮多最優(yōu)解

例3解線性規(guī)劃Z=0Z=-2第14頁(yè)/共35頁(yè)16例4解線性規(guī)劃有無(wú)界解

第15頁(yè)/共35頁(yè)17例5：MaxZ=3X1-2X2X1+X2<=12X1+2X2>=8X1,X2>=0無(wú)可行解第16頁(yè)/共35頁(yè)18結(jié)論：

1、線性規(guī)劃問(wèn)題的可行域?yàn)橥辜?/p>

2、若有最優(yōu)解一定可以在其可行域的頂點(diǎn)上得到線性規(guī)劃問(wèn)題解的幾種情況：

1、有唯一最優(yōu)解

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

3、無(wú)可行解

4、無(wú)最優(yōu)解第17頁(yè)/共35頁(yè)19第三節(jié)單純形法----原理單純形法：?jiǎn)渭冃畏ㄊ乔蠼饩€性規(guī)劃的主要算法，1947年由美國(guó)斯坦福大學(xué)教授丹捷格（G.B.Danzig）提出。盡管在其后的幾十年中，又有一些算法問(wèn)世，但單純形法以其簡(jiǎn)單實(shí)用的特色始終保持著絕對(duì)的“市場(chǎng)”占有率。第18頁(yè)/共35頁(yè)20定義1：基(基陣)——由A中一個(gè)子矩陣B是可逆矩陣，則方陣B稱為L(zhǎng)P問(wèn)題的一個(gè)基。A=(P1…

PmPm+1…

Pn)=(BN)

基向量非基向量…X=(X1…

XmXm+1…

Xn)T=(XBXN)T

基變量非基變量

XB

XN…線性規(guī)劃問(wèn)題解的概念第19頁(yè)/共35頁(yè)21例1、X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50121003201002001P1P2P3P4P5A=第20頁(yè)/共35頁(yè)22AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN第21頁(yè)/共35頁(yè)23定義2：基本解——對(duì)應(yīng)于基B，X=為AX=b的一個(gè)解。B-1b0定義3：基本可行解——基B，基本解X=若B-1b0，稱基B為可行基。最優(yōu)解、最優(yōu)基B-1b0※基本解中最多有m個(gè)非零分量?！窘獾臄?shù)目不超過(guò)Cnm=個(gè)。n!m!(n-m)!第22頁(yè)/共35頁(yè)24X1X2X3X4X5X=b=306024B=(P3P4P5)=I可逆基N=(P1P2)X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2例1：第23頁(yè)/共35頁(yè)25令X1=

X2=0,X3=30,X4=60,X5=24X===XN0XBB-1b00306024121又：Ｂ1=(P1P2P3)=320020|B1|=6≠0,B可逆第24頁(yè)/共35頁(yè)26X1=12-(1/3X4-1/3X5)X2=12-(1/2X5)X3=-6-(-1/3X4-2/3X5)令X4=X5=0X=(12,12,-6,0,0)TZ=40X1+50X2=40[12-(1/3X4-1/3X5)]+50[12-1/2X5]=1080+(-40/3X4-35/3X5)基本解，但不可行第25頁(yè)/共35頁(yè)27例2：給定約束條件

-X3+X4=0X2+X3+X4=3-X1+X2+X3+X4=2Xj0(j=1,2,3,4)求出基變量是X1,X3,X4的基本解，是不是可行解？第26頁(yè)/共35頁(yè)28

0-11解：B=(P1P3P4)=011-111

01-10B-1=-1/21/2031/21/202b=第27頁(yè)/共35頁(yè)29X1

X3=B-1b

X4

XB=

01-101

=-1/21/203=3/2

1/21/2023/2∴X=(1,0,3/2,3/2)T是第28頁(yè)/共35頁(yè)30定義1：凸集——D是n維歐氏空間的一個(gè)集合

X(1),

X(2)∈D,若任一個(gè)滿足

X=X(1)+(1-)X(2)(01)

有X∈D線性規(guī)劃問(wèn)題的幾何意義(例2)第29頁(yè)/共35頁(yè)31

X(1),X(2),…,X(k)

是n維歐氏空間中的k個(gè)點(diǎn)，若有一組數(shù)

μ1,μ2,…,μk

滿足

0μi1(i=1,…,k)定義2μ

i=1ki=1有點(diǎn)x=μ1X(1)

+…+μk