第一講緒論運(yùn)籌1回顧

運(yùn)籌學(xué)(OR)主講：張潤(rùn)東管理學(xué)博士管理學(xué)院管理科學(xué)與工程系

張潤(rùn)東Tel-mail：rung_bj2008@163.com平時(shí)成績(jī)＝出勤（30）+考試（70）第一講

緒論及運(yùn)籌1回顧

運(yùn)籌學(xué)是高等學(xué)校經(jīng)濟(jì)管理類專業(yè)本科生所必修的一門專業(yè)基礎(chǔ)課；是分析和解決經(jīng)營(yíng)管理領(lǐng)域最優(yōu)化問題的一門方法論學(xué)科各高?！哆\(yùn)籌學(xué)》開課情況：哈工大：管理學(xué)院十門平臺(tái)課之一，本科60學(xué)時(shí)，考試100％試卷；碩士70％試卷＋30％案例。重大：本科64學(xué)時(shí)，碩士45學(xué)時(shí)，博士30學(xué)時(shí)。東北大學(xué)：本科72學(xué)時(shí)＋32學(xué)時(shí)案例分析南航：本科72學(xué)時(shí)《運(yùn)籌學(xué)》教材《運(yùn)籌學(xué)》

吳祈宗主編，機(jī)械工業(yè)出版社，北理工，韓潤(rùn)春參考書1、《運(yùn)籌學(xué)》教材編寫組，錢頌迪，胡運(yùn)權(quán)清華大學(xué)出版社2、《管理科學(xué)基礎(chǔ)》吳育華，杜綱主編，天津大學(xué)出版社多目標(biāo)決策與綜合評(píng)估技術(shù)吳育華教授主要研究方向博弈理論與風(fēng)險(xiǎn)分析12信息技術(shù)在現(xiàn)代管理中的應(yīng)用3沖突分析與合作理論4經(jīng)濟(jì)增長(zhǎng)的非參數(shù)方法測(cè)度5足球經(jīng)濟(jì)與足球管理6授課原則須以一桶水的內(nèi)必容來講授一杯水內(nèi)容杯桶原則樹干原則演戲原則力求講清課程內(nèi)容的樹干及主要分支，而不刻意描述樹葉內(nèi)容自編自導(dǎo)自演教師學(xué)生知識(shí)杯桶原則必須以一桶水的內(nèi)容來講授一杯水內(nèi)容樹干原則力求講清課程內(nèi)容的樹干及主要分支，而不刻意描述樹葉內(nèi)容演戲原則演員導(dǎo)演編劇自編、自導(dǎo)、自演，把每一堂課作為一藝術(shù)精品課

程

簡(jiǎn)

介

何謂“運(yùn)籌學(xué)”？它的英文名稱是OperationsResearch,直譯為“運(yùn)作研究”或者作戰(zhàn)行動(dòng)。就是研究在經(jīng)營(yíng)管理活動(dòng)中如何行動(dòng)，如何以盡可能小的代價(jià)，獲取盡可能好的結(jié)果，即所謂“最優(yōu)化”問題。課

程

簡(jiǎn)

介

中國(guó)學(xué)者把這門學(xué)科意譯為“運(yùn)籌學(xué)”，就是取自古語“運(yùn)籌于帷幄之中，決勝于千里之外”，其意為運(yùn)算籌劃，出謀獻(xiàn)策，以最佳策略取勝。這就極為恰當(dāng)?shù)馗爬诉@門學(xué)科的精髓。什么是運(yùn)籌學(xué)？多快好??！課

程

簡(jiǎn)

介

我們講授這門課程的目的就是要使同學(xué)們系統(tǒng)地了解運(yùn)籌學(xué)的基本概念、基本原理、研究方法及其應(yīng)用，掌握運(yùn)籌學(xué)整體優(yōu)化的思想和定量分析的優(yōu)化技術(shù)，并能正確應(yīng)用各類模型分析和解決實(shí)際問題。這門課程共講授40學(xué)時(shí)。考試要求平時(shí)成績(jī)（30%）+期末考試（70%）課

程

簡(jiǎn)

介

根據(jù)這些學(xué)時(shí)和教材，作了如下安排：

第二章：線性規(guī)劃與單純形法重要分支，1947年提出問題解法-單純形法，計(jì)算機(jī)技術(shù)的發(fā)展，可以處理成千上萬的約束條件和決策變量，解決實(shí)際問題。生產(chǎn)結(jié)構(gòu)的優(yōu)化、產(chǎn)品組合。

第三章：線性規(guī)劃的對(duì)偶理論與靈敏度分析線性規(guī)劃的進(jìn)一步發(fā)展，對(duì)偶可以用于解決決策變量多于約束條件的線性規(guī)劃問題，當(dāng)常數(shù)或者系數(shù)發(fā)生變化時(shí)的分析為靈敏度分析。課

程

簡(jiǎn)

介

第四章：運(yùn)輸問題

特殊的一類線性規(guī)劃問題，系數(shù)矩陣具有特殊結(jié)構(gòu)，表上作業(yè)法解決運(yùn)輸問題，是物資調(diào)運(yùn)運(yùn)費(fèi)最小問題。以上是運(yùn)籌學(xué)的基本組成部分，是教學(xué)的重點(diǎn)內(nèi)容。

第五章：整數(shù)規(guī)劃一個(gè)數(shù)學(xué)規(guī)劃問題如果一部分或全部決策變量的值必須取整數(shù)，則這樣的數(shù)學(xué)規(guī)劃稱為整數(shù)規(guī)劃問題。一般簡(jiǎn)稱整數(shù)規(guī)劃（IntegerProgramming，簡(jiǎn)記為IP）。整數(shù)規(guī)劃是近年來發(fā)展起來的規(guī)劃論中的一個(gè)分支，它在許多領(lǐng)域中都有重要應(yīng)用。課

程

簡(jiǎn)

介

第六章：動(dòng)態(tài)規(guī)劃解決多階段決策過程的最優(yōu)化問題的數(shù)學(xué)方法。Bellman提出動(dòng)態(tài)規(guī)劃方法，將多階段決策問題轉(zhuǎn)化為一系列相互聯(lián)系的單階段問題，逐個(gè)加以解決。適用于庫存問題，資源分配問題，背包問題-商人負(fù)重上山。第七章：排隊(duì)論隨即服務(wù)系統(tǒng)理論，是研究擁擠等待現(xiàn)象的科學(xué)，在研究概率規(guī)律基礎(chǔ)上，解決排隊(duì)系統(tǒng)的最優(yōu)化設(shè)計(jì)和最優(yōu)控制問題。性態(tài)問題。介紹

課

程

簡(jiǎn)

介

第八章：圖與網(wǎng)絡(luò)分析圖論運(yùn)籌學(xué)一個(gè)重要的分支，應(yīng)用廣泛，物理學(xué)、控制論、交通運(yùn)輸、工程技術(shù)、計(jì)算機(jī)等領(lǐng)域，解決許多實(shí)際問題，交通、通訊網(wǎng)絡(luò)的架設(shè)于分布。最短路問題（郵遞員送信問題），網(wǎng)絡(luò)最大流問題（車輛流、現(xiàn)金流）。介紹網(wǎng)絡(luò)設(shè)計(jì)建設(shè)工程。管理學(xué)應(yīng)用水平

制造〉建筑〉服務(wù)〉政府課

程

簡(jiǎn)

介

