第三讲 数学规划模型

第三讲数学规划模型

3.1奶制品的生产计划3.2一般优化模型简介3.3接力队选拔和选课策略3.4钢管的截断切割问题3.5投资的风险与收益问题3.6进一步的学习y3.1奶制品的生产计划第三讲数学规划模型

1桶牛奶3公斤A1

12小时8小时4公斤A2

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

制订生产计划，使每天获利最大每天：35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？问题3.1奶制品的生产计划第三讲数学规划模型

x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

线性规划模型(LP)模型的建立与求解（LINGO软件）第三讲数学规划模型

一、优化模型的三要素：决策变量（decisionvariable）目标函数（objectivefunction）约束条件（constraints）→feasibleregion:3.2一般优化模型（数学规划）简介第三讲数学规划模型

二、优化模型的一般形式generalmodel3.2一般优化模型（数学规划）简介三、局部最优解与全局最优解第三讲数学规划模型

3.2一般优化模型（数学规划）简介四、优化模型的基本类型（2）离散优化/组合优化（discreteopt/combinatorialopt）（2）无约束优化（unconstrainedopt）1、按照有无约束（1）约束优化（constrainedoptimization）2、按照决策变量x的分量取值（1）连续优化/数学规划（continuousopt/mathematicalprogramming）第三讲数学规划模型

3.2一般优化模型（数学规划）简介3、按照目标函数的个数单目标规划与多目标规划4、按照参数或者决策变量是否具有不确定性确定性规划与不确定性规划（如随机规划、模糊规划等）5、按照目标函数f，约束条件g、h是否连续可微光滑优化与非光滑优化第三讲数学规划模型

四、优化模型的基本类型3.2一般优化模型（数学规划）简介五、常见的优化问题类型第三讲数学规划模型

3.2一般优化模型（数学规划）简介五、常见的优化问题类型第三讲数学规划模型

3.2一般优化模型（数学规划）简介六、优化模型的求解难度优化连续优化整数规划LPQPNLP问题求解的难度增加第三讲数学规划模型

3.2一般优化模型（数学规划）简介建立优化模型时需要注意的几个基本问题

1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)第三讲数学规划模型

3.3.1指派问题3.3接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。第三讲数学规划模型

丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?3.3.2混合泳接力队的选拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-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每种泳姿有且只有1人模型求解

最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1ENDINT20

输入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

57.5,方案是否调整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21=x32=x43=x51=1,成绩为4’17”7c43,c54的新数据重新输入模型，用LINDO求解指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案为了选修课程门数最少，应学习哪些课程？

3.3.3选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求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~不选）

选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。

课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机先修课程要求最优解：

x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型

约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分

2线性代数

3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程

8预测理论应用统计9数学实验微积分；线性代数多目标规划

在课程最少的前提下以学分最多为目标。最优解：

x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。多目标规划

对学分数和课程数加权形成一个目标，如三七开。最优解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3讨论与思考最优解与1=0，2=1的结果相同——学分最多多目标规划

最优解与1=1，2=0的结果相同——课程最少生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小3.4钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大第三讲数学规划模型

问题1.如何下料最节省?3.4.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米50根，5米10根，6米20根，8米15根每根原料钢管长19米LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。第三讲数学规划模型

3.5投资的风险与收益问题见word文档第三讲数学规划模型

3.6进一步的学习一、运输问题假设WirelessWidget（WW）公司有6个仓库（warehouse）向8个销售商（vendor）供应小装饰品，每个仓库的供应量是有限的，而每个销售商的需求又必须得到满足。因此WW公司要决定每个仓库出多少货能满足每个销售商而运输成本又最低。相关数据如下列表格所示。请引入合适的变量，建立求解该问题的数学模型。表1-1存货数据仓库号（WH）WH1WH2WH3WH4WH5WH6货物量CAPACITY605551434152表1-2销售商需求销售商号（W）V1V2V3V4V5V6V7V8需求量DEMAND3537223241324338表1-3单位运输成本($)COSTV1V2V3V4V5V6V7V8WH162674259WH249538582WH352197433WH476739271WH532957265WH655228143第三讲数学规划模型

3.6进一步的学习二、易拉罐下料问题：某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高10cm，上盖和下底直径均为5cm。该公司使用两种不同规格的镀锡板原料：规格1的镀锡板是边长为24cm的正方形，规格2的镀锡板是长方形，长、宽分别为32cm和28cm。由于生产工艺的限制，对于规格1的镀锡板原料只能按照模式1、2、3进行冲压；对于规格2的镀锡板原料只能按照模式4进行冲压。使用模式1、2、3、4进行每次冲压所需要的时间分别为1.5s、2s、1s、3s。该工厂每周工作40小时，每周可供使用的规格1、规格2的镀锡板原料分别为5万张和2万张。目前每只易拉罐的利润为0.10元，原料余料损失为0.001元/厘米2（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作原料余料损失）。问工厂应如何安排每周生产计划？板材规格2：长方形，3228cm，2万张。易拉罐下料每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001元/cm2（不能装配的罐身、盖、底也是余料）模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上盖下底罐身罐身高10cm，上盖、下底直径均5cm。

板材规格1：正方形，边长24cm，5万张。如何安排每周生产？

罐身个数底、盖个数余料损失（cm2）冲压时间（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形边长24cm问题分析计算各种模式下的余料损失上、下底直径d=5cm，罐身高h=10cm。模式1余料损失242-10d2/4-dh=222.6cm2问题分析目标:易拉罐利润扣除原料余料损失后的净利润最大

约束：每周工作时间不超过40小时；原料数量：规格1（模式1~3）5万张，规格2（模式4）2万张；罐身和底、盖的配套组装。注意：不能装配的罐身、上下底也是余料决策变量

xi~按照第i种模式的生产张数(i=1,2,3,4)；y1~一周生产的易拉罐个数；y2~不配套的罐身个数；y3~不配套的底、盖个数。模型建立目标

约束条件

时间约束原料约束产量余料时间x1222.61.5x2183.32x3261.81x4169.53模型建立y1~易拉罐个数；y2~不配套的罐身；y3~不配套的底、盖。每只易拉罐利润0.10元，余料损失0.001元/cm2罐身面积dh=157.1cm2

底盖面积d2/4=19.6cm2(40小时)约束条件

配套约束y1~易拉罐个数；y2~不配套的罐身；y3~不配套的底、盖。罐身底、盖1102401645产量x1x2x3x4虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理。将所有决策变量扩大10000倍（xi~万张，yi~万件）

LINDO发出警告信息：“数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别”模式2生产40125张，模式3生产3750张，模式4生产20000张，共产易拉罐160250个(罐身和底、盖无剩余)，净利润为4298元

模型求解OBJECTIVEFUNC