【優(yōu)質(zhì)】運(yùn)籌學(xué)與系統(tǒng)分析復(fù)習(xí)資料答案

1、運(yùn)籌學(xué)與系統(tǒng)分析 復(fù)習(xí)資料14單選題1 在產(chǎn)銷平衡運(yùn)輸問(wèn)題中，設(shè)產(chǎn)地為m個(gè)，銷地為 n 個(gè)，那么解中非零變量的個(gè)數(shù)【 C 】不能小于 ( m+n-1)不確定A. 等于( m+n-1)B.C. 不能大于 ( m+n-1) D.2 在單純形表的終表中，若非基變量的檢驗(yàn)數(shù)有 0 ，那么最優(yōu)解【 B 】A. 不存在 B. 唯一 C. 無(wú)窮多 D. 無(wú)窮大3. 在用對(duì)偶單純形法解最大化線性規(guī)劃問(wèn)題時(shí)，每次迭代要求單純形表中 【 D 】A.b 列元素不小于零B.檢驗(yàn)數(shù)都大于零C. 檢驗(yàn)數(shù)都不小于零D.檢驗(yàn)數(shù)都不大于零4 在約束方程中引入人工變量的目的是【 D 】A. 體現(xiàn)變量的多樣性B.變不等式為等式C.

2、 使目標(biāo)函數(shù)為最優(yōu)D.形成一個(gè)單位矩陣5 若運(yùn)輸問(wèn)題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部【A. 大于或等于零 B. 大于零 C. 小于零D.小于或等于零6在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為A.多余變量B. 松弛變量 C.自由變量D.人工變量7 線性規(guī)劃問(wèn)題的最優(yōu)解對(duì)應(yīng)其可行域的【A.內(nèi)點(diǎn)B. 頂點(diǎn) C. 外點(diǎn)D.幾何點(diǎn)8 對(duì)偶問(wèn)題的對(duì)偶是【D 】A. 基本問(wèn)題 B. 解的問(wèn)題 C.其它問(wèn)題D. 原問(wèn)題D. 解的分量個(gè)數(shù)9 原問(wèn)題與對(duì)偶問(wèn)題具有相同的最優(yōu)【A. 解 B. 目標(biāo)值 C. 解結(jié)構(gòu)10 在對(duì)偶問(wèn)題中，若原問(wèn)題與對(duì)偶問(wèn)題均具有可行解，則【 A 】A.兩者均具有最優(yōu)解，且它們最

3、優(yōu)解的目標(biāo)函數(shù)值相等B. 兩者均具有最優(yōu)解，原問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值小于對(duì)偶問(wèn)題最優(yōu)解的目標(biāo) 函數(shù)值C. 若原問(wèn)題有無(wú)界解，則對(duì)偶問(wèn)題無(wú)最優(yōu)解D. 若原問(wèn)題有無(wú)窮多個(gè)最優(yōu)解，則對(duì)偶問(wèn)題只有唯一最優(yōu)解11 表上作業(yè)法中初始方案均為【 A 】A. 可行解 B. 非可行解 C. 待改進(jìn)解 D. 最優(yōu)解12 若原問(wèn)題中 xi 為自由變量，那么對(duì)偶問(wèn)題中的第 i 個(gè)約束一定為【 A 】A. 等式約束B.“”型約束C.“”約束D. 無(wú)法確定13 線性規(guī)劃一般模型中，自由變量可以代換為兩個(gè)非負(fù)變量的【B 】A. 和B. 差 C. 積 D. 商14 建立運(yùn)籌學(xué)模型的過(guò)程不包括的階段是【 D 】A. 觀察環(huán)境B

