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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、金十起二3* 2天+ 2x2 + x牛二 4圭,，財 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,對任意可行解X和丫，存在關(guān)系A(chǔ) . Z W B . Z = WC . ZWD . ZW 5 .有6個產(chǎn)地4個銷地的平衡運(yùn)輸問題模型具有特征有10個變量24個約束有24個變量10個約束C .有24個變量9個約束D .有9個基變量10個非基變量下例錯誤的說法是標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最大值標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最小值標(biāo)準(zhǔn)型的常數(shù)項非正標(biāo)準(zhǔn)型的

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

27、有m + n-1個基變量，mn-m-n-1個非基變量10 .要求不超過第一目標(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)為下列命題是否正確，對正確的打“寸；錯誤的打“X”。每小題1分，共15分)若線性規(guī)劃無最優(yōu)解則其可行域無界X基本解為空x凡基本解一定是可行解X同19x線性規(guī)

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

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

30、極小值是（）X + 5 X 一 上 X = 5.來源行1 6 36 43的高莫雷方程是（）.運(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）求原問題和對偶問題的最優(yōu)解；（2）求最優(yōu)解不變時的變化范圍求下列指派問題（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)輸問題（min）（10分）_ 854 -40C =14181390_ 92101108010060五、應(yīng)用題（15分）40 .某公司要將一批貨從三個產(chǎn)地運(yùn)到四個銷地，有關(guān)數(shù)據(jù)如下表所示。銷地產(chǎn)地B1B2B3B4供應(yīng)量A1737956A22651140A3642575現(xiàn)要求制定調(diào)運(yùn)計劃，且依次滿足：（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)最小。試建立該問題的目標(biāo)規(guī)劃數(shù)學(xué)模型。運(yùn)籌學(xué)陌卷）一、單項選擇題（從下列各題四個備選答案中選出一個正確答案，答案選錯或未選者，該題不得 分。每小題1分，共10分）.線性規(guī)劃最優(yōu)解不唯一是指（）ff r Ofi = 1 -A可行解集合無界B .存在某個檢驗數(shù)0且此一C可行解集合是空集D.最優(yōu)表中存在非基變量的檢驗數(shù)非零m雙 1=4電+工4匯+3舟 丈24,她占10,工. 姻占，則（ ）A.無可行解 B.有唯一最優(yōu)解 C.有無界解 D.有多重

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

34、有可行解C .原問題有最優(yōu)解解，對偶問題可能沒有最優(yōu)解D .原問題無界解，對偶問題無可行解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.對任意S）g知斗B.對任意饑）快-駕咬C.對任意（技）*有而嚀D.對任意（）叫，有產(chǎn)二、判斷題（你認(rèn)為下列命題是否正確，對正確的打“W ；錯誤的打“X”。每小題1分，共15分）線性規(guī)劃的最優(yōu)解是基本解x.可行

35、解是基本解x.運(yùn)輸問題不一定存在最優(yōu)解x.一對正負(fù)偏差變量至少一個等于零x.人工變量出基后還可能再進(jìn)基x.將指派問題效率表中的每一元素同時減去一個數(shù)后最優(yōu)解不變.求極大值的目標(biāo)值是各分枝的上界.若原問題具有m個約束，則它的對偶問題具有m個變量.原問題求最大值，第i個約束是倉”約束，則第i個對偶變量*Q的線性規(guī)劃中，設(shè)1 00 1，它的全部基是（.運(yùn)輸問題中m+n - 1個變量構(gòu)成基變量的充要條件是（）.對偶變量的最優(yōu)解就是（）價格.來源行23 33 43的高莫雷方程是（）.約束條件的常數(shù)項br變化后，最優(yōu)表中（）發(fā)生變化.運(yùn)輸問題的檢驗數(shù)彳與對偶變量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 .求解下列指派問題（min）（1。分） TOC o 1-5 h z 3923715 6 6947103254219624639 .求下圖七到匕的最短路及最短路長（10分）五、應(yīng)用題（15分）40 .某廠組裝三種產(chǎn)品，有關(guān)數(shù)據(jù)如下表所示。產(chǎn)品單件組裝工時日銷量（件）產(chǎn)值（元/件）日裝配能力A1.17040B1.36060300C1.58080要求確定兩種產(chǎn)品的日生產(chǎn)計劃，并滿足：（1）工廠希望裝配線盡量不超負(fù)荷生產(chǎn)；（2）每日剩余產(chǎn)

37、品盡可能少；（3）日產(chǎn)值盡可能達(dá)到6000元。試建立該問題的目標(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.（對偶問題可行）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叫增加一個單位總運(yùn)費(fèi)增加氣四、計算題（共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）對偶問題的最優(yōu)解Y =（3.4,2.8） （2 分）Ac2-17/2,C G （一8,9）, 則1c -1（4分）F13O-F03O-0386028&232022204101400137.解：（5分）