1、最優化方法介紹最優化方法介紹一一.運輸問題運輸問題1. 產銷平衡的運輸問題產銷平衡的運輸問題2. 產大于銷的運輸問題產大于銷的運輸問題(產銷不平衡產銷不平衡)3. 銷大于產的運輸問題銷大于產的運輸問題(產銷不平衡產銷不平衡)二二.整數規劃問題整數規劃問題1. 投資決策問題投資決策問題(0-1規劃規劃)2. 下料問題下料問題(整數規劃整數規劃)3. 工作安排問題工作安排問題(整數規劃整數規劃)4. 指派問題指派問題(0-規劃規劃)運輸問題的數學模型運輸問題的數學模型例例1.從甲城調出蔬菜從甲城調出蔬菜2000噸噸,從乙城調出蔬從乙城調出蔬菜菜1100噸噸,分別供應分別供應A地地1700噸噸,B地

2、地1100噸噸,C地地200噸噸,D地地100噸噸,每噸運費每噸運費 (元元)如下如下 A地地B地地C地地 D地地甲城甲城 2125715乙城乙城 51513715確定運費最省的調撥計劃確定運費最省的調撥計劃 .用用x11,x12,x13,x14,分別表示從甲城調往分別表示從甲城調往A,B,C,D四地四地的蔬菜量的蔬菜量;用用x21,x22,x23,x24分別表示從乙城調往分別表示從乙城調往A,B,C,D四地的蔬菜量四地的蔬菜量.總運費可以表示為總運費可以表示為f =21x11+25x12+7x13+15x14+51x21+51x2237x23+15x24約束條件約束條件:x11+x12+x1

3、3+x14=2000 x21+x22+x23+x24=1100 x11+x21=1700 x12+x22=1100 x13+x23=200 x14+x24=100 xij 0, i=1,2; j= 1,2,3,4求目標函數求目標函數 f 的極小值的極小值,且滿足六個等式且滿足六個等式約束和非負性約束的約束條件約束和非負性約束的約束條件.LINDO軟件軟件可用于求解線性規劃、整數可用于求解線性規劃、整數規劃、二次規劃問題規劃、二次規劃問題.LINDO是英文是英文 Linear, INteractive, and Discrete Optimizer的縮寫的縮寫,可譯為交互式可譯為交互式線性離散最

4、優化軟件。線性離散最優化軟件。用用LINDO求解數學規劃分兩步求解數學規劃分兩步:第一步第一步,建建立數學模型立數學模型;第二步第二步,求解數學模型求解數學模型.建立模型在模型窗口中進行建立模型在模型窗口中進行,而模型求解的而模型求解的所有數據結果只能在報告窗口中獲得所有數據結果只能在報告窗口中獲得 .LINDO的模型包括三個部分的模型包括三個部分:目標函數、變目標函數、變量和約束條件量和約束條件.目標函數前面必須有關鍵字目標函數前面必須有關鍵字“max”或或“min”.約束條件以約束條件以“subject to”開始開始,以以“end”結束結束.在在“subject to ”和和“end”之

5、間之間,輸入變量滿足的約束條件。輸入變量滿足的約束條件。如果當前窗口是模型窗口如果當前窗口是模型窗口,則可使用則可使用solve(求解求解)命令求解模型命令求解模型xij為第為第i產地到第產地到第j銷地物質運量銷地物質運量.則數學模型為則數學模型為minjijijxcf11min0. .11ijmijijnjiijxbxaxts i=1,2,m J=1,2,ni=1,m;j=1,n設有設有m個產地的產量分別為個產地的產量分別為:a1,a2,am,而有而有n個個銷地的銷量分別為銷地的銷量分別為:b1,b2,bn.已知從第已知從第i個產地個產地到第到第j個銷地的單位物質運費為個銷地的單位物質運費為

