數(shù)學(xué)建模—線性規(guī)劃

1、2022-5-31數(shù)學(xué)建模2022-5-31第三講 線性規(guī)劃應(yīng)用實(shí)例分析線性規(guī)劃問題的求解方法實(shí)驗(yàn)準(zhǔn)備 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)8080輛，輛， 那么那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例例1 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動(dòng)時(shí)間的需求，利潤及工廠每月的現(xiàn)有量如下表。勞動(dòng)時(shí)間的需求，利潤及工廠每月的現(xiàn)有量如下表。 小型小型 中型中型 大型大型 現(xiàn)有現(xiàn)有量量鋼材（噸）鋼材（噸） 1.5 3 5 600勞動(dòng)時(shí)間（小時(shí)）勞動(dòng)時(shí)間（小時(shí)）

2、 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。LP實(shí)例一 汽車生產(chǎn)設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x3，工廠的月利潤為工廠的月利潤為z z。321432xxxzMax6005351.321xxx.ts60000400250280321xxx0,321xxx汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤利潤 2 3 4

3、線性線性規(guī)劃規(guī)劃模型模型(LP)模型求解模型求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 %汽車生產(chǎn)計(jì)劃：線性規(guī)劃模型%format short c=-2;-3;-4;a=1.5,3,5;280,250,400;b=600;60000;x =linprog(c,a,b,zeros(3,1)FVAL=(-c*X)結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z=629，與與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如?。┰囂剑喝缛1=

4、65，x2=167；x1=64，x2=168等，計(jì)算函等，計(jì)算函數(shù)值數(shù)值z，通過比較可能得到更優(yōu)的解。，通過比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿足約束條件。為什么？但必須檢驗(yàn)它們是否滿足約束條件。為什么？汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 例例2 投資方案確定投資方案確定LP實(shí)例二 投資問題某企業(yè)要進(jìn)行投資，現(xiàn)有四個(gè)投資項(xiàng)目。項(xiàng)目A：從第一年到第四年的每年年初需要投資，并于次年年末回收本利115；項(xiàng)目B：從第三年年初需要投資，到第五年年末回收本利125%，但規(guī)定最大投資額不超過40萬元；項(xiàng)目C：第二年初需要投資，到第五年末才能回收本利140%，但規(guī)定最大投資額不超過30萬元；項(xiàng)目D：五年內(nèi)每

5、年的年初可買公債，于當(dāng)年年末歸還，并可獲得6%的利息。已知該部門現(xiàn)有資金100萬元，試為該企業(yè)確定投資方案，使得第五年末它擁有的資金本利總額最大？模型建立模型建立LP實(shí)例二 投資問題u決策變量。決策變量為每年年初向四個(gè)項(xiàng)目的投資額，設(shè)第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4)四個(gè)項(xiàng)目的投資額為xij（萬元）。u目標(biāo)函數(shù)。設(shè)第五年年末擁有的資金本利總額為z。項(xiàng)目年份12345投資限額/萬元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54所有可能的投資項(xiàng)目表LP實(shí)例二 投資問題投資方案要使得第五年末資金本利總額最大，目標(biāo)函數(shù)應(yīng)該是四

6、項(xiàng)投資在第五年年末的本利之和，于是 約束條件模型建立模型建立54233241061401251151 x.x.x.x.zMax1001411xx（1）為了獲得最大的投資收益，每年年初應(yīng)將手頭的全部資金投出去，因此第一年的投資總額應(yīng)是100萬元，即（2）b第二年的投資總額應(yīng)是第一年年底回收的各項(xiàng)投資的本利，.xxxLP實(shí)例二 投資問題模型建立模型建立（3）同理，第三、四、五每年的投資額應(yīng)是上一年年底回收的各項(xiàng)投資的本利，即第三年：第四年：第五年：314454213444411124343231151061151061151061x.x.xx.x.xxx.x.xxx項(xiàng)目年

7、份12345投資限額/萬元Ax11x21x31x41Bx3240Cx2330Dx14x24x34x44x54LP實(shí)例二 投資問題（4）由于投資的限額，因此還有模型建立模型建立30,402332xx數(shù)學(xué)模型數(shù)學(xué)模型4,1;5 ,1,0jixij314454213444411124343231151061151061151061x.x.xx.x.xxx.x.xx.xxx1001411xx54233241061401251151 x.x.x.x.zMaxs . t .LP實(shí)例二 投資問題（3）用matlab的linprog函數(shù)求解，可得模型求解%線性規(guī)劃：投資問題%c=ze

8、ros(3,1);-1.4;0;0;-1.25;0;-1.15;0;-1.06;a=zeros(6,1),1,zeros(4,1);zeros(3,1),1,zeros(7,1);b=40;30;aeq_one=1,1,zeros(9,1);aeq_two=0,-1.06,1,1,1,zeros(6,1);aeq_three=-1.15,zeros(3,1),-1.06,1,1,1,zeros(3,1);aeq_four=0,0,-1.15,zeros(4,1),-1.06,1,1,0;aeq_five=zeros(5,1),-1.15,zeros(3,1),-1.06,1;Aeq=aeq_o

