運籌學(OR)主講：張潤東管理學博士管理學院管理科學與工程系

張潤東Tel-mail：rung_bj2008@163.com平時成績＝出勤（30）+考試（70）第一講

緒論及運籌1回顧

運籌學是高等學校經濟管理類專業本科生所必修的一門專業基礎課；是分析和解決經營管理領域最優化問題的一門方法論學科各高校《運籌學》開課情況：哈工大：管理學院十門平臺課之一，本科60學時，考試100％試卷；碩士70％試卷＋30％案例。重大：本科64學時，碩士45學時，博士30學時。東北大學：本科72學時＋32學時案例分析南航：本科72學時《運籌學》教材《運籌學》

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

程

簡

介

何謂“運籌學”？它的英文名稱是OperationsResearch,直譯為“運作研究”或者作戰行動。就是研究在經營管理活動中如何行動，如何以盡可能小的代價，獲取盡可能好的結果，即所謂“最優化”問題。課

程

簡

介

中國學者把這門學科意譯為“運籌學”，就是取自古語“運籌于帷幄之中，決勝于千里之外”，其意為運算籌劃，出謀獻策，以最佳策略取勝。這就極為恰當地概括了這門學科的精髓。什么是運籌學？多快好省！課

程

簡

介

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

程

簡

介

根據這些學時和教材，作了如下安排：

第二章：線性規劃與單純形法重要分支，1947年提出問題解法-單純形法，計算機技術的發展，可以處理成千上萬的約束條件和決策變量，解決實際問題。生產結構的優化、產品組合。

第三章：線性規劃的對偶理論與靈敏度分析線性規劃的進一步發展，對偶可以用于解決決策變量多于約束條件的線性規劃問題，當常數或者系數發生變化時的分析為靈敏度分析。課

程

簡

介

第四章：運輸問題

特殊的一類線性規劃問題，系數矩陣具有特殊結構，表上作業法解決運輸問題，是物資調運運費最小問題。以上是運籌學的基本組成部分，是教學的重點內容。

第五章：整數規劃一個數學規劃問題如果一部分或全部決策變量的值必須取整數，則這樣的數學規劃稱為整數規劃問題。一般簡稱整數規劃（IntegerProgramming，簡記為IP）。整數規劃是近年來發展起來的規劃論中的一個分支，它在許多領域中都有重要應用。課

程

簡

介

第六章：動態規劃解決多階段決策過程的最優化問題的數學方法。Bellman提出動態規劃方法，將多階段決策問題轉化為一系列相互聯系的單階段問題，逐個加以解決。適用于庫存問題，資源分配問題，背包問題-商人負重上山。第七章：排隊論隨即服務系統理論，是研究擁擠等待現象的科學，在研究概率規律基礎上，解決排隊系統的最優化設計和最優控制問題。性態問題。介紹

課

程

簡

介

第八章：圖與網絡分析圖論運籌學一個重要的分支，應用廣泛，物理學、控制論、交通運輸、工程技術、計算機等領域，解決許多實際問題，交通、通訊網絡的架設于分布。最短路問題（郵遞員送信問題），網絡最大流問題（車輛流、現金流）。介紹網絡設計建設工程。管理學應用水平

制造〉建筑〉服務〉政府課

程

簡

介

第九章：存儲論存儲是一個普遍經濟現象，是為了解決供應與需求不協調而采取的措施。存儲輪研究最合理最經濟的存儲問題。存儲多少最為經濟，多長時間補充，補充多少最合理。水庫（發電與安全）。介紹幾個典型的存儲模型。

第十章：決策分析

管理就是用各種有限的資源以更高水平實現目標的決策過程。西蒙認為管理就是決策。決策分析有效應用于投資分析、產品開發、市場營銷（廣告策劃）等，從定量的角度加以研究。從決策量化的內容角度研究確定性、不確定性和風險性決策。介紹。（1）軍事：

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

1、規劃論：線性規劃（是由丹捷格在1947年發表的有關美國空軍軍事規劃時文章中提出的，并提出了求解線性規劃問題的單純行法。單純行法是運籌學發展史上最重大的進展之一）、非線性規劃、整數規劃、目標規劃、動態規劃

2、運籌學的學科體系

2、存儲論：存儲論中最優批量公式是在本世紀20年代提出的。3、排隊論：先驅為丹麥工程師愛爾朗（Erlang）1917年在哥本哈根電話公司研究電話通信系統時，提出排隊論的一些著名公式。4、圖論與網絡5、決策論6、對策論1、明確問題；2、將問題歸類、使概念化；3、建立數學模型；4、求解數學模型；5、結果分析與模型檢驗（反饋）；6、實施（對現實問題的管理和控制）

