2010年東大暑期建模培訓(xùn)課件優(yōu)化方法7月30日

1、優(yōu)化問題的建模方法優(yōu)化專題一線性規(guī)劃模型二非線性規(guī)劃模型三動態(tài)規(guī)劃生產(chǎn)計劃問題線性規(guī)劃模型 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2 求最大利潤三種材料量的限制生產(chǎn)量非負線性規(guī)劃模型運輸問題線性規(guī)劃模型解：設(shè)A1,A2調(diào)運到三個糧站的大米分別為x1，x2， x3， x4， x5， x6噸。題設(shè)量可總到下表：線性規(guī)劃模型結(jié)合存量限制和需量限制得數(shù)學(xué)模型：線性規(guī)劃模型 m個產(chǎn)地A1,Am聯(lián)合供應(yīng)n個銷地B1,Bn,各產(chǎn)地至各銷地單位運價(單位:元/噸)為cij，問如何調(diào)運使總運費最少?一般運輸問題總運價產(chǎn)量限制需量限制運量非負線性規(guī)劃模型

2、假設(shè)產(chǎn)銷平衡: 在很多實際問題中,解題思想和運輸問題同出一轍,也就是說我們可以用運輸模型解決其他問題.線性規(guī)劃模型 設(shè)有n件工作B1, B2, Bn,分派給n人A1, A2, An去做,每人只做一件工作且每件工作只派一個人去做,設(shè)Ai完成Bj的工時為cij,問應(yīng)如何分派才能完成全部工作的總工時最少.每件工作只派1人每個人只派做1件變量xi只取0和1,故建立的模型也稱0-1規(guī)劃.分派問題線性規(guī)劃模型選址問題線性規(guī)劃模型 現(xiàn)要做100套鋼架,用長為2.9m、2.1m和1.5m的元鋼各一根,已知原料長7.4m,問如何下料,使用的原材料最省?分析:下料方式：最省：1.所用剛架根數(shù)最少；2.余料最少下料

3、問題線性規(guī)劃模型原料截成所需長度的根數(shù)下料方法所需根長2.9m211100002.1m021032101.5m10130234剩余料頭0.10.30.901.10.20.81.4線性規(guī)劃模型不同方法截得每種根長的總數(shù)至少100例3,4中的此例的變量xi只取正整數(shù),故建立的模型也稱整數(shù)規(guī)劃.0-1規(guī)劃是整數(shù)規(guī)劃的特殊情形.線性規(guī)劃模型 某公司生產(chǎn)某產(chǎn)品,最大生產(chǎn)能力為100單位,每單位存儲費2元,預(yù)定的銷售量與單位成本如下:月份單位成本(元) 銷售量1234 70 60 72 70 80 120 76 60求一生產(chǎn)計劃,使 1)滿足需求; 2)不超過生產(chǎn)能力;3)成本(生產(chǎn)成本與存儲費之和)最低

4、.階段生產(chǎn)問題線性規(guī)劃模型 解:假定1月初無庫存,4月底買完,當(dāng)月生產(chǎn)的不庫存,庫存量無限制.第j+1個月的庫存量第j+1個月的庫存費共3個月的庫存費到本月總生產(chǎn)量大于等于銷售量4個月總生產(chǎn)量等于總銷售量4個月總生產(chǎn)成本線性規(guī)劃模型線性規(guī)劃模型月份單位成本(元) 銷售量1234 70 60 72 70 80 120 76 60線性規(guī)劃模型76827676-80-7472-747270生產(chǎn)月100100100100產(chǎn)量6041207060銷量4321321需求月費用cij線性規(guī)劃模型本題3個模型為整數(shù)規(guī)劃模型.線性規(guī)劃模型線性規(guī)劃模型特點決策變量：向量(x1 xn)T ,決策人要考慮和控制的因素

