運籌學(xué)課件第一章線性規(guī)劃及單純形法

1、第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法1線性規(guī)劃介紹2線性規(guī)劃數(shù)學(xué)模型3線性規(guī)劃標(biāo)準(zhǔn)形式4線性規(guī)劃的圖解法5線性規(guī)劃基本概念6單純形法7應(yīng)用舉例第一章1線性規(guī)劃介紹線性規(guī)劃介紹歷史悠久，理論成熟，應(yīng)用廣泛運籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費用最小或獲得的收益最大。第一章線性規(guī)劃理論的發(fā)展線性規(guī)劃理論的發(fā)展：1939年前蘇聯(lián)康托洛維奇（年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ） 生產(chǎn)組織與計劃中的生產(chǎn)組織與計劃中的 數(shù)學(xué)方法數(shù)學(xué)方法提出提出 “解乘數(shù)法解乘數(shù)法”。1線性規(guī)劃介紹線性規(guī)劃介紹

2、列奧尼德列奧尼德康托羅維奇，前蘇聯(lián)人，由于在康托羅維奇，前蘇聯(lián)人，由于在1939年創(chuàng)立年創(chuàng)立了享譽全球的線形規(guī)劃要點，對資源最優(yōu)分配理論做了享譽全球的線形規(guī)劃要點，對資源最優(yōu)分配理論做出了貢獻，而獲得諾貝爾經(jīng)濟學(xué)獎。出了貢獻，而獲得諾貝爾經(jīng)濟學(xué)獎。第一章美國科學(xué)院院士美國科學(xué)院院士DANTZIG（丹齊克），（丹齊克），1948年在年在研究美國空軍資源的優(yōu)化配置時提出線性規(guī)劃及其通用研究美國空軍資源的優(yōu)化配置時提出線性規(guī)劃及其通用解法解法 “單純形法單純形法”。被稱為線性規(guī)劃之父。被稱為線性規(guī)劃之父。1線性規(guī)劃介紹線性規(guī)劃介紹 線性規(guī)劃之父的Dantzig (丹齊克)。據(jù)說，一次上課，Dantz

3、ig遲到 了，仰頭看去，黑板上留了幾個幾個題目，他就抄了一下，回家后埋頭苦做。幾個星期之后，疲憊的去找老師說，這件事情真的對不起，作業(yè)好像太難了，我所以現(xiàn)在才交，言下很是 慚愧。幾天之后，他的老師就把他召了過去，興奮的告訴他說他太興奮了。Dantzig很不解 , 后來才知道原來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解決的問題，他給出的那個解法也就是單純形法。這個方法是上個世紀(jì)前十位的算法。 第一章1線性規(guī)劃介紹線性規(guī)劃介紹 1960 1960年，年，“最佳資源利用的經(jīng)濟計算最佳資源利用的經(jīng)濟計算” ” 康托洛維奇康托洛維奇和庫伯曼斯和庫伯曼斯(Koopmans) (Koop

4、mans) 。兩人因?qū)Y源最優(yōu)分配理論的。兩人因?qū)Y源最優(yōu)分配理論的貢獻而獲貢獻而獲19751975年諾貝爾經(jīng)濟學(xué)獎年諾貝爾經(jīng)濟學(xué)獎 佳林佳林庫普曼斯，美國人，他將數(shù)理統(tǒng)計學(xué)成功運用庫普曼斯，美國人，他將數(shù)理統(tǒng)計學(xué)成功運用于經(jīng)濟計量學(xué)，對資源最優(yōu)分配理論做出了貢獻。于經(jīng)濟計量學(xué)，對資源最優(yōu)分配理論做出了貢獻。第一章1961年，查恩斯與庫伯提出了目標(biāo)規(guī)劃，艾吉利提出了用優(yōu)先因子來處理多目標(biāo)問題。20世紀(jì)70年代，斯姆李與杰斯開萊尼應(yīng)用計算機處理目標(biāo)規(guī)劃問題。計算機 50約束 100變量 30000約束 3000000變量1線性規(guī)劃介紹線性規(guī)劃介紹第一章從1964年諾貝爾獎設(shè)經(jīng)濟學(xué)獎后，到1992

5、年28年間的32名獲獎?wù)咧杏?3人(40%)從事過與線性規(guī)劃有關(guān)的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。1線性規(guī)劃介紹線性規(guī)劃介紹保羅-薩繆爾遜（PAUL A SAMUELSON ）, 他發(fā)展了數(shù)理和動態(tài)經(jīng)濟理論，將經(jīng)濟科學(xué)提高到新的水平。他的研究涉及經(jīng)濟學(xué)的全部領(lǐng)域。于1970年獲得諾貝爾經(jīng)濟學(xué)獎。華西里列昂惕夫（WASSILY LEONTIEF） ，美國人，他發(fā)展了投入產(chǎn)出方法，該方法在許多重要的經(jīng)濟問題中得到運用。曾獲1973年諾貝爾經(jīng)濟科學(xué)獎?？夏崴?J-阿羅（KENNETH J. ARROW）,美國人，因與約翰-希克斯（J

