1、運(yùn)籌學(xué)復(fù)習(xí)題復(fù)習(xí)范圍：1.單純形法求解線性規(guī)劃問(wèn)題2.對(duì)偶問(wèn)題及互補(bǔ)松弛性3.表上作業(yè)法求解運(yùn)輸問(wèn)題4.建立整數(shù)規(guī)劃模型（不求解）5.匈牙利法求解指派問(wèn)題6.求網(wǎng)絡(luò)最大流專項(xiàng)練習(xí)：一、單純形法求解線性規(guī)劃問(wèn)題例、用單純形法求下列線性規(guī)劃問(wèn)題:max z二二10 x5x23x14x2豈9I5x 2x2乞8 Xi, X2 0解：化為標(biāo)準(zhǔn)型maxz二10 x5x2用單純形表進(jìn)行計(jì)算Cj10500CB基bxiX2X3X40X39341033x4x2X35x 2x2X400X482018/52.Cj-Zj105000 x321/58/014/51-3/53/210X1512/501/54Cj-Zj010

2、-25x23/2015/14-3/1410X1110-1/72/7q-Zj00-5/14-25/14所有非基變量的檢驗(yàn)數(shù)全部小于零，所以此線性規(guī)劃問(wèn)題有唯一最優(yōu)解最優(yōu)解X=（1，3/2,0, 0）;最優(yōu)值Z=35/2.解題步驟1.化為標(biāo)準(zhǔn)形2.列表求解Key:尋找主元（檢驗(yàn)數(shù)最大，檢驗(yàn)比最小） 主元變?yōu)?,其余變?yōu)?.3.結(jié)論（最優(yōu)解和最優(yōu)值） 練習(xí)題:1.maxz二2xx23x 5x 15I6x 2x2乞24j X1, X20maxz二2x5x2x42x2蘭123x2x2乞18NN x 03.maxz二2x4x25x3x 3x2x3豈62x2+ 2x3蘭43xx22x3乞7x!,x2,x 0

3、4.maxz二2x3x2x311*213347X2X333313x13x2,x30練習(xí)題答案1.最優(yōu)解X=(15/4,3/4,0,0),最優(yōu)值max z=33/42.最優(yōu)解X=(2,6,2,0,0),最優(yōu)值max z=34 3.最優(yōu)解X=(1,0,2,7,0,0),最優(yōu)值maxz=124.最優(yōu)解X=(1,2,0,0,0),最優(yōu)值max z=8注意細(xì)節(jié)1.右端項(xiàng)b用于計(jì)算檢驗(yàn)比，只有系數(shù)大于0時(shí)才計(jì)算檢驗(yàn)比；價(jià)值系數(shù)cj用于計(jì)算檢驗(yàn)數(shù)。2.注意自我檢查：基變量一定對(duì)應(yīng)到單位矩陣，其檢驗(yàn)數(shù)一定等于0;最優(yōu)表給出對(duì)偶問(wèn)題的最優(yōu)解，對(duì)應(yīng)的最優(yōu)值等于原問(wèn)題的最優(yōu)值。3.對(duì)矩陣的某行乘以一個(gè)較大的數(shù)，總能

4、做到所有檢驗(yàn)數(shù)小于0，所以不要 隨便通分，如練習(xí)4。二、對(duì)偶問(wèn)題及互補(bǔ)松弛性例、給出線性規(guī)劃問(wèn)題：maxz二2x4x2X3x4x3X2x4乞8I2Xq十x2蘭6x2x3x4乞6xX2X3蘭9Xi0（i = 1,2,3,4）要求：（1）寫(xiě)出其對(duì)偶問(wèn)題；（2）已知原問(wèn)題的最優(yōu)解為X*=（2,2,4,0），試根據(jù)對(duì)偶理論，直接求出對(duì) 偶問(wèn)題的最優(yōu)解。解：（1）對(duì)偶問(wèn)題為min二8y6y26y39y4yi2y?42I3y目目2乂乂 目目44iy3y41yiy31yi0 (i = 1,2,3,4)x3x2x4= 82Xq +x2= 6(2)將最優(yōu)解(2,2,4,0)帶入原問(wèn)題的約束條件，x2 X3 X4

