数学建模讲座优化建模与LINGO优化软件课件.ppt

1、数学建模讲座数学建模讲座优化建模与优化建模与LINGO优化软件优化软件例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 Lingo 基 础nLingo 程序nMIN=-2*X1-6*X2+X1*X1-2*X1*X2+2*X1*X1;nX1+X2=2;n-X1+2*X2=2;Lingo 基 础n计算结果nObjective value:-9.777778nX1 =0.6666667 X2 =1.333333 Lingo 基 础n例例2)12424()(22122211xxxxxexfx x1+x2=0 s

2、.t.1.5+x1x2-x1-x2 0 -x1x2 10 0 Lingo 基 础nLingo程序nmin=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1);nx1+x2=0;n1.5+x1*x2-x1-x2=0;n-x1*x2-10=0;nfree(x1);nfree(x2);Lingo 基 础n计算结果nObjective value:5.276848nX1 =1.224745 nX2 =-1.224745n这是局部最优值 Lingo 基 础Lingo菜单中Options，选Global Solver，在Use Global Solver 中打钩，再次计算。O

3、bjective value:1.156627X1=-3.162278 X2=3.162278 Lingo 基 础例三2,1,6,.,1,.)()(min612121612/122 jecidctsbyaxcjijiiijjjiijijijLingo 基 础n例三中,x,y,e是一维数组，长度为2，a,b,d 也是一维数组，长度为6，c是二维数组（62矩阵）nLingo中如何定义它们？Lingo 基 础nLingo 程序 example3_2nsets:ndemand/1.6/:a,b,d;nsupply/1.2/:x,y,e;nlink(demand,supply):c;nendsetsnd

4、ata:na=1.25,8.75,0.5,5.75,3,7.25;nb=1.25,0.75,4.75,5,6.5,7.75;nd=3,5,4,7,6,11;e=20,20;nenddata Lingo 基 础ninit:nx,y=5,1,2,7;nendinit min=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i););for(supply(i):sum(demand(j):c(j,i)=e(i););n f o r(s u p p l y:b n d(0.5

5、,X,8.7 5);bnd(0.75,Y,7.75););nEND Lingo 基 础n计算结果为n Objective value:89.88349模型的集部分模型的集部分nL I N G O 有 两 种 类 型 的 集：原 始 集原 始 集(primitiveset)和派生集派生集(derived set)。n一个原始集是由一些最基本的对象组成的。n一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。n定义一个原始集，用下面的语法：nsetname/member_list/:attribute_list;n注意：用“”表示该部分内容可选。nMember_list

6、是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们 模型的数据部分模型的数据部分 n数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。数据部分的未知数值数据部分的未知数值 n有时只想为一个集的部分成员的某个属性指定值，而让其余成员的该属性保持未知，以便让LINGO去求出它们的最优值。在数据声明中输入两个相连的逗号表示该位置对应的集成员的属性值未知。两个逗号间可以有空格 数据部分的未知数值数据部分的未知数值nsets:n years/1.5/:capaci

7、ty;nendsetsndata:n capacity=,34,20,;nenddatan属性capacity的第2个和第3个值分别为34和20，其余的未知 模型的初始部分模型的初始部分n一个初始部分以“init:”开始，以“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同。模型的初始部分模型的初始部分ninit:nx,y=5,1,2,7;nendinitLINGO函数函数 n基本运算符n数学函数n金融函数n概率函数n变量界定函数n集操作函数n集循环函数n数据输入输出函数n辅助函数 算术运算符算术运算符 n乘方n乘n除n加n减逻辑运算符逻辑运算符 n#not#n#eq#

8、n#ne#n#gt#n#ge#n#lt#n#le#and#or#关系运算符关系运算符 nLINGO有三种关系运算符：“=”、“=”。nLINGO并不支持严格小于和严格大于关系运算符。然而，如果需要严格小于和严格大于关系，比如让A严格小于B：AB，那么可以把它变成如下的小于等于表达式：A+=B，数学函数数学函数 nabs(x)sin(x)cos(x)tan(x)exp(x)nlog(x)nlgm(x)返回x的gamma函数的自然对数sign(x)如果x0返回-1；否则，返回1n f l o o r(x)返 回 x 的 整 数 部 分。smax(x1,x2,xn)n smin(x1,x2,xn)变

9、量界定函数变量界定函数 nbin(x)限制x为0或1nbnd(L,x,U)限制LxUnfree(x)取消对变量x的默认下界为0的限制，即x可以取任意实数ngin(x)限制x为整数集操作函数集操作函数nindex(set_name,primitive_set_element)n该函数返回在集set_name中原始集成员primitive_set_element的索引。集操作函数集操作函数nwrap(index,limit)该函数为index模limit再加1 size(set_name)该函数返回集set_name的成员个数 集合循环函数集合循环函数n四个集合循环函数：四个集合循环函数：FOR、

10、SUM、MAX、MINnfunction(setname (set_index_list)|condition:expression_list);例:PAIRSJIJIMATCHJIBENEFIT),(),(*),(SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J);例:FOR(STUDENTS(I):SUM(pair(j,k)|j#EQ#i#OR#k#EQ#i:match(j,k)=1);.2,1,1),(),(ikjmatchikijpairkj或FILE和和TEXT：文本文件输入输出文本文件输入输出data:a=file(example3_3.ldt);b=fi

11、le(example3_3.ldt);d=file(example3_3.ldt);e=file(example3_3.ldt);enddatainit:x,y=file(example3_3.ldt);endinit1.25,8.75,0.5,5.75,3,7.251.25,0.75,4.75,5,6.5,7.753,5,4,7,6,1120,205,1,2,7Example3_3.ldt的格式格式FILE和和TEXT：文本文件输入输出文本文件输入输出比较a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,1

12、1;e=20,20;x,y=5,1,2,7;OLE：与与EXCEL连接连接使用格式OLE(“filename”，range_name_list)filename 为电子表 文件名,range_name_list 为数据的单元范围。OLE 的使用例子Excel文件example3_4.xls 的内容abdexyresult1.251.25320518.750.75520270.54.7545.755736.567.257.7511注意 要将表格中的数据进行命名:选中数据,选菜单“插入|名称|定义”在这里分别命名为 a,b,d,e,x,y,result OLE 的使用例子Lingo文件exampl

13、e3_4.lg4 的内容data:a,b,d,e=OLE(d:数学建模EXAMPLE3_4.XLS);enddatainit:x,y=Ole(d:数学建模Example3_4.xls);endinitOLE 的使用例子如果在Lingo文件example3_4.lg4 加上以下内容其他不变data:ole(d:数学建模EXAMPLE3_4.XLS,result)=c;ole(d:数学建模EXAMPLE3_4.XLS,x)=x;ole(d:数学建模EXAMPLE3_4.XLS,y)=y;enddataOLE 的使用例子则example3_4.xls 变为abdexyresult1.251.2532

14、05.69594 4.92852438.750.75520 7.2499977.7500.54.75455.7557036.5647.257.751107015011注意其中x,y,result 的变化例例 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每

15、小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(L

16、P)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;OBJECTIVE FUNCTION VALUE 1)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.0000

17、00 NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润利润3360元。元。模型求解模型求解 reduced cost值表值表示当该非基变量示当该非基变量增加一个单位时增加一个单位时（其他非基变量（其他非基变量保持不变）目标保持不变）目标函数减少的量函数减少的量(对对max型问题型问题)OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRIC

18、ES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2也可理解为：也可理解为：为了使该非基变为了使该非基变量变成基变量，量变成基变量，目标函数中对应目标函数中对应系数应增加的量系数应增加的量 OBJECTIVE FUNCTION VALUE 1)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

