運(yùn)籌學(xué)練習(xí)題

一、填空題（每小題1分,共5分；許圣蘭得分:4分）1、已知線性規(guī)劃maxZ=3x1+4x2+x3,x1+2x2+x3≤10,2x1+2x2+x3≤16,x1,x2,x3≥0最優(yōu)基為約束條件系數(shù)矩陣第一、第二兩列，則最優(yōu)解(x1,x2)=

(6,2)

?！?/p>

+1分2、非基變量xj系數(shù)為cj,對(duì)應(yīng)最終表檢驗(yàn)數(shù)為-2,則最優(yōu)解不變時(shí),cj允許增量應(yīng)滿足(用不等式表示):Δcj

<=2/cj

。×!參考答案:<=23、已知非整數(shù)最優(yōu)解中基變量x1=3.25，x1要求取整數(shù)，則添加分枝約束x1<=3和

x1>=4

?！?/p>

+1分4、一個(gè)可行流為最大流充要條件是存在一個(gè)截集使其截量

等于

網(wǎng)絡(luò)流流量?！?/p>

+1分5、每隔相同時(shí)間t0進(jìn)貨一次且每次進(jìn)貨量

都相等

存貯策略稱為t0循環(huán)策略?！?/p>

+1分-------------------------------------------------------------------------------------------------------------------------二、判斷題（每小題1分,共10分；許圣蘭得分:9分）1、當(dāng)你自己建立LP模型無最優(yōu)解時(shí)，一定是模型中存在矛盾約束條件(錯(cuò)誤)√

+1分2、設(shè)X*是minz=CX,AX≥b,X≥0最優(yōu)解，Y*是maxw=Yb,YA≤C,Y≥0最優(yōu)解，則CX*=Y*b(正確)√

+1分3、整數(shù)規(guī)劃可行解集合是離散型集合(正確)√

+1分4、若運(yùn)輸問題中產(chǎn)量和銷量為整數(shù)則其最優(yōu)解也一定為整數(shù)。(錯(cuò)誤)√

+1分5、μ是一條增廣鏈，則后向弧上滿足流量f≥0。(錯(cuò)誤)√

+1分6、指派問題一定有最優(yōu)解(正確)√

+1分7、(s,S)策略是連續(xù)盤存，當(dāng)存放量降到s時(shí)立刻提出訂貨，訂貨量等于S(錯(cuò)誤)√

+1分8、LP問題基本可行解對(duì)應(yīng)可行域頂點(diǎn)。(錯(cuò)誤)×9、若某種資源影子價(jià)格為零，則該資源一定有剩下。(錯(cuò)誤)√

+1分10、在同一存貯模型中，可能既發(fā)生存貯費(fèi)用，又發(fā)生短缺費(fèi)用(正確)√

+1分-------------------------------------------------------------------------------------------------------------------------三、單項(xiàng)選擇題（每小題1分,共10分；許圣蘭得分:7分）1、線性規(guī)劃具備無界解是指

1)、可行解集合無界

選擇正確2)、存在某個(gè)檢驗(yàn)數(shù)＞0,且此檢驗(yàn)數(shù)所在列上系數(shù)均不＞0

√

+1分

3)、有相同最小比值

4)、最優(yōu)表中全部非基變量檢驗(yàn)數(shù)非零

2、假如決議變量數(shù)相等兩個(gè)線性規(guī)劃最優(yōu)解相同，則兩個(gè)線性規(guī)劃

1)、模型相同

2)、最優(yōu)目標(biāo)函數(shù)值相等

選擇正確3)、以上結(jié)論都不對(duì)

√

+1分

4)、約束條件相同

3、以下說法正確是

1)、用割平面法求解整數(shù)規(guī)劃問題，結(jié)構(gòu)割平面有可能切去一些不屬于最優(yōu)解整數(shù)解

2)、用分枝定界法求解一個(gè)極大化整數(shù)規(guī)劃時(shí)，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通常可任取其中一個(gè)作為下界，再進(jìn)行比較剪枝

3)、整數(shù)規(guī)劃問題最優(yōu)值優(yōu)于其對(duì)應(yīng)線性規(guī)劃問題最優(yōu)值

選擇正確4)、分枝定界法在處理整數(shù)規(guī)劃問題時(shí)，借用線性規(guī)劃單純形法基本思想，在求對(duì)應(yīng)線性模型解同時(shí)，逐步加入對(duì)各變量整數(shù)要求限制，從而把原整數(shù)規(guī)劃問題經(jīng)過分枝迭代求出最優(yōu)解。