5、=6Xqx2x3= 89根據(jù)互補(bǔ)松弛性，y4二0另一方面，因?yàn)閄i= 0,X2= 0, X3= 0，相應(yīng)的對(duì)偶問(wèn)題的約束條件應(yīng)取等號(hào)。所以yi2y2= 23y y2y3=4y3=1解得Iiy2二i從而，對(duì)偶問(wèn)題的最優(yōu)解為Y=(4/5, 3/5, 1, 0),最優(yōu)值為16解題步驟1.寫(xiě)出對(duì)偶問(wèn)題的步驟最大變最小；系數(shù)矩陣轉(zhuǎn)置；三變；價(jià)值系數(shù)與右端項(xiàng)互換。2.互補(bǔ)松弛性的應(yīng)用Key:約束條件對(duì)應(yīng)決策變量第一步：把最優(yōu)解帶入約束條件，約束條件取不等號(hào)，相應(yīng)的決策變量等于零;第二步：最優(yōu)解不為零，對(duì)應(yīng)的約束條件取等號(hào)；第三步：解方程 練習(xí)題：1.已知線性規(guī)劃4535maxz二3x4x?x3x2X2x3

6、乞10 2x2X2x3乞乞16kx1,X2,X3王0的最優(yōu)解是X*=(6,2,0),(1)寫(xiě)出原問(wèn)題的對(duì)偶問(wèn)題；(2)根據(jù)對(duì)偶理論直接求出對(duì)偶問(wèn)題的最優(yōu)解。2.已知線性規(guī)劃maxz二2xX25x36x42xx3x4遼82x2X2X32X412Xi,X2,X3,X4x 0其對(duì)偶問(wèn)題的最優(yōu)解為Y*=(4,1)，(1)寫(xiě)出對(duì)偶問(wèn)題；應(yīng)用對(duì)偶問(wèn)題的性質(zhì)，求原問(wèn)題的最優(yōu)解3.已知線性規(guī)劃max z 4x3x2x 2x 2IXq X272x 3x2乞53xx 3x“ X20其最優(yōu)解為X*=(4/5, 3，寫(xiě)出對(duì)偶問(wèn)題；(2)應(yīng)用對(duì)偶問(wèn)題的性質(zhì)，求對(duì)偶問(wèn)題的最優(yōu)解4.已知線性規(guī)劃maxz二x2X23x34x

7、4x2X22X33X4乞202x24 3371 0獨(dú)立0元的個(gè)數(shù)小于4，試指派不成功，調(diào)整系數(shù):重新試指派：34310 52 4 42 6 0 0獨(dú)立0元個(gè)數(shù)為4，指派成功，最優(yōu)解為01001110000100;最優(yōu)值為：2+4+1+8=150010解題步驟1.變換系數(shù)矩陣，目的：使每行每列中都出現(xiàn)零元素:原系數(shù)矩陣每行都減去該行的最小元素； 新得到的系數(shù)矩陣每列減去該列的最小元素2.試指派，目的：尋找獨(dú)立0、丿0 0 5 5 4 4 0 03 30 0 4 4 0 04 41010 6 6V - V :;-4-;-3-;0j一-4 4爐*1 1_ -選擇多的禮讓選擇少的，選擇少的優(yōu)先指派3.

8、獨(dú)立0元個(gè)數(shù)不足則變換矩陣，目的：增加新的0用最少的直線通過(guò)所有0元素（行不勾列勾）調(diào)整系數(shù)（沒(méi)有劃線的元素中的最小元素為我們的調(diào)整量，所有沒(méi)劃線 的元素減去調(diào)整量，劃一次線的元素不變，劃兩次線的元素加上調(diào)整量）4.寫(xiě)出最優(yōu)解和最優(yōu)值練習(xí)題：1.求指派問(wèn)題（min）（要求寫(xiě)出解和值）( (17979、89666 1c = 71712141211151466101 4107106求指派問(wèn)題（min）（要求寫(xiě)出解和值）：3123119、5715103c = 7325548577847493.求指派問(wèn)題（min）（要求寫(xiě)出解和值）4.求指派問(wèn)題（min）（要求寫(xiě)出解和值）10111428171110

9、1412c二15I69121411315111017練習(xí)題答案0100000010000011.最優(yōu)解為00100，最優(yōu)值為3210000丿151821241192322佃261716佃19212317C二00100、1|00001101100012.最優(yōu)解為10000|，最優(yōu)值為仃2)v2)(83)V502)2.求下3.求下圖中的網(wǎng)絡(luò)最大流4.發(fā)點(diǎn)Si,S2分別可供應(yīng)10和15個(gè)單位，收點(diǎn)Ti和T2可接收10個(gè)和25個(gè)單位，求最大流，邊上的數(shù)為Cij練習(xí)題答案SiS2TiT2V2(4,21.最大流=52.最大流=143.最大流=94.最大流=22注意細(xì)節(jié)1.尋找可增廣鏈時(shí)，不要忽略后向可減少的情況2.找到可增廣鏈后，修改網(wǎng)絡(luò)流量；再?gòu)念^尋找新的可增廣鏈，直到再