6、cij,求總運費最小求總運費最小的物質調運方案的物質調運方案.運輸問題的一般表示運輸問題的一般表示1.產地產地產量之和產量之和與銷地與銷地銷量之和銷量之和相等的運輸相等的運輸問題稱為問題稱為產銷平衡運輸問題產銷平衡運輸問題.2.約束條件數是產地數與銷地數之和約束條件數是產地數與銷地數之和m+n3.決策變量數是產地數與銷地數之積決策變量數是產地數與銷地數之積mn4. 產量之和大于銷量之和時產量之和大于銷量之和時,有有產大于銷產大于銷的運的運輸問題輸問題,其數學模型為其數學模型為minjijijxcf11min0. .11ijmijijnjiijxbxaxts i=1,2,m J=1,2,ni=1

7、,m;j=1,n5.當銷量之和大于產量之和時當銷量之和大于產量之和時,這類運輸問這類運輸問題稱為題稱為銷大于產銷大于產的運輸問題的運輸問題,其數學模型為其數學模型為minjijijxcf11min0. .11ijmijijnjiijxbxaxts i=1,2,m J=1,2,ni=1,m;j=1,n產大于銷的運輸問題與銷大于產的運輸問題產大于銷的運輸問題與銷大于產的運輸問題統稱為統稱為產銷不平衡的運輸問題產銷不平衡的運輸問題.練習題練習題某種物品先存放在兩個倉庫某種物品先存放在兩個倉庫A1和和A2中中,再運往三個使用地再運往三個使用地B1,B2,B3,其間的距離其間的距離(或單位或單位運價運價

8、),各倉庫的存量和使用地的需用量如下各倉庫的存量和使用地的需用量如下:B1B2B3產量產量A134210A23534銷量銷量356建立使總運輸量最小的運輸問題的數學模型建立使總運輸量最小的運輸問題的數學模型.整數規劃整數規劃(決策變量只能取整數的線性規劃問題決策變量只能取整數的線性規劃問題)投資決策問題投資決策問題設一年內可用于投資的總金額為設一年內可用于投資的總金額為十萬元十萬元,有五個項目可投資有五個項目可投資,假定每一項目只能假定每一項目只能投資一次投資一次,已知各項目投資金額和利潤如下已知各項目投資金額和利潤如下投資項目投資項目投資金額投資金額(元元)利潤利潤(元元)125000100

9、0210000800330000120042000010005300001800問如何選擇投資項目問如何選擇投資項目, 才能使總利潤最大才能使總利潤最大.設決策變量為設決策變量為:xj(j = 1,2,3,4,5)若對第若對第j項投資項投資,則則xj=1,否則否則xj=0.設總利潤為設總利潤為z,則數學模型為則數學模型為Max z=1000 x1+800 x2+1200 x3+1000 x4+1800 x5s. t. 25000 x1+10000 x2+30000 x3 +20000 x4+30000 x5100000 xj=0 或或 1, (j=1,2,3,4,5)因為決策變量只取因為決策變

10、量只取“0”或或“1”,所以這類所以這類問題稱為問題稱為0-1規劃問題規劃問題.使用使用LINDO軟件求解整數規劃問題時軟件求解整數規劃問題時,在建立在建立了模型之后了模型之后,還要再添加變量取整數的說明還要再添加變量取整數的說明:“0-1”規劃用規劃用: int x1, int x2, 一般的整數規劃用一般的整數規劃用:gin x1, gin x2,下料問題下料問題:某車間有長度為某車間有長度為180厘米的鋼管厘米的鋼管(數量充數量充分多分多),今要將其截為三種不同長度今要將其截為三種不同長度,長度分別為長度分別為70厘米的管料厘米的管料100根根,而而52厘米、厘米、35厘米的管料分別厘米

11、的管料分別不得少于不得少于150根根,120根根,問應采取怎樣的截法問應采取怎樣的截法,才能才能完成任務，同時使剩下的余料最少？完成任務，同時使剩下的余料最少？ 長度長度 一一二二三三四四五五六六七七八八 需需7021110000 1005202103210 1503510130235 120余余56235246235首先做技術處理首先做技術處理,所有可能的截法有下面八種所有可能的截法有下面八種:考慮八種截法的配合使用考慮八種截法的配合使用,使總的余料最少使總的余料最少.設第設第i種截法用鋼管數目為種截法用鋼管數目為xi,則目標函數為配則目標函數為配合使用各種截法的總余料之和合使用各種截法的總

