重慶大學(xué)運(yùn)籌學(xué)第3次1答案

1、作業(yè) 試卷總分:100 得分:100 一、解答題(共 (共 4 道試題,共 28 分) 1.有一輛貨車(chē)載重量為10噸 ，用來(lái)裝載貨物A、B時(shí)成本分別為5元/噸和4元/噸?，F(xiàn)在已知每噸貨物的運(yùn)價(jià)與該貨物的重量有如下線性關(guān)系： A：P 1 =15-x 1 ，B：P 2 = P 2 =18-2x 2 其中x 1 、x 2 分別為貨物A、B的重量。如果要求貨物滿載，A和B各裝載多少，才能使總利潤(rùn)最大？建立該問(wèn)題的模型并用動(dòng)態(tài)規(guī)劃方法求解。 答案:將原題改為A：P1=15-x1，B：P2=18-2x2由題意可得各種貨物利潤(rùn)函數(shù)為21111112222222()(155)10()(1824)142gxxx

2、xxgxxxxx?原問(wèn)題的數(shù)學(xué)模型歸結(jié)為max(10)(142)10,0zxxxxxxxx?最優(yōu)解：x1=6，x2=4；z482.求下列運(yùn)輸問(wèn)題的最優(yōu)解（目標(biāo)函數(shù)求最小值）： 圖 答案:3.學(xué)校舉行游泳、自行車(chē)、長(zhǎng)跑和登山四項(xiàng)接力賽，已知五名運(yùn)動(dòng)員完成各項(xiàng)目的成績(jī)（分鐘）如下表所示如何從中選拔一個(gè)接力隊(duì)，使預(yù)期的比賽成績(jī)最好 成績(jī)表(分鐘) 游泳 自行車(chē) 長(zhǎng)跑 登山 甲 20 43 33 29 乙 15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 答案: 一樓錯(cuò)在選了最慢的.二樓錯(cuò)在不懂什么叫接力.問(wèn)題在于乙和戊都是高手,但只能用一次,

3、如何取舍!于是我們對(duì)下面的矩陣建模.5 10 5 30 0 0 03 9 10 34 11 4 12 1 2 2得到的正確結(jié)果是丁來(lái)登山. 戊自行車(chē).乙來(lái)長(zhǎng)跑.丙來(lái)游泳.18+34+28+27 = 107分鐘完成比賽. 4.用逆推法求解第37題中的動(dòng)態(tài)規(guī)劃。 答案:二、填空題(共 (共 8 道試題,共 32 分) 1.一個(gè)不規(guī)范型的線性規(guī)劃其對(duì)偶規(guī)劃一定也為_(kāi)。 答案:不規(guī)范型2.線性規(guī)劃中滿足所有約束的解稱(chēng)為_(kāi)。 答案: 可行解 3.圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是_的 答案:一致4.M個(gè)頂點(diǎn)的連通圖的最小支撐樹(shù)有 條邊。 答案:M-15.動(dòng)態(tài)規(guī)劃中反映當(dāng)前階段決策

4、產(chǎn)生結(jié)果的指標(biāo)稱(chēng)為 。 答案:階段指標(biāo)6.整數(shù)規(guī)劃可能出現(xiàn)_的情況。 答案:無(wú)可行解7.運(yùn)輸問(wèn)題中按照“運(yùn)價(jià)低處有限調(diào)運(yùn)”產(chǎn)生初始調(diào)運(yùn)方案的方法是 。 答案:最小元素法8.線性規(guī)劃中的約束必須為_(kāi)等式或不等式。 答案: 線性 三、計(jì)算題(共 (共 8 道試題,共 40 分) 1.某工廠利用原材料甲、乙、丙生產(chǎn)產(chǎn)品A、B、C，具體情況如下表所示。 圖 產(chǎn)品 材料消耗 原材料 A B C 每月可供原材料（Kg） 甲 乙 丙 2 1 1 200 1 2 3 500 2 2 1 600 每件產(chǎn)品利潤(rùn) 4 1 3 問(wèn)單位產(chǎn)品利潤(rùn)分別在什么范圍內(nèi)變化時(shí)，原生產(chǎn)計(jì)劃不變？ 答案: 解：（1）生產(chǎn)了甲種產(chǎn)品x

5、噸，用去A原料3x噸生產(chǎn)了乙種產(chǎn)品y噸，用去A原料y噸生產(chǎn)了甲種產(chǎn)品x噸和乙種產(chǎn)品y噸，共用去A原料200噸，3x+y=200（2）設(shè)生產(chǎn)甲種產(chǎn)品x噸，乙種產(chǎn)品y噸，由圖象得，甲乙產(chǎn)品所獲利潤(rùn)同銷(xiāo)量的函數(shù)關(guān)系分別為m=3n m=2n，則3x+2y220又3x+y=200解得：y20設(shè)要用B原料m噸，m=3x+5y=200+4y200+80=280答：至少要用B原料280噸 2.女子體操團(tuán)體賽規(guī)定： （1）每個(gè)代表隊(duì)由5名運(yùn)動(dòng)員組成，比賽項(xiàng)目是高低杠、平衡木、鞍馬及自由體操。 （2）每個(gè)運(yùn)動(dòng)員最多只能參加3個(gè)項(xiàng)目并且每個(gè)項(xiàng)目只能參賽一次； （3）每個(gè)項(xiàng)目至少要有人參賽一次，并且總的參賽人次數(shù)等于

6、10； （4）每個(gè)項(xiàng)目采用10分制記分，將10次比賽的得分求和，按其得分高低排名，分?jǐn)?shù)越高成績(jī)?cè)胶谩?已知代表隊(duì)5名運(yùn)動(dòng)員各單項(xiàng)的預(yù)賽成績(jī)?nèi)绫?-13所示。 表3-13 圖 怎樣安排運(yùn)動(dòng)員的參賽項(xiàng)目使團(tuán)體總分最高，建立該問(wèn)題的數(shù)學(xué)模型。 答案:3.建立求下圖中v 1 到v 6 的最大流問(wèn)題的線性規(guī)劃數(shù)學(xué)模型。 圖 答案: （1）確定決策變量（2）確定目標(biāo)函數(shù)（3）確定約束條件（4）線性規(guī)劃問(wèn)題的描述 4.已知線性規(guī)劃圖的最優(yōu)單純形表如下： X B x 1 x 2 x 3 x 4 x 5 b x 3 0 0 1 -12/5 1 180 x 2 0 1 0 3/10 -1/6 15 x 1 1 0

