《運(yùn)籌學(xué)學(xué)》課程考試試題及答案一、選擇題（每題3分，共30分）1.線性規(guī)劃模型中，決策變量（）A.只能取整數(shù)B.只能取非負(fù)實(shí)數(shù)C.可以取任意實(shí)數(shù)D.只能取大于零的實(shí)數(shù)答案：B。在線性規(guī)劃模型中，決策變量通常代表實(shí)際問題中的資源分配、生產(chǎn)數(shù)量等，一般要求非負(fù)，以符合實(shí)際意義。2.若線性規(guī)劃問題的可行域是無界的，則該問題（）A.一定有最優(yōu)解B.一定無最優(yōu)解C.可能有最優(yōu)解，也可能無最優(yōu)解D.有唯一最優(yōu)解答案：C?？尚杏驘o界時(shí)，目標(biāo)函數(shù)可能有最優(yōu)解（如目標(biāo)函數(shù)在無界可行域上有最值），也可能無最優(yōu)解（如目標(biāo)函數(shù)在無界可行域上可以無限增大或減?。?.對(duì)偶問題的對(duì)偶是（）A.原問題B.松弛問題C.無可行解問題D.不確定答案：A。根據(jù)對(duì)偶理論，對(duì)偶問題的對(duì)偶就是原問題。4.運(yùn)輸問題中，產(chǎn)地個(gè)數(shù)為m，銷地個(gè)數(shù)為n，則基變量的個(gè)數(shù)為（）A.m+nB.m+n1C.mnD.m×n答案：B。在運(yùn)輸問題中，基變量的個(gè)數(shù)等于產(chǎn)地個(gè)數(shù)與銷地個(gè)數(shù)之和減1。5.動(dòng)態(tài)規(guī)劃的基本方程是由（）導(dǎo)出的。A.貪心算法B.最優(yōu)性原理C.分治法D.搜索算法答案：B。動(dòng)態(tài)規(guī)劃的基本方程是基于最優(yōu)性原理推導(dǎo)出來的，最優(yōu)性原理指出一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。6.對(duì)于一個(gè)排隊(duì)系統(tǒng)，顧客到達(dá)率為λ，服務(wù)率為μ，當(dāng)（）時(shí)，系統(tǒng)可以達(dá)到穩(wěn)定狀態(tài)。A.λ>μB.λ<μC.λ=μD.與λ和μ無關(guān)答案：B。當(dāng)顧客到達(dá)率λ小于服務(wù)率μ時(shí)，系統(tǒng)中不會(huì)出現(xiàn)顧客無限堆積的情況，系統(tǒng)可以達(dá)到穩(wěn)定狀態(tài)。7.整數(shù)規(guī)劃問題中，若所有決策變量都要求取整數(shù)，則稱為（）A.純整數(shù)規(guī)劃B.混合整數(shù)規(guī)劃C.01整數(shù)規(guī)劃D.線性整數(shù)規(guī)劃答案：A。純整數(shù)規(guī)劃是指所有決策變量都要求取整數(shù)的整數(shù)規(guī)劃問題。8.圖論中，若一個(gè)圖中任意兩個(gè)頂點(diǎn)之間都有邊相連，則該圖稱為（）A.連通圖B.完全圖C.樹D.有向圖答案：B。完全圖是指圖中任意兩個(gè)頂點(diǎn)之間都有邊相連的圖。9.目標(biāo)規(guī)劃中，若要求恰好達(dá)到目標(biāo)值，則應(yīng)引入（）A.正偏差變量B.負(fù)偏差變量C.正、負(fù)偏差變量D.無偏差變量答案：C。在目標(biāo)規(guī)劃中，若要求恰好達(dá)到目標(biāo)值，需要同時(shí)考慮正偏差變量（超過目標(biāo)值的部分）和負(fù)偏差變量（未達(dá)到目標(biāo)值的部分）。10.線性規(guī)劃問題的標(biāo)準(zhǔn)型中，約束條件必須是（）A.等式B.不等式C.大于等于不等式D.小于等于不等式答案：A。線性規(guī)劃問題的標(biāo)準(zhǔn)型中，約束條件必須是等式，且決策變量非負(fù)，目標(biāo)函數(shù)求最大化。二、判斷題（每題2分，共20分）1.線性規(guī)劃問題的可行解一定是基本可行解。（）答案：錯(cuò)誤。可行解不一定是基本可行解，基本可行解是可行域的頂點(diǎn)，是滿足一定條件的可行解。2.對(duì)偶問題的最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值與原問題的最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值相等。（）答案：正確。根據(jù)對(duì)偶理論，在滿足一定條件下，對(duì)偶問題的最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值與原問題的最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值相等。3.運(yùn)輸問題一定有最優(yōu)解。（）答案：正確。運(yùn)輸問題是一類特殊的線性規(guī)劃問題，由于其可行域非空且有界，所以一定有最優(yōu)解。4.動(dòng)態(tài)規(guī)劃的求解過程是從初始狀態(tài)開始，逐步向后遞推。（）答案：錯(cuò)誤。動(dòng)態(tài)規(guī)劃的求解過程可以是從初始狀態(tài)開始向后遞推（順推法），也可以是從終止?fàn)顟B(tài)開始向前遞推（逆推法）。5.排隊(duì)系統(tǒng)中，顧客的平均等待時(shí)間和平均逗留時(shí)間相等。（）答案：錯(cuò)誤。顧客的平均逗留時(shí)間等于平均等待時(shí)間加上平均服務(wù)時(shí)間，二者一般不相等。6.整數(shù)規(guī)劃問題的最優(yōu)解一定是其對(duì)應(yīng)的線性規(guī)劃問題的最優(yōu)解。（）答案：錯(cuò)誤。整數(shù)規(guī)劃問題的可行域是其對(duì)應(yīng)的線性規(guī)劃問題可行域的子集，整數(shù)規(guī)劃的最優(yōu)解不一定是線性規(guī)劃的最優(yōu)解。7.圖論中，樹是一種無回路的連通圖。（）答案：正確。樹的定義就是無回路的連通圖。8.目標(biāo)規(guī)劃中，優(yōu)先級(jí)高的目標(biāo)總是優(yōu)先考慮。（）答案：正確。目標(biāo)規(guī)劃中，按照優(yōu)先級(jí)的高低依次考慮各個(gè)目標(biāo)，優(yōu)先級(jí)高的目標(biāo)優(yōu)先滿足。9.線性規(guī)劃問題的最優(yōu)解一定在可行域的頂點(diǎn)上。（）答案：正確。對(duì)于線性規(guī)劃問題，若存在最優(yōu)解，則最優(yōu)解一定在可行域的頂點(diǎn)上。10.若一個(gè)線性規(guī)劃問題有可行解，則一定有最優(yōu)解。（）答案：錯(cuò)誤。線性規(guī)劃問題有可行解時(shí)，可能無最優(yōu)解，如可行域無界且目標(biāo)函數(shù)無最值的情況。三、計(jì)算題（每題15分，共30分）1.求解線性規(guī)劃問題：\(\maxz=3x_1+2x_2\)\(\begin{cases}x_1+x_2\leq6\\x_1+2x_2\leq8\\x_1,x_2\geq0\end{cases}\)解：首先，將不等式約束化為等式約束，引入松弛變量\(x_3\)和\(x_4\)，得到標(biāo)準(zhǔn)型：\(\maxz=3x_1+2x_2+0x_3+0x_4\)\(\begin{cases}x_1+x_2+x_3=6\\x_1+2x_2+x_4=8\\x_1,x_2,x_3,x_4\geq0\end{cases}\)列出初始單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|1|1|0|6||1|2|0|1|8||3|2|0|0|0|選擇\(x_1\)作為進(jìn)基變量，計(jì)算\(\theta\)值：\(\theta_1=\frac{6}{1}=6\)，\(\theta_2=\frac{8}{1}=8\)，\(\theta=\min\{6,8\}=6\)，所以\(x_3\)為出基變量。進(jìn)行初等行變換，得到新的單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|1|1|0|6||0|1|1|1|2||0|1|3|0|18|選擇\(x_2\)作為進(jìn)基變量，計(jì)算\(\theta\)值：\(\theta_1=\frac{6}{1}=6\)，\(\theta_2=\frac{2}{1}=2\)，\(\theta=\min\{6,2\}=2\)，所以\(x_4\)為出基變量。進(jìn)行初等行變換，得到最終單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|0|2|1|4||0|1|1|1|2||0|0|4|1|20|此時(shí)，所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解\(x_1=4\)，\(x_2=2\)，最優(yōu)值\(z=20\)。2.某運(yùn)輸問題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表如下：|產(chǎn)地|銷地1|銷地2|銷地3|產(chǎn)量||||||||產(chǎn)地1|3|1|7|5||產(chǎn)地2|2|4|5|3||銷量|2|3|3||用最小元素法求初始調(diào)運(yùn)方案，并計(jì)算總運(yùn)費(fèi)。解：（1）用最小元素法求初始調(diào)運(yùn)方案：首先，單位運(yùn)價(jià)最小的是\(c_{12}=1\)，將產(chǎn)地1的3個(gè)單位產(chǎn)品運(yùn)往銷地2，此時(shí)銷地2需求滿足，產(chǎn)地1剩余產(chǎn)量\(53=2\)。接著，剩下的單位運(yùn)價(jià)中最小的是\(c_{21}=2\)，將產(chǎn)地2的2個(gè)單位產(chǎn)品運(yùn)往銷地1，此時(shí)銷地1需求滿足，產(chǎn)地2剩余產(chǎn)量\(32=1\)。然后，最小的單位運(yùn)價(jià)是\(c_{23}=5\)，將產(chǎn)地2的1個(gè)單位產(chǎn)品運(yùn)往銷地3，此時(shí)產(chǎn)地2產(chǎn)量用完，銷地3還需\(31=2\)。最后，將產(chǎn)地1的2個(gè)單位產(chǎn)品運(yùn)往銷地3，此時(shí)所有產(chǎn)地的產(chǎn)量和銷地的需求都得到滿足。初始調(diào)運(yùn)方案如下：|產(chǎn)地|銷地1|銷地2|銷地3|產(chǎn)量||||||||產(chǎn)地1|0|3|2|5||產(chǎn)地2|2|0|1|3||銷量|2|3|3||（2）計(jì)算總運(yùn)費(fèi)：總運(yùn)費(fèi)\(Z=3\times0+1\times3+7\times2+2\times2+4\times0+5\times1\)\(=0+3+14+4+0+5=26\)四、應(yīng)用題（20分）某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)甲產(chǎn)品每件需用A原料3千克、B原料2千克；生產(chǎn)乙產(chǎn)品每件需用A原料1千克、B原料3千克。已知A原料每天有12千克，B原料每天有15千克。甲產(chǎn)品每件利潤為5元，乙產(chǎn)品每件利潤為4元。問該工廠每天應(yīng)生產(chǎn)甲、乙產(chǎn)品各多少件，才能使利潤最大？解：設(shè)該工廠每天生產(chǎn)甲產(chǎn)品\(x_1\)件，生產(chǎn)乙產(chǎn)品\(x_2\)件。（1）建立數(shù)學(xué)模型：目標(biāo)函數(shù)：\(\maxz=5x_1+4x_2\)約束條件：\(\begin{cases}3x_1+x_2\leq12\\2x_1+3x_2\leq15\\x_1,x_2\geq0\end{cases}\)（2）將不等式約束化為等式約束，引入松弛變量\(x_3\)和\(x_4\)，得到標(biāo)準(zhǔn)型：\(\maxz=5x_1+4x_2+0x_3+0x_4\)\(\begin{cases}3x_1+x_2+x_3=12\\2x_1+3x_2+x_4=15\\x_1,x_2,x_3,x_4\geq0\end{cases}\)（3）列出初始單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||3|1|1|0|12||2|3|0|1|15||5|4|0|0|0|選擇\(x_1\)作為進(jìn)基變量，計(jì)算\(\theta\)值：\(\theta_1=\frac{12}{3}=4\)，\(\theta_2=\frac{15}{2}=7.5\)，\(\theta=\min\{4,7.5\}=4\)，所以\(x_3\)為出基變量。進(jìn)行初等行變換，得到新的單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||||||||1|\(\frac{1}{3}\)|\(\frac{1}{3}\)|0|4||0|\(\frac{7}{3}\)|\(\frac{2}{3}\)|1|7||0|\(\frac{7}{3}\)|\(\frac{5}{3}\)|0|20|選擇\(x_2\)作為進(jìn)基變量，計(jì)算\(\theta\)值：\(\theta_1=\frac{4}{\frac{1}{3}}=12\)，\(\theta_2=\frac{7}{\frac{7}{3}}=3\)，\(\theta=\min\{12,3\}=3\)，所以\(x_4\)為出基變量。進(jìn)行初等行變換，得到最終單純形表：|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)|||