數(shù)學(xué)線性規(guī)劃PPT學(xué)習(xí)教案

1、數(shù)學(xué)線性規(guī)劃數(shù)學(xué)線性規(guī)劃1.1 數(shù)學(xué)模型 Mathematical Model 第1頁/共107頁1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP線性規(guī)劃（Linear Programming,縮寫為LP）確定的任務(wù)或目標；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多 、利潤最大）。第2頁/共107頁【例1-1】生產(chǎn)計劃問題。某企業(yè)在計劃期內(nèi)計劃生產(chǎn)甲、乙兩種產(chǎn)品。按工藝資料規(guī)定，每件產(chǎn)品甲需要消耗材料A 2公斤，消耗材料B 1公斤，每件產(chǎn)品乙需要消耗材料A 1公斤，消耗材料B 1.5公斤。已知在計劃期內(nèi)可供材料分別為40、30公斤；

2、每生產(chǎn)一件甲、乙兩產(chǎn)品，企業(yè)可獲得利潤分別為40、30元，如表11所示。假定市場需求無限制。企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP1.1.1 應(yīng)用模型舉例第3頁/共107頁12max300400Zxx【解】設(shè)x1、x2分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為：1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙現(xiàn)有資現(xiàn)有資源源材料材料C材料材料D利潤（元利潤（元/件）件） 1212122401.5300,0 xxxxxx表1-1第4頁/共107

3、頁線性規(guī)劃的數(shù)學(xué)模型由決策變量 Decision variables 目標函數(shù)Objective function及約束條件Constraints構(gòu)成。稱為三個要素。n其特征是：n1解決問題的目標函數(shù)是多個決策變量的 線性函數(shù)，通常是求最大值或 最小值；n2解決問題的是一組多個決策變量 的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第5頁/共107頁【例1-2】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據(jù)統(tǒng)計，商場每天需要的營業(yè)員如表1-2所示。表1-2 營業(yè)員需要量統(tǒng)計表商場人力資源部應(yīng)如何

4、安排每天的上班人數(shù)，使商場總的營業(yè)員最少。 星期星期需要人數(shù)需要人數(shù)星期星期需要人數(shù)需要人數(shù)一一300五五480二二300六六600三三350日日550四四4001.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第6頁/共107頁【解】 設(shè)xj(j=1，2，7)為休息2天后星期一到星期日開始上班的營業(yè)員，則這個問題的線性規(guī)劃模型為 7 ,2, 1,0550600480400350300300min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZ

5、j1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP星星期期需要需要人數(shù)人數(shù)星星期期需要需要人數(shù)人數(shù)一一300五五480二二300六六600三三350日日550四四400第7頁/共107頁1 1 X1X10 0 C1C1404404 =3003001041042 2 X2X26767 C2C2301301 =3003001 13 3 X3X3146146 C3C3350350 =3503500 04 4 X4X4170170 C4C4400400 =4004000 05 5 X5X59797 C5C5480480 =4804800 06 6 X6X6120120 C6

6、C6600600 =6006000 07 7 X7X71717 C7C7550550 =5505500 0最優(yōu)解：Z617（人）1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第8頁/共107頁【例1-3】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4 m。現(xiàn)在要制造1000輛汽車，最少要用多少圓鋼來生產(chǎn)這些軸？ 【解】這是一個條材下料問題 ，設(shè)切口寬度為零。 設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1，y2，y3,則切割方式可用不等式1.5y1+y2+0.7y34表

7、示，求這個不等式關(guān)于y1，y2，y3的非負整數(shù)解。象這樣的非負整數(shù)解共有10組，也就是有10種下料方式，如表1-3所示。表1-3 下料方案 方案方案規(guī)格規(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ù)學(xué)模型 Mathematical Model of LP第9頁/共107頁設(shè)xj(j=1,2,10)為第j種下料方案所用圓鋼的根數(shù)。則用料最少數(shù)學(xué)模型求下料方案時應(yīng)注意，余料不能超過最短