19、 48.000000 3)0.000000 2.000000 4)40.000000 0.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2stx1+x25012x1+8x24803x1100三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK O

20、R SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量 原料增原料增1单位单位,利润增利润增48 时间加时间加1单位单位,利润增利润增2 能力增减不影响利润能力增减不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！RANGES IN WHICH TH

21、E BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80

22、.000000 4 100.000000 INFINITY 40.000000最优解不变时目标最优解不变时目标系数允许变化范围系数允许变化范围 DO RANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到 30元元/千克，应否改变生产计划千克，应否改变生产计划 x1系数由系数由24 3=72 增加增加为为30 3=90，在，在允许范允许范围内围内 不变！不变！(约束条件不变约束条件不变)结果解释结果解释 结果解释结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED

23、:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000

24、 INFINITY 40.000000影子价格有意义影子价格有意义时约束右端的允时约束右端的允许变化范围许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶？桶？(目标函数不变目标函数不变)注意注意:充分但充分但可能不必要可能不必要LINGOLINGO模型例：选址问题模型例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）ia1.258.750.55.7537.25b1.250.7

25、54.7556.57.75d35476111)现有 2 料场，位于 A(5,1),B(2,7),记(xj,yj),j=1,2,日储量 ej各有 20 吨。假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路目标：制定每天的供应计划，即从 A,B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。用例中数据计算，最优解为i1234561ic（料料场场 A）3507012ic（料料场场 B）00406102,1,6,.,1,.)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型线性规划模型决策变量：决策变量：ci j(料场料场j

26、到到工地工地i的的运量）运量）12维维选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。在其它条件不变下使总吨公里数最小。2,1,6,.,1,.)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型LINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETS ENDSETS）数据段（数据段（DATA ENDDATA）初始段（初始段（INIT

27、ENDINIT）目标与目标与约束段约束段 局部最优：局部最优：89.8835(吨公里吨公里)LP：移到数据段：移到数据段问题问题1.如何下料最节省如何下料最节省?例例 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 按照客户需要在一根原料钢管上安排切割的一种组

28、合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模切割模式式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米

29、钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数

30、根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27整数约束：整数约束：xi 为为整数整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx1527

