1、MATLAB建模與求解建模與求解 彭揚?,./2, 5, 321可使利潤最大可使利潤最大問如何安排計劃問如何安排計劃噸噸萬元萬元的利潤分別為的利潤分別為且且下表下表原材料（單位：噸）如原材料（單位：噸）如每噸所需原材料及現有每噸所需原材料及現有，兩種產品，已知生產兩種產品，已知生產，生產生產和和，料料某工廠計劃用三種原材某工廠計劃用三種原材 AAA1. 生產計劃問題生產計劃問題一、線性規劃模型 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2,:21噸噸兩兩種種產產品品分分別別為為設設生生產產解解xx 求最大利潤求最大利潤三種材料量的限制三種

2、材料量的限制生產量非負生產量非負線性規劃模型。問如何調運使運費最低問如何調運使運費最低如下如下公里公里單位單位距離距離兩個糧庫到三個糧站的兩個糧庫到三個糧站的噸噸大米分別為大米分別為三個糧站至少需要三個糧站至少需要噸噸噸噸為為兩個糧庫現存大米分別兩個糧庫現存大米分別調運大米調運大米向三個糧站向三個糧站有兩個糧庫有兩個糧庫,):(,5 , 4 , 2,8 ,4, 32121BBBAA2. 運輸問題運輸問題解：解：設設A A1,1,A A2 2調運到三個糧站的大米分別為調運到三個糧站的大米分別為x x1 1，x x2 2， x x3 3， x x4 4， x x5 5， x x6 6噸。噸。題設量

3、可總到下表：題設量可總到下表：結合存量限制和需量限制得數學模型結合存量限制和需量限制得數學模型：65432124123082412minxxxxxxf 0,54284.654321635241654321xxxxxxxxxxxxxxxxxxts m個產地個產地A1,Am聯合供應聯合供應n個銷地個銷地B1,Bn,各產各產地至各銷地單位運價地至各銷地單位運價(單位單位:元元/噸噸)為為cij，問如何調運使，問如何調運使總運費最少總運費最少?一般運輸問題一般運輸問題.:ijjixBA的的運運輸輸量量為為到到銷銷地地設設從從產產地地解解 njmixnjbxmiaxtsxcfijjmiijinjijmi

4、njijij,.,1;,.,10,.,1,.,1,.min1111總運價總運價產量限制產量限制需量限制需量限制運量非負運量非負 njmixnjbxmiaxtsxcfijjmiijinjijminjijij,.,1;,.,10,.,1,.,1,.min1111假設假設產銷平衡產銷平衡: 在很多實際問題中在很多實際問題中,解題思想和運輸問題同出一轍解題思想和運輸問題同出一轍,也就是說我們可以用運輸模型解決其他問題也就是說我們可以用運輸模型解決其他問題. njjmiiba11 設有設有n件工作件工作B1, B2, Bn,分派給分派給n人人A1, A2, An去去做做,每人只做一件工作且每件工作只派一

5、個人去做每人只做一件工作且每件工作只派一個人去做,設設Ai完成完成Bj的工時為的工時為cij,問應如何分派才能完成全部工作的問應如何分派才能完成全部工作的總工時最少總工時最少. 否則否則去做去做分派給分派給工作工作設設解解01:ijijABx ninjijijxcf11min ）（或或）（）（njixnixnjxtsijnjijniij,.,2 , 1,10,.,2 , 11,.,2 , 11.11每件工作只派每件工作只派1人人每個人只派做每個人只派做1件件變量變量xi只取只取0和和1,故建立故建立的模型也稱的模型也稱0-1規劃規劃.3. 分派問題分派問題?,1,2:),(),(),(),()

