《運(yùn)籌學(xué)》試題及答案

1、運(yùn)籌學(xué)試題及答案19、簡(jiǎn)述線性規(guī)劃模型主要參數(shù)（P11）（1）、價(jià)值系數(shù)：目標(biāo)函數(shù)中決策變量前的系數(shù)為價(jià)值系數(shù)（2）、技術(shù)系數(shù)：約束條件中決策變量前的系數(shù)（3）、約束條件右邊常數(shù)項(xiàng)15、簡(jiǎn)述線性規(guī)劃解幾種可能的結(jié)果（情形）（ppt第二章39或89頁(yè)）（1）.有唯一最優(yōu)解（單純形法中在求最大目標(biāo)函數(shù)的問(wèn)題時(shí)，對(duì)于某個(gè)基 本可行解，所有6jW0）（2）.無(wú)可行解，即可行域?yàn)榭沼?，不存在滿足約束條件的解，也就不存在 最優(yōu)解了。（3）.無(wú)界解，即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú) 窮小，一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件（4）.無(wú)窮多個(gè)最優(yōu)解，則線段上的所有點(diǎn)都代表了最

2、優(yōu)解（5）退化問(wèn)題，基變量有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次 迭代中就有一個(gè)或幾個(gè)基變量等于零，用圖解法無(wú)退化解1、簡(jiǎn)述單純形法的基本思路（p70）從可行域中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是，則再找另 一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直 到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線 性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。17、簡(jiǎn)述線性規(guī)劃中添加人工變量的前提（p85）在系數(shù)矩陣中直接找不到初始可行解，進(jìn)而通過(guò)添加人工變量的方法來(lái)構(gòu)造 初始可行基，得出初始基本可行解10、簡(jiǎn)述線性規(guī)劃對(duì)偶問(wèn)題的基本性質(zhì)（p122）（1）對(duì)稱性

3、（2）弱對(duì)偶性（3）強(qiáng)對(duì)偶性（4）最優(yōu)性（5）互補(bǔ)松弛型 原函數(shù)與對(duì)偶問(wèn)題的關(guān)系1）求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題中有n個(gè)變量m個(gè)約束條件，它的約束 條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問(wèn)題， 有m個(gè)變量n個(gè)約束條件，其約束條件都為大于等于不等式。2）原問(wèn)題的目標(biāo)函數(shù)中的價(jià)值系數(shù)為對(duì)偶問(wèn)題中的約束條件的右邊常數(shù)項(xiàng)，并 且原問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)價(jià)值系數(shù)就等于對(duì)偶問(wèn)題中的第i個(gè)約束條件的 右邊常數(shù)項(xiàng)。3）原問(wèn)題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問(wèn)題的目標(biāo)函數(shù)中價(jià)值系數(shù)。并且原 問(wèn)題的第i個(gè)約束條件的右邊常數(shù)項(xiàng)就等于零對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變 量的系數(shù)。4）對(duì)偶問(wèn)題的

4、約束條件的系數(shù)矩陣A是原問(wèn)題約束矩陣的轉(zhuǎn)置。5、運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，但為什么不用單純形法求解因?yàn)檫@類線性規(guī)劃問(wèn)題在結(jié)構(gòu)上存在著特殊性,表上作業(yè)法根據(jù)運(yùn)輸問(wèn)題的 特點(diǎn)來(lái)設(shè)計(jì)的特殊的單純形法，可以更加形象直觀簡(jiǎn)單的解決運(yùn)輸問(wèn)題。9、簡(jiǎn)述表上作業(yè)法的基本步驟（1）用最小元素法找出初始基可行解，也就是初始調(diào)運(yùn)方案。對(duì)于有m個(gè)產(chǎn) 地n個(gè)銷地的產(chǎn)銷平衡問(wèn)題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約 束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個(gè)獨(dú)立的約束方程，即運(yùn)輸問(wèn)題 有m+n-1個(gè)基變量。在mXn的產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格，其相對(duì)應(yīng)的 調(diào)運(yùn)量的值即為基變量的值。（2）求各非基

5、變量的檢驗(yàn)數(shù)。（3）用閉回路法來(lái)判別問(wèn)題是否達(dá)到最優(yōu)解。如已是最優(yōu)解則停止計(jì)算， 否則繼續(xù)下一步。（4）用閉回路法進(jìn)行基變換，確定入基變量和出基變量，找出新的基本可 行解。在表上用閉回路法調(diào)整。其敝學(xué)模型為：.再指qgSl11、簡(jiǎn)述指派問(wèn)題的標(biāo)準(zhǔn)形式及數(shù)學(xué) 模型（？?七 或書上 p179）設(shè)n個(gè)人被分配去做n件工作， 規(guī)定每個(gè)人只做一件工作，每件工作 只有一個(gè)人去做。已知第i個(gè)人去做 第j件工作的效率（時(shí)間或費(fèi)用）為 Cij（i=1.2n；j=1.2n）并假設(shè)Cij N0。問(wèn)應(yīng)如何分配才能使總效率（時(shí)設(shè)決策變蟄d指派簫i個(gè)人去鍬第j件工作Xy=j|.n ）不指派第1個(gè)人去隧第.1祥工作 C.i

