1、第四章第四章 数学规划模型数学规划模型 4.0 数学规划模型数学规划模型4.1 奶制品的生产与销售奶制品的生产与销售4.2 自来水输送与货机装运自来水输送与货机装运4.3 汽车生产与原油采购汽车生产与原油采购4.4 接力队选拔和选课策略接力队选拔和选课策略4.5 投资的收益和风险投资的收益和风险4.6 供应与选址供应与选址y4.0 数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(.),(),()(1或x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件多元函数多元函数条件极值条件极值 决策变量个数决策
2、变量个数n和和约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域的边界上取得的边界上取得 数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析一一 线性规划线性规划案例案例4.1，4.2引例引例生产组织计划问题生产组织计划问题某厂若只限生产甲乙两种产品，已知生产甲产品每单某厂若只限生产甲乙两种产品，已知生产甲产品每单位可获利位可获利10元，生产乙产品每单位可获利元，生产乙产品每单位可获利12元，甲乙元，甲乙两种产品的生产都必须经过厂里的三个车间，每单位两种产品的生产都必须经过厂里的三个车间，每单位产品在每个车
3、间里所需要的工时数和每个车间可以用产品在每个车间里所需要的工时数和每个车间可以用来加工的总时数如下表，问应如何安排生产，才能使来加工的总时数如下表，问应如何安排生产，才能使厂方获得最大利润？厂方获得最大利润？单位产品需工时数单位产品需工时数一车间一车间二车间二车间三车间三车间甲（甲（10元）元）231乙（乙（12元）元）321本月总时数本月总时数15001500600单位产品需工时数单位产品需工时数一车间一车间二车间二车间三车间三车间甲（甲（10元）元）231乙（乙（12元）元）321本月总时数本月总时数15001500600设一月中生产甲产品设一月中生产甲产品x1个单位，乙产品个单位，乙产品
4、x2个单位个单位厂方本月所获利润为厂方本月所获利润为F模模型型 0,0600150023150032.1210max2121212121xxxxxxxxtsxxF表示利润表示利润F最大最大一车间可用工时数限制一车间可用工时数限制二车间可用工时数限制二车间可用工时数限制三车间可用工时数限制三车间可用工时数限制两种产品非负约束两种产品非负约束线性规划问题的标准型线性规划问题的标准型njjjxcF1max目标函数目标函数ts.njxmibxajinjjij,.,2,1,0,.,2,1,1约束条件约束条件若记若记),.,(,)(),.,(,),.,(212121mnmijnnbbbbaAccccxxx
5、x则则0.maxxbAxtscxF矩阵形式矩阵形式(LP)(Linear Programming)非标准型化标准型非标准型化标准型1）若求）若求min F=cx可化为可化为 max(-F)=-cx2）若）若AAbxAiii的第的第i行行则引入则引入ininxx,0松弛变量松弛变量即可化为等式约束即可化为等式约束iinibxxAiibxA时同理时同理3）若某）若某xk无非负要求，无非负要求，xk自由变量自由变量令令)0,0(,kkkkkxxxxx思考：思考：jnjjjxxcF1max自由变量自由变量线性规划的求解线性规划的求解1）若只有两个变量时可以用图解法，见）若只有两个变量时可以用图解法，见
6、4.12）单纯形法（略）有兴趣可参阅运筹学方面的教材）单纯形法（略）有兴趣可参阅运筹学方面的教材3）Matlab软件求解软件求解4）LindoLingo软件求解软件求解计算机软件计算机软件直接求解直接求解用用MATLAB优化工具箱解线性规划优化工具箱解线性规划命令：命令：x=linprog（c，A，b）2、模型、模型：min z=cX bAXts.beqXAeq命令：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：注意：若没有不等式：存在，则令存在，则令A=，b=.bAX min z=cX bAXts.1、模型：、模型：3、模型、模型：min z=cX bAXts.b
7、eqXAeqlbXub命令：命令：1 x=linprog（c，A，b，Aeq,beq,lb，ub）2 x=linprog（c，A，b，Aeq,beq,lb，ub,X0）注意：注意：1 若没有等式约束若没有等式约束:,则令则令Aeq=,beq=.2其中其中X0表示初始点表示初始点 beqXAeq4、命令：、命令：x,fval=linprog()返回最优解及处的目标函数值返回最优解及处的目标函数值fval.c=-10-12;A=2 3;3 2;1 1;b=1500 1500 600;Aeq=;beq=;lb=0;0;ub=;x,fval=linprog(c,A,b,Aeq,beq,lb,ub)0,
8、0600150023150032.1210max2121212121xxxxxxxxtsxxF用用MATLAB求解引例求解引例 Optimization terminated successfully.x=300.0000 300.0000fval=-6.6000e+003用用Lingo软件解软件解线性规划线性规划max=10*x1+12*x2;2*x1+3*x21500;3*x1+2*x21500;x1+x2600;Global optimal solution found at iteration:2 Objective value:6600.000 Variable Value Redu
9、ced Cost X1 300.0000 0.000000 X2 300.0000 0.000000 Row Slack or Surplus Dual Price 1 6600.000 1.000000 2 0.000000 3.200000 3 0.000000 1.200000 4 0.000000 0.000000 问题1 某厂利用甲,乙,丙,丁四种设备生产A,B,C三种产品,相关数据如表所示.已知这三种产品的单件利润分别是4.5,5,7（百元）,试问该厂应如何安排生产可获得最大利润?ABC总工时总工时甲甲224800乙乙123650丙丙423850丁丁242700 分析 ：该问题的关
10、键所在是确定每种产品的产量,为此以 表示三种产品的产量,则目标为1,x23,xx123Max 4.557.zxxx 在一个生产周期中,每种设备所提供的工时为有限的,故对四种设备而言还应该满足下列条件:123123123123224800,23650,423850,242700.xxxxxxxxxxxx.st非负性0,1,2,3.ixi用Lingo软件可以得到相应问题的解.启动Lingo,在窗口下中输入下列程序:max4.5*15*27*3;2*12*24*3800;1*12*23*3650;4*12*24*3850;2*14*22*3700;Endxxxxxxxxxxxxxxx保存完之后执行L
11、ingo菜单下的Solve命令,得到相应的解.Variable Value Reduced Cost X1 85.71429 0.000000 X2 71.42857 0.000000 X3 121.4286 0.000000 Row Slack or Surplus Dual Price 1 1592.857 1.000000 2 0.000000 1.357143 3 57.14286 0.000000 4 0.000000 0.2142857 5 0.000000 0.4642857 问题2 某车间要制造100套钢筋架,每套需要长为2.9m,2.1m,1.5 m 的钢筋各一根.已知原料钢
12、筋长度为7.4 m,问如何切割钢筋,使得钢筋的利用率为最高?分析 该问题的要点是如何切割钢筋,使得每次切割之后,剩下的余料为最少?假设在切割过程中,我们不考虑钢筋的损耗,并考虑各种切割方案:方案方案2.92.11.5余料余料1103022010.130220.241200.350130.8 从分析中可以看出,此问题的关键是确定每种方案下的余料数.设 表示第 种方案中使用的原料钢筋数,则余料数为1,2,5ix i i23450.10.20.30.8.zxxxx而相应的限制条件为12434512352100,22100,323100.xxxxxxxxxx非负性0,1,2,5.ixi.st在Ling
13、o下得到该问题的解为min 0.1*20.2*30.3*40.8*5;12*24100;2*32*45100;3*122*33*5100;Endxxxxxxxxxxxxxx运行后得到该问题的解为 X2 10.00000 0.000000 X3 0.000000 0.3666667 X4 50.00000 0.000000 X5 0.000000 1.283333 X1 30.00000 0.000000 问题3 要从甲地调出物资2000吨,从乙地调出物资1100吨,分别供给A地1700吨,B地1100吨,C地200吨和D地100吨,已知每吨运费如表所示,试建立一个使运费达到最小的调拨计划.单位
14、路程运费表销地销地15375151乙乙1572521甲甲DCBA产地产地 分析 设从第 个产地到第 个销地的运输量为 运输成本为 则问题的目标函数为ij,ijx,ijc111213142125715zxxxx2122232451513715,xxxx由于从第一个产地调出的物资的总和为第一个产地的产量,即有111213142000,xxxx同理,有212223241100.xxxx对称地,对销地而言,有关系11211700,xx12221100,xx1323200,xx1424100.xx由此得到该问题的数学模型11121314min 2125715zxxxx2122232451513715,x
15、xxx111213142122232411211222132314242000,1100.1700,1100,200,100.xxxxxxxxxxxxxxxx.st0.ijx 注 该问题又称为运输问题.运输问题的一般形式可写成min ,ijijzc x11,mijiinijjjxaxb.st0.ijx其中 是第 个产地的产量,是第 个销地的需求量.iaijbj11,nijijmijjixaxb.st0.ijx在上面的关系中,有11.mnijijab相应的运输问题称为产销平衡的运输问题.若产销不平衡,应该如何处理?为什么总是假定产销是平衡的.二二 整数规划整数规划案例案例4.3，4.4取整,0.
16、maxxbAxtscxF整数规划的求解整数规划的求解1）分支定界法和割平面法（略）分支定界法和割平面法（略）有兴趣可参阅运筹学方面的教材有兴趣可参阅运筹学方面的教材2）LindoLingo软件求解软件求解（后面讲）（后面讲）IPInteger Programming0-1规划规划1,0.maxxbAxtscxF整数规划的求解整数规划的求解1）隐枚举法（略）有兴趣可参阅运筹学方面的教材）隐枚举法（略）有兴趣可参阅运筹学方面的教材3）LindoLingo软件求解软件求解（后面讲）（后面讲）2）Matlab软件求解软件求解 （7.0版本以上）版本以上）x,fval=bintprog（c,A,b,Ae
17、q,beq）三三 多目标规划多目标规划4.4，4.5四四 非线性规划非线性规划4.3，4.6求解求解 方法多样化，技巧性强方法多样化，技巧性强企业生产计划企业生产计划4.1 奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外
18、部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题例例1 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘
19、用临时工人，付出的工资最多是每小时几元?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线性线性规划规划模型模型(LP)时间时间
20、480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:,0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直
21、线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end 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
22、.000000 4)40.000000 0.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释 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.0
23、00000 4)40.000000 0.000000 NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK O
24、R SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量 原料增加原料增加1单位单位,利润增长利润增长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元
25、！RANGES IN WHICH THE 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.
26、000000 53.333332 80.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
27、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.000000
28、4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)例例2 奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 0.8千克千克B12小时小时,3元元1千克千克获利获利44元元
29、/千克千克 0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克 制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时 至多至多100公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？1桶桶牛奶牛奶 3千克千克 A1 12小时小时 8小时小时 4千克千克 A2 或或获利获利24元元/千克千克 获利获利16元元/kg 0.8千克千克 B
30、12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克 B22小时小时,3元元1千克千克获利获利32元元/千克千克 出售出售x1 千克千克 A1,x2 千克千克 A2，X3千克千克 B1,x4千克千克 B2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 0,61xx x5千克千克 A1加工加工B1，x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加约束附加约束 5380
31、x.x64750 x.x OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000
32、5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2模型求解模型求解 软件实现软件实现 LINDO 6.1 5043)26251xxxx48022)(2)(4)3656251xxxxxx600334)26521xxxx44804624)36521xxxxDO RANGE(SENSITIVITY)ANALYSIS?No OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X
33、3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2结果解释结果解释每天销售每天销售168 千克千克A2和和19.2 千克千克B1，利润利润3460.8（元）（元）8桶牛奶加工成桶牛
34、奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，将得到的将得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均为紧约束为紧约束结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DU
35、AL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000增加增加1桶牛奶使利润增桶牛奶使利润增长长3.1612=37.925043)26251xxxx600334)26521xxxx4增加增加1小时时间使利小时时间使利润增长润增长3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，桶牛奶，
36、可赚回可赚回189.6元。（大于元。（大于增加时间的利润增长）增加时间的利润增长）结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166
37、667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE(SENSITIVITY)ANALYSIS?YesB1获利下降获利下降10%，超，超出出X3 系数允许范围系数允许范围B2获利上升获利上升10%，超，超出出X4 系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，会发现结果有很大变化。计算，会发现结果有很大变化。4.2 自来水输送与货机装运自来水
38、输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。如何搭配装载，使获利最高，或装箱数量最少。其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲
39、乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水库供水量水库供水量(千吨千吨)小区基本用水量小区基本用水量(千吨千吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 总需求量总需
40、求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润 =收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供应供应限制限制B,C 类似处理类似处理50:A14131211xxxx10014131211xxxx问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变或按教材需求约束
41、可以不变或按教材p97中简化中简化求解求解Objective value:88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.00
42、0000 X33 30.000000 0.000000 这类问题一般称为这类问题一般称为“运输问题运输问题”(Transportation Problem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2 货机装运货机装运 重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物21
43、56503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混
44、装，并保证不留空隙；多种货物可以混装，并保证不留空隙；模型建立模型建立 货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax货机装运货机装运模型建立模型建立 货舱货舱重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量680039058065048041312111xxxx530039058065048043
45、332313xxxx870039058065048042322212xxxx约束约束条件条件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx货物货物供应供应 18131211xxx15232221xxx23333231xxx12434241xxx货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量 Objective value:121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X
46、12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中
47、仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中仓3。X21=10,X23=5；X32=13,X33=3；X42=3。870087103*39013*580870039058065048042322212带入数据xxxx注意：取整后不满足约束条件注意：取整后不满足约束条件 22）要得到整数解，可以在模型中加人整数约束，要得到整数解，可以在模型中加人整数约束，于是问题变为整数
48、规划模型（于是问题变为整数规划模型（IP），再求解！），再求解！思考思考 Global optimal solution found at iteration:11 Objective value:121400.0 Variable Value X11 0.000000 X12 2.000000 X13 0.000000 X21 7.000000 X22 0.000000 X23 8.000000 X31 3.000000 X32 12.00000 X33 0.000000 X41 0.000000 X42 2.000000 X43 0.000000121515.80.0000000.0000
49、00 0.00000010.0000000.0000005.0000000.00000012.9473693.0000000.0000003.0526320.000000结果对比结果对比LingoLingo求解求解 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型 中型中型 大
50、型大型 现有量现有量钢材（吨）钢材（吨）1.5 3 5 600劳动时间（小时）劳动时间（小时）280 250 400 60000利润（万元）利润（万元）2 3 4 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。4.3 汽车生产与原油采购汽车生产与原油采购设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3321432xxxzMax600535.1.321xxxts60000400250280321xxx0,321xxx汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5
