線性規(guī)劃-數(shù)據(jù)模型與決策的定義

1、數(shù)據(jù)、模型與決策數(shù)據(jù)、模型與決策 線性規(guī)劃線性規(guī)劃Linear Programming1.1 LP的數(shù)學模型的數(shù)學模型 Mathematical Model of LP1.2 圖解法圖解法 Graphical Method1.3 標準型標準型 Standard form of LP1.4 基本概念基本概念 Basic Concepts1.5 單純形法單純形法 Simplex Method12/28/20211.1 數(shù)學模型數(shù)學模型 Mathematical Model 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 3 1.1 線性規(guī)劃的數(shù)學模

2、型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP 線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運行等問線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運行等問題。例如，當任務或目標確定后，如何統(tǒng)籌兼顧，合理安題。例如，當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源排，用最少的資源 （如資金、設(shè)備、原標材料、人工、時（如資金、設(shè)備、原標材料、人工、時間等）去完成確定的任務或目標；企業(yè)在一定的資源條件間等）去完成確定的任務或目標；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多量最多 、利潤最大）。、

3、利潤最大）。線性規(guī)劃線性規(guī)劃（Linear Programming,縮寫為LP）是運籌學的重要是運籌學的重要分支之一，在實際中應用得較廣泛，其方法也較成熟，借助分支之一，在實際中應用得較廣泛，其方法也較成熟，借助計算機，使得計算更方便，應用領(lǐng)域更廣泛和深入。計算機，使得計算更方便，應用領(lǐng)域更廣泛和深入。12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 4 【例例1.1】最優(yōu)生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、最優(yōu)生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要要在設(shè)備A、B上

4、加工，需上加工，需要消耗材料要消耗材料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工及所需要的資源如表工及所需要的資源如表1.1所示。已知在計劃期內(nèi)設(shè)備的加工能所示。已知在計劃期內(nèi)設(shè)備的加工能力各為力各為200臺時，可供材料分別為臺時，可供材料分別為360、300公斤；每生產(chǎn)一件甲、公斤；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定元，假定市場需求無限制。企業(yè)決策者應如何安排生產(chǎn)計劃，使企業(yè)在市場需求無限制。企業(yè)決策者應如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大？計劃期內(nèi)總的利潤收

5、入最大？1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP1.1.1 應用模型舉例應用模型舉例12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 5 表表1.1 產(chǎn)品資源消耗產(chǎn)品資源消耗1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 6 321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxx

6、xxxxxxx，【解解】設(shè)設(shè)x1、x2、x3 分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學模型分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學模型為：為：1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP最優(yōu)解最優(yōu)解X=(50,30,10);Z=340012/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 7 線性規(guī)劃的數(shù)學模型由線性規(guī)劃的數(shù)學模型由決策變量決策變量 Decision variables 目標函數(shù)目標函數(shù)Objective function及約束條件及約束條件Constraints構(gòu)成。稱為三個要素構(gòu)成。稱為三個要

7、素。n其特征是：其特征是：n1解決問題的目標函數(shù)是多個決策變量的解決問題的目標函數(shù)是多個決策變量的 線性函數(shù)，通常是求最大值或線性函數(shù)，通常是求最大值或 最小值；最小值；n2解決問題的解決問題的是一組多個決策變量是一組多個決策變量 的線性不等式或等式。的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？怎樣辨別一個模型是線性規(guī)劃模型？1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 8 【例例1.2】某商場決定：營業(yè)員每周連續(xù)工作某商場決定：營業(yè)員每周連

8、續(xù)工作5天后連續(xù)休息天后連續(xù)休息2天，天，輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表1.2所示。所示。表表1.2 營業(yè)員需要量統(tǒng)計表營業(yè)員需要量統(tǒng)計表商場人力資源部應如何安排每天的上班人數(shù)，使商場總的營業(yè)員商場人力資源部應如何安排每天的上班人數(shù)，使商場總的營業(yè)員最少。最少。 1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 9 【解解】 設(shè)設(shè)xj(j=1，2，7)為休息為休息2天后星期一到星期日開始上班天后星