8、毛坯的長度；最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。102 , 1, 010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 方案方案規(guī)格規(guī)格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 124

9、51000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.5第10頁/共107頁1 1 X1X15005002 2 X2X20 03 3 X3X30 04 4 X4X40 05 5 X5X50 06 6 X6X662.562.57 7 X7X70 08 8 X8X80 09 9 X9X92502501010 X10X100 0Z812.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第11頁/共107頁【例1-4】配料問題。某鋼鐵公司生產(chǎn)一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許

10、有其他成分。鋼鐵公司擬從五種不同級別的礦石中進行冶煉，每種礦物的成分含量和價格如表1-4所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中，合金含量沒有發(fā)生變化。表1-4 礦石的金屬含量 合金合金礦石礦石錫錫%鋅鋅%鉛鉛%鎳鎳%雜質(zhì)雜質(zhì)費用（元費用（元/t ）1251010253034024000303026030155206018042020040202305851517551901.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第12頁/共107頁解: 設(shè)xj（j=1,2，5）是第j 種礦石數(shù)量，得到下列線性規(guī)劃模型 注意，礦石

11、在實際冶煉時金屬含量會發(fā)生變化，建模時應(yīng)將這種變化考慮進去，有可能是非線性關(guān)系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產(chǎn)中都能遇到。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP礦石礦石錫錫%鋅鋅%鉛鉛%鎳鎳%雜質(zhì)雜質(zhì)費用（元費用（元/t ）1251010253034024000303026030155206018042020040202305851517551901234512451345135123451234512min3402601802301900.250.40.20.080.280.10.150.20.050.150.10.050.15

12、0.10.250.30.20.40.170.550.250.30.20.40.170.350.70.7Zxxxxxxxxxxxxxxxxxxxxxxxxxxxx3450.40.80.4510,1,2,5jxxxxj第13頁/共107頁1 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最優(yōu)解：Z=347.51.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第14頁/共107頁1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP【例1-

13、5】投資問題。某投資公司擬將5000萬元的資金用于國債、地方國債及基金三種類型證券投資，每類各有兩種。每種證券的評級、到期年限及每年稅后收益率見表1-5所示。表15 證券投資方案序序號號證券類型證券類型 評級評級 到期年限到期年限 每年稅后每年稅后收益率收益率(%)1國債國債1 1 83.22國債國債2 1 103.83地方債券地方債券1 2 44.34地方債券地方債券2 3 64.75基金基金1 4 34.26基金基金2 5 44.6 決策者希望：國債投資額不少于1000萬，平均到期年限不超過5年，平均評級不超過2。問每種證券各投資多少使總收益最大。 第15頁/共107頁1.1 線性規(guī)劃的數(shù)

14、學(xué)模型 Mathematical Model of LP解 設(shè)xj(j=1,2,，6)為第j種證券的投資額，目標函數(shù)是稅后總收益為123456(8 3.210 3.84 4.36 4.73 4.24 4.6)/100Zxxxxxx 資金約束：1234565000 xxxxxx國債投資額約束：121000 xx平均評級約束：12345612345623452xxxxxxxxxxxx平均到期年限約束：12345612345681046345xxxxxxxxxxxx第16頁/共107頁整理后得到線性規(guī)劃模型1234561234561212456123456max0.2560.380.1720.282

15、0.1260.1845000100023035200,1,2,6jZxxxxxxxxxxxxxxxxxxxxxxxxxxj1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第17頁/共107頁【例1-6】均衡配套生產(chǎn)問題。某產(chǎn)品由2件甲、3件乙零件組裝而成。兩種零件必須經(jīng)過設(shè)備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘。現(xiàn)有2臺設(shè)備A和3臺設(shè)備B，每天可供加工時間為8小時。為了保持兩種設(shè)備均衡負荷生產(chǎn)，要求一種設(shè)備每天的加工總時間不超過另一種設(shè)備總時間1小時。怎樣安排設(shè)備的加工時間使每天產(chǎn)品的