第九章：存儲(chǔ)論存儲(chǔ)是一個(gè)普遍經(jīng)濟(jì)現(xiàn)象，是為了解決供應(yīng)與需求不協(xié)調(diào)而采取的措施。存儲(chǔ)輪研究最合理最經(jīng)濟(jì)的存儲(chǔ)問題。存儲(chǔ)多少最為經(jīng)濟(jì)，多長(zhǎng)時(shí)間補(bǔ)充，補(bǔ)充多少最合理。水庫（發(fā)電與安全）。介紹幾個(gè)典型的存儲(chǔ)模型。

第十章：決策分析

管理就是用各種有限的資源以更高水平實(shí)現(xiàn)目標(biāo)的決策過程。西蒙認(rèn)為管理就是決策。決策分析有效應(yīng)用于投資分析、產(chǎn)品開發(fā)、市場(chǎng)營(yíng)銷（廣告策劃）等，從定量的角度加以研究。從決策量化的內(nèi)容角度研究確定性、不確定性和風(fēng)險(xiǎn)性決策。介紹。（1）軍事：

運(yùn)籌學(xué)作為科學(xué)名字出現(xiàn)在20世紀(jì)30年代末，當(dāng)時(shí)英美對(duì)付德國(guó)的空襲，雷達(dá)作為防空系統(tǒng)的一部分，從技術(shù)上是可行的，但實(shí)際運(yùn)用時(shí)不好用。為此，英美等國(guó)抽調(diào)各方面的專家參與各種戰(zhàn)略戰(zhàn)術(shù)的優(yōu)化研究工作，獲得了顯著的成功，大大推進(jìn)了勝利的進(jìn)程。戰(zhàn)后，從事這些活動(dòng)的許多專家轉(zhuǎn)到了民用部門。1、運(yùn)籌學(xué)的歷史來源：（2）管理：管理既具有科學(xué)性又具有藝術(shù)性。動(dòng)作研究切削效率與車速、進(jìn)刀量等因素的數(shù)學(xué)關(guān)系-優(yōu)選法用于生產(chǎn)活動(dòng)分析和計(jì)劃統(tǒng)籌方法（3）經(jīng)濟(jì)：經(jīng)濟(jì)理論特別是數(shù)理經(jīng)濟(jì)學(xué)派對(duì)運(yùn)籌學(xué)影響巨大。近30年來，經(jīng)濟(jì)數(shù)學(xué)和運(yùn)籌學(xué)互相影響，相互促進(jìn)，共同發(fā)展。運(yùn)籌學(xué)在中國(guó)：50年代中期錢學(xué)森，許國(guó)志引入華羅庚推廣優(yōu)選法、統(tǒng)籌法中國(guó)郵遞員問題、運(yùn)輸問題

1、規(guī)劃論：線性規(guī)劃（是由丹捷格在1947年發(fā)表的有關(guān)美國(guó)空軍軍事規(guī)劃時(shí)文章中提出的，并提出了求解線性規(guī)劃問題的單純行法。單純行法是運(yùn)籌學(xué)發(fā)展史上最重大的進(jìn)展之一）、非線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃

2、運(yùn)籌學(xué)的學(xué)科體系

2、存儲(chǔ)論：存儲(chǔ)論中最優(yōu)批量公式是在本世紀(jì)20年代提出的。3、排隊(duì)論：先驅(qū)為丹麥工程師愛爾朗（Erlang）1917年在哥本哈根電話公司研究電話通信系統(tǒng)時(shí)，提出排隊(duì)論的一些著名公式。4、圖論與網(wǎng)絡(luò)5、決策論6、對(duì)策論1、明確問題；2、將問題歸類、使概念化；3、建立數(shù)學(xué)模型；4、求解數(shù)學(xué)模型；5、結(jié)果分析與模型檢驗(yàn)（反饋）；6、實(shí)施（對(duì)現(xiàn)實(shí)問題的管理和控制）

3、運(yùn)籌學(xué)分析的主要步驟真實(shí)系統(tǒng)問題歸類模型建立模型求解結(jié)果分析與模型檢驗(yàn)數(shù)據(jù)準(zhǔn)備明確問題

實(shí)施1、明確問題：確定問題是什么？通過系統(tǒng)分析與研究來定義問題，解決什么問題？為此必須做出什么決策？最終要達(dá)到什么目標(biāo)？有哪些不可控因素等。2、將問題歸類、使概念化：將問題用哪類管理科學(xué)方法解決。方法對(duì)號(hào)入座。概念化是指將將方法中的要素和術(shù)語重新描述具體實(shí)際問題，為建立模型作準(zhǔn)備。3、建立數(shù)學(xué)模型：是運(yùn)籌學(xué)的關(guān)鍵步驟，用變量和數(shù)學(xué)關(guān)系形成數(shù)學(xué)模型。（1）構(gòu)成要素：結(jié)果變量、決策變量和不可控變量。結(jié)果變量是一種相依變量，反映了系統(tǒng)達(dá)成目標(biāo)的有效性。決策變量是可控的獨(dú)立變量，描敘了決策問題中必須做出選擇的要素。不可控變量是獨(dú)立變量，描述了對(duì)決策有重要影響因素。（2）數(shù)學(xué)模型如下圖：決策變量不可控變量結(jié)果變量數(shù)學(xué)關(guān)系式?jīng)Q策變量X1,X2（產(chǎn)品產(chǎn)量）線性規(guī)劃模型舉例數(shù)學(xué)關(guān)系式有兩種：目標(biāo)函數(shù)和約束條件生產(chǎn)結(jié)構(gòu)優(yōu)化（產(chǎn)品組合）問題，模型結(jié)構(gòu)圖如下：數(shù)學(xué)關(guān)系式MaxR目標(biāo)函數(shù)X1+X2≤50約束條件不可控變量P1，P2和50（市場(chǎng)價(jià)格和需求）結(jié)果變量R=P1X1+P2X2總收入4、求解模型：求解的方法和解的性質(zhì)各異。求解方法可以分為數(shù)值的和分析的。數(shù)值的是通過某種模式一步一步地搜尋并不斷改進(jìn)解的過程。如數(shù)學(xué)規(guī)劃和動(dòng)態(tài)規(guī)劃等。分析的是由數(shù)學(xué)公式一步求出解。存貯輪。最優(yōu)解和滿意解5、結(jié)果分析和模型檢驗(yàn)：與實(shí)際問題是否相符，靈敏度分析等。6、實(shí)施：對(duì)問題事先管理和控制1生產(chǎn)計(jì)劃--線性規(guī)劃以謀求最大的利潤(rùn)或最小的成本，使用運(yùn)籌學(xué)方法從總體上確定適應(yīng)要求的生產(chǎn)。貯存和勞動(dòng)力安排等計(jì)劃。此外還在生產(chǎn)作業(yè)計(jì)劃日程表的編排，合理下料，配料問題。2市場(chǎng)營(yíng)銷

可把運(yùn)籌學(xué)方法用于廣告預(yù)算和媒介的選擇，競(jìng)爭(zhēng)性的定價(jià)、新產(chǎn)品的開發(fā)、銷售計(jì)劃的制定等方面。4、運(yùn)籌學(xué)的企業(yè)應(yīng)用

