西南交大《管理運籌學(xué)A》作業(yè)答案.doc

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