12、余料之和f=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8同理同理, 由各種截法截成由各種截法截成52cm和和35cm的鋼管數以的鋼管數以及總數下限得及總數下限得2x2+x3+3x5+2x6+x7150X1+x3+3x4+2x6+3x7+5x8 120分析約束條件如下分析約束條件如下,用各種截法所截用各種截法所截72cm的鋼管的鋼管數為數為(2x1+x2+x3+x4),其總數為其總數為100,故故2x1+x2+x3+x4=100練習題練習題:用長度為用長度為500厘米的條材厘米的條材,分別截成分別截成長度為長度為98厘米與厘米與78厘米的兩種毛壞厘米的兩種毛壞,要求截要求

13、截出長出長98厘米的毛坯共厘米的毛坯共1000根根,78厘米的毛坯厘米的毛坯共共2000根根,問怎樣截法問怎樣截法,才能使所用的原材才能使所用的原材料最少料最少,試建立數學模型。試建立數學模型。 下料問題的數學模型下料問題的數學模型Min f=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8s.t. 2x1+x2+x3+x4=100 2x2+x3+3x5+2x6+x7 150 x1+x3+3x4+2x6+3x7+5x8 120 xj 0, (j=1,2,3,8)工作安排問題工作安排問題:某服務部門各時段某服務部門各時段(每每2小時為一小時為一時段時段)需要的服務人員數如下需

14、要的服務人員數如下時段時段:12345678人數要求人數要求: 10891113853按規定按規定,服務員連續工作服務員連續工作8小時小時(4個時段個時段)為一班為一班.試安排服務員的工作時間試安排服務員的工作時間,使服務部門服務員總使服務部門服務員總數最少數最少.設在第設在第j時段開始時上班的服務員人數為時段開始時上班的服務員人數為xj.由于由于第第j時段開始時上班的服務員將在第時段開始時上班的服務員將在第j+3時段結時段結束時下班束時下班,故決策變量只需要考慮故決策變量只需要考慮x1,x2,x3,x4,x5.目標函數為目標函數為:z = x1+ x2+ x3+ x4+ x5約束條件為各時段

15、開始時對人數的最少要求約束條件為各時段開始時對人數的最少要求:x110 x1+x2 8x1+x2+x3 9x1+x2+x3+x4 11x2+x3+x4+x5 13x3+x4+x5 8x4+x5 5x5 3x1,x2,x3,x4 ,x50且且x1,x2,x3,x4 ,x5皆為整數皆為整數.指派問題指派問題:某商業公司計劃建五家新商店某商業公司計劃建五家新商店.為了為了盡早建成營業盡早建成營業,商業公司決定由商業公司決定由5家建筑公司分家建筑公司分別承建別承建.已知建筑公司已知建筑公司Ai(I=1,2,5)對新商店對新商店Bj(j=1,2,5)的建造費用報價的建造費用報價(萬元萬元)如下如下:商業