3人事管理可以用運(yùn)籌學(xué)方法對(duì)人員的需求和獲得情況進(jìn)行預(yù)測(cè)，確定適合需要的人員編制。用指派問題對(duì)人員合理分配，用層次分析法等方法來確定一個(gè)人才評(píng)價(jià)體系。4財(cái)務(wù)和會(huì)計(jì)設(shè)計(jì)到預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理，使用轉(zhuǎn)變的運(yùn)籌學(xué)方法為：統(tǒng)計(jì)分析、數(shù)學(xué)規(guī)劃、決策分析等。5庫存管理6運(yùn)輸問題等都有廣泛的應(yīng)用。1、科學(xué)性它是在科學(xué)方法論的指導(dǎo)下通過一系列規(guī)范化步驟進(jìn)行。明確問題觀察提出假設(shè)設(shè)計(jì)試驗(yàn)完成試驗(yàn)接受或者決絕假設(shè)5、運(yùn)籌學(xué)研究的特點(diǎn)2、實(shí)踐性運(yùn)籌學(xué)以實(shí)際問題為分析對(duì)象，通過鑒別問題的性質(zhì)、系統(tǒng)的目標(biāo)以及系統(tǒng)內(nèi)主要變量之間的關(guān)系，利用數(shù)學(xué)方法達(dá)到對(duì)系統(tǒng)進(jìn)行最優(yōu)化的目的。結(jié)果要能被實(shí)踐檢驗(yàn)，并被用來指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。3、系統(tǒng)性運(yùn)籌學(xué)用系統(tǒng)的觀點(diǎn)來分析一個(gè)組織（或系統(tǒng)），它著眼于整個(gè)系統(tǒng)而不是一個(gè)局部，通過協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個(gè)系統(tǒng)達(dá)到最優(yōu)狀態(tài)。

運(yùn)籌學(xué)的應(yīng)用案例樸素的運(yùn)籌思想：都江堰水利工程戰(zhàn)國(guó)時(shí)期（大約公元前250年）川西太守李冰父子主持修建。其目標(biāo)是：利用岷江上游的水資源灌溉川西平原。追求的效益還有防洪與航運(yùn)。其總體構(gòu)思是系統(tǒng)思想的杰出運(yùn)用。

都江堰由三大工程及120多項(xiàng)配套工程組成：

1.“魚嘴”岷江分水工程：將岷江水有控制地引入內(nèi)江。

2.“飛沙堰”分洪排沙工程：將泥沙排入外江。

3.“寶瓶口”引水工程：除沙后的江水引入水網(wǎng)干道。

它們巧妙結(jié)合，完整而嚴(yán)密，相得益彰。兩千多年來，這項(xiàng)工程一直發(fā)揮著巨大的效益，是我國(guó)最成功的水利工程。三峽工程皇宮修復(fù)工程

“一溝三用”

北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。方案是：先將工程皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、生產(chǎn)、運(yùn)輸及廢墟物的處理用巧妙地解決了。田忌賽馬

齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王 上 中 下 田忌 下 上 中 最終凈勝一局，贏得1000金。鮑德西（Bawdsey）雷達(dá)站的研究（1935年）

1935年，英國(guó)科學(xué)家R.Watson-Wart發(fā)明了雷達(dá)。丘吉爾命令在英國(guó)東海岸的Bawdsey建立了一個(gè)秘密雷達(dá)站。當(dāng)時(shí)，德國(guó)已擁有一支強(qiáng)大的空軍，起飛17分鐘即到達(dá)英國(guó)本土。在如此短的時(shí)間內(nèi)，如何預(yù)警和攔截成為一大難題。

1939年由曼徹斯特大學(xué)物理學(xué)家、英國(guó)戰(zhàn)斗機(jī)司令部顧問、戰(zhàn)后獲得諾貝爾獎(jiǎng)金的P.M.S.Blackett為首，組織了一個(gè)小組，代號(hào)“Blackett馬戲團(tuán)”。

Team：三名心理學(xué)家、兩名數(shù)學(xué)家、兩名應(yīng)用數(shù)學(xué)家、一名天文物理學(xué)家、一名普通物理學(xué)家、一名海軍軍官、一名陸軍軍官、一名測(cè)量員。

研究的問題是：

1、設(shè)計(jì)將雷達(dá)信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；

2、雷達(dá)與武器的最佳配置；

通過他們卓有成效的研究，獲得巨大成功?！癇lackett馬戲團(tuán)”在秘密報(bào)告中首次使用了“OperationalResearch”，即“運(yùn)籌學(xué)”。大西洋反潛戰(zhàn)（1942年）

1942年，美國(guó)大西洋艦隊(duì)反潛戰(zhàn)官員W.D.BAKER艦長(zhǎng)請(qǐng)求成立反潛戰(zhàn)運(yùn)籌組，麻省理工學(xué)院的物理學(xué)家P.W.MORSE被請(qǐng)來擔(dān)任計(jì)劃與監(jiān)督。1941-1942年，德國(guó)潛艇嚴(yán)密封鎖了英吉利海峽，企圖切斷英國(guó)的“生命線”。海軍幾次反封鎖，均不成功。

MORSE經(jīng)過多方實(shí)地考察，最后提出了兩條重要建議：

1、將反潛攻擊由反潛潛艇投擲水雷，改為飛機(jī)投擲炸彈。起爆深度由100米左右改為25米左右。即當(dāng)潛艇剛下潛時(shí)攻擊效果最佳。(提高效率4-7倍)2、運(yùn)送物資的船隊(duì)及護(hù)航艦隊(duì)編隊(duì)，由小規(guī)模多批次，改為加大規(guī)模、減少批次，這樣，損失率將減少。（25%下降到10%）

丘吉爾采納了MORSE的建議，最終成功地打破封鎖，并重創(chuàng)了德國(guó)潛艇。MORSE同時(shí)獲得英國(guó)和美國(guó)的最高勛章。阿波羅登月計(jì)劃（1958-1969年）

阿波羅登月計(jì)劃的全部任務(wù)分別由地面、空間和登月三部分組成，是一項(xiàng)復(fù)雜龐大的工程項(xiàng)目，它不僅涉及到火箭技術(shù)、電力技術(shù)、冶金和化工等多種技術(shù)，為把人安全地送上月球，還需要了解宇宙空間的物理環(huán)境。

