數學建模案例之線性規(guī)劃第一頁，共56頁。優(yōu)化問題及其一般模型：

引言優(yōu)化問題是人們在工程技術、經濟管理和科學研究等領域中最常遇到的問題之一。例如：設計師要在滿足強度要求等條件下選擇材料的尺寸，使結構總重量最輕；公司經理要根據生產成本和市場需求確定產品價格，使所獲利潤最高；調度人員要在滿足物質需求和裝載條件下安排從各供應點到需求點的運量和路線，使運輸總費用最低；投資者要選擇一些股票,債券下注,使收益最大,而風險最小…………第二頁，共56頁。一般地，優(yōu)化模型可以表述如下：

這是一個多元函數的條件極值問題，其中

x=[x1,x2,…,xn]。

許多實際問題歸結出的這種優(yōu)化模型，但是其決策變量個數n和約束條件個數m一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡單地用微分法求解，數學規(guī)劃就是解決這類問題的有效方法。

引言第三頁，共56頁。數學規(guī)劃模型分類:“數學規(guī)劃是運籌學和管理科學中應用及其廣泛的分支。在許多情況下，應用數學規(guī)劃取得的如此成功，以致它的用途已超出了運籌學的范疇，成為人們日常的規(guī)劃工具?！盵H.P.Williams.數學規(guī)劃模型的建立]。數學規(guī)劃包括線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、幾何規(guī)劃、多目標規(guī)劃等，用數學規(guī)劃方法解決實際問題，就要將實際問題經過抽象、簡化、假設，確定變量與參數，建立適當層次上的數學模型，并求解。引言第四頁，共56頁。建立數學規(guī)劃模型的步驟:當你打算用數學建模的方法來處理一個優(yōu)化問題的時候，首先要確定尋求的決策是什么，優(yōu)化的目標是什么，決策受到那些條件的限制（如果有限制的話），然后用數學工具（變量、常數、函數等）表示它們，最后用合適的方法求解它們并對結果作出一些定性、定量的分析和必要的檢驗。引言第五頁，共56頁。引言Step1.尋求決策，即回答什么？必須清楚，無歧義。閱讀完題目的第一步不是尋找答案或者解法，而是……Step2.確定決策變量第一來源：Step1的結果，用變量固定需要回答的決策第二來源：由決策導出的變量（具有派生結構）其它來源：輔助變量（聯合完成更清楚的回答）Step3.確定優(yōu)化目標用決策變量表示的利潤、成本等。Step4.尋找約束條件決策變量之間、決策變量與常量之間的聯系。第一來源：需求；第二來源：供給；其它來源：輔助以及常識。Step5.構成數學模型

將目標以及約束放在一起，寫成數學表達式。第六頁，共56頁。內容：如何建立線性規(guī)劃模型舉例線性規(guī)劃模型的求解方法要求：掌握線性規(guī)劃模型的建立方法掌握利用數學軟件LINDO

、Matlab等求解線性規(guī)劃模型的方法理解單純形法的計算步驟重點、難點：重點：線性規(guī)劃模型的建立與軟件求解難點：線性規(guī)劃問題的理論求解方法—單純形法第七頁，共56頁。簡介

線性規(guī)劃是最簡單、應用最廣泛的一種數學規(guī)劃方法，也是應用最早的一種最優(yōu)化方法；線性規(guī)劃的數學模型是目標函數和全部約束式都是變量的線性函數；線性規(guī)劃是學習運籌學的首要課程之一；1947年，丹茨格（Dantzig）提出了單純形法，使線性規(guī)劃的算法趨于成熟；在數學上講，線性規(guī)劃問題就是研究一類條件極值問題，即在一組線性約束條件（包括等式及不等式約束）下，找出一個線性函數的最大值或最小值。第八頁，共56頁。例1：加工奶制品的生產計劃一奶制品加工廠用牛奶生產A1，A2兩種奶制品，一桶牛奶可以在設備甲上用12小時加工成3公斤A1，或者在設備乙上用8小時加工成4公斤A2。根據市場需求，生產的A1、A2全部能夠售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F在加工廠每天能夠得到50桶牛奶的供應，每天正式工人總的勞動時間為480小時，并且設備甲每天至多能加工100公斤A1，設備乙的加工能力沒有限制。試為該廠制定一個生產計劃，使每天獲利最大?并進一步討論以下三個附加問題：