16、產(chǎn)量最大?！窘狻?設(shè)x1、x2為每天加工甲、乙兩種零件的件數(shù)，則產(chǎn)品的產(chǎn)量是)31,21min(21xxy 設(shè)備A、B每天加工工時的約束為60831096082452121xxxx要求一種設(shè)備每臺每天的加工時間不超過另一種設(shè)備1小時的約束為 60)109()452121xxxx（1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第18頁/共107頁目標函數(shù)線性化。產(chǎn)品的產(chǎn)量y等價于2131,21xyxy整理得到線性規(guī)劃模型 約束線性化。將絕對值約束寫成兩個不等式60)109()45(60)109()45(21212121xxxxxxxx1.1 線性規(guī)劃的數(shù)學(xué)模型 Ma

17、thematical Model of LP121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、第19頁/共107頁1.1.2 線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個約束，有n個決策變量xj, j=1,2,n，目標函數(shù)的變量系數(shù)用cj表示, cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成1 1221111221121 1222221 122max(min)(, )(, )(, )0,1,

18、2,nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xba xaxaxbxjn 或或或為了書寫方便，上式也可寫成： 1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第20頁/共107頁11max(min)(, )1,2,0,1,2,njjjnijjijjZc xa xbimxjn 或在實際中一般xj0,但有時xj0或xj無符號限制。1.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP第21頁/共107頁1.什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征3.線性規(guī)劃數(shù)學(xué)模型

19、的一般表達式。作業(yè)：教材習(xí)題 1.11.61.1 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP下一節(jié)：圖解法第22頁/共107頁1.2 圖解法 Graphical Method第23頁/共107頁圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非 負要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標函數(shù)圖形。先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目標函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應(yīng)的坐標就是最優(yōu)解。一般地

20、，將目標函數(shù)直線放在可行域中 求最大值時直線沿著矢量方向移動 求最小值時沿著矢量的反方向移動1.2 圖解法The Graphical Method第24頁/共107頁x1x2O1020304010203040(300,400)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=850040221xx305 . 121xx0, 0305 . 1402212121xxxxxx例1-712max300400Zxx1.2 圖解法The Graphical Method第25頁/共107頁246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)006346321212121xxxxxxxx、min Z

21、=x1+2x2例1-8(1,2)1.2 圖解法The Graphical Method第26頁/共107頁246x1x2246X（2）（3,1）X（1）（1,3）(5,5)006346321212121xxxxxxxx、min Z=5x1+5x2例1-9有無窮多個最優(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 Method第27頁/共107頁246x1x2246(1,2)006346321212121xxxxxxxx、無界解(無最優(yōu)解)max Z=x1+2

22、x2例1-101.2 圖解法The Graphical Method第28頁/共107頁x1x2O102030401020304050500,050305 .140221212121xxxxxxxx無可行解即無最優(yōu)解max Z=10 x1+4x2例1-111.2 圖解法The Graphical Method第29頁/共107頁由以上例題可知，線性規(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 Method第30頁/共107頁1.

23、通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點 (1)可行解區(qū)域要畫正確 (2)目標函數(shù)增加的方向不能畫錯 (3)目標函數(shù)的直線怎樣平行移動作業(yè)：教材習(xí)題 1.7 1.2 圖解法The Graphical Method下一節(jié)：線性規(guī)劃的標準型第31頁/共107頁1.3 線性規(guī)劃的標準型Standard form of LP第32頁/共107頁 在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。1.3 線性規(guī)劃的標準型Standard form of LP線性規(guī)劃問題的標準型為:1目標函數(shù)求最大值（或求最小值）2約束條件都為等式方程3變量xj非負4常數(shù)

24、bi非負第33頁/共107頁mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,02211222222111212111max(或min)Z=c1x1+c2x2+cnxn1.3 線性規(guī)劃的標準型Standard form of LP注：本教材默認目標函數(shù)是 max第34頁/共107頁njjjxcZ1maxminjxbxajnjijij, 2 , 1, 2 , 1, 010maxXbAXCXZ或?qū)懗上铝行问剑?或用矩陣形式1.3 線性規(guī)劃的標準型Standard form of LP第35頁/共107頁111211121222221212, ,

25、 , )nnnmmm nnmaaaxbaaaxbAXbCc ccaaaxb ； (通常X記為： 稱為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況mn，且r()m。TnxxxX),21（m ax0ZC XA XbX其中:1.3 線性規(guī)劃的標準型Standard form of LP第36頁/共107頁【例1-12】將下列線性規(guī)劃化為標準型 3213minxxxZ無符號要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx【解】（）因為x3無符號要求 ，即x3取正值也可取負值，標準型中要求變量非負，所以令 0,33333 xxxxx其