它耗資300億美元，研制零件有幾百萬種，共有二萬家企業(yè)參與，涉及42萬人，歷時(shí)11年之久，為完成這項(xiàng)工作，除了考慮每個(gè)部門之間的配合和協(xié)調(diào)工作外，還要估計(jì)各種未知因素可能帶來的種種影響，就要求有一個(gè)總體規(guī)劃部門運(yùn)用一種科學(xué)的組織管理方法，綜合考慮，統(tǒng)籌安排來解決。2007年10月24日18時(shí)05分嫦娥一號(hào)衛(wèi)星中采用了大量新技術(shù)，能夠?qū)崿F(xiàn)自主控制、三位定向、自我故障診斷、多路加熱器的自主控制、整星能源管理和分配、故障下的應(yīng)急處理等多項(xiàng)功能?！版隙鹨惶?hào)”衛(wèi)星的配套軟件達(dá)到了23類46套，其中控制衛(wèi)星動(dòng)作和姿態(tài)的GNC分系統(tǒng)占了9類20套。實(shí)現(xiàn)衛(wèi)星自主化，完備的軟件是核心。裝有當(dāng)今世界上運(yùn)算能力最強(qiáng)的星載計(jì)算機(jī)，對(duì)月球軌道參數(shù)的計(jì)算提高到1秒種之內(nèi)。在嫦娥一號(hào)衛(wèi)星上，推進(jìn)分系統(tǒng)配置了1臺(tái)大推力的變軌發(fā)動(dòng)機(jī)和12臺(tái)小推力的推力器。12臺(tái)推力器分成Ａ、Ｂ兩分支，每分支6臺(tái)互為備份。嫦娥一號(hào)衛(wèi)星第3次變軌成功后，由24小時(shí)軌道轉(zhuǎn)入48小時(shí)軌道，遠(yuǎn)地點(diǎn)高度由7萬多公里提高到12萬多公里。“嫦娥一號(hào)”衛(wèi)星的設(shè)定了4個(gè)科學(xué)技術(shù)目標(biāo)。第一，通過CCD相機(jī)與激光高度計(jì)獲取月球表面三維立體影像，描繪月球地質(zhì)與構(gòu)造圖；第二，通過γ／x射線譜儀分析月球表面的元素及礦物質(zhì)的含量和分布；第三，通過微波探測(cè)儀測(cè)量月壤的厚度并評(píng)估月壤中氦－3資源；第四，通過高能粒子探測(cè)儀探測(cè)地－月球空間環(huán)境。日本繞月探測(cè)衛(wèi)星“月亮女神”的功能和科學(xué)目標(biāo)與“嫦娥一號(hào)”頗為相似，“輝夜姬”的衛(wèi)星上搭載著14種探測(cè)裝置，是嫦娥一號(hào)裝置數(shù)兩倍多，而且還是一顆主衛(wèi)星和兩顆子衛(wèi)星的多星系統(tǒng)。長(zhǎng)征三號(hào)甲火箭，地球同步轉(zhuǎn)移軌道的運(yùn)載能力為2．65噸，全箭起飛質(zhì)量241噸；美國(guó)阿波羅登月計(jì)劃所動(dòng)用的巨無霸——土星5號(hào)運(yùn)載火箭，月球軌道的運(yùn)載能力為47噸，起飛質(zhì)量達(dá)到了3000噸。我國(guó)數(shù)十家科研院所和高等學(xué)校參與了“嫦娥工程”，已產(chǎn)生4000多項(xiàng)創(chuàng)新。而探月工程取得的各項(xiàng)成果，滲流到國(guó)民經(jīng)濟(jì)的血管中，流入每個(gè)人的日常生活。

“阿波羅”計(jì)劃其科研成果帶動(dòng)了美國(guó)20世紀(jì)60－70年代計(jì)算機(jī)、通信、測(cè)控、火箭、激光、材料和醫(yī)療等高新技術(shù)全面發(fā)展，把科技整體水平提高到了一個(gè)全新高度。每投入1美元，就會(huì)產(chǎn)生4至5美元的國(guó)民經(jīng)濟(jì)回報(bào)。國(guó)際上五大智囊團(tuán)：蘭德（RAND）公司（美國(guó)）國(guó)際應(yīng)用系統(tǒng)分析研究所（美國(guó)）野村研究中心（日本）德國(guó)工業(yè)企業(yè)設(shè)備公司（德國(guó)）斯坦福咨詢公司（美國(guó)）朝鮮戰(zhàn)爭(zhēng)中國(guó)是否出兵？美國(guó)政府出資要求蘭德（RAND）公司做一項(xiàng)緊急研究，并將成果呈報(bào)美國(guó)總統(tǒng)。該項(xiàng)研究成果的結(jié)論極其明晰：中國(guó)將派軍隊(duì)入朝參戰(zhàn)！與歷史的實(shí)際完全一致。在其透徹的分析中，還包含了對(duì)毛澤東主席的性格及心理學(xué)分析，毛澤東性格剛強(qiáng)，面對(duì)挑戰(zhàn)絕不退縮，因此，可以斷定毛澤東會(huì)最終做出參戰(zhàn)的重大決策。學(xué)習(xí)建議要求：學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、方法、思路。培養(yǎng)分析解題結(jié)果及經(jīng)濟(jì)評(píng)價(jià)的能力；培養(yǎng)理論聯(lián)系實(shí)際能力及自學(xué)能力。一、線性規(guī)劃問題

人力資源分配問題例1.11某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時(shí)間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開始時(shí)上班，并連續(xù)工作8小時(shí)，問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?解：設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員人數(shù)。此問題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機(jī)和乘務(wù)員150人。2.生產(chǎn)計(jì)劃問題

某廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（單位小時(shí)）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費(fèi)（每件）0.250.350.5售價(jià)（每件）1.252.002.8解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：目標(biāo)是利潤(rùn)最大化，即利潤(rùn)的計(jì)算公式如下：帶入數(shù)據(jù)整理得到：因此該規(guī)劃問題的模型為：3.套裁下料問題例：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取2.5米長(zhǎng)的毛坯100根，長(zhǎng)1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？解：為了找到一個(gè)省料的套裁方案，必須先設(shè)計(jì)出較好的幾個(gè)下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計(jì)出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭0設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數(shù)分別為xj(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：例題1——配方問題養(yǎng)海貍鼠飼料中營(yíng)養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：

飼料VAVBVC價(jià)格元/kgIIIIIIIVV3216180.510.220.827495營(yíng)養(yǎng)要求70030200建模

設(shè)抓取飼料Ix1kg;飼料IIx2kg;飼料IIIx3kg飼料IVx4kg飼料Vx5kg目標(biāo)函數(shù)：Z=2x1+7x2+4x3+9x4+5x5最省錢minZ=2x1+7x2+4x3+9x4+5x5約束條件：3x1+2x2+x3+6x4+18x5

≥700營(yíng)養(yǎng)要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200非負(fù)性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0

完整的數(shù)學(xué)模型

minZ=2x1+7x2+4x3+9x4+5x53x1+2x2+x3+6x4+18x5

≥700

x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0

一、線性規(guī)劃問題1、掌握模型的數(shù)學(xué)形式和標(biāo)準(zhǔn)形式：目標(biāo)函數(shù)：約束條件：線性規(guī)劃的標(biāo)準(zhǔn)型

代數(shù)式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

…

…

…am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,n標(biāo)準(zhǔn)型的特征

w目標(biāo)函數(shù)極大化w約束條件為等式w右端相為非負(fù)值w決策變量非負(fù)值MaxZ=X1+X25X2≤156X1+2X2

≤24X1+X2≤5X1≥0，X2≥0①②X1X2③1、唯一最優(yōu)解2、無窮多最優(yōu)解（例題）3、無界解4、無可行解

理解線性規(guī)劃問題解的性質(zhì)１、若線性規(guī)劃的可行域存在，則可行域是一個(gè)凸集。2、若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一一定是可行域的凸集的某個(gè)頂點(diǎn)。3、線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。

基：設(shè)A是m×n階約束系數(shù)矩陣（m≤n）,秩為m。則A中一定存在m個(gè)線性無關(guān)的列向量。稱可逆矩陣B=（Pj1,Pj2,…,Pjm

）為線性規(guī)劃（L）的一個(gè)基。基解：X=（x1,x2,…xm,0,…,0）T，稱X為線性規(guī)劃問題的基解基可行解：若基本解中XB=B-1b≥0，則稱該解為基可行解，

可行基：對(duì)應(yīng)于基可行解的基稱為可行基。

非可行解可行解基解基可行解找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)（找更大的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束4、掌握單純性表解法：確定初始基可行解若LP的標(biāo)準(zhǔn)型為:MaxZ=c1x1+c2x2+cmxm+cm+1xm+1…+cnxn

