教案1-緒論及線模

1、運(yùn)籌學(xué) (OR)(美Operations Research)(英 Operational Research)11 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)是運(yùn)用籌劃的科學(xué)，原意“作戰(zhàn)研究”或“運(yùn)用研究”。一、 緒論20.運(yùn)籌學(xué)的三個(gè)來源是軍事、管理和經(jīng)濟(jì)軍事 特點(diǎn)是：定量化、系統(tǒng)化方法迅速發(fā)展；采集真實(shí)的實(shí)際數(shù)據(jù)；多學(xué)科密切協(xié)作；解決方法滲透物理學(xué)的思想。管理 生產(chǎn)配置問題、原材料的合理利用、運(yùn)輸問題等 生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法經(jīng)濟(jì) 對策論與經(jīng)濟(jì)行為1.Morse小組領(lǐng)導(dǎo)的運(yùn)籌學(xué)小組目標(biāo)：打破德軍對英吉利海峽的封鎖建議：用飛機(jī)代替艦艇投擲水雷，起爆深度由100米改為25米，當(dāng)敵艦剛下潛時(shí)攻擊； 運(yùn)送物資的船

2、隊(duì)及護(hù)衛(wèi)艦的編隊(duì)由小規(guī)模、多批次改為大規(guī)模、少批次。丘吉爾采納了建議英國戰(zhàn)斗機(jī)援法德軍突破馬奇諾防線，法軍節(jié)節(jié)敗退，英軍參與抗德。英軍的戰(zhàn)機(jī)均在法國上空與德軍作戰(zhàn)，指揮維護(hù)在法國。法國請求增援10中隊(duì)，邱吉爾同意。但運(yùn)籌學(xué)小組認(rèn)為：按現(xiàn)在的方式，英軍的援法戰(zhàn)機(jī)兩周內(nèi)會全軍覆滅；不增加戰(zhàn)機(jī)，而應(yīng)以英國本土為基地與德軍戰(zhàn)斗，使局面大為改觀。31.基本思想 田忌賽馬 齊王 田忌 齊王 田忌 上 上 上 上 中 中 中 中 下 下 下 下 實(shí)力 結(jié)果 “史記高祖本紀(jì)”中劉邦語：“夫運(yùn)籌帷幄之中，決勝于千里之外”。41917年愛爾朗的排隊(duì)論公式。 1939年英國成立第一個(gè)運(yùn)籌學(xué)工作小組，從事防空預(yù)警系統(tǒng)

3、的研制（研究如何合理運(yùn)用雷達(dá)），使原先平均擊落一架敵機(jī)要發(fā)2萬發(fā)炮彈改善為只要發(fā)4千發(fā)炮彈。1939年前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型，1960年最佳資源利用的經(jīng)濟(jì)計(jì)算，獲諾貝爾獎。 1942年美國成立運(yùn)籌學(xué)工作小組，研究戰(zhàn)斗行動效能，行動方式。1947年美國數(shù)學(xué)家，提出線性規(guī)劃模型及單純形算法戰(zhàn)爭結(jié)束，Mores和Kimball合著第一部運(yùn)籌學(xué)專著“運(yùn)籌學(xué)的方法”。戰(zhàn)后，運(yùn)籌學(xué)的應(yīng)用領(lǐng)域從軍事擴(kuò)展到其它各領(lǐng)域。2.重要事件51948年英國成立運(yùn)籌學(xué)學(xué)會1952年美國成立運(yùn)籌學(xué)學(xué)會1956年法國成立運(yùn)籌學(xué)學(xué)會1959年英、美、法成立運(yùn)籌學(xué)聯(lián)合會 我國50年代引入運(yùn)籌學(xué)，1982年加入世界