3、運籌學分析的主要步驟真實系統問題歸類模型建立模型求解結果分析與模型檢驗數據準備明確問題

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

可把運籌學方法用于廣告預算和媒介的選擇，競爭性的定價、新產品的開發、銷售計劃的制定等方面。4、運籌學的企業應用

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

運籌學的應用案例樸素的運籌思想：都江堰水利工程戰國時期（大約公元前250年）川西太守李冰父子主持修建。其目標是：利用岷江上游的水資源灌溉川西平原。追求的效益還有防洪與航運。其總體構思是系統思想的杰出運用。

都江堰由三大工程及120多項配套工程組成：

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

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

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

它們巧妙結合，完整而嚴密，相得益彰。兩千多年來，這項工程一直發揮著巨大的效益，是我國最成功的水利工程。三峽工程皇宮修復工程

“一溝三用”

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

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

1935年，英國科學家R.Watson-Wart發明了雷達。丘吉爾命令在英國東海岸的Bawdsey建立了一個秘密雷達站。當時，德國已擁有一支強大的空軍，起飛17分鐘即到達英國本土。在如此短的時間內，如何預警和攔截成為一大難題。

1939年由曼徹斯特大學物理學家、英國戰斗機司令部顧問、戰后獲得諾貝爾獎金的P.M.S.Blackett為首，組織了一個小組，代號“Blackett馬戲團”。

Team：三名心理學家、兩名數學家、兩名應用數學家、一名天文物理學家、一名普通物理學家、一名海軍軍官、一名陸軍軍官、一名測量員。

研究的問題是：

1、設計將雷達信息傳送到指揮系統和武器系統的最佳方式；

2、雷達與武器的最佳配置；

通過他們卓有成效的研究，獲得巨大成功。“Blackett馬戲團”在秘密報告中首次使用了“OperationalResearch”，即“運籌學”。大西洋反潛戰（1942年）

1942年，美國大西洋艦隊反潛戰官員W.D.BAKER艦長請求成立反潛戰運籌組，麻省理工學院的物理學家P.W.MORSE被請來擔任計劃與監督。1941-1942年，德國潛艇嚴密封鎖了英吉利海峽，企圖切斷英國的“生命線”。海軍幾次反封鎖，均不成功。

MORSE經過多方實地考察，最后提出了兩條重要建議：

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

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

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

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

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

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

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

飼料VAVBVC價格元/kgIIIIIIIVV3216180.510.220.827495營養要求70030200建模

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

≥700營養要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200非負性要求：x1

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

完整的數學模型

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

一、線性規劃問題1、掌握模型的數學形式和標準形式：目標函數：約束條件：線性規劃的標準型

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

…

…

…am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,n標準型的特征

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

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

理解線性規劃問題解的性質１、若線性規劃的可行域存在，則可行域是一個凸集。2、若線性規劃問題的最優解存在，則最優解或最優解之一一定是可行域的凸集的某個頂點。3、線性規劃問題有最優解，一定存在一個基可行解是最優解。

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

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

可行基：對應于基可行解的基稱為可行基。

非可行解可行解基解基可行解找出一個初始可行解是否最優轉移到另一個目標函數（找更大的基本可行解）最優解是否循環直到找出為止，核心是：變量迭代結束4、掌握單純性表解法：確定初始基可行解若LP的標準型為:MaxZ=c1x1+c2x2+cmxm+cm+1xm+1…+cnxn

A=該標準型稱為規范式(以x1,…xm為基變量的規范式)單純形初始表為:標準型最優性檢驗換入變量的確定換出變量的確定相同相持(max)(1).當有二個相等的最大數,任取一個(或取下標小的)(取調整量大的)(2).當i有二個相等的最小數,取下標小的一個.若出現循環,則回到該表換另一個最小數作為主行例1用單純性法求解下列線性規劃問題例1的標準型來說明上述計算步驟。

最優解

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

目標函數的最大值z*=14

5用M法求解一般線性規劃問題設線性規劃問題的約束條件則分別給每一個約束方程加入人工變量xn+1,…,xn+m，得到假定人工變量在最大目標函數中的系數為(-M)(M為任意大的正數)人工變量經過基的變換將它們從基變量中逐個替換出來。基變量中不再含有非零的人工變量，這表示原問題有解。若在最終表中當所有cj-zj≤0，而在其中還有某個非零人工變量，這表示原問題無可行解。例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標準型x1+x2-2x3+x4

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

+x7=1x1…x7≥0懲罰項M是很大的正數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的檢驗數為零，所以存在無窮多個最優解