A=該標(biāo)準(zhǔn)型稱為規(guī)范式(以x1,…xm為基變量的規(guī)范式)單純形初始表為:標(biāo)準(zhǔn)型最優(yōu)性檢驗(yàn)換入變量的確定換出變量的確定相同相持(max)(1).當(dāng)有二個(gè)相等的最大數(shù),任取一個(gè)(或取下標(biāo)小的)(取調(diào)整量大的)(2).當(dāng)i有二個(gè)相等的最小數(shù),取下標(biāo)小的一個(gè).若出現(xiàn)循環(huán),則回到該表換另一個(gè)最小數(shù)作為主行例1用單純性法求解下列線性規(guī)劃問題例1的標(biāo)準(zhǔn)型來說明上述計(jì)算步驟。

最優(yōu)解

X*=X(3)=(4,2,0,0,4)T

目標(biāo)函數(shù)的最大值z(mì)*=14

5用M法求解一般線性規(guī)劃問題設(shè)線性規(guī)劃問題的約束條件則分別給每一個(gè)約束方程加入人工變量xn+1,…,xn+m，得到假定人工變量在最大目標(biāo)函數(shù)中的系數(shù)為(-M)(M為任意大的正數(shù))人工變量經(jīng)過基的變換將它們從基變量中逐個(gè)替換出來。基變量中不再含有非零的人工變量，這表示原問題有解。若在最終表中當(dāng)所有cj-zj≤0，而在其中還有某個(gè)非零人工變量，這表示原問題無可行解。例3：用大M法求解下列問題maxZ=2x1-x2+x3x1+x2-2x3

≤84x1-x2+x3

≤22x1+3x2-x3≥

4x1…x3≥0，

maxZ=2x1-x2+x3+0x4+0x5+0x6-Mx7標(biāo)準(zhǔn)型x1+x2-2x3+x4

=84x1-x2+x3+x5=22x1+3x2-x3-x6

+x7=1x1…x7≥0懲罰項(xiàng)M是很大的正數(shù)cj2-11000-McBxBbx1x2x3x4x5x6x70x4811-210008/10X524-110100-Mx7423-100-114/3σj

2+2M-1+3M1-M00-M0√√cj2-11000-McBxBbx1x2x3x4x5x6x70x420/31/30-5/3101/3-1/3200X510/314/302/301-1/31/35/7-1x24/32/31-1/300-1/31/32σj

8/302/300-1/3-M+1/3√cj2-11000-McBxBbx1x2x3x4x5x6x70x445/700-12/71-1/145/14-5/142X15/7101/703/14-1/141/145-1x26/701-3/70-1/7-2/72/7σj

002/70-2/7-1/7-M+1/7√cj2-11000-McBxBbx1x2x3x4x5x6x70x415120015/2-1/21/21X3570103/2-1/21/2-1x2331001/2-1/21/2σj

-2000-10-MX*=（0，3，5，15，0，0，0）Z=-[1*5+（-1）*3]=-2，由于x6的檢驗(yàn)數(shù)為零，所以存在無窮多個(gè)最優(yōu)解

二、線性規(guī)劃問題的對(duì)偶問題

1、對(duì)稱形式下對(duì)偶問題的引出和意義原問題maxz=cTxAx

≤bx≥0對(duì)偶問題minω=bTyATy≥cy≥02、掌握對(duì)偶變換規(guī)則LP（DP）DP（LP）maxzA

右端項(xiàng)價(jià)值系數(shù)minwA'

價(jià)值系數(shù)右端項(xiàng)變量n個(gè)≥0≤0無約束n個(gè)≥≤=約束條件約束條件m個(gè)≤≥

=m個(gè)≥0≤0無約束變量例：求出下列線形規(guī)劃問題的對(duì)偶問題maxZ=x1+4x2+3x32x1+3x2-5x3≤2①

3x1-x2+6x3≥1②x1+x2+x3=4③

x1≥0,x2≤0x3無約束minw=2y1+y2

+4y32y1+3y2

+y3≥13y1-y2

+y3≤

4-5y1+6y2

+y3=3y1≥0y2≤0y3無約束minZ=2x1+3x2-5x3+x4

x1+x2-3x3+x4

≥5①

2x1+2x3-x4≤4②

x2+x3+x4=6③

x1≤0,x2，x3≥0

x4無約束練習(xí)求其對(duì)偶問題Maxw=5y1+4y2

+6y3y1+2y2

y1

+y3-3y1+2y2

+y3y1-y2

+y3≥2≤

3≤

-5=1y1≥0y2≤0y3無約束

3掌握對(duì)偶問題的基本性質(zhì)(1)對(duì)稱性

對(duì)偶問題的對(duì)偶是原問題

;(2)弱對(duì)偶性若X是原問題的可行解，Y是對(duì)偶問題的可行解。則存在CX≤Yb;(3)無界性

若原問題(對(duì)偶問題)為無界解，則其對(duì)偶問題(原問題)無可行解;(4)

對(duì)偶定理若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解；且目標(biāo)函數(shù)值相等。(4)可行解是最優(yōu)解時(shí)的性質(zhì)

設(shè)是原問題的可行解，是對(duì)偶問題的可行解，當(dāng)時(shí)，是最優(yōu)解。(6)原問題檢驗(yàn)數(shù)與對(duì)偶問題解的關(guān)系

設(shè)原問題是maxz=CX;AX+XS=b;X,XS≥0它的對(duì)偶問題是minω=Yb;YA-YS=C;Y,YS≥0則原問題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解。

規(guī)劃問題的對(duì)偶問題的最優(yōu)解y*i

稱為第i個(gè)約束條件的影子價(jià)格，代表若P的某個(gè)約束條件的右端項(xiàng)常數(shù)bi增加一個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z*

的改變量。

5了解影子價(jià)格的概念影子價(jià)格可以分析兩類問題

1、增加最大的影子價(jià)格的約束條件的資源量

2、資源的市場(chǎng)價(jià)格和影子價(jià)格的關(guān)系，低于-企業(yè)應(yīng)該買進(jìn)該資源用于擴(kuò)大生產(chǎn)；高于-則企業(yè)的決策者應(yīng)該將已有資源買掉。

ci

,bj發(fā)生變化——對(duì)線性規(guī)劃的影響

6了解靈敏度分析的基本意義

三、運(yùn)輸問題及其數(shù)學(xué)模型

問題的提出一般的運(yùn)輸問題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案?；乇菊履夸?/p>

下面分兩種情況來討論：（1）。即運(yùn)輸問題的總產(chǎn)量等于其總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷平衡的運(yùn)輸問題。（2）。即運(yùn)輸問題的總產(chǎn)量不等于總銷量，這樣的運(yùn)輸問題稱為產(chǎn)銷不平衡的運(yùn)輸問題。若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，數(shù)學(xué)模型為：其中，ai和bj滿足：

(3-2)稱為產(chǎn)銷平衡條件。

該系數(shù)矩陣中對(duì)應(yīng)于變量xij的系數(shù)向量Pij，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零。即產(chǎn)量大于銷量

對(duì)于產(chǎn)大于銷問題，可得到下列運(yùn)輸問題的模型：