6、rrr間或費(fèi)用)最高？12、簡(jiǎn)述分枝定界法的基本步驟分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問(wèn)題。如果其最優(yōu)解不符合整數(shù)條 件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線性規(guī)劃的可 行域分成子區(qū)域(稱為分枝)，再求解這些子區(qū)域上的線性規(guī)劃問(wèn)題，不斷縮小 整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解?；舅悸罚?、先求出線性規(guī)劃的解2、確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)*初始上界和下界z3、將一個(gè)線性規(guī)劃問(wèn)題分為兩枝，并求解4、修改最優(yōu)目標(biāo)函數(shù)上、下界5、比較與剪枝：各分枝的目標(biāo)函數(shù)值中，若有小于 乙者，則剪掉此枝， 表明此子問(wèn)題已經(jīng)探清，不必再分枝了；否則繼續(xù)分枝。6、如此反復(fù)進(jìn)行，直

7、到得到Z=Z*為止，即得最優(yōu)解X*。6、簡(jiǎn)述目標(biāo)規(guī)劃的目標(biāo)函數(shù)主要類型及其數(shù)學(xué)表達(dá)式。目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能取極小形式，即minz=f(d+,d-)，共有如下三種形 式：(1),要求恰好等于目標(biāo)值，即希望決策值超過(guò)和不足目標(biāo)值的部分都盡可 能小，因此由函數(shù)minz=f(d+d-)； (2)，要求不超過(guò)目標(biāo)值，允許達(dá)不到目標(biāo) 值，即希望決策值不超過(guò)目標(biāo)值，也希望d+越小越好，因此有minz=f (d+) ;(3) 要求不低于目標(biāo)值，允許超過(guò)目標(biāo)值，即希望決策值不低于目標(biāo)值，也希望d- 越小越好，因此有minz=f(d-).2、簡(jiǎn)述運(yùn)籌學(xué)中背包問(wèn)題的一般提法(p225)對(duì)于N種具有不同重量和不同價(jià)

8、值的物品，在攜帶物品總重量限制的情況下， 決定這N種物品中每一種物品多少數(shù)量裝入背包內(nèi)，使得裝入背包物品的總價(jià)值 最大。4、建立動(dòng)態(tài)規(guī)劃模型時(shí)，應(yīng)定義狀態(tài)變量，請(qǐng)說(shuō)明狀態(tài)變量的特點(diǎn)第一,可知性，即各階段的狀態(tài)變量的取值能直接或間接的確定；第二，能夠 確切的描述過(guò)程的演變且滿足無(wú)后效性.7、簡(jiǎn)述動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型要點(diǎn)(ppt第十章18論述題增加階段和階段變量)（1）分析題意，識(shí)別問(wèn)題的多階段特性，按時(shí)間或空間的先后順序適當(dāng)劃 分為滿足遞推關(guān)系的若干階段，對(duì)分時(shí)序的靜態(tài)問(wèn)題要認(rèn)為賦予“時(shí)段”概念;（2）正確選擇狀態(tài)變量，狀態(tài)變量應(yīng)具備兩個(gè)特征：第一，可知性，即各 階段的狀態(tài)變量的取值能直接或間接的確

9、定；第二，能夠確切的描述過(guò)程的演變 且滿足無(wú)后效性；（3）根據(jù)狀態(tài)變量和決策變量的含義，正確寫出狀態(tài)轉(zhuǎn)移方程；（4）根據(jù)題意明確過(guò)程指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)以及第k階段指標(biāo)函數(shù)的 含義，并正確列出基本方程。這其賣也是個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題.下面用地序解法求廓它= 階段變量虹第k次裝載第k種物品（k=,2n） 狀態(tài)變量時(shí) 第k次.裝載時(shí)背包還可以裝載的S： 決策變量*二%：第k次裝救物品的拌數(shù)；決策允許集合；DJ*） = 瓦|g X5k/wk，林為整數(shù) i狀態(tài)轉(zhuǎn)移方屋：h|- srWA: 階段:指標(biāo)：Vk= c；最優(yōu)過(guò)舞指標(biāo)函蜿（氣*第k到n階段容許裝人物品的最大使 用價(jià)值遞推方程；再（金）=如昭%形垣l

10、（如-am 心風(fēng)坊1（如叫矽： x斗&）終端條件：史偃盤=0匚3、簡(jiǎn)述著名的哥尼斯堡七橋難題及答案這個(gè)問(wèn)題可以用整數(shù)加劃模型來(lái)描述：詵Vj 為第f神物品裝入背包的件數(shù)， 泊，背包中物品的總價(jià)值為隊(duì)則, M瞇2 = 杠沔+%品叫&+甜杰戶s.t.0且為整數(shù)（i=l,2】，n） 河上有7座橋，將河中的兩個(gè)島和河岸連結(jié)，如圖1所示。一個(gè)散步者能否 一次走遍7座橋，而且每座橋只許通過(guò)一次，最后仍回到起始地點(diǎn)。這就是七橋 問(wèn)題，一個(gè)著名的圖論問(wèn)題。歐拉證明了這樣的走法不存在。歐拉是這樣解決問(wèn)題的：既然陸地是橋梁的 連接地點(diǎn)，不妨把圖中被河隔開的陸地看成A、B、C、D4個(gè)點(diǎn)，7座橋表示成7 條連接這4個(gè)點(diǎn)

