運籌學期末復習題及答案

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

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

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

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

5、表上給出 m+n-1 個數(shù)字格，其相對應的調(diào)運量的值即為基變量的值。（2） 求各非基變量的檢驗數(shù)。（3） 用閉回路法來判別問題是否達到最優(yōu)解。如已是最優(yōu)解則停止計算， 否則繼續(xù)下一步。（4） 用閉回路法進行基變換，確定入基變量和出基變量，找出新的基本可行解。在表上用閉回路法調(diào)整。11、簡述指派問題的標準形式及數(shù)學模型（ ppt 或書上 p179）設n 個人被分配去做 n 件工作， 規(guī)定每個人只做一件工作， 每件工作只有一個人去做。 已知第 i 個人去做第 j 件工作的效率 （時間或費用） 為cij ( i =1.2,n; j =1.2,n) 并假設 cij0。問應如何分配才能使總效率 （時間或

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

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

8、同重量和不同價值的物品， 在攜帶物品總重量限制的情況下， 決定這 n種物品中每一種物品多少數(shù)量裝入背包內(nèi)， 使得裝入背包物品的總價值最大。4、建立動態(tài)規(guī)劃模型時，應定義狀態(tài)變量，請說明狀態(tài)變量的特點第一, 可知性, 即各階段的狀態(tài)變量的取值能直接或間接的確定；第二, 能夠確切的描述過程的演變且滿足無后效性.7、簡述動態(tài)規(guī)劃數(shù)學模型要點（ppt 第十章 18 論述題增加階段和階段變量）（1） 分析題意，識別問題的多階段特性，按時間或空間的先后順序適當劃3、簡述著名的哥尼斯堡七橋難題及答案河上有 7 座橋，將河中的兩個島和河岸連結， 如圖 1 所示。一個散步者能否一次走遍 7 座橋，而且每座橋只許

9、通過一次， 最后仍回到起始地點。 這就是七橋問題，一個著名的圖論問題。acd分為滿足遞推關系的若干階段，對分時序的靜態(tài)問題要認為賦予“時段”概念；（2） 正確選擇狀態(tài)變量，狀態(tài)變量應具備兩個特征：第一，可知性，即各 階段的狀態(tài)變量的取值能直接或間接的確定； 第二，能夠確切的描述過程的演變且滿足無后效性；（3） 根據(jù)狀態(tài)變量和決策變量的含義，正確寫出狀態(tài)轉移方程；（4） 根據(jù)題意明確過程指標函數(shù)和最優(yōu)指標函數(shù)以及第k 階段指標函數(shù)的含義，并正確列出基本方程。b歐拉證明了這樣的走法不存在。 歐拉是這樣解決問題的： 既然陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地看成a、b、c、d4 個點， 7

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

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

12、決策環(huán)境不確定的條件下進行， 決策者對各自然狀態(tài)發(fā)生的概率可以預先估計或計算出來非程序化決策： 13、簡述不確定型決策的決策方法（決策準則） （ p389）（1） 最大最小準則（悲觀準則） ，決策者從最不利的角度去考慮問題；（2） 最大最大準則（樂觀準則） ，決策者從最有利的角度去考慮問題；（3） 等可能性準則，決策者把各自然狀態(tài)發(fā)生的機會看成是等可能的;（4） 樂觀系數(shù)準則 ( 折衷準則 ) ，決策者取樂觀準則和悲觀準則的折衷；（5） 后悔值準則（沙萬奇準則） ，決策者從后悔的角度去考慮問題14、簡述層次分析法的基本步驟 （ppt 第 16 章 31）1. 明確問題，提出總目標 2. 繪制層

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

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

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

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

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

18、幄之中，決勝千里之外”之功效。4、請簡要列舉（至少 3）我國古代樸素的運籌學思想，并論述其間的運籌學原理。（4 個）答：（1）孫子兵法與運籌學思想。 孫子兵法在表達軍事思想的同時，也蘊藏著豐富的運籌學思想 -軍事運籌學。 孫武在孫子兵法 中靈活運用整體性原則研究軍事問題， 采用定量分析方法謀劃戰(zhàn)爭， 運用優(yōu)化原則進行科學決策。（2） 田忌賽馬。戰(zhàn)國時期的“田忌賽馬”是運籌思想的一次完美應用。整 個賽馬過程中， 孫臏巧妙地運用了一種科學合理的方法博弈論。博弈論是運籌學的一個分支， 是指二人在平等的對局中各自利用對方的策略變換自己的對抗策略，達到取勝的目的。 通過博弈論的思想， 孫臏指出用本方的下

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

20、同 時 也 分 析 計 算 了 用各 種 牲 畜 運 糧 與人 力運 糧 之 間 的 利 弊， 最后 做出 了 從敵 國 就 地征 糧 ， 保障 前 方供 應的 重 要決 策， 從而 減少 了后 勤 人員的比例，增強了前方作戰(zhàn)的兵力。這種軍事后勤問題的分析計算是具有現(xiàn)代意義的運籌思想的范例。（5） ）晉國公重建皇城的施工方案，體現(xiàn)了運籌學的樸素斯思想。要使重建工程的各個工序，在時間、空間上彼此協(xié)調(diào)，環(huán)環(huán)相扣，就需要運用行列式的相關知識，進行精確計算。1. 影子價格 : 當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值增加的數(shù)量。（影增）2. 對偶價格 : 當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值改進的數(shù)量。3. 靈敏度分析 : 對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度分析。4.0-1 規(guī)劃: 所有決策變量只能取 0或 1兩個整數(shù)的整數(shù)線性規(guī)劃。5. 分支定界法 : 分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件， 則求出整數(shù)規(guī)劃的上下界， 用增加約束條件的辦法， 把相應的線性規(guī)劃的可行域分成子區(qū)域 （稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題， 不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。6. 生成子圖 : 給定一個無向圖 g=（ v,e），保留