1）若用35元可以買到一桶牛奶，應否作這項投資？若投資，每天最多購買多少桶牛奶？

2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時多少元？

3）由于市場需求變化，每公斤A1的獲利增加到30元，應否改變生產計劃？第九頁，共56頁。問題分析企業(yè)內部的生產計劃有各種不同的情況。

空間層次工廠級：根據外部需求和內部設備、人力、原料等條件，以最大利潤為目標制訂產品生產計劃車間級：根據生產計劃、工藝流程、資源約束及費用參數等，以最小成本為目標制訂生產批量計劃

時間層次若短時間內外部需求和內部資源等不隨時間變化，可制訂單階段生產計劃，否則應制訂多階段生產計劃第十頁，共56頁。問題分析1桶牛奶

3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤每天50桶牛奶

時間480小時

至多加工100公斤A1

制訂生產計劃，使每天獲利最大

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?

A1的獲利增加到30元/公斤，應否改變生產計劃?1桶牛奶

3公斤A1

12小時

8小時

4公斤A2

或獲利24元/公斤

獲利16元/公斤第十一頁，共56頁。模型構成引入決策變量

x1

桶牛奶生產A1，x2桶牛奶生產A2

（每天）目標函數（每天獲利）生產A1

獲利：

24×3x1

生產A2

獲利：16×4x2

每天獲利總額：z=72x1+64x2

約束條件原料供應：x1+x2≤50勞動時間：12x1+8x2≤480加工能力：3x1≤100非負約束：x1,x2≥0第十二頁，共56頁。模型構成數學模型：LP

模型第十三頁，共56頁。線性規(guī)劃模型具有的三條性質比例性

可加性

連續(xù)性

xi對目標函數的“貢獻”與xi取值成正比

xi對約束條件的“貢獻”與xi取值成正比

xi對目標函數的“貢獻”與xj取值無關

xi對約束條件的“貢獻”與xj取值無關

A1,A2每公斤的獲利是與各自產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與各自產量無關的常數A1,A2每公斤的獲利是與相互產量無關的常數每桶牛奶加工出A1,A2的數量和時間是與相互產量無關的常數加工A1,A2的牛奶桶數是實數xi取值連續(xù)第十四頁，共56頁。LP問題的一般概念

1.LP模型的一般形式求一組決策變量x1,x2,…,xn的值，使其滿足約束條件：

并使目標函數取得最大（或最小)值，其中aij,bi,cj為已知量。第十五頁，共56頁。LP問題的一般概念2.標準形式其中第十六頁，共56頁。LP問題的一般概念3.將一般線性規(guī)劃模型轉化為標準形例題：將下述LP模型轉化成標準形式解：轉化分為目標函數、大于等于約束、小于等于約束和自由約束變量幾個不同部分。第十七頁，共56頁。LP問題的一般概念目標函數

maxz=4x1+5x2+7x3-x4

minz1=-4x1-5x2-7x3+x4約束條件大于等于約束x1+x2+2x3-x4≥1添加剩余變量x5≥0

x1+x2+2x3-x4-x5=1小于等于約束2x1-6x2+3x3+x4≤-3添加松弛變量x6≥0

-2x1+6x2-3x3-x4-x6=3自由變量（無）第十八頁，共56頁。LP問題的一般概念化成標準型為：原始形式標準形式第十九頁，共56頁。LP問題的一般概念4.單純形法G.B.Dantzig的單純形法（Simplexmethod）是一個頂點迭代算法，即從一個頂點出發(fā)，沿著凸多面體的棱迭代到另一個頂點，使目標函數值下降（至少不升），由頂點個數的有限性，可以證明經過有限次迭代一定可以求得最優(yōu)解或者判定該問題無最優(yōu)解，這就是單純形法的基本思想。而幾何上一個的頂點對應在代數上的一個基可行解，因此，單純形法求解線性規(guī)劃問題只需要關心基可行解。第二十頁，共56頁。LP問題的一般概念基本理論參見任何一本運籌學教材上的相關內容，下面僅以一個例子說明單純形法的步驟。

利用單純形法求解下述LP問題。

第二十一頁，共56頁。LP問題的一般概念Step1.將一般的LP問題劃成標準形式引入松弛變量x3，x4，x5