6、OHN R. HICKS）共同深入研究了經(jīng)濟均衡理論和福利理論獲得1972年諾貝爾經(jīng)濟學(xué)獎。牟頓-米勒（MERTON M. MILLER）,1923-2000, 美國人,由于他在金融經(jīng)濟學(xué)方面做出了開創(chuàng)性工作，于1990年獲得諾貝爾經(jīng)濟獎。第一章1線性規(guī)劃介紹線性規(guī)劃介紹線性規(guī)劃研究的主要問題：有一定的人力、財力、資源條件下，如何合理安排使用，效益最高? 某項任務(wù)確定后，如何安排人、財、物，使之最省?第一章 例例1 美佳公司計劃制造美佳公司計劃制造I，II兩種家電產(chǎn)品。已知各兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及的臺時、調(diào)試時間及A、B設(shè)備

7、和調(diào)試工序每天可用于這兩種家電的能力、各售出設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表一件時的獲利情況如表Il所示。問該公司應(yīng)制造所示。問該公司應(yīng)制造A、B兩兩種家電各多少件，使獲取的利潤為最大？種家電各多少件，使獲取的利潤為最大？項目項目I IIIII每天可用能力每天可用能力設(shè)備設(shè)備A A（h h）設(shè)備設(shè)備B B（h h）調(diào)試工序（調(diào)試工序（h h）0 06 61 15 52 21 1151524245 5利潤（元）利潤（元）2 21 12線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件解：用變量解：用變量x x1 1和和x x2 2分別表示美

8、佳公司制造家電分別表示美佳公司制造家電I I和和IIII的數(shù)量。的數(shù)量。項目項目I IIIII每天可用能力每天可用能力設(shè)備設(shè)備A A（h h）設(shè)備設(shè)備B B（h h）調(diào)試工序（調(diào)試工序（h h）0 06 61 15 52 21 1151524245 5利潤（元）利潤（元）2 21 1例例1 1212maxxxz0,52426155.2121212xxxxxxxts用數(shù)學(xué)語言描述用數(shù)學(xué)語言描述2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章解：(1)、確定可行域 x1 0 x1 =0 (縱) x2 0 x2=0 (橫) x1+2x2 30 x1+2x2 =30 (0,15) (30,0)x2010203

9、0DABC3x1+2x2 =60(0,30) (20,0) 2x2 =24203010 x1線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章例例2 捷運公司擬在下一年度的捷運公司擬在下一年度的1-4月的月的4個月內(nèi)需租用倉庫堆個月內(nèi)需租用倉庫堆放物資。已知各月份所需倉庫面積數(shù)列見下表。倉庫租借費用隨放物資。已知各月份所需倉庫面積數(shù)列見下表。倉庫租借費用隨合同期定，期限越長折扣越大，具體數(shù)字見下表。租借倉庫的合合同期定，期限越長折扣越大，具體數(shù)字見下表。租借倉庫的合同每月初都可辦理，每份臺同具體現(xiàn)定租用面積數(shù)和期限。因此同每月初都可辦理，每份臺同具體現(xiàn)定租用面積數(shù)和期限。因此該廠可根據(jù)需要，在任何一個月初

10、辦理租借臺同。每次辦理時可該廠可根據(jù)需要，在任何一個月初辦理租借臺同。每次辦理時可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費用最小。該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費用最小。月份月份1 12 23 34 4所需所需倉庫面積倉庫面積1515101020201212合同租借期限合同租借期限1 1個月個月2 2個月個月3 3個月個月4 4個月個月合同期內(nèi)的租費合同期內(nèi)的租費280028004500450060006000730073002線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型

11、第一章解：設(shè)變量xij表示捷運公司在第i(i1，4)個月初簽訂的租借期為jj1，4)個月的倉庫面積的合同(單位為100m2)。約束條件目標(biāo)函數(shù)例例2 2月份月份1 12 23 34 4所需所需倉庫面積倉庫面積1515101020201212合同租借期限合同租借期限1 1個月個月2 2個月個月3 3個月個月4 4個月個月合同期內(nèi)的租費合同期內(nèi)的租費28002800450045006000600073007300142313322212413121117300)(6000)(4500)(2800minxxxxxxxxxxz)4.1;4.1(012201015.4132231432312322141

12、323222114131214131211jixxxxxxxxxxxxxxxxxxxxxtsij2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章14max(min)Z=c1x1+ c2x2+cnxnn個變量個變量價值系價值系數(shù)數(shù)第第i 種資種資源的擁有源的擁有量量技術(shù)系數(shù)或技術(shù)系數(shù)或工藝系數(shù)工藝系數(shù)a11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n)s.t.線性規(guī)劃的一般式線性規(guī)劃的一般式2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章njjjxcz1max(min), 2 ,

