機械優(yōu)化設計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)品甲、乙的單件利潤分別為40元和80元。問工廠如何組織生產(chǎn)才能獲得最大利潤？一）應用實例6-1 線性規(guī)劃的基本概念10/13/20222 某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知：兩種產(chǎn)品分別由兩條生產(chǎn)日利潤最大生產(chǎn)能力限制勞動力限制變量非負解: 設甲、乙兩種

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

3、邊乘s.t.化為標準型:10/13/20226s.t.化為標準型: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）可行解滿足約束條件及非負條件的解。（D內(nèi)及其邊界上的解）2）基本解使n-m個變量等于0，解約束方程組(共有m個約束方程)所得的解?；窘鈱诩s束邊界的交點.3）基本可行解可行域中的基本解（即D的頂點）。4）基本變量與非基本變量 預先取為零值的n-m個變量為非基本變量，其余m個為基本變量。x2x10F=0F*

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

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

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

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

8、法求解解:增廣矩陣:10/13/202219三.用單純形表求解線性規(guī)劃例.用初等變換法求解解:增廣矩陣:s.t.離基判別數(shù)進基判別數(shù) 單純形法實際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數(shù)的計算.421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例110/13/202220s.t.離基判別數(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問題有無界解10/13/202223-2-300基變量x1x2x3x40 x3-1110330 x46-3 初始基本可行解大M法 引入一組人工變量,它們在目標函數(shù)中的系數(shù)均是非常大的正數(shù)M;(2) 兩相法 引入一組人工變量,在人工變量未完全離基前目標函數(shù)為各人工變量之和,當人工變量完全離基后恢復原目標函數(shù)。 當

11、A內(nèi)不包含單位矩陣時,需引入由人工變量組成的單位矩陣,以方便獲得初始可行解.10/13/2022246-3 初始基本可行解大M法 當A內(nèi)不包含單位矩陣時,一.采用大M法獲得初始基本可行解s.t.采用大M法：s.t.原問題： 因M是比其他價值系數(shù)大得多的正數(shù),且人工變量非負,迭代的結果會使人工變量趨于零,而獲得原問題的基本可行解.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是一個充分大的正數(shù), 有時在計算機上不便處理.s.t.原問題：s.t.相1問題：10/13/202230二.采用兩相法獲得初始基本可行解大M法的M是一個充分大的正數(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表三初始基