管理運籌學教案1_緒論及線性規(guī)劃模型【企業(yè)經營管理推薦】

1、趙 鵬 徐 彬 ：51687005辦公地點：8711郵箱2022-3-20管理運籌學課程組21 運籌學的由來一、緒論 2022-3-20管理運籌學課程組32022-3-20管理運籌學課程組42022-3-20管理運籌學課程組5重要事件: 古代樸素的運籌思想 1917年愛爾朗的排隊論公式。 1939年英國成立第一個運籌學工作小組，從事防空預警系統(tǒng)的研制（研究如何合理運用雷達），使原先平均擊落一架敵機要發(fā)2萬發(fā)炮彈改善為只要發(fā)4千發(fā)炮彈。 1939年前蘇聯(lián)的康托洛維奇提出類似線性規(guī)劃模型， 1960年最佳資源利用的經濟計算,獲諾貝爾獎。 1942年美國成立運籌學工作小組,研究戰(zhàn)斗行動效能,行動方式

2、。 1947年美國數(shù)學家，提出線性規(guī)劃模型及單純形算法 戰(zhàn)爭結束，Mores和Kimball合著第一部專著“運籌學的方法”。 戰(zhàn)后，運籌學的應用領域從軍事擴展到其它各領域。2022-3-20管理運籌學課程組6學會組織 1948年英國成立運籌學學會 1952年美國成立運籌學學會 1956年法國成立運籌學學會 1959年英、美、法成立運籌學聯(lián)合會 我國50年代引入運籌學，1982年加入世界運籌學聯(lián)合會(1956年時曾使用“運用學”，57年定名為“運籌學”)2022-3-20管理運籌學課程組72 運籌學的性質和內容 由一支綜合性的隊伍，采用科學的方法，為一些涉及到有機系統(tǒng)（人-機）的控制系統(tǒng)問題提供

3、解答，為該系統(tǒng)的總目標服務的學科。錢學森 運用科學方法來解決工業(yè)、商業(yè)、政府、國防等部門里有關人力、機器、物資、資金等大型系統(tǒng)的指揮或管理中所出現(xiàn)的復雜問題的一門學科。其目的是“幫助管理者以科學方法確定其方針和行動”英國運籌學會 運籌學是應用系統(tǒng)的、科學的、數(shù)學分析的方法，通過建模、檢驗和求解數(shù)學模型而獲得最優(yōu)決策的科學。近代運籌學工作者1.運籌學的定義 “運籌學是在實行管理的領域，運用數(shù)學方法，對需要進行管理的問題統(tǒng)籌規(guī)劃，作出決策的一門應用科學。” 與2022-3-20管理運籌學課程組82.特點(1)運籌學已被廣泛應用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織內的統(tǒng)籌協(xié)調問題，故其應用不受行

4、業(yè)、部門之限制；(2)運籌學既對各種經營進行創(chuàng)造性的科學研究，又涉及到組織的實際管理問題，它具有很強的實踐性，最終應能向決策者提供建設性意見，并應收到實效；(3)它以整體最優(yōu)為目標，從系統(tǒng)的觀點出發(fā)，力圖以整個系統(tǒng)最佳的方式來解決該系統(tǒng)各部門之間的利害沖突。對所研究的問題求出最優(yōu)解，尋求最佳的行動方案，所以它也可看成是一門優(yōu)化技術，提供的是解決各類問題的優(yōu)化方法。 2022-3-20管理運籌學課程組9 規(guī)劃論線性規(guī)劃、目標規(guī)劃、非線性規(guī)劃、 整數(shù)規(guī)劃、動態(tài)規(guī)劃、組合規(guī)劃等 圖與網絡 存儲論 排隊論 對策論 決策論 仿真 馬爾科夫過程 可靠性 多目標規(guī)劃 2022-3-20管理運籌學課程組103

