第四章 数学规划模型.pdf

zyxzyx数 学 模 型数 学 模 型数学与应用数学第四章数学规划模型第四章数学规划模型4.1 奶制品的生产与销售奶制品的生产与销售4.2汽车生产与原油采购汽车生产与原油采购4.3接力队选拔和选课策略接力队选拔和选课策略4.4饮料厂的生产与检修饮料厂的生产与检修4.5 钢管和易拉罐下料钢管和易拉罐下料y数学规划模型数学规划模型实际问题中的优化模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn?,2,1,0)(.),(),()(1=或x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件多元函数条件极值多元函数条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数学规划数学规划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析企业生产计划企业生产计划4.1 奶制品的生产与销售奶制品的生产与销售空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可制订若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题例例1 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利 243x1获利获利 164 x2原料供应原料供应5021+xx劳动时间劳动时间48081221+xx加工能力加工能力10031x决策变量决策变量目标函数目标函数216472xxzMax+=每天获利每天获利约束条件约束条件非负约束非负约束0,21xx线性规划模型线性规划模型(LP)时间时间480小时小时50桶牛奶每天桶牛奶每天至多加工至多加工100公斤公斤A1模型分析与假设模型分析与假设比例性比例性可加性可加性连续性连续性xi对目标函数的对目标函数的“贡献贡献”与与xi取值成正比取值成正比xi对约束条件的对约束条件的“贡献贡献”与与xi取值成正比取值成正比xi对目标函数的对目标函数的“贡献贡献”与与xj取值无关取值无关xi对约束条件的对约束条件的“贡献贡献”与与xj取值无关取值无关xi取值连续取值连续A1,A2每公斤的获利是与各自产量无关的常数每公斤的获利是与各自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每公斤的获利是与相互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数的数量和时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型模型求解模型求解图解法图解法x1x20ABCDl2l3l4l55021+xx48081221+xx10031x0,21xx约束条件约束条件50:211=+xxl480812:212=+xxl1003:13=xl0:,0:2514=xlxl216472xxzMax+=目标函数目标函数Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。最优解一定在凸多边形的某个顶点取得。l1模型求解模型求解软件实现软件实现LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVE FUNCTION VALUE1)3360.000VARIABLE VALUEREDUCED COSTX1 20.0000000.000000X2 30.0000000.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 48.0000003)0.000000 2.0000004)40.000000 0.000000NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释OBJECTIVE FUNCTION VALUE1)3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROWSLACK OR SURPLUSDUAL PRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源三种资源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释OBJECTIVE FUNCTION VALUE1)3360.000VARIABLE VALUE REDUCED COSTX1 20.000000 0.000000X2 30.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 48.0000003)0.000000 2.0000004)40.000000 0.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增量的增量原料增加原料增加1单位单位,利润增长利润增长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004 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:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多桶牛奶，每天最多买多少少？最多买最多买10桶桶!(目标函数不变目标函数不变)例例2 奶制品的生产销售计划奶制品的生产销售计划在例在例1基础上深加工基础上深加工1桶牛奶桶牛奶3千克千克A112小时小时8小时小时4公斤公斤A2或获利或获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B12小时小时,3元元1千克获利千克获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克获利千克获利32元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投资？现投资小时时间，应否投资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？1桶牛奶桶牛奶3千克千克 A112小时小时8小时小时4千克千克 A2或获利或获利24元元/千克千克获利获利16元元/kg0.8千克千克 B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克 B22小时小时,3元元1千克千克获利获利32元元/千克千克出售出售x1 千克千克 A1,x2 千克千克 A2，X3千克千克 B1,x4千克千克 B2原料供应原料供应劳动时间劳动时间加工能力加工能力决策变量决策变量目标函数目标函数利润利润约束条件约束条件非负约束非负约束0,61xx?6543213332441624xxxxxxzMaxx5千克千克 A1加工加工B1，x6千克千克 A2加工加工B2+=50436251+xxxx48022)(2)(4656251+xxxxxx10051+xx附加约束附加约束5380 x.x=64750 x.x=模型求解模型求解软件实现软件实现LINDO 6.1 5043)26251+xxxx48022)(2)(4)3656251+xxxxxxOBJECTIVE FUNCTION VALUE1)3460.800VARIABLE VALUE REDUCED COSTX1 0.000000 1.680000X2 168.000000 0.000000X3 19.200001 0.000000X4 0.000000 0.000000X5 24.000000 0.000000X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 3.1600003)0.000000 3.2600004)76.000000 0.0000005)0.000000 44.0000006)0.000000 32.000000NO.ITERATIONS=2600334)26521+xxxx44804624)36521+xxxxDO RANGE(SENSITIVITY)ANALYSIS?NoOBJECTIVE FUNCTION VALUE1)3460.800VARIABLE VALUEREDUCED COSTX1 0.0000001.680000X2 168.0000000.000000X3 19.2000010.000000X4 0.0000000.000000X5 24.0000000.000000X6 0.0000001.520000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 3.1600003)0.000000 3.2600004)76.000000 0.0000005)0.000000 44.0000006)0.000000 32.000000NO.ITERATIONS=2结果解释结果解释每天销售每天销售168 千克千克A2和和19.2 千克千克B1，利润，利润3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶牛奶加工成桶牛奶加工成A2，将得到的，将得到的24千克千克A1全部加工成全部加工成B1除加工能力外均为紧约束除加工能力外均为紧约束结果解释结果解释OBJECTIVE FUNCTION VALUE1)3460.800VARIABLE VALUE REDUCED COSTX1 0.000000 1.680000X2 168.000000 0.000000X3 19.200001 0.000000X4 0.000000 0.000000X5 24.000000 0.000000X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 3.1600003)0.000000 3.2600004)76.000000 0.0000005)0.000000 44.0000006)0.000000 32.000000增加增加1桶牛奶使利润增长桶牛奶使利润增长3.1612=37.925043)26251+xxxx600334)26521+xxxx4增加增加1小时时间使利润增长小时时间使利润增长3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投资？现投资小时时间，应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，可赚回桶牛奶，可赚回189.6元。（大于增加时间的利润增长）元。（大于增加时间的利润增长）结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 24.000000 1.680000 INFINITYX2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITYX5 -3.000000 15.800000 2.533334X6 -3.000000 1.520000 INFINITY DO RANGE(SENSITIVITY)ANALYSIS?YesB1获利下降获利下降10%，超出，超出X3 系数允许范围系数允许范围B2获利上升获利上升10%，超出，超出X4 系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，会发现结果有很大变化。计算，会发现结果有很大变化。如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，那么最优的生产计划应作何改变？辆，那么最优的生产计划应作何改变？例例4.2.1 汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。小型中型大型现有量钢材（吨）小型中型大型现有量钢材（吨）1.5 3 5 600劳动时间（小时）劳动时间（小时）280 250 400 60000利润（万元）利润（万元）2 3 4 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。4.2汽车生产与原油采购汽车生产与原油采购设每月生产小、中、大型汽车的数量分别为设每月生产小、中、大型汽车的数量分别为x1,x2,x3321432xxxzMax+=600535.1.321+xxxts60000400250280321+xxx0,321xxx汽车厂生产计划汽车厂生产计划模型建立模型建立线性线性规划规划模型模型(LP)小型中型大型现有量钢材小型中型大型现有量钢材1.5 3 5 600时间时间280 250 400 60000利润利润2 3 4 模型求解模型求解3）模型中增加条件：）模型中增加条件：x1,x2,x3 均为整数，重新求解。均为整数，重新求解。OBJECTIVE FUNCTION VALUE1)632.2581VARIABLE VALUE REDUCED COSTX1 64.5161290.000000X2 167.7419280.000000X3 0.000000 0.946237ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 0.7311833)0.000000 0.003226结果为小数，怎么办？结果为小数，怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值最优值632.2581相差不大。相差不大。2）试探：如取）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值等，计算函数值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？IP可用可用LINDO直接求解直接求解整数规划(整数规划(Integer Programming,简记,简记IP)“gin 3”表示表示“前前3个变量为整数个变量为整数”，等价于：，等价于：gin x1gin x2gin x3 IP 的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE1)632.0000VARIABLE VALUE REDUCED COSTX1 64.000000 -2.000000X2 168.000000 -3.000000X3 0.000000 -4.000000 321432xxxzMax+=600535.1.321+xxxts60000400250280321+xxx为非负整数321,xxx模型求解模型求解IP 结果输出结果输出其中其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产80辆，求生产计划。若生产某类汽车，则至少生产80辆，求生产计划。321432xxxzMax+=600535.1.321+xxxts60000400250280321+xxxx1,x2,x3=0 或 或 80 x1=80，x2=150，x3=0，最优值，最优值z=61080,0,0321=xxx0,80,0321=xxx80,80,0321=xxx0,0,80321=xxx0,80,80321=xxx80,0,80321=xxx80,80,80321xxx0,321=xxx LINDO中对中对0-1变量的限定：变量的限定：int y1int y2int y3 方法方法2：引入：引入0-1变量，化为整数规划变量，化为整数规划M为大的正数，可取为大的正数，可取1000 OBJECTIVE FUNCTION VALUE1)610.0000VARIABLE VALUE REDUCED COSTX1 80.000000-2.000000X2 150.000000-3.000000X3 0.000000-4.000000Y1 1.000000 0.000000Y2 1.000000 0.000000Y3 0.000000 0.000000 若生产某类汽车，则至少生产80辆，求生产计划。若生产某类汽车，则至少生产80辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 801,0,80,11111yyxMyx1,0,80,22222yyxMyx1,0,80,33333yyxMyx最优解同前最优解同前NLP虽然可用现成的数学软件求解(如虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。)，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划：化为非线性规划非线性规划（非线性规划（Non-Linear Programming，简记，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产80辆，求生产计划。若生产某类汽车，则至少生产80辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx应如何安排原油的采购和加工？应如何安排原油的采购和加工？例例4.3.2 原油采购与加工原油采购与加工市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A：购买量不超过购买量不超过500吨时的单价为吨时的单价为10000元/吨；元/吨；购买量超过购买量超过500吨但不超过吨但不超过1000吨时，超过吨时，超过500吨的部分吨的部分8000元/吨；元/吨；购买量超过购买量超过1000吨时，超过吨时，超过1000吨的部分吨的部分6000元/吨。元/吨。售价售价4800元元/吨吨售价售价5600元元/吨吨库存库存500吨吨库存库存1000吨吨汽油甲汽油甲(A 50%)原油原油A 原油原油B 汽油乙汽油乙(A 60%)决策变量决策变量目标函数目标函数问题分析问题分析 利润：销售汽油的收入-购买原油利润：销售汽油的收入-购买原油A的支出的支出 难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂)()(6.5)(8.422122111xcxxxxzMax+=甲甲(A 50%)A B 乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨5.6千元千元/吨吨原油原油A的购买量,原油的购买量,原油A,B生产汽油甲生产汽油甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？原油供应原油供应约束条件约束条件xxx+500121110002221+xx1500 x+=500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500吨单价为吨单价为10千元/吨；千元/吨；500吨吨 x 1000吨，超过吨，超过500吨的吨的8千元/吨；千元/吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千元/吨。千元/吨。目标函数目标函数购买购买x A B x11x12x21x22库存库存500吨库存吨库存1000吨吨?目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；?对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；，一般的非线性规划软件也难以输入和求解；?想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。汽油含原油汽油含原油A的比例限制的比例限制5.0211111+xxx6.0221212+xxx2111xx221232xx约束条件约束条件甲甲(A 50%)A B 乙乙(A 60%)x11x12x21x22x1,x2,x3 以价格以价格10,8,6(千元/吨)采购千元/吨)采购A的吨数的吨数目标函数只有当以目标函数只有当以10千元千元/吨的价格购买吨的价格购买x1=500(吨)时，才能以(吨)时，才能以8千元千元/吨的价格购买吨的价格购买x2方法方法1)6810()(6.5)(8.432122122111xxxxxxxzMax+=0)500(32=xx500,0321xxx非线性规划模型，可以用非线性规划模型，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超过吨，超过500吨的吨的8千元/吨千元/吨增加约束增加约束0)500(21=xxx=x1+x2+x3,c(x)=10 x1+8x2+6x3方法方法1：LINGO求解求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12 x+500;x21+x22 0;2*x12-3*x22 0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1 500;x2 500;x3 0;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value:4800.000Variable Value Reduced CostX11 500.00000.0000000E+00X21 500.00000.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00X1 0.1021405E-13 10.00000X2 0.0000000E+00 8.000000X3 0.0000000E+00 6.000000X 0.0000000E+00 0.0000000E+00 LINGO得到的是局部最优解，还能得到更好的解吗？得到的是局部最优解，还能得到更好的解吗？用库存的用库存的500吨原油吨原油A、500吨原油吨原油B生产汽油甲，不购买新的原油生产汽油甲，不购买新的原油A，利润为，利润为4,800千元。千元。y1,y2,y3=1 以价格以价格10,8,6(千元/吨)采购千元/吨)采购A增加约束增加约束方法方法20-1线性规划模型，可用线性规划模型，可用LINDO求解求解112500500yxy223500500yxy33500yx y1,y2,y3=0或或1 OBJECTIVE FUNCTION VALUE1)5000.000VARIABLE VALUE REDUCED COSTY1 1.000000 0.000000Y2 1.000000 2200.000000Y3 1.000000 1200.000000X11 0.000000 0.800000X21 0.000000 0.800000X12 1500.000000 0.000000X22 1000.000000 0.000000X1 500.0000000.000000X2 500.0000000.000000X3 0.000000 0.400000X 1000.0000000.000000 购买购买1000吨原油吨原油A，与库存的，与库存的500吨原油吨原油A和和1000吨原油吨原油B一起，生产汽油乙，利润为一起，生产汽油乙，利润为5,000千元。千元。x1,x2,x3 以价格以价格10,8,6(千元/吨)采购千元/吨)采购A的吨数的吨数y=0 x=0 x0 y=1优于方法优于方法1的结果的结果b1 b2b3b4方法方法3*b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x=z2b2+z3b3，z2+z3=1，z2,z3 0,c(x)=z2c(b2)+z3c(b3).b3 x b4，x=z3b3+z4b4，z3+z4=1，z3,z4 0,c(x)=z3c(b3)+z4c(b4).+=500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc直接处理分段线性函数直接处理分段线性函数c(x)IP模型，模型，LINDO求解，得到的结果与方法求解，得到的结果与方法2相同.相同.处理分段线性函数，方法处理分段线性函数，方法3更具一般性更具一般性44332211bzbzbzbzx+=)()()()()(44332211bczbczbczbczxc+=bk x bk+1yk=1,否则,否则,yk=03432321211,yzyyzyyzyz+)4,3,2,1(0,14321=+kzzzzzk10,1321321或=+yyyyyy方法方法3bk x bk+1,x=zkbk+z k+1 bk+1zk+zk+1=1，zk,zk+1 0,c(x)=zkc(bk)+zk+1 c(bk+1).c(x)x1200090005000050010001500b1 b2b3b4对于对于k=1,2,3分派问题分派问题4.3 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?如何选拔队员组成4100米混合泳接力队?例例4.3.1 混合泳接力队的选拔混合泳接力队的选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的百米成绩名候选人的百米成绩穷举法：组成接力队的方案共有穷举法：组成接力队的方案共有5!=120种。种。目标函数目标函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记,否则记xij=00-1规划模型规划模型cij(秒)(秒)队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束条件约束条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4=4151jiijijxcZMin每种泳姿有且只有1人每种泳姿有且只有1人5,1,141?=ixjij4,1,151?=jxiij模型求解模型求解最优解：最优解：x14=x21=x32=x43=1,其它变量为其它变量为0;成绩为成绩为253.2(秒)(秒)=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14+67.4x51+71 x52+83.8x53+62.4x54SUBJECT TOx11+x12+x13+x14=1 x41+x42+x43+x44=1x11+x21+x31+x41+x51=1 x14+x24+x34+x44+x54=1END INT 20输入输入LINDO求解求解甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲 自由泳、乙自由泳、乙 蝶泳、丙蝶泳、丙 仰泳、丁仰泳、丁 蛙泳.蛙泳.丁蛙泳丁蛙泳c43=69.675.2，戊自由泳，戊自由泳c54=62.4 57.5,方案是否调整？敏感性分析？,方案是否调整？敏感性分析？乙乙 蝶泳、丙蝶泳、丙 仰泳、丁仰泳、丁 蛙泳、戊蛙泳、戊 自由泳自由泳IP规划一般没有与规划一般没有与LP规划相类似的理论，规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。输出的敏感性分析结果通常是没有意义的。最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为417”7 c43,c54的新数据重新输入模型，用的新数据重新输入模型，用LINDO求解求解指派(指派(Assignment)问题：)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论讨论甲甲 自由泳、乙自由泳、乙 蝶泳、丙蝶泳、丙 仰泳、丁仰泳、丁 蛙泳.蛙泳.原方案原方案为了选修课程门数最少，应学习哪些课程？为了选修课程门数最少，应学习哪些课程？例例4.3.2 选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型规划模型决策变量决策变量目标函数目标函数xi=1 选修课号选修课号i 的课程（的课程（xi=0 不选）不选）91iiM inZx=选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课。门计算机课。254321+xxxxx398653+xxxxx29764+xxxx课号课号课名课名所属类别所属类别1微积分微积分数学数学