運籌學全部課件

1、第1講 目錄課程簡介CH0 緒論CH1 線性規(guī)劃及單純形法 1.1 線性規(guī)劃問題及其數(shù)學模型 1.2 線性規(guī)劃問題的解 1.3 線性規(guī)劃的單純形法 1.4 單純形表 1.5 單純形法應(yīng)用的幾個問題 1.6 線性規(guī)劃建模舉例課程簡介課程性質(zhì)：學科必修課先修課程：高等數(shù)學、線性代數(shù)、概率論與數(shù)理統(tǒng) 計學分：4學時: 64（116周，每周4學時）考核方式：閉卷考試 成績由三部分組成:理論考試成績(80%)、平時成績（含考勤、課堂紀律、課堂提問、平時作業(yè)）(20%)。教材：胡運權(quán) 主編. 運籌學教程（第4版）. 北京：清華大學出版社,2012.11.課程簡介參考文獻： （1）運籌學教材編寫組編著. 運

2、籌學.北京：清華大學出版社，1990年9月.（2）郭耀煌等編.運籌學原理與方法.成都：西南交通大學出版社，1994年9月（3） WAYNE L.WINSTON. Operations Research (Mathematical Programming). 清華大學出版社(影印版) (4) Frederic S.Hillier. 運籌學導論(第8版).清華大學出版社(影印版) . 課程簡介教學目的 1 、使學生掌握若干運籌學的基本模型，為進一步學習IE的其它專業(yè)課程奠定基礎(chǔ);同時也為進一步研究IE方向之一的運籌學(OR)打下基礎(chǔ)。 2 、使學生初步掌握將實際管理問題形成運籌學模型的方法與技巧。

3、 3 、使學生初步具備運用軟件求解重要的運籌學模型的能力，會使用所學軟件解決實際的經(jīng)濟管理問題。 4 、注重理論與應(yīng)用并重，兼顧以理論與方法為主的學生（以不低于研究生入學考試水平為要求）。 課程簡介教學要求 (1)課前要預習、上課思路要跟上、課后認真完成作業(yè)（要求各位同學準備標準的作業(yè)本）、認真完成案例及實驗。 (2)基本思路：模型、算法及原理（必要時復習相關(guān)的數(shù)學知識）、建模與求解（包括軟件的應(yīng)用） (3) 本課程將通過重點講授原理方法、上機解題、個人研究與小組討論相結(jié)合的案例分析等環(huán)節(jié)，培養(yǎng)學生全局優(yōu)化的思想，使學生掌握若干類常用的運籌學模型，并能用其解決經(jīng)濟管理中的復雜問題。0.1 運籌

4、學的定義、發(fā)展與應(yīng)用簡介1 運籌學的定義(不唯一)運籌學簡稱 OR（美）Operations Research（英）Operational Research 按照原意應(yīng)譯為運作研究或作戰(zhàn)研究。運用科學的數(shù)量方法主要是數(shù)學模型研究對人力、物力進行合理籌劃和運用，尋找管理及決策最優(yōu)化的綜合性學科。 我國科學家把它譯成“運籌學”，“運籌”一詞出于史記：漢高祖本紀：運籌策帷幄之中，決勝千里之外。 關(guān)于OR的不同定義Operations Research (or, often,management science) means a scientific approach to decision maki

5、ng, which seeks to determine how best to design and operate a system, usually under conditions requiring the allocation of scarce resources.2 發(fā)展簡史運籌學思想的出現(xiàn)可以追溯到很早“田忌齊王賽馬”（對策論）、孫子兵法等都體現(xiàn)了優(yōu)化的思想。 “運籌學”這一名詞最早出現(xiàn)在第二次世界大戰(zhàn)期間 美、英等國家的作戰(zhàn)研究小組為了解決作戰(zhàn)中所遇到的許多錯綜復雜的戰(zhàn)略、戰(zhàn)術(shù)問題而提出的。數(shù)學對運籌學的作用是有關(guān)理論和方法的研究基礎(chǔ)，是建立運籌學模型的工具。 計算機的發(fā)展

6、，促進運籌學的進一步發(fā)展高速、可靠的計算是運籌學解決問題的基本保障。3 應(yīng)用領(lǐng)域運籌學能夠?qū)?jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。通常以最優(yōu)、最佳等作為決策目標，避開最劣的方案。在軍事，生產(chǎn)、決策、運輸、存儲、排隊等經(jīng)濟管理領(lǐng)域有著廣泛的應(yīng)用。3 應(yīng)用領(lǐng)域人事管理：對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才評價體系等。 市場營銷：廣告預算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等。3 應(yīng)用領(lǐng)域 財務(wù)和會計：包括預測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等。 其他： 設(shè)備維修、更新，項目選擇、評價，工程優(yōu)化設(shè)