5、非負；約束條件：線性等式或不等式；目標(biāo)函數(shù)：Z=(x1 xn) 線性式，求Z極大或極??；線性規(guī)劃模型一般形式目標(biāo)函數(shù)約束條件線性規(guī)劃模型矩陣形式線性規(guī)劃模型滿足約束條件的變量的值稱為可行解，可行解的集合稱為可行域。使目標(biāo)函數(shù)達到最大（?。┲档目尚薪夥Q為最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)的值稱為最優(yōu)值。線性規(guī)劃模型線性規(guī)劃問題的性質(zhì):比例性 每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻與該決策變量的取值成正比.可加性 每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻與其他決策變量的取值無關(guān).連續(xù)性 每個決策變量的取值都是連續(xù)的.線性規(guī)劃模型應(yīng) 用市場營銷(廣告預(yù)算和媒介選擇，競爭性定價，新產(chǎn)品開發(fā)，制定銷售計劃)生產(chǎn)計劃制

6、定(合理下料，配料，“生產(chǎn)計劃、庫存、勞力綜合”)庫存管理(合理物資庫存量，停車場大小，設(shè)備容量)運輸問題財政、會計(預(yù)算，貸款，成本分析，投資，證券管理)人事(人員分配，人才評價，工資和獎金的確定)設(shè)備管理(維修計劃，設(shè)備更新)城市管理(供水，污水管理，服務(wù)系統(tǒng)設(shè)計、運用)線性規(guī)劃模型線性規(guī)劃問題的基本理論用圖解法求解線性規(guī)劃問題是一簇斜率為-5/2的平行直線族斜率為-2C/2為直線與y軸的交點x10 x28443x240 x1834如圖所示: 顯然直線向右上移動時，與y軸交點越高，從而c/2越大，使得目標(biāo)函數(shù)值c 越大。線性規(guī)劃問題的基本理論從上述幾何直觀可看出：線性規(guī)劃問題的任意兩個可行

7、解聯(lián)線上的點都是可行解；線性規(guī)劃問題的任意兩個最優(yōu)解聯(lián)線上的點都是最優(yōu)解；線性規(guī)劃問題的最優(yōu)值若存在，則一定在某個頂點達到。線性規(guī)劃問題的基本理論任何一個線性規(guī)劃問題都可以化為標(biāo)準(zhǔn)形式，我們的求解方法都是針對標(biāo)準(zhǔn)形式的。線性規(guī)劃問題的基本理論標(biāo)準(zhǔn)形式:如果給定的LP問題是極大化問題,即可化為極小化問題約束條件不變,其最優(yōu)解是一致的,但目標(biāo)函數(shù)值的符號相反.則:結(jié)論:如果問題是求目標(biāo)函數(shù)的最大值,則化為求 f 的最小值;1.關(guān)于目標(biāo)函數(shù)線性規(guī)劃問題的基本理論2.關(guān)于約束條件(1) 如果給定的LP有約束不等式線性規(guī)劃問題的基本理論注意:新引入的變量在目標(biāo)函數(shù)和約束條件中的系數(shù)均為0.(2) 如果給

8、定的LP有約束不等式線性規(guī)劃問題的基本理論3.關(guān)于變量 在標(biāo)準(zhǔn)形式中,所有的變量都有非負限制,如果某些變量沒有非負限制,則稱這些變量為自由的.兩種處理辦法:線性規(guī)劃問題的基本理論線性規(guī)劃問題的基本理論線性規(guī)劃問題的基本理論相應(yīng)的典式如下:最優(yōu)值為5.非基可行解是最優(yōu)解，線性規(guī)劃問題的基本理論 1 2 3 4 5 6 7 8 96 5 4 3 2 1（2.25，3.75） 1 2 3 4 5 6 7 8 96 5 4 3 2 1分枝定界法線性規(guī)劃問題的基本理論隱枚舉法過濾條件檢驗可行目標(biāo)值可行檢驗過濾檢驗(0,0,0) 0(0,0,1) 55(0,1,0) - 2(0,1,1) 3(1,0,0)

