天津大學(xué)2011運(yùn)籌學(xué)試題及答案

1、天津大學(xué)招收dftWWBWIWfiw及參考答案考試科小運(yùn)籌學(xué)基礎(chǔ)考試科目編號(hào):832一、填空題：（每空格2分，共16分）1、 線性規(guī)劃的解有唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解 和無(wú)可行解四種。2、 在求運(yùn)費(fèi)最少的調(diào)度運(yùn)輸問(wèn)題中，如果某一非基變量的檢驗(yàn)數(shù)為4,則說(shuō)明如果在該空格中增 TOC o 1-5 h z 加一個(gè)運(yùn)量運(yùn)費(fèi)將增加4。3、 “如果線性規(guī)劃的原問(wèn)題存在可行解，則其對(duì)偶問(wèn)題一定存在可行解”，這句話對(duì)還是錯(cuò)？錯(cuò)4、如果某一整數(shù)規(guī)劃：MaxZ=X +X 12Xi+9/14X251/14-2Xi+X21/3%,%0且均為整數(shù)所對(duì)應(yīng)的線性規(guī)劃（松弛問(wèn)題）的最優(yōu)解為Xj3/2, %=10/3,

2、MaxZ=6/29，我們現(xiàn)在要對(duì)進(jìn)行分枝， 應(yīng)該分為 X11和 X1N2。5、 在用逆向解法求動(dòng)態(tài)規(guī)劃時(shí)，fk（sk）的含義是：從第k個(gè)階段到第n個(gè)階段的最優(yōu)解。6、假設(shè)某線性規(guī)劃的可行解的集合為D，而其所對(duì)應(yīng)的整數(shù)規(guī)劃的可行解集合為B，那么D和B的關(guān) 系為 D包含B7、已知下表是制訂生產(chǎn)計(jì)劃問(wèn)題的一張LP最優(yōu)單純形表（極大化問(wèn)題，約束條件均為“忍”型不等 式）其中X3,X4,X5為松馳變量。XbXXXXXX30203-213X4/310-1/302/3XQ10100-1C-Z.00-50-23(-213 :問(wèn)：（1）寫(xiě)出B-1=-1/3 .0 2/3、00 -1 ?（2）對(duì)偶問(wèn)題的最優(yōu)解：Y

3、=（5,0，23，0，0) t_線性規(guī)劃問(wèn)題如果有無(wú)窮多最優(yōu)解，則單純形計(jì)算表的終表中必然有 某一個(gè)非基變量的檢驗(yàn)數(shù) 為0;極大化的線性規(guī)劃問(wèn)題為無(wú)界解時(shí)，則對(duì)偶問(wèn)題 無(wú)解；若整數(shù)規(guī)劃的松馳問(wèn)題的最優(yōu)解不符合整數(shù)要求，假設(shè)X=b不符合整數(shù)要求，INT （b ）是不超過(guò)b的最大整數(shù)，則構(gòu)造兩個(gè)約束條件：XiNINT （b ） +1 和 XiINT （b ） ，分別 將其并入上述松馳問(wèn)題中，形成兩個(gè)分支，即兩個(gè)后繼問(wèn)題。i知下表是制訂生產(chǎn)計(jì)劃問(wèn)題的一張lp最優(yōu)單純形表（極大化問(wèn)題，約束條件均為 y 型不等式） 其中X4,X5,X6為松馳變量。X 2bX X X 2X dX X G02;問(wèn)：（/）對(duì)

4、偶問(wèn)題的最優(yōu)解：Y=（4,0,9,0,0,0）t2/31-9（2）寫(xiě)出 B-i二二、計(jì)算題（60分）1、已知線性規(guī)劃（20分）MaxZ=3X +4X 12代+X產(chǎn)52Xi+4X2123Xi+2X28lX,X N0 其最優(yōu)解為:基變量XX 2X 3X 4X 5X 33/2001-1/8-1/4X5/20103/8-1/42X1100-1/41/2a j000-3/4-1/21）寫(xiě)出該線性規(guī)劃的對(duì)偶問(wèn)題。天津大學(xué)招收2011年碩士學(xué)位研究生入學(xué)考試試題及參考答案由于基變量的值仍然都是大于0的，所以最優(yōu)解的基變量不會(huì)發(fā)生變化。4）如果增加一種新的產(chǎn)品，則P? =（11/8,7/8,-1/4） tc6