26、中1.3 線性規(guī)劃的標準型Standard form of LP第37頁/共107頁 (3)第二個約束條件是號，在號 左端減去剩余變量(Surplus variable)x5，x50。也稱松馳變量3213minxxxZ無符號要求、32132132132100)3(523)2(3) 1 (82xxxxxxxxxxxx1.3 線性規(guī)劃的標準型Standard form of LP(2) 第一個約束條件是號，在左端加入松馳變量 (slack variable) x4，x40,化為等式；(4)第三個約束條件是號且常數(shù)項為負數(shù)，因此在左邊加入松馳變量x6，x60，同時兩邊乘以1。 （5）目標函數(shù)是最小值

27、，為了化為求最大值，令Z=Z,得到max Z=Z，即當Z達到最小值時Z達到最大值，反之亦然。 第38頁/共107頁綜合起來得到下列標準型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 線性規(guī)劃的標準型Standard form of LP第39頁/共107頁 當某個變量xj0時,令x/j=xj 。 當某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束 974321xxx將其化為兩個不等式 974974321321xxxxxx再加入松馳變量化為等式。 1.3 線性規(guī)劃的標

28、準型Standard form of LP第40頁/共107頁【例1-13】將下例線性規(guī)劃化為標準型無約束、211212145|maxxxxxxxxZ【解】 此題關(guān)鍵是將目標函數(shù)中的絕對值去掉。令 0000000000002222222211111111xxxxxxxxxxxxxxxx，222222111111,|,|xxxxxxxxxxxx 則有1.3 線性規(guī)劃的標準型Standard form of LP第41頁/共107頁得到線性規(guī)劃的標準形式 112211223114112234max()()540Zxxxxxxxxxxxxxxxxxx 、 、 、 、 、1.3 線性規(guī)劃的標準型Sta

29、ndard form of LP對于axb(a、b均大于零)的有界變量化為標準形式有兩種方法。 一種方法是增加兩個約束xa及xb 另一種方法是令x=xa，則axb等價于0 xba，增加一個約束xba并且將原問題所有x用x= x+a替換。第42頁/共107頁1.如何化標準形式？ 可以對照四條標準逐一判斷！ 標準形式是人為定義的，目標函數(shù)可以是求最小值。2.用WinQSB軟件求解時，不必化成標準型。圖解法時不必化為標準型。3.單純形法求解時一定要化為標準型。作業(yè)：教材習(xí)題 1.81.3 線性規(guī)劃的標準型Standard form of LP下一節(jié)：基本概念第43頁/共107頁1.4 線性規(guī)劃的有關(guān)

30、概念Basic Concepts of LP第44頁/共107頁 設(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ī)劃的一個基（或基矩陣basis matrix ）。當m=n時，基矩陣唯一，當mn時，基矩陣就可能有多個，但數(shù)目不超過mnC第45頁/共107頁【例1-14】線性規(guī)劃 32124maxxxxZ5 , 1, 0226103553214321j

31、xxxxxxxxxj 求所有基矩陣。 【解】約束方程的系數(shù)矩陣為25矩陣 10261001115A,610151B,010152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出r(A)=2，2階子矩陣有C52=10個，其中第1列與第3列構(gòu)成的2階矩陣不是一個基，基矩陣只有9個，即1.4 基本概念Basic Concepts 第46頁/共107頁由線性代數(shù)知，基矩陣B必為非奇異矩陣并且|B|0。當矩陣B的行列式等式零即|B|=0時就不是基 當確定某一矩陣為基矩陣時，則基矩陣對應(yīng)的列向量稱為基向量(basis vector)，其余列向量稱為

32、非基向量 基向量對應(yīng)的變量稱為基變量(basis variable)，非基向量對應(yīng)的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對某一確定基而言的，不同的基對應(yīng)的基變量和非基變量也不同。010152B10261001115A1.4 基本概念Basic Concepts 第47頁/共107頁可行解(feasible solution) 滿足式（1.2）及（1.3）的解X=（x1,x2，xn)T 稱為可行解 ?；究尚薪?basis feasible solution) 若基本解是可行解則稱

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

