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

1、第六章 線性規(guī)劃一.線性規(guī)劃的基本概念二.求解線性規(guī)劃的單純形法三.初始基本可行解10/13/20221第六章 線性規(guī)劃一.線性規(guī)劃的基本概念二.求解線性規(guī)劃的單純 某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)品分別由兩條生產(chǎn)線生產(chǎn)。第一條生產(chǎn)甲，每天最多生產(chǎn)9件，第二條生產(chǎn)乙，每天最多生產(chǎn)7件；該廠僅有工人24名，生產(chǎn)甲每件用2工日，生產(chǎn)乙每件用3工日；產(chǎn)品甲、乙的單件利潤(rùn)分別為40元和80元。問(wèn)工廠如何組織生產(chǎn)才能獲得最大利潤(rùn)？一）應(yīng)用實(shí)例6-1 線性規(guī)劃的基本概念10/13/20222 某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)品分別由兩條生產(chǎn)日利潤(rùn)最大生產(chǎn)能力限制勞動(dòng)力限制變量非負(fù)解: 設(shè)甲、乙兩種

2、產(chǎn)品的日產(chǎn)件數(shù)分別為s.t.10/13/20223日利潤(rùn)最大生產(chǎn)能力限制勞動(dòng)力限制變量非負(fù)解: 設(shè)甲、乙兩種產(chǎn)二)線性規(guī)劃的一般形式s.t.特點(diǎn): 1)為極小化問(wèn)題; 2)約束取等號(hào); 3)限定系數(shù)非負(fù); 4)變量非負(fù).式中， 價(jià)值系數(shù)； 結(jié)構(gòu)系數(shù) 限定系數(shù)10/13/20224二)線性規(guī)劃的一般形式s.t.特點(diǎn): 1)為極小化問(wèn)題; 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型的方法1）將極大化問(wèn)題化為極小化問(wèn)題 松弛變量（開關(guān)變量）（兩邊乘-1）4）將負(fù)的限定系數(shù)化為正值3）將任意變量化為非負(fù)變量2）將不等式約束變?yōu)榈仁郊s束：目標(biāo)函數(shù)變號(hào)；10/13/20225將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型的方法 松弛變量（開關(guān)變量）（兩

3、邊乘s.t.化為標(biāo)準(zhǔn)型:10/13/20226s.t.化為標(biāo)準(zhǔn)型:10/11/20226三）線性規(guī)劃的基本概念s.t. 1.線性規(guī)劃的圖解x2x10F=0F*=620(1.5,7)10/13/20227三）線性規(guī)劃的基本概念s.t. 1.線性規(guī)劃的圖解x2x102. 線性規(guī)劃的基本概念1）可行解滿足約束條件及非負(fù)條件的解。（D內(nèi)及其邊界上的解）2）基本解使n-m個(gè)變量等于0，解約束方程組(共有m個(gè)約束方程)所得的解。基本解對(duì)應(yīng)于約束邊界的交點(diǎn).3）基本可行解可行域中的基本解（即D的頂點(diǎn)）。4）基本變量與非基本變量 預(yù)先取為零值的n-m個(gè)變量為非基本變量，其余m個(gè)為基本變量。x2x10F=0F*

4、=-620(1.5,7)s.t.10/13/202282. 線性規(guī)劃的基本概念1）可行解滿足約束條件及非負(fù)條件的四）線性規(guī)劃的基本性質(zhì) 1）可行域D為凸集，每個(gè)基本可行解對(duì)應(yīng)于D上的一個(gè)頂點(diǎn)； 2）只要可行域存在且封閉，則起碼有一個(gè)基本可行解為最優(yōu)點(diǎn)； *）若最優(yōu)點(diǎn)所在的邊界線與等值線平行，則該邊界線上的點(diǎn)均為最優(yōu)點(diǎn)； ）若可行域不封閉，則可能有無(wú)界解。 3)最優(yōu)點(diǎn)可在D的頂點(diǎn)中尋找。10/13/20229四）線性規(guī)劃的基本性質(zhì)10/11/202296-2 求解線性規(guī)劃的單純形法一.基本思路 先取D的一個(gè)頂點(diǎn)作為初始點(diǎn),由此出發(fā)朝可使目標(biāo)函數(shù)降低最快的方向依次經(jīng)過(guò)一系列的基本可行解,直至達(dá)到最

5、優(yōu)解.*1)需獲得一個(gè)初始基本可行解; 2)每次只更換一個(gè)非基本變量;3)保證下降性和可行性.10/13/2022106-2 求解線性規(guī)劃的單純形法一.基本思路 先取D的一二.計(jì)算實(shí)例s.t.1.初始基本可行解取x5,x6 為基本變量, 則有:0 0 0 0 4 5T10/13/202211二.計(jì)算實(shí)例s.t.1.初始基本可行解取x5,x6 為基本變2.第一次變換頂點(diǎn)(1)選取進(jìn)基變量原則: 考慮下降性,且下降得最快判別數(shù):假定x2進(jìn)基, 則有取相應(yīng)的目標(biāo)函數(shù)變化量:即10/13/2022122.第一次變換頂點(diǎn)(1)選取進(jìn)基變量原則: 考慮下降性,且寫成一般形式:最小,x3 應(yīng)為進(jìn)基變量推論:

6、 若線性規(guī)劃的一個(gè)基本可行解的所有進(jìn)基判別數(shù)均為非負(fù),則該解為最優(yōu)解.10/13/202213寫成一般形式:最小,x3 應(yīng)為進(jìn)基變量推論: 10/11/2(2)確定離基變量原則:考慮可行性(該變量離基后,能使余下的基本變量為非負(fù))判別數(shù):由于)若取 (離基),則有 應(yīng)取 為正且其值為最小者對(duì)應(yīng)的基本變量離基.(可行)(不可行)若取 (離基),則有 10/13/202214(2)確定離基變量原則:考慮可行性(該變量離基后,能使余下)推論:若線性規(guī)劃的的所有離基判別數(shù)均為負(fù)數(shù)時(shí),則問(wèn)題有無(wú)界解.最小,x6 應(yīng)為離基變量0 0 5/3 0 2/3 0T* )因?yàn)?,故 也必須大于0, 否則不滿足可行

7、性要求;10/13/202215)推論:若線性規(guī)劃的的所有離基判別數(shù)均為負(fù)數(shù)時(shí),則問(wèn)題有無(wú)進(jìn)基3.第二次變換頂點(diǎn)去掉了(1)(2)1)確定進(jìn)基變量(3)(4)10/13/202216進(jìn)基3.第二次變換頂點(diǎn)去掉了(1)(2)1)確定進(jìn)基變量(32)確定離基變量 離基(1)(2)0 0 8/5 1/5 0 0T(3)(4)10/13/2022172)確定離基變量 離基(1)(2)0 0 4. 第三次變換頂點(diǎn)1) 確定進(jìn)基變量 故 為最優(yōu)點(diǎn), 為最優(yōu)值:0 0 8/5 1/5 0 0T10/13/2022184. 第三次變換頂點(diǎn)1) 確定進(jìn)基變量 故 為最優(yōu)點(diǎn)三.用單純形表求解線性規(guī)劃例.用初等變換

8、法求解解:增廣矩陣:10/13/202219三.用單純形表求解線性規(guī)劃例.用初等變換法求解解:增廣矩陣:s.t.離基判別數(shù)進(jìn)基判別數(shù) 單純形法實(shí)際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數(shù)的計(jì)算.421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例110/13/202220s.t.離基判別數(shù)進(jìn)基判別數(shù) 單純形法實(shí)際上是解一系列的42123基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38

9、/37/3-25/3421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-1510/13/20222142123基變量x1x2x3x4x5x63x51/3-1/342123基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/34212基變量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5已獲得最優(yōu)解10/13/202222

10、42123基變量x1x2x3x4x5x63x51/3-1/3-2-300基變量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3-2-30基變量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5s.t.例2問(wèn)題有無(wú)界解10/13/202223-2-300基變量x1x2x3x40 x3-1110330 x46-3 初始基本可行解大M法 引入一組人工變量,它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均是非常大的正數(shù)M;(2) 兩相法 引入一組人工變量,在人工變量未完全離基前目標(biāo)函數(shù)為各人工變量之和,當(dāng)人工變量完全離基后恢復(fù)原目標(biāo)函數(shù)。 當(dāng)

11、A內(nèi)不包含單位矩陣時(shí),需引入由人工變量組成的單位矩陣,以方便獲得初始可行解.10/13/2022246-3 初始基本可行解大M法 當(dāng)A內(nèi)不包含單位矩陣時(shí),一.采用大M法獲得初始基本可行解s.t.采用大M法：s.t.原問(wèn)題： 因M是比其他價(jià)值系數(shù)大得多的正數(shù),且人工變量非負(fù),迭代的結(jié)果會(huì)使人工變量趨于零,而獲得原問(wèn)題的基本可行解.10/13/202225一.采用大M法獲得初始基本可行解s.t.采用大M法：s.t.s.t.411MM基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M表一10/13/202226s.t.411MM基變量x1

12、x2x3x4x5Mx421210411MM基變量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M411M基變量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3表一表二10/13/202227411MM基變量x1x2x3x4x5Mx42121042Mx411基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40表三初始基本可行解411M基變量x1x2x3x4x5Mx40-14/3121.54x11

13、11/3013X110020F14+2M-3+M-4/3-4M/3表二10/13/202228411基變量x1x2x3x4x51x30-3/411.5-2411基變量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40411基變量x1x2x3x4x51x3011.81x2100.4X300.41.8F32.2表三表四初始基本可行解最優(yōu)解10/13/202229411基變量x1x2x3x4x51x30-3/411.5-2二.采用兩相法獲得初始基本可行解大M法的M是一個(gè)充分大的正數(shù), 有時(shí)在計(jì)算機(jī)上不便處理.s.t.原問(wèn)題：s.t.相1問(wèn)題：10/13/202230二.采用兩相法獲得初始基本可行解大M法的M是一個(gè)充分大的正數(shù)00011基變量x1x2x3x4x51x421210421x53310131X0 00043F07-5-4-30001基變量x1x2x3x4x51x40-14/3121.50 x1111/3013X1 10020F121-4/3表一表二10/13/20223100011基變量x1x2x3x4x51x421210421x000基變量x1x2x3x4x50 x30-3/411.5-20 x115/400.50.4X2 0.501.5F2 00表三初始基