運籌學北京理工大學管理與經濟學院吳祈宗教授1

1、緒論

2、線性規劃

3、運輸問題

4、動態規劃

5、圖與網絡分析

6、排隊論

7、教學日歷運籌學——目錄說明本教學課件是與教材緊密配合使用的，教材為：《運籌學》楊民助編著西安交通大學出版社，2000年6月參考書：《運籌學》清華大學出版社或其他的《運籌學》方面本科教材的相關內容下面所標注的頁號，均為本課程教材的頁號。例如：p123表示第123頁p31-34表示從第31頁到第34頁2緒論

運籌學（OperationalResearch)直譯為“運作研究”運籌學是運用科學的方法（如分析、試驗、量化等）來決定如何最佳地運營和設計各種系統的一門學科。運籌學對經濟管理系統中的人力、物力、財力等資源進行統籌安排，為決策者提供有依據的最優方案，以實現最有效的管理。

運籌學有廣泛應用（可以自己找一些參考書看）運籌學的產生和發展（可以自己找一些參考書看）3運籌學解決問題的過程1）提出問題：認清問題2）尋求可行方案：建模、求解3）確定評估目標及方案的標準或方法、途徑4）評估各個方案：解的檢驗、靈敏性分析等5）選擇最優方案：決策6）方案實施：回到實踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構成決策。4運籌學的分支線性規劃非線性規劃整數規劃動態規劃多目標規劃隨機規劃模糊規劃等圖與網絡理論存儲論排隊論決策論對策論排序與統籌方法可靠性理論等5運籌學在工商管理中的應用生產計劃：生產作業的計劃、日程表的編排、合理下料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運輸問題：確定最小成本的運輸線路、物資的調撥、運輸工具的調度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產品開發與銷售計劃制定等財務和會計：預測、貸款、成本分析、定價、證券管理、現金管理等***設備維修、更新，項目選擇、評價，工程優化設計與管理等6運籌學方法使用情況(美1983)（%）7運籌學方法在中國使用情況(隨機抽樣)（%）8運籌學的推廣應用前景據美勞工局1992年統計預測:

運籌學應用分析人員需求從1990年到2005年的增長百分比預測為73%,增長速度排到各項職業的前三位.結論:運籌學在國內或國外的推廣前景是非常廣闊的工商企業對運籌學應用和需求是很大的在工商企業推廣運籌學方面有大量的工作要做9學習運籌學要把重點放在分析、理解有關的概念、思路上。在自學過程中，應該多向自己提問，如一個方法的實質是什么，為什么這樣做，怎么做等。自學時要掌握三個重要環節：1、認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關書籍。一般每一本運籌學教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學習深入。但是，把時間過多放在參考資料上，會導致思路分散，不利于學好。2、要在理解了基本概念和理論的基礎上研究例題，注意例題是為了幫助你理解概念、理論的。作業練習的主要作用也是這樣，它同時還有讓你自己檢查自己學習的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節內容有內在聯系，只要學到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。3、要學會做學習小結。每一節或一章學完后，必須學會用精煉的語言來該書所學內容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關知識和內容。這就稱作“把書讀薄”，若能夠結合自己參考大量文獻后的深入理解，把相關知識從更深入、廣泛的角度進行論述，則稱之為“把書讀厚”在建數學模型時要結合實際應用，要學會用計算機軟件解決問題。如何學習運籌學課程返回目錄10各章節節的重重點、、難點點及及注意意事項項111、線線性性規規劃劃線性規規劃模模型：：目標函函數：：Maxz=50x1+100x2約束條條件：：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看看p7--9例例1-1，1-2例1.某工廠廠在計計劃期期內要要安排排甲、、乙兩兩種產產品的的生產產，已已知生生產單單位產產品所所需的的設備備臺時時及A、B兩種種原材材料的的消耗耗以及及資源源的限限制，，如下下表：：問題：：工廠廠應分分別生生產多多少單單位甲甲、乙乙產品品才能能使工工廠獲獲利最最多？？121、線線性性規規劃劃（（續續1.1））1.1線線性規規劃的的概念念線性規規劃的的組成成：目標函函數Maxf或或Minf約束條條件s.t.(subjectto)滿滿足足于決策變變量用用符符號來來表示示可控控制的的因素素一般形形式(p10--p11)目標函函數：：Max（（Min））z=c1x1+c2x2+……+cnxn約束條條件：：s.t.a11x1+a12x2+……+a1nxn≤（（=,≥≥））b1a21x1+a22x2+……+a2nxn≤（（=,≥≥））b2………………am1x1+am2x2+……+amnxn≤（（=,≥≥））bmx1，x2，…，，xn≥0標準形形式(p11--p15，，例1-3)目標標函函數數：：Maxz=c1x1+c2x2+……+cnxn約束束條條件件：：s.t.a11x1+a12x2+……+a1nxn=b1a21x1+a22x2+……+a2nxn=b2…………………am1x1+am2x2+……+amnxn=bmx1，x2，……，，xn≥0**練練習習：：p68--70習習題題11-1，，1-2131、、線線性性規規劃劃（（續續1.2））1.2線線性性規規劃劃問問題題解解的的概概念念及及性性質質熟悉悉下下列列一一些些解解的的概概念念（（p15--16））可行行解解、、可可行行解解集集（（可可行行域域）），，最最優優解解、、最最優優值值，，基基、、基基變變量量、、非非基基變變量量，，基基本本解解、、基基本本可可行行解解，，可可行行基基、、最最優優基基。。圖解解方方法法及及各各有有關關概概念念的的意意義義（（p16--20））看：：圖圖解解法法步步驟驟，，例例1-4，，1-5，，1-6，，1-7，，1-8，，1-9下一一頁頁是是一一個個圖圖解解法法解解題題的的一一個個例例子子，，右右圖圖中中的的陰陰影影部部分分為為可可行行域域。。單純純形形法法的的理理論論基基礎礎（（p20--30））1.2.3段段要要求求看看懂懂，，了了解解如如何何直直接接通通過過對對約約束束矩矩陣陣的的分分析析求求出出基基本本可可行行解解1.2.4,1.2.5兩兩段段應應注注重重結結論論的的了了解解，，如如單單純純形形法法思思想想和和關關于于線線性性規規劃劃解解的的四四個個定理理，，而而對對證證明明過過程程則則可可根根據據自自己己的的數數學學基基礎礎來來掌掌握握：：基礎礎很很好好，，可可要要求求掌掌握握；；否否則則，，也也可可略略去去不不看看。。**習習題題：：p70習習題題11-3，，1-4141、、線線性性規規劃劃（（續續1.2））例1.目標標函函數數：：Maxz=50x1+100x2約束束條條件件：：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到到最最優優解解：：x1=50，，x2=250最優優目目標標值值z=27500151、、線線性性規規劃劃（（續續1.3））1.3單單純純形形法法利用用單單純純形形表表的的方方法法求求解解線線性性規規劃劃————重重點點(p30--451.3.1,1.3.2,1.3.3)此項項內內容容是是本本章章的的重重點點，，學學習習中中應應注注意意掌掌握握表表格格單單純純形形法法求求解解線線性性規規劃劃問問題題的的基基本本過過程程。。要要通通過過讀讀懂懂教教材材內內容容以以及及大大量量練練習習來來掌掌握握。。161、線線性規規劃劃（續續1.3）表格單純純形法(p40--p45)考慮：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2………………am1x1+am2x2+…+amnxn≤bmx1，x2，…，，xn≥0加入松弛弛變量：：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥017顯然，xj=0j=1,……,n;xn+i=bii=1,…,m是基本可可行解對應的基基是單位位矩陣。。以下是初初始單純純形表：：mm其中：f=-∑cn+ibij=cj-∑cn+iaij為檢驗數數cn+i=0i=1,…,mi=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,……,m1、線線性規規劃劃（續續1.3）181、線線性規規劃劃（續續1.3單純形形法解題題例）例1。化化標準形形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最優解x1=50x2=250x4=50（松松弛標量量，表示示原料A有50個單位位的剩余余）19注意：單單純形法法中，1、每一一步運算算只能用用矩陣初初等行變變換；2、表中中第3列列的數總總應保持持非負（（≥0）；3、當所所有檢驗驗數均非非正（≤≤0））時，得得到最優優單純形形表。1、線線性規規劃劃（續續1.3）201、線線性規規劃劃（續續1.3）一般情況況的處理理及注意意事項的的強調（（p45--55）1.3.4段主主要是討討論初始始基本可可行解不不明顯時時，常用用的方法法。要弄弄清它的的原理，，并通過過例1-14~例例1-17掌握握這些方方法，同同時進一一步熟悉悉用單純純形法解解題。考慮一般般問題：：bi>0i=1,……,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………………am1x1+am2x2+…+amnxn=bmx1，x2，…，，xn≥0211、線線性規規劃劃（續續1.3）大M法：：引入人工工變量xn+i≥0i=1,…,m;充充分分大正數數M。。得得到到，Maxz=c1x1+c2x2+…+cnxn+Mxn+1+…+Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0顯然，xj=0j=1,……,n;xn+i=bii=1,……,m是基本可可行解對應的基基是單位位矩陣。。結論：若若得到的的最優解解滿足xn+i=0i=1,…,m則是原問問題的最最優解；；否則，，原問題題無可行行解。221、線線性規規劃劃（續續1.3）兩階段法法：引入人工工變量xn+i≥0，，i=1,……,m；構構造，Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2………………am1x1+am2x2+……+amnxn+xn+m=bmx1，x2，…，，xn，xn+1，…，，xn+m≥0第一階階段求求解上上述問問題：：顯然，，xj=0j=1,……,n;xn+i=bii=1,……,m是基本本可行行解對應的的基是是單位位矩陣陣。結論：：若得得到的的最優優解滿滿足xn+i=0i=1,……,m則是原原問題題的基基本可可行解解；否否則，，原問問題無無可行行解。。得到原原問題題的基基本可可行解解后，，第二二階段段求解解原問問題。。231、線線性性規規劃劃（（續續1.3））例題題例：（（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0大M法法問題題（LP-M））Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0兩階段段法：：第第一階階段問問題（（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0241、線線性性規規劃劃（（續續1.3））大M法例例大M法（LP-M）得到最優解解：(25/3，10/3，，0，11)T最優目標值值：112/3251、線性性規劃劃（續續1.3））兩階段法法例第一階段（LP-1）得到原問題題的基本可可行解：(0，15/7，25/7，，52/7)T261、線性性規劃劃（續續1.3））兩階段法法例第二階段把基本可行行解填入表表中得到原問題題的最優解解：(25/3，10/3，，0，11)T最優目標值值：112/3271、線性性規劃劃（續續1.3））1.3.5矩矩陣描述———此段段為選讀，，有困難者者可不看。。1.3.6段段單純形迭迭代過程中中的幾點注注意事項是是對有關內內容的強調調和補充，，要認真學學習、理解解。**習題：：p70--71習習題11-5，1-6281.4線線性性規劃應用用——建建模（p55--68）本節介紹了了些線性規規劃應用的的例子，這這些例子從從多個方面面介紹建模模對未來是是很有用的的，應認真真對待。除了教材上上的例子之之外，還有有許多其它它應用：*合理利利用線材問問題：如何何下料使用用材最少*配料問問題：在原原料供應量量的限制下下如何獲取取最大利潤潤*投資問問題：從投投資項目中中選取方案案，使投資資回報最大大*產品生生產計劃：：合理利用用人力、物物力、財力力等，使獲獲利最大*勞動力力安排：用用最少的勞勞動力來滿滿足工作的的需要*運輸問問題：如何何制定調運運方案，使使總運費最最小**下面是是一些建模模的例子，，有興趣者者，可作為為練習。這這些例子有有一定的難難度，做起起來會有一一些困難。。**習題：：p72--73習習題11-7，1-8，1-9，1-101、線性性規劃劃（續續1.4））返回目錄29例．某晝夜夜服務的公公交線路每每天各時間間段內所需需司機和乘乘務人員數數如下：設司機和乘乘務人員分分別在各時時間段一開開始時上班班，并連續續工作八小小時，問該該公交線路路怎樣安排排司機和乘乘務人員，，既能滿足足工作需要要，又配備備最少司機機和乘務人人員?例：人力資資源分配的的問題30解：設xi表示第i班班次時開始始上班的司司機和乘務務人員數,這樣我們們建立如下下的數學模模型。目標函數：：Minx1+x2+x3+x4+x5+x6約束條件：：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0例：人力資資源分配的的問題（續續）31例、明明興公司生生產甲、乙乙、丙三種種產品，都都需要經過過鑄造、機機加工和裝裝配三個車車間。甲、、乙兩種產產品的鑄件件可以外包包協作，亦亦可以自行行生產，但但產品丙必必須本廠鑄鑄造才能保保證質量。。數據如下下表。問：：公司為了了獲得最大大利潤，甲甲、乙、丙丙三種產品品各生產多多少件？甲甲、乙兩種種產品的鑄鑄造中，由由本公司鑄鑄造和由外外包協作各各應多少件件？例：生產計計劃的問題題32解：設x1,x2,x3分別為三道道工序都由由本公司加加工的甲、、乙、丙三三種產品的的件數，x4,x5分別為由外外協鑄造再再由本公司司機加工和和裝配的甲甲、乙兩種種產品的件件數。求xi的利潤：利利潤=售售價-各成本本之和可得到xi（i=1,2,3,4,5））的利潤分分別為15、10、、7、13、9元。。這樣我們建建立如下的的數學模型型。目標函數：：Max15x1+10x2+7x3+13x4+9x5約束條件：：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例：生產計計劃的問題題（續）33例、永久久機械廠生生產Ⅰ、ⅡⅡ、Ⅲ三種種產品，均均要經過A、B兩兩道工序加加工。假設設有兩種規規格的設備備A1、A2能完成A工序；；有三種規規格的設備備B1、B2、B3能完成B工工序。Ⅰ可可在A、B的的任何規格的的設備上加工工；Ⅱ可在在任意規格的的A設備上加加工，但對B工序，只能能在B1設備上加工；；Ⅲ只能在A2與B2設備上加工；；數據如下表表。問：為使使該廠獲得最最大利潤，應應如何制定產產品加工方案案？例：生產計劃劃的問題（續續）34解：設xijk表示第i種種產品，在在第j種種工序上的第第k種設設備上加工的的數量。利潤=[（銷售單價價-原料料單價）*產產品件數]之和-（（每臺時的的設備費用*設備實際使使用的總臺時時數）之和。。這樣我們建立立如下的數學學模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123s.t.5x111+10x211≤6000（（設備A1）7x112+9x212+12x312≤10000（（設備A2）6x121+8x221≤4000（（設備B1）4x122+11x322≤7000（（設備B2）7x123≤4000（（設備B3）x111+x112-x121-x122-x123=0（ⅠⅠ產品在A、、B工序加工工的數量相等等）x211+x212-x221=0（ⅡⅡ產品在A、、B工序加工工的數量相等等）x312-x322=0（ⅢⅢ產品在A、、B工序加工工的數量相等等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3例：生產計劃劃的問題（續續）35例、某工廠要要做100套套鋼架，每套套用長為2.9m,2.1m,1.5m的圓鋼各一一根。已知原原料每根長7.4m，，問：應如何何下料，可使使所用原料最最省？解：設計計下列5種種下料方案案假設x1,x2,x3,x4,x5分別為上面前前5種方方案下料的原原材料根數。。這樣我們建建立如下的數數學模型。目標函數：Minx1+x2+x3+x4+x5約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0例：套裁下料料問題36例6．某工廠廠要用三種原原料1、2、、3混合調配配出三種不同例：配料問題題37例：配料問題題（續）解：設xij表示第i種種（甲、對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；目標函數：利潤最大，利潤=收入-原料支出約束條件：規格要求4個；供應量限制3個。38Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33s.t.0.5x11-0.5x12-0.5x13≥0（原原材料1不少少于50%））-0.25x11+0.75x12-0.25x13≤0（原原材料2不超超過25%））0.75x21-0.25x22-0.25x23≥0（原原材料1不少少于25%））-0.5x21+0.5x22-0.5x23≤0（原原材料2不超超過50%））x11+x21+x31≤100(供應應量限制）x12+x22+x32≤100(供應應量限制）x13+x23+x33≤60(供應應量限制）xij≥0,i=1,2,3;j=1,2,3例：配料問題題（續）39例8．某部門門現有資金200萬元，，今后五年內內考慮給以下下的項目投資資。已知：項項目A：從第一一年到第五年年每年年初都都可投資，當當年末能收回回本利110%；項目B：從第一年到第四年年每年年初都都可投資，次次年末能收回回本利125%，但規定定每年最大投投資額不能超過30萬元；項目目C：需在第第三年年初投投資，第五年年末能收回本本利140%，但規定最大投資額額不能超過80萬元；項項目D：需在在第二年年利155%，但規定最大投資額不能超過100萬元；據測定每萬元每次投資的風險指數如右表：問：a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數為最小？解：1）確定決策變量量：連續投資資問題設xij(i=1-5，j=1、2、3、4)表示示第i年年初投資于A(j=1)、B(j=2)、C(j=3)、、D(j=4)項目的金金額。這樣我我們建立如下下的決策變量量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24例：投資問題題402）約束條件件：第一年：A當當年末可收回回投資，故第第一年年初應應把全部資金金投出去，于于是x11+x12=200；；第二年：B次次當年末才可可收回投資故第三年：年初的資金為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的投資限制：xi2≤30(I=1、2、3、4)，x33≤80，x24≤1003）目標函數及模型：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；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤100

xij≥0(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；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）例：投資問題題（續）412、線性規劃劃問題的進一一步研究（2.1）2.1對對偶原理1、對偶問題題：考慮前文例1若設備和原料料都用于外協協加工，工廠廠收取加工費費。試問：設設備工時和原原料A、B各各如何收費費才最有競爭爭力？設y1，y2，y3分別為每設備備工時、原料A、B每單位的收收取費用Maxz=50x1+100x2Minf=300y1+400y2+250y3s.t.x1+x2≤300s.t.y1+2y2+≥502x1+x2≤400（不少于甲產產品的利潤））x2≤250y1+y2+y3≥100x1,x2≥0y1,y2,y3≥0422、對偶定義義對稱形式：互互為對偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤≤bs.t.ATy≥cx≥0y≥0“Max--≤””““Min--≥”一般形式：若一個問題的的某約束為等等式，那么對對應的對偶問問題的相應變變量無非負限限制；反之，，若一個問問題的某變量量無非負限制制，那么對應應的對偶問題題的相應約束束為等式。2、線性規劃劃問題的進一一步研究（2.1）433、對偶定理理（原問題題與對偶問題題解的關系））考慮（LP））和（DP））定理2-1（（弱對偶定定理）若x,y分分別為（LP）和（DP）的可行解解，那么cTx≤bTy。推論若（LP）可行，，那么（LP）無有限最最優解的充分分必要條件是是（LD）無無可行解。定理2-2（（最優性準準則定理）若若x,y分別為（（LP）和（（DP）的可可行解，且cTx=bTy，那么x,y分分別為（LP）和（DP）的最優解解。定理2-3（（主對偶定定理）若（LP）和（DP）均可行行，那么（LP）和（DP）均有最最優解，且最最優值相等。。以上定理、推推論對任意形形式的相應線線性規劃的對對偶均有效**習題：p99習習題22-12、線性規劃劃問題的進一一步研究（2.1）444、影影子價價格——是是一一個向向量，，它的的分量量表示示最優優目標標值隨隨相應應資源源數量量變化化的變變化率率。若x*,y*分別為為（LP））和（（DP）的的最優優解，，那么，，cTx*=bTy*。根據f=bTy*=b1y1*+b2y2*++bmym*可知f/bi=yi*yi*表示bi變化1個單單位對對目標標f產產生的的影響響，稱稱yi*為bi的影子子價格格。注意：：若B是是最最優基基，y*=(BT)-1cB為影子子價格格向量量。2、線線性規規劃問問題的的進一一步研研究（（2.1））455、由由最優優單純純形表表求對對偶問問題最最優解解第1章章例1。化化標準準形式式：Maxz=50x1+100x2s.t.x1+x2+x3=300，，2x1+x2+x4=400x2+x5=250，，x1,x2,x3,x4,x5≥0IOB=(p1,p4,p2)(BT)-1cBB-1最優解解x1=50x2=250x4=50（松松弛標標量，，表示示原料料A有有50個單單位的的剩余余）影子價價格y1=50y2=0y3=50,B-1對應的的檢驗驗數(BT)-1cB。2、線線性規規劃問問題的的進一一步研研究（（2.1））462.2對對偶偶單純純形法法對偶單單純形形法在在什么么情況況下使使用：：應用前前提：：有一一個基基，其其對應應的基基本解解滿足足①單單純形形表的的檢驗驗數行行全部部非正正（對對偶可可行））；②變變量取取值可可有負負數（（非可可行解解）。。**注注：通通過矩矩陣行行變換換運算算，使使所有有相應應變量量取值值均為為非負負數即即得到到最優優單純純性表表。2、線線性規規劃問問題的的進一一步研研究（（2.2））472、線線性規規劃問問題的的進一一步研研究（（2.2））對偶單單純形形法求求解線線性規規劃問問題過過程：：1、建建立初初始對對偶單單純形形表，，對應應一個個基本本解，，所有有檢驗驗數均均非正正，轉轉2；；2、若若b’’≥0，，則得得到最最優解解，停停止；；否則則，若若有bk<0則則選k行行的的基變變量為為出基基變量量，轉轉3；；3、若若所有有akj’≥0(j=1,2,……,n)，則則原問問題無無可行行解，，停止止；否否則，，若有有akj’<0則則選=min{j’/akj’┃akj’<0}=r’/akr’那么么r為為進基基變量量，轉轉4；；4、以以akr’為轉轉軸元元，作作矩陣陣行變變換使使其變變為1，，該列列其他他元變變為0，，轉2。48例：求解線線性規規劃問問題：：Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥0標準化化：MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線線性規規劃問問題的的進一一步研研究（（2.2））49表格對對偶單單純形形法**習習題：：p100習習題22-2，2-32、線線性規規劃問問題的的進一一步研研究（（2.2））502.3靈靈敏度度分析析進一步步理解解最優優單純純形表表中各各元素素的含含義考慮問問題Maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2………………am1x1+am2x2+……+amnxn≤bmx1，x2，…，，xn≥0引入m個個松松弛變變量后后，通通過計計算得得到最最優單單純形形表。。應-1-1能夠找找到最最優基基B的逆逆矩陣陣B，，以以及BN，檢檢驗數數等。。2、線線性規規劃問問題的的進一一步研研究（（2.3））512、線線性規規劃問問題的的進一一步研研究（（2.3））最優單單純形形表B-1(BT)-1cBIO52價值系系數C發生生變化化：m考慮檢驗數數j=cj-∑criarijj=1,2,……,ni=11、若ck是非基變量量的系數：：設ck變化為ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0，，即ck≤-k，則最優解不不變；否則則，將最優優單純形表表中的檢驗驗數k用k’取代，繼續續單純形法法的表格計計算。例:MaxZ=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規規劃問題的的進一步研研究（2.3）53例：最優單單純形表從表中看到到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔΔC3≤9/5時時，原最優優解不變。。2、線性規規劃問題的的進一步研研究（2.3）542、若cs是基變量的的系數：設設cs變化為cs+cs，那么j’=cj-∑criarij-(cs+cs)asj=j-csasj，對所有非非基變量i≠s只要對所有有非基變量量j’≤0，，即j≤csasj，則最優解不不變；否則則，將最優優單純形表表中的檢驗驗數j用j’取代，繼續續單純形法法的表格計計算。Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}例:MaxZ=2x1+3x2+0x3+0x4+0x5S.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥02、線性規規劃問題的的進一步研研究（2.3）55例、下表為為最優單純純形表，考考慮基變量量系數c2發生變化從表中看到到σj=Cj-（C1*a1j+C5*a5j+（C2+ΔC2）*a2j）j=3、、4可得到-3≤≤ΔC2≤1時時，原原最優解不不變。2、線性規規劃問題的的進一步研研究（2.3）56右端項b發生變變化設分量br變化為br+br，根據第1章的討論論，最優解解的基變量量xB=B-1b，那么只只要保持B-1(b+b)≥0，則最最優基不變變，即基變變量保持，，只有值的的變化；否否則，需要要利用對偶偶單純形法法繼續計算算。對于問題(LP)Maxz=cTxs.t.Ax≤bx≥0最優單純形形表中含有有B-1=（aij）i=1,……,m;j=n+1,……,n+m那么，新的的xi=(B-1b)i+brairi=1,…,m。。由此可得得，最優基基不變的條條件是Max{-bi/airair>0}≤br≤Min{-bi/airair<0}2、線性規規劃問題的的進一步研研究（2.3）57例、上例最最優單純形形表如下00.250這里B-1=-20.51各各列分別別對應b1、b2、b3的單一0.5-0.1250變化。因此此，設b1增加4，，則x1,x5,x2分別變為：：4+0*4=4，4+(-2)*4=-4<0，，2+0.5*4=4用對偶單純純形法進一一步求解，，可得：x*=(4,3,2,0,0)Tf*=172、線性規規劃問題的的進一步研研究（2.3）58增加一個變變量增加變量xn+1則有相應的的pn+1，cn+1。那么，計計算出B-1pn+1n+1=cn+1-∑criarin+1填入最優單單純形表，，若n+1≤0則最優解不不變；否則則，進一步步用單純形形法求解。。例、前例增增加x6，p6=(2,6,3)T，c6=5。。計算得到到2、線性規規劃問題的的進一步研研究（2.3）用單純形法法進一步求求解，可得得：x*=(1,1.5,0,0,0,2)Tf*=16.559增加一個約約束增加約束一一個之后，，應把最優優解帶入新新的約束，，若滿足則則最優解不不變，否則則填入最優優單純形表表作為新的的一行，引引入1個新新的非負變變量（原約約束若是小小于等于形形式可引入入非負松弛弛變量，否否則引入非非負人工變變量），并并通過矩陣陣行變換把把對應基變變量的元素素變為0，，進一步用用單純形法法或對偶單單純形法求求解。例、前例增增加3x1+2x2≤15，原原最優解不不滿足這個個約束。于于是2、線性規規劃問題的的進一步研研究（2.3）60A中元素發發生變化（只討論N中某某一列變化化情況）與增加變量量xn+1的情況類似似，假設pj變化。那那么，重新新計算出B-1pjj=cj-∑criarij填入最優單單純形表，，若j≤0則最優解不不變；否則則，進一步步用單純形形法求解。。2、線性規規劃問題的的進一步研研究（2.3）可得最優解解：x*=(3.2,0.8,0,0,2.4)Tf*=15.2612、線性規規劃問題的的進一步研研究（2.3）2.3靈靈敏度分分析(內內容，為重重點)2.3.1Ci發生變化2.3.2Bj發生變化2.3.3增增加一個變變量2.3.4增增加一個約約束2.3.5A中元素發發生變化**習題：：p100習習題22-4返回目錄623.1運運輸問問題模型與與性質運輸模型例、某公司從兩兩個產地A1、A2將物品運往往三個銷地地B1、B2、B3，各產地的的產量、各各銷地的銷銷量和各產產地運往個個銷地每件件物品的運運費如下表表所示，問問：應如何何調運可使使總運輸費費用最小？？3、運輸輸問問題（（3.1）63解：產銷平衡衡問題：：總產產量=總銷銷量設xij為從產地地Ai運往銷地地Bj的運輸量量，得到到下列運運輸量表表：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、、2；j=1、2、3））3、運輸輸問問題（（3.1）64系數矩陣陣111000000111100100010010001001特點：1、共有m+n行，分別別表示產地和和銷地；mn列分別表示示各變量；2、每列只有有兩個1，，其余為0，分別表示示只有一個產產地和一個銷銷地被使用；；3、運輸問問題（3.1）65設xij為從產地Ai運往銷地Bj的運輸量，得得到下列一般般運輸量問題題的模型：mnMinf=cijxiji=1j=ins.t.xij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,……,m;j=1,2,…,n)一般運輸模型型：產銷平衡A1、A2、…、Am表示某物資的的m個產地；；B1、B2、…、Bn表示某物質的的n個銷地；；si表示產地Ai的產量；dj表示銷地Bj的銷量；cij表示把物資為為從產地Ai運往銷地Bj的單位運價。。3、運輸問問題（3.1續）663、運輸問問題（3.1續）變化：1）有時目標標函數求最大大，如求利潤潤最大或營業業額最大等；；2）當某些運運輸線路上的的能力有限制制時，模型中中可直接加入入（等式或不不等式）約束束；3）產銷不平673、運輸問問題（求解思路是基本可行解最優否結束否換基運輸問題基變變量的特點*運輸問問題的基變量量共有m+n-1個，A的秩為m+n-1。*運輸問問題的m+n-1個變量量構成基變量量的充分必要要條件是不含含閉回路。要弄清下列概概念：閉回回路、閉回路路的頂點。683.2運運輸問題的表表上作業法——本章重重點1、初始基本本可行解的確確定：（1）西北角角法：從西北角（左左上角）格開開始，在格內內的右下角標標上允許取得的最大數。然然后按行（列列）標下一格格的數。若某某行（列）的的產量（銷量量）已滿足，，則把該行（（列）的其他他格劃去。如如此進行下去去，直至得到到一個基本可可行解。（2）最小元元素法：從運價最小的的格開始，在在格內的右下下角標上允許取得的最大數。然然后按運價從從小到大順序序填數。若某某行（列）的的產量（銷量量）已滿足，，則把該行（（列）的其他他格劃去。如如此進行下去去，直至得到到一個基本可可行解。注：應用西北角法法和最小元素素法，每次填填完數，都只只劃去一行或或一列，只有有最后一個元元例外（同時時劃去一行和和一列）。當當填上一個數數后行、列同同時飽和時，，也應任意劃劃去一行（列列）在保留的的列（行）任任意沒被劃去去的格內標一一個0。3、運輸問問題（3.2）69*3、運輸問問題（3.2）70*3、運輸問712、最優性檢檢驗：因為求最小，，當所有檢驗驗數均大于等等于0時為最最優解（1）位勢法法求檢驗數：：位勢：設對應基變量量xij的m+n-1個ij，存在ui,vj滿足ui+vj=cij，i=1,…,m;j=1,…,n.稱稱這些ui,vj為該基本可行行解對應的位位勢。由于有m+n個個變量（ui,vj），m+n-1個方程（（基變量個數數），故有一一個自由變量量，位勢不唯唯一。利用位勢求檢檢驗數：ij=cij-ui-vji=1,…,m;j=1,…,n3、運輸問問題（3.2）72前例，位勢法法求檢驗數：：step1從任意基變量量對應的cij開始，任取ui或vj，然后利用公公式cij=ui+vj依次找出m+n個個ui,vj；從c14=10開開始step2計算非基變量量的檢驗數ij=cij-ui-vj；填入圓圈內3、運輸問問題（3.2）733、主元變換換：（1）選負檢檢驗數中最小小者rk，那么xrk為主元，作為為進基變量；；（上頁圖中x24）（2）以為xrk起點找一條閉閉回路，除xrk外其余頂點必必須為基變量量格；（上頁圖中藍藍色回路））（3）為閉回回路的每一個個頂點標號，，xrk為1，沿一一個方向依次次給各頂點標標號；（4）求=min{xijxij對應閉回路上上的偶數標號號格}=xpq那么確確定xpq為出基基變量量，為調整整量；；（5））對閉閉回路路的各各奇標標號頂頂點xij+，對各各偶標標號頂頂點xij-，特別別xpq-=0，變為為非基基變量量；3、運運輸輸問問題題（3.2）重復2、3步，，直到到所有有檢驗驗數均均非負負，得得到最最優解解。74主元變變換：：由前面面得到到=1，于是是3、運運輸輸問問題題（3.2）ij≥0，得得到最最優解解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其其余余xij=0;最優費費用：：f*=3*5+10*2+1*3+8*1+4*6+5*3=85**習習題：：p123習習題33-1,3-2753.3產產銷銷不平平衡的的運輸輸問題題1、產產量大大于銷銷量例例、、某公司司從兩兩個產產地A1、A2將物品品運往往三個個銷地地B1、B2、B3，各產產地的的產量量、各各銷地地的銷銷量和和各產產地運運往個個銷地地每件件物品品的運運費如如下表表所示示，問問：應應如何何調運運可使使總運運輸費費用最最小？？解：增加加一個個虛設設的銷銷地運運輸費費用為為03、運運輸輸問問題題（3.3）762、銷銷量大大于產產量例、某公司司從兩兩個產產地A1、A2將物品品運往往三個個銷地地B1、B2、B3，各產產地的的產量量、各各銷地地的銷銷量和和各產產地運運往個個銷地地每件件物品品的運運費如如下表表所示示，問問：應應如何何調運運可使使總運運輸費費用最最小？？解：增加加一個個虛設設的產產地運運輸費費用為為03、運運輸輸問問題題（3.3）77下面給給出一一些例例題，，可作作為建建模的的練習習：例、石家莊莊北方方研究究院有有一、、二、、三，，三個個區。。每年年分別別需要要用煤煤3000、1000、、2000噸，，由河河北臨臨城、、山西西盂縣縣兩處處煤礦礦負責責供應應，價價格、、質量量相同同。供供應能能力分分別為為1500、4000噸噸，運運價如如下表表。由由于需需大于于供，，經院院研究究決定定一區區供應應量可可減少少0--200噸，，二區區必須須滿足足需求求量，，三區區供應應量不不少于于1700噸，，試求求總費費用為為最低低的調調運方方案。。3、運運輸輸問問題題（例例題））78解：根據題題意，，作出出產銷銷平衡衡與運運價表表：取M代代表一一個很很大的的正數數，其其作用用是強強迫相相應的的x31、x33、x34取值為為0。。3、運運輸輸問問題題（例例題））79例、設有A、B、C三個個化肥肥廠供供應1、2、3、4四個個地區區的農農用化化肥。。假設設效果果相同同，有有關數數據如如下表表。試試求總總費用用為最最低的的化肥肥調撥撥方案案。3、運運輸輸問問題題（例例題））80解：根據題意意，作出出產銷平平衡與運運價表：：最低要求求必須滿滿足，因因此把相相應的虛虛設產地地運費取取為M，而而最高要要求與最最低要求求的差允允許按需需要安排排，因此此把相應應的虛設設產地運運費取為為0。。對應應4””的銷量量50是考考慮問題題本身適適當取的的數據，，根據產產銷平衡衡要求確確定D的產量量為50。3、運輸輸問問題（（例題））81例、某廠按合合同規定定須于當當年每個個季度末末分別提提供10、15、25、20臺同一一規格的的柴油機機。已知知該廠各各季度的的生產能能力及生生產每臺臺柴油機機的成本本如下表表。如果果生產出出來的柴柴油機當當季不交交貨，每每臺每積積壓一個個季度需需儲存、、維護等等費用0.15萬元。。試求在在完成合合同的情情況下，，使該廠廠全年生生產總費費用為最最小的決決策方案案。3、運輸輸問問題（（例題））82解：設xij為第i季度度生產的的第j季度度交貨的的柴油機機數目，，那末應應滿足：：交貨：x11=10生生產：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度度生產的的柴油機機數目看看作第i個個生產廠廠的產量量；把第第j季季度交交貨的柴柴油機數數目看作作第j個銷銷售點的的銷量；；成本加加儲存、、維護等等費用看看作運費費。可構構造下列列產銷平平衡問題題：目標函數數：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x443、運輸輸問問題（（例題））83例、光明儀器器廠生產產電腦繡繡花機是是以產定定銷的。。已知1至6月月份各月月的生產產能力、、合同銷銷量和單單臺電腦腦繡花機機平均生生產費用用見下表表已知上年年末庫存存103臺繡花花機，如如果當月月生產出出來的機機器當月月不交貨貨，則需需要運到到分廠庫庫房，每每臺增加加運輸成成本0.1萬元元,每臺臺機器每每月的平平均倉儲儲費、維