√

+1分

4、求運(yùn)輸利潤最大運(yùn)輸方案時(shí)，若某方案中空格檢驗(yàn)數(shù)滿足（），該方案是最優(yōu)方案。

1)、均大于0

2)、有一個(gè)大于0

選擇正確3)、均小于等于0

√

+1分

4)、有一個(gè)小于0

5、某有線電視臺(tái)需從現(xiàn)有道路中選擇部分道路架設(shè)電纜，使各居民小區(qū)都能收到電視信號(hào)，并使總電纜費(fèi)用最少。則該問題能夠看作一個(gè)：

選擇

×

1)、最短路問題

2)、最大流問題

正確3)、最小支撐樹問題

4)、最小費(fèi)用流問題

6、求最大流計(jì)算方法有

選擇正確1)、Ford-Fulkerson算法

√

+1分

2)、Floyd算法

3)、加邊法

4)、Dijkstra算法

7、在相同單位時(shí)間內(nèi),不允許缺貨存貯量比允許缺貨時(shí)存貯量

正確1)、多

選擇

×

2)、少

3)、一樣

4)、不確定

8、將通常線性規(guī)劃模型化為標(biāo)準(zhǔn)形時(shí)，自由變量能夠用兩個(gè)非負(fù)變量()來代換

1)、和

2)、積

選擇正確3)、差

√

+1分

4)、商

9、用動(dòng)態(tài)規(guī)劃方法求背包問題時(shí)

1)、將背包容量作為決議

2)、將裝載物品品種數(shù)作為一個(gè)階段決議

選擇正確3)、將裝載物品品種數(shù)作為階段數(shù)

√

+1分

4)、將裝載物品件數(shù)作為狀態(tài)

10、目標(biāo)函數(shù)MaxZ,xj為非基變量,若系數(shù)向量(cj,a1j,…,amj)改變后最優(yōu)解不變，則只需

正確1)、cj-CBB-1>(a1j,…,amj)'≤0

2)、B-1(a1j,…,amj)'≥0

選擇

×

3)、B-1b≥0

4)、CN-CBB-1N≥0五、應(yīng)用題(題分:10，許圣蘭得分:6)

有五項(xiàng)設(shè)計(jì)任務(wù)可供選擇。各項(xiàng)任務(wù)預(yù)期完成時(shí)間分別為3、8、5、4、10周，設(shè)計(jì)酬勞分別為7、17、11、9、21萬元。設(shè)計(jì)任務(wù)只能一項(xiàng)一項(xiàng)地進(jìn)行，總期限是20周。選擇任務(wù)時(shí)必須滿足下面條件：

（1）最少完成3項(xiàng)設(shè)計(jì)任務(wù)；

（2）若選擇任務(wù)1，必須同時(shí)選擇任務(wù)2；

（3）任務(wù)3和任務(wù)4不能同時(shí)選擇。

應(yīng)該選擇哪些設(shè)計(jì)任務(wù)，才能使總設(shè)計(jì)酬勞最大？做題統(tǒng)計(jì)：

解:設(shè)五項(xiàng)任務(wù)分x1,x2,x3,x4,x5.則

maxz=7x1+17x2+11x3+9x4+21x5

3x1+8x2+5x3+4x4+10x5<=20

x1+x2<=0

x1+x2>=2

x3+x4=1

x1+x2+x3+x4+x5>=3

xj=0或1,j=1,2,3,4,5

答案：

解：設(shè)選擇sj時(shí)，xj=1,不選擇sj時(shí)，xj=0；j=1,2…,5

由題意可得整數(shù)規(guī)劃模型以下：

maxZ=7x1+17x2+11x3+9x4+21x5

s.t.x1+x2+x3+x4+x5≥3

x1≤x2

x3+x4≤1

3x1+8x2+5x3+4x4+10x5≤20

xj=0或1(j=1,2,…5)。第二份一、填空題（每小題1分,共5分；孫運(yùn)偉得分:5分）1、若一線性規(guī)劃有多重最優(yōu)解，則其全部最優(yōu)解組成集合一定為

凸

集?！?/p>

+1分2、已知maxZ=3x1+4x2+x3,2x1+3x2+x3≤1,x1+2x2+2x3≤3,x1,x2,x3≥0最優(yōu)解為X=(1/2,0,0)'，則第二種資源影子價(jià)格為

0

?！?/p>