34、8頁/共107頁顯然，只要基本解中的基變量的解滿足式（1.）的非負要求，那么這個基本解就是基本可行解。 在例1-13中，對來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=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 第49頁/共107頁由于 是基本解，從而它是基本可行解，在 中x

35、10i表1-6(a)XBx1x2x3x4bx3211040 x413/20130j30040000 (b)x3x2j (c)x1 x210 j 基變量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/2 11000-25-250將3/2化為11.5 單純形法 Simplex Method2015第62頁/共107頁最優(yōu)解X=(15，10，0，0)T，最優(yōu)值Z=8500X(1)=(0,0)x11.5 單純形法 Simplex Methodx1x2O102030401020304040221xx305 . 121xx0, 0305 . 14

36、02212121xxxxxx12max300400ZxxX(2)=(0,20)X(3)=(15,10)第63頁/共107頁單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形表（表1-6）。計算步驟：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零； 2.判斷： （a）若j（j，n）得到最解； （b）某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解(見例1-18)。 （c）若存在k0且aik (i=1,m)不全非正，則進行換基；1.5 單純形法 Simplex Method第64頁/共107頁min0,0,iiLikikikikbbaaM Ma

37、a當 時為任意大的正數(shù)第個比值最小 ，選最小比值對應(yīng)行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素； (c）求新的基可行解：用初等行變換方法將aLk 化為,k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。（b）選出基變量 ，求最小比值：1.5 單純形法 Simplex Method3.換基：（a）選進基變量設(shè)k=max j | j 0,xk為進基變量第65頁/共107頁【例1-16】 用單純形法求解3212maxxxxZ02053115232321321321xxxxxxxxx、【解】將數(shù)學(xué)模型化為標準形式：3212maxxxxZ5 ,

38、2 , 1, 0205311523253214321jxxxxxxxxxj不難看出x4、x5可作為初始基變量，單純法計算結(jié)果如表 1-7所示 。 1.5 單純形法 Simplex Method第66頁/共107頁Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表171/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/31.5 單純形法 Simplex

39、 Method第67頁/共107頁【例1-17】用單純形法求解 42122minxxxZ5 , 1, 0212665521421321jxxxxxxxxxxj【解】 這是一個極小化的線性規(guī)劃問題,可以將其化為極大化問題求解,也可以直接求解,這時判斷標準是：j0(j=1，n)時得到最優(yōu)解。容易觀察到,系數(shù)矩陣中有一個3階單位矩陣,x3、x4、x5為基變量。目標函數(shù)中含有基變量x4,由第二個約束得到x4=6+x1x2，并代入目標函數(shù)消去x4得12121222(6)6Zxxxxxx 1.5 單純形法 Simplex Method第68頁/共107頁XBx1x2x3x4x5bx3x4x51-16112

40、10001000156215621/2j1-1000 x2x4x51-241001-1-20100015111 j20100 表中j0,j=1,2,5所以最優(yōu)解為X=(0,5,0,1,11,)最優(yōu)值 Z=2x12x2x4=251=11極小值問題,注意判斷標準,選進基變量時,應(yīng)選j0, x2進基，而a120，a220且aik（i=1，2,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。1.5 單純形法 Simplex Method第75頁/共107頁在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變

41、量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?-20】用大M法解 下列線性規(guī)劃012210243423max321321321321321xxxxxxxxxxxxxxxZ、1. 大M 單純形法1.5.2大M和兩階段單純形法1.5 單純形法 Simplex Method第76頁/共107頁【解】首先將數(shù)學(xué)模型化為標準形式5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變

42、量x6、x7，目標函數(shù)中加入Mx6Mx7一項，得到人工變量單純形法數(shù)學(xué)模型用前面介紹的單純形法求解，見下表。 7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj1.5 單純形法 Simplex Method第77頁/共107頁Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/5100001

43、1/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3第78頁/共107頁（2）初始表中的檢驗數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達式代入目標涵數(shù)消去x6和x7，得到用非基變量表達的目標函數(shù)，其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算，如最優(yōu)解X（31/3，13，19/3，0，0)T；最優(yōu)值Z152/3注意：1.5 單純形法 Simplex Method11143( M,0, M)123( M) ( 4)0 1( M)232MBCC P (1) M是一個很大的抽象的數(shù)，不需

