【正文】 al Research,港臺地區(qū)譯為：《 作業(yè)研究 》 、 《 運作研究 》 。留侯世家 》 ?“ 籌”是古代比算盤還早的計算工具之一。 ——沈括 《 夢溪筆談 .補筆談卷二 .權(quán)智 》 2022/2/13 “運籌”的出典 ?據(jù) 《 史記 》 記載：漢高祖劉邦稱贊張良： 運籌 策帷帳中，決勝千里外，子房功也。事畢 ,卻以斥 棄瓦礫灰壤實于塹 中 ,復(fù)為街衢。時 丁晉公 主營復(fù)宮室 ,患取土遠 ,公乃令鑿?fù)ㄡ?取土 ,不日皆成巨塹。運籌學(xué) Operational Research 天津大學(xué)管理學(xué)院 教師簡介 張小濤，博士，副教授 研究方向： 計算實驗金融，中小企業(yè)融資 Email： 運籌學(xué)簡介 什么是運籌學(xué) ? 運籌學(xué)的簡史 運籌學(xué)的分支有哪些 ? 運籌學(xué)研究的一般程序 課程要求 2022/2/13 古籍中的運籌問題 ?田忌賽馬：田忌與齊王多次賽馬，屢戰(zhàn)屢敗，田忌的一位謀士比較了六種對策后建議 …… ——《 十萬個為什么 .數(shù)學(xué)分冊 》 ?最早記載的 《 對策論 》 范例。 2022/2/13 1 2 3 4 5 6上 上 上 中 中 下 下中 中 下 上 下 中 上下 下 中 下 上 上 中齊王田忌古籍中的運籌問題 ?祥符中 ,禁火。乃決汴水入塹中 ,引諸道竹木排筏及船運雜材 ,盡自塹中入至宮門。一舉而三役濟 ,計 省費 以億萬計。 ——司馬遷 《 史記 “運籌”是計劃、安排、比較、決策優(yōu)化的一個過程。五十年代末華羅庚等人介紹國外這一門新興學(xué)科時就建議定名為：運籌學(xué)。其作用越來越被人們所認識。 2022/2/13 我國當代數(shù)學(xué)家在 《 運籌學(xué) 》 中的貢獻 ?1957年起中科院一批數(shù)學(xué)家作了許多令國際同行稱道的工作：如物資調(diào)運問題。 ?凡是講圖論的優(yōu)化的教科書，多半有專門的一章名： Chinese Postman Problems,其中無一例外的要提到管梅谷先生的杰出工作： 中國郵遞員問題 (CPP)。運籌學(xué)對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。 ? 醫(yī)學(xué)、生物、理化、遺傳； ? 工程計劃、安排等“優(yōu)化” 。 2022/2/13 運籌學(xué)的發(fā)展：三個來源 ? 軍 事 ? 管 理 ? 經(jīng) 濟 軍事：運籌學(xué)的主要發(fā)源地 ? 古代軍事運籌學(xué)思想 ? 中國古代的“孫子兵法”在質(zhì)的論斷中滲透著量的分析（ 1981年美國軍事運籌學(xué)會出版了一本書，書中第一句話就是說孫武子是世界上第一個軍事運籌學(xué)的實踐家），中國古代運籌學(xué)思想的例子還有：田忌賽馬、圍魏救趙、行軍運糧，等等。 ? 運籌學(xué)的正式產(chǎn)生：第二次世界大戰(zhàn) ? 鮑德西（ Bawdsey）雷達站的研究 1939年，以 Blackett為首的一個研究小組（代號“ Blackett 馬戲團”），研究如何改進英國的空防系統(tǒng)，提高英國本土防空能力。 據(jù)不完全統(tǒng)計，二戰(zhàn)期間，僅在英、美和加拿大，參加運籌學(xué)工作的科學(xué)家超過 700名。尤其是 1909年的論文“概率與電話通話理論”，開創(chuàng)了運籌學(xué)的重要分支－－排隊論。 ? 康托洛維奇與“生產(chǎn)組織與計劃中的數(shù)學(xué)方法” ? 30年代，蘇聯(lián)數(shù)理經(jīng)濟學(xué)家康托洛維奇從事生產(chǎn)組織與管理中的定量化方法研究，取得了很多重要成果。 運籌學(xué)的性質(zhì)和特點 ?應(yīng)用科學(xué)－“應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)”。 ? 全面質(zhì)量管理 (TQC)。 課程教材： 胡運權(quán)，運籌學(xué)教程，北京：清華大學(xué)出版社， 2022； 主要參考書： [1] 丁以中主編，管理科學(xué) 運用 Spreadsheet建模和求解，北京：清華大學(xué)出版社， 2022； [2] [美 ]弗雷德里克 希利爾（ Frederick S Hillier） ,任建標譯 ,數(shù)據(jù)、模型與決策（原書名 Introduction to Management Science），北京：中國財政經(jīng)濟出版社， 2022； [3]謝金星， 優(yōu)化建模 LINDO/LINGO軟件，清華大學(xué)出版社 [4] 錢頌迪等，運籌學(xué)，北京：清華大學(xué)出版社， 1990； [5]吳育華 ,杜綱 . 《 管理科學(xué)基礎(chǔ) 》 ，天津大學(xué)出版社。 1 線性規(guī)劃的模型與圖解法 一、 LP問題及其數(shù)學(xué)模型 例 1 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計劃。 ?可加性假定： 每個決策變量對目標函數(shù)和約束方程的影響是獨立于其他變量的，目標函數(shù)值是每個決策變量對目標函數(shù)貢獻的總和。 ?確定性假定： 線性規(guī)劃問題中的所有參數(shù)都是確定的參數(shù)。 例 2 某市今年要興建大量住宅 ,已知有三種住宅體系可以 大量興建，各體系資源用量及今年供應(yīng)量見下表： 要求在充分利用各種資源條件下使建造住宅的總面積為最 大 (即求安排各住宅多少 m2)，求建造方案。 課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的 A、 B、 C、 D四種養(yǎng)分。（列出模型） A B C D 價格 M 0 300 N 200 每頭日需 10 5 8 7 養(yǎng)分 飼料 課堂練習(xí) 某蓄場每日要為每頭牲畜購買飼料，以使其獲取所需的 A、 B、 C、 D四種養(yǎng)分。（列出模型） A B C D 價格 M 0 300 N 200 每頭日需 10 5 8 7 養(yǎng)分 飼料 答案： 設(shè)購買 M飼料 x1， N飼料 x2 x1 +≥10 + ≥5 + ≥8 ≥7 x1 , x2≥0 . Min Z=300 x1 +200x2 思考題 月份 1 2 3 4 所需倉庫面積 15 10 20 12 表 12 表 13 合同租借期限 1個月 2個月 3個月 4個月 合同期內(nèi)的租費 2800 4500 6000 7300 單位： 100m2 單位；元 /100m2 解：設(shè) 表示捷運公司在第 i (i=1,2,3,4)月初簽訂的租期為 j (j=1,2,3,4)個月的倉庫面積的合同（單位為 100m2)。4,1(012201015.4132231432312322141323222114131214131211?? jixxxxxxxxxxxxxxxxxxxxxstij)(4 5 0 0)(2 8 0 0m i n 32221241312111 xxxxxxxZ ???????142313 7 3 0 0)(6 0 0 0 xxx ???目標函數(shù) 約束條件 二、線性規(guī)劃的圖解法 1. 步驟 （ 1）作約束的圖形 ——可行域 可行解的集合 ① 先作非負約束 ②再作資源約束 9x1+4x2=360 4x1+5x2=200 3x1+10x2=300 公共部分，即為可行域 例：煤電油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 . x1 x2 40 20 60 80 100 20 40 60 80 100 0 （ 2）作目標函數(shù)的等值線 ① 給 z不同的值，作相應(yīng)直線，判斷出 z增大時，直線的移動方向 ② 將直線向增大方向移動，直至可行域邊界，交點 X*即為最優(yōu)解。 即沒有凹入的部分；沒有空洞。 A B C D 從圖解法中我們了解到以下事實： ①若 LP問題的可行域存在，則可行域一定是凸集。 思路： ①最優(yōu)解先在可行域中找。） ②最優(yōu)解在可行域的極點中找。 三、 線性規(guī)劃應(yīng)用舉例與軟件求解 例 1 （ 下料問題） 某工廠要做 100套鋼架，每套用長為 m, m, m的圓鋼各一根。已知原料每根長 m，問：應(yīng)如何下料，可使所用原料最省？ 方案 余料 m m 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 50 10 30 2x1 + x2 + x3 + x4 ≥ 100 2x2 + x3 + 3x5 + 2x6 + x7 ≥ 100 x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 ≥ 100 x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0 設(shè) x1,x2,x3,x4,x5,x6,x7,x8 分別為上述 8種方案下料的原材料根數(shù)， 建立如下的 LP模型： 最優(yōu)解為： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0 min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ?????. 余料 方案 2 0 1 Ⅰ 1 2 0 Ⅱ 1 1 1 Ⅲ 1 0 3 0 Ⅳ 0 3 0 Ⅴ 0 2 2 Ⅵ 0 1 3 Ⅶ 0 0 4 Ⅷ 第二節(jié) 單純形法 單純形法是求解線性規(guī)劃的主要算法， 1947 年由美國斯坦福大學(xué)教授丹捷格（ ） 提出。 用單純形法求解線性規(guī)劃的前提是先將模 型化為標準型： ??????0..XbAXtsCXM a x z 標準型的特征： Max型、等式約束、非負約束 一、單純形法的預(yù)備知識 。 )(xf)(xf?*x注意： Min型化為 Max型求解后，最優(yōu)解不變，但最優(yōu)值差負號。而這 個松弛量也是變量，記為 X3 ，則有 36049 321 ??? xxxX3稱為松弛變量。 練習(xí)：請將例 1的約束化為標準型 ??????????????0,3 0 01032 0 0543 6 049..21212121xxxxxxxxts解：增加松弛變量 則約束化為 ,543 xxx?????????????????0,300 10320224360 49..54321521421321xxxxxxxxxxxxxxts易見，增加的松弛變量的系數(shù)恰構(gòu)成一個單位陣 I。 3) 當模型中有某變量 xk 沒有非負要求， 稱 為自由變量 , 則可令 0, ////// ???kkkkk xxxxx化為標準型。 為基變量。 為非基變量，或自由變量。 TX )5,24,15,0,0(0 ?若對（ 1）式中的變量再加上非負限制 ?????????????2152142352624515xxxxxxxx?????????????????5,105242615552142132?ixxxxxxxxxi其解為 ?????????????????5,105262451521