機械優(yōu)化設計6線性規(guī)劃ppt課件

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

2、0元和元和8080元。問工廠如何組織消費才干獲得元。問工廠如何組織消費才干獲得最大利潤？最大利潤？一運用實例一運用實例6-1 6-1 線性規(guī)劃的根本概念線性規(guī)劃的根本概念日利潤最大日利潤最大消費才干限制消費才干限制勞動力限制勞動力限制變量非負變量非負.,21xx解解: 設甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為設甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為0,2432798040)(max212121221xxxxxxRDXxxXFs.t.二二) )線性規(guī)劃的普通方式線性規(guī)劃的普通方式0,.,.)(min21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxab

3、xaxaxaxcxcxcXFs.t.s.t.特點特點: 1): 1)為極小化問題為極小化問題; 2); 2)約束取等號約束取等號; ; 3) 3)限定系數(shù)非負限定系數(shù)非負; 4); 4)變量非負變量非負. .式中，式中， 價值系數(shù)；價值系數(shù)； 構造系數(shù)構造系數(shù) 限定系數(shù)限定系數(shù)jcijaib 將數(shù)學模型化為規(guī)范型的方法將數(shù)學模型化為規(guī)范型的方法 1 1將極大化問題化為極小化將極大化問題化為極小化問題問題iibXg)() 1 ( 若iibXg)()2(若kx 松弛變量松弛變量/jjjxxx開關變量開關變量兩邊乘兩邊乘-1-14 4將負的限定系數(shù)化為正值將負的限定系數(shù)化為正值3 3將恣意變量化為非

4、負變量將恣意變量化為非負變量2 2將不等式約束變?yōu)榈仁郊s束：將不等式約束變?yōu)榈仁郊s束：目的函數(shù)變號；目的函數(shù)變號；ikibxXg)(ikibxXg)(0,.,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.化為規(guī)范型化為規(guī)范型:三線性規(guī)劃的根本概念三線性規(guī)劃的根本概念0,2432798040)(max212121221xxxxxxRDXxxXFs.t. 1. 1.線性規(guī)劃的圖線性規(guī)劃的圖解解x2x10F=0F*=620(1.5,7)2. 2. 線性規(guī)劃的根本概念線性規(guī)劃的根本概念1 1可行解可行解滿足約束條件及非負條件的解。滿足約束條件及非負條

5、件的解。D D內(nèi)及其邊境上的解內(nèi)及其邊境上的解2 2根本解根本解使使n-mn-m個變量等于個變量等于0 0，解約束方程，解約束方程組組( (共有共有m m個約束方程個約束方程) )所得的解。所得的解。根本解對應于約束邊境的交點根本解對應于約束邊境的交點. .3 3根本可行解根本可行解可行域中的根本解即可行域中的根本解即D D的頂點。的頂點。4 4根本變量與非根本變量根本變量與非根本變量 預先取為零值的預先取為零值的n-mn-m個變量為非個變量為非根本變量，其他根本變量，其他m m個為根本變量。個為根本變量。03xx2x10F=0F*=-620(1.5,7)04x05x01x02x0,.,243

6、2798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.四線性規(guī)劃的根本性質(zhì)四線性規(guī)劃的根本性質(zhì) 1 1可行域可行域D D為凸集，每個根本可行解對應于為凸集，每個根本可行解對應于D D上的一個頂點；上的一個頂點； 2 2只需可行域存在且封鎖，那么起碼有一只需可行域存在且封鎖，那么起碼有一個根本可行解為最優(yōu)點；個根本可行解為最優(yōu)點； * *假設最優(yōu)點所在的邊境限與等值線平假設最優(yōu)點所在的邊境限與等值線平行，那么該邊境限上的點均為最優(yōu)點；行，那么該邊境限上的點均為最優(yōu)點； 假設可行域不封鎖，那么能夠有無界假設可行域不封鎖，那么能夠有無界解。解。 3)3)最優(yōu)點可

7、在最優(yōu)點可在D D的頂點中尋覓。的頂點中尋覓。6-2 6-2 求解線性規(guī)劃的單純形法求解線性規(guī)劃的單純形法一一. .根本思緒根本思緒 先取先取D D的一個頂點作為初始點的一個頂點作為初始點, ,由此出發(fā)朝可使目由此出發(fā)朝可使目的函數(shù)降低最快的方向依次經(jīng)過一系列的根本可行的函數(shù)降低最快的方向依次經(jīng)過一系列的根本可行解解, ,直至到達最優(yōu)解直至到達最優(yōu)解. .* *1)1)需獲得一個初始根本可行解需獲得一個初始根本可行解; ; 2) 2)每次只改換一個非根本變量每次只改換一個非根本變量; ;3)3)保證下降性和可行性保證下降性和可行性. .二二. .計算實例計算實例6,.,2 , 1,.05324