9、期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為的營業(yè)員，則這個問題的線性規(guī)劃模型為 7 ,2, 1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 10 最優(yōu)解：最優(yōu)解：Z617（人）人）12/28/2021 制作與教學

10、 線性規(guī)劃線性規(guī)劃Linear Programming Page 11 【例例1.3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是些軸的規(guī)格分別是1.5，1，0.7（m），），這些軸需要用同一種圓鋼來做，圓鋼長這些軸需要用同一種圓鋼來做，圓鋼長度為度為4 m?，F(xiàn)在要制造現(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？ 【解解】這是一個條材下料問題這是一個條材下料問題 ，設(shè)切口寬度為零。，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)

11、分別為乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式則切割方式可用不等式1.5y1+y2+0.7y34表示，求這個不等式關(guān)于表示，求這個不等式關(guān)于y1，y2，y3的非負整數(shù)解。象這樣的非負整數(shù)解。象這樣的非負整數(shù)解共有的非負整數(shù)解共有10組，也就是有組，也就是有10種下料方式，如表種下料方式，如表1.3所示。所示。表表13 下料方案下料方案1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 12 設(shè)設(shè)xj(j=1,2,10)為第為第j種下料

12、方案所用圓鋼的根數(shù)。則用料最少種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學模型數(shù)學模型求下料方案時應注意，余料不能超過最短毛坯的長度；最好將毛求下料方案時應注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計。如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。算機編程排方案，去掉余料較長的方案，進行初選。102 , 1, 010005423210002342100022min1098754298

13、7643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 13 Z812.512/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 14 【例例1.4】配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于是：錫不少于28%，鋅不多于，鋅不多于15%，鉛恰好，鉛恰好10%，鎳要界于，鎳要界

14、于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級之間，不允許有其他成分。鋼鐵公司擬從五種不同級別的礦石中進行冶煉，每種礦物的成分含量和價格如表別的礦石中進行冶煉，每種礦物的成分含量和價格如表1.4所示。所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。量。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。表表1.4 礦石的金屬含量礦石的金屬含量1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性

15、規(guī)劃線性規(guī)劃Linear Programming Page 15 解解: 設(shè)設(shè)xj（j=1,2，5）是第是第j 種礦石數(shù)量，得到下列線性規(guī)劃模種礦石數(shù)量，得到下列線性規(guī)劃模型型 注意，礦石在實際冶煉時金屬含量會發(fā)生變化，建模時應將這種注意，礦石在實際冶煉時金屬含量會發(fā)生變化，建模時應將這種變化考慮進去，有可能是非線性關(guān)系。配料問題也稱配方問題、變化考慮進去，有可能是非線性關(guān)系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP123451

16、2451345135123451234512min3402601802301900.250.40.20.080.280.10.150.20.050.150.10.050.150.10.250.30.20.40.170.550.250.30.20.40.170.350.70.7Zxxxxxxxxxxxxxxxxxxxxxxxxxxxx3450.40.80.4510,1,2,5jxxxxj12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 16 最優(yōu)解：最優(yōu)解：Z=347.51.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Mod

17、el of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 17 【例例1.5】投資問題。某投資公司在第一年有投資問題。某投資公司在第一年有200萬元資金，每年都有如下的萬元資金，每年都有如下的投資方案可供考慮采納：投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一，那么到第三年就可回收第一年投入資金的一倍金額倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。多。第