31、53xxxxi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米”相比相比 钢管下料问题钢管下料问题2 2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割

32、模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量满足需求满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxr15343242141xrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212

33、rrrr1986541643332313rrrr整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2 2目标函数（目标函数（总根数）总根数）321xxxMin约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：原料钢管总根数下界：2619158206105504特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢

34、管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：31 3126321xxx模式排列顺序可任定模式排列顺序可任定 钢管下料问题钢管下料问题2 2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米LINGOLINGO求解整数非线性规划模型求解整数非线性规划模型Local optimal solution found at iteration:12211 Objective value:28.00000Variable Value Reduced CostX1

35、10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2

36、.000000 0.000000 模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含

37、量（称为品位）都是已知的。量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间每个铲位至多安置一台电铲，电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观的，原则上卡车在等待时所耗费的能量也是相当可观的，原则上在安排时在安排时不应发生卡车等待不应发生卡车等待的情况。的情况。露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限品位限制），搭配量在一个班次（制），搭配量在一个班次（8小时）内满足品位限制即小时）内满足品位限制即可。卸点在一个班次内不变。卡车载

38、重量为可。卸点在一个班次内不变。卡车载重量为154吨，平吨，平均时速均时速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次卡车，分别在哪些路线上各运输多少次?平面示意图问题数据问题数据 距离铲位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.563.513.

39、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%问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与

40、岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地；产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运

41、输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排模型假设模型假设n卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后再启动的情况；的情况；n在铲位或卸点处由两条路线以上造成的冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；为不冲突。我们不排时地进行讨论；n空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；n卡车可提前退出系统，等等。卡车可

42、提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解个别参数队找到了可行解（略）（略）符号符号nxij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量（车）（车）单位：单位：吨；吨；ncij：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离 公公里；里；nTij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间 分；分；nAij：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数 辆；辆；nBij：从号铲位到号卸点路线上一辆车最多可运行的次数

43、：从号铲位到号卸点路线上一辆车最多可运行的次数 次；次；npi：i号铲位的矿石铁含量号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31)%nqj:j号卸点任务需求，号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨吨ncki：i号铲位的铁矿石储量号铲位的铁矿石储量 万吨万吨ncyi：i号铲位的岩石储量号铲位的岩石储量 万吨万吨nfi:描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，取变量，取1为使用；为使用；0为关闭。为关闭。532平均速度距离到jiTij5ijijTAijijijTAB5)1(608(近似近似)优化模型c

44、xijijij10151min5,1,10,1,jiBAxijijij10,1,5/60851ifxijij5,1,208101jiijx10,1,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束 5,1,154/101jqxjiij5,2,1,0)5.28(0)5.30(101101jpxpxiiijiiij.7101iifxij为非负整数fi 为0-1整数计算结果（计算结果（LINGOLINGO

45、软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 27070铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0.8671.8620.314倒场1.0771.162岩场1.8920.326岩石漏1.8411.229倒场0.6840.11.489计算结果（派车）计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1(29)倒场1(39)1(37)岩场1(37)岩石漏1(44)1(35)倒场1(47)结论：结论：铲位铲位1、2

46、、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。此外：此外：6辆联合派车（方案略）辆联合派车（方案略）2005年全国大学生数学建模竞赛B题 DVD在线租赁在线租赁 n随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互

47、动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。n考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁 n请考虑以下问题：n1、n2、表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员

48、的在线订单（表2的数据格式示例如下表），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001C0030）分别获得哪些DVD。DVD编号D001D002D003D004现有数量10401520会员在线订单C00016000C00020000C00030003C00040000cjaijn注：D001D100表示100种DVD,C0001C1000表示1000个会员,会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。n问题二的解答n1、如何定义满意度？n满意度是在线订单表格数字的减函数 n满意度的

49、几种定义方式,1/,00,0ijijijijAASA,11,00,0i ji ji ji jAASA,(11)/10,00,0i ji ji ji jAASAn2、0-1规划模型对于问题中的分配问题,我们可以设0-1 决策变量 ,=1 表示将j 号DVD分配给i 号会员,=0 表示不分配.ijxijxijxijx 2005 DVD问题数学模型1 0 0 01 0 0,11,.,1,2,.1 0 03,1,2,.1 0 0 0,0,1ijijijijijijjiijijijiM a xXSs t XAXCjXYiXY nlingo程序n!Excel 表b2005table2.xls A(i,j)

50、为零改为 11；n!Excel表b2005table3.xls 为未改动数据nmodel:nsets:nuser/1.1000/:y;ndvd/1.100/:C;nlink(user,dvd):A,S,X;nendsets 2005 DVD问题ndata:nS=ole(d:lingo8B2005table2.xls);nC=ole(d:lingo8B2005table2.xls,CC);nA=ole(d:ling8b2005table3.xls);nenddata 2005 DVD问题nmax=sum(link(i,j):(11-S(i,j)/10*X(i,j);nfor(dvd(j):sum