可增加一個(gè)假想的銷地，其銷量為：某個(gè)產(chǎn)地Ai運(yùn)到這個(gè)假想銷地Bn+1的物資量xi,n+1，實(shí)際上就意味著將這些物資在原產(chǎn)地貯存，其相應(yīng)的運(yùn)價(jià)，

轉(zhuǎn)化為產(chǎn)銷平衡的問題，其數(shù)學(xué)模型為：

產(chǎn)量小于銷量

可增加一個(gè)假想的產(chǎn)地，其產(chǎn)量為：因此由假想產(chǎn)地運(yùn)往某個(gè)銷地的物資數(shù)量，實(shí)際上就意味著銷地缺少這些物資供應(yīng)的量，其相應(yīng)的運(yùn)費(fèi)為。上述不平衡問題就轉(zhuǎn)化為平衡的問題，

表上作業(yè)法:1.確定初始調(diào)運(yùn)方案的最小元素法；2.檢驗(yàn)數(shù)的意義、計(jì)算方法和格式；3.方案調(diào)整的方法；4.把不平衡運(yùn)輸問題轉(zhuǎn)化為標(biāo)準(zhǔn)模型的方法。

確定初始基本可行解的方法：最小元素法，西北角法

解的最優(yōu)性檢驗(yàn)閉回路法和位勢(shì)法閉回路法

在運(yùn)輸問題中，每個(gè)空格對(duì)應(yīng)一個(gè)非基變量。因此，我們需要求出每個(gè)空格的檢驗(yàn)數(shù)。當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案。

如果對(duì)閉回路的方向不加區(qū)別，對(duì)每一個(gè)非基變量（空格）可以找到而且只能找到唯一的一個(gè)由基變量（數(shù)字格）組成的閉回路。閉合回路法的空格檢驗(yàn)數(shù)代表：向空格調(diào)運(yùn)單位貨物與原運(yùn)輸方案相比引起的運(yùn)費(fèi)的變化。檢驗(yàn)數(shù)的經(jīng)濟(jì)意義為空格增運(yùn)1單位引起總費(fèi)用的變化數(shù)

例1

某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個(gè)加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為表3-3所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。

解

先作出這問題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，見表3-3，表3-4

表3-3單位運(yùn)價(jià)表

表3-4產(chǎn)銷平衡表

這方案的總運(yùn)費(fèi)為860元。

850元四動(dòng)態(tài)規(guī)劃1、理解動(dòng)態(tài)規(guī)劃的基本概念

狀態(tài)的選擇應(yīng)使其具有“無后效性”，即過程的歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展。或者說過程未來的進(jìn)程只與當(dāng)前的狀態(tài)有關(guān)，而與過程的歷史無關(guān)。狀態(tài)變量，常用sk表示在第k階段的某一階段，Sk表示第k階段的狀態(tài)變量集合。方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量k﹑狀態(tài)變量sk﹑決策變量uk;指標(biāo):

動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過程;

效益指標(biāo)函數(shù)形式:

和、積無后效性可遞推解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時(shí)的狀態(tài)序列

最優(yōu)目標(biāo)函數(shù)值從k到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值動(dòng)態(tài)規(guī)劃最優(yōu)化原理：

“無論過去狀態(tài)及決策如何，對(duì)于面前決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。”一個(gè)最優(yōu)策略的子策略是最優(yōu)的。2、理解動(dòng)態(tài)規(guī)劃基本方程

例

今有1000臺(tái)機(jī)床，要投放到A、B兩個(gè)生產(chǎn)部門，計(jì)劃連續(xù)使用5年。已知對(duì)A部門投入ua臺(tái)機(jī)器時(shí)的年收益是g(ua)=8ua元，機(jī)器完好率a=0.7；相應(yīng)地，B部門為h(ub)=5ub，b=0.9。試建立5年間總收益最大的年度機(jī)器分配方案。 解：階段變量k表示年度

n=5sk：第k年度開始時(shí)擁有的完好的機(jī)床臺(tái)數(shù)。uk：第k年度開始時(shí)對(duì)A部門投放的機(jī)床數(shù)則第k階段B部門投放的機(jī)床數(shù)目標(biāo)函數(shù)狀態(tài)轉(zhuǎn)移方程

基本方程

fk(sk)：由第k年的sk出發(fā)，采用最優(yōu)分配方案到第5個(gè)年度結(jié)束這段時(shí)間內(nèi)產(chǎn)品的產(chǎn)量。k=5時(shí)，k=4時(shí)，k=4時(shí)，k=3時(shí)，k=3時(shí)，k=2時(shí)，k=2時(shí)，k=1時(shí)，k=1時(shí)，

例2投資問題

現(xiàn)有資金5百萬元，可對(duì)三個(gè)項(xiàng)目進(jìn)行投資，投資額均為整數(shù)（單位為百萬元），其中2號(hào)項(xiàng)目的投資不得超過3百萬元，1號(hào)和3號(hào)項(xiàng)目的投資均不得超過4百萬元，3號(hào)項(xiàng)目至少要投資1百萬元。每個(gè)項(xiàng)目投資5年后，預(yù)計(jì)可獲得的收益見下表，問如何投資可望獲得最大的收益。

01234103610122051012---30481115投資額u收益wk項(xiàng)目k

[解]sk——對(duì)1,…,(k-1)項(xiàng)目投資后剩余的金額(狀態(tài)變量)，投資第k個(gè)項(xiàng)目前的資金數(shù)uk——對(duì)k項(xiàng)目的投資額wk(sk,uk)——對(duì)k項(xiàng)目投資uk后的收益wk(uk)

fk(sk)——應(yīng)用剩余資金sk對(duì)k,(k+1),…,n項(xiàng)目投資可獲得的最大收益狀態(tài)轉(zhuǎn)移方程為sk+1=sk-uk

為了獲得最大收益，必須將5百萬元資金全部用于投資，可得下面的遞歸方程：

f4(s4)=0fk(sk)=max{wk(sk,uk)+fk+1(sk+1)}k=3,2,1當(dāng)k=3時(shí)uk=skf3(1)=4f3(2)=8f3(3)=11f3(4)=15sk+1=sk-uk1號(hào)和3號(hào)項(xiàng)目的投資均不得超過4百萬元，3號(hào)項(xiàng)目至少要投資1百萬元。

當(dāng)k=2時(shí),有(注意：項(xiàng)目3至少投資1百萬元)s212345D2(sk){0}{0,1}{0,1,2}{0,1,2,3}{1,2,3}

其中2號(hào)項(xiàng)目的投資不得超過3百萬元，1號(hào)和3號(hào)項(xiàng)目的投資均不得超過4百萬元00

f2(1)=w2(1,0)+f3(1)=4f2(2)=maxw2(2,1)+f3(1)w2(2,0)+f3(2)=max5+40+8=9f2(3)=maxw2(3,2)+f3(1)w2(3,1)+f3(2)w2(3,0)+f3(3)=max10+45+80+11=14f2(4)=maxw2(4,3)+f3(1)w2(4,2)+f3(2)w2(4,1)+f3(3)w2(4,0)+f3(4)=max12+410+85+110+15=18f2(5)=maxw2(5,3)+f3(2)w2(5,2)+f3(3)w2(5,1)+f3(4)=max12+810+115+15=21當(dāng)k=1時(shí)，有s1=5D1(s1)={0,1,2,3,4}f1(5)=maxw1(5,4)+f2(1)w1(5,3)+f2(2)w1(5,2)+f2(3)w1(5,1)+f2(4)w1(5,0)+f2(5)=max12+410+96+143+180+21=21應(yīng)用順序跟蹤，可知，最優(yōu)方案有兩個(gè)：方案Ⅰ——u1*=0,u2*=2,u3*=3方案Ⅱ——u1*=1,u2*=2,u3*=2最大收益為21百萬元。五圖論與網(wǎng)絡(luò)分析