13、 1(0), 2 , 1(.1njxmibxastjinjjij線性規(guī)劃的簡寫式線性規(guī)劃的簡寫式2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章CXz max(min)0),(.1Xbxpstnjjj),.,(21ncccC nxxxX21mjjjjaaaP21mbbbb21線性規(guī)劃的向量表示式線性規(guī)劃的向量表示式2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章CXz max(min)0),(.XbAXstmnmmnnaaaaaaaaaA.212222111211線性規(guī)劃的矩陣表示式線性規(guī)劃的矩陣表示式2線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型第一章線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù) ：max，min約束條件：,=,變量符號

14、：0, 00)(),(. .max(min)XbAXt sXCzT0. .maxXbAXtsXCzT線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：max約束條件：=變量符號：03線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章標(biāo)準(zhǔn)型的一般型標(biāo)準(zhǔn)型的一般型maxZ=c1x1+ c2x2+cnxn其中 bi 0 (i=1,2,m)a11x1+ a12x2+ a1nxn =b1a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ amnxn =bmxj 0(j=1,2,n)s.t.3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章 P1 P2 Pn a11 a12 a1n其中 A= a21 a22 a2n am1

15、am2 amn x1 x= x2 xn b1 b= b2 bmC=(C1 C2 Cn )標(biāo)準(zhǔn)型的矩陣型標(biāo)準(zhǔn)型的矩陣型maxZ=Cx Ax=b x 0 b0 b 0 0 3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章 x1Ax=(P1 P2 Pn ) x2 = b xn CXZ max01XbxpnjjjP1 x1+ P2 x2 + +Pn xn=b標(biāo)準(zhǔn)型的向量型標(biāo)準(zhǔn)型的向量型3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章線性規(guī)劃問題化標(biāo)準(zhǔn)型：線性規(guī)劃問題化標(biāo)準(zhǔn)型：(1)、約束條件(2)、變量(3)、目標(biāo)函數(shù)(4)、右端常數(shù)3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章第一章(1)、約束條件、約束條件x3為松弛變

16、量x4為剩余變量 松弛變量或剩余變量在實際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。242621xx：如2426321xxx18121021xx：如181210421xxx當(dāng)約束條件為“ ”時：當(dāng)約束條件為“ ”時：3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章(2)、變量、變量3 x1 -3 x1 +2x2 8 x1 - x1 - 4x2 14x1 , x1 ,x2 01、x 0的情況，3x1+2x2 8 x1 -4x2 14 x20令x1= x1- x1 2、x取值無約束的情況。令x- x。令x= x- x3 x1 -3 x

17、1 +2x2 +x3 = 8 x1 - x1 - 4x2 +x 4= 14x1 , x1 ,x2 ,x3 ,x4 03線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章x1 +x2 11x1 16x1 , x2 0（3 3）、）、x兩邊有約束的情況。兩邊有約束的情況。x1+x2 5-6 x1 10 x20-6+6 x1+6 10+6 令x1 = x1 +6 0 x1 163線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章(3)、目標(biāo)函數(shù)、目標(biāo)函數(shù)xoZ-Z令Z = - Z njjjxcZ1minnjjjxcZ1min3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章(4)、右端常數(shù)、右端常數(shù)右端項b0時，只需將等式或不等式兩

18、端同乘(一1)，則等式右端項必大于零。3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式 X1 +2X2 +X3 =30 s.t. 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 , , X5 0 0 轉(zhuǎn)化為：轉(zhuǎn)化為：maxZ=40X1+ 50X2+0X3 +0X4+0X5 x1 + 2x2 30 3x1 + 2x2 60s.t. 2x2 24 x1，x2 0 例：例：max Z= 40 x1 +50 x2松弛變量松弛變量第一章3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式例：例： 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14

19、2x2 + x3+3x4 8 xi 0 (i =1,4)4X1+6X2+ X3 +2X4 - X5 =12 X1+ X2+7X3+5X4 - X6 =14 2X2+ X3+3X4 - X7=8 X1 , , X7 0 0 剩余變量剩余變量第一章例3：將 min Z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，x3無限制化為標(biāo)準(zhǔn)型3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章解： 令x3 =x4 - x5 加松弛變量x6加剩余變量x7 令Z= -ZmaxZ= x1 -2x2 +3x4 -3x5 x1 +x2 +x4 -x5 +x6=7x1 -x2 +x4 -

20、x5 -x7 =2x1 , x2 , x4 , , x7 0min Z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，x3無限制3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章(1) min Z= 2x1 -x2+2x3練習(xí)練習(xí)5 將下列線性規(guī)劃問題化成標(biāo)準(zhǔn)型：將下列線性規(guī)劃問題化成標(biāo)準(zhǔn)型：- x1 +x2 +x3 = 4 - x1 +x2 - x3 6x1 0 ，x2 0, x3 無約束 s.t.(2) max Z= 2x1 +x2+3x3 +x4x1 +x2 +x3 +x3 7 2x1 - 3x2 + x3 = - 8x1 - 2x3 + 2x4 1x1

21、, x3 0, x2 0 ， x4 無約束 s.t.3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章(3) min Z= 2x1 +3x2+5x3x1 +x2 -x3 - 5 - 6x1 + 7x2 -9 x3 = 15|19x1 - 7x2+ 5x3| 13x1 , x2 0, x3 無約束 s.t.(4) max Z= x1 -3x2- x1 +2x2 - 5 x1 + 3x2 = 10 x1 , x2 無約束 s.t.3線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃標(biāo)準(zhǔn)形式第一章Ax=b (1)x 0 (2)maxZ=Cx (3)定義1：滿足約束(1)、(2)的x=(x1 xn)T稱為LP問題的可行解，全部可行解的集

22、合稱為可行域。定義2：滿足(3)的可行解稱為LP問題的最優(yōu)解線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章圖解法求解的目的：一是判別線性規(guī)劃問題的求解結(jié)局；二是在存在最優(yōu)解的條件下，把問題的最優(yōu)解找出來。 4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章圖解法的步驟：1、在平面上建立直角坐標(biāo)系；2、圖示約束條件，找出可行域；3、圖示目標(biāo)函數(shù)和尋找最優(yōu)解。4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章例1 maxZ=40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 04線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章解：(1)、確定可行域 x1 0

23、 x1 =0 (縱) x2 0 x2=0 (橫) x1+2x2 30 x1+2x2 =30 (0,15) (30,0)x20102030DABC3x1+2x2 =60(0,30) (20,0) 2x2 =24203010 x14線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章(2)、求最優(yōu)解最優(yōu)解：x* = (15,7.5) Zmax =975Z=40 x1+50 x20=40 x1+50 x2 (0,0)， (10,-8)x20102030203010 x1DABCC點： x1+2x2 =30 3x1+2x2 =604線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章Z= 40 x1 + 80 x2 =0 x1

24、+ 2x2 =30DABCx20 x1解: 最優(yōu)解：最優(yōu)解：BC線段線段B點 C點x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1-) x(2) (0 1)例2 maxZ=40 x1+ 80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 04線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章4線性規(guī)劃的圖解法線性規(guī)劃的圖解法X1 =6 + (1- )15X2=12 + (1- )7.5X1 =15-9 X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15 X2 12 7.5第一章無界解無有限最優(yōu)解例3 maxZ=2x