9、 3(1,0,1) 88（最優(yōu)）(1,1,0) 1(1,1,1) 6線性規(guī)劃問題的基本理論練習(xí) 某服務(wù)部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定應(yīng)聘方案，即周一到周日每天聘用多少人，使在滿足需要的條件下聘用總?cè)藬?shù)最少 線性模型題目1 生產(chǎn)計劃問題某工廠計劃安排生產(chǎn)，兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備臺時及A,B兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的定額如表所示，問：）怎么安排生產(chǎn)使得工廠獲利最大？）產(chǎn)品的單位利潤降低到1.8萬元，要不要改變生產(chǎn)計劃，如果降低到1萬元呢？）產(chǎn)

10、品的單位利潤增大到5萬元，要不要改變生產(chǎn)計劃？）如果產(chǎn)品，的單位利潤同時降低了1萬元，要不要改變生產(chǎn)計劃？ 產(chǎn)品產(chǎn)品最大資源量設(shè)備128臺時原材料A4016kg原材料B0412kg單位產(chǎn)品利潤23 線性模型建立 線性模型求解程序編寫model:title 生產(chǎn)計劃問題;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END 線性模型求解運行結(jié)果 Model Title: 生產(chǎn)計劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or

11、Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 對問題1，安排是生產(chǎn)產(chǎn)品4單位，產(chǎn)品2單位，最大盈利為14萬元 。 線性模型敏感性理論1目標(biāo)函數(shù)的系數(shù)變化的敏感性分析如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會影響目標(biāo)函數(shù) f 斜率的變化，但是只要f 的斜率小于等于-1/2（也就是直線l夾在l1與l2之間時），最優(yōu)解都在(4,2)上取到，最優(yōu)解不變，從而生產(chǎn)計劃不會變. 線性模型敏感性分析1要使用敏感性分析必須要在這里選擇Prices & Ra

12、nges然后保存退出路徑：LINGOOptionsGeneral Solver(通用求解程序)選項卡 線性模型敏感性分析1要調(diào)出敏感性分析的結(jié)果，必須先求解后再在程序窗口下點擊LINGORange， 線性模型敏感性分析1Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.

13、000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 當(dāng)前變量系數(shù)允許增加量允許減少量對問題2，產(chǎn)品的單位利潤降低到1.8萬元，在（1.5，）之間，所以不改變生產(chǎn)計劃。如果降低到1萬元，不在（1.5，）內(nèi)，要改變生產(chǎn)計劃。在程序中將目標(biāo)函數(shù)的系數(shù)“2”改為“1”，可得新的計劃為安排是生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單

14、位，最大盈利為11萬元.對問題3，要改變生產(chǎn)計劃，更改程序得新計劃為生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單位，最大盈利為19萬元.對問題4，因為兩個系數(shù)同時改變了，所以只有更改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計劃，但是最大利潤降低到8萬元. 線性模型敏感性理論2 線性模型影子價格理論把y1,y2,y3作為三種原料的定價，定價的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤. 在最優(yōu)情況下，y的值就是資源的影子價格，影子價格有意義是有范圍的。影子價格經(jīng)濟含義是：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量 線性模型綜合討論Ranges in which the bas

15、is is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8

16、.000000 TIME 12.00000 INFINITY 4.000000 運行結(jié)果 Model Title: 生產(chǎn)計劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 線性模型題目21桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利1

17、6元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？ 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？ 每天：加工奶制品的生產(chǎn)計劃 線性模型建立x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負約束 線性規(guī)劃模型(LP) 線性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1)

18、3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元。 線性模型影子價格 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1

19、 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可買到1桶牛奶，要買嗎？35 0，初始可行點xk,初始步長k0,在xk線性化得線性規(guī)劃問題：非線性規(guī)劃有約束問題 求出此線性規(guī)劃問題得最優(yōu)解xk1，檢驗是否為原問題的的可行解，若是轉(zhuǎn)，否則縮短步長轉(zhuǎn)；判斷精度。則取最優(yōu)解x*=xk+1,停，否則令k=k+1轉(zhuǎn)。非線性規(guī)劃有約束問題（2）罰函數(shù)法轉(zhuǎn)化為無約束最優(yōu)化問