4、運(yùn)籌學(xué)聯(lián)合會由于計(jì)算機(jī)的發(fā)展和大系統(tǒng)的要求，越來越重視定性定量相結(jié)合、人機(jī)交互算法。3.學(xué)會組織62 運(yùn)籌學(xué)的性質(zhì)和內(nèi)容 由一支綜合性的隊(duì)伍，采用科學(xué)的方法，為一些涉及到有機(jī)系統(tǒng)（人-機(jī)）的控制系統(tǒng)問題提供解答，為該系統(tǒng)的總目標(biāo)服務(wù)的學(xué)科。錢學(xué)森 運(yùn)用科學(xué)方法來解決工業(yè)、商業(yè)、政府、國防等部門里有關(guān)人力、機(jī)器、物資、金錢等大型系統(tǒng)的指揮或管理中所出現(xiàn)的復(fù)雜問題的一門學(xué)科。其目的是“幫助管理者以科學(xué)方法確定其方針和行動”英國運(yùn)籌學(xué)會 運(yùn)籌學(xué)是應(yīng)用系統(tǒng)的、科學(xué)的、數(shù)學(xué)分析的方法，通過建模、檢驗(yàn)和求解數(shù)學(xué)模型而獲得最優(yōu)決策的科學(xué)。近代運(yùn)籌學(xué)工作者1.運(yùn)籌學(xué)的定義72.性質(zhì)追求的目標(biāo)是整個(gè)組織或系統(tǒng)的

5、最佳行動路線強(qiáng)調(diào)定量的手法以軟科學(xué)研究軟系統(tǒng)，定性與定量相結(jié)合，多學(xué)科交叉83.分支 規(guī)劃論線性規(guī)劃、目標(biāo)規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、組合規(guī)劃等 圖與網(wǎng)絡(luò) 存儲論 排隊(duì)論 對策論 決策論 仿真 馬爾科夫過程 可靠性 多目標(biāo)規(guī)劃 93 運(yùn)籌學(xué)的工作步驟1. 提出和形成問題。即要弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)；2. 建立模型。即把問題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來； 3. 求解。用各種手段( 主要是數(shù)學(xué)方法，也可用其他方法 )將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要求可由決策者提出；4. 解的檢驗(yàn)

6、。首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反應(yīng)現(xiàn)實(shí)問題；5. 解的控制。通過控制解的變化過程決定對解是否要作一定的改變；6. 解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清楚用法、在實(shí)施中可能產(chǎn)生的問題和修改。104 本課程的要求本課程的授課對象是管理科學(xué)與工程類及交通運(yùn)輸類專業(yè)本科生，屬管理類專業(yè)技術(shù)基礎(chǔ)必修課。學(xué)生通過學(xué)習(xí)該課程，應(yīng)了解管理運(yùn)籌學(xué)對優(yōu)化決策問題進(jìn)行定量研究的特點(diǎn)，理解線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)、排隊(duì)論和庫存論等分支的基本優(yōu)化原理，掌握其中常用的模型和算法，具有一定的建模能力。先修課程主要為線性代數(shù)和概率統(tǒng)計(jì)，學(xué)生對它們的掌握程度直接影響

7、本課程的學(xué)習(xí)，所以要求學(xué)生課前要做必要的復(fù)習(xí)。學(xué)習(xí)方法：理解、掌握基本理論和方法的基礎(chǔ)上，適當(dāng)作些習(xí)題。參考書：其他版本的管理運(yùn)籌學(xué)11二. 線性規(guī)劃 (LP )( Linear Programming)第一章 線性規(guī)劃與單純形法1947年由美國空軍G.B.Dantzig提出。本部分是課程的最重要部分121 線性規(guī)劃問題及其數(shù)學(xué)模型1311 問題的提出14利潤最大 目標(biāo)函數(shù) max z = 2x1+ 3x215例2 某工廠用鋼與橡膠生產(chǎn)3種產(chǎn)品A、B、C，有關(guān)資料如下表404524332231 A B C單位產(chǎn)品利潤單位產(chǎn)品橡膠量單位產(chǎn)品鋼消耗量產(chǎn)品已知每天可獲得100單位的鋼和120單位橡膠