11、的線，如圖2所示。于是“七橋問(wèn)題”就等價(jià)于圖3中所畫圖形的一筆畫問(wèn)題了。每個(gè)點(diǎn)如果有 進(jìn)去的邊就必須有出來(lái)的邊，從而每個(gè)點(diǎn)連接的邊數(shù)必須有偶數(shù)個(gè)才能完成一筆 畫。圖3的每個(gè)點(diǎn)都連接著奇數(shù)條邊，因此不可能一筆畫出，這就說(shuō)明不存在一 次走遍7座橋，而每座橋只許通過(guò)一次的走法。8、簡(jiǎn)述樹定義及性質(zhì)樹:連通且不含圈的無(wú)向圖稱為樹。性質(zhì)：（1）樹無(wú)圈，m=n-1.（2）樹連通，m=n-1.（3）樹無(wú)圈，但每加一條新 邊，則可得到惟一一個(gè)圈.（4）樹連通，但任舍一條邊，圖就不連通.（5）樹中任 意兩點(diǎn)之間有惟一一條鏈相連.16、簡(jiǎn)述求最小生成樹的方法（1）避圈法：將圖中的邊按權(quán)由小到大排序；按排序由小到大

12、選定n-1 條邊為止，選擇時(shí)每選一條邊應(yīng)避免和已選的邊構(gòu)成圈，且所選邊是未選邊中的 最小權(quán)邊。（2）破圈法：在給定的賦權(quán)的連通圖上任選一個(gè)圈；在所找的圈中去掉一 個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其 中一條）；如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成 樹，否則返回第1步。18、簡(jiǎn)述決策按環(huán)境分類（分為哪幾種）（p389）確定型決策：在決策環(huán)境完全確定的條件下進(jìn)行不確定型決策：在決策環(huán)境不確定的條件下進(jìn)行，決策者對(duì)個(gè)自然狀態(tài)發(fā)生 的概率一無(wú)所知風(fēng)險(xiǎn)型決策問(wèn)題：在決策環(huán)境不確定的條件下進(jìn)行，決策者對(duì)各自然狀態(tài)發(fā) 生的概率可以預(yù)先估計(jì)或計(jì)算出來(lái)非

13、程序化決策:13、簡(jiǎn)述不確定型決策的決策方法（決策準(zhǔn)則）（p389）（1）最大最小準(zhǔn)則（悲觀準(zhǔn)則），決策者從最不利的角度去考慮問(wèn)題；（2）最大最大準(zhǔn)則（樂(lè)觀準(zhǔn)則），決策者從最有利的角度去考慮問(wèn)題；（3）等可能性準(zhǔn)則，決策者把各自然狀態(tài)發(fā)生的機(jī)會(huì)看成是等可能的；（4）樂(lè)觀系數(shù)準(zhǔn)則（折衷準(zhǔn)則），決策者取樂(lè)觀準(zhǔn)則和悲觀準(zhǔn)則的折衷；（5）后悔值準(zhǔn)則（沙萬(wàn)奇準(zhǔn)則），決策者從后悔的角度去考慮問(wèn)題概率修正中要用到兩個(gè)公式;1 全概率公式：14、簡(jiǎn)述層次分析法的基本步驟（ppt 第16章31）戶伏）工2刊。沖NE孩（. 2、貝分斯公式：典腳滬且”JI-1,2，* P（I ）明確問(wèn)題，提出總目標(biāo)2.繪 制層次結(jié)

14、構(gòu)圖3.標(biāo)度及兩兩比較 矩陣4.求各因素權(quán)重的過(guò)程5.兩兩 比較矩陣一致性檢驗(yàn)6.利用權(quán)數(shù) 或特征向量求出各方案的優(yōu)劣次序.EVPI = EVwPI - EVwoPI1、結(jié)合我國(guó)企業(yè)發(fā)展中面臨的一實(shí)際問(wèn)題，簡(jiǎn)要論述運(yùn)籌學(xué)在我國(guó)企業(yè)管理優(yōu)化中的重要應(yīng)用及作用。答：運(yùn)籌學(xué)在企業(yè)管理優(yōu)化領(lǐng)域的主要應(yīng)用有：生產(chǎn)計(jì)劃。如一家重型制造廠用線性規(guī)劃及整數(shù)規(guī)劃安排生產(chǎn)計(jì)劃，節(jié)約 了 10%的生產(chǎn)費(fèi)用。市場(chǎng)營(yíng)銷。在廣告預(yù)算和廣告媒介的選擇、競(jìng)爭(zhēng)性定價(jià)、新產(chǎn)品開發(fā)、銷 售計(jì)劃、市場(chǎng)競(jìng)爭(zhēng)策略的制定等方面，運(yùn)籌學(xué)也大展身手。美國(guó)杜邦公司在五十 年代起就非常重視將運(yùn)籌學(xué)用于研究如何做好廣告工作、產(chǎn)品定價(jià)，通用公司也 運(yùn)