+1分3、用0-1變量x1、x2、x3分別表示A1、A2、A3選與不選，值為1表示選中，不然為不選，則A1，A2，A3中必須選兩個(gè)表示式為

x1+x2+x3=2

。√

+1分4、可行流中，源凈發(fā)量一定

等于

匯凈收量?！?/p>

+1分5、從發(fā)出訂貨指令到所訂貨物進(jìn)入存貯系統(tǒng)所經(jīng)歷時(shí)間稱為

訂貨提前期

。√

+1分-------------------------------------------------------------------------------------------------------------------------二、判斷題（每小題1分,共10分；孫運(yùn)偉得分:8分）1、若矩陣B為一可行基,則|B|=0。(錯(cuò)誤)√

+1分2、設(shè)X*是minz=CX,AX≥b,X≥0可行解，Y*是maxw=Yb,YA≤C,Y≥0可行解，則有CX*≤Y*b(錯(cuò)誤)√

+1分3、整數(shù)規(guī)劃最優(yōu)解是先求對(duì)應(yīng)線性規(guī)劃最優(yōu)解然后取整得到(錯(cuò)誤)√

+1分4、不平衡運(yùn)輸問題不一定有最優(yōu)解。(錯(cuò)誤)√

+1分5、割集中弧流量之和稱為割量。(錯(cuò)誤)√

+1分6、m+n－1個(gè)變量組成基變量組充要條件是它們不包含閉回路。(正確)√

+1分7、接收有折扣訂貨量總成本不一定比經(jīng)濟(jì)訂貨批量總成本少(正確)√

+1分8、線性規(guī)劃最優(yōu)解一定是基本可行解(正確)×9、過程指標(biāo)函數(shù)是階段指標(biāo)函數(shù)函數(shù)(錯(cuò)誤)×10、在同一存貯模型中，可能既發(fā)生存貯費(fèi)用，又發(fā)生短缺費(fèi)用(正確)√

+1分-------------------------------------------------------------------------------------------------------------------------三、單項(xiàng)選擇題（每小題1分,共10分；孫運(yùn)偉得分:7分）1、以下敘述正確是

1)、線性規(guī)劃問題一定有基可行解

選擇正確2)、線性規(guī)劃問題，若有最優(yōu)解，則必有一個(gè)基可行解是最優(yōu)解

√

+1分

3)、線性規(guī)劃問題最優(yōu)解只能在極點(diǎn)上達(dá)成

4)、單純形法求解線性規(guī)劃問題時(shí)每換基迭代一次必使目標(biāo)函數(shù)值下降一次

2、原問題（求最大化問題）決議變量xi≥0，則以下描述正確是

1)、對(duì)偶問題決議變量yi≤0

選擇正確2)、對(duì)偶問題第i個(gè)約束條件是“≥”

√

+1分

3)、對(duì)偶問題第i個(gè)約束條件是“≤”

4)、對(duì)偶問題決議變量yi≥0

3、對(duì)一個(gè)求目標(biāo)函數(shù)最大混合整數(shù)規(guī)劃問題，以下命題中不正確是：

選擇

×

1)、任一可行解目標(biāo)函數(shù)值不可能大于其松弛問題目標(biāo)函數(shù)最優(yōu)值

2)、該問題可行解中可能存在不取整數(shù)值變量

3)、其松弛問題最優(yōu)解可能是該整數(shù)規(guī)劃問題最優(yōu)解

正確4)、該問題可行解個(gè)數(shù)是有限

4、有5個(gè)產(chǎn)地4個(gè)銷地平衡運(yùn)輸問題

選擇正確1)、有8個(gè)基變量

√

+1分

2)、有9個(gè)基變量

3)、有20個(gè)約束

4)、有9個(gè)變量

5、從甲市到乙市之間有一公路網(wǎng)絡(luò)，為了盡快從甲市驅(qū)車趕到乙市，此問題屬于:

1)、最小生成樹問題

選擇正確2)、最短路問題

√

+1分

3)、最大流問題

4)、一筆畫問題

6、以下錯(cuò)誤結(jié)論是

1)、將指派問題效率矩陣每行分別加上一個(gè)數(shù)后最優(yōu)解不變

選擇

×

2)、將指派問題效率矩陣每個(gè)元素同時(shí)乘以一個(gè)非零數(shù)后最優(yōu)解不變

3)、指派問題數(shù)學(xué)模型是整數(shù)規(guī)劃模型

