管理運(yùn)籌學(xué)期末復(fù)習(xí)資料【韓伯棠】

1、運(yùn)籌學(xué)（Operational Research）復(fù)習(xí)資料第一章 緒論一、名詞解釋1.運(yùn)籌學(xué)：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。二、選擇題1.運(yùn)籌學(xué)的主要分支包括（ ABDE ）A圖論 B線性規(guī)劃 C非線性規(guī)劃 D整數(shù)規(guī)劃 E目標(biāo)規(guī)劃2. 最早運(yùn)用運(yùn)籌學(xué)理論的是（ A ）A . 二次世界大戰(zhàn)期間，英國(guó)軍事部門將運(yùn)籌學(xué)運(yùn)用到軍事戰(zhàn)略部署 B . 美國(guó)最早將運(yùn)籌學(xué)運(yùn)用到農(nóng)業(yè)和人口規(guī)劃問題上C . 二次世界大戰(zhàn)期間，英國(guó)政府將運(yùn)籌學(xué)運(yùn)用到政府制定計(jì)劃 D . 50年代，運(yùn)籌學(xué)運(yùn)用到研究人口，能源

2、，糧食，第三世界經(jīng)濟(jì)發(fā)展等問題上第二章 線性規(guī)劃的圖解法一、選擇題/填空題1.線性規(guī)劃標(biāo)準(zhǔn)式的特點(diǎn)： （1）目標(biāo)函數(shù)最大化（2）約束條件為等式（3 決策變量為非負(fù)（4 ) 右端常數(shù)項(xiàng)為非負(fù)2. 在一定范圍內(nèi)，約束條件右邊常數(shù)項(xiàng)增加一個(gè)單位： （1）如果對(duì)偶價(jià)格大于0，則其最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)，即求最大值時(shí)，最優(yōu)目標(biāo)函數(shù)值變得更大，求最小值時(shí)最優(yōu)目標(biāo)函數(shù)值變得更小。 （2）如果對(duì)偶價(jià)格小于0，則其最優(yōu)目標(biāo)函數(shù)值變壞，即求最大值時(shí)，最優(yōu)目標(biāo)函數(shù)值變小了；求最小值時(shí)，最優(yōu)目標(biāo)函數(shù)值變大了。 （3）如果對(duì)偶價(jià)格等于0，則其最優(yōu)目標(biāo)函數(shù)值不變。3.LP模型（線性規(guī)劃模型）三要素：（1）決策變量 （2）

3、約束條件 （3）目標(biāo)函數(shù)4. 數(shù)學(xué)模型中，“s·t”表示約束條件。5. 將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式時(shí)，“”的約束條件要在不等式左端加上松弛變量。6. 將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式時(shí)，“”的約束條件要在不等式左端減去剩余變量。7下列圖形中陰影部分構(gòu)成的集合是凸集的是 A 【解析】：如何判斷是凸集？ 凸集：兩點(diǎn)之間連線在圖內(nèi) 凹集：兩點(diǎn)之間連線在圖外8. 線性規(guī)劃問題有可行解且凸多邊形無界，這時(shí) C A沒有無界解 B 沒有可行解 C 有無界解 D 有有限最優(yōu)解9. 對(duì)于線性規(guī)劃問題，下列說法正確的是（ D ）A. 線性規(guī)劃問題可能沒有可行解 B. 在圖解法上，線性規(guī)劃問題的可行解區(qū)域都是“

4、凸”區(qū)域C. 線性規(guī)劃問題如有最優(yōu)解，則最優(yōu)解可在可行解區(qū)域頂點(diǎn)上到達(dá) D. 上述說法都正確第三章 線性規(guī)劃問題的計(jì)算機(jī)求解一、名詞解釋1.相差值：相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量，使得決策變量為正值。2.對(duì)偶價(jià)格（影子價(jià)格）：約束條件右端常數(shù)項(xiàng)增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量。二、選擇題/填空題/判斷題1.松弛變量：表示沒使用的資源或能力的變量。2.剩余變量：表示最低限約束的超過量。3.線性規(guī)劃問題解的情況：（1）如果某一個(gè)線性規(guī)劃問題有最優(yōu)解則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)最優(yōu)解（2）線性規(guī)劃存在有無窮多個(gè)最優(yōu)解的情況。（3）線性規(guī)劃存在無界解，即無最優(yōu)解情況。（4）線性規(guī)劃