4、.數(shù)據(jù)分析C. 模型設(shè)計(jì)D.模型實(shí)施15 使用人工變量法求解極大化線性規(guī)劃問(wèn)題時(shí)，當(dāng)所有的檢驗(yàn)數(shù) j 0 ，在 基變量中仍含有非零的人工變量，表明該線性規(guī)劃問(wèn)題 【 D 】A. 有唯一的最優(yōu)解B. 有無(wú)窮多個(gè)最優(yōu)解C. 為無(wú)界解D.無(wú)可行解16 線性規(guī)劃模型不包括的要素有【 D 】A. 目標(biāo)函數(shù)B.約束條件C. 決策變量D.狀態(tài)變量二 填空題1 線性規(guī)劃問(wèn)題的可行解是指滿足 約束條件和非負(fù)條件 解。2 若線形規(guī)劃問(wèn)題存在可行解，則該問(wèn)題的可行域是 凸 集。3 線性規(guī)劃問(wèn)題有可行解，則必有 。5 動(dòng)態(tài)規(guī)劃模型中，各階段開始時(shí)的客觀條件叫做 狀態(tài) 。6 當(dāng)線性規(guī)劃問(wèn)題的系數(shù)矩陣中不存在現(xiàn)成的可行基

5、時(shí)，一般可以加入人工變量 構(gòu)造可行解。7 在大 M 法中， M 表示 人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)。8 線形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式是： 目標(biāo)函授是求 是確定的 ，約束條件全為 線性等式 ，約束條件右側(cè)常數(shù)項(xiàng)全為 非負(fù)值 。9 線性規(guī)劃的右端常數(shù)項(xiàng)其對(duì)偶問(wèn)題的 價(jià)值系數(shù) ；線性規(guī)劃的第 i 個(gè)約束條件 其對(duì)偶問(wèn)題 決策變量 。10在一個(gè)基本可行解中， 取正數(shù)值的變量稱為 基變量 ；取零值的變量稱為 非 基變量 。11 在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為自由變量 。12 為求解需要量大于供應(yīng)量的運(yùn)輸問(wèn)題，可虛設(shè)一個(gè)供應(yīng)點(diǎn)，該點(diǎn)的供應(yīng)量等 于 需求量與供應(yīng)量的差值 。13 線性規(guī)劃問(wèn)題可分為目標(biāo)

6、函數(shù)求極大值 和 極小值 兩類。14 若線性規(guī)劃為最大化問(wèn)題，則對(duì)偶問(wèn)題為極小化 問(wèn)題。15 用運(yùn)籌學(xué)解決問(wèn)題的核心是建立 數(shù)學(xué)模型 ，并對(duì) 數(shù)學(xué)模型 求解。16 在將線性規(guī)劃問(wèn)題的一般形式化為標(biāo)準(zhǔn)形式時(shí)，引入的松弛變量在目標(biāo)函數(shù) 中的系數(shù)為 零 。17 動(dòng)態(tài)規(guī)劃模型的構(gòu)成要素有 階段 、 狀態(tài) 、 決策和策略 、 狀態(tài)轉(zhuǎn)移 和 目標(biāo)函數(shù) 。三計(jì)算題1 用大 M法求解線性規(guī)劃問(wèn)題MinZ = 3X1 + X2+ X3s.t X1 2X2 + X3 114X1+ X2 + 2X3 3 2X1X31X1 , X2,X3 0解：（1）將線性規(guī)劃化為標(biāo)準(zhǔn)型。 引入松弛變量 x4 ，剩余變量 x5，并令

7、 Z' Z ; max Z'=3x 1 x2 x3x1 2x2 x3 x4 11得： 4x1 x2 2x3 x5 3s.t. 1 2 3 52x1 x3 1x1,x2,x3,x4,x5 0 約束方程系數(shù)矩陣 A 為：1-2110A-4120-1-20100A中只有一個(gè)單位列向量，故對(duì)第二、第三個(gè)約束條件引入人工變量 x6，x7 對(duì)模型整理得：max Z'=3x 1 x2 x3 Mx6 Mx7x1 2x2 x3 x4 11s.t.4x1 x2 2x3 x5 x6 32x1 x3 x7 1xj 0; j 1,2,37改造后的系數(shù)矩陣 A 為：1 -2 1 1 0 0 0A

8、-4 1 2 0 -1 1 0-2 0 1 0 0 0 1以 x4 , x6 , x7為初始基變量進(jìn)行單純形法求解如下表。CBXBcjxjb3-1-100MMjx1x2x3x4x5x6x70x4111-21100011/1Mx63-4120-1103/2Mx71-20100011Z'4M3-6M-1+M-1+3M0-M000x4103-20100-1-Mx610100-11-21-1x31-2010001-Z'1+M1-1+M00-M01-3M0x4123001-22-54-1x210100-11-2-1x31-2010001-Z'21000-M1-M-1-M3x141