9、ne;aeq_two;aeq_three;aeq_four;aeq_five;beq=100;0;0;0;0;x=linprog(c,a,b,Aeq,beq,zeros(11,1)vlaue=(-c*x)LP實(shí)例二 投資問題模型分析 投資方案表第五年末資金本利總額最大為143.75萬元。問題：有沒有其它的投資組合，在第五年末獲得更大或者相同的資本總額？項(xiàng)目年份12345Ax11=62.2643x21=9.9999x31=17.0592x41=26.9173Bx32=40Cx23=30Dx14=37.7357x24=0 x34=14.5448x44=0 x54=19.6181x11=71.698

10、112萬元，x14=28.301888萬元，x23=30萬元，x32=40萬元，x34=42.452831萬元，x41=45萬元，例例3 飛機(jī)運(yùn)輸安排飛機(jī)運(yùn)輸安排LP實(shí)例三 運(yùn)輸問題某貨機(jī)有三個(gè)貨艙：前艙、中艙、后艙。三個(gè)貨艙所能裝載的貨物的最大重量和體積都要限制，如下表所示。并且，為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大允許的重量成比例。前艙中艙后艙重量限制/t10168體積限制/m3680087005300三個(gè)貨艙裝載貨物的最大容許量和體積例例3 3 飛機(jī)運(yùn)輸安排飛機(jī)運(yùn)輸安排LP實(shí)例三 運(yùn)輸問題現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信息如下表所示，最后一列表示裝運(yùn)該貨

11、物后獲得的利潤。質(zhì)量/t空間/(m3/t)利潤(元/t)貨物1184803100貨物2156503800貨物3235803500貨物4123902850四類裝運(yùn)貨物的信息問題：應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行利潤最大？2022-5-31LP實(shí)例三 運(yùn)輸問題1.模型假設(shè)題目中沒有對貨物形狀提出要求，我們可做如下假設(shè)：每種貨物可以分割到任意??；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙。決策變量：用xij表示第i種貨物裝入第j個(gè)貨艙的重量（噸），貨艙j=1,2,3分別表示前艙、中艙、后艙。目標(biāo)函數(shù)：決策目標(biāo)是最大化總利潤，即目標(biāo)函數(shù)為2.模型建立11121321222

12、33132334142433100()3800()3500()2850().zxxxxxxxxxxxx 2022-5-31LP實(shí)例三 運(yùn)輸問題約束條件：約束條件包括以下4個(gè)方面：2.模型建立2022-5-31LP實(shí)例三 運(yùn)輸問題約束條件：約束條件包括以下4個(gè)方面：2.模型建立2022-5-31LP實(shí)例三 運(yùn)輸問題將以上模型參數(shù)輸入matlab中 模型，可以得到結(jié)果。參考結(jié)果：最優(yōu)解為x21=10t, x23=5t, x32=12.947t, x33=3t, x42=3.053t, 其余變量均為零，最優(yōu)值z=121515.8t。建模過程中假設(shè)的嚴(yán)謹(jǐn)程度？如果貨物運(yùn)輸過程中有風(fēng)險(xiǎn)？如何加入風(fēng)險(xiǎn)控制

13、？模型的適用范圍？是否達(dá)到建模的目的？思考其它類似的問題:勞動(dòng)力的安排問題；原料比例分配問題等3.模型求解4.模型分析2022-5-31線性規(guī)劃問題線性規(guī)劃（LP）數(shù)學(xué)規(guī)劃問題：有限的人力、物力、財(cái)力等資源做最優(yōu)決策當(dāng)?shù)玫降臄?shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)的數(shù)學(xué)模型。LP問題的數(shù)學(xué)建模過程（1）列出約束條件及目標(biāo)函數(shù)決策變量106目標(biāo)函數(shù)（線性函數(shù)）約束條件104（2）約束條件所表達(dá)的可行域單純形法（改進(jìn)單純形法、對偶單純形法、多項(xiàng)式時(shí)間算法）（3）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值2022-5-31線性規(guī)劃問題求解方法單純形法LP問題的可行域是n維向量空間Rn的多面凸集，其最優(yōu)解如果存在，必在該凸集的某頂點(diǎn)處達(dá)到。凸集：任意兩點(diǎn)的連線都在集合S內(nèi)，稱S為凸集歐式空間：直觀上，凸集就是凸的。一維：直線，線段，射線；二維：圓，橢圓，扇面；三維：球可行解：滿足所有約束條件的解可行域：所有可行解的集合基本可行解：頂點(diǎn)所對應(yīng)的可行解最優(yōu)解：是目標(biāo)函數(shù)達(dá)到最大或最小值的可行解存在一個(gè)：某個(gè)頂點(diǎn)所對應(yīng)的基本可行解存在無窮多個(gè)不存在：約束條件不阻止目標(biāo)函數(shù)值的（負(fù)方向）無限增大2022-5-31線性規(guī)劃問題求解方法單純形法最優(yōu)解如存在，一定在可行域的頂點(diǎn)處達(dá)到基本可行解個(gè)數(shù)有限，可以在基本可行解中尋找最優(yōu)解需要解決的問題？如何找到頂