6、,(),(),(:7, 7654321的年利潤最大的年利潤最大問如何選擇地址使公司問如何選擇地址使公司元元總投資不超過總投資不超過元元每年可獲利每年可獲利元元投資投資若選若選個個漢口漢陽至少漢口漢陽至少個個武昌至多武昌至多并規定并規定漢商漢商二十一世紀二十一世紀行街行街步步武廣武廣司門口司門口亞貿亞貿中商中商個地址個地址有有擬議中擬議中漢陽建立專賣店漢陽建立專賣店漢口漢口某公司擬定在在武昌某公司擬定在在武昌bcbAAAAAAAAiii 否則否則選擇選擇解解, 0, 1:iiAx 71maxiiixcf 7,.,2 , 110112.765432171ixxxxxxxxbxbtsiiii或或4.

7、選址問題選址問題 現要做現要做100套鋼架套鋼架,用長為用長為2.9m、2.1m和和1.5m的元的元鋼各一根鋼各一根,已知原料長已知原料長7.4m,問如何下料問如何下料,使用的原材料使用的原材料最省最省?分析分析:下料方式：下料方式：最省：最省：1.所用剛架根數最少；所用剛架根數最少；2.余料最少余料最少5.下料問題下料問題原料截成所需原料截成所需長度的根數長度的根數下料方法下料方法所所需需根根長長2.9m211100002.1m021032101.5m10130234剩余料頭剩余料頭0.10.30.901.10.20.81.4:, 為為則問題的線性規劃模型則問題的線性規劃模型根數根數種辦法下

8、料的原材料的種辦法下料的原材料的表示按第表示按第設設ixi876543214 . 18 . 02 . 01 . 109 . 03 . 01 . 0minxxxxxxxxf 取整取整jjxjxxxxxxxxxxxxxxxxts;8 , 7 , 6 , 5 , 4 , 3 , 2 , 1, 0100432310023321002.876431765324321不同方不同方法截得法截得每種根每種根長的總長的總數至少數至少100例例3,4中的此例的變量中的此例的變量xi只取正整數只取正整數,故建立的模型也稱故建立的模型也稱整數規劃整數規劃.0-1規劃是整數規劃的特殊情形規劃是整數規劃的特殊情形. 某公

9、司生產某產品某公司生產某產品,最大生產能力為最大生產能力為100單位單位,每單位每單位存儲費存儲費2元元,預定的銷售量與單位成本如下預定的銷售量與單位成本如下:月份月份單位成本單位成本(元元) 銷售量銷售量1234 70 60 72 70 80 120 76 60求一生產計劃求一生產計劃,使使 1)滿足需求滿足需求; 2)不超過生產能力不超過生產能力;3)成本成本(生產成本與存儲費之和生產成本與存儲費之和)最低最低.6. 生產批量問題生產批量問題 1 je 解解:假定假定1月初無庫存月初無庫存,4月底賣完月底賣完,當月生產的不庫當月生產的不庫存存,庫存量無限制庫存量無限制.為單位成本，為存儲費

10、，為銷售量，月產量，為第：設模型iiiicedix jiijiidx11 31j 41jjjxc fmin第j+1個月的庫存量第j+1個月的庫存費共共3個月的庫存費個月的庫存費 4 ,23, 110003 , 2 , 1.414111ixdxjdxtsiiiiijijiii且為正整數且為正整數到本月總生產量到本月總生產量大于等于銷售量大于等于銷售量4個月總生產量等個月總生產量等于總銷售量于總銷售量4個月總個月總生產成本生產成本.iiiiisicedix月初的庫存量為月初的庫存量為為單位成本，設第為單位成本，設第為存儲費，為存儲費，為銷售量，為銷售量，月產量，月產量，為第為第：設：設模型模型 4

11、141miniiiiiisexcf.ts 1is, iiidxs 4 , 3 , 2 , 1 i0051 ss4321043211000，且為整數且為整數，且為整數，且為整數， isixii.,月的銷售量表示的第之和存儲費月賣出時的生產成本與月生產的產品在第第表示月賣出的數量月生產的產品在第表示第設化為運輸問題解法jdjicjixjijij月份月份單位成本單位成本(元元) 銷售量銷售量1234 70 60 72 70 80 120 76 6076827676-80-7472-747270生產月100100100100產量6041207060銷量4321321需求月費用費用cij線性規劃模型且為

12、整數且為整數0100.min41,411 ijijijjijijjjiijijxxdxtsxcf4 , 3 , 2 , 1 j4 , 3 , 2 , 1 i4 , 3 , 2 , 1, ji本問題的本問題的3個模型為整數規劃模型個模型為整數規劃模型.線性規劃模型特點 決策變量：向量(x1 xn)T ,決策人要考慮和控制的因素非負； 約束條件：線性等式或不等式； 目標函數：Z=(x1 xn) 線性式，求Z極大或極小；21一般形式一般形式 0,.minmax21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxc

13、f目標函數目標函數約約束束條條件件 矩陣形式為：矩陣形式為：記記,),(212121TnTnnmijnbbbbxxxxaAcccc 0.minxbAxtscxfL稱為約束矩陣。稱為約束矩陣。的每一分量的每一分量指指Axxxj, 00 矩陣形式矩陣形式滿足約束條件的變量的值稱為滿足約束條件的變量的值稱為可行解可行解，可行解的集合稱為可行解的集合稱為可行域可行域。使目標函數達到最大（小）值的可行解使目標函數達到最大（小）值的可行解稱為稱為最優解最優解，相應的目標函數的值稱為相應的目標函數的值稱為最優值最優值。線性規劃問題的性質: 比例性比例性 每個決策變量對目標函數以及右端項每個決策變量對目標函數

14、以及右端項的貢獻與該決策變量的取值成正比的貢獻與該決策變量的取值成正比. 可加性可加性 每個決策變量對目標函數以及右端項的每個決策變量對目標函數以及右端項的貢獻與其他決策變量的取值無關貢獻與其他決策變量的取值無關. 連續性連續性 每個決策變量的取值都是連續的每個決策變量的取值都是連續的.應 用 市場營銷市場營銷(廣告預算和媒介選擇，競爭性定價，廣告預算和媒介選擇，競爭性定價，新產品開發，制定銷售計劃新產品開發，制定銷售計劃) 生產計劃制定生產計劃制定(合理下料，配料，合理下料，配料，“生產計劃、生產計劃、庫存、勞力綜合庫存、勞力綜合”) 庫存管理庫存管理(合理物資庫存量，停車場大小，設合理物資

15、庫存量，停車場大小，設備容量備容量) 運輸問題運輸問題線性規劃模型 財政、會計財政、會計(預算，貸款，成本分析，投預算，貸款，成本分析，投資，證券管理資，證券管理) 人事人事(人員分配，人才評價，工資和獎金人員分配，人才評價，工資和獎金的確定的確定) 設備管理設備管理(維修計劃，設備更新維修計劃，設備更新) 城市管理城市管理(供水，污水管理，服務系統設供水，污水管理，服務系統設計、運用計、運用) 求解線性規劃的Matlab解法 1. Matlab解線性規劃的標準形式 x,fval = linprog(c,A1,b1,A2,b2) x,fval = linprog(c,A1,b1,A2,b2,l

16、b,ub) x,fval = linprog(c,A1,b1,A2,b2,lb,ub,x0) 沒有的加例如x=0;則lb=0,ub用代替ubxlbbxAbxAtsxcxfT2211.)(min求解線性規劃問題 編寫Matlab程序如下：c=2;3;1;a=-1,-4,-2;-3,-2,-0;b=-8;-6;x,y=linprog(c,a,b,zeros(3,1)32132 minxxxz0,62382432121321xxxxxxxx案例案例 一奶制品加工廠用牛奶生產A1,A2兩種奶制品，1桶牛奶可以在甲車間用12小時加工成3公斤A1，或者在乙車間用8小時加工成4公斤A2。根據市場需求，生產的

17、A1,A2全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元。現在加工廠每天能得到50桶牛奶的供應，每天正式工人總的勞動時間480小時，并且甲車間每天至多能加工100公斤A1，乙車間的加工能力沒有限制。試為該廠制訂一個生產計劃，使每天獲利最大，并進一步討論以下3個附加問題： 1）若用35元可以買到1桶牛奶，應否作這項投資？若投資，每天最多購買多少桶牛奶？ 2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？ 3）由于市場需求變化，每公斤A1的獲利增加到30元，應否改變生產計劃？線性規劃綜合舉例：生產計劃問題線性規劃綜合舉例：生產計劃問題2 該問題的模型為:max=7

18、2*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x135元因此可以作這方面的投資.進一步考慮,以35元一桶的牛奶擴大供應再生產,在現有資源的限制下規模可以擴大到什么程度.6、靈敏度分析:為了分析付給臨時工人的工資最多是每小時幾元？,可以將工時約束條件480改為481(相當于聘用臨時工增加一個工時),重新求最大利潤, 利潤在原來的基礎上提高一定的數值,付給臨時工人的工資理論上應不超過這個數值。約束條件480改為481以后,結果為: x = 20.2500 29.7500fval = -3.3620e+003由結果可以看出增加一個工時增加的利潤為3362-3360=2元因

19、此付給臨時工人的工資理論上應不超過2元/小時.進一步考慮,是否付給臨時工人的工資一定不超過2元/小時,條件對利潤的影響是綜合的相互的,工時的限制會限制規模的擴張,從而影響利潤的增長,因此,這種固定其他約束,改變一個約束來分析該約束對利潤的影響是有一定局限性7、靈敏度分析:目標函數的系數發生變化時（假定約束條件不變），最優解和最優值會改變嗎？這個問題不能簡單地回答。通過改變目標函數系數值求解,觀察解的變化,得到系數值允許的變化范圍：x1的系數為（64，96）；x2的系數為（48，72）。注意：x1系數的允許范圍需要x2系數64不變，反之亦然。由于目標函數的費用系數變化并不影響約束條件，因此此時最

20、優基不變可以保證最優解也不變，但最優值變化。用這個結果很容易回答附加問題3）：若每公斤A1的獲利增加到30元，則x1系數變為303=90，在允許范圍內，所以不應改變生產計劃，但最優值變為9020+6430=3720。由于市場需求變化，每公斤A1的獲利增加到32元(A2獲利不變)，或者每公斤A2的獲利增加到18元(A1獲利不變),則都應該改變生產計劃,很容易定出新的生產計劃. 2.整數規劃 定義規劃中的變量（部分或全部）限制為整數時，稱為整數規劃。若在線性規劃模型中，變量限制為整數，則稱為整數線性規劃。目前所流行的求解整數規劃的方法，往往只適用于整數線性規劃。目前還沒有一種方法能有效地求解一切整

21、數規劃 1o 變量全限制為整數時，稱純（完全）整數規劃。 2o 變量部分限制為整數的，稱混合整數規劃。 3o 變量只能取0或1時，稱之為0-1整數規劃。 （i）分枝定界法可求純或混合整數線性規劃。 （ii）割平面法可求純或混合整數線性規劃。 （iii）隱枚舉法求解“0-1”整數規劃： 過濾隱枚舉法； 分枝隱枚舉法。 （iv）匈牙利法解決指派問題（“0-1”規劃特殊情形）。 （v）蒙特卡洛法求解各種類型規劃(隨機取樣法) 特殊的整數規劃 指派問題（又稱分配問題Assignment Problem） 擬分配 人去干 項工作，每人干且僅干一項工作，若分配第 人去干第 項工作，需花費 單位時間，問應如

22、何分配工作才能使工人花費的總時間最少？nnijijcninjijijxc11min n,1,2,ji, 1 0,2,1,1,2,1,111或ijniijnjijxnjxnixij 求解下列指派問題，已知指派矩陣為 1096109532485724679278310283編寫Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5；8 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog

23、(c,a,b,zeros(25,1),ones(25,1) 2022-6-2740優化問題三要素：優化問題三要素：決策變量決策變量decision bariable；目標目標函數函數objective function；約束條件約束條件constraints約約束束條條件件決策變量決策變量優化問題的一般形式優化問題的一般形式njiDxljxgmixhtsxfopt,.,1,0)(,.,1,0)(.)(目標函數目標函數等約束等約束equality constraint不等約束不等約束inequality constraint一般優化問題概述 要解決的問題的目標可以用數值指標反要解決的問題的目標可

24、以用數值指標反映映 對于要實現的目標有多種方案可選擇對于要實現的目標有多種方案可選擇 有影響決策的若干約束條件有影響決策的若干約束條件特點一般優化問題概述可行解可行解feasible solution（滿足約束）與可行域（滿足約束）與可行域feasible region（可行解的集合）（可行解的集合）最優解最優解optimal solution（取到最小（取到最小minimum大值大值maximum的可行解的可行解,對應最優值對應最優值optimal value）局部最優解或相對最優解局部最優解或相對最優解local/relative optimizer全局或整體最優解全局或整體最優解glob

25、al optimizaer優化模型的基本類型優化模型的基本類型無約束優化無約束優化unconstrained optimization約束優化約束優化constrained optimization特殊：等式（不等式）方程組特殊：等式（不等式）方程組 system of equations(inequations)一般優化問題概述約束優化約束優化constrained optimization的簡單分類的簡單分類數學規劃數學規劃mathematical programming或連續優化或連續優化continuous optmization 線性規劃線性規劃(LP) 目標和約束均為線性函數目標和

26、約束均為線性函數 Linear programming 非線性規劃非線性規劃(NLP) 目標或約束中存在非線性函數目標或約束中存在非線性函數 Nonlinear programming 二次規劃二次規劃(QP) 目標為二次函數、約束為線性目標為二次函數、約束為線性 Quadratic programming一般優化問題概述整數規劃整數規劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數為整數Integer programming 整數整數線性線性規劃規劃(ILP)，整數，整數非線性非線性規劃規劃(INLP) 純整數規劃純整數規劃(PIP), 混合整數規劃混合整數規劃(MIP) Pure (mixed) Integer programming 一般整數規劃，一般整數規劃，0-1（整數）規劃（整數）規劃Zero-one programming離散優化離散優化discrete optimization或組合優化或組合優化combinatorial optimization一般優化問題概述MatlabMatlab優化工具箱簡介優化工具箱簡介1.MATL