二、線性規劃問題的對偶問題

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

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

右端項價值系數minwA'

價值系數右端項變量n個≥0≤0無約束n個≥≤=約束條件約束條件m個≤≥

=m個≥0≤0無約束變量例：求出下列線形規劃問題的對偶問題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無約束練習求其對偶問題Maxw=5y1+4y2

+6y3y1+2y2

y1

+y3-3y1+2y2

+y3y1-y2

+y3≥2≤

3≤

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

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

對偶問題的對偶是原問題

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

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

對偶定理若原問題有最優解，那么對偶問題也有最優解；且目標函數值相等。(4)可行解是最優解時的性質

設是原問題的可行解，是對偶問題的可行解，當時，是最優解。(6)原問題檢驗數與對偶問題解的關系

設原問題是maxz=CX;AX+XS=b;X,XS≥0它的對偶問題是minω=Yb;YA-YS=C;Y,YS≥0則原問題單純形表的檢驗數行對應其對偶問題的一個基解。

規劃問題的對偶問題的最優解y*i

稱為第i個約束條件的影子價格，代表若P的某個約束條件的右端項常數bi增加一個單位時，所引起的目標函數最優值Z*

的改變量。

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

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

2、資源的市場價格和影子價格的關系，低于-企業應該買進該資源用于擴大生產；高于-則企業的決策者應該將已有資源買掉。

ci

,bj發生變化——對線性規劃的影響

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

三、運輸問題及其數學模型

問題的提出一般的運輸問題就是要解決把某種產品從若干個產地調運到若干個銷地，在每個產地的供應量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。回本章目錄

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

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

該系數矩陣中對應于變量xij的系數向量Pij，其分量中除第i個和第m+j個為1以外，其余的都為零。即產量大于銷量

對于產大于銷問題，可得到下列運輸問題的模型：

可增加一個假想的銷地，其銷量為：某個產地Ai運到這個假想銷地Bn+1的物資量xi,n+1，實際上就意味著將這些物資在原產地貯存，其相應的運價，

轉化為產銷平衡的問題，其數學模型為：

產量小于銷量

可增加一個假想的產地，其產量為：因此由假想產地運往某個銷地的物資數量，實際上就意味著銷地缺少這些物資供應的量，其相應的運費為。上述不平衡問題就轉化為平衡的問題，

表上作業法:1.確定初始調運方案的最小元素法；2.檢驗數的意義、計算方法和格式；3.方案調整的方法；4.把不平衡運輸問題轉化為標準模型的方法。

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

解的最優性檢驗閉回路法和位勢法閉回路法

在運輸問題中，每個空格對應一個非基變量。因此，我們需要求出每個空格的檢驗數。當所有的檢驗數都大于或等于零時該調運方案就是最優方案。

如果對閉回路的方向不加區別，對每一個非基變量（空格）可以找到而且只能找到唯一的一個由基變量（數字格）組成的閉回路。閉合回路法的空格檢驗數代表：向空格調運單位貨物與原運輸方案相比引起的運費的變化。檢驗數的經濟意義為空格增運1單位引起總費用的變化數

例1

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

解

先作出這問題的產銷平衡表和單位運價表，見表3-3，表3-4

表3-3單位運價表

表3-4產銷平衡表

這方案的總運費為860元。

850元四動態規劃1、理解動態規劃的基本概念

狀態的選擇應使其具有“無后效性”，即過程的歷史只能通過當前的狀態去影響它未來的發展。或者說過程未來的進程只與當前的狀態有關，而與過程的歷史無關。狀態變量，常用sk表示在第k階段的某一階段，Sk表示第k階段的狀態變量集合。方程:狀態轉移方程概念:階段變量k﹑狀態變量sk﹑決策變量uk;指標:

動態規劃本質上是多階段決策過程;

效益指標函數形式:

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

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

最優軌線，即執行最優策略時的狀態序列

最優目標函數值從k到終點最優策略子策略的最優目標函數值動態規劃最優化原理：

“無論過去狀態及決策如何，對于面前決策所形成的狀態而言，余下的諸決策必構成最優策略。”一個最優策略的子策略是最優的。2、理解動態規劃基本方程

例

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

n=5sk：第k年度開始時擁有的完好的機床臺數。uk：第k年度開始時對A部門投放的機床數則第k階段B部門投放的機床數目標函數狀態轉移方程

基本方程

fk(sk)：由第k年的sk出發，采用最優分配方案到第5個年度結束這段時間內產品的產量。k=5時，k=4時，k=4時，k=3時，k=3時，k=2時，k=2時，k=1時，k=1時，

