算法-第4章数学模型

第4章数学规划模型第四章数学规划模型

4.1奶制品的生产与销售4.2

自来水输送与货机装运4.3

汽车生产与原油采购4.4

接力队选拔和选课策略4.5

饮料厂的生产与检修4.6钢管和易拉罐下料y数学规划模型

实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析企业生产计划4.1奶制品的生产与销售

空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3360z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！

聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)例2奶制品的生产销售计划

在例1基础上深加工1桶牛奶3千克A1

12小时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千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/kg

0.8千克

B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5千克A1加工B1，x6千克A2加工B2附加约束

模型求解

软件实现

LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1

除加工能力外均为紧约束结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增加1桶牛奶使利润增长3.16×12=37.92增加1小时时间使利润增长3.2630元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）结果解释B1,B2的获利有10%的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000

X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY

…………DORANGE(SENSITIVITY)ANALYSIS?YesB1获利下降10%，超出X3系数允许范围B2获利上升10%，超出X4系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小§6钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大问题1.如何下料最节省?例1

钢管下料问题2.客户增加需求：原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根按照客户需要在一根原料钢管上安排切割的一种组合。

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

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量

目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12,x5=15,

其余为0；最优值：27。整数约束：xi为整数当余料没有用处时，通常以总根数最少为目标目标2（总根数）钢管下料问题1约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。xi为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增加一种需求：5米10根；切割模式不超过3种。现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。决策变量

xi~按第i种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数增加约束，缩小可行域，便于求解原料钢管总根数下界：

特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=31模式排列顺序可任定

钢管下料问题2需求：4