优化2010.ppt

优化方法建模侯为根安徽工业大学数理学院Email：优化模型和算法的重要意义最优化:在一定条件下，寻求使目标最大(小)的决策最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:运输方案结构设计 资源分配 生产计划 经验积累，主观判断 作试验，比优劣 建立数学模型，求解最优策略解决优化问题的手段CUMCM赛题：约有一半为优化问题须用软件求解优化问题的一般形式优化问题三要素：决策变量；目标函数；约束条件目标函数约束条件决策变量可行解(满足约束条件)，可行域(可行解的集合)，最优解(使目标达到最大/最小的可行解)例1 加工奶制品的生产计划获利24元/公斤获利16元/公斤1桶牛奶12小时8小时3公斤A14公斤A2或每天:50桶牛奶 时间480小时 A1至多加工100公斤制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？获利24元/公斤获利16元/公斤1桶牛奶12小时8小时3公斤A14公斤A2或每天：50桶牛奶 时间480小时 A1至多加工100公斤决策变量x1桶牛奶生产A1x2桶牛奶生产A2目标函数获利243x1获利164x2每天获利 Max z=72x1+64 x2约束条件原料供应劳动时间加工能力非负约束x1+x250线性规划模型(LP)12x1+8x24803x1100 x1,x20模型求解图解法约束条件x1+x25012x1+8x24803x1100 x1,x20l1:x1+x2=50l2:12x1+8x2=480l3:3x1=100l4:x1=0,l5:x2=0目标函数Max z=72x1+64 x2z=c(常数)等值线在B(20,30)点得到最优解最优解一定在凸多边形的某个顶点取得目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线模型求解软件实现 Objective value:3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;endLingo 8.020桶牛奶生产A1,30桶生产A2，利润3360元。未做敏感性分析结果解释Global optimal solution found at iteration:4 Objective value:3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;end三种资源原料无剩余时间无剩余加工能力剩余40“资源”剩余为零的约束为紧约束（有效约束）结果解释 Objective value:3360.000Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000最优解下“资源”增加1单位时“效益”的增量。影子价格原料增加1单位,利润增长48。时间增加1单位,利润增长2。加工能力增长不影响利润。聘用临时工人付出的工资最多每小时几元？35元可买到1桶牛奶，要买吗？35 48,应该买！2元！Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000结果解释作敏感性分析最优解不变时，目标函数系数允许变化范围(约束条件不变)x1系数范围(64,96)x2系数范围(48,72)x1系数为303=90 在允许范围内A1的获利增加到30元/公斤，应否改变生产计划？生产计划不变！Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000结果解释 影子价格有意义时约束右端的允许变化范围(目标函数不变)原料最多可增加10时间最多可增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!例2 钢管下料原料钢管:每根19米客户需求4米50根6米20根8米15根问题1.如何下料最节省?节省的标准是什么？问题2.客户增加需求：5米10根由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？钢管下料切割模式按照客户需要在一根原料钢管上安排切割的一种组合合理切割模式的余料应小于客户需要钢管的最小尺寸余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料3米8米1根8米1根钢管下料问题1合理切割模式模式 4米钢管根数 6米钢管根数 8米钢管根数余料(米)14003231013201341203511116030170023为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？两种标准1.原料钢管剩余总余量最小2.所用原料钢管总根数最少决策变量xi按第i种模式切割的原料钢管根数(i=1,2,7)目标1(总余量)Min Z=3x1+x2+3x3+3x4+x5+x6+3x7模式4米根数6米根数8米根数余料(米)14003231013201341203511116030170023需求502015约束满足需求4x1+3x2+2x3+x4+x550 x2+2x4+x5+3x620 x3+x5+2x715整数约束xi为整数最优解:x2=12,x5=15,其它为0最优值:z=27按模式2切割12根,按模式5切割15根，余料27米L280.lg4钢管下料问题1目标2(总根数)Min Z=x1+x2+x3+x4+x5+x6+x7约束条件不变最优值：254x1+3x2+2x3+x4+x550 x2+2x4+x5+3x620 x3+x5+2x715与目标1的结果“共切割27根,余料27米”相比按模式1切割5根按模式2切割5根按模式5切割15根共25根，余料35米虽余料增加8米，但减少了2根当余料没有用处时，通常以总根数最少为目标最优解：x1=5,x2=5,x5=15,其余为0L281.lg4钢管下料问题2增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定全部合理切割模式为：模式12345678910 11 12 13 14 15 164米00000011112223345米00112200130120106米03120112000101008米2010101010100000余料3102131320301123决策变量xi按第i种模式切割的原料钢管根数(i=1,2,16)目标(总根数)钢管下料问题2约束满足需求x7+x8+x9+x10+2x11+2x12+2x13+3x14+3x15+4x16 50 x3+x4+2x5+2x6+x9+3x10+x12+2x13+x15 103x2+x3+2x4+x6+x7+2x8+x12+x14 202x1+x3+x5+x7+x9+x11 15整数约束xi为整数,i=1,2,16为方便分别令:a=(0,0,0,0,0,0,1,1,1,1,2,2,2,3,3,4)；b=(0,0,1,1,2,2,0,0,1,3,0,1,2,0,1,0)；c=(0,3,1,2,0,1,1,2,0,0,0,1,0,1,0,0)；d=(2,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0)。x1=7,x11=1,x12=12,x14=8,共28根;Mathematica和Lingo的求解的结果分别为:x8=7,x9=10,x11=5,x16=6,共28根;裁剪模式过多不符合要求!规划问题可表示为:xi为整数,i=1,2,16钢管下料问题2解决方法:增加约束条件:设变量 ri,其只取2个值0和1,取1表示选取第i种裁剪模式,0表示不选取。因为只允许有选择三种裁剪模式，所以增加约束：其他约束改变为：xi为整数，ri为0-1变量，i=1,2,16.目标函数不变：lingo求解结果为：x2=5，x3=10，x16=13，共28根。Mathematica时间太长，等不及！r1i,r2i,r3i,r4i第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量钢管下料问题2增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。对大规模问题，用模型的约束条件界定合理模式决策变量xi按第i种模式切割的原料钢管根数(i=1,2,3)另一种思路钢管下料问题2目标函数（总根数）Min z=x1+x2+x3模式合理：每根余料不超过3米约束条件满足需求r11x1+r12x2+r13x350r21x1+r22x2+r23x310r31x1+r32x2+r33x320r41x1+r42x2+r43x315164r11+5r21+6r31+8r4119164r12+5r22+6r32+8r4219164r13+5r23+6r33+8r4319整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数。整数非线性规划模型钢管下料问题2增加约束，缩小可行域，便于求解需求:4米50根，5米10根 6米20根，8米15根每根原料钢管长19米原料钢管数量的下界：特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=3126x1+x2+x3 31模式排列顺序可任定x1x2 x3 Objective value:28.00000Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.00000 X3 8.000000 1.000000R11 2.000000 0.000000R12 3.000000 0.000000R13 0.000000 0.000000R21 1.000000 0.000000R22 0.000000 0.000000R23 0.000000 0.000000R31 1.000000 0.000000R32 1.000000 0.000000R33 0.000000 0.000000R41 0.000000 0.000000R42 0.000000 0.000000R43 2.000000 0.000000模式2：每根原料钢管切成3根4米和1根6米钢管,共10根；Lingo求解整数非线性规划模型原料钢管总根数为28根模式1：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根L291.lg4例3 饮料厂的生产与检修企业生产计划考虑与产量无关的固定费用给优化模型求解带来新的困难。单阶段生产计划多阶段生产计划外部需求和内部资源随时间变化生产批量问题饮料厂的生产与检修计划某种饮料4周的需求量、生产能力和成本周次需求量(千箱)生产能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合计100135存贮费:每周每千箱饮料0.2(千元)。安排生产计划,满足每周的需求,使4周总费用最小。在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?问题分析除第4周外每周的生产能力超过每周的需求；生产成本逐周上升；前几周应多生产一些。周次需求 能力成本115305.0225405.1335455.4425205.5合计100135模型假设饮料厂在第1周开始时没有库存；从费用最小考虑,第4周末不能有库存；周末有库存时需支出一周的存贮费；每周末的库存量等于下周初的库存量。模型建立周次需求 能力成本115305.0225405.1335455.4425205.5决策变量x1x4：第14周的生产量y1y3：第13周末库存量存贮费：0.2(千元/周千箱)目标函数产量、库存与需求平衡能力限制约束条件x1-y1=15x2+y1-y2=25x3+y2-y3=35x4+y3=35x130,x2 40 x345,x420 非负约束x1,x2,x3,x4,y1,y2,y30模型求解Lingo求解x1x4：15，40，25，20；y1y3：0，15，5。最优解周次需求产量库存能力成本115150305.02254015405.1335255455.4425200205.54周生产计划的总费用为528(千元)L271.lg4在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?检修计划周次需求 能力成本115305.0225405.1335455.4425205.50-1变量wt：wt=1检修安排在第t周(t=1,2,3,4）检修安排在任一周均可约束条件产量、库存与需求平衡条件不变能力限制x130 x240 x345x420 x1+15w130 x2+15w240+5w1x3+15w345+5w1+5w2x4+15w420+5w1+5w2+5w34周内设备检修一次：增加约束w1+w2+w3+w4=1目标函数不变检修计划Lingo求解Objective value:527.0000Variable Value Reduced Cost X1 15.00000 0.000000 X2 45.00000 0.000000 X3 15.00000 0.000000 X4 25.00000 0.000000 Y1 0.000000 0.000000 Y2 20.00000 0.000000 Y3 0.000000 0.100000 W1 1.000000 -0.500000 W2 0.000000 1.500000 W3 0.000000 0.000000 W4 0.000000 0.000000w1=1 在第一周内检修4周的生产量分别为：x1=15,x2=45,x3=15,x4=25.3周的库存量分别为：y1=0,y2=20,y3=0总费用由528降为527(千元)。检修所导致的生产能力提高的作用,需要更长的时间才能得到充分体现。L272.lg4饮料的生产批量问题饮料厂使用同一条生产线轮流生产多种饮料。若某周开工生产某种饮料,需支出生产准备费8千元。某种饮料4周的需求量、生产能力和成本周次需求量(千箱)生产能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合计100135存贮费:每周每千箱饮料0.2(千元)。安排生产计划,满足每周的需求,使4周总费用最小。生产批量问题的一般提法ct时段t生产费用(元/件)；ht时段t(末)库存费(元/件)；st时段t生产准备费(元)；dt时段t市场需求(件)；Mt时段t生产能力(件)。假设初始库存为0制订生产计划，满足需求,并使T个时段的总费用最小。决策变量xt时段t生产量；yt时段t(末)库存量；wt=1时段t开工生产(wt=0 不开工)。目标约束生产批量问题的一般提法混合0-1规划模型将所给参数代入模型，用Lingo求解最优解：x1x4：30，40，30，0；总费用554.0(千元)x1x4：15，40，45，0；也是最优解总费用一样L273.lg4Lingo软件包能求解的优化模型优化模型连续优化整数规划线性规划（LP）二次规划QP非线性规划NLPLingo软件的求解过程1、确定常数Lingo预处理程序线性规划求解程序非线性规划求解程序分支定界管理程序LPNLPQPIP全局优化ILPIQPINLP2、识别类型1、单纯形算法2、内点算法1、顺序线性规划法2、广义既约梯度法3、多点搜索建模时要注意的几个基本问题1、尽量使用实数优划，减少整数约束和整数变量2、尽量使用光滑优划，减少非光滑约束个数如：尽量少使用绝对值、符号函数、多个变量求最大值/最小值，四舍五入，取整函数等3、尽量使用线性模型、减少非线性约束和非线性变量的个数 （如：x/y5改为x5y)4、合理设定变量上下界，尽可能给出变量初始值。5、模型中使用的参数数量级要适当(如小于103)。Lingo模型的优点包含Lindo的全部功能提供了灵活的编程语言（矩阵生成器）Lingo模型的构成目标与约束段集合段（SETS ENDSETE）数据段（DATA ENDDATA）初始段（INTT ENDINTT）计算段（CALC ENDCALC）LINGO9.0例4、运输问题某公司有6个货栈，分别向8个销售点供应商品，每一个货栈的供应量都是有限的，每个销售点需求量必须满足，不同的货栈向不同的销售点运输单位货物的成本是不一样的，问该公司如何调配各货栈和销售点之间的物资运量，才能使运输费用最小？wh1wh2wh3wh4wh5wh6V1V2V3V4V5V6V7V8销售网示意图48条运输路线运费V1V2V3V4V5V6V7B8供应量wh16267425960wh24953858255wh35219743351wh47673927143wh52395726541wh65522814352需求量3537223241324338货栈供应量、销售点需求量以及各点之间的运费如下表设xij、cij分别表示从i货栈向j销售点运送的货物量和单位货物量的运费，目标是总运费为最小：约束条件：约束条件：每个货栈运往各销售点的货物总量应小于货栈的可供应量，设货栈i的可供应量为wi，则有每个销售点的需求量必须满足，设销售点j的需求量为vj，则有model:sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost,volume;endsetsdata:capacity=60 55 51 43 41 52;demand=35 37 22 32 41 32 43 38;cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddata!目标函数;min=sum(links:cost*volume);!需求约束;for(vendors(J):sum(warehouses(I):volume(I,J)=demand(J);!产量约束;for(warehouses(I):sum(vendors(J):volume(I,J)=capacity(I);end集合段（SETS ENDSETE）数据段（DATA ENDDATA）目标与约束段例5：选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里)水泥日用量di(单位：顿)i123456a1.258.750.55.7537.25b1.250.754.7556.57.75c3547611假设：料场与工地之间有直线道路1）现有两个料场，位于A(5,1)，B(2,7),记(xj,yj),j=1,2 日储存量ej各20吨。目标：制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总吨公里数最小。决策变量：cij料场j到工地i的运量12维线性规划模型用例中数据计算，最优解为i123456ci1(料场料场A)350701ci2(料场料场B)0040610总吨公里数为136.2选址问题:NLP2）重建两个新料场，需要确定新料场的位置(xj,yj)和运量cij，在其他条件不变下使总吨公里数最小。决策变量：cij，xj，yj16维非线性规划模型Model:sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:!需求点的位置需求点的位置;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,11;!需求量需求量;e=20,20;!供应量供应量;enddatainit:endinit!目标函数目标函数;OBJmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);!需求约束需求约束;for(demand(i):Demand_Comsum(supply(j):c(i,j)=d(i););!供应约束供应约束;for(supply(j):Supply_comsum(demand(i):c(i,j)=e(j););for(supply:free(x);free(y););endLingo模型的构成：4个段集合段：SETS ENDSETS数据段：DATA ENDDATA初始段：SETS ENDSETS目标与约束段：集合的类型集合派生集合基本集合稀疏集合 稠密集合元素列表法元素过滤法直接列举法 隐式列举法setname(parent_set_list)/member_list/:atribute_list;setname/member_list/:atribute_list;sets:students/John,Jill,Rose,Mike/:sex,age;endsets例如：定义有4个成员2个属性的学生集合上面为直接列举法，当集合成员很多时可用隐式列举法，例如：sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;endsets为了定义一个原始集，必须详细声明：1、集的名字，2、集的成员(可选)，3、集成员的属性(可选)；用下面的语法（表示可选）：setname/member_list/:attribute_list;定义基本集合：集合元素的隐式列举类型隐式列举格式示例示例集合的元素数字型 1.n1.51,2,3,4,5字符数字型stringM.stringNCar101.Car108Car102,Car102,Car104,car108星期型 dayM.dayNMon.FriMon,Tue,Wed,Thu,Fri月份型 monthM.monthNOCT.JANOCT,NOV,DEC,JAN年份月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NEV2001,DEC2001,JAN2002下表给出了隐式列举的一些具体方法1、集的名字，2、父集的名字，3、集成员(可选)，4、集成员的属性(可选)定义派生集为了定义一个派生集，必须详细声明：setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。定义一个派生集语法：setname(parent_set_list)/member_list/:attribute_list;sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost,volume;endsets例如下列集合links就是派生集合：sets:cities/a1,a2,a3,a4/;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上例的派生集合为稠密集合，若为稀疏集合，则可选用元素列表法或元素过滤法：若派生集合是基本集合构成的笛卡儿积,则称它为稠密集合;派生集合的元素可以只是这个笛卡儿积的一个真子集合，这种派生集合称为稀疏集合例如下二例：元素列表法元素过滤法运算符的优先级三类运算符：逻辑运算符算术运算符关系运算符优先级运算符最高#NOT#-（负号）*/+-(减法）#EG#NE#GT#GE#LT#LE#AND#OR#最低(=)四个集合循环函数：FOR、SUM、MAX、MIN集合循环函数循环函数一般格式function(setname(set_index_list)|condtion:expression_list);例如：objectivemax=sum(pairs(i,j):benefit(i,j)*match(i,j);例如：for(students(i):condtion sum(pairs(i,j)|j#EQ#i#OR#k#EQ#i:match(j,k)=1);集合操作函数四个集合循环函数 IN、INDEX、WARP、SIZE1in(set_name,primitive_index_1,primitive_index_2,)如果元素在指定集中，返回1；否则返回0。例：全集为I，B是I的一个子集，C是B的补集。sets:I/x1.x4/;B(I)/x2/;C(I)|#not#in(B,&1):;endsets2index(set_name,primitive_set_element)函数返回在集set_name中成员primitive_set_element 的索引 sets:girls/debble,sue,alice/;boys/bob,joe,sue,fred/;endsetsI1=index(sue);I2=index(boys,sue)I1的值是2，I2的值是3。我们建议在使用index函数时最好指定集。例：确定成员在集合中的位置 该函数返回j=index-k*limit，其中k是一个整数，取适当值保证j落在区间1，limit内。该函数相当于index模limit再加1。该函数在循环、多阶段计划编制中特别有用。3wrap(index,limit)该函数返回集set_name的成员个数。在模型中明确给出集大小时最好使用该函数。它的使用使模型更加数据中立，集大小改变时也更易维护。4size(set_name)变量界定函数实现对变量取值范围的附加限制，共4种：bin(x)限制x为0或1；bnd(L,x,U)限制LxU；free(x)取消对变量x的默认下界为0的限制；gin(x)限制x为整数。变量界定函数一项工作一周7天都需要有人（比如护士工作），每天（周一至周日）所需的最少职员数为20、16、13、16、19、14和12，并要求每个职员一周连续工作5天，试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。例6:职员时序安排模型设周一到周日安排的人数分别为：x1,x2,x7，则周一到周日工作的人数为：先考虑周一：因为一旦安排了工作就连续工作五天，所以周一工作的人员应为上周四到本周一安排工作的人数之和：所以有x4+x5+x6+x7+x120同理，周二到周日的约束为：x5+x6+x7+x1+x216；x6+x7+x1+x2+x313；x7+x1+x2+x3+x416；x1+x2+x3+x4+x519；x2+x3+x4+x5+x614；x3+x4+x5+x6+x712；目标函数为 Min Z=x1+x2+x3+x4+x5+x6+x7xi为正整数。model:sets:days/mon.sun/:required,start;endsetsdata:!每天所需的最少职员数每天所需的最少职员数;required=20 16 13 16 19 14 12;enddata!最小化每周所需职员数最小化每周所需职员数;min=sum(days:start);for(days(J):sum(days(I)|I#le#5:start(wrap(J-I+1,7)=required(J);end8 名同学准备分成4 个调查队（每队两人）前往4 个地区进行社会调查。设两两之间组队的效率如表所示（由于对称性只列出了上三角部分），问如何组队可以使总效率最高？例7:匹配问题学生s1s2s3s4s5s6s7s8s1_9342156s2_173521s3_44291s4_1552s5_876s6_23s7_4“元素过滤”法设mij为0-1变量，mij=1表示学生i与j匹配，设bij为学生i与j匹配的效率，目标为总效率最高：目标函数对学生i有且只有一个其他的学生与其匹配约束条件mij为0-1变量MODEL:SETS:students/1.8/;pairs(students,students)|&2#GT#&1:efects,match;ENDSETSDATA:efects=9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;ENDDATAMAX=SUM(pairs(I,J):efects(I,J)*match(I,J);FOR(students(I):SUM(pairs(J,K)|J#EQ#I#OR#K#EQ#I:match(J,K)=1);FOR(pairs(I,J):BIN(match(I,J);END结果为1,8,2,4,3,7,5,6匹配,效率为30。在公路网中，司机希望找到一条从一个城市到另一个城市的最短路.假设图表示的是该公路网,节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离（百公里）.那么,货车从城市S 出发到达城市T,如何选择行路线,使所经过的路程最短?SA1A2A3B1B2C1C2T633658674678956S到T的最优行驶路线P先求出从Ck(k=1,2)到T的最优行驶路线.从Bk到T的最优行驶路线.从Ak到T的最优行驶路线.例8 最短路问题从S到T的行驶过程分成4 个阶段,即SAi(i=1,2 或3),Ai Bj(j=1或2),Bj Ck(k=1或2),Ck T记d(Y,X)为城市Y与城市X之间的直接距离（若这两个城市之间没有道路直接相连，则可以认为直接距离为无穷大），用L(X)表示城市X到城市T的最优行驶路线的路长,则:!最短路问题最短路问题;model:sets:cities/S,A1,A2,A3,B1,B2,C1,C2,T/:L;roads(cities,cities)/S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/:P,D;endsetsdata:D=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6;L=,0;enddata!L(index(T)=0;for(cities(i)|i#LT#INDEX(T):L(i)=min(roads(i,j):D(i,j)+L(j););!显然，如果显然，如果P(i,j)=1,则点则点i到点到点n的最短路径的第一步是的最短路径的第一步是i-j，否则就不是。，否则就不是。由此，我们就可方便的确定出最短路径由此，我们就可方便的确定出最短路径;for(roads(i,j):P(i,j)=if(L(i)#eq#D(i,j)+L(j),1,0);end结果L(S)=20，路径为：SA3B2C1T1324567891051213121163104121496851052现有10个城市的交通网，我们想找到从城市1到城市10的最短路径;动态规划图示说明SETS:!这里是这里是10个城市的基础集，其中个城市的基础集，其中F(i)表示从城市表示从城市i到最后一个城到最后一个城市的最短路径市的最短路径;CITIES/1.10/:F;!派生集派生集ROADS列出了城市间所有存在的道路（注：并非所有城市间列出了城市间所有存在的道路（注：并非所有城市间都有道路直接连接，并假定所有直接连接路径仅有一条都有道路直接连接，并假定所有直接连接路径仅有一条;ROADS(CITIES,CITIES)/1,2 1,3 1,4 2,5 2,6 2,7 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/:D;!D(i,j)是城市是城市 i 到到 j的距离的距离;ENDSETSDATA:!这里是对应于上述直接连接的道路的长度这里是对应于上述直接连接的道路的长度;D=1 5 2 13 12 11 6 10 4 12 14 3 9 6 5 8 10 5 2;ENDDATA!如果你已经位于城市如果你已经位于城市10，则你到城市的，则你到城市的10旅行长度为旅行长度为0;F(SIZE(CITIES)=0;!下列是经典的动态规划递归式。用语言叙述就是：从城市下列是经典的动态规划递归式。用语言叙述就是：从城市i到城市到城市10的最短路径为城市的最短路径为城市i到所有能直达的城市到所有能直达的城市j的路径长度加上城市的路径长度加上城市j到城市到城市10的最短路径的和的最小值的最短路径的和的最小值;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j);例9:装车问题要把七种不同规格的包装箱装到两辆铁路平板车上去，包装箱的宽和高都是相等的，但厚度（t以厘米计）及重量（w以千克计）却不同，下表给出它们的厚度、重量及数量c1c2c3c4c5c6c7t(厘米)48.752.061.372.048.752.064.0w(千克)200030001000500400020001000k(箱数)8796648每辆平板车有10.2米长的地方可用于装箱（像面包片那样），载重量为40吨，由于当地的货运的限制，对c3、c6、c7三类包装箱的总数有如下特殊约束：他们所占的空间不得超过302.7厘米，是把这些包装箱装到车上去，而浪费的空间最小。问题分析包装箱总重89吨，平板车能载80吨，装不完，究竟在车上装那些包装箱，每种装多少，必须有一