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

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

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

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

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

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

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

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

8、定的LP有約束不等式線(xiàn)性規(guī)劃問(wèn)題的基本理論3.關(guān)于變量 在標(biāo)準(zhǔn)形式中,所有的變量都有非負(fù)限制,如果某些變量沒(méi)有非負(fù)限制,則稱(chēng)這些變量為自由的.兩種處理辦法:線(xiàn)性規(guī)劃問(wèn)題的基本理論線(xiàn)性規(guī)劃問(wèn)題的基本理論線(xiàn)性規(guī)劃問(wèn)題的基本理論相應(yīng)的典式如下:最優(yōu)值為5.非基可行解是最優(yōu)解，線(xiàn)性規(guī)劃問(wèn)題的基本理論 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分枝定界法線(xiàn)性規(guī)劃問(wèn)題的基本理論隱枚舉法過(guò)濾條件檢驗(yàn)可行目標(biāo)值可行檢驗(yàn)過(guò)濾檢驗(yàn)(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線(xiàn)性規(guī)劃問(wèn)題的基本理論練習(xí) 某服務(wù)部門(mén)一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定應(yīng)聘方案，即周一到周日每天聘用多少人，使在滿(mǎn)足需要的條件下聘用總?cè)藬?shù)最少 線(xiàn)性模型題目1 生產(chǎn)計(jì)劃問(wèn)題某工廠(chǎng)計(jì)劃安排生產(chǎn)，兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤(rùn)，生產(chǎn)單位產(chǎn)品所需設(shè)備臺(tái)時(shí)及A,B兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如表所示，問(wèn)：）怎么安排生產(chǎn)使得工廠(chǎng)獲利最大？）產(chǎn)品的單位利潤(rùn)降低到1.8萬(wàn)元，要不要改變生產(chǎn)計(jì)劃，如果降低到1萬(wàn)元呢？）產(chǎn)

10、品的單位利潤(rùn)增大到5萬(wàn)元，要不要改變生產(chǎn)計(jì)劃？）如果產(chǎn)品，的單位利潤(rùn)同時(shí)降低了1萬(wàn)元，要不要改變生產(chǎn)計(jì)劃？ 產(chǎn)品產(chǎn)品最大資源量設(shè)備128臺(tái)時(shí)原材料A4016kg原材料B0412kg單位產(chǎn)品利潤(rùn)23 線(xiàn)性模型建立 線(xiàn)性模型求解程序編寫(xiě)model:title 生產(chǎn)計(jì)劃問(wèn)題;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END 線(xiàn)性模型求解運(yùn)行結(jié)果 Model Title: 生產(chǎn)計(jì)劃問(wè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 對(duì)問(wèn)題1，安排是生產(chǎn)產(chǎn)品4單位，產(chǎn)品2單位，最大盈利為14萬(wàn)元 。 線(xiàn)性模型敏感性理論1目標(biāo)函數(shù)的系數(shù)變化的敏感性分析如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會(huì)影響目標(biāo)函數(shù) f 斜率的變化，但是只要f 的斜率小于等于-1/2（也就是直線(xiàn)l夾在l1與l2之間時(shí)），最優(yōu)解都在(4,2)上取到，最優(yōu)解不變，從而生產(chǎn)計(jì)劃不會(huì)變. 線(xiàn)性模型敏感性分析1要使用敏感性分析必須要在這里選擇Prices & Ra

12、nges然后保存退出路徑：LINGOOptionsGeneral Solver(通用求解程序)選項(xiàng)卡 線(xiàn)性模型敏感性分析1要調(diào)出敏感性分析的結(jié)果，必須先求解后再在程序窗口下點(diǎn)擊LINGORange， 線(xiàn)性模型敏感性分析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ù)允許增加量允許減少量對(duì)問(wèn)題2，產(chǎn)品的單位利潤(rùn)降低到1.8萬(wàn)元，在（1.5，）之間，所以不改變生產(chǎn)計(jì)劃。如果降低到1萬(wàn)元，不在（1.5，）內(nèi)，要改變生產(chǎn)計(jì)劃。在程序中將目標(biāo)函數(shù)的系數(shù)“2”改為“1”，可得新的計(jì)劃為安排是生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單

