機(jī)械優(yōu)化設(shè)計(jì)6線性規(guī)劃

1、2022-6-171第六章第六章 線性規(guī)劃線性規(guī)劃一一. .線性規(guī)劃的基本概念線性規(guī)劃的基本概念二二. .求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法三三. .初始基本可行解初始基本可行解2022-6-172 某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)品分別由兩條生產(chǎn)線生產(chǎn)。第一條生產(chǎn)甲，每天品分別由兩條生產(chǎn)線生產(chǎn)。第一條生產(chǎn)甲，每天最多生產(chǎn)最多生產(chǎn)9 9件，第二條生產(chǎn)乙，每天最多生產(chǎn)件，第二條生產(chǎn)乙，每天最多生產(chǎn)7 7件；件；該廠僅有工人該廠僅有工人2424名，生產(chǎn)甲每件用名，生產(chǎn)甲每件用2 2工日，生工日，生產(chǎn)乙每件用產(chǎn)乙每件用3 3工日；產(chǎn)品甲、乙的單件利潤(rùn)

2、分工日；產(chǎn)品甲、乙的單件利潤(rùn)分別為別為4040元和元和8080元。問(wèn)工廠如何組織生產(chǎn)才能獲得元。問(wèn)工廠如何組織生產(chǎn)才能獲得最大利潤(rùn)？最大利潤(rùn)？一）應(yīng)用實(shí)例一）應(yīng)用實(shí)例6-1 6-1 線性規(guī)劃的基本概念線性規(guī)劃的基本概念2022-6-173日利潤(rùn)最大日利潤(rùn)最大生產(chǎn)能力限制生產(chǎn)能力限制勞動(dòng)力限制勞動(dòng)力限制變量非負(fù)變量非負(fù).,21xx解解: 設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為0,2432798040)(max212121221xxxxxxRDXxxXFs.t.2022-6-174二二) )線性規(guī)劃的一般形式線性規(guī)劃的一般形式0,.,.)(min2122112222212

3、1112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcXFs.t.s.t.特點(diǎn)特點(diǎn): : 1) 1)為極小化問(wèn)題為極小化問(wèn)題; 2); 2)約束取等號(hào)約束取等號(hào); ; 3) 3)限定系數(shù)非負(fù)限定系數(shù)非負(fù); 4); 4)變量非負(fù)變量非負(fù). .式中，式中， 價(jià)值系數(shù)；價(jià)值系數(shù)； 結(jié)構(gòu)系數(shù)結(jié)構(gòu)系數(shù) 限定系數(shù)限定系數(shù)jcijaib2022-6-175 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型的方法將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型的方法1 1）將極大化問(wèn)題化為極小化問(wèn)題）將極大化問(wèn)題化為極小化問(wèn)題iibXg)() 1 ( 若iibXg)()2(若kx 松弛變量松弛變量/jjjx

4、xx（開(kāi)關(guān)變量）（開(kāi)關(guān)變量）（兩邊乘（兩邊乘-1-1）4 4）將負(fù)的限定系數(shù)化為正值）將負(fù)的限定系數(shù)化為正值3 3）將任意變量化為非負(fù)變量）將任意變量化為非負(fù)變量2 2）將不等式約束變?yōu)榈仁郊s束：）將不等式約束變?yōu)榈仁郊s束：目標(biāo)函數(shù)變號(hào)；目標(biāo)函數(shù)變號(hào)；ikibxXg)(ikibxXg)(2022-6-1760,.,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型:2022-6-177三）線性規(guī)劃的基本概念三）線性規(guī)劃的基本概念0,2432798040)(max212121221xxxxxxRDXxxXFs.t. 1.1.線性

5、規(guī)劃的圖解線性規(guī)劃的圖解x2x10F=0F*=620(1.5,7)2022-6-1782. 2. 線性規(guī)劃的基本概念線性規(guī)劃的基本概念1 1）可行解）可行解滿足約束條件及非負(fù)條件的解。滿足約束條件及非負(fù)條件的解。（D D內(nèi)及其邊界上的解）內(nèi)及其邊界上的解）2 2）基本解）基本解使使n-mn-m個(gè)變量等于個(gè)變量等于0 0，解約束方程，解約束方程組組( (共有共有m m個(gè)約束方程個(gè)約束方程) )所得的解。所得的解。基本解對(duì)應(yīng)于約束邊界的交點(diǎn)基本解對(duì)應(yīng)于約束邊界的交點(diǎn). .3 3）基本可行解）基本可行解可行域中的基本解（即可行域中的基本解（即D D的頂點(diǎn)）。的頂點(diǎn)）。4 4）基本變量與非基本變量）基

6、本變量與非基本變量 預(yù)先取為零值的預(yù)先取為零值的n-mn-m個(gè)變量為非個(gè)變量為非基本變量，其余基本變量，其余m m個(gè)為基本變量。個(gè)為基本變量。03xx2x10F=0F*=-620(1.5,7)04x05x01x02x0,.,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.2022-6-179四）線性規(guī)劃的基本性質(zhì)四）線性規(guī)劃的基本性質(zhì) 1 1）可行域）可行域D D為凸集，每個(gè)基本可行解對(duì)應(yīng)于為凸集，每個(gè)基本可行解對(duì)應(yīng)于D D上的上的一個(gè)頂點(diǎn)；一個(gè)頂點(diǎn)； 2 2）只要可行域存在且封閉，則起碼有一個(gè)基本可）只要可行域存在且封閉，則起碼有一個(gè)基本可行

7、解為最優(yōu)點(diǎn)；行解為最優(yōu)點(diǎn)； * *）若最優(yōu)點(diǎn)所在的邊界線與等值線平行，則該）若最優(yōu)點(diǎn)所在的邊界線與等值線平行，則該邊界線上的點(diǎn)均為最優(yōu)點(diǎn)；邊界線上的點(diǎn)均為最優(yōu)點(diǎn)； ）若可行域不封閉，則可能有無(wú)界解。）若可行域不封閉，則可能有無(wú)界解。 3)3)最優(yōu)點(diǎn)可在最優(yōu)點(diǎn)可在D D的頂點(diǎn)中尋找。的頂點(diǎn)中尋找。2022-6-17106-2 6-2 求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法一一. .基本思路基本思路 先取先取D D的一個(gè)頂點(diǎn)作為初始點(diǎn)的一個(gè)頂點(diǎn)作為初始點(diǎn), ,由此出發(fā)朝由此出發(fā)朝可使目標(biāo)函數(shù)降低最快的方向依次經(jīng)過(guò)一系可使目標(biāo)函數(shù)降低最快的方向依次經(jīng)過(guò)一系列的基本可行解列的基本可行解, ,直至