圖的基本概念

網(wǎng)絡(luò)分析最小支撐樹問題最短路徑問題網(wǎng)絡(luò)最大流問題§1圖的基本概念由點(diǎn)和邊組成，記作G=(V，E)，其中V=(v1，v2，……，vn)為結(jié)點(diǎn)的集合，E=(e1，e2，……，em)為邊的集合。點(diǎn)表示研究對(duì)象邊表示表示研究對(duì)象之間的特定關(guān)系1.圖

定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。定理2

在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。

定理：有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和?！?最小支撐樹問題本節(jié)主要內(nèi)容：樹支撐樹最小支撐樹

[例]今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點(diǎn)的煤氣管道所需的費(fèi)用（單位：萬元）如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線，并求所需的總費(fèi)用。3.5ABCDEFGHIJKS2222225452634531樹無圈連通圖(A)(B)(C)例判斷下面圖形哪個(gè)是樹：一、樹的概念與性質(zhì)樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分支點(diǎn)。1、設(shè)圖G=（V，E）是一個(gè)樹，P（G）≥2，那么圖G中至少有兩個(gè)懸掛點(diǎn)。2、樹任刪去一邊則不連通，故樹是使圖保持連通且具有最少邊數(shù)的一種圖形。樹的性質(zhì)：一、樹的概念與性質(zhì)v1v2v3v4v5v6

樹

的性質(zhì)：（3）樹必連通，但無回路（圈）。（4）圖是樹的沖要條件是：圖不含圈（或者是連通圖），有且僅有p-1條邊。（5）樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。（6）n個(gè)頂點(diǎn)的樹必有n-1條邊。（7）樹無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。問題：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。二、最小支撐樹問題55.5v1v2v3v4v53.57.5423算法1（避圈法）：把邊按權(quán)從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結(jié)點(diǎn)數(shù)）。[例]

求上例中的最小支撐樹解：3v12v4v545v23.5v3算法2（破圈法）：

在圖中找圈，并刪除其中最大邊。如此進(jìn)行下去，直至圖中不存在圈。55.5v1v2v3v4v53.57.5423§3最短路徑問題最短路問題是在一個(gè)網(wǎng)絡(luò)（賦權(quán)有向圖）中尋找從起點(diǎn)到某個(gè)節(jié)點(diǎn)之間一條最短的路線?，F(xiàn)欲求出υ1至υ6距離最短的路徑。最短路問題的Dijstra解法（權(quán)為整數(shù)）

1.標(biāo)號(hào)意義給點(diǎn)vi標(biāo)上號(hào)的意義：表示起點(diǎn)v1到點(diǎn)vi

的最短路已找到第一個(gè)標(biāo)號(hào)表示v1至vi點(diǎn)最短路的路長(zhǎng)第二個(gè)標(biāo)號(hào)表示v1至vi的最短路中vi之前節(jié)點(diǎn)為2.算法基本步驟如下：(1)首先對(duì)起點(diǎn)v1標(biāo)號(hào),即計(jì)算v1至v1的最短路，最短路長(zhǎng)為零，標(biāo)號(hào)(2)考慮網(wǎng)絡(luò)中所有這樣的弧代表標(biāo)號(hào)點(diǎn)的集合2.算法基本步驟如下：(3)若非空，計(jì)算

其中wij為弧(vi,vj)之長(zhǎng)度，一未標(biāo)號(hào)頂點(diǎn)vjk(4)對(duì)頂點(diǎn)vjk標(biāo)號(hào)，其中

表示v1至vjk最短路已求出，vjk

點(diǎn)由未標(biāo)號(hào)點(diǎn)變成已標(biāo)號(hào)點(diǎn)，重復(fù)(2)練習(xí)：用標(biāo)號(hào)法解題v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1]其中2=min{0+2,0+5,0+3}其中3=min{0+3，0+5，2+2，2+7}[4，v2][7，v3][8，v5][13，v6]最短距為13；最短路為v1-v2-v3-v5-v6-v7。V3

5V5V24541V612455V4V1V8238V77(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7)關(guān)鍵線路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路長(zhǎng)：124、最大流問題maxv=v（f）容量約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362可行流6、增廣鏈可行流中fij＝cij

的弧叫做飽和??；fij＜cij的弧叫做非飽和??；fij＞0的弧叫做非零流??；fij＝0的弧叫做零流弧。

若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，上的弧凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其集合分別用和表示。f

是一個(gè)可行流，如果滿足：

則稱為從vs到vt

的關(guān)于f的一條增廣鏈。即中的每一條弧都是非飽和弧即中的每一條弧都是非零流弧13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一個(gè)增廣鏈顯然圖中增廣鏈不止一條最大流判定定理：

可行流f*是最大流的充分必要條件是當(dāng)且僅當(dāng)不存在從vs到vt

的關(guān)于f*的增廣鏈。

7、截集和截集的截量

容量網(wǎng)絡(luò)D=（V，A，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合

使則所有始點(diǎn)屬于S，而終點(diǎn)屬于的弧的集合，稱為分離vs和vt由S決定的截集。截集中所有弧的容量之和，稱為這個(gè)截集的截量，記為13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為容量為248.流量與截量的關(guān)系任一可行流的流量都不會(huì)超過任一截集的截量（∵v(f)=f(V1,V2)-f(V2,V1)≤f(V1,V2)≤C(V1,V2)）v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）最大流最小截定理：網(wǎng)絡(luò)的最大流量等于最小截量。求最大流方法——標(biāo)號(hào)法理論依據(jù)：最大流最小截定理

不存在關(guān)于f的增廣鏈

判斷：可行流f是最大流：思路：從始點(diǎn)開始標(biāo)號(hào)，尋找是否存在增廣鏈。給vj標(biāo)號(hào)為[θj,vi]，其中θj為調(diào)整量，vi為前一節(jié)點(diǎn)。網(wǎng)絡(luò)最大流問題的標(biāo)號(hào)解法步驟：

（1）確定初始可行流（觀察法和零流法）

（2）對(duì)已知可行流用標(biāo)號(hào)法尋找增值鏈

（3）沿可增值鏈調(diào)整成更大的可行流

（4）重復(fù)標(biāo)號(hào)過程，直至標(biāo)號(hào)終止，確定最大流一.標(biāo)號(hào)步驟：檢查所有已標(biāo)號(hào)點(diǎn)與沒標(biāo)號(hào)點(diǎn)的關(guān)聯(lián)弧流出弧和流入弧三.標(biāo)號(hào)終止，說明不存在可增價(jià)值鏈，當(dāng)前即為流為最大流，并得最小截集(4)給終點(diǎn)標(biāo)上號(hào)，說明存在可增值鏈,反向追蹤找出，轉(zhuǎn)二.

