MBA運籌學(xué)培訓(xùn)課程(PPT 127頁).ppt

1,運籌學(xué),北京理工大學(xué)管理與經(jīng)濟學(xué)院吳祈宗教授,2,1、緒論2、線性規(guī)劃3、運輸問題4、動態(tài)規(guī)劃5、圖與網(wǎng)絡(luò)分析6、排隊論7、教學(xué)日歷,運籌學(xué)目錄,說明本教學(xué)課件是與教材緊密配合使用的，教材為：運籌學(xué)楊民助編著西安交通大學(xué)出版社，2000年6月參考書：運籌學(xué)清華大學(xué)出版社或其他的運籌學(xué)方面本科教材的相關(guān)內(nèi)容下面所標(biāo)注的頁號，均為本課程教材的頁號。例如：p123表示第123頁p31-34表示從第31頁到第34頁,3,緒論,運籌學(xué)（OperationalResearch)直譯為“運作研究”運籌學(xué)是運用科學(xué)的方法（如分析、試驗、量化等）來決定如何最佳地運營和設(shè)計各種系統(tǒng)的一門學(xué)科。運籌學(xué)對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。運籌學(xué)有廣泛應(yīng)用（可以自己找一些參考書看）運籌學(xué)的產(chǎn)生和發(fā)展（可以自己找一些參考書看）,4,運籌學(xué)解決問題的過程,1）提出問題：認(rèn)清問題2）尋求可行方案：建模、求解3）確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑4）評估各個方案：解的檢驗、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實施：回到實踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。,5,運籌學(xué)的分支,線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃多目標(biāo)規(guī)劃隨機規(guī)劃模糊規(guī)劃等,圖與網(wǎng)絡(luò)理論存儲論排隊論決策論對策論排序與統(tǒng)籌方法可靠性理論等,6,運籌學(xué)在工商管理中的應(yīng)用,生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、運輸工具的調(diào)度以及建廠地址的選擇等人事管理：對人員的需求和使用的預(yù)測，確定人員編制、人員合理分配，建立人才評價體系等市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等財務(wù)和會計：預(yù)測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等*設(shè)備維修、更新，項目選擇、評價，工程優(yōu)化設(shè)計與管理等,7,運籌學(xué)方法使用情況(美1983)（%）,8,運籌學(xué)方法在中國使用情況(隨機抽樣)（%）,9,運籌學(xué)的推廣應(yīng)用前景,據(jù)美勞工局1992年統(tǒng)計預(yù)測:運籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長百分比預(yù)測為73%,增長速度排到各項職業(yè)的前三位.結(jié)論:運籌學(xué)在國內(nèi)或國外的推廣前景是非常廣闊的工商企業(yè)對運籌學(xué)應(yīng)用和需求是很大的在工商企業(yè)推廣運籌學(xué)方面有大量的工作要做,10,學(xué)習(xí)運籌學(xué)要把重點放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，如一個方法的實質(zhì)是什么，為什么這樣做，怎么做等。自學(xué)時要掌握三個重要環(huán)節(jié)：1、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時參考其他有關(guān)書籍。一般每一本運籌學(xué)教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學(xué)習(xí)深入。但是，把時間過多放在參考資料上，會導(dǎo)致思路分散，不利于學(xué)好。2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。3、要學(xué)會做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會用精煉的語言來該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關(guān)知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻后的深入理解，把相關(guān)知識從更深入、廣泛的角度進行論述，則稱之為“把書讀厚”在建數(shù)學(xué)模型時要結(jié)合實際應(yīng)用，要學(xué)會用計算機軟件解決問題。,如何學(xué)習(xí)運籌學(xué)課程,返回目錄,11,各章節(jié)的重點、難點及注意事項,12,1、線性規(guī)劃,線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50 x1+100 x2約束條件：s.t.x1+x23002x1+x2400 x2250 x1,x20*看p7-9例1-1，1-2,例1.某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗以及資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？,13,1、線性規(guī)劃（續(xù)1.1）,1.1線性規(guī)劃的概念線性規(guī)劃的組成：目標(biāo)函數(shù)Maxf或Minf約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素,一般形式(p10-p11)目標(biāo)函數(shù)：Max（Min）z=c1x1+c2x2+cnxn約束條件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0,標(biāo)準(zhǔn)形式(p11-p15，例1-3)目標(biāo)函數(shù)：Maxz=c1x1+c2x2+cnxn約束條件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0*練習(xí)：p68-70習(xí)題11-1，1-2,14,1、線性規(guī)劃（續(xù)1.2）,1.2線性規(guī)劃問題解的概念及性質(zhì)熟悉下列一些解的概念（p15-16）可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。,圖解方法及各有關(guān)概念的意義（p16-20）看：圖解法步驟，例1-4，1-5，1-6，1-7，1-8，1-9下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。,單純形法的理論基礎(chǔ)（p20-30）1.2.3段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解1.2.4,1.2.5兩段應(yīng)注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解的四個定理，而對證明過程則可根據(jù)自己的數(shù)學(xué)基礎(chǔ)來掌握：基礎(chǔ)很好，可要求掌握；否則，也可略去不看。*習(xí)題：p70習(xí)題11-3，1-4,15,1、線性規(guī)劃（續(xù)1.2）,例1.目標(biāo)函數(shù)：Maxz=50 x1+100 x2約束條件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最優(yōu)解：x1=50，x2=250最優(yōu)目標(biāo)值z=27500,16,1、線性規(guī)劃（續(xù)1.3）,1.3單純形法利用單純形表的方法求解線性規(guī)劃重點(p30-451.3.1,1.3.2,1.3.3)此項內(nèi)容是本章的重點，學(xué)習(xí)中應(yīng)注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。,17,1、線性規(guī)劃（續(xù)1.3）,表格單純形法(p40-p45)考慮：bi0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0加入松弛變量：Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0,18,顯然，xj=0j=1,n;xn+i=bii=1,m是基本可行解對應(yīng)的基是單位矩陣。以下是初始單純形表：mm其中：f=-cn+ibij=cj-cn+iaij為檢驗數(shù)cn+i=0i=1,mi=1i=1an+i,i=1,an+i,j=0(ji)i,j=1,m,1、線性規(guī)劃（續(xù)1.3）,19,1、線性規(guī)劃（續(xù)1.3單純形法解題例）,例1。化標(biāo)準(zhǔn)形式：Maxz=50 x1+100 x2s.t.x1+x2+x3=3002x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x50最優(yōu)解x1=50 x2=250 x4=50（松弛標(biāo)量，表示原料A有50個單位的剩余）,20,注意：單純形法中，1、每一步運算只能用矩陣初等行變換；2、表中第3列的數(shù)總應(yīng)保持非負(fù)（0）；3、當(dāng)所有檢驗數(shù)均非正（0）時，得到最優(yōu)單純形表。,1、線性規(guī)劃（續(xù)1.3）,21,1、線性規(guī)劃（續(xù)1.3）,一般情況的處理及注意事項的強調(diào)（p45-55）1.3.4段主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例1-14例1-17掌握這些方法，同時進一步熟悉用單純形法解題?？紤]一般問題：bi0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0,22,1、線性規(guī)劃（續(xù)1.3）,大M法：引入人工變量xn+i0i=1,m;充分大正數(shù)M。得到，Maxz=c1x1+c2x2+cnxn+Mxn+1+Mxn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0顯然，xj=0j=1,n;xn+i=bii=1,m是基本可行解對應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足xn+i=0i=1,m則是原問題的最優(yōu)解；否則，原問題無可行解。,23,1、線性規(guī)劃（續(xù)1.3）,兩階段法：引入人工變量xn+i0，i=1,m；構(gòu)造，Maxz=-xn+1-xn+2-xn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0第一階段求解上述問題：顯然，xj=0j=1,n;xn+i=bii=1,m是基本可行解對應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足xn+i=0i=1,m則是原問題的基本可行解；否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。,24,1、線性規(guī)劃（續(xù)1.3）例題,例：（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40大M法問題（LP-M）Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60兩階段法：第一階段問題（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,25,1、線性規(guī)劃（續(xù)1.3）大M法例,大M法（LP-M）,得到最優(yōu)解：(25/3，10/3，0，11)T最優(yōu)目標(biāo)值：112/3,26,1、線性規(guī)劃（續(xù)1.3）兩階段法例,第一階段（LP-1）,得到原問題的基本可行解：(0，15/7，25/7，52/7)T,27,1、線性規(guī)劃（續(xù)1.3）兩階段法例,第二階段把基本可行解填入表中,得到原問題的最優(yōu)解：(25/3，10/3，0，11)T最優(yōu)目標(biāo)值：112/3,28,1、線性規(guī)劃（續(xù)1.3）,1.3.5矩陣描述此段為選讀，有困難者可不看。1.3.6段單純形迭代過程中的幾點注意事項是對有關(guān)內(nèi)容的強調(diào)和補充，要認(rèn)真學(xué)習(xí)、理解。*習(xí)題：p70-71習(xí)題11-5，1-6,29,1.4線性規(guī)劃應(yīng)用建模（p55-68）本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個方面介紹建模對未來是很有用的，應(yīng)認(rèn)真對待。除了教材上的例子之外，還有許多其它應(yīng)用：*合理利用線材問題：如何下料使用材最少*配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤*投資問題：從投資項目中選取方案，使投資回報最大*產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大*勞動力安排：用最少的勞動力來滿足工作的需要*運輸問題：如何制定調(diào)運方案，使總運費最小*下面是一些建模的例子，有興趣者，可作為練習(xí)。這些例子有一定的難度，做起來會有一些困難。*習(xí)題：p72-73習(xí)題11-7，1-8，1-9，1-10,1、線性規(guī)劃（續(xù)1.4）,返回目錄,30,例某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?,例：人力資源分配的問題,31,解：設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6約束條件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,例：人力資源分配的問題（續(xù)）,32,例、明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？,例：生產(chǎn)計劃的問題,33,解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤：利潤=售價-各成本之和可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Max15x1+10 x2+7x3+13x4+9x5約束條件：s.t.5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50,例：生產(chǎn)計劃的問題（續(xù)）,34,例、永久機械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序?？稍贏、B的任何規(guī)格的設(shè)備上加工；可在任意規(guī)格的A設(shè)備上加工，但對B工序，只能在B1設(shè)備上加工；只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應(yīng)如何制定產(chǎn)品加工方案？,例：生產(chǎn)計劃的問題（續(xù)）,35,解：設(shè)xijk表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。利潤=（銷售單價-原料單價）*產(chǎn)品件數(shù)之和-（每臺時的設(shè)備費用*設(shè)備實際使用的總臺時數(shù)）之和。這樣我們建立如下的數(shù)學(xué)模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123s.t.5x111+10 x2116000（設(shè)備A1）7x112+9x212+12x31210000（設(shè)備A2）6x121+8x2214000（設(shè)備B1）4x122+11x3227000（設(shè)備B2）7x1234000（設(shè)備B3）x111+x112-x121-x122-x123=0（產(chǎn)品在A、B工序加工的數(shù)量相等）x211+x212-x221=0（產(chǎn)品在A、B工序加工的數(shù)量相等）x312-x322=0（產(chǎn)品在A、B工序加工的數(shù)量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3,例：生產(chǎn)計劃的問題（續(xù)）,36,例、某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應(yīng)如何下料，可使所用原料最省？解：設(shè)計下列5種下料方案,假設(shè)x1,x2,x3,x4,x5分別為上面前5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5約束條件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50,例：套裁下料問題,37,例6某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大？,例：配料問題,38,例：配料問題（續(xù)）,解：設(shè)xij表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時，要考慮：對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；目標(biāo)函數(shù)：利潤最大，利潤=收入-原料支出約束條件：規(guī)格要求4個；供應(yīng)量限制3個。,39,Maxz=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33s.t.0.5x11-0.5x12-0.5x130（原材料1不少于50%）-0.25x11+0.75x12-0.25x130（原材料2不超過25%）0.75x21-0.25x22-0.25x230（原材料1不少于25%）-0.5x21+0.5x22-0.5x230（原材料2不超過50%）x11+x21+x31100(供應(yīng)量限制）x12+x22+x32100(供應(yīng)量限制）x13+x23+x3360(供應(yīng)量限制）xij0,i=1,2,3;j=1,2,3,例：配料問題（續(xù)）,40,例8某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知：項目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元；據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如右表：問：a）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(shù)為最?。?解：1）確定決策變量：連續(xù)投資問題設(shè)xij(i=1-5，j=1、2、3、4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24,例：投資問題,41,2）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x11+x12=200；第二年：B次當(dāng)年末才可收回投資故第二年年初的資金為x11，于是x21+x22+x24=1.1x11；第三年：年初的資金為x21+x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初的資金為x31+x22，于是x41+x42=1.1x31+1.25x22；第五年：年初的資金為x41+x32，于是x51=1.1x41+1.25x32；B、C、D的投資限制：xi230(I=1、2、3、4)，x3380，x241003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi230(I=1、2、3、4)，x3380，x24100 xij0(i=1、2、3、4、5；j=1、2、3、4）b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi230(I=1、2、3、4)，x3380，x241001.1x51+1.25x42+1.4x33+1.55x24330 xij0(i=1、2、3、4、5；j=1、2、3、4）,例：投資問題（續(xù)）,42,2、線性規(guī)劃問題的進一步研究（2.1）,2.1對偶原理1、對偶問題：考慮前文例1若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費。試問：設(shè)備工時和原料A、B各如何收費才最有競爭力？設(shè)y1，y2，y3分別為每設(shè)備工時、原料A、B每單位的收取費用Maxz=50 x1+100 x2Minf=300y1+400y2+250y3s.t.x1+x2300s.t.y1+2y2+502x1+x2400（不少于甲產(chǎn)品的利潤）x2250y1+y2+y3100 x1,x20y1,y2,y30,43,2、對偶定義對稱形式：互為對偶(LP)Maxz=cTx(DP)Minf=bTys.t.Axbs.t.ATycx0y0“Max-”“Min-”一般形式：若一個問題的某約束為等式，那么對應(yīng)的對偶問題的相應(yīng)變量無非負(fù)限制；反之，若一個問題的某變量無非負(fù)限制，那么對應(yīng)的對偶問題的相應(yīng)約束為等式。,2、線性規(guī)劃問題的進一步研究（2.1）,44,3、對偶定理（原問題與對偶問題解的關(guān)系）考慮（LP）和（DP）定理2-1（弱對偶定理）若x,y分別為（LP）和（DP）的可行解，那么cTxbTy。推論若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。定理2-2（最優(yōu)性準(zhǔn)則定理）若x,y分別為（LP）和（DP）的可行解，且cTx=bTy，那么x,y分別為（LP）和（DP）的最優(yōu)解。定理2-3（主對偶定理）若（LP）和（DP）均可行，那么（LP）和（DP）均有最優(yōu)解，且最優(yōu)值相等。以上定理、推論對任意形式的相應(yīng)線性規(guī)劃的對偶均有效*習(xí)題：p99習(xí)題22-1,2、線性規(guī)劃問題的進一步研究（2.1）,45,4、影子價格是一個向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。若x*,y*分別為（LP）和（DP）的最優(yōu)解，那么，cTx*=bTy*。根據(jù)f=bTy*=b1y1*+b2y2*+bmym*可知f/bi=yi*yi*表示bi變化1個單位對目標(biāo)f產(chǎn)生的影響，稱yi*為bi的影子價格。注意：若B是最優(yōu)基，y*=(BT)-1cB為影子價格向量。,2、線性規(guī)劃問題的進一步研究（2.1）,46,5、由最優(yōu)單純形表求對偶問題最優(yōu)解第1章例1?；瘶?biāo)準(zhǔn)形式：Maxz=50 x1+100 x2s.t.x1+x2+x3=300，2x1+x2+x4=400 x2+x5=250，x1,x2,x3,x4,x50IOB=(p1,p4,p2)(BT)-1cBB-1最優(yōu)解x1=50 x2=250 x4=50（松弛標(biāo)量，表示原料A有50個單位的剩余）影子價格y1=50y2=0y3=50,B-1對應(yīng)的檢驗數(shù)(BT)-1cB。,2、線性規(guī)劃問題的進一步研究（2.1）,47,2.2對偶單純形法對偶單純形法在什么情況下使用：應(yīng)用前提：有一個基，其對應(yīng)的基本解滿足單純形表的檢驗數(shù)行全部非正（對偶可行）；變量取值可有負(fù)數(shù)（非可行解）。*注：通過矩陣行變換運算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純性表。,2、線性規(guī)劃問題的進一步研究（2.2）,48,2、線性規(guī)劃問題的進一步研究（2.2）,對偶單純形法求解線性規(guī)劃問題過程：1、建立初始對偶單純形表，對應(yīng)一個基本解，所有檢驗數(shù)均非正，轉(zhuǎn)2；2、若b0，則得到最優(yōu)解，停止；否則，若有bk0則選k行的基變量為出基變量，轉(zhuǎn)3；3、若所有akj0(j=1,2,n)，則原問題無可行解，停止；否則，若有akj0則選=minj/akjakj0csMinj/asjasj0brMin-bi/airair0,2、線性規(guī)劃問題的進一步研究（2.3）,58,例、上例最優(yōu)單純形表如下00.250這里B-1=-20.51各列分別對應(yīng)b1、b2、b3的單一0.5-0.1250變化。因此，設(shè)b1增加4，則x1,x5,x2分別變?yōu)椋?+0*4=4，4+(-2)*4=-40為單位時間平均到達的顧客數(shù)：PI=n=ne-/n!(n=0,1,2,)負(fù)指數(shù)分布為平均服務(wù)率，即單位時間服務(wù)的顧客數(shù)P（服務(wù)時間t)=1-e-tt0系統(tǒng)狀態(tài)概率分布及狀態(tài)轉(zhuǎn)移速度圖基本的概率分布推導(dǎo),6、排隊論（6.2）,117,系統(tǒng)的運行指標(biāo)：（1）、系統(tǒng)中顧客數(shù)的期望值Ls（2）、系統(tǒng)中排隊等待顧客數(shù)的期望值Lq（3）、系統(tǒng)中顧客平均的排隊等待時間Wq（4）、系統(tǒng)中顧客的平均逗留時間Ws（5）、有效到達率e,6、排隊論（6.2續(xù)）,118,6、排隊論（6.2續(xù)）,（6）、系統(tǒng)中Ls，Lq，Wq，Ws，e之間的關(guān)系Ls=npn，Lq=(n-c)pn，Ws=Ls/e，Wq=Lq/e，Ws=Wq+1/，e=npn=npn，Ls=Lq+e/。,119,6、排隊論（6.3）,*在6.1、6.2節(jié)的基礎(chǔ)上，結(jié)合例題學(xué)習(xí)、掌握下列各系統(tǒng)有關(guān)問題的計算63M/M/1無限源系統(tǒng)（p239-246）M/M/1/N系統(tǒng)，M/M/1等待制系統(tǒng)，M/M/l損失制系統(tǒng)，無限源模型特點64M/M/C無限源系統(tǒng)（p246-253）M/M/C/N系統(tǒng)，M/M/C等待制系統(tǒng)，M/M/C損失制系統(tǒng)65客源有限的排隊系統(tǒng)（p253-258）M/M/1/m/m系統(tǒng)，M/M/C/m/m系統(tǒng)66排隊系統(tǒng)應(yīng)用舉例（p258-264）本段的各例題要在充分理解的基礎(chǔ)上學(xué)習(xí)，然后獨立去完成課后練習(xí)作業(yè)。67本章小結(jié)（p264）學(xué)習(xí)本節(jié)內(nèi)容，要認(rèn)真體會第6章的重點和難點。小結(jié)也需要學(xué)習(xí)，自己應(yīng)仿照此在總復(fù)習(xí)中作各章的小結(jié)。*習(xí)題：p265-266習(xí)題66-1，6-2，6-3，6-4，6-5，6-6，6-7，6-8,返回目錄,120,教學(xué)日歷,周次學(xué)習(xí)內(nèi)容課內(nèi)學(xué)時自學(xué)學(xué)時作業(yè)（教材）1緒論21線性規(guī)劃111線性規(guī)劃的概念24習(xí)題11-1,1-2111線性規(guī)劃問題的導(dǎo)出112線性胡劃問題的概念和模型113線性規(guī)劃問題的標(biāo)準(zhǔn)型114線性規(guī)劃問題的標(biāo)準(zhǔn)化212線性規(guī)劃問題解的概念及性質(zhì)48習(xí)題11-3,1-4121解的概念122圖解法(解的幾何表示)123基本可行解的幾何意義124線性規(guī)劃求解思路(單純形法思想)125線性規(guī)劃解的性質(zhì)的證明313單純形法612習(xí)題11-5,1-6131單純形法引例132單純形法的一般描述,121,周次學(xué)習(xí)內(nèi)容課內(nèi)學(xué)時自學(xué)學(xué)時作業(yè)（教材）133表格單純形法134一般線性規(guī)劃問題的處理135單純形法的矩陣描述136單純形迭代過程中的幾點注意事項414線性規(guī)劃應(yīng)用612習(xí)題11-7,1-8141線性規(guī)劃建模1-9142生產(chǎn)計劃問題143合理下料問題144合理配料問題145運輸問題146最大流量問題2線性規(guī)劃問題的進一步研究521對偶原理24習(xí)題22-1211對偶線性規(guī)劃問題的導(dǎo)出212對偶問題的定義213對偶定理,教學(xué)日歷（續(xù)）,122,周次學(xué)習(xí)內(nèi)容課內(nèi)學(xué)時自學(xué)學(xué)時作業(yè)（教材）214對偶最優(yōu)解的經(jīng)濟含義影子價格215由最優(yōu)單純形表求對偶問題最優(yōu)解522對偶單純形法24習(xí)題22-2,2-3623靈敏度分析48習(xí)題22-4231價值系數(shù)C發(fā)生改變232右端常數(shù)b發(fā)