18、五年：第五年：(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，整理后得到下列線性規(guī)劃模型整理后得到下列線性規(guī)劃模型 1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP【解解】設(shè)設(shè) x1：第一年的投資；第一年的投資； x2：第一年的保留資金第一年的保留資金 x3：第二年新的投資；第二年新的投資；x4：第二年的保留資金

19、第二年的保留資金 x5：第三年新的投資；第三年新的投資； x6：第三年的保留資金第三年的保留資金 x7：第四年新的投資第四年新的投資 x8：第四年的保留資金第四年的保留資金 x9：第五年的保留資金第五年的保留資金 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 18 7912123413456356785789max22002220422204222042200,1,2,9jZxxxxxxxxxxxxxxxxxxxxxxxj1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP最優(yōu)解：最優(yōu)解：Z 416.

20、26萬元萬元x1：第一年的投資；第一年的投資； x2：第一年的保留資金第一年的保留資金 x3：第二年新的投資；第二年新的投資；x4：第二年的保留資金第二年的保留資金 x5：第三年新的投資；第三年新的投資； x6：第三年的保留資金第三年的保留資金 x7：第四年新的投資第四年新的投資 x8：第四年的保留資金第四年的保留資金 x9：第五年的保留資金第五年的保留資金 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 19 【例例1.6】均衡配套生產(chǎn)問題。某產(chǎn)品由均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、件甲、3件乙零件組裝而成。件乙零件組裝而成。兩種零件必須經(jīng)過

21、設(shè)備兩種零件必須經(jīng)過設(shè)備A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工時上的加工時間分別為間分別為5分鐘和分鐘和9分鐘，每件乙零件在分鐘，每件乙零件在A、B上的加工時間分別為上的加工時間分別為4分分鐘和鐘和10分鐘?，F(xiàn)有分鐘?，F(xiàn)有2臺設(shè)備臺設(shè)備A和和3臺設(shè)備臺設(shè)備B，每天可供加工時間為每天可供加工時間為8小時。小時。為了保持兩種設(shè)備均衡負荷生產(chǎn)，要求一種設(shè)備每天的加工總時間不為了保持兩種設(shè)備均衡負荷生產(chǎn)，要求一種設(shè)備每天的加工總時間不超過另一種設(shè)備總時間超過另一種設(shè)備總時間1小時。怎樣安排設(shè)備的加工時間使每天產(chǎn)品的小時。怎樣安排設(shè)備的加工時間使每天產(chǎn)品的產(chǎn)量最大。產(chǎn)量最大?！窘饨?/p>

22、】 設(shè)設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是)31,21min(21xxy 設(shè)備設(shè)備A、B每天加工工時的約束為每天加工工時的約束為60831096082452121xxxx要求一種設(shè)備每臺每天的加工時間不超過另一種設(shè)備要求一種設(shè)備每臺每天的加工時間不超過另一種設(shè)備1小時的約小時的約束為束為 60)109()452121xxxx（1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 20 目標函