5、存在無可行解的情況。4. 如線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)可行域邊界上的一個(gè)點(diǎn)。【正確】5. 百分之一百法則：（1）對(duì)于目標(biāo)函數(shù)決策變量系數(shù)時(shí)，當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時(shí)，最優(yōu)解不變。（2）對(duì)于約束條件右端常數(shù)項(xiàng)變化時(shí)，當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過100%時(shí)，對(duì)偶價(jià)格不變。* 允許增加的百分比 = 增加量 / 允許增加量=增加量/（上限當(dāng)前值） * 允許減少的百分比 = 減少量 / 允許減少量=減少量/（當(dāng)前值下限） * 當(dāng)允許增加量（允許減少量）為無窮大時(shí)，則對(duì)任意增加量（減少量），其允許增加（減少）百分比均看作0；6.

6、在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，不可能存在的變量是D .A可控變量 B松馳變量 c剩余變量 D人工變量 7.看圖填空題：【詳見：課本例題P29 / 平時(shí)測(cè)驗(yàn)試卷】第四章 線性規(guī)劃在工商管理中的應(yīng)用一、選擇題/判斷題1.線性規(guī)劃可以解決： （1）人力資源分配問題 （2）生產(chǎn)計(jì)劃問題 （3）套裁下料問題（4）配料問題 （5）投資問題第七章 運(yùn)輸問題一、選擇題/填空題/判斷題1.產(chǎn)銷平衡問題：總產(chǎn)量=總銷量2.平衡運(yùn)輸問題即是指m個(gè)供應(yīng)地的總供應(yīng)量 D n個(gè)需求地的總需求量。A 大于 B 大于等于 C小于 D 等于3.產(chǎn)銷不平衡問題：（1）總產(chǎn)量>總銷量：增加假想銷地（2）總產(chǎn)量<總銷量：增

7、加假想產(chǎn)地4. 物資調(diào)運(yùn)問題中，有m個(gè)供應(yīng)地，Al，A2，Am，Aj的供應(yīng)量為ai(i=1，2，m)，n個(gè)需求地B1，B2，Bn，B的需求量為bj(j=1，2，n)，則供需平衡條件為 =二、構(gòu)建模型題【運(yùn)輸問題】考題：某化學(xué)公司有三個(gè)原料基地，每天要把生產(chǎn)的原料運(yùn)往、四個(gè)工廠，各原料基地的產(chǎn)量分別為16噸、10噸、22噸，各工廠的需求量分別8噸、14噸、12噸、14噸,各原料基地到各工廠的運(yùn)價(jià)（百元/噸）如下表所示。問應(yīng)如何組織調(diào)運(yùn)才能使總運(yùn)費(fèi)最少，請(qǐng)畫出產(chǎn)銷平衡與運(yùn)價(jià)表？工廠運(yùn)價(jià)基地B1B2B3B4產(chǎn)量A1A2A34281210543111196161022銷量8141214【解析】本題為產(chǎn)

8、銷平衡問題。 答案略.第八章 整數(shù)規(guī)劃一、名詞解釋1.純整數(shù)規(guī)劃：在整數(shù)規(guī)劃中，所有的變量都為非負(fù)整數(shù)。2.混合整數(shù)規(guī)劃：在整數(shù)規(guī)劃中，有一部分變量為負(fù)整數(shù)。3. 0-1規(guī)劃：在整數(shù)規(guī)劃中，變量的取值只為0和1。二、選擇題1.整數(shù)規(guī)劃可以解決： （1）投資場(chǎng)所的選擇 （2） 固定成本問題 （3）指派問題（4）分布系統(tǒng)設(shè)計(jì) （5）投資問題2.整數(shù)規(guī)劃問題中，變量的取值可能是D。A整數(shù) B0或1 C大于零的非整數(shù) D以上三種都可能3.整數(shù)規(guī)劃類型包括（ CDE ）A 線性規(guī)劃 B 非線性規(guī)劃 C 純整數(shù)規(guī)劃 D混合整數(shù)規(guī)劃 E 01規(guī)劃三、構(gòu)建模型題【指派問題】考題：有四個(gè)工人，要分別指派他們完成

