数学建模第四讲

1、第四讲第四讲 数学规划模型数学规划模型( (一一) ) 4.1 奶制品的生产奶制品的生产4.2 自来水输送与货机装运自来水输送与货机装运数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxg xim或x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条件约束条件多元函数多元函数条件极值条件极值 决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域的边界上取得的边界上取得 数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建

2、立和结果的分析重点在模型的建立和结果的分析企业生产计划企业生产计划4.1 奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划用参数等，以最小成本为目标制订生产批量计划.时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划

3、单阶段生产计划，否则应制订多阶段生产计划，否则应制订多阶段生产计划.本节课题本节课题一、加工奶制品的生产计划一、加工奶制品的生产计划1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或获利获利24元元/kg 获利获利16元元/kg 50桶牛奶桶牛奶 时间时间480h 至多加工至多加工100kgA1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/kg，应否改变

4、生产计划？，应否改变生产计划？ 每天：每天：问问题题模型假设模型假设1. A1、A2两种产品每千克的获利是与它们的各自产两种产品每千克的获利是与它们的各自产量无关的常数，每桶牛奶加工出量无关的常数，每桶牛奶加工出A1、A2的数量和所的数量和所需时间是与它们各自产量无关的常数；需时间是与它们各自产量无关的常数；2. A1、A2两种产品每千克的获利是与它们相互间产两种产品每千克的获利是与它们相互间产量无关的常数，每桶牛奶加工出量无关的常数，每桶牛奶加工出A1、A2的数量和所的数量和所需时间是与它们相互间产量无关的常数；需时间是与它们相互间产量无关的常数；3. 加工加工A1、A2的牛奶桶数可以是任意

5、实数。的牛奶桶数可以是任意实数。1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或获利获利24元元/kg 获利获利16元元/kg x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472maxxxz每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480h 至多加工至多加工100kgA1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型求解

6、模型求解 图解法图解法 x1x2OABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472maxxxz目标目标函数函数 z=0z=2400z=3360z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最优解.目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得

7、形的某个顶点取得. . 模型求解模型求解 软件实现软件实现 LINGO model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3

8、360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元元. 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/kg，应否改变生产计划？，应否改变生产计划？ 附加问题的求解附加问题的求解5021 xx48081221 xx10031x21

9、6472maxxxz0,21xx问题问题1,2等价于分析模型中约束等价于分析模型中约束条件右端资源项增加一个单位条件右端资源项增加一个单位会给目标函数增加多少效益。会给目标函数增加多少效益。 问题问题3等价于分析模型中等价于分析模型中目标函数价值系数的改目标函数价值系数的改变是否改变最优解。变是否改变最优解。 线性规划的灵敏度分析！线性规划的灵敏度分析！结果解释结果解释 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X

10、1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 原料无剩余原料无剩余时间无剩

11、余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 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 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000

12、000最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量 影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?35 48, 应该买！应该买！ 聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元? 2元！元！原料增加原料增加1单位单位, 利润增长利润增长48 时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allow

13、ableVariable 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 MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最优解不变时目标函最优解不变时目标函数系数允许变化

14、范围数系数允许变化范围 敏感性分析敏感性分析 (“LINGO|Ranges” ) x1系数范围系数范围(64,96) x2系数范围系数范围(48,72) A1获利增加到获利增加到 30元元/kg，应否改变生产计划，应否改变生产计划? x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内 不变！不变！(约束条件不变约束条件不变)结果解释结果解释 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coeffic

15、ient 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 MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原

16、料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶桶牛奶, 每天最多买多少每天最多买多少?最多买最多买10桶桶!(目标函数不变目标函数不变)4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大怎样安排输送方案使运费最小，或利润最大?运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少如何搭配装载，使获利最高，或装箱数量最少?其他费用其他费用: :450元元/

17、103t 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？ 元元/ 103t甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费一、一、 自来水输送自来水输送收入：收入：900元元/103t 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水库供水量水库供水量小区基本用水小区基本用水量量小区额外用水量小区额外用水量（以天计）（以天计）(103t)(103t)

18、(103t)总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润 = 收入收入(900) 其他费用其他费用( (450) 引水管理费引水管理费利润利润(元元/ 103t )甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/问题二问题二 确定送水方案确定送水方案使利润最大使利润最大供应供应限制限制约束约束条件条件需求需求限制限制 线性线性

19、规划规划模型模型(LP)10014131211xxxx10012033323124232221xxxxxxx8030312111xxxx3010332313xxx50102414xx目标目标函数函数 3332312423222114131211220250260300260320310280230320290maxxxxxxxxxxxxZ模型建立模型建立 求解求解部分结果：部分结果：Objective Value: 88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.

20、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.000000 X33 30.000000 0.000000 运输问题运输问题总利润总利润 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)40100

21、50305030供应点供应点需求点需求点物资物资供需平衡或不平衡供需平衡或不平衡LINGOLINGO如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？ 三个货舱三个货舱最大最大载载重重(t),(t),最大最大容积容积(m(m3 3) ) 二、二、 货机装运货机装运 重量重量（t）空间空间( m3/t）利润利润（元（元/t）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例. . 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8

22、；5300飞机平衡飞机平衡模型假设模型假设 1. 1. 每种货物可以分割到任意小；每种货物可以分割到任意小；2. 2. 每种货物可以在一个或多个货舱中任每种货物可以在一个或多个货舱中任意分布；意分布；3. 3. 多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙； 4.4.所给出的数据都是精确的，没有误差所给出的数据都是精确的，没有误差。 决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(t(t）i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓分别代表前、中、后仓)模型建立模型建立 WET=(10,16,8), VOL=(6800,8700,5300); w=(18,15,23,12), v=(480,650, 580,390), p=(3100,3800,3500,2850).已知参数已知参数 i=1,2,3,4（货物），（货物），j=1,2,3 (分别代表前、中、后仓分别代表前、中、后仓)货舱货舱j的重量限制的重量限制WETj ，体积限制体积限制VOLj第第i种货物的重量种货物的重量wi，体积，体积vi，利润，利润