例用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）??????第一次標(biāo)號(hào)可得兩條可增值鏈如圖1.用標(biāo)號(hào)法求可增價(jià)值鏈按調(diào)整量大的增值鏈調(diào)整，這里按第二條增值鏈調(diào)整，調(diào)后進(jìn)行第二次標(biāo)號(hào)如圖。Vs-V1-V2-V4-Vt，調(diào)量=1v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）?????（5，2）（1，0）（1，0）（2，2）××Vs-V1-V2-V3-Vt，調(diào)量=12.調(diào)整新流，重復(fù)標(biāo)號(hào)，直至標(biāo)號(hào)終止在所得的可增值鏈上調(diào)整流量，=1，調(diào)后進(jìn)行第二次標(biāo)號(hào)如圖。第二次標(biāo)號(hào)未進(jìn)行到底，得最大流如圖，最大流量v=5，同時(shí)得最小截v4v2vsv1vtv3（2，2）（3，3）（4，3）（3，0）（5，3）??????（5，2）（1，0）（1，0）（2，2）習(xí)題課練習(xí)：過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數(shù)字單位：千輛/小時(shí)。求（1）該路網(wǎng)能承受的北-南向最大流量；（2）若要擴(kuò)充通過能力，應(yīng)在那一組路段上擴(kuò)充，說明原因。2143562366241331進(jìn)入Albany（北）離開Albany（南）(1)選取一個(gè)可行流123546（進(jìn)入Albany(北)離開Albany(南)2(2)4(1)3(0)1(1)6(5)3(3)2(2)3(3)6(2)1(1)V1—V4—V2—V5—V6，可擴(kuò)充量為1，調(diào)整成新流，繼續(xù)標(biāo)號(hào),用標(biāo)號(hào)法得可擴(kuò)充鏈123546（進(jìn)入Albany(北)離開Albany(南)2(2)4(2)3(1)1(1)6(5)3(3)2(2)3(3)6(3)1(0)標(biāo)號(hào)終止，當(dāng)前流為最大流，最大流量為8截集為：1-2,4-5，4-6，3-6應(yīng)該在截集弧上擴(kuò)大流量第11章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃關(guān)鍵路線法（CPM）（criticalpathmethod）工程工期的概率分析—項(xiàng)目評(píng)審技術(shù)（PERT）（programevaluation＆

reviewtechnique）壓縮工期問題工程工序費(fèi)用分析

學(xué)習(xí)目的及要求：1、掌握繪制網(wǎng)絡(luò)圖的規(guī)律和方法，對(duì)一些簡(jiǎn)單的實(shí)際問題，通過對(duì)問題的分析，會(huì)繪制網(wǎng)絡(luò)圖。2、熟練掌握網(wǎng)絡(luò)圖中各種參數(shù)的計(jì)算，并會(huì)求關(guān)鍵路線；3、掌握最優(yōu)方案的調(diào)整方法。六決策分析第1節(jié)決策的分類和過程第2節(jié)確定型的決策第3節(jié)不確定型的決策第4節(jié)風(fēng)險(xiǎn)決策第5節(jié)靈敏度分析第6節(jié)效用理論在決策中的應(yīng)用按決策環(huán)境分類：確定型：自然環(huán)境因素完全確定。不確定型：自然環(huán)境因素完全不確定，發(fā)生的概率無法確定，主觀意向決策。風(fēng)險(xiǎn)型：自然環(huán)境因素不是完全確定，發(fā)生的概率已知。決策問題的要素構(gòu)成：(1)決策者，他的任務(wù)是進(jìn)行決策。決策者可以是個(gè)人、委員會(huì)或某個(gè)組織。一般指領(lǐng)導(dǎo)者或領(lǐng)導(dǎo)集體。(2)可供選擇的方案(替代方案)、行動(dòng)或策略。參謀人員提供選擇方案。研究對(duì)象的屬性（客觀度量、主觀選定）目的和目標(biāo)。(3)準(zhǔn)則是衡量選擇方案，包括目的、目標(biāo)、屬性、正確性的標(biāo)準(zhǔn)，在決策時(shí)有單一準(zhǔn)則和多準(zhǔn)則。(4)事件是指不為決策者所控制的客觀存在的將發(fā)生的狀態(tài)，即為自然狀態(tài)。(5)每一事件的發(fā)生將會(huì)產(chǎn)生某種結(jié)果，如獲得收益或損失。(6)決策者的價(jià)值觀，如決策者對(duì)貨幣額或不同風(fēng)險(xiǎn)程度的主觀價(jià)值觀念。確定型的決策第3節(jié)不確定型的決策不確定型的決策是指決策者對(duì)環(huán)境情況一無所知，自然狀態(tài)（事件）是不確定的。決策者根據(jù)自己的主觀傾向進(jìn)行決策，由決策者的主觀態(tài)度不同可分為四種準(zhǔn)則：悲觀主義準(zhǔn)則樂觀主義準(zhǔn)則等可能性準(zhǔn)則最小機(jī)會(huì)準(zhǔn)則3.1悲觀主義(maxmin)決策準(zhǔn)則

悲觀主義決策準(zhǔn)則亦稱保守主義決策準(zhǔn)則。當(dāng)決策者面臨著各事件的發(fā)生概率不清時(shí)，決策者考慮可能由于決策錯(cuò)誤而造成重大經(jīng)濟(jì)損失。由于自己的經(jīng)濟(jì)實(shí)力比較脆弱，他在處理問題時(shí)就較謹(jǐn)慎。他分析各種最壞的可能結(jié)果，從中選擇最好者，以它對(duì)應(yīng)的策略為決策策略，用符號(hào)表示為maxmin決策準(zhǔn)則。3.1悲觀主義(maxmin)決策準(zhǔn)則

在收益矩陣中先從各策略所對(duì)應(yīng)的可能發(fā)生的“策略—事件”對(duì)的結(jié)果中選出最小值，將它們列于表的最右列。再從此列的數(shù)值中選出最大者，以它對(duì)應(yīng)的策略為決策者應(yīng)選的決策策略。3.2樂觀主義(maxmax)決策準(zhǔn)則持樂觀主義(maxmax)決策準(zhǔn)則的決策者對(duì)待風(fēng)險(xiǎn)的態(tài)度與悲觀主義者不同，當(dāng)他面臨情況不明的策略問題時(shí)，他絕不放棄任何一個(gè)可獲得最好結(jié)果的機(jī)會(huì)，以爭(zhēng)取好中之好的樂觀態(tài)度來選擇他的決策策略。3.2樂觀主義(maxmax)決策準(zhǔn)則

決策者在分析收益矩陣各策略的“策略—事件”對(duì)的結(jié)果中選出最大者，記在表的最右列。再從該列數(shù)值中選擇最大者，以它對(duì)應(yīng)的策略為決策策略。3.3等可能性(Laplace)準(zhǔn)則等可能性(Laplace)準(zhǔn)則是19世紀(jì)數(shù)學(xué)家Laplace提出的。他認(rèn)為：當(dāng)一個(gè)人面臨著某事件集合，在沒有什么確切理由來說明這一事件比那一事件有更多發(fā)生機(jī)會(huì)時(shí)，只能認(rèn)為各事件發(fā)生的機(jī)會(huì)是均等的。即每一事件發(fā)生的概率都是1/事件數(shù)。3.3等可能性(Laplace)準(zhǔn)則

決策者計(jì)算各策略的收益期望值，然后在所有這些期望值中選擇最大者，以它對(duì)應(yīng)的策略為決策策略，見表15-5。然后按下式?jīng)Q定決策策略。3.4最小機(jī)會(huì)損失準(zhǔn)則最小機(jī)會(huì)損失決策準(zhǔn)則亦稱