9、四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。解：引入01變量 xij，并令 xij = 1(當(dāng)指派第 i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第 i人去完成第j項(xiàng)工作時(shí))構(gòu)建0-1規(guī)劃模型：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作) x31+

10、x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 為0-1變量，i,j = 1,2,3,4第九章 目標(biāo)規(guī)劃一、名詞解釋1. 目標(biāo)規(guī)劃：解決存在多個(gè)目標(biāo)的最優(yōu)化問題的方法二、選擇題1.目標(biāo)規(guī)劃可以解決： （1）企業(yè)生產(chǎn)問題 （2）商務(wù)活動(dòng)問題 （3）

11、投資問題 （4）裁員問題 （5）營(yíng)銷問題2. 正、負(fù)偏差相乘積為零。即：d+×d-=0三、構(gòu)建模型題 【目標(biāo)規(guī)劃模型】 考題：詳見書本課后習(xí)題。（必考）第十一章 圖與網(wǎng)絡(luò)模型一、名詞解釋1. 最小生成樹問題：在一個(gè)賦權(quán)的連通的無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。2.樹：無圈的連通圖3.最大流問題：在網(wǎng)絡(luò)圖中，在單位時(shí)間內(nèi)，從發(fā)點(diǎn)到收點(diǎn)的最大流量二、選擇題/填空題/判斷題1.一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的?！菊_】2.點(diǎn)和邊構(gòu)成：無向圖。點(diǎn)邊交錯(cuò)在一起，最終重合成為：圈3.點(diǎn)和弧構(gòu)成：有向圖。

12、點(diǎn)弧交錯(cuò)在一起，最終起點(diǎn)和終點(diǎn)重合成為：路 4.最短路問題-雙標(biāo)號(hào)法：對(duì)圖中的點(diǎn)vj賦予兩個(gè)標(biāo)號(hào)（lj ,kj），第一個(gè)標(biāo)號(hào)lj表示從起點(diǎn)vs到vj的最短路的長(zhǎng)度，第二個(gè)標(biāo)號(hào)kj表示在vs至vj的最短路上vj前面一個(gè)鄰點(diǎn)的下標(biāo)。5.圖論可以解決： （1）最短路問題 （2）最小生成樹問題 （3）最大流問題 （4）最小費(fèi)用最大流問題 （5）七橋問題三、構(gòu)建模型題1.用破圈法求最小生成樹問題：【答題模板】 解：（1）在原圖G中，任找一個(gè)圈（ ， ， ， ），去掉最大邊 , ，得到生成子圖G1;（2）在生成子圖G1中，任找一個(gè)圈（ ， ， ， ），去掉最大邊 , ，得到生成子圖G2;（3）在生成子圖G

13、2中，任找一個(gè)圈（ ， ， ， ），去掉最大邊 , ，得到生成子圖G3; . . . . . . . . .（6）在生成子圖G5中，再也找不到任何一個(gè)圈了，得到最小生成樹。如下圖所示.2.求最大流問題：【答題模板】 解：（1）對(duì)圖中的流量表示做一下改進(jìn)，如圖所示；（2）選擇路V VV ，可知pf= ，改進(jìn)的網(wǎng)絡(luò)流量圖如圖；（3）選擇路V VV ，可知pf= ，改進(jìn)的網(wǎng)絡(luò)流量圖如圖；（4）選擇路V VV ，可知pf= ，改進(jìn)的網(wǎng)絡(luò)流量圖如圖；（5）在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路，路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為 。最大流量圖如圖所示。第十二章 排序與統(tǒng)籌方法一、填空題/選擇題/判斷題Ø 1.一臺(tái)機(jī)器、n個(gè)零件的排序問題：加工時(shí)間短的零件放在前面，加工時(shí)間長(zhǎng)的零件放在后面。Ø 2.兩臺(tái)機(jī)器、n個(gè)零件的排序問題加工時(shí)間短的零件放在后面。第十五章 對(duì)策論一、名詞解釋1. 二人有限零和對(duì)策（矩陣策略）：指有兩個(gè)局中人，每個(gè)局中人的策略集的策略數(shù)目都是有限的；每一局勢(shì)的對(duì)策都有確定的益損值，并且