44、要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值第79頁/共107頁【例1-21】求解線性規(guī)劃 0,426385min21212121xxxxxxxxZ【解】加入松馳變量x3、x4化為標準型4 , 2 , 1, 0426385min42132121jxxxxxxxxxZj在第二個方程中加入人工變量x5，目標函數(shù)中加上M x5一項，得到 1.5 單純形法 Simplex Method第80頁/共107頁5 , 2 , 1, 0426385min5421321521jxxxxxxxxMxxxZj用單純形法計算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x531121

45、0010164j5M8+2M0M0 5Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM0 1.5 單純形法 Simplex Method第81頁/共107頁表中j0，j=1，2，5，從而得到最優(yōu)解X=（2，0，0，0，2）， Z=10+2M。但最優(yōu)解中含有人工變量x50說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。 兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始基本可行解。將問題分成兩個階段求解，第一階段的目標函數(shù)是miiRw1min約束條件是加入人工變量后的約束方程，當?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變

46、量時，得到原線性規(guī)劃的一個基本可行解，第二階段就以此為基礎(chǔ)對原目標函數(shù)求最優(yōu)解。當?shù)谝浑A段的最優(yōu)解w0時，說明還有不為零的人工變量是基變量，則原問題無可行解。1.5 單純形法 Simplex Method2. 兩階段單純形法第82頁/共107頁【例1-22】用兩階段單純形法求解例19的線性規(guī)劃?！窘狻繕藴市蜑? , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj在第一、三約束方程中加入人工變量x6、x7后，第一階段問題為7 , 2 , 1, 0122102434min732153216432176jxxxxxxxxxxxxxxxxw

47、j用單純形法求解，得到第一階段問題的計算表如下：1.5 單純形法 Simplex Method第83頁/共107頁Cj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000 100 x6x5x3632532001100010100 381j650100 000 x2x5x36/53/52/51000011/53/52/5010 3/531/511/5j00000 1.5 單純形法 Simplex Method第84頁/共107頁最優(yōu)解為 最優(yōu)值w=0。第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作