7、 0 -1/10 1/6 75 圖 0 0 0 -2 -20/3 在不重新進(jìn)行迭代的前提下，分別解決以下兩個(gè)問(wèn)題： （1）若第一個(gè)約束中資源限量發(fā)生變化，為使原最優(yōu)基不變，變化范圍應(yīng)為多少？ （2）若決策變量x 2 的價(jià)值系數(shù)發(fā)生變化，為使原最優(yōu)基不變，變化范圍應(yīng)為多少？ 答案: 運(yùn)籌學(xué)線性規(guī)劃中的凸集和基本可行解角頂可行解初始基變量和非基變量到底是參考二維問(wèn)題的圖解法,其可行域是由幾個(gè)線條圍起來(lái)的區(qū)域,所以肯定是凸集 5.用單純形法求解 圖 答案:單純形表： C(j)6.已知線性規(guī)劃 圖 的最優(yōu)基為圖，試用矩陣公式求（1）最優(yōu)解；(2)單純形乘子；(3)圖(4)圖 答案:7.一輛貨車(chē)的有效載重量是20噸，載貨有效空間是83.52 m?，F(xiàn)有六件貨物可供選擇運(yùn)輸，每件貨物的重量、體積及收入如表1。另外，在貨物4和5中先運(yùn)貨物5，貨物1和2不能混裝，怎樣安排貨物運(yùn)輸使收入最大，建立整數(shù)規(guī)劃模型（不求解）。 表1 貨 物 號(hào) 1 2 3 4 5 6 重量（T） 6 5 3 4 7 2 體積（m 3 ） 3 7 4 5 6 2 收入（百元） 5 8 4 6 7 3 答案:設(shè)xj為裝載第j件貨物的狀態(tài)，xj=1表示裝載第j件貨物，xj=0表示不裝載第j件貨物，有?18.已知某設(shè)備可繼續(xù)使用5年，也可以在