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

機(jī)械優(yōu)化設(shè)計(jì)6線性規(guī)劃2024/3/232第六章線性規(guī)劃一.線性規(guī)劃的基本概念二.求解線性規(guī)劃的單純形法三.初始基本可行解2024/3/233

某廠生產(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)用實(shí)例§6-1線性規(guī)劃的基本概念2024/3/234二)線性規(guī)劃的一般形式s.t.特點(diǎn):1)為極小化問題;2)約束取等號(hào);3)限定系數(shù)非負(fù);4)變量非負(fù).式中，—價(jià)值系數(shù)；—結(jié)構(gòu)系數(shù)

—限定系數(shù)2024/3/235將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型的方法1）將極大化問題化為極小化問題

—松弛變量（開關(guān)變量）（兩邊乘-1）4）將負(fù)的限定系數(shù)化為正值3）將任意變量化為非負(fù)變量2）將不等式約束變?yōu)榈仁郊s束：—目標(biāo)函數(shù)變號(hào)；2024/3/236s.t.化為標(biāo)準(zhǔn)型:2024/3/237四）線性規(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)；

ⅱ）若可行域不封閉，則可能有無界解。

3)最優(yōu)點(diǎn)可在D的頂點(diǎn)中尋找。2024/3/238§6-2求解線性規(guī)劃的單純形法一.基本思路

先取D的一個(gè)頂點(diǎn)作為初始點(diǎn),由此出發(fā)朝可使目標(biāo)函數(shù)降低最快的方向依次經(jīng)過一系列的基本可行解,直至達(dá)到最優(yōu)解.*1)需獲得一個(gè)初始基本可行解;2)每次只更換一個(gè)非基本變量;3)保證下降性和可行性.2024/3/239寫成一般形式:最小,x3應(yīng)為進(jìn)基變量推論:

若線性規(guī)劃的一個(gè)基本可行解的所有進(jìn)基判別數(shù)均為非負(fù),則該解為最優(yōu)解.2024/3/2310(2)確定離基變量①原則:考慮可行性(該變量離基后,能使余下的基本變量為非負(fù))②判別數(shù):由于ⅰ)若取(離基),則有應(yīng)取為正且其值為最小者對(duì)應(yīng)的基本變量離基.(可行)(不可行)ⅱ)若取(離基),則有2024/3/2311ⅱ)推論:若線性規(guī)劃的的所有離基判別數(shù)均為負(fù)數(shù)時(shí),則問題有無界解.最小,x6

應(yīng)為離基變量[005/302/30]T*ⅰ)因?yàn)?故也必須大于0,否則不滿足可行性要求;2024/3/2312進(jìn)基3.第二次變換頂點(diǎn)去掉了(1)(2)1)確定進(jìn)基變量(3)(4)2024/3/23132)確定離基變量

離基(1)(2)[008/51/500]T(3)(4)2024/3/23144.第三次變換頂點(diǎn)1)確定進(jìn)基變量

故為最優(yōu)點(diǎn),為最優(yōu)值:[008/51/500]T2024/3/2315三.用單純形表求解線性規(guī)劃例.用初等變換法求解解:增廣矩陣:2024/3/2316s.t.離基判別數(shù)進(jìn)基判別數(shù)

單純形法實(shí)際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數(shù)的計(jì)算.421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例12024/3/231742123基變量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3421235基變量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-152024/3/231842123基變量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)解2024/3/2319-2-300基變量x1x2x3x40x3-1110330x41-4014-1X00034F00-2-3-2-30基變量x1x2x3x4-3x2-1103-30x4-30116-16/3X103016F1-9-5s.t.例2問題有無界解2024/3/2320§6-3初始基本可行解大M法引入一組人工變量,它們?cè)谀繕?biāo)函數(shù)中的系