1、運籌學Operations Research2016.9.7運籌學Operations Research2016.9.15 十月 20222一、運籌學（OR）發(fā)展簡介運籌學在國外英國稱為 Operational Research美國稱為 Operations Research起源于二戰(zhàn)期間的軍事問題，如雷達的設置、運輸船隊的護航艦隊的規(guī)模、反潛作戰(zhàn)中深水炸彈的深度、飛機出擊隊型、軍事物資的存儲等。二戰(zhàn)以后運籌學應用于經(jīng)濟管理領域（LP、計算機）1948年英國首先成立運籌學會；1952年美國成立運籌學會。1952年，Morse 和 Kimball出版運籌學方法1959年成立國際運籌學聯(lián)合會11

2、十月 20222一、運籌學（OR）發(fā)展簡介運籌學在國外15 十月 20223 運籌學在國內(nèi)中國古代樸素的運籌學思想（田忌與齊王對馬、丁渭修復皇宮）1956年成立運籌學小組1958年提出運輸問題的圖上作業(yè)法1962年提出中國郵路問題1964年華羅庚推廣統(tǒng)籌方法我國于1982年加入國際運籌學聯(lián)合會，并于1999年8月組織了第15屆大會11 十月 20223 運籌學在國內(nèi)15 十月 20224二、運籌學的特點及研究對象運籌學的定義運籌學為決策機構對所控制的業(yè)務活動作決策時，提供以數(shù)量為基礎的科學方法Morse 和 Kimball運籌學是把科學方法應用在指導人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各

3、種問題，其方法是發(fā)展一個科學的系統(tǒng)模式，并運用這種模式預測、比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學地決定工作方針和政策英國運籌學會運籌學是應用分析、試驗、量化的方法對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理中國百科全書現(xiàn)代運籌學涵蓋了一切領域的管理與優(yōu)化問題，稱為 Management Science11 十月 20224二、運籌學的特點及研究對象運籌學的定義15 十月 20225三、運籌學的工作步驟明確問題建立模型設計算法整理數(shù)據(jù)求解模型評價結果簡化？滿意？YesNoNo明確問題建立模型設計算法整理數(shù)據(jù)求解模型評價結果11 十

4、月 20225三、運籌學的工作步驟明確問題建立模型設15 十月 20226四、運籌學內(nèi)容介紹 線性規(guī)劃及單純形法 對偶理論及靈敏度分析 運輸問題 整數(shù)規(guī)劃 動態(tài)規(guī)劃 圖與網(wǎng)絡分析 存儲論 排隊論（隨機服務理論） 決策論11 十月 20226四、運籌學內(nèi)容介紹 線性規(guī)劃及單純形法成績考評平時成績 10%期中考核成績 30%期末考試成績 60%15 十月 20227成績考評平時成績 10%11 十月 20227Chapter 1 線性規(guī)劃Linear Programming1.1 LP的數(shù)學模型 Mathematical Model of LP1.2 圖解法 Graphical Method1.3

5、 標準型 Standard form of LP1.4 基本概念 Basic Concepts1.5 單純形法 Simplex MethodChapter 1 線性規(guī)劃1.1 LP的數(shù)學模型 1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 1.1 線性規(guī)劃的數(shù)學模型 15 十月 2022101.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 線性規(guī)劃通常研究資源的最優(yōu)利用、設備最佳運行等問題。例如，當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標；企業(yè)在一定的資源條件

6、限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多 、利潤最大）。線性規(guī)劃（Linear Programming,縮寫為LP）是運籌學的重要分支之一，在實際中應用得較廣泛，其方法也較成熟，借助計算機，使得計算更方便，應用領域更廣泛和深入。11 十月 2022101.1 線性規(guī)劃的數(shù)學模型 Mat15 十月 202211【例1.1】最優(yōu)生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設備上加工及所需要的資源如表1.1所示。已知在計劃期內(nèi)設備的加工能力各為200臺時，可供材料分別為360、300

7、公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。企業(yè)決策者應如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大？1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP1.1.1 應用模型舉例11 十月 202211【例1.1】最優(yōu)生產(chǎn)計劃問題。某企業(yè)15 十月 202212 產(chǎn)品 資源 甲 乙 丙現(xiàn)有資源設備A 3 1 2 200設備B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利潤（元/件） 40 30 50表1.1 產(chǎn)品資源消耗1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model