9、001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z'-2000-1/3-1/31/3-M2/3-M故，當(dāng) x1 4,x2 1,x3 9時(shí)，取得最優(yōu)解。 Z Z' 22用單純形法求解下列線性規(guī)劃 , 解出最優(yōu)解。MaxZ = 3X1 + 4X2s.t X1 + X2 42X1+ 3X2 6X1 , X2 0 解：將線性規(guī)劃化成標(biāo)準(zhǔn)型，引入松弛變量 x3和 x4： max Z=3x 1 4x2x1 x2 x3 4s.t. 2x1 3x2 x4 6x1,x2,x3,x4 01 1 1 0系數(shù)矩陣 A為： A，以 x3和 x4為初

10、始基變量計(jì)算，單純性計(jì)算表Z034000 x321/301-1/364 x222/3101/33Z81/300-4/30 x310-1/21-1/23 x1313/201/2Z90-1/20-3/2故，當(dāng) x1 3,x2 0 時(shí)，線性規(guī)劃取得最大值 Z 93 已知：運(yùn)輸問(wèn)題的單價(jià)表。（ 1） 用最小元素法找出初始可行解；（ 2） 用位勢(shì)法求出初始可行解相應(yīng)的檢驗(yàn)數(shù)；（ 3） 求最優(yōu)方案。單位：萬(wàn)元單價(jià)甲乙丙供給量A35810B74620C32910需求量5255解：（1）用最小元素法求初始可行解。設(shè)供應(yīng)地 A、 B、C 到甲、乙、丙三地的運(yùn)價(jià)分別為 cij ；運(yùn)量分別為 xij 。由 于總的供

11、給量為 40，需求量為 35，為供給量大于需求量的不平衡運(yùn)輸問(wèn)題，增 設(shè)一個(gè)假想需求地丁，需求量為 5，A、B、C 到給地的運(yùn)價(jià)均為零。運(yùn)價(jià)表變更 為：?jiǎn)蝺r(jià)甲乙丙丁（存儲(chǔ)）供給量A358010B746020C329010需求量5255540先不考慮丁地的需求，由表格可知 x32的運(yùn)價(jià)最小， C 全部供應(yīng)乙地，乙地 需求還剩 15；依次找出最小運(yùn)價(jià)，首先滿足其需求，重復(fù)此過(guò)程，可以得出初 始可行解，如下表所示：運(yùn)量甲乙丙丁A53050850B071545600C031020900(2)用位勢(shì)法求檢驗(yàn)數(shù)。設(shè) u1 0,u2 0 ；可知 u1 v1 3;u1 v4 0;u2 v2 4;u2 v3 6

12、;u3 v2 2;代入，可解： u1 0;u2 0;u3 2;v1 3;v2 4;v3 6.v4 0 ；計(jì)算如下表：甲乙丙丁A30u1B46u2C2u3v1v2v3v4甲乙丙丁A34600B34600C124-2-23460成本表ui vj根據(jù) ij cij (ui vj ) 計(jì)算如下表：cijui vj甲乙丙丁A3580B7460C3290ij甲乙丙丁A3460B3460C124-2甲乙丙丁A0120B4000C20524 將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)型 MinZ = X1 X2+3 X3s.t X1 X2 + X3 105X17X2 + 3X3 8X1X22X318X10, X2 0,X3

13、無(wú)符號(hào)限制解，引入松弛變量 x4 ，x6 ，剩余變量 x5 ，兩個(gè)非負(fù)變量 x'3和 x''3，且 x3 x 3' x ''3令 Z' Z ，則線性規(guī)劃的標(biāo)準(zhǔn)型為：max Z'= x1 x2 3 x'3 x''3x1 x2 x'3 x''3 105x1 7x2 3x'3 3x''3 x4 8s.t. x1 x2 x5 2x'3 x''3 x6 18 x1,x2,x'3,x''3,x4,x5,x6 05 有四項(xiàng)工作

