(5.3.2)-2.1線性規(guī)劃問題數(shù)學(xué)建模

腳本-線性規(guī)劃問題（ppt1,ppt2）同學(xué)，你好！這節(jié)課我們來學(xué)習(xí)線性規(guī)劃問題。(ppt3)首先，我們來探討一下規(guī)劃模型的重要性。(ppt4)（動畫1）規(guī)劃模型是一類有著廣泛應(yīng)用的確定性系統(tǒng)優(yōu)化模型。（動畫2）例如，嫦娥三號軟著陸軌道確定和最優(yōu)控制研究利用到了規(guī)劃模型。（動畫3）公交車的最優(yōu)調(diào)度策略也是屬于規(guī)劃模型。(ppt5)（動畫1）還有項(xiàng)目投資利潤最大化，（動畫2）以及醫(yī)院病床的合理性安排，都離不開規(guī)劃模型。(ppt6)接下來，我們來了解規(guī)劃模型中最基本的模型，線性規(guī)劃模型。(ppt7)（動畫1）首先，什么是線性規(guī)劃問題呢？（動畫2）線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。（動畫3）他的特征是在滿足一組線性約束和變量非負(fù)的條件下，求多變量線性函數(shù)值（最大值或最小值）。（動畫4）因?yàn)樗倪@個(gè)特征，所以所有的線性規(guī)劃模型可以化為相同的標(biāo)準(zhǔn)形式，這樣就可以采用固定的方法求解，比如單純形法。(ppt8)（動畫1）然后我們來了解一下線性規(guī)劃問題的標(biāo)準(zhǔn)形式。（動畫2）線性規(guī)劃問題的目標(biāo)函數(shù)是：max??=??_1??_1+??_2??_2+……+??_????_??，（動畫3）其約束條件為a_11*x_1加上a_12*x_2一直加到a_1n*x_n等于b_1，類似的可以得到第m個(gè)約束條件為a_m1*x_1加上a_m2*x_2一直加到a_mn*x_n等于b_m。并且x_1,x_2,…,x_n都是大于等于0的。B_1,b_2,…,b_m均為非負(fù)值。(ppt9)（動畫1）若令C=(c_1,c_2,…,c_n)的轉(zhuǎn)置，X=(x_1,x_2,…,x_n)的轉(zhuǎn)置，A=約束條件的系數(shù)矩陣，B=(b_1,b_2,…,b_m)的轉(zhuǎn)置。（動畫2）那么，線性規(guī)劃問題的標(biāo)準(zhǔn)形可以寫為：（動畫3）目標(biāo)函數(shù)：maxz=C的轉(zhuǎn)置乘以X。（動畫4）約束條件可以寫為：AX=B，且X大于等于0。(ppt10)（動畫1）那么，一個(gè)非標(biāo)準(zhǔn)形的問題如何轉(zhuǎn)化為標(biāo)準(zhǔn)形呢？（動畫2）第一，若目標(biāo)函數(shù)是求極小值，那么就等價(jià)于對標(biāo)準(zhǔn)形的目標(biāo)函數(shù)求負(fù)。（動畫3）第二，當(dāng)右端的項(xiàng)??_??小于0時(shí)，只需將等式兩端同乘以(?1),則等式右端(???_??)就大于0。（動畫4）第三，若約束條件為不等式時(shí)，當(dāng)約束條件為小于等于時(shí)，如5??_1+??_2小于等于24，可以令??_3=24?5??_1???_2，則此約束條件就成為5??_1+??_2+??_3=24,??_3大于等于0。(ppt11)（動畫1）當(dāng)約束條件為“大于等于”時(shí)，如10??_1+9??_2大于等于18，則可以令??_4=10??_1+9??_2?18得10??_1+9??_2???_4=18,??_4大于等于0。??_3,??_4都是新加上去的變量，取值為非負(fù)，加到原約束條件上去的目的是將不等式轉(zhuǎn)化為等式，其中??_3稱為松弛變量，??_4稱為剩余變量。（動畫2）取值為無約束的變量。若??_5的取值無約束，則令??_5=x_5一撇減去x_5兩撇，其中x_5一撇，和x_5兩撇均大于等于0。（動畫3）當(dāng)??_6小于等于0時(shí)，就令x_6一撇=???_6，即有x_6一撇大于等于0。(ppt12)然后我們來講一下線性規(guī)劃問題的python求解方法。（動畫1）線性規(guī)劃的目標(biāo)函數(shù)和約束函數(shù)標(biāo)準(zhǔn)形式可寫為：目標(biāo)函數(shù)為：????????=??^??*??，約束條件為：A*x小于等于b；Aeq*x=beq；x大于等于Lb小于等于Ub。（動畫2）函數(shù)的linprog格式為（動畫3）res=linprog(c,A,b,Aeq,beq,bound)（動畫4）其中c代表目標(biāo)向量；（動畫5）A,b代表不等號約束；（動畫6）Aeq，beq代表等號約束；（動畫7）bound表示決策向量的下界和上界向量所組成的n個(gè)元素的元組。(ppt13)接下來我們通過案例來進(jìn)一步了解線性規(guī)劃模型。(ppt14)（動畫1，2）先來看例一，一奶制品加工廠用牛奶生產(chǎn)A,B兩種奶制品，1桶牛奶工人可以在甲類設(shè)備上用12小時(shí)加工成3千克A,或者工人在乙類設(shè)備上用8小時(shí)加工成4千克B。假定根據(jù)市場需求，生產(chǎn)的A,B全部能售出，且每千克A獲利24元，每千克B獲利16元?，F(xiàn)在加工廠能得到50桶牛奶的供應(yīng)。正式工人總的勞動時(shí)間為480小時(shí)，并且甲類設(shè)備至多能加工100千克A,乙類設(shè)備的加工能力沒有限制。試為該廠制定一個(gè)生產(chǎn)計(jì)劃，使獲利最大，并進(jìn)一步討論以下問題：(1)若可以聘用臨時(shí)工人以增加勞動時(shí)間，是否聘用臨時(shí)工人？(2)假設(shè)由于市場需求變化，每千克A的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？(ppt15)（動畫1）我們來解這個(gè)線性規(guī)劃問題，設(shè)該廠用??_1桶牛奶生產(chǎn)A,用??_2桶牛奶生產(chǎn)B,所得到的總利潤為??(元）。（動畫2）先看第一問是否聘用臨時(shí)工人。（動畫3）確定目標(biāo)函數(shù)：由題意知生產(chǎn)一千克A可得利潤24元，生產(chǎn)一千克B可得利潤16元，而一桶牛奶由一個(gè)設(shè)備加工，則總利潤為：maxz=72*x_1+64*x_2。第二步，確定約束條件，第一個(gè)條件是牛奶供應(yīng)數(shù)量的約束，x_1+x_2小于等于50。第二個(gè)條件是工人的勞動時(shí)間約束，12*x_1+8*x_2小于等于480。第三個(gè)條件是工廠的設(shè)備約束，3*x_1小于等于100。第四個(gè)條件為產(chǎn)品的產(chǎn)量不能為負(fù)數(shù)，因此x_i都大于等于0。(ppt16)（動畫1）根據(jù)上面的分析，我們把目標(biāo)函數(shù)與約束條件聯(lián)立，就可以建立數(shù)學(xué)模型如下所示。（動畫2）最后我們通過python求解，解得??_1=20,??_2=30，即最優(yōu)解使得不等式的第二個(gè)約束條件達(dá)到了邊界。所以增加勞動時(shí)間，會提高收益，因而應(yīng)該聘用臨時(shí)工人。(ppt17)（動畫1）再來看第二個(gè)問題，假設(shè)由于市場需求變化，每千克A的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃。（動畫2）我們可以得到目標(biāo)函數(shù)為：max_z=90x_1+64x_2。約束條件為和問題一中的一樣，（動畫3）運(yùn)用python求得結(jié)果如下：??_1=20,??_2=30，因?yàn)榍蟮玫淖顑?yōu)解不變，所以不應(yīng)該改變生產(chǎn)計(jì)劃。(ppt18)（動畫1）再來看第二個(gè)例子，一貿(mào)易公司專門經(jīng)營某種雜糧的批發(fā)業(yè)務(wù).公司現(xiàn)有庫容量5000噸的倉庫．1月1日，公司擁有庫存1000噸雜糧，并有資金20000元．估計(jì)第一季度雜糧價(jià)格如下表所示，如果買進(jìn)的雜糧當(dāng)月到貨，但需到下月才能賣出，且規(guī)定“貨到付款”。公司希望季度末庫存為2000噸，問應(yīng)當(dāng)采取什么樣的買進(jìn)和賣出政策，才能使三個(gè)月總的獲利最大？(ppt19)（動畫1）先來分析一下問題，首先確定決策變量：要確定每個(gè)月買進(jìn)多少，賣出多少，故設(shè)：一、二、三月買進(jìn)的雜糧噸數(shù)分別為分別為x_1，x_2，x_3；一、二、三月賣出雜糧的噸數(shù)分別為y_1，y_2，y_3。（動畫2）再來確定目標(biāo)函數(shù)：max??=3.10??_1+3.25??_2+2.95??_3?2.85??_1?3.05??_2?2.90??_3（動畫3）確定約束條件：依題意，共有四類約束即存貨約束、庫容約束、資金約束、期末庫存約束。下面我們來分別討論。(ppt20)（動畫1）①存貨約束：由于當(dāng)月買進(jìn)的雜糧只能在下月出售，故每個(gè)月賣出的雜糧不能超過上個(gè)月末的存貨量，即得到存貨約束為??_1小于等于1000，??_2小于等于1000???_1+??_1，??_3小于等于1000???_1+??_1???_2+??_2小于等于5000。（動畫2）②庫容約束：由于庫容為5000噸，那么每個(gè)月的存貨數(shù)量不能超過5000噸，不妨設(shè)貿(mào)易公司每個(gè)月都在月底進(jìn)貨，或者是當(dāng)月在將雜糧賣出以后再進(jìn)貨，這樣就會減少庫存容量，這個(gè)假設(shè)是合理的．那么庫存容量約束為1000???_1+??_1小于等于5000；1000???_1+??_1???_2+??_2小于等于5000。(ppt21)（動畫1）③資金約束：貿(mào)易公司的資金除了初始的以外，每個(gè)月都要出售雜糧回收資金，在回收資金以后，再進(jìn)雜糧，每個(gè)月進(jìn)雜糧的數(shù)量不能超過其擁有資金能購買的雜糧數(shù)量，即得資金約束為：??_1小于等于(20000+3.1*??_1)除以2.85；??_2小于等于(20000+3.1*??_1?2.85*??_1+3.25*??_2)除以3.05；??_3小于等于(20000+3.1*??_1?2.85*??_1+3.25*??_2?3.05*??_2+2.95*??_3)除以2.9。（動畫2）④季末庫存：題中要求季末的庫存為2000噸，得到關(guān)系式：1000???_1+??_1???_2+??_2???_3+??_3=2000。顯然，每個(gè)月出售的雜糧數(shù)和買進(jìn)的雜糧數(shù)不能為負(fù)，即：??_1,??_2,??_3,??_1,??_2,??_3均大于等于0.(ppt22)（動畫1）將上述目標(biāo)函數(shù)和約束條件聯(lián)立，記可得到該公司的雜糧采購與銷售計(jì)劃的線性規(guī)劃數(shù)學(xué)模型。（動畫2）求得最終的結(jié)果為：??_1=5000,??_2=0,??_3=2000;??_1=1000,??_2=5000,??_3=0時(shí)總獲利最大。(ppt23)最后我們來了解一些線性規(guī)劃模型的應(yīng)用。(ppt24)（動畫1）線性規(guī)劃模型可以用于合理規(guī)劃線材問題，研究怎么樣下料用料最