7、計與管理等。組織應(yīng)用Interface期刊號 每年節(jié)支（美元）聯(lián)合航空公司滿足乘客需求前提下,以最低成本進行訂票及安排機場工作班次1-2/1986600萬Citgo石油優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營銷1-2/19877000萬荷馬特發(fā)展公司（Homart Development Co.）優(yōu)化商業(yè)區(qū)和辦公樓銷售程序1-2/19874000萬AT&T 優(yōu)化商業(yè)用戶的電話銷售中心選址1-2/19904.06億 ，更多銷售標準品牌公司控制成品庫存（制定最優(yōu)再訂購點和訂購量，確保安全庫存）12/1981380萬施樂公司通過戰(zhàn)略調(diào)整，縮短維修機器的反應(yīng)時間和改進維修人員的生產(chǎn)率11/1975第二部分生產(chǎn)

8、率提高50%以上寶潔公司重新設(shè)計北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場進入速度1-2/19972億法國國家鐵路制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運營量1-2/19981500萬更多年收入Delta航空公司進行上千個國內(nèi)航線的飛機優(yōu)化配置來最大化利潤1-2/19941億IBM重組全球供應(yīng)鏈，保持最小庫存的同時滿足客戶需求1-2/2000第一年7.5億Merit青銅制品公司安裝統(tǒng)計銷售預測和成品庫存管理系統(tǒng)，改進客戶服務(wù)1-2/1993更優(yōu)的服務(wù)OR應(yīng)用的成功例子 0.2 運籌學與工業(yè)工程泰勒時代的IE叫傳統(tǒng)IE或經(jīng)典IE。（工作研究等）現(xiàn)代工業(yè)工程以系統(tǒng)工程和運籌學為理論基礎(chǔ)，以計算機為工具。20

9、世紀40年代運籌學的發(fā)展豐富了工業(yè)工程的內(nèi)涵。同時OR成為IE重要的研究領(lǐng)域,如國外大學和清華IE系.大學名稱IE研究方向清華大學運籌與物流生產(chǎn)工程人因與工效學 佐治亞理工大學Georgia Institute of Technologyoptimization, stochastic systems, manufacturing and logistics, simulation, statistics, natural systems, economic decision analysis, and human-integrated systems analysis.密歇根大學Univer

10、sity of Michigan Operations Research Management Engineering Financial Engineering Ergonomics, Human Performance, and Occupational Safety Production/Manufacturing/Distribution Systems Quality Engineering and Applied Statistics 普度大學Purdue UniversityHuman Factors Manufacturing Operations Research Produ

11、ction Systems OR與IE0.3 運籌學的主要分支及本課程的講授內(nèi)容運籌學是一門應(yīng)用性學科，它主要是應(yīng)用定性分析和定量分析相結(jié)合的方法，通過建立實際問題的數(shù)學模型，應(yīng)用合適的優(yōu)化算法對模型進行求解，從而解決實際問題。運籌學的內(nèi)容很多，一般認為有以下分支：線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、網(wǎng)絡(luò)計劃、存儲論、排隊論、目標規(guī)劃、決策分析、對策（博弈論）等。講授內(nèi)容教學內(nèi)容 CH0 緒論 CH1 線性規(guī)劃及單純形法 CH2 線性規(guī)劃的對偶理論與靈敏度分析 CH3 運輸問題 CH4 整數(shù)規(guī)劃 CH5 動態(tài)規(guī)劃 CH6 圖與網(wǎng)絡(luò)方法 CH7 網(wǎng)絡(luò)計劃 CH8 目標規(guī)劃 C

12、H9 排隊論 CH10 對策論 CH11 決策分析 CH12 存貯論（庫存模型） 0.4 運籌學研究的基本特征與基本方法1、運籌學研究的基本特點：系統(tǒng)的整體優(yōu)化多學科的配合模型方法的應(yīng)用1）系統(tǒng)的整體觀念 系統(tǒng)是由相互關(guān)聯(lián)、相互制約、相互作用的一些部分組成的具有某種功能的有機整體。2）多學科的綜合 系統(tǒng)常常涉及到很多領(lǐng)域,運籌學研究中需吸收來自不同領(lǐng)域、具有不同經(jīng)驗和技能的專家。3）模型方法的應(yīng)用 運籌學研究的系統(tǒng)往往不能搬到實驗室來,代替的方法是建立這個問題的模型。、運籌學解決問題的步驟1）問題的分析；2）模型的建立3）模型的求解；4）解的檢驗5）解的有效控制；6）方案的實施。真實系統(tǒng)系統(tǒng)分