23、數(shù)線性化。產(chǎn)品的產(chǎn)量目標函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于等價于2131,21xyxy整理得到線性規(guī)劃模型整理得到線性規(guī)劃模型 約束線性化。將絕對值約束寫成兩個不等式約束線性化。將絕對值約束寫成兩個不等式60)109()45(60)109()45(21212121xxxxxxxx1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Pag

24、e 21 1.1.2 線性規(guī)劃的一般模型線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學模型中，有一般地，假設(shè)線性規(guī)劃數(shù)學模型中，有m個約束，有個約束，有n個決策變量個決策變量xj, j=1,2,n，目標函數(shù)的變量系數(shù)用目標函數(shù)的變量系數(shù)用cj表示表示, cj稱為稱為價值系數(shù)價值系數(shù)。約。約束條件的變量系數(shù)用束條件的變量系數(shù)用aij表示，表示，aij稱為稱為工藝系數(shù)工藝系數(shù)。約束條件右端的。約束條件右端的常數(shù)用常數(shù)用bi表示，表示，bi稱為稱為資源限量資源限量。則線性規(guī)劃數(shù)學模型的一般表達。則線性規(guī)劃數(shù)學模型的一般表達式可寫成式可寫成1 1221111221121 1222221 122max(mi

25、n)(, )(, )(, )0,1,2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或為了書寫方便，上式也可寫成：為了書寫方便，上式也可寫成： 1.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 22 11max(min)(, )1,2,0,1,2,njjjnijjijjZc xa xbinxjn 或在實際中一般在實際中一般xj0,但有時但有時xj0或或xj無符號限制。無符號限制。1.1

26、 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 23 1.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應用例子幾個應用例子2.線性規(guī)劃數(shù)學模型的組成及其特征線性規(guī)劃數(shù)學模型的組成及其特征3.線性規(guī)劃數(shù)學模型的一般表達式。線性規(guī)劃數(shù)學模型的一般表達式。作業(yè)：教材作業(yè)：教材P31 T 2，3，4，5，61.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型 Mathematical Model of LP下一節(jié)：圖解法下一節(jié)：圖解法12

27、/28/20211.2 圖解法圖解法 Graphical Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 25 圖解法的步驟：圖解法的步驟：1.求可行解集合。求可行解集合。分別求出滿足每個約束包括變量非分別求出滿足每個約束包括變量非 負要求負要求的區(qū)域，其交集就是可行解集合，或稱為的區(qū)域，其交集就是可行解集合，或稱為可行域可行域；2.繪制目標函數(shù)圖形。繪制目標函數(shù)圖形。先過原點作一條矢量指向點（先過原點作一條矢量指向點（c1,c2)，矢矢量的方向就是目標函數(shù)增加的方向，稱為梯度方向，再作一量的方向就是目標函數(shù)增加的方向，稱為梯度方向

28、，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；3.求最優(yōu)解。求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應的坐標就是直線與可行域相交的點對應的坐標就是最優(yōu)解。最優(yōu)解。一般地，將目標函數(shù)直線放在可行域中一般地，將目標函數(shù)直線放在可行域中 求最大值時直線沿著矢量方向移動求最大值時直線沿著矢量方向移動 求最小值時沿著矢量的反方向移動求最小值時沿著矢量的反方向移動1.2 圖解法圖解法The Graphical Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Lin

29、ear Programming Page 26 x1x2O1020304010203040(3,4)(15,10)最優(yōu)解最優(yōu)解X=(15,10)最優(yōu)值最優(yōu)值Z=8540221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例1.72143maxxxZ1.2 圖解法圖解法The Graphical Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 27 246x1x2246最優(yōu)解最優(yōu)解X=(3,1)最優(yōu)值最優(yōu)值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2例例1.

30、8(1,2)1.2 圖解法圖解法The Graphical Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 28 246x1x2246X（2）（3,1）X（1）（1,3）(5,5)006346321212121xxxxxxxx、min Z=5x1+5x2例例1.9有無窮多個最優(yōu)解有無窮多個最優(yōu)解即具有多重解即具有多重解,通解為通解為 01 ,)1 ()2() 1 (XXX 當當=0.5時時=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 圖解法圖解法The Graphical Method12/28/2021

31、 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 29 246x1x2246(1,2)006346321212121xxxxxxxx、無界解無界解(無最優(yōu)解無最優(yōu)解)max Z=x1+2x2例例1.1012/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 30 x1x2O102030401020304050500,050305 .140221212121xxxxxxxx無無可行解可行解即無最優(yōu)解即無最優(yōu)解max Z=10 x1+4x2例例1.111.2 圖解法圖解法The Graphical Method12/28/202

32、1 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 31 由由以上例題可知，線性規(guī)劃的解有以上例題可知，線性規(guī)劃的解有4種形式種形式：1.有唯一最優(yōu)解有唯一最優(yōu)解(例例1.7例例1.8)2.有多重解有多重解(例例1.9)3.有無界解有無界解(例例1.10)4.無可行解無可行解(例例1.11)1、2情形為有最優(yōu)解情形為有最優(yōu)解3、4情形為無最優(yōu)解情形為無最優(yōu)解1.2 圖解法圖解法The Graphical Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 32 1.通過圖解法了解線性規(guī)劃有幾種解的形式通過圖解

33、法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點作圖的關(guān)鍵有三點 (1)可行解區(qū)域要畫正確可行解區(qū)域要畫正確 (2)目標函數(shù)增加的方向不能畫錯目標函數(shù)增加的方向不能畫錯 (3)目標函數(shù)的直線怎樣平行移動目標函數(shù)的直線怎樣平行移動作業(yè)：教材作業(yè)：教材P34 T7 1.2 圖解法圖解法The Graphical Method下一節(jié)：線性規(guī)劃的標準型下一節(jié)：線性規(guī)劃的標準型12/28/20211.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 34 在用單純法求解線性規(guī)劃問題時

34、，為了討論問題在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP線性規(guī)劃問題的標準型為線性規(guī)劃問題的標準型為:1目標函數(shù)求最大值（或求最小值）目標函數(shù)求最大值（或求最小值）2約束條件都為等式方程約束條件都為等式方程3變量變量xj非負非負4常數(shù)常數(shù)bi非負非負12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 35 mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2,

35、 1,0,2, 1,02211222222111212111max(或min)Z=c1x1+c2x2+cnxn1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP注：本教材默認目標函數(shù)是注：本教材默認目標函數(shù)是 max12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 36 njjjxcZ1maxminjxbxajnjijij, 2 , 1, 2 , 1, 010maxXbAXCXZ或?qū)懗上铝行问交驅(qū)懗上铝行问剑?或用矩陣形式或用矩陣形式1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/2