16、公司應怎樣分派商業公司應怎樣分派, 才能使總的建造費用最少才能使總的建造費用最少.B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106設決策變量為設決策變量為0-1 變量變量xij,當當Ai承建承建Bj時時,xij取值為取值為1,否則取值為否則取值為0數學模型數學模型:Min z=4x11+8x12+7x13+15x14+12x15+ 6x51+9x52+12x53+10 x54+6x55)5, 2, 1(1)5, 2, 1(1. .5151ixjxtSjijiijxij=0 或或 1 (i, j=1,2,5)練習題：食譜問題練習題：食

17、譜問題一飼養場飼養供實驗用的動物一飼養場飼養供實驗用的動物,已知動物生長對飼料中的三種營養成分已知動物生長對飼料中的三種營養成分:蛋白質、礦蛋白質、礦物質和維生素特別敏感物質和維生素特別敏感,每個動物每天至少需要蛋白每個動物每天至少需要蛋白質質70克克,礦物質礦物質3克克,維生素維生素10毫克毫克,該場能搞到五種飼該場能搞到五種飼料料,每種飼料每種飼料10千克的成本如下千克的成本如下: 飼料飼料: A1 A2 A3 A4 A5成本（元）：成本（元）：2 7 4 3 5每一千克飼料中所含的營養成分如下表：每一千克飼料中所含的營養成分如下表：飼料飼料 蛋白質蛋白質(克克) 礦物質礦物質(克克) 維

18、生素維生素(毫克毫克) A1 5A2 2.00.050.10A3 1.000.020.02 A4 0.600.200.20A5 1.80.051.8確定既能滿足動物需要確定既能滿足動物需要,又使總成本為最低的飼料配方又使總成本為最低的飼料配方 實際問題中實際問題中的優化模型的優化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標函數目標函數gi(x) 0約束條件約束條件數學規劃數學規劃線性規劃線性規劃(LP)二次規劃二次規劃(QP)非線性規劃非線性規劃(NLP)純整數規劃純整數規劃(PIP)混合整數

19、規劃混合整數規劃(MIP)整數規劃整數規劃(IP)0-1整數規劃整數規劃一般整數規劃一般整數規劃連續規劃連續規劃美國芝加哥美國芝加哥(Chicago)大學的大學的Linus Schrage教授于教授于1980年前后開發年前后開發, 后來成立后來成立 LINDO系統公司（系統公司（LINDO Systems Inc.），）， 網址：網址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Ap

20、plication Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示演示(試用試用)版、學生版、高級版、超級版、工業版、版、學生版、高級版、超級版、工業版、擴展版擴展版 （求解（求解問題規模問題規模和和選件選件不同）不同） LINGO LINDO優化模型優化模型線性規劃線性規劃(LP)非線性規劃非線性規劃(NLP)二次規劃二次規劃(QP)連續優化連續優化整數規劃整數規劃(IP) LP QP NLP IP 全局優化全局優化(選選) ILP IQP INLP LINDO/LINGO預處理程序預處理程

21、序線性優化求解程序線性優化求解程序非線性優化求解程序非線性優化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數確定常數2. 識別類型識別類型1. 單純形算法單純形算法2. 內點算法內點算法(選選)1、順序線性規劃法、順序線性規劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點搜索、多點搜索(Multistart) (選選) 1、盡量使用實數優化，減少整數約束和整數變量盡量使用實數優化，減少整數約束和整數變量2、盡量使用光滑優化，減少非光滑約束的個數盡量使用光滑優化，減少非光滑約束的個數 如：盡量少使用絕對值、符號函數、多個變量求如：盡量少使用絕對值、符號函數

22、、多個變量求最大最大/最小值、四舍五入、取整函數等最小值、四舍五入、取整函數等3、盡量使用線性模型，減少非線性約束和非線性變盡量使用線性模型，減少非線性約束和非線性變量的個數量的個數 （如（如x/y 5 改為改為x5y）4、合理設定變量上下界，盡可能給出變量初始值合理設定變量上下界，盡可能給出變量初始值 5、模型中使用的參數數量級要適當模型中使用的參數數量級要適當 (如小于如小于103)1、LINDO: 正確閱讀求解報告（尤其要掌握敏感性分析）正確閱讀求解報告（尤其要掌握敏感性分析）2、LINGO： 掌握集合掌握集合(SETS)的應用；的應用；正確閱讀求解報告；正確閱讀求解報告；正確理解求解狀

23、態窗口；正確理解求解狀態窗口； 學會設置基本的求解選項學會設置基本的求解選項(OPTIONS) ； 掌握與外部文件的基本接口方法掌握與外部文件的基本接口方法LINGO軟件簡介軟件簡介目標與約束段目標與約束段 集合段（集合段（SETS ENDSETS） 數據段（數據段（DATA ENDDATA）初始段（初始段（INIT ENDINIT）LINGO模型的構成：模型的構成：4個段個段LINGO模型的優點模型的優點包含了包含了LINDO的全部功能的全部功能提供了靈活的編程語言（矩陣生成器）提供了靈活的編程語言（矩陣生成器）某公司有某公司有6個建筑工地，位置坐標為個建筑工地，位置坐標為(ai, bi)

24、(單位：公里單位：公里),水泥日用量水泥日用量di (單位：噸）單位：噸）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)現有 2 料場，位于 A (5, 1), B (2, 7),記(xj,yj),j=1,2, 日儲量 ej各有 20 噸。假設：假設：料場料場和工地之間和工地之間有直線道路有直線道路目標：制定每天的供應計劃，即從 A, B 兩料場分別向各工地運送多少噸水泥，使總的噸公里數最小。用例中數據計算，最優解為i 1 2 3 4 5 6 1 ic（料料場場 A） 3 5 0 7 0 1 2ic（料料場場 B） 0 0 4 0 6

25、 10 2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規劃模型線性規劃模型決策變量：決策變量：ci j (料場料場j到到工地工地i的的運量）運量）12維維2）改建兩個新料場，需要確定新料場位置）改建兩個新料場，需要確定新料場位置(xj,yj)和和運量運量cij ，在其它條件不變下使總噸公里數最小。，在其它條件不變下使總噸公里數最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij決策變量：決策變量：ci j，(xj,yj)16維維

26、非線性規劃模型非線性規劃模型LINGO模型的構成：模型的構成：4個段個段集合段（集合段（SETS ENDSETS）數據段（數據段（DATA ENDDATA）初始段（初始段（INIT ENDINIT） 目標與目標與約束段約束段 局部最優：局部最優：89.8835(噸公里噸公里 ) LP：移到數據段：移到數據段 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素過濾法元素過濾法 直接列舉法直接列舉法 隱式列舉法隱式列舉法setname /member_list/ : attribute_list;setname(parent_set_lis

27、t) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS類型類型隱式列舉格式隱式列舉格式示例示例示例集合的元素示例集合的元素數字型數字型 1.n1.51, 2, 3, 4, 5字符字符-數字型數字型stringM.stringNCar1

28、01.car208Car101, car102, , car208星期型星期型 dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型月份型 monthM.monthNOCT.JANOCT, NOV, DEC, JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001, JAN2002優先級優先級運算符運算符最高最高#NOT# （負號）（負號）* /+ （減法）（減法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低最低(=)三類運算符

29、：三類運算符： 算術運算符算術運算符 邏輯運算符邏輯運算符 關系運算符關系運算符四個集合循環函數：四個集合循環函數：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_list);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( I): constraints SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1);FO