13、析問題描述模型建立與修改模型求解與檢驗結(jié)果分析與實施數(shù)據(jù)準備CH1 線性規(guī)劃及單純形法1.1 線性規(guī)劃問題及其數(shù)學模型1.2 線性規(guī)劃問題的解1.3 線性規(guī)劃的單純形法1.4 單純形表1.5 單純形法應(yīng)用的幾個問題1.6 線性規(guī)劃建模舉例1.1 線性規(guī)劃問題及其數(shù)學模型一、線性規(guī)劃問題 在生產(chǎn)管理和經(jīng)營活動中經(jīng)常需要解決：如何合理地利用有限的資源（人力、物力、財力等 ），以得到最大的效益。生產(chǎn)計劃問題如何合理使用有限的人力，物力和資金，使得收到最好的經(jīng)濟效益。如何合理使用有限的人力，物力和資金，以達到最經(jīng)濟的方式，完成生產(chǎn)計劃的要求。1.1 線性規(guī)劃問題及其數(shù)學模型例1-1 某工廠生產(chǎn)A,B兩

14、種產(chǎn)品,若生產(chǎn)A產(chǎn)品每噸需煤9噸,木材4立方米,人力3個勞動日,生產(chǎn)B產(chǎn)品每噸需煤4噸,木材5立方米,人力10個勞動日。已知A,B兩種產(chǎn)品每噸的價格分別為700元和1200元,并知該廠現(xiàn)有的資源為：煤360噸,木材200立方米,可提供人力300個勞動日,試問應(yīng)生產(chǎn)A,B產(chǎn)品各多少噸,能使該廠的產(chǎn)值最高？解 先將題中有關(guān)數(shù)據(jù)列為下表 產(chǎn)品 原材料 A B 資源 煤94360 木材45200 人力310300 單價7001200設(shè)計劃生產(chǎn)A,B產(chǎn)品分別為 噸,產(chǎn)值為Z元,該問題的數(shù)學模型如下： 稱（1-1）為目標函數(shù),（1-2）（1-5）為約束條件（其中s.t是subject to的縮寫,可譯為受

15、約束于）。 這是一個典型的利潤最大化的生產(chǎn)計劃問題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subject to”的縮寫，表示“滿足于”。 因此，上述模型的含義是：在給定條件限制下，求使目標函數(shù)z達到最大的x1 ,x2 的取值。 例1-2:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500目標函數(shù) Max

16、z =1500 x1+2500 x2約束條件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0 產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500線性規(guī)劃模型的三要素3.約束條件：為實現(xiàn)優(yōu)化目標需受到的限制，用決策變量的等式或不 等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標函數(shù)：需優(yōu)化的量，即欲達的目標，用決策變量的表達式表示；例1 . 營養(yǎng)配餐問題 假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和

17、市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最小？各種食物的營養(yǎng)成分表解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為： min S=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0以上例題的共同特征： 每一個問題都用一組決策變量表示某一方案； 這組決策變量的值就代表一個具體方案，一般這些變量取值是非負的。 存在一定的約束條件，這些約

18、束條件用一組線性等式或不等式來表示。 都有一個要達到的目標，它可用決策變量的線性函數(shù)即目標函數(shù)來表示，按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。 由于目標函數(shù)和約束條件都是自變量的線性函數(shù)，故稱這各規(guī)劃問題為線性規(guī)劃問題。其他典型問題：合理下料問題運輸問題生產(chǎn)的組織與計劃問題投資證券組合問題分派問題生產(chǎn)工藝優(yōu)化問題二、線性規(guī)劃的數(shù)學模型 Max（Min） z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn （ =, ）b1 a21x1 + a22x2 + + a2nxn （=, ）b2 am1x1 + am2x2 + + amnxn （=, ）bm x1 ，x2 ， ，xn 0s.t.在線性規(guī)劃的數(shù)學模型中有：目標函數(shù);約束條件;決策變量的非負約束條件。線性規(guī)劃問題隱含的假定：比例性假定：決策變量變化引起的目標函數(shù)的改變量和決策變量的改變量成比例，同樣，每個決策變量的變化引起約束方程左端值的改變量和該變量