25、1+ 4x2 2x1+x2 8-2x1+x2 2x1 , x2 0Z=02x1+ x2=8-2x1+ x2=28246x240 x14線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章例4、 maxZ=3x1+2x2 -x1 -x2 1x1 , x2 0無解無可行解-1x1-1x204線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章唯一解無窮多解 無有限最優(yōu)解 無可行解有解無解當(dāng)目標(biāo)函數(shù)的直線族與某約束條件平行，且該問題有解時。約束條件無公共區(qū)域。有解但可行域可伸展到無窮時總總 結(jié)結(jié)4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章由圖解法得到的啟示由圖解法得到的啟示(1)、線性規(guī)劃問題的解的情況有四種：唯一最優(yōu)解；無窮多最

26、優(yōu)解；無界解；無可行解。(2)、若線性規(guī)劃可行域存在，則可行域是一個凸集。(3)、若有最優(yōu)解，定可在可行域的頂點得到。(4)、解題思路是找出凸集的各頂點的最大目標(biāo)函數(shù)值。4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章練習(xí)：練習(xí)：用圖解法解以下問題： max Z= 5x1 +6x2x1 - 2x2 2 -2x1 + 3x2 2x1 , x2 無約束 s.t.4線性規(guī)劃的圖解法線性規(guī)劃的圖解法第一章Ax=b (1)x 0 (2)maxZ=Cx (3)1、可行解：滿足約束(1)、(2)的x=(x1 xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。2、最優(yōu)解：滿足(3)的可行解稱為LP問題的最優(yōu)解

27、線性規(guī)劃的標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)型一、線性規(guī)劃問題的解的概念一、線性規(guī)劃問題的解的概念5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章3、基、基(基陣基陣) 設(shè)A為約束方程組的mn階系數(shù)矩陣設(shè)(nm)，其秩為m，B是矩陣A中的一個mm階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個基。 P1 P2 Pm Pn a11 a12 a1m a1n A= a21 a22 a2m a2n am1 am2 amm amnB5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章A= (P1 Pm Pm+1 Pn )=(BN) 基向量 非基向量x= (x1 xm xm+1 xn )T=(xB xN)T 基變量 非基變量 xB xNB中的每一