36、8/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 37 111211121222221212, , , )nnnmmm nnmaaaxbaaaxbAXbCc ccaaaxb ； (通常通常X記為：記為： 稱為約束方稱為約束方程的系數(shù)矩陣，程的系數(shù)矩陣，m是約束方程的個數(shù)，是約束方程的個數(shù)，n是決策變量的個數(shù)，是決策變量的個數(shù)，一般情況一般情況mn，且，且r()m。TnxxxX),21（m ax0ZC XA XbX其中其中:1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Lin

37、ear Programming Page 38 【例例1.12】將下列線性規(guī)劃化為標準型將下列線性規(guī)劃化為標準型 3213minxxxZ無符號要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx【解解】（）因為（）因為x3無符號要求無符號要求 ，即，即x3取正值也取正值也可取負值，標準型中要求變量非負，所以令可取負值，標準型中要求變量非負，所以令 0,33333 xxxxx其中1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 39

38、 (3)第二個約束條件是第二個約束條件是號，在號，在號號 左左端減去剩余變量端減去剩余變量(Surplus variable)x5，x50。也稱松馳變也稱松馳變量量3213minxxxZ無符號要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP(2) 第一個約束條件是第一個約束條件是號，在號，在左端左端加入松馳變量加入松馳變量 (slack variable) x4，x40,化為等式；化為等式；(4)第三個約束條件是第三個約束條件是號且常數(shù)項為負數(shù)，因此在號且常數(shù)項為負數(shù)，因

39、此在左邊加入松左邊加入松馳變量馳變量x6，x60，同時兩邊乘以同時兩邊乘以1。 （5）目標函數(shù)是最小值，為了化為求最大值，令）目標函數(shù)是最小值，為了化為求最大值，令Z=Z,得到得到max Z=Z，即當即當Z達到最小值時達到最小值時Z達到最大值，反之亦然。達到最大值，反之亦然。 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 40 綜合起來得到下列標準型綜合起來得到下列標準型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 線性規(guī)劃的標準型線性規(guī)劃的

40、標準型Standard form of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 41 當某個變量當某個變量xj0時時,令令x/j=xj 。 當某個約束是絕對值不等式當某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束時，將絕對值不等式化為兩個不等式，再化為等式，例如約束 974321xxx將其化為兩個不等式將其化為兩個不等式 974974321321xxxxxx再加入松馳變量化為等式。再加入松馳變量化為等式。 1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/28/2021