15、用運(yùn)籌學(xué)方法進(jìn)行市場(chǎng)模擬研究。庫(kù)存管理。運(yùn)籌學(xué)中的存貯論可以應(yīng)用于物資庫(kù)存量的管理，以確定倉(cāng)庫(kù) 的合理容量，以及確定適當(dāng)?shù)膸?kù)存方式和庫(kù)存量。運(yùn)輸問(wèn)題。運(yùn)用運(yùn)籌學(xué)，可以確定最小成本的運(yùn)輸路線、物資的調(diào)撥、運(yùn) 輸工具的調(diào)度，以及新建廠址的選擇等等。人事管理。對(duì)人員的需求和招聘情況的預(yù)測(cè)；人力資源的開發(fā)，如對(duì)人才 的教育和培訓(xùn)，人才評(píng)價(jià)體系、薪酬體系的確定等，都可以運(yùn)用運(yùn)籌學(xué)方法。財(cái)務(wù)會(huì)計(jì)。運(yùn)籌學(xué)解決企業(yè)如何最有效的利用資金資源的問(wèn)題。其涉及到 投資決策分析、成本核算分析、證券管理等。在投資決策分析中，企業(yè)如何利用 剩余資金，如何投資往往有多種方案。而運(yùn)籌學(xué)的作用就是要要對(duì)這些不同的投 資方案進(jìn)行決

16、策，以確定最優(yōu)的方案，使得企業(yè)的收益最大。通常是利用線性規(guī) 劃模型、決策論來(lái)進(jìn)行判斷。聯(lián)合航空公司滿足乘客需求前提下，以最低成本進(jìn)行訂票及安排 機(jī)場(chǎng)工作班次1-2/1986600萬(wàn)標(biāo)準(zhǔn)品牌公司控制成品庫(kù)存（制定最優(yōu)再訂購(gòu)點(diǎn)和訂購(gòu)量，確保 安全庫(kù)存）12/1981380萬(wàn)Delta航空公司進(jìn)行上千個(gè)國(guó)內(nèi)航線的飛機(jī)優(yōu)化配置來(lái)最大化利 潤(rùn)1-2/19941億寶潔公司重新設(shè)計(jì)北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快 了市場(chǎng)進(jìn)入速度1-2/19972億2、根據(jù)您所學(xué)的運(yùn)籌學(xué)及其它學(xué)科知識(shí)，談?wù)勀鷮?duì)“運(yùn)籌帷幄，決勝千里” 的理解；語(yǔ)出史記 高祖本紀(jì)，意思是說(shuō)，張良坐在軍帳中運(yùn)用計(jì)謀，就能決定千 里之外戰(zhàn)斗的勝利

17、，這說(shuō)明張良心計(jì)多，善用腦，善用兵，后來(lái)人們就用“運(yùn)籌 帷幄”表示善于策劃用兵。學(xué)習(xí)中，我們應(yīng)當(dāng)努力學(xué)習(xí)運(yùn)籌學(xué)的理論知識(shí)，并將理論知識(shí)付諸實(shí)踐，在 學(xué)習(xí)其他學(xué)科時(shí)，運(yùn)用運(yùn)籌學(xué)的知識(shí)，比如在寫畢業(yè)論文時(shí)，運(yùn)用運(yùn)籌學(xué)的知識(shí)， 豐富論文內(nèi)容，為論文增加支撐理論。生活中，我們面對(duì)任何問(wèn)題都要仔細(xì)思考，運(yùn)用運(yùn)籌學(xué)的知識(shí)，更好地解決 問(wèn)題，而現(xiàn)在網(wǎng)絡(luò)及通訊工具的不斷發(fā)展，讓我們遠(yuǎn)在千里之外也可以解決問(wèn)題， 如：越來(lái)越多的跨國(guó)公司，不僅僅是局限于面對(duì)面的交談，很多網(wǎng)絡(luò)會(huì)議或電話 會(huì)議，讓解決問(wèn)題更加方便迅速。在企業(yè)管理中，生產(chǎn)計(jì)劃、市場(chǎng)營(yíng)銷、庫(kù)存管理、人事資源、運(yùn)輸問(wèn)題等。3、請(qǐng)論述如何把你所學(xué)的運(yùn)籌學(xué)的知

18、識(shí)應(yīng)用到今后的管理實(shí)踐中去；答：（1）對(duì)運(yùn)籌學(xué)的知識(shí)體系了若指掌。（2）處理管理實(shí)踐的問(wèn)題時(shí)，有意 識(shí)的使用運(yùn)籌學(xué)的知識(shí)體系和方法來(lái)解決。（3）需要有很強(qiáng)的歸納總結(jié)能力，把 在實(shí)踐中遇到的問(wèn)題，轉(zhuǎn)化為運(yùn)籌學(xué)書上的問(wèn)題來(lái)解決，如：背包問(wèn)題、七橋問(wèn) 題。以上三者缺一不可，遇到問(wèn)題，首先想到解決該問(wèn)題需要哪些資源，從哪里 可以獲得這些資源;其次考慮再獲得資源后，如何使這些資源得到最合理的利用， 使其產(chǎn)生最大效益。另外，強(qiáng)化管理，不斷進(jìn)行管理刨新已成為企業(yè)在競(jìng)爭(zhēng)中制 勝的根本保證。作為企業(yè)的管理者，把握并運(yùn)用好運(yùn)籌學(xué)的理念定會(huì)取得“運(yùn)籌 帷幄之中，決勝千里之外”之功效。4、請(qǐng)簡(jiǎn)要列舉（至少3）我國(guó)古代