5、=3/80所以對(duì)最優(yōu)解有影響，該種產(chǎn)品應(yīng)該生產(chǎn)2、已知運(yùn)輸問(wèn)題的調(diào)運(yùn)和運(yùn)價(jià)表如下，求最優(yōu)調(diào)運(yùn)方案和最小總費(fèi)用。（共15分）。肖地 產(chǎn)地_B1B2B3產(chǎn)量A59215A317112A 362820銷量181216解：初始解為B1B2B3產(chǎn)量/tA 11515A 21111A 3181120銷量/t181216計(jì)算檢驗(yàn)數(shù)B1B2B3產(chǎn)量/tA 1513015A 2-20011A 300020銷量/t181216由于存在非基變量的檢驗(yàn)數(shù)小于0,所以不是最優(yōu)解，需調(diào)整 調(diào)整為：VB1B2B3產(chǎn)量/tA 11515A 21111A 3712120銷量/t181216重新計(jì)算檢驗(yàn)數(shù)B1B2B3產(chǎn)量/tA

6、1513015A 202211A000203銷量/t181216所有的檢驗(yàn)數(shù)都大于等于0,所以得到最優(yōu)解3、某公司要把4個(gè)有關(guān)能源工程項(xiàng)目承包給4個(gè)互不相關(guān)的外商投標(biāo)者，規(guī)定每個(gè)承包商只能且必須 承包一個(gè)項(xiàng)目，試在總費(fèi)用最小的條件下確定各個(gè)項(xiàng)目的承包者，總費(fèi)用為多少？各承包商對(duì)工程的 報(bào)價(jià)如表2所示：（15 分）f 項(xiàng)目 投標(biāo)者ABCD甲15182124乙19232218丙26171619丁19212317答最優(yōu)解為：X=仲 1 0 01 0 0 00 0 1 0偵 0 0 1總費(fèi)用為504.考慮如下線性規(guī)劃問(wèn)題（24分）Max z=-5x +5x +13xs.t. -x +x +3x 20.

7、12x +4x +10 x 90 x , x, x N0回答以下問(wèn)題:3 X、/X1）求最優(yōu)解2）求對(duì)偶問(wèn)題的最優(yōu)解3）當(dāng)b1由20變?yōu)?5,最優(yōu)解是否發(fā)生變化。4）求新解增加一個(gè)變量x , c=10, a =3, a =5,對(duì)最優(yōu)解是否有影響6, 一 616265）c有5變?yōu)?,是否影響最優(yōu)解。答：最優(yōu)解為1）-551300eC BX BbX 1X 2X 3X 4X 50X 420-1131020/30X9012410019C-Z-551300J J13X 320/3-1/31/311/30200X70/346/322/30-10/3170/22Cj-Zj -2/32/30-13/3013X

8、 3185/33-34/33012/11-1/225XQ35/1123/1110-5/113/22-68/3300-1/11-1/11最優(yōu)解為 X =185/33, X =35/11對(duì)偶問(wèn)題最優(yōu)解為3Y=(1/22,1/11,68/33,0,0) t3)當(dāng)b1=45時(shí)X=十 45/11 、-11/90由于的值小于0,所以最優(yōu)解將發(fā)生變化4）p=（3/11,-3/4）tO凱7/200所以對(duì)最優(yōu)解有影響。5）當(dāng) C=62o -137/33a =4/11o 5=-17/22由于。大于0所以對(duì)最優(yōu)解有影響.,f.)。（15 分）(6,0)4考慮如下線性規(guī)劃問(wèn)題（20分）6x +3x +5x 93x +

9、4x +5x 8；30Max z=3x +x +4x s.t.回答以下問(wèn)題：1）求最優(yōu)解；2）直接寫(xiě)出上述問(wèn)題的對(duì)偶問(wèn)題及其最優(yōu)解；3）若問(wèn)題中x列的系數(shù)變?yōu)椋?, 2），問(wèn)最優(yōu)解是否有變化；4）c由1變?yōu)?2,是否影響最優(yōu)解，如有影響，將新的解求出。Cj31400CPXpbX1X2X3X4X50“X49635100X5834501Cj-Zj314000X413-101-14X38/53/54/5101/5Cj-Zj3/5-11/500-4/53X11/31-1/301/3-1/34X37/5011-1/52/5Cj-Zj0-20-1/5-3/5最優(yōu)解為 X1=1/3,X3=7/5,Z=33/

10、52）對(duì)偶問(wèn)題為Minw=9y1+8y2產(chǎn) 6y1+3y2N33y1+4y2N15y1+5y2N4 y1,y2N0對(duì)偶問(wèn)題最優(yōu)解為y1=1/5,y2=3/53）若問(wèn)題中X2列的系數(shù)變?yōu)椋?, 2） t則=（1/3,1/5）ta =-4/5 0所以對(duì)最優(yōu)解沒(méi)有影響4）C2由1變?yōu)?a 2=T0所以對(duì)最優(yōu)解沒(méi)有影響求如圖所示的網(wǎng)絡(luò)的最大流和最小截集（割集），每孤旁的數(shù)字是（七，孔）。（10分）(3,2)(4,0)VsVt(5,4)(7,7)V2(5,5)V4最大流=118.某廠1、II、m三種產(chǎn)品分別經(jīng)過(guò)A、B、C三種設(shè)備加工。已知生產(chǎn)單位各種產(chǎn)品所需的設(shè) 備臺(tái)時(shí)，設(shè)備的現(xiàn)有加工能力及每件產(chǎn)品的預(yù)

