（精選）運籌學習題Word版

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

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

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

4、代入目標函數(shù)后得z=10.表 13x1x2x3x4x3 2x1 acd0e101/51cj-zjb-1fg (a)求ag的值；(b)表中給出的解是否為最優(yōu)解P9 1.22 表1-5為某求極小值線性規(guī)劃問題的初始單純形表及迭代后的表,x4,x5為松弛變量,試求表中的al值及各變量下標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） 設分別為標準形式的原問題與對偶問題的可行解， 分別為其最優(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 ，在其他條件不變的情況下，當該種資源增加5個單位時，相應的目標函數(shù)值將增大5k ；（i） 應用對偶單純形法計算時，若單純形法中某一基變量 xi<0，又xi所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解；（j） 若線性規(guī)劃問題中的 bi，cj 值同時發(fā)生變化，反

7、映到最終單純形表中，不會出現(xiàn)原問題與對偶問題均為非可行解的情況；（k） 線性規(guī)劃問題的最優(yōu)解中 ，如一變量 xj 為非基變量，則在原問題中，無論改變它 在目標函數(shù)中的系數(shù) cj 或在各約束中的相應系數(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試用靈敏度分析的方法判斷： 目標函數(shù)系數(shù) c1 或c2 分別

8、在什么范圍內(nèi)變動，上述最優(yōu)解不變；(a) 約束條件右端頂 b1 ,b2當一個保持不變時，另一個在什么范圍內(nèi)變化，上述最優(yōu)基保持不變；11 1998(b) 約束條件右端頂由 變?yōu)?時上述最優(yōu)解的變化。P34 2.36 某廠生產(chǎn),三種產(chǎn)品,分別經(jīng)過A,B,C三種設備加工. 已 知生產(chǎn)單位各種產(chǎn)品所需的 設備臺時,設備現(xiàn)有的加工能力及每件產(chǎn)品的預期利潤見表2-13表 2-13設備能力（臺·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) 設備A的能力如為100+10 ,確定保持最優(yōu)基不變的的變化范圍；(e) 如有一新產(chǎn)品,加工一件需設備A,B,C的臺時各為1,4,3h ,預期每件的利潤為8元,是否值得安排生產(chǎn)；(f) 如何同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品,試確定最優(yōu)計劃的變化.P39 10.判斷下列說法是否正確：（a） 運輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解；（b） 在運輸問題中，只要任意給出一組含（m+n-1）個非零的xij，且滿足xij=ai, xij=bi,就可以作為一個初始

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

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

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

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

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