8、達(dá)到最優(yōu)解直至達(dá)到最優(yōu)解. .* *1)1)需獲得一個(gè)初始基本可行解需獲得一個(gè)初始基本可行解; ; 2) 2)每次只更換一個(gè)非基本變量每次只更換一個(gè)非基本變量; ;3)3)保證下降性和可行性保證下降性和可行性. .2022-6-1711二二. .計(jì)算實(shí)例計(jì)算實(shí)例6,.,2 , 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.s.t.1.1.初始基本可行解初始基本可行解取取x x5 5,x,x6 6 為基本變量為基本變量, , 則有則有: :)0(X0 0 0 0 4 5T375543)0(F2022-6-17122.2.

9、第一次變換頂點(diǎn)第一次變換頂點(diǎn)(1)(1)選取進(jìn)基變量選取進(jìn)基變量原則原則: : 考慮下降性考慮下降性, ,且下降得最快且下降得最快判別數(shù)判別數(shù): :假定假定x x2 2進(jìn)基進(jìn)基, , 則有則有5246252xxxx0206252xxxx取取12x, 15x26x相應(yīng)的目標(biāo)函數(shù)變化量相應(yīng)的目標(biāo)函數(shù)變化量: :1110325326522xxx12a22a即即)(22612522acacc6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2022-6-1713寫成一般形式寫成一般形式: :miijBijjjjacczc11

10、515432203523111251324151344321最小最小,x,x3 3 應(yīng)為進(jìn)基變量應(yīng)為進(jìn)基變量3推論推論: : 若線性規(guī)劃的一個(gè)基本可行解的所有進(jìn)基判別數(shù)均若線性規(guī)劃的一個(gè)基本可行解的所有進(jìn)基判別數(shù)均為非負(fù)為非負(fù), ,則該解為最優(yōu)解則該解為最優(yōu)解. .6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2022-6-1714(2)(2)確定離基變量確定離基變量原則原則: :考慮可行性考慮可行性( (該變量離基后該變量離基后, ,能使余下的基本變量為非負(fù)能使余下的基本變量為非負(fù)) )判別數(shù)判別數(shù): :)35

11、( 335)2( 224336335xxxxxx由于由于)若取若取 ( (離基離基),),則有則有 05x0263xx0323553xx)/()/(323223313113xabaxabaijiiab,.,2, 1mi 進(jìn)基變量下標(biāo)j應(yīng)取應(yīng)取 為正且其值為最小者對(duì)應(yīng)的基本變量離基為正且其值為最小者對(duì)應(yīng)的基本變量離基. .i6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj( (可行可行) )( (不可行不可行) )06x)若取若取 ( (離基離基),),則有則有 2022-6-1715)推論推論: :若線性規(guī)劃的的所

