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

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

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

4、學(xué)的定義、發(fā)展與應(yīng)用簡介1 運(yùn)籌學(xué)的定義(不唯一)運(yùn)籌學(xué)簡稱 OR（美）Operations Research（英）Operational Research 按照原意應(yīng)譯為運(yùn)作研究或作戰(zhàn)研究。運(yùn)用科學(xué)的數(shù)量方法主要是數(shù)學(xué)模型研究對(duì)人力、物力進(jìn)行合理籌劃和運(yùn)用，尋找管理及決策最優(yōu)化的綜合性學(xué)科。 我國科學(xué)家把它譯成“運(yùn)籌學(xué)”，“運(yùn)籌”一詞出于史記：漢高祖本紀(jì)：運(yùn)籌策帷幄之中，決勝千里之外。 關(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ā)展簡史運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早“田忌齊王賽馬”（對(duì)策論）、孫子兵法等都體現(xiàn)了優(yōu)化的思想。 “運(yùn)籌學(xué)”這一名詞最早出現(xiàn)在第二次世界大戰(zhàn)期間 美、英等國家的作戰(zhàn)研究小組為了解決作戰(zhàn)中所遇到的許多錯(cuò)綜復(fù)雜的戰(zhàn)略、戰(zhàn)術(shù)問題而提出的。數(shù)學(xué)對(duì)運(yùn)籌學(xué)的作用是有關(guān)理論和方法的研究基礎(chǔ)，是建立運(yùn)籌學(xué)模型的工具。 計(jì)算機(jī)的發(fā)展

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

7、計(jì)與管理等。組織應(yīng)用Interface期刊號(hào) 每年節(jié)支（美元）聯(lián)合航空公司滿足乘客需求前提下,以最低成本進(jìn)行訂票及安排機(jī)場工作班次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億 ，更多銷售標(biāo)準(zhǔn)品牌公司控制成品庫存（制定最優(yōu)再訂購點(diǎn)和訂購量，確保安全庫存）12/1981380萬施樂公司通過戰(zhàn)略調(diào)整，縮短維修機(jī)器的反應(yīng)時(shí)間和改進(jìn)維修人員的生產(chǎn)率11/1975第二部分生產(chǎn)

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

9、世紀(jì)40年代運(yùn)籌學(xué)的發(fā)展豐富了工業(yè)工程的內(nèi)涵。同時(shí)OR成為IE重要的研究領(lǐng)域,如國外大學(xué)和清華IE系.大學(xué)名稱IE研究方向清華大學(xué)運(yùn)籌與物流生產(chǎn)工程人因與工效學(xué) 佐治亞理工大學(xué)Georgia Institute of Technologyoptimization, stochastic systems, manufacturing and logistics, simulation, statistics, natural systems, economic decision analysis, and human-integrated systems analysis.密歇根大學(xué)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 普度大學(xué)Purdue UniversityHuman Factors Manufacturing Operations Research Produ

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

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

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

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

15、約束于）。 這是一個(gè)典型的利潤最大化的生產(chǎn)計(jì)劃問題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subject to”的縮寫，表示“滿足于”。 因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù)z達(dá)到最大的x1 ,x2 的取值。 例1-2:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500目標(biāo)函數(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.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不 等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；例1 . 營養(yǎng)配餐問題 假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和

17、市場價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小？各種食物的營養(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以上例題的共同特征： 每一個(gè)問題都用一組決策變量表示某一方案； 這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的。 存在一定的約束條件，這些約

18、束條件用一組線性等式或不等式來表示。 都有一個(gè)要達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)即目標(biāo)函數(shù)來表示，按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。 由于目標(biāo)函數(shù)和約束條件都是自變量的線性函數(shù)，故稱這各規(guī)劃問題為線性規(guī)劃問題。其他典型問題：合理下料問題運(yùn)輸問題生產(chǎn)的組織與計(jì)劃問題投資證券組合問題分派問題生產(chǎn)工藝優(yōu)化問題二、線性規(guī)劃的數(shù)學(xué)模型 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ù)學(xué)模型中有：目標(biāo)函數(shù);約束條件;決策變量的非負(fù)約束條件。線性規(guī)劃問題隱含的假定：比例性假定：決策變量變化引起的目標(biāo)函數(shù)的改變量和決策變量的改變量成比例，同樣，每個(gè)決策變量的變化引起約束方程左端值的改變量和該變量