41、 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 42 【例例1.13】將下例線性規(guī)劃化為標準型將下例線性規(guī)劃化為標準型無約束、211212145|maxxxxxxxxZ【解解】 此題關(guān)鍵是將目標函數(shù)中的絕對值去掉。此題關(guān)鍵是將目標函數(shù)中的絕對值去掉。令令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 則有則有1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programm

42、ing Page 43 得到線性規(guī)劃的標準形式得到線性規(guī)劃的標準形式 112211223114112234max()()540Zxxxxxxxxxxxxxxxxxx 、 、 、 、 、1.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP對于對于axb(a、b均大于零均大于零)的有界變量化為標準形式有兩種方的有界變量化為標準形式有兩種方法，一種方法是增加兩個約束法，一種方法是增加兩個約束xa及及xb，另一種方法是令另一種方法是令=xa，則，則axb等價于等價于0ba，增加一個約束增加一個約束ba并且將原問并且將原問題所有題所有x用用x=+a替換。替換。12/28/202

43、1 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 44 1.如何化標準形式？如何化標準形式？ 可以對照四條標準逐一判斷！可以對照四條標準逐一判斷！ 標準形式是人為定義的，目標函數(shù)可以是求最小值。標準形式是人為定義的，目標函數(shù)可以是求最小值。2.用用WinQSB軟件求解時，不必化成標準型。軟件求解時，不必化成標準型。圖解法時不必化為標準型。圖解法時不必化為標準型。3.單純形法求解時一定要化為標準型。單純形法求解時一定要化為標準型。作業(yè)：教材作業(yè)：教材P34 T 81.3 線性規(guī)劃的標準型線性規(guī)劃的標準型Standard form of LP下一節(jié)：基本概念下一節(jié)：基

44、本概念12/28/20211.4 線性規(guī)劃的有關(guān)概念線性規(guī)劃的有關(guān)概念Basic Concepts of LP12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 46 設(shè)線性規(guī)劃的標準型設(shè)線性規(guī)劃的標準型 max Z=CX （1.1） AX=b （1.2） X 0 （1.3）式中式中A 是是mn矩陣，矩陣，mn并且并且r（A）=m，顯然顯然A中至少有中至少有一個一個mm子矩陣子矩陣B，使得使得r（B）=m。1.4 基本概念基本概念Basic Concepts 基基 (basis)A中中mm子矩陣子矩陣B并且有并且有r（B）=m，則稱則稱B是線性規(guī)是

45、線性規(guī)劃的一個基（或基矩陣劃的一個基（或基矩陣basis matrix ）。當）。當m=n時，基矩陣唯一，時，基矩陣唯一，當當mn時，基矩陣就可能有多個，但數(shù)目不超過時，基矩陣就可能有多個，但數(shù)目不超過mnC12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 47 【例例1.14】線性規(guī)劃線性規(guī)劃 32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩陣求所有基矩陣。 【解解】約束方程的系數(shù)矩陣為約束方程的系數(shù)矩陣為25矩陣矩陣 10261001115A,610151B,010152B,110053

46、B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2階子矩陣有階子矩陣有C52=10個，其中第個，其中第1列與第列與第3列構(gòu)成列構(gòu)成的的2階矩陣不是一個基，基矩陣只有階矩陣不是一個基，基矩陣只有9個，即個，即1.4 基本概念基本概念Basic Concepts 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 48 由線性代數(shù)知，基矩陣由線性代數(shù)知，基矩陣B必為非奇異矩陣并且必為非奇異矩陣并且|B|0。當矩當矩陣陣B的行列式等式零即的行列式等式零即|B|=0時就不是基時就不是基 當確定