8、of LP11 十月 202212 產(chǎn)品 產(chǎn)品 資源 甲 乙 丙現(xiàn)有資源設備A 3 1 2 200設備B 2 2 4 200材料C 4 5 1 360材料D 2 3 5 300利潤（元/件） 40 30 5015 十月 202213【解】設x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學模型為：1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP最優(yōu)解X=(50,30,10);Z=3400 產(chǎn)品 設備A 3 15 十月 202214線性規(guī)劃的數(shù)學模型由決策變量 Decision variables 目標函數(shù)Objective function約束條件Constrai

9、nts構成。稱為三個要素。其特征是：1解決問題的目標函數(shù)是多個決策變量的 線性函數(shù)，通常是求最大值或 最小值；2解決問題的約束條件是一組多個決策變量 的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 202214線性規(guī)劃的數(shù)學模型由決策變量 Dec練習:餅干生產(chǎn)問題15 十月 20221545利潤（百元/噸）1122 烘箱512 成形機1553 攪拌機每天現(xiàn)有工時 II型餅干 I 型餅干資源單位時耗 小時/噸 產(chǎn)品為充分利用現(xiàn)有資源，該廠應如何制定生產(chǎn)計劃，使獲利最大？練習:餅干生產(chǎn)問題11 十月 202

10、21545利潤（百元/噸 設X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn)量（單位為噸），z表示I型和II型餅干所創(chuàng)造的日總利潤15 十月 202216目標： max z = 5X1 +4X2約束條件： 3X1 +5X2 15 （攪拌機的限制） 2X1 + X2 5 （成形機的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 設X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn)量（單練習：運輸問題15 十月 202217 應如何調(diào)運電機，即滿足用戶需要，又使總的運費最少？運價（元/臺）B1B2B3供應量A1152118200A2202516150需求量（臺）1008090B3

11、120練習：運輸問題11 十月 202217 應如何調(diào)運電機 設Xij表示從倉庫Ai調(diào)到商場Bj的調(diào)撥數(shù)，（i=1,2;j=1,2,3）以臺為單位，則有以下LP模型： 15 十月 202218minZ=15x11+21x12+18x13+20 x21+25x22+16x23S.T. x11+x12+x13200 x21+x22+x23150 x11+x21=100 x12+x22=80 x13+x2390 x13+x23120 xij0（i=1,2;j=1,2,3）(嚴格設Xij應取整數(shù)值，這點暫不討論) 設Xij表示從倉庫Ai調(diào)到商場Bj的調(diào)撥數(shù)，（i=1,15 十月 2022191.1.2

12、 線性規(guī)劃的一般模型一般地，假設線性規(guī)劃數(shù)學模型中，有m個約束，有n個決策變量xj, j=1,2,n，目標函數(shù)的變量系數(shù)用cj表示, cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學模型的一般表達式可寫成為了書寫方便，上式也可寫成： 1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 2022191.1.2 線性規(guī)劃的一般模型為了書15 十月 202220在實際中一般xj0,但有時xj0或xj無符號限制。1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of

13、LP11 十月 202220在實際中一般xj0,但有時xj015 十月 202221線性規(guī)劃一般模型的結構目標函數(shù) ：max，min約束條件：,=,變量符號：0, unr,0說明：線性規(guī)劃模型由三部分構成：目標函數(shù)、約束條件和變 量符號。任何實際問題嚴格來講是非線性的。在實際建模時應 明確什么樣的特性使我們可以做出線性性質(zhì)的假定。第二章 線性規(guī)劃11 十月 202221線性規(guī)劃一般模型的結構說明：第二章 15 十月 202222【例1.2】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表1.2所示。表1.2 營業(yè)員需要量統(tǒng)計表商場人力資源部應如何安