8、，問每天生產(chǎn)A、B、C各多少使總利潤最大？解：設(shè)x1，x2， x3分別為A、B、C日產(chǎn)量，則有 約束條件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30稱x1，x2 ，x30為決策變量 目標(biāo)函數(shù)： max z=40 x1+45x2 +24x3162萬m31.4萬m3172萬m31.4萬m318x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24o.向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后交點(diǎn)，這種點(diǎn)就對應(yīng)最優(yōu)解。 19線性規(guī)劃問題解的存在情況：(1)存在唯一最優(yōu)

9、解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例120（2）有無窮多最優(yōu)解 若將例1目標(biāo)函數(shù)變?yōu)?max z = 2x1+ 4x2，則問題變得存在無窮多最優(yōu)解。如圖x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q221（3）有無界解( 無有限最優(yōu)解或無最優(yōu)解 ) z（4）無可行解（可行域?yàn)榭占┳⒁猓簺]有存在有限多個(gè)解的情況可行域有界時(shí)必有最優(yōu)解，無界時(shí)不一定無最優(yōu)解22 用圖解法求下面問題的解12無界不可行2313 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 為了求解LP問題，必須統(tǒng)一其模型，本課程選

10、用標(biāo)準(zhǔn)型式為max z =c1x1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3)其中bi 0，（i =1，2，m）一般m 0。24標(biāo)準(zhǔn)型的簡寫形式:max z =c1x1 + c2x2 + cnxn (1.1)s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = b

11、m x1，x2，xn 0 (1.3)用求和符號表示25用矩陣描述為： max z =CX AX = b X 0= (P1，P2，Pn)；a11 a12 a1na21 a22 a2n am1 am2 amnA=稱 A 為約束條件的m n 階系數(shù)矩陣，一般A的秩為m。0 =00026用向量表示：X=x1x2xnPj =a1ja2jamjb=b1b2bm向 量 Pj 對 應(yīng) 的 決 策 變 量 為 xj 。27b1b2 bm (p1,p2, ,pn)Pjxj=b a11 a12 a1n a21 a22 a2n am1 am2 amnx1x2 xn=xj0 j=1,nx1x2 xnMax z=x1x2

12、 xn (c1 , c2, ,cn )=cjxj=CX=aijxj =bi i=1,mAX = b X 0 b28 x1 + 2 x2 84 x1 16 4 x2 12x1，x2 0 max z = 2x1+ 3x2 + 0 x3 + 0 x4+ 0 x5標(biāo)準(zhǔn)型：例3將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。 max z = 2x1+ 3x2 所加松弛變量x3，x4，x5表示沒有被利用的資源，當(dāng)然也沒有利潤，在目標(biāo)函數(shù)中其系數(shù)應(yīng)為零；即c3 ，c4 ，c5 = 0。 x1+ 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 + x5 =12 x1，x2，x3，x4，x5 029 x1 + x

13、2 + x3 7 x1 x2 + x3 23 x1+ x2 +2 x3 = 5x1，x2 0，x3為無符號約束例4將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型 min z = x1 +2x2 3x3解：用x4 - x5 替換x3 ，令z = -z x1 + x2 + (x4 - x5) + x6 = 7 x1 x2 + (x4 - x5) - x7 = 23x1 + x2 +2(x4 - x5) = 5 x1，x2，x4，x5，x6，x7 0max z= x1 2x2 + 3(x4 - x5)+0 x6+0 x7用標(biāo)準(zhǔn)型求最優(yōu)解后，再回到原變量。30練習(xí): 將下列線性規(guī)劃問題化成標(biāo)準(zhǔn)型 1、 min Z= 5x1+ x2 + x3 3x1+ x2 - x37 - 3x1 + x2 6 s.t x1 + 2x2 4 x2-3, x1無限制2、 max Z= -x1+4 x2 s.t x1- 2x2+4x3-6 x2+3x3 = 3 x1 ,x20, x3無限制31復(fù)習(xí)線性代數(shù)內(nèi)容:列向量 x=(x1，x2，xn）T為n維列向量。xRn行向量 x=(x1，x2，xn）為n維列向量。xRn矩陣(向量)運(yùn)算規(guī)則 加減乘、求逆運(yùn)算 結(jié)合律 分