11、期利潤(rùn)見(jiàn)表：IIII設(shè)備能力（臺(tái).h）A111100B1045600C226300單位產(chǎn)品利潤(rùn)（元）10641）建立線性規(guī)劃模型，求獲利最大的產(chǎn)品生產(chǎn)計(jì)劃。（15分）2）產(chǎn)品III每件的利潤(rùn)到多大時(shí)才值得安排生產(chǎn)？如產(chǎn)品III每件利潤(rùn)增加到50/6元，求最優(yōu)計(jì)劃的 變化。（4分）3）產(chǎn)品I的利潤(rùn)在多大范圍內(nèi)變化時(shí)，原最優(yōu)計(jì)劃保持不變。（2分）4）設(shè)備A的能力在什么范圍內(nèi)變化時(shí)，最優(yōu)基變量不變。（3分）5）如有一種新產(chǎn)品，加工一件需設(shè)備A、B、C的臺(tái)時(shí)各為1、4、3h,預(yù)期每件為8元，是否值得 生產(chǎn)。（3分）6）如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品I，試確定最優(yōu)計(jì)劃的變化。（3分）解：1）建立線性規(guī)

12、劃模型為：MaxZ=10 x1+6x2+4x3yx1+x2+x3 10010 x1+4x2+5x36002x1+2x2+6x3300 xj0,j=1,2,3獲利最大的產(chǎn)品生產(chǎn)計(jì)劃為：X*=（x1,x2,x3,x4,x5,x6） =（100/3,200/3,0,0,0,100） Z*=2200/32）產(chǎn)品I每件利潤(rùn)到20/3才值得生產(chǎn)。如果產(chǎn)品I每件利潤(rùn)增加到50/6元，最優(yōu)計(jì)劃的變化為：X*=（x1,x2,x3,x4,x5,x6） =（175/6,275/6,25,0,0,0） Z*=7753）產(chǎn)品I的利潤(rùn)在6,15變化時(shí)，原最優(yōu)計(jì)劃保持不變。4）設(shè)備A的能力在60,150變化時(shí)，最優(yōu)基變量不

13、變。5）新產(chǎn)品值得生產(chǎn)。6）最優(yōu)計(jì)劃的變化為：X*=（x1,x2,x3,x4,x5,x6） =（190/6,350/6,10,0,0,60 ） Z*=706.79.給出成性規(guī)劃問(wèn)題：（15分）Min z=2x1+3x2+6x3f x1+2x2+x32i -2x +x +3x _3,x 曷 2 j=1,，4要求：（1）寫(xiě)出其對(duì)偶問(wèn)題。（5分）（2）利用圖解法求解對(duì)偶問(wèn)題。（5分）利用的結(jié)果，根據(jù)對(duì)偶問(wèn)題性質(zhì)寫(xiě)出原問(wèn)題最優(yōu)解。（5分）解：1）該問(wèn)題的LD為：MaxW=2y1-3y2y1-2y222y1+y23y1+3y26y1N0,y20用圖解法求得 LD 的最優(yōu)解為：Y*=(y1,y2) =(8

14、/5,-1/5)W*=19/5由互補(bǔ)松弛定理：原問(wèn)題的最優(yōu)解為：X*=(x1,x2,x3) =(8/5,1/5,0) 28t 和 4t16t 和 4t28t 和 16t某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)（銷地）出售，各工廠的 生產(chǎn)量，各銷售點(diǎn)的銷售量（單位.t）以及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/t）示于下表中，要求研究 產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)量最小？（10分）產(chǎn)f-T銷一B 1B 2B 3B 4產(chǎn)量A41241132A 22103920A 38511644銷量162828249696解：最優(yōu)調(diào)運(yùn)方案為：A1-B3 和 B4A2-B1 和 B4A3-B2 和 B4最小總運(yùn)費(fèi)為：460元求解下列0-1規(guī)劃問(wèn)題maxz=3x +2x -5x -2x +3x TOC o 1-5 h z 123451x +x +x +2x +x 4123457x1+3x3-4x4+3x5 W 811x -6x +3x -3x N31245、x =0 或 1(j=1,，5)解：最優(yōu)解為：x1=x2=1，其他為0，最優(yōu)目標(biāo)函數(shù)值為52）若C從4變成5,最優(yōu)解是否會(huì)發(fā)生改變，為什