12、有離基若線性規(guī)劃的的所有離基判別數(shù)均為負(fù)數(shù)時(shí)判別數(shù)均為負(fù)數(shù)時(shí), ,則問(wèn)題有無(wú)界解則問(wèn)題有無(wú)界解. .最小最小,x,x6 6 應(yīng)為離基變量應(yīng)為離基變量2) 1 (X0 0 5/3 0 2/3 0T31132335) 1 (F* * ) )因?yàn)橐驗(yàn)?, ,故故 也必須大于也必須大于0, 0, 否則不滿足否則不滿足可行性要求可行性要求; ;0,21bb2313,aa6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj)35( 335)2( 224336335xxxxxx2022-6-1716進(jìn)基進(jìn)基4x3.3.第二次變換頂點(diǎn)

13、第二次變換頂點(diǎn)去掉了去掉了6x5,.,2, 1,.05324423224)(min43215432154321jxxxxxxxxxxxxxxxXFj(1)(2)1)1)確定進(jìn)基變量確定進(jìn)基變量03183103311231231332123223133114421:3)2(3)(4)353132314321xxxx: ) 1 ()2()3(3231031315421xxxxmiijBijjacc12022-6-17172)2)確定離基變量確定離基變量2 . 0310/32531/3521 離基離基5x(1)(1)(2)(2)4321224)(minxxxxXF323103131353132314

14、214321xxxxxxx)2(X0 0 8/5 1/5 0 0T251258)2(F:310/ )2(3)(3)(4)(4)51101101421xxx: ) 1 ()31()3(58107103321xxx353132314321xxxx3231031315421xxxx2022-6-17184. 4. 第三次變換頂點(diǎn)第三次變換頂點(diǎn)1) 1) 確定進(jìn)基變量確定進(jìn)基變量05 . 110121071205 . 310121031421 故故 為最優(yōu)點(diǎn)為最優(yōu)點(diǎn), , 為最優(yōu)值為最優(yōu)值: :)2(X)2(F)2(*XX0 0 8/5 1/5 0 0T251258)2(* FF51101101421

15、xxx58107103321xxx4321224)(minxxxxXF2022-6-1719三三. .用單純形表求解線性規(guī)劃用單純形表求解線性規(guī)劃例例. .用初等變換法求解用初等變換法求解解解: :增廣矩陣增廣矩陣: :1125452121xxxx1112545,51030111123011112390135321xx2022-6-17206,.,2 , 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.離基判別數(shù)離基判別數(shù)進(jìn)基判別數(shù)進(jìn)基判別數(shù) 單純形法實(shí)際上是解一系列的線性方程組單純形法實(shí)際上是解一系列的線性方程組, ,

16、也可用初等也可用初等變換方法列表求解變換方法列表求解. .但需加入判別數(shù)的計(jì)算但需加入判別數(shù)的計(jì)算. .421235基變量基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij例例1 12022-6-172142123基變量基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij421235基變量基變量x1x2x3x4x5x63x5112410425x612310155/3X00

17、00045F037-4-11-20-15jcBicibij2022-6-172242123基變量基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij4212基變量基變量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5jcBicibij已獲得最優(yōu)解已獲得最優(yōu)解2022-6-1723-2-300基變量基變量x1x2x3x40 x3-1110330 x41-4014-1X00034F0

18、0-2-3jcBicibij-2-30基變量基變量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5jcBicibij4,.,2 , 1,.044332)(min42132121jxxxxxxxxxXFjs.t.例例2 2問(wèn)題有無(wú)界解問(wèn)題有無(wú)界解2022-6-17246-3 6-3 初始基本可行初始基本可行解解大大M M法法 引入一組人工變量引入一組人工變量, ,它們?cè)谀繕?biāo)函數(shù)中的它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均是非常大的正數(shù)系數(shù)均是非常大的正數(shù)M;M;(2) (2) 兩相法兩相法 引入一組人工變量引入一組人工變量, ,在人工變量未完全離在人工變量未完全離基

19、前目標(biāo)函數(shù)為各人工變量之和基前目標(biāo)函數(shù)為各人工變量之和, ,當(dāng)人工變當(dāng)人工變量完全離基后恢復(fù)原目標(biāo)函數(shù)。量完全離基后恢復(fù)原目標(biāo)函數(shù)。 當(dāng)當(dāng)A A內(nèi)不包含單位矩陣時(shí)內(nèi)不包含單位矩陣時(shí), ,需引入由人工變量組需引入由人工變量組成的單位矩陣成的單位矩陣, ,以方便獲得初始可行解以方便獲得初始可行解. .2022-6-1725一一. .采用大采用大M M法獲得初始基本可行解法獲得初始基本可行解543214)(minMxMxxxxXF33342253214321xxxxxxxx, 0jx5,.,2 , 1js.t.采用大采用大M M法法：3214)(minxxxXF333422321321xxxxxx,

20、 0jx3 , 2 , 1js.t.原問(wèn)題原問(wèn)題： 因因M M是比其他價(jià)值系數(shù)大得多的正數(shù)是比其他價(jià)值系數(shù)大得多的正數(shù), ,且人工變量非負(fù)且人工變量非負(fù), ,迭代迭代的結(jié)果會(huì)使人工變量趨于零的結(jié)果會(huì)使人工變量趨于零, ,而獲得原問(wèn)題的基本可行解而獲得原問(wèn)題的基本可行解. .2022-6-1726543214)(minMxMxxxxXF33342253214321xxxxxxxx, 0jx5,.,2 , 1js.t.411MM基變量基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij表一表一2022-6-1727411

21、MM基變量基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij411M基變量基變量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3jcBicibij表一表一表二表二2022-6-1728411基變量基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40jcBicibij表三表三初始基本初始基本可行解可行解411M基變量基變量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3jcBicibij表二表二2022-6-1729411基變量基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40jcBicibij411基變量基變量x1x2x3x4x51x3011.81x