建筑鋼結(jié)構(gòu)全部圖片

復(fù)習(xí)運(yùn)籌學(xué)課件胡運(yùn)權(quán)第四版復(fù)習(xí)要點(diǎn)復(fù)習(xí)運(yùn)籌學(xué)課件胡運(yùn)權(quán)第四版復(fù)習(xí)要點(diǎn)1第一章線性規(guī)劃及單純形法如何轉(zhuǎn)化為標(biāo)準(zhǔn)形式？1、目標(biāo)函數(shù)為求極小值，即為：。因?yàn)榍髆inz等價(jià)于求max(-z)，令z’=-z，即化為：

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

３、右端項(xiàng)bi<0時(shí)，只需將等式兩端同乘（-1）則右端項(xiàng)必大于零

4、決策變量無(wú)非負(fù)約束

設(shè)xj

沒(méi)有非負(fù)約束，若xj≤0，可令xj=-xj’，則xj’≥0；

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

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化為標(biāo)準(zhǔn)形式。解：令x3=x4-x5

其中x4、x5

≥0；對(duì)第一個(gè)約束條件加上松弛變量x6；對(duì)第二個(gè)約束條件減去松弛變量x7；對(duì)第三個(gè)約束條件兩邊乘以“-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問(wèn)題4§2線性規(guī)劃問(wèn)題的圖解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

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

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

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

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

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

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

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

仍然考慮先前的例子

銷地B1B2B3B411銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513（1）先分別計(jì)算出各行各列最小費(fèi)用與次小費(fèi)用的差額，并填入該表的最右列和最下行。銷地B1B2B3B4產(chǎn)量行差額A13112（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小元素所在的格作為優(yōu)先的運(yùn)輸方案。在這里優(yōu)先選A3滿足B26個(gè)單位，B2列已滿足，劃去B2列。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A374610591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最13（3）計(jì)算剩余元素的行差額和列差額，并選出最大者，選擇它所在的行或列中的最小元素所在的格作為優(yōu)先的運(yùn)輸方案。在這里優(yōu)先選A3供應(yīng)B43個(gè)單位，A3行已滿足，劃去A3行。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A3746105392銷量3656列差額2513（3）計(jì)算剩余元素的行差額和列差額，并選出最大者，選擇它所在14（4）繼續(xù)進(jìn)行。在這里優(yōu)先選A2供應(yīng)B13個(gè)單位，B1列已滿足，劃去B1列。銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A21392841A3746105392銷量3656列差額2512（4）繼續(xù)進(jìn)行。在這里優(yōu)先選A2供應(yīng)B13個(gè)單位，B115（5）繼續(xù)進(jìn)行銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1311351077A21392846A3746105392銷量3656列差額2512（5）繼續(xù)進(jìn)行銷地B1B2B3B4產(chǎn)量行16（6）繼續(xù)進(jìn)行銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131135107A21392814A3746105392銷量3656列差額2512（6）繼續(xù)進(jìn)行銷地B1B2B3B4產(chǎn)量行17銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311351027A21392814A374610539銷量3656（7）繼續(xù)進(jìn)行得最終結(jié)果為：銷地B1B2B3B4產(chǎn)量A1311318（8）得到初始方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3總運(yùn)費(fèi)=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]計(jì)算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}計(jì)算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}計(jì)算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}計(jì)算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}計(jì)算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}計(jì)算min{2+6,6+9,6+4,3+8}=m