30、R(PAIRS( I, J): BIN( MATCH( I, J);MAXB=MAX(PAIRS( I, J): BENEFIT( I, J);MINB=MIN(PAIRS( I, J): BENEFIT( I, J);Example:PAIRSJIJIMATCHJIBENEFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCHSolver Type:B-and-BGlobal MultistartModel Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal Optim

31、umFeasibleInfeasibleUnboundedInterruptedUndetermined7 7個選項卡個選項卡( (可設置可設置80-9080-90個控制參數個控制參數) ) 程序與數據分離程序與數據分離文文本本文文件件使用外部數據文件使用外部數據文件 Cut (or Copy) Paste 方法方法 FILE 輸入數據、輸入數據、TEXT輸出數據（文本文件）輸出數據（文本文件） OLE函數與電子表格軟件（如函數與電子表格軟件（如EXCEL）連接）連接 ODBC函數與數據庫連接函數與數據庫連接 LINGO命令腳本文件命令腳本文件 LG4 （LONGO模型文件）模型文件） LNG

32、 （LONGO模型文件）模型文件） LTF （LONGO腳本文件）腳本文件） LDT （LONGO數據文件）數據文件） LRP （LONGO報告文件）報告文件）常用文件后綴常用文件后綴FILEFILE和和TEXTTEXT：文本文件輸入輸出：文本文件輸入輸出MODEL:SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt);ENDSETSMIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) NEED( I);

33、CON2 SHIP( I) SUPPLY( I);DATA: MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATAEND mydata.xls文件中必須有下列名稱(及數據)： CITIES， COST，NEED，SUPPLY，SOLUTION 在在EXCEL中還可以通過中還可以通過“宏宏”自動調用自動調用LINGO(略略) 也可以將也可以將EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示 M

34、ydataExample.lg4ODBC ODBC ：與數據庫連接：與數據庫連接輸入基本集合元素：輸入基本集合元素：setname/ODBC(datasource , tablename , columnname)/輸入派生集合元素：輸入派生集合元素：setname/ODBC(source,table , column1, column2)/目前支持下列目前支持下列DBMS: (如為其他數據庫，則需自行安裝驅動如為其他數據庫，則需自行安裝驅動)ACCESS， DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQL SERVER， TEXE FILES使用數據庫之前，數據源需

35、要在使用數據庫之前，數據源需要在ODBC管理器注冊管理器注冊輸入數據：輸入數據：Attr_list=ODBC(source,table , column1, column2)輸出數據：輸出數據：ODBC(source,table , column1, column2)= Attr_list具體例子略具體例子略建模實例與求解建模實例與求解最短路問題最短路問題下料問題下料問題露天礦的運輸問題露天礦的運輸問題鋼管運輸問題鋼管運輸問題最短路問題最短路問題求各點到求各點到T的最短路的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4jijAjiiLcL)

36、,(min露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數的為礦石，否則為巖石。每個鏟位的礦石、巖石數量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘卡車在等待時所耗費的能量也是相當可觀的，原則上卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時在安排時不應發生卡車等待不應發生卡車等待的情況。的情況。 露天礦生產的車輛安排露天礦生產的車輛安排(CUMCM-2

37、003B) 礦石卸點需要的鐵含量要求都為礦石卸點需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個班次（制），搭配量在一個班次（8小時）內滿足品位限制即小時）內滿足品位限制即可。卸點在一個班次內不變。卡車載重量為可。卸點在一個班次內不變。卡車載重量為154噸，平噸，平均時速均時速28km,平均卸車時間為平均卸車時間為3分鐘。分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次卡車，分別在哪些路線上各運輸多少次 ?問題數據問題數據 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦

38、石漏5.202.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.710.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量1251101351051151351051

39、15135125鐵含量30%28%29%32%31%33%32%31%33%31%問題分析問題分析 與典型的運輸問題明顯有以下不同：與典型的運輸問題明顯有以下不同：這是運輸礦石與巖石兩種物資的問題；這是運輸礦石與巖石兩種物資的問題；屬于產量大于銷量的不平衡運輸問題；屬于產量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；為了完成品位約束，礦石要搭配運輸；產地、銷地均有單位時間的流量限制；產地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，運輸車輛只有一種，每次滿載運輸，154噸噸/車次；車次；鏟位數多于鏟車數意味著要最優的選擇不多于鏟位數多于鏟車數意味著要最優的選擇不

40、多于7個個產地作為最后結果中的產地；產地作為最后結果中的產地；1. 最后求出各條路線上的派出車輛數及安排。最后求出各條路線上的派出車輛數及安排。近似處理：近似處理：先求出產位、卸點每條線路上的運輸量先求出產位、卸點每條線路上的運輸量(MIP模型模型)然后求出各條路線上的派出車輛數及安排然后求出各條路線上的派出車輛數及安排v卡車在一個班次中不應發生等待或熄火后再啟動卡車在一個班次中不應發生等待或熄火后再啟動的情況；的情況；v在鏟位或卸點處由兩條路線以上造成的沖突問題在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務，就認面前，我們認為只要平均時間能完成任務，就認為不沖

41、突。我們不排時地進行討論；為不沖突。我們不排時地進行討論；v空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大；v卡車可提前退出系統，等等。卡車可提前退出系統，等等。如理解為嚴格不等待，難以用數學規劃模型來解如理解為嚴格不等待，難以用數學規劃模型來解 個別參數隊找到了可行解個別參數隊找到了可行解 （略）（略）vxij ：從：從i鏟位到鏟位到j號卸點的石料運量號卸點的石料運量 （車）（車） 單位：單位： 噸；噸；vcij ：從：從i號鏟位到號鏟位到j號卸點的距離號卸點的距離 公里；公里；vTij :從從i號鏟位到號號鏟位到號j卸點路線上運行一個周期平均時間卸點路線上運行一個周期平均時間 分；分；vAij ：從：從i號鏟位到號鏟位到j號卸點最多能同時運行的卡車數號卸點最多能同時運行的卡車數 v輛；輛；vBij ：從：從i號鏟位到號鏟位到j號卸點路線上一輛車最多可運行的次數號卸點路線上一輛車最多可運行的次數 v 次；次；vpi：i號鏟位的礦石鐵含量號鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) %vqj : j號卸點任務需求，號卸點任務需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸vcki ：