復習運籌學課件胡運權(quán)第四版復習要點復習運籌學課件胡運權(quán)第四版復習要點1第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標準形式？1、目標函數(shù)為求極小值，即為：。因為求minz等價于求max(-z)，令z’=-z，即化為：

2、約束條件為不等式，xn+1≥0松弛變量如何處理？第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標準形式？1、目標2§1線性規(guī)劃問題及其數(shù)學模型

３、右端項bi<0時，只需將等式兩端同乘（-1）則右端項必大于零

4、決策變量無非負約束

設xj

沒有非負約束，若xj≤0，可令xj=-xj’，則xj’≥0；

又若xj為自由變量，即xj可為任意實數(shù)，可令xj=xj’-xj’’，且xj’,xj’’≥0§1線性規(guī)劃問題及其數(shù)學模型３、右端項bi<0時，只3第一章線性規(guī)劃及單純形法e.g.3試將LP問題minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化為標準形式。解：令x3=x4-x5

其中x4、x5

≥0；對第一個約束條件加上松弛變量x6；對第二個約束條件減去松弛變量x7；對第三個約束條件兩邊乘以“-1”；令z’=-z把求minz改為求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

第一章線性規(guī)劃及單純形法e.g.3試將LP問題4§2線性規(guī)劃問題的圖解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目標函數(shù)變形：x2=-3/5

x1+z/25x2x1最優(yōu)解：

x1=30x2=10最優(yōu)值：zmax=700B點是使z達到最大的唯一可行點§2線性規(guī)劃問題的圖解法maxz=15x1+255第一章線性規(guī)劃及單純形法LP問題圖解法的基本步驟：1、在平面上建立直角坐標系；2、圖示約束條件，確定可行域和頂點坐標；3、圖示目標函數(shù)（等值線）和移動方向；4、尋找最優(yōu)解。第一章線性規(guī)劃及單純形法LP問題圖解法的基本步驟：16§2線性規(guī)劃問題的圖解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1

，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

綠色線段上的所有點都是最優(yōu)解,即有無窮多最優(yōu)解。Zman=34.2§2線性規(guī)劃問題的圖解法maxz=3x1+5.77第一章線性規(guī)劃及單純形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域為無界區(qū)域，目標函數(shù)值可無限增大，即解無界。稱為無最優(yōu)解?？尚杏驗闊o界區(qū)域一定無最優(yōu)解嗎？第一章線性規(guī)劃及單純形法maxz=2x18§2線性規(guī)劃問題的圖解法由以上兩例分析可得如下重要結(jié)論：1、LP問題從解的角度可分為：⑴有可行解⑵無可行解有唯一最優(yōu)解b.有無窮多最優(yōu)解C.無最優(yōu)解2、LP問題若有最優(yōu)解，必在可行域的某個頂點上取到；若有兩個頂點上同時取到，則這兩點的連線上任一點都是最優(yōu)解。§2線性規(guī)劃問題的圖解法由以上兩例分析可得如下重要結(jié)論：193：差值法（伏格爾法）

最小元素法的缺點是：為了節(jié)省一處的費用，有時造成其它處要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小費用就近供應，就考慮次小費用，這就有一個差額，差額越大，說明不按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應當采用最小調(diào)運方案?；诖耍駹柗ǖ牟襟E是：每次從當前運價表上，計算各行各列中最小費用與次小費用這兩個運價的差值，優(yōu)先取最大差值的行或列中最小的運價來確定運輸關系，直到求出初始方案。3：差值法（伏格爾法）10仍然考慮先前的例子

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656伏格爾法的步驟如下：

仍然考慮先前的例子

銷地B1B2B3B411銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513（1）先分別計算出各行各列最小費用與次小費用的差額，并填入該表的最右列和最下行。銷地B1B2B3B4產(chǎn)量行差額A13112（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小元素所在的格作為優(yōu)先的運輸方案。在這里優(yōu)先選A3滿足B26個單位，B2列已滿足，劃去B2列。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A374610591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最13（3）計算剩余元素的行差額和列差額，并選出最大者，選擇它所在的行或列中的最小元素所在的格作為優(yōu)先的運輸方案。在這里優(yōu)先選A3供應B43個單位，A3行已滿足，劃去A3行。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A3746105392銷量3656列差額2513（3）計算剩余元素的行差額和列差額，并選出最大者，選擇它所在14（4）繼續(xù)進行。在這里優(yōu)先選A2供應B13個單位，B1列已滿足，劃去B1列。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A21392841A3746105392銷量3656列差額2512（4）繼續(xù)進行。在這里優(yōu)先選A2供應B13個單位，B115（5）繼續(xù)進行銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1311351077A21392846A3746105392銷量3656列差額2512（5）繼續(xù)進行銷地B1B2B3B4產(chǎn)量行16（6）繼續(xù)進行銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131135107A21392814A3746105392銷量3656列差額2512（6）繼續(xù)進行銷地B1B2B3B4產(chǎn)量行17銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311351027A21392814A374610539銷量3656（7）繼續(xù)進行得最終結(jié)果為：銷地B1B2B3B4產(chǎn)量A1311318（8）得到初始方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3總運費=3*5+10*2+1*3+8*1+4*6+5*3=85（元）銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311351027A21392814A374610539銷量3656（8）得到初始方案：X13=5，X14=2，X21=3，X219例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682例：求v1至v8的最短路。v2v3v7v1v8v4v5v6620v2v3v7v1v8v4v5v66134105275934682(1)v1:[0,v1]計算min{0+2,0+1,0+3}=min{2,1,3}=1v4:[1.v1][1,v1][0,v1](2)A={v1}檢查邊（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934621v2v3v7v1v8v4v5v66134105275934682(3)A={v1,v4}計算min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2v2:[2,v1][0,v1][1,v1][2,v1]考慮邊（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934622v2v3v7v1v8v4v5v66134105275934682（4）A={v1,v2,v4}計算min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3v6:[3,v1][2,v1][1,v1][0,v1][3,v1]考慮邊（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934623v2v3v7v1v8v4v5v66134105275934682(5)A={V1,V2,V4,V6}計算min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3v7:[3,v4][2，V1][1，V1][0，V1][3，V1][3,v4]考慮邊(v2,v3),(v2,v5),(v4,v7),(v6,v7)v2v3v7v1v8v4v5v66134105275934624V2V3V7V1V8V4V5V66134105275934682(6)A={V1,V2,V4,V6,V7}計算min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6v5:[6,v7][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7]考慮邊(v2,v3),(v2,v5),(v7,v5),(v7,v8)V2V3V7V1V8V4V5V66134105275934625v2v3v7v1v8v4v5v66134105275934682(7)A={V1,V2,V4,V6,V7}計算min{2+6,6+9,6+4,3+8}=m