20、題：M為足夠大的正數(shù)。稱為罰因子。算法分析：設(shè)可行域為S，構(gòu)造函數(shù)：非線性規(guī)劃有約束問題 求無約束問題得最優(yōu)解為X(M),直觀看出，只有當(dāng)X(M) S才可能真正取得極小值，若就加大罰因子M，使X(M) 向S逼近，當(dāng)M時，點列非線性規(guī)劃有約束問題計算步驟：（第k次迭代）非線性規(guī)劃有約束問題 露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘。 卡車在等待時所耗費的能量也是相當(dāng)可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。 礦石卸點需要的鐵含量要求都為29

21、.5%1%(品位限制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平均時速28km,平均卸車時間為3分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次 ? 露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 露天礦生產(chǎn)的車輛安排(CUMCM-2003B)距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614

22、.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31% 露天礦生產(chǎn)的車輛安排(CUMCM-2003B)與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；屬

23、于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排 問題分析卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認(rèn)為只要平均時間能完成任務(wù)，就認(rèn)為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。

24、 模型假設(shè)(近似)xij ：從i鏟位到j(luò)號卸點的石料運量 （車） 單位： 輛；cij ：從i號鏟位到j(luò)號卸點的距離 公里；Tij :從i號鏟位到j(luò)號卸點路線上運行一個周期平均時間 分；Aij ：從i號鏟位到j(luò)號卸點最多能同時運行的卡車數(shù) 輛；Bij ：從i號鏟位到j(luò)號卸點路線上一輛車最多可運行的次數(shù) 次；pi：i號鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j號卸點任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸cki ：i號鏟位的鐵礦石儲量 萬噸cyi ：i號鏟位的巖石儲量 萬噸fi :描述第i號鏟位是否使用的0-

25、1變量，取1為使用；0為關(guān)閉 符號說明（4）鏟位儲量約束（1）道路能力(卡車數(shù))約束（2）電鏟能力約束（3）卸點能力約束 模型建立優(yōu)化模型xij為非負整數(shù)fi 為0-1整數(shù)（5）產(chǎn)量任務(wù)約束（8）整數(shù)約束 （7）電鏟數(shù)量約束（6）鐵含量約束 模型建立 程序編寫model:title CUMCM-2003B-01;sets:cai / 1.10 /:crate,cnum,cy,ck,flag;xie / 1 . 5 /:xsubject,xnum;link( xie,cai ):distance,lsubject,number,che,b;endsetsdata:crate=30 28 29 3

26、2 31 33 32 31 33 31;xsubject= 1.2 1.3 1.3 1.9 1.3 ;distance= 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62

27、 1.27 0.50;cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25; enddata 程序編寫!目標(biāo)函數(shù);min=sum( cai (i): sum ( xie (j): number (j,i)*154*distance (j,i);!卡車每一條路線上最多可以運行的次數(shù);for (link (i,j):b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)-1)*5)

28、/(distance(i,j)/28*60*2+3+5);!每一條路線上的最大總車次的計算;for( link (i,j):lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j);!計算各個鏟位的總產(chǎn)量;for (cai(j): cnum(j)=sum(xie(i):number(i,j);!計算各個卸點的總產(chǎn)量;for (xie(i): xnum(i)=sum(cai(j):number(i,j); 程序編寫!道路能力約束;for (link (i,j): number(i,j)=lsubject(i,j);!電鏟能力約束;for

29、(cai (j) : cnum(j) = flag(j)*8*60/5 );!電鏟數(shù)量約束 - added by Xie Jinxing, 2003-09-07;sum(cai(j): flag(j) ) =7; !卸點能力約束;for (xie (i): xnum (i)=8*20);!鏟位產(chǎn)量約束;for (cai (i): number(1,i)+number(2,i)+number(5,i)=ck(i)*10000/154);for (cai (i): number(3,i)+number(4,i)= xsubject (i)*10000/154); 程序編寫!鐵含量約束;sum(cai (j): number(1,j)*(crate(j)-30.5) )=0;sum(cai (j): number(2,j)*(crate(j)-30.5) )=0;sum(cai (j): number(5,j)*(crate(j)-30.5) )=0;sum(c