《運(yùn)籌學(xué) 試題》由會員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué) 試題（5頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、運(yùn)籌學(xué)試題 一、填空題 1. 線性規(guī)劃闖題中，如果在約束條件中出現(xiàn)等式約束，我們通常用增加 人工變 量—的方法來產(chǎn)生初始可行基。 2. 在圖論方法中，樹具有 的特點(diǎn)，樹中的連線數(shù)必定等于 。 3. 線性規(guī)劃數(shù)學(xué)模型三要素： 、 、 4. 在多目標(biāo)決策問題中，當(dāng)目標(biāo)中規(guī)定了 x=b為達(dá)到了目標(biāo)，則必須同時(shí)滿足 才算達(dá)到了目標(biāo)。 7 ?動態(tài)規(guī)劃是解決 決策過程最優(yōu)化問題的一種方法。 1、 在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負(fù)限制的解為 可行解 2、 在線性規(guī)劃問題中，圖解法適合用于處理丄量 為兩個(gè)的線性規(guī)劃問題。 3、 求解不平衡的運(yùn)輸問題的基本思想是 設(shè)立虛供地

2、或虛需求點(diǎn)，化為供求平 衡的標(biāo)準(zhǔn)形式。 4、 在圖論中，稱無圈的連通圖為樹。 5、 運(yùn)輸問題中求初始基本可行解的方法通常有最小費(fèi)用法、西北角法兩 種方法。 3?原問題的第1個(gè)約束方程是“二”型，則對偶問題相應(yīng)的變量是—無約束—變 量。 4?求最小生成樹問題，常用的方法有：避圈法和破圈法。 二、單項(xiàng)選擇題 1?設(shè)P是線性規(guī)劃問題，D是其對偶問題，貝H ）不正確。 A. P有最優(yōu)解，D不一定有最優(yōu)解 B. 若P和D都有最優(yōu)解，則二者最優(yōu)值肯定相等 C. 若P無可行解，則D無有界最優(yōu)解 D. D的對偶問題為P 2?在求minz的線性規(guī)劃問題中，貝H ）不正確。 A. 最優(yōu)解只

3、能在可行基解中才有 B. 最優(yōu)解只能在基解中才有 C. 基變量的檢驗(yàn)數(shù)只能為零 D. 有可行解必有最優(yōu)解 3. 用圖解法求解下列問題：max S=2x-3y s.t.-x+2y<=2 x+2y<=6 x-y<=3 x+3y>=3 x,y>=0 其最優(yōu)解為（ ） A. （2，2） B. （4，1） C. （3，0） D. （2，5） 4. 若運(yùn)輸問題在總供應(yīng)量大于總需要量時(shí)，（）。 A. 必須用線性規(guī)劃單純形法求最優(yōu)解 B. 不存在可行解 C. 虛設(shè)一個(gè)需求點(diǎn) D. 虛設(shè)一個(gè)供應(yīng)點(diǎn) 3、對于線性規(guī)劃問題，下列說法正確的是（ D ） A線性規(guī)劃問題可能沒有可行解

4、 B在圖解法上，線性規(guī)劃問題的可行解區(qū)域都是“凸”區(qū)域 C線性規(guī)劃問題如果有最優(yōu)解，則最優(yōu)解可以在可行解區(qū)域的頂點(diǎn)上到達(dá) D上述說法都正確 4、下面哪些不是線性規(guī)劃問題的標(biāo)準(zhǔn)形式所具備的（C A所有的變量必須是非負(fù)的 B所有的約束條件（變量的非負(fù)約束除外）必須是等式 C添加新變量時(shí)，可以不考慮變量的正負(fù)性 D求目標(biāo)函數(shù)的最小值 6、在用單純形法求解線性規(guī)劃問題時(shí)，下列說法錯誤的是（D A如果在單純形表中，所有檢驗(yàn)數(shù)都非正，則對應(yīng)的基本可行解就是最優(yōu)解 B如果在單純形表中，某一檢驗(yàn)數(shù)大于零，而且對應(yīng)變量所在列中沒有正數(shù)， 則線性規(guī)劃問題沒有最優(yōu)解 C利用單純形表進(jìn)行迭代，我

5、們一定可以求出線性規(guī)劃問題的最優(yōu)解或是判斷 線性規(guī)劃問題無最優(yōu)解 D如果在單純形表中，某一檢驗(yàn)數(shù)大于零，則線性規(guī)劃問題沒有最優(yōu)解 1. 使用人工變量法求解極大化線性規(guī)劃問題時(shí)，當(dāng)所有的檢驗(yàn)數(shù) 在基變量 中仍含有非零的人工變量，表明該線性規(guī)劃問題 【 】 A?有唯一的最優(yōu)解 B?有無窮多最優(yōu)解 C.為無界解 D.無可行解 2. 對偶單純形法解最大化線性規(guī)劃問題時(shí)，每次迭代要求單純形表中 【 】 A. b列元素不小于零 B.檢驗(yàn)數(shù)都大于零 C.檢驗(yàn)數(shù)都不小于零 D.檢驗(yàn)數(shù)都不大于零 3. 已知某個(gè)含10個(gè)結(jié)點(diǎn)的樹圖，其中9個(gè)結(jié)點(diǎn)的次為1,1, 3，1，1，1，3, 1，3,