28、個列向量Pj稱為基向量，與基向量對應(yīng)的變量稱為基變量，其他變量稱為非基變量。5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章4、基解在約束方程組中，令所有非基變量等于零，又因為矩陣B不等于0，根據(jù)克萊姆法則，由m個約束方程可以解出m個集變量的唯一解，將這個解加上非基變量取0的值，稱為線性規(guī)劃問題的基解。5、基本可行解基B，基本解x=若B-1 b0，稱基解為基本可行解，也稱基可行解。 基本解中最多有m個非零分量。 基本解的數(shù)目不超過Cnm = 個。n!m!(n-m)!6、可行基對應(yīng)于基可行解的基稱為可行基。5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章例8 x1+2x2 +x3 =30 3x1+2x2 +x4

29、 =60 2x2 +x5=24 x1 x5 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=5線性規(guī)劃基本概念線性規(guī)劃基本概念B=(P3 P4 P5)=I 是滿秩子矩陣 非基 N=(P1 P2)x1x2x3x4x5x= 00306024令x1 = x2 =0, x3=30, x4=60, x5=24第一章例9：給定約束條件 -x3+x4 =0 x2 +x3 +x4 =3 -x1 +x2 +x3+x4 =2 xj 0 ( j=1,2,3,4 )求出基變量是x1 , x3 , x4的基本解，是不是可行解？5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章 0 -1 1

30、解：B=(P1 P3 P4)= 0 1 1 -1 1 1 0 1 -1 0B-1= -1/2 1/2 0 3 1/2 1/2 0 2b=5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章 x1 x3 = B-1 b x4 xB = 0 1 -1 0 1 = -1/2 1/2 0 3 = 3/2 1/2 1/2 0 2 3/2x=(1, 0, 3/2, 3/2)T 是 5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章凸集D是n維空間的一個集合，x(1), x(2)D,若對任何x(1), x(2)，有x= x(1)+(1-) x(2) D(0 1)，則D為凸集。定義定義1： 凸集如果集合D中任意兩個點，其連線上的所

31、有點也都是集合D中的點，則稱D為凸集。二、凸集及其頂點二、凸集及其頂點5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章x(1)x(2)凸多邊形凸多邊形凹多邊形凹多邊形x(1)x(2)5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章第一章 x(1) , x(2) , ,x(k) 是n維歐氏空間中的k個點，若有一組數(shù) 1 , 2 , , k 滿足 0 i 1 (i=1, ,k)定義定義2 i =1ki=1有點 x= 1 x(1) + + k x(k)則稱點x為 x(1) , x(2) , ,x(k) 的凸組合。凸組合5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章 凸集D, 點 xD，若找不到兩個不同的點x(1) , x

32、(2) D 使得 x= x(1) +(1- ) x(2) (0 1) 則稱x為 D的頂點。定義定義3頂點頂點5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章證明：設(shè)LP問題的可行解域為集合CC= x| Ax=b x 0 任取x(1) , x(2) C, 則 x= x(1) +(1- ) x(2) 0 (0 1)又因為 A x(1) =b， A x(2) =b所以 Ax=A x(1) +(1- ) x(2) = b +(1- ) b=b 則 xC，C為凸集定理定理1：LP問題的可行解域一定是凸集。問題的可行解域一定是凸集。三、幾個基本定理的證明三、幾個基本定理的證明5線性規(guī)劃基本概念線性規(guī)劃基本概念第一

33、章只須證明： D的k個頂點x(1) , ,x(k) ，有 預(yù)理預(yù)理1 D為有界凸多面集，為有界凸多面集， x D，x必可表必可表 為為D的頂?shù)捻旤c的凸組合點的凸組合 。0 i 1，使 x= 1 x(1) + + k x(k) i =1ki=15線性規(guī)劃基本概念線性規(guī)劃基本概念第一章證明可用歸納法（略）x(1)x(2)x(3)x xx在邊界上x在內(nèi)部 x(1) (1- ) x(2) (1- )x(3) x=+x x +(1- ) x(2) (0 1)x x(1) +(1- ) x(3) (0 1)5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章證明：設(shè)x(1) , ,x(k) 為可行域頂點，若x*不是頂