正確4)、將指派（分配）問題效率矩陣每行分別乘以一個(gè)非零數(shù)后最優(yōu)解不變

7、瞬時(shí)供貨且允許缺貨經(jīng)濟(jì)批量模型中，若訂貨費(fèi)、存放費(fèi)和缺貨費(fèi)同時(shí)增加δ倍時(shí)，經(jīng)濟(jì)訂貨批量

1)、為原來1/δ1/2倍

2)、為原來1/(2δ)1/2

選擇正確3)、不變

√

+1分

4)、為原來δ1/2倍

8、用單純形法求解線性規(guī)劃問題時(shí)引入松弛變量在目標(biāo)函數(shù)中系數(shù)為

選擇

×

1)、很大正數(shù)

正確2)、0

3)、1

4)、很大負(fù)數(shù)

9、動(dòng)態(tài)規(guī)劃逆序法中，fk(sk)表示是

選擇正確1)、從第k個(gè)階段到最終階段最優(yōu)效益值

√

+1分

2)、第k個(gè)階段最優(yōu)效益值

3)、從第1階段到第k階段最優(yōu)效益值

4)、第k個(gè)階段狀態(tài)轉(zhuǎn)移方程

10、在制品采取不允許缺貨t0循環(huán)策略時(shí)，以下哪個(gè)參數(shù)單獨(dú)改變不會(huì)使生產(chǎn)間隔期t0縮短

選擇正確1)、單位變動(dòng)成本K增加

√

+1分

2)、單位存貯費(fèi)C1增加

3)、生產(chǎn)速度P增加

4)、固定成本C3降低五、應(yīng)用題(題分:10，孫運(yùn)偉得分:10)

某航空企業(yè)希望更有效地安排售票員工作時(shí)間，以降低工資支出。每個(gè)售票員上班后將連續(xù)工作8個(gè)小時(shí)，假定天天8:00至24:00為售票工作時(shí)間。應(yīng)該怎樣計(jì)劃每個(gè)時(shí)段初上班售票員人數(shù)，建立售票員總?cè)藬?shù)最少數(shù)學(xué)模型（15分）。

數(shù)據(jù)資料以下：時(shí)段8:00~10:0010:00~12:0012:00~14:0014:00~16:0016:00~18:0018:00~20:0020:00~22:0022:00~24:00需售票員數(shù)10891113853做題統(tǒng)計(jì)：

統(tǒng)計(jì)每個(gè)階段所需人數(shù)x

minz=x1+x2+x3+x4+x5

x1>=10

x1+x2>=8

x1+x2+x3>=9

x1+x2+x3+x4>=11

x2+x3+x4+x5>=13

x3+x4+x5>=8

x4+x5>=5

x5>=3

xi>0取整

答案：

設(shè)xj為第j時(shí)段開始來上班人數(shù)(j=1,2,...,5)，(3分)

則模型以下：

minS=x1+x2+x3+x4+x5

s.t.x1≥10

x1+x2≥8

x1+x2+x3≥9

x1+x2+x3+x4≥11

x2+x3+x4+x5≥13

x3+x4+x5≥8

x4+x5≥5

x5≥3

xj≥0(j=1,2,…5),且為整數(shù)。第三份一、填空題（每小題1分,共5分；安超群得分:5分）1、線性規(guī)劃可行域?yàn)?/p>

凸

集?！?/p>

+1分2、一最大化目標(biāo)線性規(guī)劃第i個(gè)約束條件為≥型不等式，則對(duì)應(yīng)第i個(gè)對(duì)偶變量yi

<=

0?！?/p>

+1分3、用0-1變量x1、x2、x3分別表示A1、A2、A3選與不選，值為1表示選中，不然為不選，則A1，A2，A3中必須選兩個(gè)表示式為

x1+x2+x3=2

?！?/p>

+1分4、樹是無圈圖中邊數(shù)

最多

圖?！?/p>

+1分5、采取允許缺貨t0循環(huán)策略時(shí)，訂購費(fèi)、單位存貯費(fèi)和單位缺貨費(fèi)均增加20%，而需求速度降低20%，則最好進(jìn)貨間隔期t0將會(huì)變?yōu)樵瓉?/p>

1.12

倍(保留小數(shù)點(diǎn)后兩位)?！?/p>