例2投資問題

現有資金5百萬元，可對三個項目進行投資，投資額均為整數（單位為百萬元），其中2號項目的投資不得超過3百萬元，1號和3號項目的投資均不得超過4百萬元，3號項目至少要投資1百萬元。每個項目投資5年后，預計可獲得的收益見下表，問如何投資可望獲得最大的收益。

01234103610122051012---30481115投資額u收益wk項目k

[解]sk——對1,…,(k-1)項目投資后剩余的金額(狀態變量)，投資第k個項目前的資金數uk——對k項目的投資額wk(sk,uk)——對k項目投資uk后的收益wk(uk)

fk(sk)——應用剩余資金sk對k,(k+1),…,n項目投資可獲得的最大收益狀態轉移方程為sk+1=sk-uk

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

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

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

其中2號項目的投資不得超過3百萬元，1號和3號項目的投資均不得超過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當k=1時，有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應用順序跟蹤，可知，最優方案有兩個：方案Ⅰ——u1*=0,u2*=2,u3*=3方案Ⅱ——u1*=1,u2*=2,u3*=2最大收益為21百萬元。五圖論與網絡分析

圖的基本概念

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

定理1所有頂點度數之和等于所有邊數的2倍。定理2

在任一圖中，奇點的個數必為偶數。

定理：有向圖中，所有頂點的入次之和等于所有頂點的出次之和。§2最小支撐樹問題本節主要內容：樹支撐樹最小支撐樹

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

樹

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

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

在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。55.5v1v2v3v4v53.57.5423§3最短路徑問題最短路問題是在一個網絡（賦權有向圖）中尋找從起點到某個節點之間一條最短的路線。現欲求出υ1至υ6距離最短的路徑。最短路問題的Dijstra解法（權為整數）

1.標號意義給點vi標上號的意義：表示起點v1到點vi

的最短路已找到第一個標號表示v1至vi點最短路的路長第二個標號表示v1至vi的最短路中vi之前節點為2.算法基本步驟如下：(1)首先對起點v1標號,即計算v1至v1的最短路，最短路長為零，標號(2)考慮網絡中所有這樣的弧代表標號點的集合2.算法基本步驟如下：(3)若非空，計算

其中wij為弧(vi,vj)之長度，一未標號頂點vjk(4)對頂點vjk標號，其中

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

點由未標號點變成已標號點，重復(2)練習：用標號法解題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)關鍵線路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路長：124、最大流問題maxv=v（f）容量約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362可行流6、增廣鏈可行流中fij＝cij

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

若為網絡中從vs到vt的一條鏈，給定向為從vs到vt，上的弧凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其集合分別用和表示。f

是一個可行流，如果滿足：

則稱為從vs到vt

的關于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)是一個增廣鏈顯然圖中增廣鏈不止一條最大流判定定理：

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

的關于f*的增廣鏈。

7、截集和截集的截量

容量網絡D=（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合

使則所有始點屬于S，而終點屬于的弧的集合，稱為分離vs和vt由S決定的截集。截集中所有弧的容量之和，稱為這個截集的截量，記為13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設，則截集為容量為248.流量與截量的關系任一可行流的流量都不會超過任一截集的截量（∵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）最大流最小截定理：網絡的最大流量等于最小截量。求最大流方法——標號法理論依據：最大流最小截定理

不存在關于f的增廣鏈

判斷：可行流f是最大流：思路：從始點開始標號，尋找是否存在增廣鏈。給vj標號為[θj,vi]，其中θj為調整量，vi為前一節點。網絡最大流問題的標號解法步驟：

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

（2）對已知可行流用標號法尋找增值鏈

（3）沿可增值鏈調整成更大的可行流

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

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

reviewtechnique）壓縮工期問題工程工序費用分析

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

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

在收益矩陣中先從各策略所對應的可能發生的“策略—事件”對的結果中選出最小值，將它們列于表的最右列。再從此列的數值中選出最大者，以它對應的策略為決策者應選的決策策略。3.2樂觀主義(maxmax)決策準則持樂觀主義(maxmax)決策準則的決策者對待風險的態度與悲觀主義者不同，當他面臨情況不明的策略問題時，他絕不放棄任何一個可獲得最好結果的機會，以爭取好中之好的樂觀態度來選擇他的決策策略。3.2樂觀主義(maxmax)決策準則

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

決策者計算各策略的收益期望值，然后在所有這些期望值中選擇最大者，以它對應的策略為決策策略，見表15-5。然后按下式決定決策策略。3.4最小機會損失準則最小機會損失決策準則亦稱