14、排每天的上班人數(shù)，使商場總的營業(yè)員最少。 星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 202222【例1.2】某商場決定：營業(yè)員每周連15 十月 202223【解】 設xj(j=1，2，7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為 1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四40011 十月 202223【解】 設xj(j=1，2，7)1

15、5 十月 2022241X10C1404=3001042X267C2301=30013X3146C3350=35004X4170C4400=40005X597C5480=48006X6120C6600=60007X717C7550=5500最優(yōu)解：Z617（人）11 十月 2022241X10C1404=300104215 十月 202225【例1.3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4 m。現(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？ 【解】這是一個條材下料問題 ，設切口寬度

16、為零。 設一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個不等式關于y1，y2，y3的非負整數(shù)解。象這樣的非負整數(shù)解共有10組，也就是有10種下料方式，如表1.3所示。表13 下料方案 方案規(guī)格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 202225【例1.

17、3】合理用料問題。某汽車需要15 十月 202226設xj(j=1,2,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學模型為:求下料方案時應注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 方案規(guī)格 1234 5678910需求量y1(根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（m）

18、00.30.5 0.1o.4 00.30.60.20.511 十月 202226設xj(j=1,2,10)為第j種15 十月 2022271X15002X203X304X405X506X662.57X708X809X925010X100Z812.51.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 2022271X15002X203X304X4015 十月 202228【例1.4】配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級別的礦石中進行冶

19、煉，每種礦物的成分含量和價格如表1.4所示。礦石雜質(zhì)在冶煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設礦石在冶煉過程中，合金含量沒有發(fā)生變化。表1.4 礦石的金屬含量 合金礦石錫%鋅%鉛%鎳%雜質(zhì)費用（元/t ）1251010253034024000303026030155206018042020040202305851517551901.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 202228【例1.4】配料問題。某鋼鐵公司生產(chǎn)15 十月 202229解: 設xj（j=1,2，5）是第j 種礦石數(shù)量，得到下列線性規(guī)劃模型 注意，礦石在實際冶煉時金

20、屬含量會發(fā)生變化，建模時應將這種變化考慮進去，有可能是非線性關系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP礦石錫%鋅%鉛%鎳%雜質(zhì)費用（元/t ）12510102530340240003030260301552060180420200402023058515175519011 十月 202229解: 設xj（j=1,2，5）是15 十月 2022301X102X20.33333X304X40.58335X50.6667最優(yōu)解：Z=347.51.1 線性規(guī)劃的數(shù)學模型 Mathematical

21、 Model of LP11 十月 2022301X102X20.33333X30415 十月 202231【例1.5】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。第五年：x7/2+x9=x8+2x5第一年：x1+x2=200(萬元)第二年：(x1/2 +x3)+x4=x2第三年(x3/2+x5)+x6=x4+2x1第四年：(x5/2+x7)+x8=x6+2x3到第六年實有資金總額為x9+2x7，整理

22、后得到下列線性規(guī)劃模型 1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP【解】設 x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資； x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 11 十月 202231【例1.5】投資問題。某投資公司在第15 十月 2022321.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP1X155.28462X2144.71553X3117.07324X405X552.03256X607X7208.13

23、018X809X90最優(yōu)解：Z 416.26萬元x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資；x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 11 十月 2022321.1 線性規(guī)劃的數(shù)學模型 Mat15 十月 202233【例1.6】均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過設備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘?，F(xiàn)有2臺設備A和3臺設備B，每天可供加工時間為8小時。

24、為了保持兩種設備均衡負荷生產(chǎn)，要求一種設備每天的加工總時間不超過另一種設備總時間1小時。怎樣安排設備的加工時間使每天產(chǎn)品的產(chǎn)量最大。【解】 設x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是設備A、B每天加工工時的約束為要求一種設備每臺每天的加工時間不超過另一種設備1小時的約束為 1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP11 十月 202233【例1.6】均衡配套生產(chǎn)問題。某產(chǎn)品15 十月 202234目標函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于整理得到線性規(guī)劃模型 約束線性化。將絕對值約束寫成兩個不等式1.1 線性規(guī)劃的數(shù)學模型 Mathematical M

25、odel of LP11 十月 202234目標函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于整15 十月 2022351.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應用例子2.線性規(guī)劃數(shù)學模型的組成及其特征3.線性規(guī)劃數(shù)學模型的一般表達式。1.1 線性規(guī)劃的數(shù)學模型 Mathematical Model of LP下一節(jié)：圖解法11 十月 2022351.什么是線性規(guī)劃，掌握線性規(guī)劃在管1.2 圖解法 Graphical Method1.2 圖解法 15 十月 202237 通常用于求解含有兩個決策變量的線性規(guī)劃問題。 所求一般模型的線性規(guī)劃問題無需化成標準模型。線性規(guī)劃的圖解法第二章 線性規(guī)劃11 十月

26、202237 通常用于求解含有兩個決策變量max z=5x1+4x2s.t. 3x1+ 5x2152x1+ x25 2x1+ 2x211x1 0, x2015 十月 202238目標函數(shù)等值線最優(yōu)解0 x1x2Z=0Z=4OABCx2 = -5/4 x1 + 1/4 z(10/7,15/7) max z=110/75355/211/211/2可行域1.2 圖解法The Graphical Methodmax z=5x1+4x211 十月 202238目標函15 十月 202239圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非負要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.

27、繪制目標函數(shù)圖形。先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目標函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應的坐標就是最優(yōu)解。一般地，將目標函數(shù)直線放在可行域中 求最大值時直線沿著矢量方向移動 求最小值時沿著矢量的反方向移動1.2 圖解法The Graphical Method11 十月 202239圖解法的步驟：1.求可行解集合。分別15 十月 202240 x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85練

28、習例1.71.2 圖解法The Graphical Method11 十月 202240 x1x2O102030401020315 十月 202241246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)min Z=x1+2x2例1.8(1,2)1.2 圖解法The Graphical Method11 十月 202241246x1x2246最優(yōu)解X=(3,15 十月 202242246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例1.9有無窮多個最優(yōu)解即具有多重解,通解為 01 當=0.5時=(x1,x2)=0.5(1,3)+0.5(3,1)

29、=(2,2) 1.2 圖解法The Graphical Method11 十月 202242246x1x2246X（2）（3,15 十月 202243246x1x2246(1,2)無界解(無最優(yōu)解)max Z=x1+2x2例1.101.2 圖解法The Graphical Method11 十月 202243246x1x2246(1,2)無界解15 十月 202244x1x2O10203040102030405050無可行解即無最優(yōu)解max Z=10 x1+4x2例1.111.2 圖解法The Graphical Method11 十月 202244x1x2O102030401020315 十

30、月 202245由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例1.7例1.8)2.有多重解(例1.9)3.有無界解(例1.10)4.無可行解(例1.11)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解1.2 圖解法The Graphical Method11 十月 202245由以上例題可知，線性規(guī)劃的解有4種形15 十月 2022461.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關鍵有三點 (1)可行解區(qū)域要畫正確 (2)目標函數(shù)增加的方向不能畫錯 (3)目標函數(shù)的直線怎樣平行移動1.2 圖解法The Graphical Method下一節(jié)：線性規(guī)劃的標準型11 十月 20224

31、61.通過圖解法了解線性規(guī)劃有幾種解的1.3 線性規(guī)劃的標準型Standard form of LP1.3 線性規(guī)劃的標準型15 十月 202248線性規(guī)劃問題的標準型特點：(1) 目標函數(shù)求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零(3) 決策變量xj為非負。11 十月 202248線性規(guī)劃問題的標準型特點：15 十月 202249通常設A的秩r（A）= m，且m n。 即AX=b中所包含的 m個方程式彼此 獨立，沒有多余方程，且方程個數(shù)小 于未知量個數(shù)。11 十月 202249通常設A的秩r（A）= m，且m 15 十月 202250約束條件是不等式

32、轉(zhuǎn)化為等式：“”約束 加上松弛變 量 “”約束 減去松弛變量極小化目標函數(shù)轉(zhuǎn)化為極大化：目標函數(shù)系數(shù)變號變量沒有符號限制（unr）轉(zhuǎn)化為變量非負：沒有符號限制的變量用兩個非負變量的差表示變量為非正轉(zhuǎn)化為變量非負用添加負號的變量替換原變量，設新變量為正右端資源向量為非正（b 0） 在資源向量所在方程式兩邊同乘負號 將一般型轉(zhuǎn)化為標準型第二章 線性規(guī)劃11 十月 202250約束條件是不等式轉(zhuǎn)化為等式：“”約15 十月 202251【例1.12】將下列線性規(guī)劃化為標準型 【解】（）因為x3無符號要求 ，即x3取正值也可取負值，標準型中要求變量非負，所以令 1.3 線性規(guī)劃的標準型Standard

33、form of LP11 十月 202251【例1.12】將下列線性規(guī)劃化為標準15 十月 202252 (3)第二個約束條件是號，在號 左端減去剩余變量(Surplus variable)x5，x50。也稱松馳變量1.3 線性規(guī)劃的標準型Standard form of LP(2) 第一個約束條件是號，在左端加入松馳變量 (slack variable) x4，x40,化為等式；(4)第三個約束條件是號且常數(shù)項為負數(shù)，因此在左邊加入松馳變量x6，x60，同時兩邊乘以1。 （5）目標函數(shù)是最小值，為了化為求最大值，令Z=Z,得到max Z=Z，即當Z達到最小值時Z達到最大值，反之亦然。 11

34、十月 202252 (3)第二個約束條件是號，在號15 十月 202253綜合起來得到下列標準型 1.3 線性規(guī)劃的標準型Standard form of LP11 十月 202253綜合起來得到下列標準型 1.3 線性15 十月 202254 當某個變量xj0時,令x/j=xj 。 當某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束 將其化為兩個不等式 再加入松馳變量化為等式。 1.3 線性規(guī)劃的標準型Standard form of LP11 十月 202254 當某個變量xj0時,令x/15 十月 202255【例1.13】將下例線性規(guī)劃化為標準型【解】 此題

35、關鍵是將目標函數(shù)中的絕對值去掉。令 則有1.3 線性規(guī)劃的標準型Standard form of LP11 十月 202255【例1.13】將下例線性規(guī)劃化為標準15 十月 202256得到線性規(guī)劃的標準形式 1.3 線性規(guī)劃的標準型Standard form of LP對于axb(a、b均大于零)的有界變量化為標準形式有兩種方法。 一種方法是增加兩個約束xa及xb 另一種方法是令x=xa，則axb等價于0 xba，增加一個約束xba并且將原問題所有x用x= x+a替換。11 十月 202256得到線性規(guī)劃的標準形式 1.3 線性15 十月 2022571.如何化標準形式？ 可以對照四條標準逐

36、一判斷！ 標準形式是人為定義的，目標函數(shù)可以是求最小值。2.圖解法時不必化為標準型。3.單純形法求解時一定要化為標準型。1.3 線性規(guī)劃的標準型Standard form of LP下一節(jié)：基本概念11 十月 2022571.如何化標準形式？ 可以對照四條1.4 線性規(guī)劃的有關概念Basic Concepts of LP1.4 線性規(guī)劃的有關概念15 十月 202259線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標函數(shù)(1)達到最大值。11 十月 202259線性規(guī)劃問題的解線性規(guī)劃問題求解線性15 十月 202260 可行解：滿足約

37、束條件、的解為可行解。所有可行解的集合為可行域。 最優(yōu)解：使目標函數(shù)達到最大值的可行解。 基：設A為約束條件的mn階系數(shù)矩陣(mn)，其秩為m，B是矩陣A中m階滿秩子矩陣（B0），稱B是規(guī)劃問題的一個基。設：稱 B中每個列向量Pj ( j = 1 2 m) 為基向量。與基向量Pj 對應的變量xj 為基變量。除基變量以外的變量為非基變量。11 十月 202260 可行解：滿足約束條件、的解為15 十月 202261 基解：某一確定的基B，令非基變量等于零，由約束條件方程解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過 基可行解：滿足變量非負約束條件的基本解，

38、簡稱基可行解。 可行基：對應于基可行解的基稱為可行基。非可行解可行解基解基可行解11 十月 202261 基解：某一確定的基B，令非基變量15 十月 202262【例1.14】線性規(guī)劃 求所有基矩陣。 【解】約束方程的系數(shù)矩陣為25矩陣 容易看出r(A)=2，2階子矩陣有C52=10個，其中第1列與第3列構成的2階矩陣不是一個基，基矩陣只有9個，即1.4 基本概念Basic Concepts 11 十月 202262【例1.14】線性規(guī)劃 求所有基矩15 十月 202263 基、基變量、非基變量 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 =目標函數(shù)約束條件行列式0基矩陣右邊

39、常數(shù)基變量: x2, x4, x7非基變量: x1 x3 x5 x6 x8 x9 x10 0基解： （0， x2 ，0 ， x4，0，0，x7，0，0，0）基可行解均0基： = （x2, x4, x7） 11 十月 202263 基、基變量、非基變15 十月 202264基本最優(yōu)解、最優(yōu)解、基本可行解、基本解、可行解的關系如下所示：基本最優(yōu)解基本可行解可行解最 優(yōu) 解基本解例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解。1.4 基本概念Basic Concepts 11 十月 202264基本最優(yōu)解、最優(yōu)解、基本可行解、基本

40、15 十月 202265練習max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A第二章 線性規(guī)劃11 十月 202265練習max z=x1+3x215 十月 202266O451-1243123ABDCEHFIGx1Min z=2x1+3x2s.t. x1+ x24 （1） 2x1+5x2 10 （2） -x1+ x2 1 （3） x1，x2 0約束條件（1）、（2）、（3）的松弛變量或剩余 變量分別為x3、x4、x5x2=0 x3=0 x4=0 x5=0 x1=0以上問題

41、中，有 個基變量， 個非基變量；基解為 ；基可行解為 ；最優(yōu)解為 。32Z=9Z=6A B C D E F G H I OC D HDx2練習11 十月 202266O451-1243123ABDCEH線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解可以在極點上得到15 十月 202267凸集凸集不是凸集極點可行域的性質(zhì)線性規(guī)劃的可行域是凸集11 十月 202267凸集凸集不是凸15 十月 202268凸集：設E是n維歐氏空間的一點集，若X1和X2是E 中的任意兩點，則必有E的連線上的一切點均 屬于點集E，則稱E為凸集。直觀上講：凸集是沒有凹入部分，其內(nèi)部沒有空洞。 極點：設E是凸集，X屬于E，若X不能

42、用不同的兩點 X1和X2的線性組合表示為X = aX1 + (1-a) X2 (0a04010換出行將3化為15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/54001111 十月 202279cj3400icB基變量bx1x215 十月 202280最優(yōu)解X=(18，4，0，0)T，最優(yōu)值Z=70O20301040(3,4)X(3)=(18,4)最優(yōu)解X=(18,4)最優(yōu)值Z=70X(1)=(0,0)2010 x2x1301.5 單純形法 Simplex MethodX(2)=(0,10)11 十月 202280最優(yōu)解X=(1

43、8，4，0，0)T，最15 十月 202281【例1.16】 用單純形法求解【解】將數(shù)學模型化為標準形式：不難看出x4、x5可作為初始基變量，單純法計算結果如表 1.所示 。 1.5 單純形法 Simplex Method11 十月 202281【例1.16】 用單純形法求解【解】15 十月 202282Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j表151/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解X=(

44、25，35/3，0，0，0)T，最優(yōu)值Z=145/31.5 單純形法 Simplex Method11 十月 202282Cj12100bCBXBx1x2x練習題2 設X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn)量（單位為噸），z表示I型和II型餅干所創(chuàng)造的日總利潤15 十月 202283目標： max z = 5X1 +4X2約束條件： 3X1 +5X2 15 （攪拌機的限制） 2X1 + X2 5 （成形機的限制） 2X1 +2X2 11 （烘箱的限制） X1 0 ， X2 0 練習題2 設X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn) 轉(zhuǎn)化為標準模型 引入松弛變量s1 , s2 , s

45、3 0 15 十月 202284目標： max z = 5X1 +4X2約束條件： 3X1 +5X2 + s1 = 15 （攪拌機的限制） 2X1 + X2 + s2 = 5 （成形機的限制） 2X1 +2X2 + s3 = 11 （烘箱的限制） X1, X2, s1 , s2 , s3 0 轉(zhuǎn)化為標準模型11 十月 202284目標： m15 十月 202285基變量CBX1X2S1S2S3b 比值54000S1035100155S202101055/2S30240011111/2 zjj cj-zj00000Z=05400011 十月 202285基變量CBX1X2S1S2S3b 比15

46、十月 202286基變量CBX1X2S1S2S3b 比值54000S1007/21-3/2015/215/7x1511/2005/25S30010-1166 zjj cj-zj55/205/20Z=25/203/20-5/2011 十月 202286基變量CBX1X2S1S2S3b 比15 十月 202287基變量CBX1X2S1S2S3b 比 值54000 x24012/7-3/7015/7x1510-1/75/7010/7S3000-2/7-4/7127/7 zjj cj-zj543/713/70Z=110/700- 3/7-13/70得到最優(yōu)解，最優(yōu)解為：（x1，x2，s1，s2，s3）

47、=（10/7，15/7，0，0，0，27/7）max z=110/711 十月 202287基變量CBX1X2S1S2S3b 比15 十月 202288【例1.18】求解線性規(guī)劃【解】化為標準型1.5 單純形法 Simplex Method11 十月 202288【例1.18】求解線性規(guī)劃【解】化為15 十月 202289初始單純形表為XBx1x2x3x4bx3x43221100114j11002=10, x2進基，而a120，a220且aik（i=1，2,m）則線性規(guī)劃具有無界解1.5 單純形法 Simplex Method11 十月 202293唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變15 十

48、月 202294 在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。1.5.2大M法1.5 單純形法 Simplex Method11 十月 202294 在實際問題中有些模型15 十月 202295人工變量法如果約束條件全為“”，且右邊常數(shù)全為非負，則引進的松弛變量就可以作為初始的基變量，得到一個初始的基礎可行解。如果約束條件有“=” ，右邊常數(shù)全為非負，則需要加上非負人工變量，建立輔助問題。如果約

49、束條件有“”，右邊常數(shù)全為非負，則需要加上非負人工變量，建立輔助問題。11 十月 202295人工變量法15 十月 202296人工變量人工變量11 十月 202296人工變量人工變量15 十月 202297【例1.20】用大M法解 下列線性規(guī)劃1. 大M 單純形法1.5 單純形法 Simplex Method引進松弛變量，使約束條件全為等式。引進人工變量，令人工變量在目標函數(shù)中的系數(shù)為大M （任意大的正數(shù)）用單純形法求解，得到原問題的最優(yōu)解。若基變量中有非零的人工變量，則該LP無可行解。11 十月 202297【例1.20】用大M法解 下列線性規(guī)15 十月 202298【解】首先將數(shù)學模型化

50、為標準形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量x6、x7，目標函數(shù)中加入Mx6Mx7一項，得到人工變量單純形法數(shù)學模型用前面介紹的單純形法求解，見下表。 1.5 單純形法 Simplex Method11 十月 202298【解】首先將數(shù)學模型化為標準形式式中15 十月 202299Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/

51、51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/311 十月 202299Cj32100MMbCBXBx15 十月 2022100（1）初始表中的檢驗數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達式代入目標涵數(shù)消去x6和x7，得到用非基變量表達的目標函數(shù)，其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算，如（2）M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/3注意：

52、1.5 單純形法 Simplex Method11 十月 2022100（1）初始表中的檢驗數(shù)有兩種算法，15 十月 2022101設有線性規(guī)劃其中Amn且r(A)=m,X0應理解為X大于等于零向量，即xj0,j=1,2,n。1.5.3 計算公式1.5 單純形法 Simplex Method11 十月 2022101設有線性規(guī)劃其中Amn且r(A)15 十月 2022102不妨假設A（P1，P2，Pn）中前m個列向量構成一個可行基，記為B=(P1，P2，Pm)。矩陣A中后nm列構成的矩陣記為N（Pm+1,Pn）,則A可以寫成分塊矩陣A=（B，N）。對于基B，基變量為XB=（x1,x2，xm ）T, 非基變量為XN=(xm+1,xm+2,xn)T。則X可表示成 同理將C寫成分塊矩陣C=（CB，CN），CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn) 則AX=b可寫成1.5 單純形法 Simplex Method11 十月 2022102不妨假設A（P1，P2，Pn15 十月 2022103因為r（B）=m（或|B|0）所以B 1存在，因此可有 令非基變量XN=0，XB=B1b，由 B是 可行基的假設，則得到基本可行解X