機械優(yōu)化設(shè)計之線性規(guī)劃課件(ppt 34頁).ppt

2020/6/5,1,第六章線性規(guī)劃,一.線性規(guī)劃的基本概念,二.求解線性規(guī)劃的單純形法,三.初始基本可行解,2020/6/5,2,某廠生產(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)才能獲得最大利潤？,一）應(yīng)用實例,6-1線性規(guī)劃的基本概念,2020/6/5,3,日利潤最大,生產(chǎn)能力限制,勞動力限制,變量非負,解:設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為,s.t.,2020/6/5,4,二)線性規(guī)劃的一般形式,s.t.,特點:1)為極小化問題;2)約束取等號;3)限定系數(shù)非負;4)變量非負.,式中，價值系數(shù)；結(jié)構(gòu)系數(shù)限定系數(shù),2020/6/5,5,將數(shù)學(xué)模型化為標準型的方法1）將極大化問題化為極小化問題,松弛變量,（開關(guān)變量）,（兩邊乘-1）,4）將負的限定系數(shù)化為正值,3）將任意變量化為非負變量,2）將不等式約束變?yōu)榈仁郊s束：,目標函數(shù)變號；,2020/6/5,6,2020/6/5,7,三）線性規(guī)劃的基本概念,s.t.,1.線性規(guī)劃的圖解,F*=620,2020/6/5,8,2.線性規(guī)劃的基本概念,1）可行解,滿足約束條件及非負條件的解。,（D內(nèi)及其邊界上的解）,2）基本解,使n-m個變量等于0，解約束方程組(共有m個約束方程)所得的解。,基本解對應(yīng)于約束邊界的交點.,3）基本可行解,可行域中的基本解（即D的頂點）。,4）基本變量與非基本變量,預(yù)先取為零值的n-m個變量為非基本變量，其余m個為基本變量。,s.t.,2020/6/5,9,四）線性規(guī)劃的基本性質(zhì)1）可行域D為凸集，每個基本可行解對應(yīng)于D上的一個頂點；2）只要可行域存在且封閉，則起碼有一個基本可行解為最優(yōu)點；*）若最優(yōu)點所在的邊界線與等值線平行，則該邊界線上的點均為最優(yōu)點；）若可行域不封閉，則可能有無界解。3)最優(yōu)點可在D的頂點中尋找。,2020/6/5,10,6-2求解線性規(guī)劃的單純形法,一.基本思路,先取D的一個頂點作為初始點,由此出發(fā)朝可使目標函數(shù)降低最快的方向依次經(jīng)過一系列的基本可行解,直至達到最優(yōu)解.,*1)需獲得一個初始基本可行解;,2)每次只更換一個非基本變量;,3)保證下降性和可行性.,2020/6/5,11,二.計算實例,s.t.,1.初始基本可行解,取x5,x6為基本變量,則有:,000045T,2020/6/5,12,2.第一次變換頂點,(1)選取進基變量,原則:考慮下降性,且下降得最快,判別數(shù):,假定x2進基,則有,取,相應(yīng)的目標函數(shù)變化量:,即,2020/6/5,13,寫成一般形式:,最小,x3應(yīng)為進基變量,推論:若線性規(guī)劃的一個基本可行解的所有進基判別數(shù)均為非負,則該解為最優(yōu)解.,2020/6/5,14,(2)確定離基變量,原則:考慮可行性(該變量離基后,能使余下的基本變量為非負),判別數(shù):,由于,)若取(離基),則有,應(yīng)取為正且其值為最小者對應(yīng)的基本變量離基.,(可行),(不可行),)若取(離基),則有,2020/6/5,15,)推論:若線性規(guī)劃的的所有離基判別數(shù)均為負數(shù)時,則問題有無界解.,最小,x6應(yīng)為離基變量,005/302/30T,*)因為,故也必須大于0,否則不滿足可行性要求;,2020/6/5,16,進基,3.第二次變換頂點,去掉了,1)確定進基變量,2020/6/5,17,2)確定離基變量,離基,008/51/500T,2020/6/5,18,4.第三次變換頂點,1)確定進基變量,2020/6/5,19,三.用單純形表求解線性規(guī)劃,例.用初等變換法求解,解:增廣矩陣:,2020/6/5,20,s.t.,離基判別數(shù),進基判別數(shù),單純形法實際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數(shù)的計算.,例1,2020/6/5,21,2020/6/5,22,已獲得最優(yōu)解,2020/6/5,23,問題有無界解,2020/6/5,24,6-3初始基本可行解,大M法引入一組人工變量,它們在目標函數(shù)中的系數(shù)均是非常大的正數(shù)M;(2)兩相法引入一組人工變量,在人工變量未完全離基前目標函數(shù)為各人工變量之和,當(dāng)人工變量完全離基后恢復(fù)原目標函數(shù)。,當(dāng)A內(nèi)不包含單位矩陣時,需引入由人工變量組成的單位矩陣,以方便獲得初始可行解.,2020/6/5,25,一.采用大M法獲得初始基本可行解,s.t.,采用大M法：,s.t.,原問題：,因M是比其他價值系數(shù)大得多的正數(shù),且人工變量非負,迭代的結(jié)果會使人工變量趨于零,而獲得原問題的基本可行解.,2020/6/5,26,s.t.,表一,2020/6/5,27,表一,表二,2020/6/5,28,表三,初始基本可行解,表二,2020/6/5,29,表三,表四,初始基本可行解,最優(yōu)解,2020/6/5,30,二.采用兩相法獲得初始基本可行解,大M法的M是一個充分大的正數(shù),有時在計算機上不便處理.,s.t.,原問題：,s.t.,相1問題：,202