6、則另一個(gè)結(jié)點(diǎn)的次為 【 】 A. 3 B. 2 C. 1 D.以上三種情況均有可能 4. 如果要使目標(biāo)規(guī)劃實(shí)際實(shí)現(xiàn)值不超過目標(biāo)值。則相應(yīng)的偏離變量應(yīng)滿足【B】 A. d+>0 B?仁0 C. d-=0 5. 在運(yùn)輸方案中出現(xiàn)退化現(xiàn)象，是指數(shù)字格的數(shù)目 【 】 A. 等于 m+n B. 等于 m+n-1 C. 小于 m+n-1 D. 大于 m+n-1 6. 關(guān)于線性規(guī)劃的原問題和對偶問題，下列說法正確的是 【 】 A. 若原問題為元界解，則對偶問題也為無界解 B. 若原問題無可行解，其對偶問題具有無界解或無可行解 c.若原問題存在可行解，其對偶問題必存在可行解 D

7、. 若原問題存在可行解，其對偶問題無可行解 7. 下列說法正確的是 【 】 A.線性規(guī)劃問題的基本解對應(yīng)可行域的頂點(diǎn) B. 若X』是某線性規(guī)劃問題的可行黑 則X訊Xi十嘉蜀（其中九+為劉地必是 該問題的可行解 c單純形袪解標(biāo)準(zhǔn)的線性規(guī)劃何題時(shí)，當(dāng)所有檢驗(yàn)數(shù)Cj-NW03t即可判定表中 解為最優(yōu)解 D.單純形法解標(biāo)準(zhǔn)的線性規(guī)劃問題時(shí)，按最小比值原則確定換出基變量是為了 保證迭代計(jì)算后的解仍為基本可行解 三、 判斷 3、 如果在單純形表中，所有的檢驗(yàn)數(shù)都為正，則對應(yīng)的基本可行解就是最優(yōu)解 （X） 4、 如果單純形表中，某一檢驗(yàn)數(shù)大于0,而且對應(yīng)變量所在列中沒有正數(shù)，則 線性規(guī)

8、劃問題無最優(yōu)解（V） 6、在線性規(guī)劃的模型中全部變量要求是整數(shù)（X） 增加約束條件時(shí)，線性規(guī)劃模型的可行域不擴(kuò)大。（ ） （1） 線性規(guī)劃問題的對偶問題的對偶問題是原問題。（ ） （2） 動態(tài)規(guī)劃的逆推與順推解法得到相同的最優(yōu)解。（ ） （3） 若某種資源的影子價(jià)格等于k，在其他條件不變的情況下,當(dāng)該種資源增 加5時(shí)，相應(yīng)的目標(biāo)函數(shù)值將增大5k。（ ） （4） 加非負(fù)權(quán)無向連通圖中任兩點(diǎn)間必存在最短路徑。（ ） 四、 名詞解釋 線性規(guī)劃：一般地，如果我們要求出一組變量的值，使之滿足一組約束條件，這 組約束條件只含有線性不等式或線性方程，同時(shí)這組變量的值使某個(gè)線性的目標(biāo) 函數(shù)取

9、得最優(yōu)值（最大值或最小值）。這樣的數(shù)學(xué)問題就是線性規(guī)劃問題 x x x 可行解：在線性規(guī)劃問題的一般模型中，滿足約束條件的一組1' 2 n值 稱為此線性規(guī)劃問題的可行解， 最優(yōu)解：在線性規(guī)劃問題的一般模型中，使目標(biāo)函數(shù)f達(dá)到最優(yōu)值的可行解稱 為線性規(guī)劃問題的最優(yōu)解。 運(yùn)輸問題：將一批物資從若干倉庫（簡稱為發(fā)點(diǎn)）運(yùn)往若干目的地（簡稱為收點(diǎn)）， 通過組織運(yùn)輸，使花費(fèi)的費(fèi)用最少，這類問題就是運(yùn)輸問題 閉回路：如果在某一平衡表上已求得一個(gè)調(diào)運(yùn)方案，從一個(gè)空格出發(fā)，沿水平方 向或垂直方向前進(jìn)，遇到某個(gè)適當(dāng)?shù)奶钣姓{(diào)運(yùn)量的格子就轉(zhuǎn)向前進(jìn)。如此繼續(xù)下 去，經(jīng)過若干次，就一定能回到原來出發(fā)的空格。這