19、樸素的運(yùn)籌學(xué)思想，并論述其間的運(yùn)籌學(xué)原理。（4個(gè)）答：（1）孫子兵法與運(yùn)籌學(xué)思想。孫子兵法在表達(dá)軍事思想的同時(shí)，也 蘊(yùn)藏著豐富的運(yùn)籌學(xué)思想 軍事運(yùn)籌學(xué)。孫武在孫子兵法中靈活運(yùn)用整 體性原則研究軍事問(wèn)題，采用定量分析方法謀劃戰(zhàn)爭(zhēng)，運(yùn)用優(yōu)化原則進(jìn)行科學(xué)決 策。（2）田忌賽馬。戰(zhàn)國(guó)時(shí)期的“田忌賽馬”是運(yùn)籌思想的一次完美應(yīng)用。整 個(gè)賽馬過(guò)程中，孫臏巧妙地運(yùn)用了一種科學(xué)合理的方法一一博弈論。博弈論是運(yùn) 籌學(xué)的一個(gè)分支，是指二人在平等的對(duì)局中各自利用對(duì)方的策略變換自己的對(duì)抗 策略，達(dá)到取勝的目的。通過(guò)博弈論的思想，孫臏指出用本方的下馬對(duì)齊王的上 馬，用本方的上馬對(duì)齊王的中馬，用本方的中馬對(duì)齊王的下馬。最終

20、以一負(fù)兩勝 取勝。孫臏成功地將本方劣勢(shì)轉(zhuǎn)為優(yōu)勢(shì)，贏得了比賽。（3）圍魏救趙。魏國(guó)攻打趙國(guó)，趙國(guó)求救于齊。孫臏指出應(yīng)趁魏國(guó)國(guó)內(nèi)兵 力空虛之際，發(fā)兵直取魏都大梁，迫使偽軍棄趙回救。最終這一戰(zhàn)略取得了勝利。 其中的戰(zhàn)略思想，妙在善于調(diào)動(dòng)第二年。調(diào)動(dòng)敵人的要訣，在于“攻其所必救”。 這充分體現(xiàn)了如何策劃兵力，選擇最佳時(shí)間、地點(diǎn)，趨利避害，集中優(yōu)勢(shì)兵力以 弱克強(qiáng)的運(yùn)籌思想。（4）沈括運(yùn)軍糧：沈括曾經(jīng)從行軍中各類人員可以背負(fù)糧食的基本數(shù)據(jù) 出發(fā)，分析計(jì)算了后勤人員與作 戰(zhàn)兵士在不同行軍天數(shù)中的不同比例關(guān) 系，同時(shí)也分析計(jì)算了用各種牲畜運(yùn)糧與人力運(yùn)糧之間的利弊，最 后做出了從敵國(guó)就地征糧，保障前方供應(yīng)的重要

21、決策，從而減少了 后勤人員的比例，增強(qiáng)了前方作戰(zhàn)的兵力。這種軍事后勤問(wèn)題的分析計(jì)算是具有現(xiàn)代意義的運(yùn)籌思想的范例。（5）晉國(guó)公重建皇城的施工方案，體現(xiàn)了運(yùn)籌學(xué)的樸素斯思想。要使 重建工程的各個(gè)工序，在時(shí)間、空間上彼此協(xié)調(diào)，環(huán)環(huán)相扣，就需要運(yùn)用行 列式的相關(guān)知識(shí)，進(jìn)行精確計(jì)算。影子價(jià)格:當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值增加的數(shù) 量。（影增）對(duì)偶價(jià)格:當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值改進(jìn)的數(shù) 量。靈敏度分析:對(duì)系統(tǒng)或事物因周圍條件變化顯示出來(lái)的敏感程度分析。4.0-1規(guī)劃:所有決策變量只能取0或1兩個(gè)整數(shù)的整數(shù)線性規(guī)劃。分支定界法:分枝定界法是先求解整數(shù)規(guī)劃的線

22、性規(guī)劃問(wèn)題。如果其最優(yōu)解不 符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線 性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問(wèn)題， 不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。生成子圖:給定一個(gè)無(wú)向圖G=（V,E），保留G的所有點(diǎn)，而刪掉部分G的邊或 者說(shuō)保留一部分G的邊，所獲得圖G，稱之為G的生成子圖。松弛問(wèn)題:不考慮整數(shù)約束條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn) 題。歐拉回路:圖G的一個(gè)回路，若它恰通過(guò)G中每條邊一次，則稱該回路為歐拉回 路。樣本信息:研究中實(shí)際觀測(cè)或調(diào)查的一部分個(gè)體的信息。最小生成樹:在一個(gè)賦權(quán)的連通的無(wú)向圖G找