將原問題化成標準形式第二十二頁，共56頁。LP問題的一般概念Step2.建立初始單純形表，求出初始的基本可行解x(0)及對應的目標函數值z0建立初始單純形表求出基本可行解x(0)=(0,0,350,200,150)T，求出目標函數值z0=0cj→-1000-1500000系數基變量x1x2x3x4x5b0x3951003500x4450102000x525001150檢驗數rj-1000-15000000第二十三頁，共56頁。LP問題的一般概念Step3.判斷現行解是否是最優(yōu)解。若是，計算結束；否則轉第4步。判斷方法：計算檢驗數rj=cj-zj，其中zj=cBTaij，j=1,2,…,n.若所有的rj≥0，j=1,2,…,n，則現行解為最優(yōu)解。

檢驗數中r1<0，r2<0，上面的結果x(0)不是最優(yōu)解。cj→-1000-1500000系數基變量x1x2x3x4x5b0x3951003500x4450102000x525001150檢驗數rj-1000-15000000第二十四頁，共56頁。LP問題的一般概念Step4.確定進基向量計算min{rj|rj<0

}=rk，則

xk

進基；因min{rj|rj<0}=r2=-1500，所以進基變量為x2

。cj→-1000-1500000系數基變量x1x2↓x3x4x5b0x3951003500x4450102000x525001150檢驗數rj-1000-15000000第二十五頁，共56頁。LP問題的一般概念Step5.確定主元素和離基向量若aik≤0，i=1,2,…,m，則LP問題的可行域R無界，LP問題沒有優(yōu)先的最優(yōu)值，計算結束；否則計算min{bi/aik|aik>0}=bl/ark，此時主元素為ark，xl應離基。

因為150/5<200/5<350/5，所以min{bi/ai2|ai2>0}=b3/a32=3，主元素為a32=5，原來的基變量x5

離基.cj→-1000-1500000系數基變量x1x2↓x3x4x5b0x3951003500x4450102000←x525001150檢驗數rj-1000-15000000第二十六頁，共56頁。LP問題的一般概念Step6.以ark為主元素，進行換基計算，即進行一次Gauss消元計算，求得一個新的基本可行解，然后返回Step3。將xk所對應的列向量化為單位向量，使主元素處為1，其余元素均為0.新的基本可行解為x(0)=(0,30,200,50,0)T最優(yōu)值為-45000.由于r1=-400<0,且存在ai1>0，所以還沒有達到最優(yōu)解。cj→-1000-1500000系數基變量x1x2x3x4x5b0x37010-12000x42001-150-1500x20.41000.230檢驗數rj-400000300-45000第二十七頁，共56頁。LP問題的一般概念重復Step4—Step6

x1進基,x4離基,a21=2為主元素,作Gauss消去法后得到:cj→-1000-1500000系數基變量x1↓x2x3x4x5b0x37010-12000←

x42001-150-1500x20.41000.230檢驗數rj-400000300-45000第二十八頁，共56頁。LP問題的一般概念重復Step3，判斷是否為最優(yōu)解

因為所有的檢驗數rj≥0,所以現行解為最優(yōu)解，即最優(yōu)解為x(0)=(25,20,25,0,0)T，最優(yōu)值為w=-z0=55000.cj→-1000-1500000系數基變量x1x2x3x4x5b0x3001-3.5-2.525-1000x11000.5-0.525-1500x2010-0.20.420檢驗數rj000200100-55000第二十九頁，共56頁。模型求解1.圖解法x1x20ABCDl1l2l3l4l5Z=0Z=2400Z=3360c約束條件目標函數

z=c(常數)～等值線在B(20,30)點得到最優(yōu)解目標函數和約束條件是線性函數

可行域為直線段圍成的凸多邊形

目標函數的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點取得。

第三十頁，共56頁。2.單純形法Step1.將一般的LP問題劃成標準形式引入松弛變量x3，x4，x5

將原問題化成標準形式第三十一頁，共56頁。Step2.建立初始單純形表，求出初始的基本可行解x(0)及對應的目標函數值w0建立初始單純形表求出基本可行解x(0)=(0,0,50,480,100)T，求出目標函數值w0=0cj→-72-64000系數基變量x1x2x3x4x5b0x311100500x41280104800x530001100檢驗數rj-72-640000第三十二頁，共56頁。Step3.判斷現行解是否是最優(yōu)解。若是，計算結束；否則轉第4步。判斷方法：計算檢驗數rj=cj-zj，其中zj=cBTaij，j=1,2,…,n.若所有的rj≥0，j=1,2,…,n，則現行解為最優(yōu)解。