14、要甲，乙，丙，丁四個(gè)人去完成，每一項(xiàng)工作只許一個(gè)人去完成， 四項(xiàng)工作要四個(gè)不同的人去完成； 問(wèn)：應(yīng)指派每個(gè)人完成哪一項(xiàng)工作， 使得總的 消耗時(shí)間為最短？用匈牙利法求解。消耗時(shí)間工作 1工作 2工作 3工作 4甲15182124乙21232218丙26171619丁23211917故，所有檢驗(yàn)數(shù)均為非負(fù)值，得到最優(yōu)解：x11 5,x22 15; x235;x32 10最小運(yùn)價(jià) Zmin5 3 15 4 10 2 5 6 125解：（1）以各員工完成各項(xiàng)工作的時(shí)間構(gòu)造矩陣一，如下：矩陣151821242123221826171619232119172）對(duì)矩陣一進(jìn)行行約減，即每一行數(shù)據(jù)減去本行數(shù)據(jù)中

15、的最小數(shù)，得矩陣二矩陣二0 3 6 93 5 4 010 1 0 36 4 2 03）檢查矩陣二， 若矩陣二各行各列均有“ 0”，則跳過(guò)此步，否則進(jìn)行列約減，即每一列數(shù)據(jù)減去本列數(shù)據(jù)中的最小數(shù)，得矩陣三矩陣三0 2 6 93 4 4 010 0 0 36 3 2 04） 畫“蓋 0”線。即畫最少的線將矩陣三中的 0 全部覆蓋住0 2 6 93 4 4 010 0 0 36 3 2 05）數(shù)據(jù)轉(zhuǎn)換。 若“蓋0”線的數(shù)目等于矩陣的維數(shù)則跳過(guò)此步， 若“蓋0”線得數(shù)目小于矩陣得維數(shù)則進(jìn)行數(shù)據(jù)轉(zhuǎn)換，本題屬于后一種情況，應(yīng)進(jìn)行轉(zhuǎn)換， 操作步驟如下：A、找出未被“蓋 0”線覆蓋的數(shù)中的最小值，例中 2B、

16、將未被“蓋 0”線覆蓋住的數(shù)減去。C、將“蓋 0”線交叉點(diǎn)的數(shù)加上可得矩陣四0 2 6 111 2 2 010 0 0 54 1 0 06）重復(fù)步驟（ 4）、（5）直到“蓋 0”線的數(shù)目等于矩陣的維數(shù)，計(jì)算過(guò)程如下。0 2 6 11得到矩陣五1 2 2 010 0 0 54 1 0 07）求最優(yōu)解。對(duì) n維矩陣，找出不同行、不同列的 n個(gè)“ 0”，每個(gè)“ 0”的位置代表一對(duì)配置關(guān)系，具體步驟如下：A、先找只含有一個(gè)“ 0”的行（或列），將該行（或列）中的“ 0”打“”B、將帶“”的“ 0”所在列（或行）中的“ 0”打C、重復(fù)（ 1）步和（ 2）步至結(jié)束。若所有行列均含有多個(gè)“ 0”，則從“ 0

17、”的數(shù)目最少的行或列中任選一個(gè)0”打111000故，工作分配關(guān)系結(jié)果如下表。即甲完成工作 1，乙完成工作 4，丙完成工作 2，丁完成工作 3消耗時(shí)間工作 1工作 2工作 3工作 4甲15乙18丙17丁196寫出下列線形規(guī)劃問(wèn)題的對(duì)偶問(wèn)題MaxZ=X1+2X2+3X3s.t 3X1+ 3X2+ X3 122X1+ X2 + 4X3 182X1+ 2X2 + 3X3 = 20X1, X2 , X3 0 解：將線性規(guī)劃化成一般對(duì)稱形式。 maxZ x1 2x2 3x33x1 3x2 x3 122x1 x2 4x3 18s.t. 2x1 2x2 3x3 202x1 2x2 3x3 20x1,x2,x3 0寫出其對(duì)偶問(wèn)題：min W= 12y'1 18y2 20 y'3 y&#