48、為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為)5310 ,511,53, 0(X123124145134max32613555333155522115550,1,2,5jZxxxxxxxxxxxxxj1.5 單純形法 Simplex Method第85頁/共107頁565352Cj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000 231x2x1x301010000111025/32/31331/319/3j000525/3 用單純形法計算得到下表最優(yōu)解X（31/3，13，19/3，0，0

49、)T；最優(yōu)值Z152/31.5 單純形法 Simplex Method第86頁/共107頁【例1-23】用兩階段法求解例1-21的線性規(guī)劃?！窘狻坷?-21的第一階段問題為5 , 2 , 1, 04263min54213215jxxxxxxxxxwj用單純形法計算如下表：1.5 單純形法 Simplex Method第87頁/共107頁Cj00001bCBXBx1x2x3x4x501x3x5311210010164j 12010 01x1x5101/37/31/31/3010122j 07/31/310 j0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標值w=20,x5仍在基變量

50、中,從而原問題無可行解。1.5 單純形法 Simplex Method第88頁/共107頁解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。 無界解的判斷: 某個k0且aik（i=1，2,m）則線性規(guī)劃具有無界解退化基本可行解的判斷:存在某個基變量為零的基本可行解。無可行解的判斷：(1)當用大M單純形法計算得到最優(yōu)解并且存在Ri0時，則表明原線性規(guī)劃無可行解。(2) 當?shù)谝浑A段的最優(yōu)值w0時，則原問題無可行解。1.5 單純形法 Simplex Method第89頁/共107頁設(shè)有

51、線性規(guī)劃0maxXbAXCXZ其中Amn且r(A)=m,),21ncccC（Tmbbbb),(21X0應(yīng)理解為X大于等于零向量，即xj0,j=1,2,n。TnxxxX),(211.5.3 計算公式1.5 單純形法 Simplex Method第90頁/共107頁不妨假設(shè)A（P1，P2，Pn）中前m個列向量構(gòu)成一個可行基，記為B=(P1，P2，Pm)。矩陣A中后nm列構(gòu)成的矩陣記為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），NBX

52、XXCB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn) 則AX=b可寫成bNXBXXXNBNBNB)( ，1.5 單純形法 Simplex Method第91頁/共107頁因為r（B）=m（或|B|0）所以B 1存在，因此可有 NnBNBNXBbBNXbBXNXbBX111)(令非基變量XN=0，XB=B1b，由 B是 可行基的假設(shè)，則得到基本可行解X=(B1b，0)T將目標函數(shù)寫成 NNBBNBNBXCXCXXCCZ),(1111()()BNNNBNBNCB bB NXC XC B bCC B N X1.5 單純形法 Simplex Method第92頁/共107頁NBNBXNB

53、CCbBCZ)(11得到下列五個計算公式：104.BZC B b13.NNBCC B NiijijjaccjijNBa)(1其中ABCCB111.BXB b12.NB N稱為單純形算子1. 5BCB(令XN=0) 1.5 單純形法 Simplex Method第93頁/共107頁上述公式可用下面較簡單的矩陣表格運算得到，設(shè)初始矩陣單純形表1-16 將B化為I（I為m階單位矩陣）,CB化為零,即求基本可行解和檢驗數(shù)。用B1左乘表中第二行,得到表1-17XBXNbXBB-1NB-1bCBCNXBXNbXBNbCBCN表116表1171.5 單純形法 Simplex Method第94頁/共107頁

54、再將第二行左乘CB后加到第三行,得到XBZ0XBXNbXBB- -1NB- -1 1b0CN- -CBB1NCBB1bN表1181.5 單純形法 Simplex Method第95頁/共107頁五個公式的應(yīng)用【例1-24】線性規(guī)劃3212maxxxxZ5 , 1, 0205311523253214321jxxxxxxxxxj已知可行基 131321B求(1)單純形乘子; (2)基可行解及目標值; (3)求3; (4)B1是否是最優(yōu)基,為什么;(5)當可行基為 時求1及3。 10312B1.5 單純形法 Simplex Method第96頁/共107頁【解】(1)因為B1由A中第一列、第二列組成,故x1、x2為基變量，x3、x4、x5為非基變量,有關(guān)矩陣為CB=