5、 運籌學的工作步驟1. 提出和形成問題。即要弄清問題的目標，可能的約束，問題的可控變量以及有關參數(shù)；2. 建立模型。即把問題中可控變量、參數(shù)和目標與約束之間的關系用一定的模型表示出來； 3. 求解。用各種手段(主要是數(shù)學方法，也可用其他方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復雜模型的求解需用計算機，解的精度要求可由決策者提出；4. 解的檢驗。首先檢查求解步驟和程序有無錯誤，然后檢查解是否反映現(xiàn)實問題；5. 解的實施。是指將解用到實際中必須考慮到實施的問題，如向實際部門講清楚用法、在實施中可能產生的問題和修改。2022-3-20管理運籌學課程組114 本課程的要求本課程的授課對象是管

6、理科學與工程類及交通運輸類專業(yè)本科生，屬管理類專業(yè)技術基礎必修課。 學生通過學習該課程，應了解管理運籌學對優(yōu)化決策問題進行定量研究的特點，理解線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、圖與網絡、排隊論等分支的基本優(yōu)化原理，掌握其中常用的模型和算法，具有一定的建模能力。 先修課程主要為線性代數(shù)和概率統(tǒng)計，學生對它們的掌握程度直接影響本課程的學習，所以要求學生課前要做必要的復習。 學習方法：理解、掌握基本理論和方法的基礎上，適當作些習題。 參考書：其他版本的管理運籌學 二. 線性規(guī)劃 (LP )( Linear Programming)本部分是課程的最重要部分2022-3-20管理運籌學課程組13本本節(jié)節(jié)重重

7、點點：線線性性規(guī)規(guī)劃劃模模型型的的特特點點線線性性規(guī)規(guī)劃劃解解的的存存在在情情況況線線性性規(guī)規(guī)劃劃標標準準型型線線性性規(guī)規(guī)劃劃解解的的基基本本概概念念（特特別別是是基基解解和和基基可可行行解解）1 線性規(guī)劃問題及其數(shù)學模型第一章 線性規(guī)劃與單純形法2022-3-20管理運籌學課程組141.1 問題的提出 例1某工廠計劃期內要安排生產、兩種產品，已知生產單位產品所需的設備臺時和A、B兩種原材料的消耗、以及可獲利潤如表所示，問應如何安排計劃使該工廠獲利最多？2022-3-20管理運籌學課程組15設設 x1、x2分別表示計劃期內產品分別表示計劃期內產品、的產量，、的產量， 建立數(shù)學模型：建立數(shù)學模型

8、： 設備臺時設備臺時 約束條件約束條件 s.t. x1 + 2x2 8 原材料原材料 A (Subject to) 4 x1 16 原材料原材料 B 4 x2 12 產品產量產品產量 x1，x2 0 可利用資源 設備 原材料 A 原材料 B140204 8 臺時 16kg 12kg 利潤23 ？元利潤最大 目標函數(shù) max z = 2x1+ 3x22022-3-20管理運籌學課程組16例2: 某工廠用鋼與橡膠生產3種產品A、B、C，有關資料如下表404524332231 A B C單位產品利潤單位產品橡膠量單位產品鋼消耗量產品已知每天可獲得100單位的鋼和120單位橡膠，問每天生產A、B、C各

9、多少使總利潤最大？解：設x1，x2， x3分別為A、B、C日產量，則有 約束條件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30稱x1，x2 ，x30為決策變量 目標函數(shù)： max z=40 x1+45x2 +24x32022-3-20管理運籌學課程組172萬m31.4萬m32022-3-20管理運籌學課程組18 設設 x1、x2 分別為第一、第二化工廠每天處理的工業(yè)污水量。分別為第一、第二化工廠每天處理的工業(yè)污水量。約束條件：約束條件： 第一化工廠到第二化工廠之間的污水含量要不大于第一化工廠到第二化工廠之間的污水含量要不大于 0. .

10、2 2% % (2 -(2 - x1) / 500 2 / 1000 流經第二化工廠后，河流中的污水含量仍不大于流經第二化工廠后，河流中的污水含量仍不大于 0. .2 2% %0.0. 8(2 -8(2 - x1) + ( (1. .4-4- x2) / 700 2 / 1000 污水處理量限制污水處理量限制 x1 2，x2 1. .4 4，x1 0，x2 0目標函數(shù)：目標函數(shù)： 要求兩廠用于處理工業(yè)污水的費用最小要求兩廠用于處理工業(yè)污水的費用最小 min z = 1000 x1+800 x22萬m31.4萬m32022-3-20管理運籌學課程組192022-3-20管理運籌學課程組20202

11、2-3-20管理運籌學課程組21 線線性性規(guī)規(guī)劃劃模模型型的的一一般般形形式式為為： max(min) z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn ( = , ) b1 a21x1 + a22x2 + a2nxn ( = , ) b2 ( (1 1.2 2) ) am1x1 + am2x2 + amnxn ( = , ) bm x1，x2，xn 0 (1.3) 求求解解線線性性規(guī)規(guī)劃劃問問題題的的任任務務是是：在在滿滿足足(1.2)、(1.3) 的的所所有有(x1，x2，xn)（可可行行解解）中中求求出出使使(1.1)達達到到最

12、最大大(小小)z 值值的的決決策策變變量量值值(x1*，x2*，xn*)（最最優(yōu)優(yōu)解解） 。2022-3-20管理運籌學課程組22例例 1 max max z z = 2 = 2x1 + 3x2 s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 2022-3-20管理運籌學課程組23max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24.向著目標函數(shù)的優(yōu)化方向平移等值線，直至得到

13、等值線與可行域的最后交點，這種點就對應最優(yōu)解。 2022-3-20管理運籌學課程組24線性規(guī)劃問題解的存在情況：(1)存在唯一最優(yōu)解max max z z = 2 = 2x1+ 3x2s.t. x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例12022-3-20管理運籌學課程組25（2）有無窮多最優(yōu)解 若將例1目標函數(shù)變?yōu)?max z = 2x1+ 4x2，則問題變得存在無窮多最優(yōu)解。如圖max max z z = 2 = 2x1+ 4x2s.t. x1 + 2 x

14、2 8 4 x1 16 4 x2 12 x1，x2 0 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q22022-3-20管理運籌學課程組26（3）有無界解( 無有限最優(yōu)解或無最優(yōu)解 ) z（4）無可行解（可行域為空集）注意：沒有存在有限多個解的情況可行域有界時必有最優(yōu)解，無界時不一定無最優(yōu)解2022-3-20管理運籌學課程組27 用圖解法求下面問題的解m ma ax x z z = = 2 2x1+ 2x2 s.t. x1 - x2 -1 -0.5x1 + x2 2 x1，x2 0 1m ma ax x z z = = x1+ x2 s.

15、t. x1 - x2 0 3x1 - x2 -3 x1，x2 0 2無界不可行2022-3-20管理運籌學課程組2813 線性規(guī)劃問題的標準形式 為了求解LP問題，必須統(tǒng)一其模型，本課程選用標準型式為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。2022-3-20管理運籌學課程組29標準型的簡寫形式:max z =c1x

16、1 + 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) njjjxczmax1 njijijbxa1 m1,2,.,i n,.,jxj210 用求和符號表示2022-3-20管理運籌學課程組30用矩陣描述為： max z =CX AX = b X 0= (P1，P2，Pn)；a11 a12 a1na21 a22 a2n am1 am2 amnA=稱 A 為約束條件的m n 階系數(shù)矩陣，一般A的

17、秩為m。0 =0002022-3-20管理運籌學課程組31用向量表示： n,jxbxPCXzmaxjnjjj101 其其中中: : )c ,c ,c(Cn21 X=x1x2xnPj =a1ja2jamjb=b1b2bm向 量 Pj 對 應 的 決 策 變 量 為 xj 。2022-3-20管理運籌學課程組32b1b2 bm (p1,p2, ,pn)Pjxj=b a11 a12 a1n a21 a22 a2n am1 am2 amnx1x2 xn=xj0 j=1,nx1x2 xnMax z=x1x2 xn (c1 , c2, ,cn )=cjxj=CX=aijxj =bi i=1,mAX = b

18、 X 0 b2022-3-20管理運籌學課程組33 將一般形式化為標準型式將一般形式化為標準型式將目標函數(shù)最小化變?yōu)榍竽繕撕瘮?shù)最大化將目標函數(shù)最小化變?yōu)榍竽繕撕瘮?shù)最大化 min z = CX max z = -C= -CX，其中，其中 z = =- - z ；將將不不等等式式約約束束變變?yōu)闉榈鹊仁绞郊s約束束 njnjimiimjijijijxbxxabxa110 ( 松松弛弛變變量量 ) 011 imnjnjiimjijijijxbxxabxa（剩剩余余變變量量 ）將將負負約約束束、無無符符號號約約束束變變量量變變?yōu)闉榉欠秦撠摷s約束束變變量量 xj 0 xj = =- - xj ， xj 0

19、xj 為為無無符符號號約約束束變變量量 xj = xj - - xj , , xj 0, xj 0 2022-3-20管理運籌學課程組34 x1 + 2 x2 84 x1 16 4 x2 12x1，x2 0 max z = 2x1+ 3x2 + 0 x3 + 0 x4+ 0 x5標準型：例3將例1的數(shù)學模型化為標準型。 max z = 2x1+ 3x2 所加松弛變量x3，x4，x5表示沒有被利用的資源，當然也沒有利潤，在目標函數(shù)中其系數(shù)應為零；即c3 ，c4 ，c5 = 0。 x1+ 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 + x5 =12 x1，x2，x3，x4，x5 02022-3-20管理運籌學課程組35 x1 + x2 + x3 7 x1 x2 + x3 23 x1+ x2 +2 x3 = 5x1，x2 0，x3為無符號約束例4將下述線性規(guī)劃問題化為標準型 min z = x1 +2x2 3x3解：用x4 - x5 替換x3 ，令z = -z x1 +