檢驗數中r1<0，r2<0，上面的結果x(0)不是最優(yōu)解。cj→-72-64000系數基變量x1x2x3x4x5b0x311100500x41280104800x530001100檢驗數rj-72-640000第三十三頁，共56頁。Step4.確定進基向量計算min{rj|rj<0

}=rk，則

xk

進基；因min{rj|rj<0}=r1=-72，所以進基向量為x1

。cj→-72-64000系數基變量x1↓x2x3x4x5b0x311100500x41280104800x530001100檢驗數rj-72-640000第三十四頁，共56頁。Step5.確定主元素和離基向量若aik≤0，i=1,2,…,m，則LP問題的可行域R無界，LP問題沒有優(yōu)先的最優(yōu)值，計算結束；否則計算min{bi/aik|aik>0}=bl/ark，此時主元素為ark，xl應離基。

因為50/1>480/12>100/3，所以min{bi/ai1|ai1>0}=b3/a31=100/3，主元素為a31=3，原來的基向量x5

離基.cj→-72-64000系數基變量x1↓x2x3x4x5b0x311100500x41280104800←x530001100檢驗數rj-72-640000第三十五頁，共56頁。Step6.以ark為主元素，進行換基計算，即進行一次Gauss消元計算，求得一個新的基本可行解，然后返回Step3。將xk所對應的列向量化為單位向量，使主元素處為1，其余元素均為0.新的基本可行解為x(0)=(100/3,0,50/3,80,0)T最優(yōu)值為-2400.由于r2=-64<0,且存在ai2>0，所以還沒有達到最優(yōu)解。cj→-72-64000系數基變量x1x2x3x4x5b0x30110-1/350/30x40801-480-72x110001/3100/3檢驗數rj0-640024-2400第三十六頁，共56頁。重復Step4—Step6

x2進基,x4離基,a22=8為主元素,作Gauss消去法后得到:cj→-72-64000系數基變量x1x2↓x3x4x5b0x30110-1/350/30←

x40801-480-72x110001/3100/3檢驗數rj0-640024-2400第三十七頁，共56頁。重復Step3，判斷是否為最優(yōu)解

新的基本可行解為x(0)=(100/3,10,20/3,0,0)T最優(yōu)值為-3040.由于r5=-8<0,且存在ai5>0，所以還沒有達到最優(yōu)解。cj→-72-64000系數基變量x1x2x3x4x5b0x3001-1/81/620/3-64x20101/8-1/210-72x110001/3100/3檢驗數rj0008-8-3040第三十八頁，共56頁。重復Step4—Step6

x5進基,x3離基,a15=1/6為主元素,作Gauss消去法后得到:cj→-72-64000系數基變量x1x2x3x4x5↓b0←

x3001-1/81/620/30x20101/8-1/210-72x110001/3100/3檢驗數rj0008-8-3040第三十九頁，共56頁。重復Step3，判斷是否為最優(yōu)解

因為所有的檢驗數rj≥0,所以現行解為最優(yōu)解，即最優(yōu)解為x(0)=(20,30,0,0,40)T，最優(yōu)值為z=-w0=3360.cj→-72-64000系數基變量x1x2x3x4x5b0x5006-3/41400x2013-1/4030-72x11021/41/320檢驗數rj004820-3360第四十頁，共56頁。3.Mathematica軟件求解方法一：Mathematica軟件所采用的線性規(guī)劃模型是：

式中：X是n維列向量，即X=(x1,x2,

…

,

xn)T,為未知向量；

CT是n維行向量，稱為目標函數f的系數向量；b是m維列向量，稱為約束函數右端向量；

A是m×n維矩陣，稱為約束函數系數矩陣；

