2013-2014(1)學期管理運籌學A復習題二參考答案1對偶單純形法與單純形法的主要區別是每次迭代的基變量都滿足最優檢驗但不完全滿足（非負）約束。2若原問題有最優解，那么對偶問題（一定）有最優解，且原問題與對偶問題的最優（目標函數值）相等。 3原問題可行，而對偶問題不可行，則原問題（無）界。4一般的圖都具有（點）和（邊）兩個要素。5. 網絡中從一點到另一點的所有路中各邊權數之和最小的路稱為（最短路）。6. 線性規劃問題的基本解一定是基本可行解。（ ）7.用單純形法求解標準型線性規劃問題時，與檢驗數大于0相對應的變量都可被選作換入變量。（ ）8. 在運輸問題中，只要給出一組含有（m + n -1）個非零的xij且滿足全部約束，就可以作為基本可行解。（ ）9. 表上作業法實質上就是求解運輸問題的單純形法。（ ）10如果網絡G中不含有流f的增流鏈，則網絡的流為最大流。（ ）11. 增流鏈一定是不飽和鏈，不飽和鏈不一定是增流鏈。（ ）12. 如果網絡G中含有流f的增流鏈，則網絡的流值可以增加。（ ）13. 網絡的最小費用流與最小費用最大流是什么關系？答：網絡的最小費用流是指網絡的流值等于某一目標流的流值時，在這所有的流中費用最小的流；也就是在滿足某一目標運輸量下，所有的運輸方案中，運輸費用最小的運輸方案。而網絡的最小費用最大流是指在網絡流值達到最大時，所有流中費用最小的流；也就是達到運輸網絡最大運輸量的所有運輸方案中，運輸費用最小的運輸方案。可以看出，網絡的最小費用最大流是網絡的最小費用流的一種特殊情況，即目標流的流值等于最大流的的流值的情況。14當線性規劃的可行解集合非空時一定（ D ）A包含原點X=(0,0,0) B有界 C無界 D是凸集15. 有5個產地6個銷地的平衡運輸問題模型具有特征（ D ）A有11個變量 B有10個約束C 有30約束 D有10個基變量16. 根據所給的表和一組解判斷是否最優解，若不是，請求出最優解。 銷地 產地 B1B2B3B4產量 A1 3 113107 A21 9 284 A374 10 59銷量3656解：（1）計算檢驗數（格子左上角數值） 銷地 產地 B1B2B3B4 A1223100 A21 9-1-20 A311412 5-519310存在小于零的檢驗數不是最優解。（2）調整找到其閉回路，如上所示。調整量調整后的解為（格子右上角數值） 銷地 產地 B1B2B3B4產量 A1 3 11 3 107 A2 1 9 2 84 A37 4 10 59銷量3656（3）再次計算檢驗數 銷地 產地 B1B2B3B4 A1023100 A2121 8-2 A394125-539310不存在小于零的檢驗數已達最優。最優解為：（x13，x14，x21，x24，x32，x34）=（5，2，3，1，6，3）2013-2014(1)學期管理運籌學A復習題一參考答案1. 若基本可行解中非0變量的個數（ 小 ）于約束條件的個數時，就會出現退化解。2線性規劃問題若有最優解，一定可以在可行域的（ 頂點 ）達到。3確定初始基本可行解時，對大于型的約束，應當引入（ 人工 ）變量。4若原問題中第i個約束條件是“=”型約束，那么對偶問題的變量qi應是（ 自由 ）變量。5一般將邊上附有權的圖稱為（網絡）。6在線性規劃模型的標準型中,bj （j=1，2，m）一定是非負的。（ ）7線性規劃一般模型中的變量不一定是非負的。（ ）8用圖解法求最優解時，只需求出可行域頂點對應的目標值，通過比較大小，就能找出最優解。（ ）9. 線性規劃問題的一般模型中不能出現等式約束。（ ）10. 一般情況下，松弛變量和多余變量的目標函數系數為零。（ ）11.單純形法計算中，選取最大正檢驗數對應的變量作為換入變量，將使目標函數的值增加更快。（ ）12. 同一問題的線性規劃模型是唯一的。（ ）13. 有向圖G中任意兩點是可達的，稱此圖為強連通圖。（ ）14. X是線性規劃的基本可行解則有（ C ）A.X中的基變量非零，非基變量為零 BX不一定滿足約束條件 CX中的基變量非負，非基變量為零 D X是最優解 15在圖論中，圖與網絡的區別是（ D ）。 A圖中含有點，網絡中沒有點 B圖中含有邊，網絡中沒有邊C圖中含有鏈，網絡中沒有鏈 D在圖的邊上賦權就成了網絡16. 目標函數為max Z =28x4+x5+2x6，約束形式為“”，且x1，x2，x3為松弛變量， 表中的解代入目標函數中得Z=14