47、某一矩陣為基矩陣時，則基矩陣對應的列向量稱為當確定某一矩陣為基矩陣時，則基矩陣對應的列向量稱為基基向量向量(basis vector)，其余列向量稱為其余列向量稱為非基向量非基向量 基向量對應的變量稱為基向量對應的變量稱為基變量基變量(basis variable)，非基向量非基向量對應的變量稱為對應的變量稱為非基變量非基變量 在上例中在上例中B2的基向量是的基向量是A中的第一列和第四列，其余列向量中的第一列和第四列，其余列向量是非基向量，是非基向量，x1、x4是基變量，是基變量，x2、x3、x5是非基變量?；兪欠腔兞??；兞?、非基變量是針對某一確定基而言的，不同的基對應的基量、非基變量是

48、針對某一確定基而言的，不同的基對應的基變量和非基變量也不同。變量和非基變量也不同。010152B10261001115A1.4 基本概念基本概念Basic Concepts 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 49 可行解可行解(feasible solution) 滿足式（滿足式（1.2）及（）及（1.3）的解）的解X=（x1,x2，xn)T 稱為可行解稱為可行解 ?；究尚薪饣究尚薪?basis feasible solution) 若基本解是可行解則稱若基本解是可行解則稱為是基本可行解（也稱基可行解）。為是基本可行解（也稱基