10、樣就形成了一個(gè)由水平線段 和垂直線段所組成的封閉折線，我們稱之為閉回路 四、問答 1、用圖解法求解兩個(gè)變量線性規(guī)劃問題的解的一般步驟 答：（1）在平面直角坐標(biāo)系中，求出可行解區(qū)域，可行解區(qū)域是各約束條件所表 示的半平面的公共部分。 (2)求最優(yōu)解：將坐標(biāo)函數(shù)中的f看作參數(shù)，作出等值線。選取一條等值線， 使它與可行解區(qū)域有公共點(diǎn)，并取得最大值或是最小值 3、簡要描述求解線性規(guī)劃問題兩階段 答：第一階段，如果線性規(guī)劃問題已經(jīng)具有典則形式，并且約束方程右端常數(shù)非 負(fù)，則可以直接寫出對應(yīng)的單純形表，進(jìn)入第二階段，否則，在第一階段應(yīng)引入 輔助問題，求出輔助問題的最優(yōu)解，再得到原問題的基本可行解

11、對應(yīng)的單純形表 或判定原問題無可行解，在兩個(gè)階段的計(jì)算過程中，都可以利用單純形法。 4、解“運(yùn)輸問題”的一般步驟 答：(1)編制初始調(diào)運(yùn)方案：我們可以利用“西北角法”來編制初始調(diào)運(yùn)方案。 (2) 檢驗(yàn)：為了判定某一調(diào)運(yùn)方案是否最優(yōu)，我們可以利用“位勢法”來求出檢 驗(yàn)數(shù)。 (3) 調(diào)運(yùn)方案調(diào)整。 五、解答題 1．某機(jī)械部件每件進(jìn)廠價(jià)為500元，年需求總額為60萬元，求得最佳訂貨批量 為 300件，年保管費(fèi)用率為12％。求按經(jīng)濟(jì)訂貨批量進(jìn)貨時(shí)，年訂貨多少次， 每次訂貨費(fèi)用、年保管費(fèi)用和年總存貨費(fèi)用各是多少。 2．用單純形法求解某線性規(guī)劃問題得到最終單純形表： Cj 基變量 50

12、 40 10 60 S X1 X2 X3 X4 a c 0 1 1/2 1 6 b d 1 0 1/4 2 4 Cj-Zj 0 0 e f G (1) 給出a,b,c,d,e,f,g的值或表達(dá)式； 2) 指出原問題是求目標(biāo)函數(shù)的最大值還是最小值 (3) 用a+Aa, b+Ab分別代替a和b，仍然保持上表是最優(yōu)單純形表，求Aa, Ab滿足的范圍。 四、(每小題 10分，共 20分) 1．求總運(yùn)費(fèi)最小的運(yùn)輸問題，某步運(yùn)輸圖如下： B1 B2 B3 供應(yīng)量 A1 3 (3) (5) (7) 3 A2 2

13、(4) 4 (2) (4) 6 A3 (5) 1 (6) 5 (3) d 需要量 a b c e (1)寫出a,b,c,d,e的值，并求出最優(yōu)運(yùn)輸方案； (2)A3到B1的單位運(yùn)費(fèi)滿足什么條件時(shí)，表中運(yùn)輸方案為最優(yōu)方案。 2.如圖所示的運(yùn)輸網(wǎng)絡(luò)上，求最大流，邊上括號內(nèi)為($) 五、（本題8分） 某風(fēng)景區(qū)有6個(gè)海島，相互間的距離如下表所示（哩）?，F(xiàn)欲架設(shè)海上浮橋， 使各島相連且與陸地相連，已知第1個(gè)海島離海岸最近，為0．3哩，求使架設(shè) 浮橋長度最短的方案。 2 3 4 5 6 1 1. 0 3. 0 2. 5 5. 0

14、4. 0 2 2. 6 1. 7 4. 2 3. 2 3 1. 0 2. 5 1. 3 4 2. 6 1. 8 5 1. 3 三、多項(xiàng)選擇題 19．線性規(guī)劃問題的標(biāo)準(zhǔn)型最本質(zhì)的特點(diǎn)是 【 】 A.目標(biāo)要求是極小化 B.變量可以取任意值 C. 變量和右端常數(shù)要求非負(fù) D.約束條件一定是等式形式 22．關(guān)于運(yùn)輸問題，下列說法正確的是 【 】 A. 在其數(shù)學(xué)模型中，有m+n —1個(gè)約束方程 B. 用最小費(fèi)用法求得的初始解比用西北角法得到的初始解在一般情況下更靠 近最優(yōu)解 C. 對任何一個(gè)運(yùn)輸問題，一定存在最優(yōu)解 D. 對于產(chǎn)銷不平衡的運(yùn)輸問題。同樣也可以用表上作業(yè)法求解