（精選）運(yùn)籌學(xué)習(xí)題Word版

1、P1 11. 判斷下列說法是否正確：（a）圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的；（b）線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴(kuò)大；（c）線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點(diǎn)；（d）如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對應(yīng)可行域邊界上的一個點(diǎn)；（e）對取值無約束的變量 ，通常令 xj=xj-xj，其中 xj0 , xj0 ,在用單純形法求得的最優(yōu)解中有可能同時出現(xiàn)xj>0, xj>0 ；（f）用單純形法求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題時，與 j >0對應(yīng)的變量都可以被選作換入變量；（g）單純形

2、法計算中，如不按最小比值原則選取換出變量，則在下一個解中至少有一個基變量的值為負(fù)；（h）單純形法計算中，選取最大正檢驗(yàn)數(shù)k對應(yīng)的變量 xk 作為換入變量，將使目標(biāo)函數(shù)值得到最快的增長；（i）一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果；（j）線性規(guī)劃問題的任一可行解都可以用全部基可行解的線性組合表示；（k）若x1， x2分別是某一線性規(guī)劃問題的最優(yōu)解，則 X=1X1+2X2 也是該線性規(guī)劃問題的最優(yōu)解，其中1 , 2為正的實(shí)數(shù)；（l）線性規(guī)劃用兩階段法求解時，第一階段的目標(biāo)函數(shù)通常寫為min z=，但也可以寫為min z=，只要所有ki均為

3、大于零的常數(shù)；（m）對一個有 n個變量 m個約束的標(biāo)準(zhǔn)形的線性規(guī)劃問題，其可行域的頂點(diǎn)恰好為C 個；（n）單純形法的迭代計算過程是從一個可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個可行解；（o） 線性規(guī)劃問題的可行解如為最優(yōu)解 ，則該可行解一定是可行解；（p） 若線規(guī)劃問題具有可行解，切其可行域有界，則該線性規(guī)劃問題最多具有有限個數(shù)的最優(yōu)解；（q）線性規(guī)劃可行域的某一頂點(diǎn)若其目標(biāo)函數(shù)值優(yōu)于相鄰的所有頂點(diǎn)的目標(biāo)函數(shù)值，則該頂點(diǎn)處的目標(biāo)函數(shù)值達(dá)到最優(yōu)。P8 1.20 下表（表1-3）為用單純形法計算時某一步的表格。已知該線性規(guī)劃的目標(biāo)函數(shù)為max z=5x1+3x2,約束形式為，x3,x4為松弛變量，表中解

4、代入目標(biāo)函數(shù)后得z=10.表 13x1x2x3x4x3 2x1 acd0e101/51cj-zjb-1fg (a)求ag的值；(b)表中給出的解是否為最優(yōu)解P9 1.22 表1-5為某求極小值線性規(guī)劃問題的初始單純形表及迭代后的表,x4,x5為松弛變量,試求表中的al值及各變量下標(biāo)mt的值表 15x1x2x3x4x5xm 6xn 1b-1c3de1001cj - zja1-200xs fxt 4gh2i-111/21/201cj - zj07jkLP10 1.28 表1-6中給出某極大化問題的單純形表，問表中a1,a2,c1,c2,d為何值時以及表中變量屬那一種類型時有：(a) 表中解唯一最優(yōu)

5、解；(b) 表中解為無窮多最優(yōu)解之一；(c) 表中解為退化的可行解；(d)下一步迭代將以x1替換基變量x5；(e)該線性規(guī)劃問題具有無界解；(f) 該線性規(guī)劃問題無可行解。表 16x1x2x3x4x5x3 dx4 2x5 34-1a2a1-5-3100010001cj - zjc1c2000P20 10. 判斷下列說法是否正確：（a） 任何線性規(guī)劃問題存在并具有唯一的對偶問題；（b） 對偶問題的對偶問題一定是原問題;（c） 根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解，反之當(dāng)對偶問題無可行解時，其原問題具有無界解；（d） 設(shè)分別為標(biāo)準(zhǔn)形式的原問題與對偶問題的可行解， 分別為其最優(yōu)

6、解，則恒有 （e） 若線性規(guī)劃原問題有無窮多最優(yōu)解，則其對偶問題也一定具有無窮多最優(yōu)解；（f） 已知 y為線性規(guī)劃的對偶問題的最優(yōu)解，若y0，說明在最優(yōu)生產(chǎn)計劃中第 種資源已完全耗盡；（g） 已知 y為線性規(guī)劃的對偶問題的最優(yōu)解，若y=0，說明在最優(yōu)生產(chǎn)計劃中第 種資源一定有剩余；（h） 若某種資源的影子價格等于 k ，在其他條件不變的情況下，當(dāng)該種資源增加5個單位時，相應(yīng)的目標(biāo)函數(shù)值將增大5k ；（i） 應(yīng)用對偶單純形法計算時，若單純形法中某一基變量 xi<0，又xi所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解；（j） 若線性規(guī)劃問題中的 bi，cj 值同時發(fā)生變化，反

7、映到最終單純形表中，不會出現(xiàn)原問題與對偶問題均為非可行解的情況；（k） 線性規(guī)劃問題的最優(yōu)解中 ，如一變量 xj 為非基變量，則在原問題中，無論改變它 在目標(biāo)函數(shù)中的系數(shù) cj 或在各約束中的相應(yīng)系數(shù) aij ，反映到最終單純形表中，除該列數(shù)字有變化外，將不會引起其他列數(shù)字的變化。P31已知 線性規(guī)劃問題；max z=10x1+5x2st. 3x1+4x295x1+2x28x1,x20用單純形法求得最終表為表2-9所示：x1x2x3x4x2 3/2x1 101105/14-1/7-3/142/7cj - zj00-5/14-25/14試用靈敏度分析的方法判斷： 目標(biāo)函數(shù)系數(shù) c1 或c2 分別

8、在什么范圍內(nèi)變動，上述最優(yōu)解不變；(a) 約束條件右端頂 b1 ,b2當(dāng)一個保持不變時，另一個在什么范圍內(nèi)變化，上述最優(yōu)基保持不變；11 1998(b) 約束條件右端頂由 變?yōu)?時上述最優(yōu)解的變化。P34 2.36 某廠生產(chǎn),三種產(chǎn)品,分別經(jīng)過A,B,C三種設(shè)備加工. 已 知生產(chǎn)單位各種產(chǎn)品所需的 設(shè)備臺時,設(shè)備現(xiàn)有的加工能力及每件產(chǎn)品的預(yù)期利潤見表2-13表 2-13設(shè)備能力（臺·h）ABC1102142156100600300單位產(chǎn)品利潤（元）1064(a) 求獲利最大的產(chǎn)品生產(chǎn)計劃;(b) 產(chǎn)品每件的利潤增加到多大時才值得安排生產(chǎn)?如產(chǎn)品每件利潤增加到50/6元,求最優(yōu)計劃的變

9、化;(c) 產(chǎn)品的利潤在多大范圍內(nèi)變化時,原最優(yōu)計劃保持不變;(d) 設(shè)備A的能力如為100+10 ,確定保持最優(yōu)基不變的的變化范圍；(e) 如有一新產(chǎn)品,加工一件需設(shè)備A,B,C的臺時各為1,4,3h ,預(yù)期每件的利潤為8元,是否值得安排生產(chǎn)；(f) 如何同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品,試確定最優(yōu)計劃的變化.P39 10.判斷下列說法是否正確：（a） 運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解；（b） 在運(yùn)輸問題中，只要任意給出一組含（m+n-1）個非零的xij，且滿足xij=ai, xij=bi,就可以作為一個初始

10、基可行解；（c） 表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問題的單純刑法。（d） 按最小元素法（或伏格爾法）給出的初始基可行解，從每一空格出發(fā)可以找出而且能找出惟一的閉回路；（e） 如果運(yùn)輸問題單位運(yùn)價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化；（f） 如果運(yùn)輸問題單位運(yùn)價表的某一行（或某一列）元素分別乘上一個常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化；（g） 如果在運(yùn)輸問或轉(zhuǎn)運(yùn)問題模型中，Cij都是從產(chǎn)地I到銷地j的最小運(yùn)輸費(fèi)用，則運(yùn)輸問題同轉(zhuǎn)運(yùn)問題將得到相同的最優(yōu)解；（h） 當(dāng)所有產(chǎn)地產(chǎn)量和銷地的銷量均為整數(shù)值時，運(yùn)輸問題的最優(yōu)解也為整數(shù)值。P43 3.7 某玩具公司分別生產(chǎn)三種

11、新型玩具，每月可供量分別為1000件，2000件，它們分別被送到甲、乙、丙三個百貨商店銷售。已知每月百貨商店各類玩具預(yù)期銷售量均為1500件，由于經(jīng)營方面原因，各商店銷售不同玩具的盈利額不同。又知丙百貨商店要求至少供應(yīng)C玩具1000件，而拒絕進(jìn)A種玩具。求滿足下述條件下使總盈利額為最大的供銷分配方案。甲乙丙可供量ABC516124810911100020002000P47 3.16 如表3-20所示的運(yùn)輸問題中，若產(chǎn)地i有一個單位物資未運(yùn)出，則將發(fā)生儲存費(fèi)用。假定1，2，3產(chǎn)地單位物資儲存費(fèi)用分別為5，4和3。又假定產(chǎn)地2的物資至少運(yùn)出38個單位，產(chǎn)地3的物資至少運(yùn)出27個單位，試求解此運(yùn)輸問

12、題的最優(yōu)解。 銷地 ABC產(chǎn)量產(chǎn)地123112243253204030銷量302020P57 8.判斷下列說法是否正確（a） 整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解得目標(biāo)函數(shù)值；（b） 用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界；（c） 用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題，當(dāng)?shù)玫蕉嘤谝粋€可行解時，通常可任取其中一個作為下界值，再進(jìn)行比較剪枝；（d） 用割平面法求解整數(shù)規(guī)劃時，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解；（e） 用割平面法求解純整數(shù)規(guī)劃時，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值；（f） 指派問題效率

13、矩陣的每個元素都乘上同一常數(shù)k，將不影響最優(yōu)指派方案；（g） 指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，故也可以用表上作業(yè)法求解；（h） 求解0-1規(guī)劃的隱枚舉法是分枝定界法的特例；（i） 分枝定界法在需要分枝時必須滿足：一是分枝后的各子問題必須容易求解；二是各子問題解得集合必須覆蓋原問題的解。P62 5.12 分配甲、乙、丙、丁四個人去完成五項任務(wù)。每人完成各項任務(wù)時間如表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項任務(wù)，其余三人每人完成一項。試確定總花費(fèi)時間為最少的指派方案。 人ABCDE甲乙丙丁2539342429382742312628364220402337333245P

14、87 11.判斷下列說法是否正確：（a） 圖論中得圖不僅反應(yīng)了研究對象之間的關(guān)系，而且是真實(shí)圖像的寫照，因而對圖中點(diǎn)與點(diǎn)的相對位置、點(diǎn)與點(diǎn)的連線的長短曲直等都要嚴(yán)格注意；（b） 在任一圖G中，當(dāng)點(diǎn)集V確定后，樹圖是G中邊數(shù)最少的連通圖；（c） 如圖中某點(diǎn)vi有若干個相鄰點(diǎn)，與其距離最遠(yuǎn)的相鄰點(diǎn)vj,則邊i,j必不包含在最小支撐樹內(nèi)；（d） 如圖中從v1至各點(diǎn)均有惟一的最短路，則連接v1至其他各點(diǎn)的最短路再去掉重置部分，恰好構(gòu)成該圖的最小支撐樹；（e） 求圖的最小支撐樹以及求圖中的一點(diǎn)至另一點(diǎn)的最短路問題，都可以歸結(jié)為求整數(shù)規(guī)劃問題；（f） 求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個線性規(guī)劃模型。P101 7.判斷下列說法是否正確：（a） 網(wǎng)絡(luò)圖中任何一個結(jié)點(diǎn)都表示前一工序的結(jié)束和后一工序的開始；（b） 在網(wǎng)絡(luò)圖中只能有一個始點(diǎn)和一個