8、4253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.s.t.1.1.初始根本可行解初始根本可行解取取x5,x6 x5,x6 為根本變量為根本變量, , 那么有那么有: :)0(X0 0 0 0 4 5T375543)0(F2.2.第一次變換頂點第一次變換頂點(1)(1)選取進基變量選取進基變量原那么原那么: : 思索下降性思索下降性, ,且下降得最且下降得最快快判別數(shù)判別數(shù): :假定假定x2x2進基進基, , 那么有那么有5246252xxxx0206252xxxx取取12x, 15x26x相應的目的函數(shù)變化量相應的目的函數(shù)變化量: :11

9、10325326522xxx12a22a即即)(22612522acacc6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj寫成普通方式寫成普通方式: :miijBijjjjacczc11515432203523111251324151344321最小最小,x3 ,x3 應為進基變應為進基變量量3推論推論: : 假設線性規(guī)劃的一個根本可行解的一切進假設線性規(guī)劃的一個根本可行解的一切進基判別數(shù)均為非負基判別數(shù)均為非負, ,那么該解為最優(yōu)解那么該解為最優(yōu)解. .6,.,2, 1,.053244253224)(min643

10、2154321654321jxxxxxxxxxxxxxxxxxXFj(2)(2)確定離基變量確定離基變量原那么原那么: :思索可行性思索可行性( (該變量離基后該變量離基后, ,能使余下的根本變量為非能使余下的根本變量為非負負) )判別數(shù)判別數(shù): :)35( 335)2( 224336335xxxxxx由于由于)假設取假設取 ( (離基離基),),那那么有么有 05x0263xx0323553xx)/()/(323223313113xabaxabaijiiab,.,2 , 1mi 進基變量下標j應取應取 為正且其值為最小者對應的根本變量離基為正且其值為最小者對應的根本變量離基. .i6,.,2

11、, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj( (可行可行) )( (不可行不可行) )06x)假設取假設取 ( (離基離基),),那么那么有有 )推論推論: :假設線性規(guī)劃的的一切離假設線性規(guī)劃的的一切離基判別數(shù)均為負數(shù)時基判別數(shù)均為負數(shù)時, ,那么問題有無那么問題有無界解界解. .最小最小,x6 ,x6 應為離基變應為離基變量量2) 1 (X0 0 5/3 0 2/3 0T31132335) 1 (F* * ) )由于由于 , ,故故 也必需大于也必需大于0, 0, 否那么不滿否那么不滿足可行性要求足可行性要求; ;

12、0,21bb2313,aa6,.,2, 1,.053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj)35( 335)2( 224336335xxxxxx進基進基4x3.3.第二次變換頂點第二次變換頂點去掉了去掉了6x5,.,2, 1,.05324423224)(min43215432154321jxxxxxxxxxxxxxxxXFj(1)(2)1)1)確定進基變量確定進基變量03183103311231231332123223133114421:3)2(3)(4)353132314321xxxx: ) 1 ()2()3(323103131

13、5421xxxxmiijBijjacc12)2)確定離基變量確定離基變量2 . 0310/32531/3521 離基離基5x(1)(1)(2)(2)4321224)(minxxxxXF323103131353132314214321xxxxxxx)2(X0 0 8/5 1/5 0 0T251258)2(F:310/ )2(3)(3)(4)(4)51101101421xxx: ) 1 ()31()3(58107103321xxx353132314321xxxx3231031315421xxxx4. 4. 第三次變換頂點第三次變換頂點1) 1) 確定進基變量確定進基變量05 . 110121071

14、205 . 310121031421 故故 為最優(yōu)點為最優(yōu)點, , 為最優(yōu)值為最優(yōu)值: :)2(X)2(F)2(*XX0 0 8/5 1/5 0 0T251258)2(* FF51101101421xxx58107103321xxx4321224)(minxxxxXF三三. .用單純形表求解線性規(guī)劃用單純形表求解線性規(guī)劃例例. .用初等變換法求解用初等變換法求解解解: :增廣矩陣增廣矩陣: :1125452121xxxx1112545,51030111123011112390135321xx6,.,2 , 1,.053244253224)(min6432154321654321jxxxxxxx

15、xxxxxxxxxxXFjs.t.離基判別數(shù)離基判別數(shù)進基判別數(shù)進基判別數(shù) 單純形法實踐上是解一系列的線性方程組單純形法實踐上是解一系列的線性方程組, ,也可用初等也可用初等變換方法列表求解變換方法列表求解. .但需參與判別數(shù)的計算但需參與判別數(shù)的計算. .421235基變量基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij例例1 142123基變量基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/

16、3-25/3jcBicibij421235基變量基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij42123基變量基變量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)解-2-300基

17、變量基變量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3jcBicibij-2-30基變量基變量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5jcBicibij4,.,2 , 1,.044332)(min42132121jxxxxxxxxxXFjs.t.例例2 2問題有無界解問題有無界解6-3 6-3 初始根本可行初始根本可行解解大大M M法法 引入一組人工變量引入一組人工變量, ,它們在目的它們在目的函數(shù)中的系數(shù)均是非常大的正數(shù)函數(shù)中的系數(shù)均是非常大的正數(shù)M;M;(2) (2) 兩相法兩相法 引入一組人

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

19、xxXF333422321321xxxxxx, 0jx3 , 2 , 1js.t.原問題：原問題： 因因M M是比其他價值系數(shù)大得多的正數(shù)是比其他價值系數(shù)大得多的正數(shù), ,且人工變量非負且人工變量非負, ,迭代迭代的結果會使人工變量趨于零的結果會使人工變量趨于零, ,而獲得原問題的根本可行解而獲得原問題的根本可行解. .543214)(minMxMxxxxXF33342253214321xxxxxxxx, 0jx5,.,2 , 1js.t.411MM基變量基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij表一表一4

20、11MM基變量基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij411M基變量基變量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3jcBicibij表一表一表二表二411基變量基變量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表二表二411基變量基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40jcBicibij411基變量基變量x1x2x3x4x51x3