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

第六章線性規(guī)劃一.線性規(guī)劃的基本概念二.求解線性規(guī)劃的單純形法三.初始基本可行解2022/11/21

某廠生產(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元。問工廠如何組織生產(chǎn)才能獲得最大利潤(rùn)？一）應(yīng)用實(shí)例§6-1線性規(guī)劃的基本概念2022/11/22日利潤(rùn)最大生產(chǎn)能力限制勞動(dòng)力限制變量非負(fù)解:

設(shè)甲、乙兩種產(chǎn)品的日產(chǎn)件數(shù)分別為s.t.2022/11/23二)線性規(guī)劃的一般形式s.t.特點(diǎn):1)為極小化問題;2)約束取等號(hào);3)限定系數(shù)非負(fù);4)變量非負(fù).式中，—價(jià)值系數(shù)；—結(jié)構(gòu)系數(shù)

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

—松弛變量（開關(guān)變量）（兩邊乘-1）4）將負(fù)的限定系數(shù)化為正值3）將任意變量化為非負(fù)變量2）將不等式約束變?yōu)榈仁郊s束：—目標(biāo)函數(shù)變號(hào)；2022/11/25s.t.化為標(biāo)準(zhǔn)型:2022/11/26三）線性規(guī)劃的基本概念s.t.

1.線性規(guī)劃的圖解x2x10F=0F*=620(1.5,7)2022/11/272.線性規(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*=-620(1.5,7)s.t.2022/11/28四）線性規(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)中尋找。2022/11/29§6-2求解線性規(guī)劃的單純形法一.基本思路

先取D的一個(gè)頂點(diǎn)作為初始點(diǎn),由此出發(fā)朝可使目標(biāo)函數(shù)降低最快的方向依次經(jīng)過一系列的基本可行解,直至達(dá)到最優(yōu)解.*1)需獲得一個(gè)初始基本可行解;2)每次只更換一個(gè)非基本變量;3)保證下降性和可行性.2022/11/210二.計(jì)算實(shí)例s.t.1.初始基本可行解取x5,x6為基本變量,則有:[000045]T2022/11/2112.第一次變換頂點(diǎn)(1)選取進(jìn)基變量①原則:考慮下降性,且下降得最快②判別數(shù):假定x2進(jìn)基,則有取相應(yīng)的目標(biāo)函數(shù)變化量:即2022/11/212寫成一般形式:最小,x3應(yīng)為進(jìn)基變量推論:

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

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

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

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

單純形法實(shí)際上是解一系列的線性方程組,也可用初等變換方法列表求解.但需加入判別數(shù)的計(jì)算.例12022/11/2202022/11/221已獲得最優(yōu)解2022/11/222s.t.例2問題有無界解2022/11/223§6-3初始基本可行解大M法

引入一組人工變量,它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均是非常大的正數(shù)M;(2)兩相法

引入一組人工變量,在人工變量未完全離基前目標(biāo)函數(shù)為各人工變量之和,當(dāng)人工變量完全離基后恢復(fù)原目標(biāo)函數(shù)。

當(dāng)A內(nèi)不包含單位矩陣時(shí),需引入由人工變量組成的單位矩陣,以方便獲得初始可行解.2022/11/224一.采用大M法獲得初始基本可行解s.t.采用大M法：s.t.原問題：

因M是比其他價(jià)值系數(shù)大得多的正數(shù),且人工變量非負(fù),迭代的結(jié)果會(huì)使人工變量趨于零,而獲得原問題的基本可行解.2022/11/225s.t.表一2022/11/226表一表二2022/11/227表三初始基本可行解表二2022/11/228表三表四初始基本可行解最優(yōu)解2022/11/229二.采用兩相法獲得初始基本可行解大M法的M