運(yùn)籌學(xué) 試卷及答案 卷2

《運(yùn)籌學(xué)》期末考試試卷B專業(yè)班級(jí)姓名學(xué)號(hào)題號(hào)一二三四五六七八考試成績得分得分一、單選題(2分*10=20分，把答案填在序號(hào)前)（）1、對(duì)一個(gè)極大化的線性規(guī)劃問題用單純形法求解，若對(duì)所有的檢驗(yàn)數(shù)，但對(duì)某個(gè)非基變量，有，則該線性規(guī)劃問題。A．有唯一最優(yōu)解B．有無窮多最優(yōu)解C．為無界解D．無可行解（）2、關(guān)于凸集，不正確的描述是。凸集里面的任意兩個(gè)點(diǎn)的連線上的點(diǎn)仍然在該凸集內(nèi);線性規(guī)劃問題的可行域一定是一個(gè)凸集;若線性規(guī)劃問題的可行域是凸集，則該凸集上任一頂點(diǎn)都可能是最優(yōu)解;若線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定是可行域凸集上的頂點(diǎn)。（）3、在產(chǎn)銷平衡運(yùn)輸問題中，設(shè)產(chǎn)地為m個(gè)，銷地為n個(gè)，那么解中非零變量的個(gè)數(shù)。A．等于(m+n-1)；B．不能小于(m+n-1)；C．不能大于(m+n-1)；D．不確定（）4、整數(shù)規(guī)劃問題。A．可以用舍入取整法求得最優(yōu)解B．最優(yōu)目標(biāo)函數(shù)值一定優(yōu)于松弛問題最優(yōu)目標(biāo)函數(shù)值C．都可以化為0-1型整數(shù)規(guī)劃問題D．如果松弛問題的可行域是凸集，則整數(shù)規(guī)劃問題的可行解是有限的。（）5、用沃格爾法求解運(yùn)輸問題時(shí)，如果差值很大時(shí)，應(yīng)盡量優(yōu)先安排所在行或列的運(yùn)輸。A．最小單位B．最大單位C．最大差D．最小差（）6、解最大化指派問題時(shí)，先轉(zhuǎn)化為最小化指派問題，轉(zhuǎn)化的方法是。用矩陣的最大元素減去所有元素；用矩陣的最小元素減去所有元素；每行的元素減去本行最小元素，然后再對(duì)各列的元素減去本列最小元素；用每行的最大元素減去本行元素，然后再用各列的最大元素減去對(duì)本列的元素。（）7、下列描述錯(cuò)誤的是。A．對(duì)偶問題的對(duì)偶問題等同于原問題B．有些線性規(guī)劃問題通過對(duì)偶問題的求解可以簡化原問題的求解C．若原問題和對(duì)偶問題均存在最優(yōu)解時(shí)，則它們相應(yīng)的目標(biāo)函數(shù)值相等D．當(dāng)對(duì)偶問題有解時(shí)，原問題也有解（）8、線性規(guī)劃原問題第j個(gè)約束是嚴(yán)格不等式，則對(duì)偶問題中第j個(gè)變量是。A．xj≥0B．xj≤0C．xj=0D．不一定（）9、用單純形法求解LP問題時(shí)，引入的松弛變量在目標(biāo)函數(shù)中的系數(shù)為。A．0 B．很大的正數(shù)C．很大的負(fù)數(shù) D．1（）10、用單純形法求解LP問題時(shí)，應(yīng)滿足條件，問題有無窮多最優(yōu)解。對(duì)所有基變量的；對(duì)所有基變量的，但存在某個(gè)基變量的；對(duì)所有非基變量的；對(duì)所有非基變量的，但存在某個(gè)非基變量的。得分二、判斷題（2分*10=20分,填√或×填在序號(hào)前）（）1、若原問題中xj為自由變量，那么對(duì)偶問題中的第j個(gè)約束一定為等號(hào)。（）2、用閉回路法求檢驗(yàn)數(shù)時(shí)，每一個(gè)空格的閉回路是唯一確定的。（）3、整數(shù)規(guī)劃一定存在最優(yōu)解。（）4、影子價(jià)格反映的是資源對(duì)于外部市場的緊缺程度，它是機(jī)會(huì)成本。（）5、對(duì)于最小化問題，其最終表檢驗(yàn)數(shù)是對(duì)偶問題的最優(yōu)解。（）6、采用分支定界法解整數(shù)規(guī)劃問題時(shí)，如果某個(gè)問題恰好獲得整數(shù)規(guī)劃問題的一個(gè)可行解，那么可以把它作為目標(biāo)函數(shù)值的“界限”。（）7、根據(jù)互補(bǔ)松弛定理，當(dāng)時(shí)，≤0。（）8、圖解法同單純形法雖然求解形式不同，但從幾何意義是一致的。（）9、有m個(gè)產(chǎn)地，n個(gè)銷地的產(chǎn)銷平衡的運(yùn)輸問題中，用表上作業(yè)法求解得到時(shí)，表中空格數(shù)是m×n－(m＋n－1)。（）10、若某種資源的影子價(jià)格等于C，在其他條件不變的情況下，當(dāng)該種資源增加1個(gè)單位時(shí)，相應(yīng)的目標(biāo)函數(shù)值將增大1C。得分三、計(jì)算題（60分）1、寫出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對(duì)偶線性規(guī)劃。（8分）2、已知線性規(guī)劃問題用單純形法求的最終單純形表如下：3/2015/14-3/14110-1/72/700-5/14-25/14若價(jià)值系數(shù)=13，該問題的最優(yōu)解如何改變。（8分）（2）右端項(xiàng)由變?yōu)闀r(shí)，該問題的最優(yōu)解如何變化？（10分）3、求解下列運(yùn)輸問題，表格中間的數(shù)字為運(yùn)價(jià)。（12分）產(chǎn)銷B1B2B3B4產(chǎn)量A1123410A2876520A391011930銷量8221218用分枝定界法求解下面整數(shù)規(guī)劃問題（12分）。5、求出從點(diǎn)A到點(diǎn)F的最短路。（10分）66435437519125796242851544AB111B2B3C1C2C3D1D2D3E1E2F<運(yùn)籌學(xué)>課程B卷參考答案一、選擇題（每小題2分，共20分）1--5、BBCDC6--10、ADDAD判斷題（每小題1分，共10分）1--5、√√××√6--10、√×√×√三、計(jì)算題1、解：則標(biāo)準(zhǔn)形式為：設(shè)對(duì)偶變量分別為y1，y2，y3，則對(duì)偶規(guī)劃為：2、解：（1）Cj→13500θCBXBbx1x2x3x45X23/201[5/14]-3/1421/513X1110-1/72/7--δj001/14-37/14（3分）0X321/5014/51-3/513X18/512/501/5δj0-1/50-13/5（3分）此時(shí)，原問題得到最優(yōu)解為X*=(13，0，21/5，0，0)T，maxZ＝104/5（2分）（2）當(dāng)右邊向量b變?yōu)?8,9)T時(shí)，（6分）因?yàn)橛叶顺?shù)全部為正數(shù)，因此單純形表不用繼續(xù)迭代，此時(shí)保持最優(yōu)基不變，最優(yōu)解為X*=(10/7，13/14，0，0)T，maxZ＝10*10/7+5*13/14=265/14（4分）3.解：方法一：（1）用最小元素法求得初始解，并計(jì)算檢驗(yàn)數(shù)如下：B1B2B3B4產(chǎn)量uiA182（0）（2）100A2（4）（2）218203A3（0）2010（-1）308銷量8221218vj1232（初始方案2分，位勢2分，檢驗(yàn)數(shù)2分）（2）因?yàn)棣?4<0，所以此方案不是最優(yōu)方案，調(diào)整的新方案并計(jì)算新檢驗(yàn)數(shù)：B1B2B3B4產(chǎn)量uiA182（1）（3）100A2（3）（1）128204A3（0）20（1）10308銷量8221218vj1221（新方案2分，位勢1分，檢驗(yàn)數(shù)1分）因?yàn)樗笑襥j≥0，所以此解為最優(yōu)解，又因?yàn)橛蟹腔兞繖z驗(yàn)數(shù)δ31＝0，所以，該問題有多個(gè)最優(yōu)解。其中一個(gè)最優(yōu)解為：A1-B1：8，A1-B2：2，A2-B3：12，A2-B4：8，A3-B2：20，A3-B4：10；最小運(yùn)費(fèi)z=8×1+2×2+12×6+8×5+20×10+10×9＝414。（2分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評(píng)分標(biāo)準(zhǔn)：沃格爾法求得初始方案5分，檢驗(yàn)數(shù)5分，結(jié)果2分）4、(1)先求對(duì)應(yīng)的松弛問題（記為LP0）得到最優(yōu)解X＝(3.57,7.14),Z0=35.7（2分）(2):（3分）LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5(3)（2分）LP21:X=(4.33,6),Z21=35.33(4)（3分）LP212:X=(5,5),Z212=35LP211:X=(4,6),Z211=34（2分）解法二：枝的形式表現(xiàn)，如下圖。（12分）5解（10分）：分54個(gè)階段，k=1,2,3,4,5K=5時(shí)，