運(yùn)籌學(xué)期中考試試卷

1、大連大學(xué)2010/2011 學(xué)年第一學(xué)期期中考試卷考試科 目： 運(yùn) 籌 學(xué)（考試時(shí)間90分鐘）（共4頁）題號(hào)一一總得分121234得分、用圖解法求解（10分） 給定下述線性規(guī)劃問題：max zx12x24x13x23x1x23x1,x2 0畫出其可行域并找出其最優(yōu)解。 解：可行域：適用專業(yè)工程管理適用年級(jí)08考試形式閉 卷送卷單位任課教師教研室主任最優(yōu)解為（3,0）,z 3.、模型轉(zhuǎn)換（10分）寫出下列線性規(guī)劃問題的對(duì)偶問題23min zCj %i 1 j 1教學(xué)院長(zhǎng)X1x12x13七4a1x21x22x23x24a2x11x21bix12x22b2x13x23b3“4x24b4一 gJxij

2、0解： max w a1u1 a2u2 b1V1 b2v2 b3v3 b4v4U1V1c11U1v2c12U1v3c13U1v40U2v1c21U2v2c22U2v3c23U2v40u1,u2,v1, v2,v3, v4 無符號(hào)限制三、計(jì)算題（每小題20分，共80分）1.用單純形法求解下列線性規(guī)劃問題（列出計(jì)算過程）。 min z3x1 5x2Xi8x1 x3 8解：標(biāo)準(zhǔn)化：2x2 x4 123x1 4x2 x5為“2,乂3,人？5變量變量，第二步標(biāo)準(zhǔn)化2x2 12 3x1 4x2 36 x1,x2 0 MaxW3x1 5x2 0% 0x4 0x5（標(biāo)準(zhǔn)化可分兩段，第一步把決策 36 0）列單

3、純形表計(jì)算：基Cb-3-5000bXXX3X41頭Xa0-101008X400-201012X0-3-4P 001136cjzj-3-5000最優(yōu)解 X= (3, 5, 0, 0,0) T,最優(yōu)值 W=34，故 Z=-342 .用單純形法中兩階段法求解下述線性規(guī)劃問題（列出計(jì)算過程）。（注意步驟,區(qū)分人工變量與松馳變量）min z 4x1 x23xi X234x1 3x2 X36x1 2x2 x44x 0,i 1,2,3,4解：1）標(biāo)準(zhǔn)化； max z4x1 x23x1 x2 3（1）4x1 3x2 x3 6（2）x1 2x2 m 4x 0,i 1,2,3,42）在上約束方程組（1）、（2）中

4、加入人工變量，列出第一階段線性規(guī)劃問題 將正文中的問題化成標(biāo)準(zhǔn)型：min w x5 x63x1 x2 4 34K 3x2 & 凡 6x1 2x2 刈4x 0,i 1,2,3,4,5,6max z3）列出上述線性規(guī)劃問題的初始單純形表，并求解基CB0000-1-1bXX?X3X4X5X6X-13100103X6-143-10016X401P 201004cjzj74-1000X1011/3001/301&-105/3-10-4/312X4005/301-1/303cjzj0r 5/310-7/30X10101/503/5-1/53/5X2001-3/50-4/53/56/5X40

5、0r 0111-11cjzj0000-1-14）因?yàn)榈谝浑A段目標(biāo)函數(shù)值為0,做去掉人工變量，寫出第二階段目標(biāo)函數(shù)為4x1 x2 0x3 0x4,繼續(xù)用單純形法求解基CB-4-100bXX>X3X X1-4101/503/5 1X2-101-3/506/5X400r 01 11 1 1cjzj001/510X1-4100-1/52/5X2-10r 10 3/59/5：X3000111 1cjzj000-1/52 917故有唯一最優(yōu)解 X (-,-,1,0,0,0), Z 5 553 .用對(duì)偶單純形法求解下述線性規(guī)劃問題（列出計(jì)算過程）。（此問題不是加人工 變量，而是根據(jù)對(duì)偶理論，在保持對(duì)偶

6、問題為可行解的基礎(chǔ)上，通過迭代，使原 問題也達(dá)到可行解，即得到了目標(biāo)函數(shù)的最優(yōu)解。）min z 4x1 12x2 18x3x1 3x32x2 2x3Xi,X-,X3解：先將問題改寫為:max w 4x1 12x218x3 0x4 0x5X 3x3 x4 32x2 2x3 x5 5x 0,i 1,2,3,4,5約束條件兩端乘“ -1 ”得:max w4x1 12x218x3 0x4 0x53x3 x4cj-4-12-1800CB基bx1x-X3x4x50x4-3-10-3102x22x3x5xi0,i 1,2,3,4,50X5-50-2-201Cj Zj-4-12-18000X4-3-10-31

7、0-12X25/20110-1/2cj zj-40-60-6-18X311/301-1/30-12X23/2-1/3101/3-1/2cj zj-200-2-6X=(0 3/2 1 0 0), minz=364 .已知某運(yùn)輸問題的產(chǎn)銷數(shù)量表與單位運(yùn)價(jià)表如表4-1 ,用表上作業(yè)法求最優(yōu)解（列出計(jì)算過程）。表4-1、銷地AiA2A 3A4入戶 J里B291079B213425B384257銷量3846解：1.|最小元素法的初始方案肖地AiA 2A3A4入戶 J里B549B2325B3347銷量3846位勢(shì)法檢驗(yàn):B1B2B3B4A1(-4)9375A21(-1)(2)20A342(3)01422（注：括弧中的數(shù)位檢驗(yàn)數(shù)，下同）閉回路法調(diào)整（調(diào)整結(jié)果與Vogel法的初始方案一致）產(chǎn)地.一一_銷地B1B2B3B4）里A13519A255A3347銷量38462. Vogel法的初始方案:產(chǎn)地一一站地B1B2B3B4）里A13519A255A3347銷量3846位勢(shì)法檢驗(yàn):地 銷地B1B2B3B4A129(0)71A2(4)(-1)(2)2-4A3(11)42(3)-41866閉回路法調(diào)整:產(chǎn)地- 一'期地.一B1B2B3B4）里A1369A2505A3347銷量3846位勢(shì)法檢驗(yàn):地 銷地B1B2B3B4A12(1)(4)71A2(4)3(3)2-4A3(10)42(2)-31