23、出一個(gè)生成樹，并使得這個(gè)生成 樹的所有邊的權(quán)數(shù)之和最小。目標(biāo)約束:在引入了目標(biāo)值和正、負(fù)偏差變量后，可以將原目標(biāo)函數(shù)加上負(fù)偏 差變量，減去正偏差變量，并且等于目標(biāo)值，這樣形成一個(gè)新的函數(shù)方程，把它 作為一個(gè)新的約束條件，加入到原問(wèn)題中去，稱這種新的約束條件為目標(biāo)約束。偏差變:指目標(biāo)規(guī)劃中實(shí)現(xiàn)值與目標(biāo)值之間的差異。其中實(shí)現(xiàn)值超過(guò)目標(biāo)值 的部分記為d+,實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分記為d-d+, d-這樣的變量稱為偏差 變量。狀態(tài)變量：描述各階段狀態(tài)的變量稱為狀態(tài)變量?；究尚薪猓簼M足非負(fù)條件的基本解叫基本可行解。后驗(yàn)概率：利用樣本情報(bào)對(duì)先驗(yàn)概率修正后得到的概率。定性分析：借助決策者的知識(shí)，經(jīng)驗(yàn)，分析

24、和判斷能力等進(jìn)行決策的方法。定量分析：量化決策問(wèn)題并建立數(shù)學(xué)模型進(jìn)行決策的方法。（基于事物的數(shù)據(jù) 和數(shù)量關(guān)系，建模、計(jì)算找出解決方案）狀態(tài)與狀態(tài)變量：狀態(tài)是指每個(gè)階段開始所處的自然狀況或客觀條件，而描 述過(guò)程狀態(tài)的變量就是狀態(tài)變量。能夠完全描述動(dòng)態(tài)系統(tǒng)時(shí)域行為的所含變量個(gè) 數(shù)最少的變量組稱為系統(tǒng)的狀態(tài)變量。運(yùn)籌學(xué)試題及答案卷)一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案，答案選錯(cuò)或未選者，該題不得 分。每小題1分，共10分)1 .線性規(guī)劃具有唯一最優(yōu)解是指最優(yōu)表中存在常數(shù)項(xiàng)為零最優(yōu)表中非基變量檢驗(yàn)數(shù)全部非零最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零D可行解集合有界設(shè)線性規(guī)劃的約束條件為電十工

25、金十起二3* 2天+ 2x2 + x牛二 4圭,，財(cái) 0則基本可行解為A . (0, 0, 4, 3)B . (3, 4, 0, 0)C . (2, 0, 1, 0)D . (3, 0, 4, 0)min Z = 3工+ 42 ,xx + x2 + 此 C,Y 0,對(duì)任意可行解X和丫，存在關(guān)系A(chǔ) . Z W B . Z = WC . ZWD . ZW 5 .有6個(gè)產(chǎn)地4個(gè)銷地的平衡運(yùn)輸問(wèn)題模型具有特征有10個(gè)變量24個(gè)約束有24個(gè)變量10個(gè)約束C .有24個(gè)變量9個(gè)約束D .有9個(gè)基變量10個(gè)非基變量下例錯(cuò)誤的說(shuō)法是標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最大值標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最小值標(biāo)準(zhǔn)型的常數(shù)項(xiàng)非正標(biāo)準(zhǔn)型的

26、變量一定要非負(fù)m+n-1個(gè)變量構(gòu)成一組基變量的充要條件是A.m + n-1個(gè)變量恰好構(gòu)成一個(gè)閉回路B . m+n - 1個(gè)變量不包含任何閉回路C . m+n - 1個(gè)變量中部分變量構(gòu)成一個(gè)閉回路D . m + n - 1個(gè)變量對(duì)應(yīng)的系數(shù)列向量線性相關(guān)互為對(duì)偶的兩個(gè)線性規(guī)劃問(wèn)題的解存在關(guān)系原問(wèn)題無(wú)可行解，對(duì)偶問(wèn)題也無(wú)可行解對(duì)偶問(wèn)題有可行解，原問(wèn)題可能無(wú)可行解C .若最優(yōu)解存在，則最優(yōu)解相同D一個(gè)問(wèn)題無(wú)可行解，則另一個(gè)問(wèn)題具有無(wú)界解有m個(gè)產(chǎn)地n個(gè)銷地的平衡運(yùn)輸問(wèn)題模型具有特征A .有mn個(gè)變量m+n個(gè)約束 m + n-1個(gè)基變量B .有m+n個(gè)變量mn個(gè)約束有mn個(gè)變量m + n - 1約束D .

27、有m + n-1個(gè)基變量，mn-m-n-1個(gè)非基變量10 .要求不超過(guò)第一目標(biāo)值、恰好完成第二目標(biāo)值，目標(biāo)函數(shù)是min Z - p d + + p (d - + d +) TOC o 1-5 h z A .，122 7min Z - p d + + p (d d +) B .1 12 22min Z p d - + p (d d +)C .1 12 22min Z p d - + p (d - + d +)D .1 1222二、判斷題(你認(rèn)為下列命題是否正確，對(duì)正確的打“寸；錯(cuò)誤的打“X”。每小題1分，共15分)若線性規(guī)劃無(wú)最優(yōu)解則其可行域無(wú)界X基本解為空x凡基本解一定是可行解X同19x線性規(guī)

28、劃的最優(yōu)解一定是基本最優(yōu)解X可能為負(fù)x可行解集非空時(shí),則在極點(diǎn)上至少有一點(diǎn)達(dá)到最優(yōu)值X可能無(wú)窮x互為對(duì)偶問(wèn)題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解 V運(yùn)輸問(wèn)題效率表中某一行元素分別乘以一個(gè)常數(shù),則最優(yōu)解不變X要求不超過(guò)目標(biāo)值的目標(biāo)函數(shù)是皿成 2求最小值問(wèn)題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界基本解對(duì)應(yīng)的基是可行基X當(dāng)非負(fù)時(shí)為基本可行解，對(duì)應(yīng)的基叫可行基對(duì)偶問(wèn)題有可行解，則原問(wèn)題也有可行解X原問(wèn)題具有無(wú)界解，則對(duì)偶問(wèn)題不可行m+n-1個(gè)變量構(gòu)成基變量組的充要條件是它們不包含閉回路目標(biāo)約束含有偏差變量整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到X匈牙利法是對(duì)指派問(wèn)題求最小值的一種求解方法

29、三、填空題（每小題1分，共10分）.有5個(gè)產(chǎn)地5個(gè)銷地的平衡運(yùn)輸問(wèn)題，則它的基變量有（9 ）個(gè).已知最優(yōu)基ri 2_B =3 7L ，Cb=（3, 6）,則對(duì)偶問(wèn)題的最優(yōu)解是（）.已知線性規(guī)劃求極小值，用對(duì)偶單純形法求解時(shí)，初始表中應(yīng)滿足條件（對(duì)偶問(wèn)題可行.非基變量的系數(shù)c變化后，最優(yōu)表中（）發(fā)生變化.設(shè)運(yùn)輸問(wèn)題求最大值，則當(dāng)所有檢驗(yàn)數(shù)（）時(shí)得到最優(yōu)解。ma Z - 一匯1 + -q-i +曲 0.線性規(guī)劃1212121 2的最優(yōu)解是（0，6）,它的第1、2個(gè)約束中松馳變量（&）二（）.在資源優(yōu)化的線性規(guī)劃問(wèn)題中，某資源有剩余，則該資源影子價(jià)格等于（）max Z =5心.將目標(biāo)函數(shù)12轉(zhuǎn)化為求

30、極小值是（）X + 5 X 一 上 X = 5.來(lái)源行1 6 36 43的高莫雷方程是（）.運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)4的經(jīng)濟(jì)含義是（）四、求解下列各題（共50分）.已知線性規(guī)劃（15分）max Z = 3x + 4 x + 5 xx + 2 x - x 102x 一 x + 3x 0,2 j = 13,2,31 j（1）求原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解；（2）求最優(yōu)解不變時(shí)的變化范圍求下列指派問(wèn)題（min）的最優(yōu)解（10分）5612 158520 189 109 69 756求解下列目標(biāo)規(guī)劃（15分） TOC o 1-5 h z min z = p (d + + d+) + P d - + Pd - 134

31、2 13 211a rx + x + d d + = 401211x + x + d - - d + = 601222 0(i = 1,L ,4) HYPERLINK l bookmark232 o Current Document V12 i i39 .求解下列運(yùn)輸問(wèn)題（min）（10分）_ 854 -40C =14181390_ 92101108010060五、應(yīng)用題（15分）40 .某公司要將一批貨從三個(gè)產(chǎn)地運(yùn)到四個(gè)銷地，有關(guān)數(shù)據(jù)如下表所示。銷地產(chǎn)地B1B2B3B4供應(yīng)量A1737956A22651140A3642575現(xiàn)要求制定調(diào)運(yùn)計(jì)劃，且依次滿足：（1）b3的供應(yīng)量不低于需要量；（2

32、）其余銷地的供應(yīng)量不低于85% ；（3）氣給B3的供應(yīng)量不低于200 ；（4）A2盡可能少給B1 ；（5）銷地B2、B3的供應(yīng)量盡可能保持平衡。（6）使總運(yùn)費(fèi)最小。試建立該問(wèn)題的目標(biāo)規(guī)劃數(shù)學(xué)模型。運(yùn)籌學(xué)陌卷）一、單項(xiàng)選擇題（從下列各題四個(gè)備選答案中選出一個(gè)正確答案，答案選錯(cuò)或未選者，該題不得 分。每小題1分，共10分）.線性規(guī)劃最優(yōu)解不唯一是指（）ff r Ofi = 1 -A可行解集合無(wú)界B .存在某個(gè)檢驗(yàn)數(shù)0且此一C可行解集合是空集D.最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)非零m雙 1=4電+工4匯+3舟 丈24,她占10,工. 姻占，則（ ）A.無(wú)可行解 B.有唯一最優(yōu)解 C.有無(wú)界解 D.有多重

33、解.原問(wèn)題有5個(gè)變量3個(gè)約束，其對(duì)偶問(wèn)題（）A.有3個(gè)變量5個(gè)約束 B.有5個(gè)變量3個(gè)約束C.有5個(gè)變量5個(gè)約束 D.有3個(gè)變量3個(gè)約束.有3個(gè)產(chǎn)地4個(gè)銷地的平衡運(yùn)輸問(wèn)題模型具有特征（）A.有7個(gè)變量 B .有12個(gè)約束C .有6約束 D .有6個(gè)基變量.線性規(guī)劃可行域的頂點(diǎn)一定是（）A.基本可行解 B.非基本解 C.非可行解 D最優(yōu)解6.X是線性規(guī)劃的基本可行解則有（）A . X中的基變量非零，非基變量為零 B . X不一定滿足約束條件C.X中的基變量非負(fù)，非基變量為零 D.X是最優(yōu)解7 .互為對(duì)偶的兩個(gè)問(wèn)題存在關(guān)系（）A .原問(wèn)題無(wú)可行解，對(duì)偶問(wèn)題也無(wú)可行解B .對(duì)偶問(wèn)題有可行解，原問(wèn)題也