49、可行解）。 例如，例如， 與與X=（0，0，0，3，2，），）都是例都是例1 的可行解。的可行解。 TX) 1 ,27,21, 0 , 0( 基本解基本解(basis solution) 對某一確定的基對某一確定的基B，令非基變量等于零，令非基變量等于零，利用式（利用式（1.） 解出基變量，則這組解稱為基解出基變量，則這組解稱為基的基的基本解。本解。 最優(yōu)解最優(yōu)解(optimal solution) 滿足式滿足式 （1 .1）的可行解稱為最優(yōu)解，）的可行解稱為最優(yōu)解，即是使得目標函數(shù)達到最大值的可行解就是最優(yōu)解，例即是使得目標函數(shù)達到最大值的可行解就是最優(yōu)解，例如可行解如可行解 是例是例2的最

50、優(yōu)解。的最優(yōu)解。TX)8 ,0,0,0,53(非可行解非可行解(Infeasible solution) 無界解無界解 (unbound solution)1.4 基本概念基本概念Basic Concepts 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 50 顯然，只要基本解中的基變量的解滿足式（顯然，只要基本解中的基變量的解滿足式（1.）的非負要求，）的非負要求，那么這個基本解就是基本可行解。那么這個基本解就是基本可行解。 在例在例1.13中，對中，對來說，來說，x1,x2是基變量，是基變量，x3,x4，x5是非基變量，是非基變量，令令x

51、3=x4=x5=0，則式（則式（1.）為）為2610352121xxxx,610151B對對B2來說，來說，x1,x4,為基變量，令非變量為基變量，令非變量x2,x3,x5為零，由式為零，由式（1.2）得到）得到 ，x4=4，511x因因|B1|，由克萊姆法則知，由克萊姆法則知，x1、x2有唯一解有唯一解x12/5,x2=1則則 基基本解為本解為TX)0 , 0 , 0 , 1 ,52()1(1.4 基本概念基本概念Basic Concepts 12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 51 由于由于 是基本解，從而它是基本可行解，在是基

52、本解，從而它是基本可行解，在 中中x10i表表1-4(1)XBx1x2x3x4bx3211040 x4130130j3400 (2)x3x2j (3)x1 x2 j 基變量基變量110001/301/3105/31- -1/3405/30- -4/330103/5- -1/51801- -1/5 2/5400- -1- -1將將3化為化為1乘乘以以1/3后后得得到到1.5 單純形法單純形法 Simplex Method301812/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 64 最優(yōu)解最優(yōu)解X=(18，4，0，0)T，最優(yōu)值最優(yōu)值Z=70O20

53、301040(3,4)X(3)=(18,4)最優(yōu)解最優(yōu)解X=(18,4)最優(yōu)值最優(yōu)值Z=7040221xx305 . 121xx0,30340243max432142132121xxxxxxxxxxxxZX(1)=(0,0)2010 x2x1301.5 單純形法單純形法 Simplex Method0, 0305 . 1402212121xxxxxxX(2)=(0,10)12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 65 單純形法全過程的計算，可以用列表的方法計算更為簡潔，單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形

54、表（表這種表格稱為單純形表（表1.4）。）。計算步驟計算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零；基變量的檢驗數(shù)必為零； 2.判斷：判斷： （a）若）若j（j，n）得到最解；得到最解； （b）某個某個k0且且aik（i=1，2,m）則線性規(guī)劃具有無則線性規(guī)劃具有無界解界解(見例見例1.18)。 （c）若存在若存在k0且且aik (i=1,m)不全非正，則進行換基；不全非正，則進行換基；1.5 單純形法單純形法 Simplex Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Pr

55、ogramming Page 66 min0,0,iiLikikikikbbaaM Maa當 時為任意大的正數(shù)第第個比值最小個比值最小 ，選最小比值對應行的基變量為出基變量，選最小比值對應行的基變量為出基變量，若有相同最小比值，則任選一個。若有相同最小比值，則任選一個。aLk為主元素；為主元素； (c）求新的基可行解：用初等行變換方法將求新的基可行解：用初等行變換方法將aLk 化為化為,k列列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。行解，再判斷是否得到最優(yōu)解。（b）選出基變量選出基變量 ，求最小比值：，

56、求最小比值：1.5 單純形法單純形法 Simplex Method3.換基：換基：（a）選進基變量選進基變量設(shè)設(shè)k=max j | j 0,xk為進基變量為進基變量12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 67 【例例1.16】 用單純形法求解用單純形法求解3212maxxxxZ02053115232321321321xxxxxxxxx、【解解】將數(shù)學模型化為標準形式：將數(shù)學模型化為標準形式：3212maxxxxZ5 , 2 , 1, 0205311523253214321jxxxxxxxxxj不難看出不難看出x4、x5可作為初始基變量，

57、單純法計算結(jié)果如可作為初始基變量，單純法計算結(jié)果如表表 1.所示所示 。 1.5 單純形法單純形法 Simplex Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 68 Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表表151/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值最優(yōu)值Z=145/

58、31.5 單純形法單純形法 Simplex Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 69 【例例1.17】用單純形法求解用單純形法求解 42122minxxxZ5 , 1, 0212665521421321jxxxxxxxxxxj【解解】 這是一個極小化的線性規(guī)劃問題這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問可以將其化為極大化問題求解題求解,也可以直接求解也可以直接求解,這時判斷標準是：這時判斷標準是：j0(j=1，n)時得時得到最優(yōu)解到最優(yōu)解。容易觀察到容易觀察到,系數(shù)矩陣中有一個系數(shù)矩陣中有一個3階單位矩陣階單位

59、矩陣,x3、x4、x5為基變量為基變量。目標函數(shù)中含有基變量。目標函數(shù)中含有基變量x4,由第二個約束得到由第二個約束得到x4=6+x1x2，并代并代入目標函數(shù)消去入目標函數(shù)消去x4得得12121222(6)6Zxxxxxx 1.5 單純形法單純形法 Simplex Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 70 XBx1x2x3x4x5bx3x4x51- -1611210001000156215621/2j1- -1000 x2x4x51- -241001- -1- -20100015111 j20100 表中表中j0,j=1

60、,2,5所以最優(yōu)解為所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值最優(yōu)值 Z=2x12x2x4=251=11極小值問題極小值問題,注意判斷標準注意判斷標準,選進基變量時選進基變量時,應選應選j0, x2進基，而進基，而a120，a220且且aik（i=1，2,m）則線則線性規(guī)劃具有無界解性規(guī)劃具有無界解退化基本可行解的判斷退化基本可行解的判斷:存在某個基變量為零的基本可存在某個基變量為零的基本可行解。行解。1.5 單純形法單純形法 Simplex Method12/28/2021 制作與教學 線性規(guī)劃線性規(guī)劃Linear Programming Page 77 在實際問題中有些模型并不含有單