+1分-------------------------------------------------------------------------------------------------------------------------二、判斷題（每小題1分,共10分；安超群得分:6分）1、當(dāng)最優(yōu)解中存在為零基變量時(shí),則線性規(guī)劃具備多重最優(yōu)解。(正確)×2、已知maxw=Yb,YA≤C,Y≥0松弛向量Ys檢驗(yàn)數(shù)向量是λs，則X=－λs是其對(duì)偶問題基本解，若Ys是最優(yōu)解，則X=－λs是對(duì)偶最優(yōu)解(正確)√

+1分3、整數(shù)規(guī)劃最優(yōu)解是先求對(duì)應(yīng)線性規(guī)劃最優(yōu)解然后取整得到(錯(cuò)誤)√

+1分4、產(chǎn)地個(gè)數(shù)為m銷地個(gè)數(shù)為n平衡運(yùn)輸問題系數(shù)矩陣為A，則有r(A)≤m+n－1。(正確)×5、最大流問題是找一條從發(fā)點(diǎn)到收點(diǎn)路，使得經(jīng)過這條路流量最大。(錯(cuò)誤)√

+1分6、指派問題求最大值時(shí)，是將目標(biāo)函數(shù)乘以“－1”化為求最小值，再用匈牙利法求解。(錯(cuò)誤)√

+1分7、單位存放費(fèi)和訂購費(fèi)同時(shí)增加i%，則總成本也增加i%(正確)×8、LP問題基本可行解對(duì)應(yīng)可行域頂點(diǎn)。(正確)√

+1分9、用動(dòng)態(tài)規(guī)劃求解通常線性規(guī)劃問題,是將約束條件數(shù)作為階段數(shù)，變量作為狀態(tài)(正確)×10、在允許發(fā)生短缺存貯模型中，訂貨批量確實(shí)定應(yīng)使因?yàn)榇尜A量降低帶來節(jié)約能抵消缺貨時(shí)造成損失(正確)√

+1分-------------------------------------------------------------------------------------------------------------------------三、單項(xiàng)選擇題（每小題1分,共10分；安超群得分:7分）1、線性規(guī)劃具備多重最優(yōu)解是指

選擇

×

1)、目標(biāo)函數(shù)系數(shù)與某約束系數(shù)對(duì)應(yīng)成百分比

正確2)、最優(yōu)表中存在非基變量檢驗(yàn)數(shù)為零

3)、可行解集合無界

4)、基變量全部大于零

2、互為對(duì)偶兩個(gè)線性規(guī)劃問題解存在關(guān)系

1)、原問題無可行解，對(duì)偶問題也無可行解

2)、若最優(yōu)解存在，則最優(yōu)解相同

選擇正確3)、一個(gè)問題具備無界解，則另一問題無可行解

√

+1分

4)、一個(gè)問題無可行解，則另一個(gè)問題具備無界解

3、maxz=3x1+x2,4x1+3x2≤7,x1+2x2≤5,x1,x2=0或1，最優(yōu)解是

1)、（0，1）

2)、（1，0）

選擇正確3)、（1，1）

√

+1分

4)、（0,0）

4、求總銷量小于總產(chǎn)量運(yùn)輸問題不需要做是

1)、虛設(shè)一個(gè)銷地

2)、令產(chǎn)地到虛設(shè)銷地單位運(yùn)費(fèi)為0

選擇正確3)、刪去一個(gè)產(chǎn)地

√

+1分

4)、取虛設(shè)銷地需求量為恰當(dāng)值

5、μ是關(guān)于可行流f一條增廣鏈，則在μ上有

1)、對(duì)一切μ上前向弧(i,j)，有fij≥Cij

2)、對(duì)一切μ上后向弧(i,j)，有fij≤Cij

3)、對(duì)一切μ上前向弧(i,j)，有fij≤Cij

選擇正確4)、對(duì)一切μ上后向弧(i,j)，有fij＞0

√

+1分

6、不滿足匈牙利法條件是

1)、效率矩陣元素非負(fù)

正確2)、問題求最大值

3)、人數(shù)與工作數(shù)相等

選擇

×

4)、有一人不能做其中一項(xiàng)工作

7、在相同單位時(shí)間內(nèi),不允許缺貨存貯量比允許缺貨時(shí)存貯量

選擇

×

1)、少

2)、一樣

3)、不確定

正確4)、多

8、用單純形法求解線性規(guī)劃問題時(shí)引入松弛變量在目標(biāo)函數(shù)中系數(shù)為

1)、很大正數(shù)

2)、1

3)、很大負(fù)數(shù)

選擇正確4)、0

√

+1分

9、用動(dòng)態(tài)規(guī)