34、點，但 maxZ=C x* 定理定理2：可行域有界，最優(yōu)值必可在頂點得到：可行域有界，最優(yōu)值必可在頂點得到Cx*= iC x(i)ki=1 i Cx(m) ki=1= Cx(m) 設(shè) Cx(m) Max (C x(i) 1 i k i x(i)ki=1 i =1ki=10 i 1x*=5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章引理引理2：LP問題的可行解x是基本可行解x的非0分量對應(yīng)的系數(shù)列向量線性無關(guān)證明 ：（1）必要性。由基可行解的定義顯然。（2）充分性。若向量P1，P2, Pk線性獨立，則必有k m。 當(dāng)k=m時，它們恰好構(gòu)成一個基，從而x=(x1,x2,xm,0, ,0)為相應(yīng)的基可行解

35、。 當(dāng)k0 j =1, ,kxj =0 j =k+1, ,n由引理2知，p1 , , pk 線性相關(guān)必有不全為0的1 , , k使 1 p1 + k pk = 0做 (1 , , k ,0 ,0 )T則有 A 1 p1 + k pk = 0可行域C中點x是頂點x是基本可行解定理3：5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章選任一不為零的數(shù)令 x(1) =x+ 0 x(2) =x 0又Ax(1) =Ax+ A b Ax(2) =Ax A =b 所以x(1) Cx(2) C因為 x1/2 x(1) + 1/2 x(2)所以 x不是可行域的頂點5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章67證明：( )

36、不是頂點，不是基可行解設(shè)x為可行解xj 0 j =1, ,kxj =0 j =k+1, ,n若x不是頂點，則有x(1) x(2) C，使得： x = x(1) +(1- ) x(2) (0 0，1- 0， xj (1) 0 ， xj (2) 0 所以 xj (1) xj (2) 0 (j =k+1, ,n)因為 Ax(1) =b Ax(2) =b p j xj(1) =bnj=1 p j xj(2) =bnj=1即 p1 x1(1) + + pk xk(1) = b (a) p1 x1(2) + + pk xk(2) = b (b)5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章由(a) (b) 得(

37、x1(1)x1(2) )p1 + + (xk(1)xk(2) )pk = 0即x不是基可行解所以 p1 , , pk 線性相關(guān)定理定理4 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。可行解是最優(yōu)解。5線性規(guī)劃基本概念線性規(guī)劃基本概念第一章 (LP)問題的基本可行解 可行域的頂點。 若(LP)問題有最優(yōu)解，必可以在基本可行解(頂點)達到。 若(LP)問題有可行解，則可行解集(可行域)是凸集(可能有界，也可能無界)，有有限個頂點。5線性規(guī)劃基本概念線性規(guī)劃基本概念LP問題解的性質(zhì)問題解的性質(zhì)第一章6單純形法單純形法 6.1、單純形法迭代原理 6.2、

38、單純形法計算步驟 6.3、人工變量法 6.4、兩階段法 6.5、計算中的幾個問題第一章6.1 單純形法迭代原理單純形法迭代原理一、確定初始基可行解二、從一個基可行解轉(zhuǎn)換為相鄰基可行解三、最優(yōu)性檢驗和解的判別第一章A中總存在一個單位矩陣（P1,P2,Pm)。一、確定初始基可行解一、確定初始基可行解當(dāng)約束條件為時，加上松馳變量的系數(shù)矩陣即為單位矩陣。當(dāng)約束條件為或時，可以構(gòu)造人工基，人為產(chǎn)生一個單位矩陣。基向量、基變量、非基向量、非基變量可得初始基可行解: x=(x1,xm,xm+1,xn)T=(b1,bm,0,0)T6.1 單純形法迭代原理單純形法迭代原理第一章兩個基可行解相鄰指的是它們之間變換

39、且僅變換一個基變量。設(shè)x(0)=(x10,x20,xm0,0,0)T，有Pi xi0 =bmi=1系數(shù)矩陣的增廣矩陣系數(shù)矩陣的增廣矩陣mnmjmmmnjmnjmnjmmbaaabaaabaaabPPPPPP,1,2,2,21,21, 1, 11, 1121.1.00.0.10.0.01.二、基可行解的轉(zhuǎn)換二、基可行解的轉(zhuǎn)換6.1 單純形法迭代原理單純形法迭代原理第一章Pj= aij Pimi=1Pj aij Pi0 m i=1兩邊乘上一個正數(shù)0，得 (Pj aij Pi）=0 m i=1同 相加整理得： Pixi0 =bmi=1所以得到另一個點x(1) ,使bPPaxjmiiiji10)(Tm

40、jmjaxaxX)0,.,.,0 ,.,(0101)1( Pi xi(1) =bni=1可行解?基解?6.1 單純形法迭代原理單純形法迭代原理bPPPPPPaxPaxPaxnjjmmmmjmjj0.0.00)(.)()(121022021101第一章所以x(1)是可行解令ljlijijiaxaax000minTmjmjaxaxX)0,.,.,0 ,.,(0101)1(存在：00ijiax)(0)(00liliaxiji6.1 單純形法迭代原理單純形法迭代原理第一章mjmljlljlljljjmljlbababababababPPPPPP1.00.00.0.10.000.00.000.01.00

41、.0.00.100.00.01.,1, 1,1, 12,21, 11121重新排列后不含非基向量的增廣矩陣：因alj0，故上述矩陣元素組成的行列式不為零，P1,P2,Pl-1,Pj,Pl+1,Pm 是一個基。所以， x(1) ，是基可行解。lja/ja10 0 0 1 0 0 6.1 單純形法迭代原理單純形法迭代原理進行初等變換：b=(b1- a1j,bl-1- al-1,j,bl+1- al+1,j,bm-amj)T由此x(1)是x(0)相鄰的基可行解，且由基向量組成的矩陣仍為單位矩陣。第一章將基本可行解x（0）和x（1）分別代入目標(biāo)函數(shù)得：miiixcz10)0(jijmiiicaxcz1

42、0)1(110miijijmiiiaccxc1)0(miijijaccz三、最優(yōu)性檢驗和解的判別三、最優(yōu)性檢驗和解的判別6.1 單純形法迭代原理單純形法迭代原理jjmiijijjzcacc1)0()1(0, 0ZZj第一章是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標(biāo)志。 當(dāng)所有的i=0時，現(xiàn)有頂點為最優(yōu)解。 當(dāng)所有的i0，又Pj0, 則判定原問題無可行解。第第2 2階段階段：去除人工變量，求解原問題。第一階段的最優(yōu)解為原問題的初始基可行解。6.4 兩階段法兩階段法第一章例2：maxZ= -x1 +2x2 x1 +x2 2-x1 +x2 1 x2 3x1 x2 0解：第(1)階段：minW=x6 +x

43、7 x1 +x2 -x3 +x6 =2-x1 +x2 -x4 +x7 =1 x2 +x5 =3x1 x7 06.4 兩階段法兩階段法第一章列初始單純形表Cj00000-1-1CBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010 x530100100j=cj-zj02-1-1000第二階段：去除人工變量，列新單純形表求解。6.4 兩階段法兩階段法第一章Cj00000-1-1CBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010 x530100100j=cj-zj02-1-10006.4 兩階段法兩階段法-1x612

44、0-1101-10 x71-110-10010 x52100110-1j=cj-zj20-1100-2第一章Cj00000-1-1CBxBbx1x2x3x4x5x6x70 x11/210-1/21/201/2-1/20 x23/201-1/2-1/201/21/20 x53/2001/21/21-1/2-1/2j=cj-zj00000-1-16.4 兩階段法兩階段法-1x6120-1101-11/20 x21-110-10010 x52100110-12/1j=cj-zj20-1100-2第一章Cj-12000-1-1CBxBbx1x2x3x4x5x6x7-1x11/210-1/21/201/

45、2-1/212x23/201-1/2-1/201/21/20 x53/2001/21/21-1/2-1/23j=cj-zj001/23/20-1-16.4 兩階段法兩階段法0 x4120-1101-12x2211-100010 x51-101010-11j=cj-zj-302000-2第一章Cj-12000-1-1CBxBbx1x2x3x4x5x6x70 x42100111/2-1/22x23010011/21/20 x31-10101-1/2-1/2j=cj-zj-6-1000-2-1-16.4 兩階段法兩階段法0 x4120-1101-12x2211-100010 x51-101010-1

46、1j=cj-zj-302000-2第一章6.5 計算中的幾個問題計算中的幾個問題2 2、退化、退化 ： （非退化 值唯一 ）kllkllkllkikiittabababaab,1,.)0min(221 在下一次迭代中有一個或幾個基變量為0，從而出現(xiàn)退化解?？赡芸赡軙?dǎo)致循環(huán)，永遠達不到最優(yōu)解。1 1、目標(biāo)函數(shù)極小化時解的最優(yōu)性判別、目標(biāo)函數(shù)極小化時解的最優(yōu)性判別 以i 0作為判別表中解是否最優(yōu)的標(biāo)志第一章tkllkllkllkikiilllabababaabtt.)0min()221,1,221且若離基。為主元素。則11,lklxa 則xk進基kjj )0(max0j1）若有兩個以上檢驗數(shù)如何

47、解決退化問題？ Dantzig 規(guī)則：6.5 計算中的幾個問題計算中的幾個問題第一章6.5 計算中的幾個問題計算中的幾個問題 1951 年 Hoffman 給出反例。 （ 3個方程，11個變量 ）1955 年 E.M.L.Beale 3 個方程，7個變量 。6次迭代后，出現(xiàn)循環(huán)。7,.,2 , 101035019021092516041650115043min7364321543214321ixxxxxxxxxxxxxxxxxzi 按照 Dantzig規(guī)則 ： （5，6，7） （1，6，7） （1，2，7） （3，2，7） （3，4，7） （5，4，7） （5，6，7）第一章進基則若kixki

48、 0min.1離基。中下標(biāo)最小者的基變量選)0min(. 2,kikiiaabBland 原則 （1976 年 第9屆國際數(shù)學(xué)規(guī)劃大會）6.5 計算中的幾個問題計算中的幾個問題第一章3 3、無可行解的判別、無可行解的判別 當(dāng)線性規(guī)劃問題中添加人工變量后，無論用人工變量法或兩階段法，初始單純形表中的解因含非零人工變量，故實質(zhì)上是非可行解。當(dāng)求解結(jié)果出現(xiàn)所有i 0 0時， 如基變量中仍含有非零的人工變量(兩階段法求解時第一階段目標(biāo)函數(shù)值不等于零)，表明問題無可行解。6.5 計算中的幾個問題計算中的幾個問題第一章6.5 計算中的幾個問題計算中的幾個問題例7 用單純形法求解線性規(guī)劃問題 maxZ= 2

49、x1 +x2 x1 +x2 22x1 +2x2 6 x1 x2 0第一章6.5 計算中的幾個問題計算中的幾個問題解：添加松弛變量和人工變量，原模型化為標(biāo)準(zhǔn)型。maxZ= 2x1 +x2 -M x5 x1 +x2 +x3 = 22x1 +2x2 x4 +x5 = 6 x1-5 0以X3，X5為基變量列初始單純形表，進行計算。第一章6.5 計算中的幾個問題計算中的幾個問題Cj2100-MCBxBbx1x2x3x4x50 x3211100-Mx56220-11 j=cj-zj2+2M1+2M0-M02x1211100-Mx5200-2-11 j=cj-zj0-1-2-2M-M0第一章6.6單純形法小

50、結(jié)單純形法小結(jié)第一章6.6單純形法小結(jié)單純形法小結(jié)第一章7 應(yīng)用舉例應(yīng)用舉例例1：用長7.4m的鋼材做100套鋼架，每套鋼架需長2.9m , 2.1m , 1.5m 的料各一根。 問如何下料，使用的原料最??？ 分析：可行的下料方案有：2.9000011122.1012301201.543203101合計66.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1第一章 解：設(shè)第i種方案用xi根原料。Zxxxxxxxxxxxxxxxxxxxxzii01003231002210021 . 03 . 09 . 02 . 08 . 0min643215421654365

51、421 解之得 x3 = 30 x5 = 50 x6 =10思考 ：1）目標(biāo)函數(shù)可否改為 z = x1+x2+x3+x4+x5+x6 2）若每套鋼架需長2.9m一根，2.1m二根，1.5m五根。問如何求解。7 應(yīng)用舉例應(yīng)用舉例第一章例 2 連續(xù)投資問題李勇擬定在三年后購買一套房子，準(zhǔn)備在今后的三年中作一些投資，現(xiàn)有下面四個 投資機會： 1：在三年內(nèi)，投資人在每年年初投資，每年有20%的收益。 2：在三年內(nèi)，投資人在第一年年初投資，兩年后有50%的收益。這種投資最多不得超過40000元。3：在三年內(nèi)，投資人在第二年年初投資，兩年后有60%的收益。這種投資最多不得 超過30000元。4：在三年內(nèi)，投資人在第三年年初投資，一年內(nèi)有40%的收益。這種投資最多不得超過10000元。現(xiàn)有資金100000元，且每年年末有20000元的固定收入。問李勇應(yīng)怎樣決定投資計劃，才能在第三年末獲得最高收益？7 應(yīng)用舉例應(yīng)用舉例第一章解：解：設(shè)xij為第i年把資金作第j項投資的資金額。據(jù)題意可得：3431232112114 . 02 . 06 . 02 . 05 . 02 . 0maxxxxxxxz目