符號minf表示對函數f(x)求局部極小。第四十一頁，共56頁。3.Mathematica軟件求解方法二：Mathematica軟件中的NMaximize和NMinimize函數可以解線性規(guī)劃問題,還能解非線性規(guī)劃問題。其使用格式如下：函數意義Nminimize[f,{x,y,

…}]求自變量為x,y,…的函數f的最小值.Nminimize[{f,cons},{x,y,

…}]求滿足約束條件cons的函數f的最小值.Nmaximize[f,{x,y,

…}]求自變量為x,y,…的函數f的最大值.Nmaximize[{f,cons},{x,y,

…}]求滿足約束條件cons的函數f的最大值.第四十二頁，共56頁。4.Matlab軟件求解線性規(guī)劃問題的數學模型：式中f,x,b,beq,lb,ub為向量A和Aeq為矩陣.Linprog函數的調用格式如下：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)[x,fval]=linprog(…)[x,fval,exitflag]=linprog(…)…第四十三頁，共56頁。5.Lindo軟件求解

5.1軟件介紹LINDO是Linear,INteractive,andDiscreteOptimizer的縮寫可求解問題線性規(guī)劃：LinearProgramming(LP)整數規(guī)劃：IntegerProgramming(IP)二次規(guī)劃：QuadraticProgramming(QP)第四十四頁，共56頁。5.2求解線性規(guī)劃問題舉例

利用Lindo軟件求解例題1：奶制品的生產

軟件操作演示

用戶輸入程序

max72x1+64x2

st

2）x1+x2<50

3）12x1+8x2<480

4）3x1<100

end

運行程序第四十五頁，共56頁。輸出結果（不進行靈敏度分析）解釋1

OBJECTIVEFUNCTIONVALUE1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產A1,30桶生產A2，利潤3360元。

第四十六頁，共56頁。輸出結果（不進行靈敏度分析）解釋2

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2“資源”剩余為零的約束為緊約束（有效約束）

max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end原料無剩余時間無剩余加工能力剩余40三種資源第四十七頁，共56頁。輸出結果（不進行靈敏度分析）解釋3

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時“效益”的增量

原料增加1單位,利潤增長48

時間增加1單位,利潤增長2

加工能力增長不影響利潤影子價格

35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？

2元！第四十八頁，共56頁。輸出結果（有靈敏度分析）解釋4RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標函數系數允許變化范圍

(約束條件不變)x1系數范圍(64,96)x2系數范圍(48,72)

A1獲利增加到30元/千克，應否改變生產計劃？不變！x1系數由243=72增加為303=90，在允許范圍內

第四十九頁，共56頁。輸出結果（有靈敏度分析）解釋5RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時右端約束的允許變化范圍

(目標函數不變)原料最多增加10時間最多增加53

35元可買到1桶牛奶，每天最多買多少？最多買10桶!第五十頁，共56頁。例2：奶制品的生產銷售計劃

例1給出了A1，A2兩種奶制品的生產條件,利潤及工廠的“資源”限制全都不變。為增加工廠的獲利，開發(fā)了奶制品的深加工技術:用2小時和3元的加工費，可將1公斤A1加工成0.8公斤高級奶制品B1,也可將1公斤A2加工成0.75公斤高級奶制品B2,每公斤B1能獲利44元，每公斤B2能獲利32元。試為該廠制訂一個生產銷售計劃，使每天的凈利潤最大，并討論以下問題：1）若投資30元可以增加供應1桶牛奶，投資3元可以增加1小時勞動時間，應否作這些投資？若每天投資150元，可賺回多少？

2）每公斤高級奶制品B1,

B2的獲利經常有10%的波動，對制訂的生產銷售計劃有無影響？若每公斤B1的獲利下降10%，計劃應該變化嗎？第五十一頁，共56頁。例2奶制品的生產銷售計劃

在例1基礎上深加工1桶牛奶

3千克A1

12小時

8小時

4公斤A2

或獲利24元/公斤

獲利16元/公斤0.8千克B12小時,3元1千克獲利44元/千克0.75千克B22小時,3元1千克獲利32元/千克制訂生產計劃，使每天凈利潤最大

30元可增加1桶牛奶，3元可增加1小時時間，應否投資？現投資150元，可賺回多少？50桶牛奶,480小時

至多100公斤A1

B1，B2的獲利經常有10%的波動，對計劃有無影響？第五十二頁，共56頁。1桶牛奶

3千克A1

12小時

8小時

4千克A2

或獲利24元/千克

獲利16元/kg

0.8千克

B12小時,3元1千克獲利44元/千克0.75千克B22小時,3元1千克獲利32元/千克銷售x1千克A1,

x2千克A2