34、有可行解C .原問(wèn)題有最優(yōu)解解，對(duì)偶問(wèn)題可能沒(méi)有最優(yōu)解D .原問(wèn)題無(wú)界解，對(duì)偶問(wèn)題無(wú)可行解8.線性規(guī)劃的約束條件為則基本解為（ ）A . (0, 2, 3, 2)B . (3, 0, - 1, 0)C.(0, 0, 6, 5)D.(2, 0, 1, 2)9 .要求不低于目標(biāo)值，其目標(biāo)函數(shù)是（）min Z - dB .c Z = dC.10. H是關(guān)于可行流f的一條增廣鏈，則在H上有（）A.對(duì)任意S）g知斗B.對(duì)任意饑）快-駕咬C.對(duì)任意（技）*有而嚀D.對(duì)任意（）叫，有產(chǎn)二、判斷題（你認(rèn)為下列命題是否正確，對(duì)正確的打“W ；錯(cuò)誤的打“X”。每小題1分，共15分）線性規(guī)劃的最優(yōu)解是基本解x.可行

35、解是基本解x.運(yùn)輸問(wèn)題不一定存在最優(yōu)解x.一對(duì)正負(fù)偏差變量至少一個(gè)等于零x.人工變量出基后還可能再進(jìn)基x.將指派問(wèn)題效率表中的每一元素同時(shí)減去一個(gè)數(shù)后最優(yōu)解不變.求極大值的目標(biāo)值是各分枝的上界.若原問(wèn)題具有m個(gè)約束，則它的對(duì)偶問(wèn)題具有m個(gè)變量.原問(wèn)題求最大值，第i個(gè)約束是倉(cāng)”約束，則第i個(gè)對(duì)偶變量*Q的線性規(guī)劃中，設(shè)1 00 1，它的全部基是（.運(yùn)輸問(wèn)題中m+n - 1個(gè)變量構(gòu)成基變量的充要條件是（）.對(duì)偶變量的最優(yōu)解就是（）價(jià)格.來(lái)源行23 33 43的高莫雷方程是（）.約束條件的常數(shù)項(xiàng)br變化后，最優(yōu)表中（）發(fā)生變化.運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)彳與對(duì)偶變量U、匕之間存在關(guān)系（）33.線性規(guī)劃max

36、Z = - x1+ x ,2 x + x82荷十2林十工？ 1037 .求解下列目標(biāo)規(guī)劃（15分）氣+如+4 一苴=12再十2茍十d 刁;=42 x2+d -238 .求解下列指派問(wèn)題（min）（1。分） TOC o 1-5 h z 3923715 6 6947103254219624639 .求下圖七到匕的最短路及最短路長(zhǎng)（10分）五、應(yīng)用題（15分）40 .某廠組裝三種產(chǎn)品，有關(guān)數(shù)據(jù)如下表所示。產(chǎn)品單件組裝工時(shí)日銷量（件）產(chǎn)值（元/件）日裝配能力A1.17040B1.36060300C1.58080要求確定兩種產(chǎn)品的日生產(chǎn)計(jì)劃，并滿足：（1）工廠希望裝配線盡量不超負(fù)荷生產(chǎn)；（2）每日剩余產(chǎn)

37、品盡可能少；（3）日產(chǎn)值盡可能達(dá)到6000元。試建立該問(wèn)題的目標(biāo)規(guī)劃數(shù)學(xué)模型。運(yùn)籌學(xué)（A卷）試題參考答案一、單選題（每小題1分，共10分）B2.C3. A 4.D5.B6.C二、判斷題（每小題1分，共15分）x 12. x 13. x14.x15.寸21.寸 22.寸 23.寸 24. x 25.寸三、填空題（每小題1分，共10分）26.（9）27.（3,0）28.（對(duì)偶問(wèn)題可行）31. （0,2）32. （0）7.B8.B9.A10.A16.x17.寸18.寸19.x20. x29.（午30.（小于等于0）33 (min Z = -x + 5x )(s x x = J或 s 5 x 5 x

38、=4) 34 1 6 3 6 43133叫增加一個(gè)單位總運(yùn)費(fèi)增加氣四、計(jì)算題（共50分）36.解：（1）化標(biāo)準(zhǔn)型2分max Z = 3x + 4 x + 5 x123.CA CXx + 2 x - x + x = 10 0, j = 1,2,L ,5（2）單純形法5分CBXBx1x2x3x4x5b4x21100.60.275x31010.20.44C-z-600-3.4-2.848最優(yōu)解 X=（0, 7, 4） ； Z = 48（2分）（4）對(duì)偶問(wèn)題的最優(yōu)解Y =（3.4,2.8） （2 分）Ac2-17/2,C G （一8,9）, 則1c -1（4分）F13O-F03O-0386028&232022204101400137.解：（5分）