14、位，最大盈利為11萬(wàn)元.對(duì)問(wèn)題3，要改變生產(chǎn)計(jì)劃，更改程序得新計(jì)劃為生產(chǎn)產(chǎn)品2單位，產(chǎn)品3單位，最大盈利為19萬(wàn)元.對(duì)問(wèn)題4，因?yàn)閮蓚€(gè)系數(shù)同時(shí)改變了，所以只有更改程序的數(shù)據(jù)，重新運(yùn)行得：不改變生產(chǎn)計(jì)劃，但是最大利潤(rùn)降低到8萬(wàn)元. 線(xiàn)性模型敏感性理論2 線(xiàn)性模型影子價(jià)格理論把y1,y2,y3作為三種原料的定價(jià)，定價(jià)的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤(rùn)的前提下的最小利潤(rùn). 在最優(yōu)情況下，y的值就是資源的影子價(jià)格，影子價(jià)格有意義是有范圍的。影子價(jià)格經(jīng)濟(jì)含義是：在資源得到最優(yōu)配置，使總效益最大時(shí)，該資源投入量每增加一個(gè)單位所帶來(lái)總收益的增加量 線(xiàn)性模型綜合討論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 運(yùn)行結(jié)果 Model Title: 生產(chǎn)計(jì)劃問(wè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 線(xiàn)性模型題目21桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利1

17、6元/公斤 50桶牛奶 時(shí)間480小時(shí) 至多加工100公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買(mǎi)到1桶牛奶，買(mǎi)嗎？ 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：加工奶制品的生產(chǎn)計(jì)劃 線(xiàn)性模型建立x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動(dòng)時(shí)間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線(xiàn)性規(guī)劃模型(LP) 線(xiàn)性模型求解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，利潤(rùn)3360元。 線(xiàn)性模型影子價(jià)格 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元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？35 0，初始可行點(diǎn)xk,初始步長(zhǎng)k0,在xk線(xiàn)性化得線(xiàn)性規(guī)劃問(wèn)題：非線(xiàn)性規(guī)劃有約束問(wèn)題 求出此線(xiàn)性規(guī)劃問(wèn)題得最優(yōu)解xk1，檢驗(yàn)是否為原問(wèn)題的的可行解，若是轉(zhuǎn)，否則縮短步長(zhǎng)轉(zhuǎn)；判斷精度。則取最優(yōu)解x*=xk+1,停，否則令k=k+1轉(zhuǎn)。非線(xiàn)性規(guī)劃有約束問(wèn)題（2）罰函數(shù)法轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)

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

21、.5%1%(品位限制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿(mǎn)足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變?？ㄜ?chē)載重量為154噸，平均時(shí)速28km,平均卸車(chē)時(shí)間為3分鐘。問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車(chē)，分別在哪些路線(xiàn)上各運(yùn)輸多少次 ? 露天礦生產(chǎn)的車(chē)輛安排(CUMCM-2003B) 露天礦生產(chǎn)的車(chē)輛安排(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巖場(chǎng)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)的車(chē)輛安排(CUMCM-2003B)與典型的運(yùn)輸問(wèn)題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；屬

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

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

25、1變量，取1為使用；0為關(guān)閉 符號(hào)說(shuō)明（4）鏟位儲(chǔ)量約束（1）道路能力(卡車(chē)數(shù))約束（2）電鏟能力約束（3）卸點(diǎn)能力約束 模型建立優(yōu)化模型xij為非負(fù)整數(shù)fi 為0-1整數(shù)（5）產(chǎn)量任務(wù)約束（8）整數(shù)約束 （7）電鏟數(shù)量約束（6）鐵含量約束 模型建立 程序編寫(xiě)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 程序編寫(xiě)!目標(biāo)函數(shù);min=sum( cai (i): sum ( xie (j): number (j,i)*154*distance (j,i);!卡車(chē)每一條路線(xiàn)上最多可以運(yùn)行的次數(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);!每一條路線(xiàn)上的最大總車(chē)次的計(jì)算;for( link (i,j):lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j);!計(jì)算各個(gè)鏟位的總產(chǎn)量;for (cai(j): cnum(j)=sum(xie(i):number(i,j);!計(jì)算各個(gè)卸點(diǎn)的總產(chǎn)量;for (xie(i): xnum(i)=sum(cai(j):number(i,j); 程序編寫(xiě)!道路能力約束;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; !卸點(diǎn)能力約束;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); 程序編寫(xiě)!鐵含量約束;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