数学规划及软件市公开课一等奖百校联赛特等奖课件

王文祥

.7数学规划模型、案例与

软件求解10/10/第1页一.数学规划模型与优化软件介绍二.LINDO/LINGO软件Outline四.LINGO建模语言

三.建模实例10/10/第2页

•数学规划是优化问题一个分支，起始于20世纪30年代末，50年代与60年代发展成为一个完整分支并受到数学界和社会各界重视。七八十年代是数学规划飞速发展时期，不论是从理论上还是算法方面都得到了深入完善。时至今日数学规划依然是运筹学领域中热点研究问题。从国内外数学建模竞赛试题中看，有二分之一以上问题可用数学规划进行求解。

一.数学规划模型与优化软件介绍10/10/第3页约束条件决议变量数学规划模型普通形式目标函数可行域

三要素：决议变量；目标函数；约束条件可行解（只满足约束）与最优解(取到最优值)“受约束于”之意．10/10/第4页数学规划类型连续规划:全部决议变量取值均为连续数值(实数)离散规划:部分或全部决议变量只取离散数值10/10/第5页

线性规划(LP)目标和约束均为线性函数

非线性规划(NLP)目标或约束中存在非线性函数

二次规划(QP)目标为二次函数、约束为线性

整数规划(IP)决议变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)普通整数规划，0-1（整数）规划连续规划离散规划数学规划(MathematicalProgramming)10/10/第6页惯用优化软件

LINDO/LINGO软件MATLAB优化工具箱/mathematica优化程序包EXCEL软件优化功效SAS(统计分析)软件优化功效10/10/第7页LINDO企业软件产品简明介绍

美国芝加哥(Chicago)大学LinusSchrage教授于1980年前后开发,以后成立LINDO系统企业（LINDOSystemsInc.），网址：

LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer10/10/第8页LINDO和LINGO能求解数学规划模型LINGOLINDO数学规划模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续规划整数规划(IP)10/10/第9页LINDO是专门用于求解数学规划软件包。LINDO执行速度很快、易于方便输入，所以在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、二次规划。也能够用于线性方程组求解以及代数方程求根等。LINDO中包含了建模语言和许多惯用数学函数（包含大量概论函数），可供使用者建立规划问题时调用。普通用LINDO（LinearInteractiveandDiscreteOptimizer）处理线性规划二.LINDO/LINGO软件介绍10/10/第10页最大规模模型非零系数能够到达1,000,000个最大变量个数能够到达100,000个，最大目标函数和约束条件个数能够到达3个最大整数变量个数能够到达100,000个

LINDO6.1学生版至多可求解多达300个变量和150个约束规划问题10/10/第11页1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快计算能力强4.内置建模语言提供内部函数较少语句直观描述大规模优化模型5.引入集合轻易建模6.数据交换方便(与EXCEL和数据库)

LINGO软件主要功效和特点10/10/第12页例1简单线性规划（LP）问题：在空白模型窗口中输入这个LP模型：max2x+3yst4x+3y<=103x+5y<12end10/10/第13页如图：

10/10/第14页LINDO程序有以下特点：

★程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表示式和约束表示式；★目标函数和约束之间用“ST”分开；（或用“s.t.”）★程序以“END”结束（“END”也能够省略）。★系数与变量之间乘号必须省略。★系统对目标函数所在行自动生成行名“1）”,对约束默认行名分别是“2)”“3)”…，用户也能够自己输入行名；行名放在对应约束之前。★书写相当灵活，无须对齐，不区分字符大小写。★默认全部变量都是非负,所以无须输入非负约束。★约束条件中“<=”及“>=”可分别用“<”及“>”代替。★一行中感叹号“！”后面文字为是注释语句，可增强程序可读性，不参加模型建立。10/10/第15页模型求解：用鼠标点击工具栏中图标，或从菜单中选择Solve|Solve（Ctrl+S）命令LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所表示LINDO

“求解器运行状态窗口”。10/10/第16页求解器运行状态窗口显示对应信息及含义：

名称含义Status当前状态显示当前求解状态：“Optimal”表示已抵达最优解；其它可能显示还有三个：Feasible(可行解),Infeasible(不可行),Unbounded(最优值无界)。Iterations迭代次数显示迭代次数：“2”表示经过了2次迭代。

Infeasibility

不可行性约束不满足量(即各个约束条件不满足“数量”和)：“0”表示解是可行。Objective当前目标值显示目标函数当前值：7.45455。BestIP整数规划当前最正确目标值显示整数规划当前最正确目标值：“N/A”（NoAnswer）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（IP）。10/10/第17页名称含义IPBound整数规划界显示整数规划界（对最大化问题显示上界；对最小化问题，显示下界）Branches分枝数显示分枝定界算法已经计算分枝数：ElapsedTime所用时间显示计算所用时间（秒）：“0.00”说明计算太快了，用时还不到0.005秒。UpdateInterval刷新本界面时间间隔显示和控制刷新本界面时间间隔：“1”表示1秒；用户能够直接在界面上修改这个时间间隔。InterruptSolver中止求解程序当模型规模比较大时，求解时间会很长，能够在程序运行过程中用鼠标点击该按钮终止计算。Close关闭该按钮是关闭状态窗口，并不终止计算10/10/第18页紧接着弹出一对话框，问询你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。10/10/第19页汇报窗口用鼠标选择“Window|ReportsWindow”（汇报窗口），就能够查看该窗口内容10/10/第20页输出结果表示意思是：“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代（旋转）后得到最优解。“OBJECTIVEFUNCTIONVALUE1)7.454545”

表示最优目标值为7.454545.（注意：在LINDO中目标函数所在行总是被认为是第1行，这就是这里“1）”含义）。10/10/第21页“VALUE”给出最优解中各变量(VARIABLE)值:X=1.272727,Y=1.636364.“REDUCEDCOST”给出最优单纯形表中目标函数行（第1行）中变量对应系数.“SLACKORSURPLUS（松驰或剩下）”给出约束对应松驰变量值:第2、3行松驰变量均为0,说明对于最优解来讲，两个约束（第2、3行）均取等号，即都是紧约束。10/10/第22页“DUALPRICES”给出对偶价格（或影子价格）值:表示最优解下“资源”增加1单位时“效益”增量。

第2、3行对偶价格分别为.090909，.545455。

“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代。10/10/第23页使用LINDO一些注意事项“>”（或“<”）号与“>=”（或“<=”）功效相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超出8个字符变量名不区分大小写（包含LINDO中关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号后面部分为注释。如:

!It’sComment.在模型任何地方都能够用“TITLE”对模型命名（最多72个字符），如： TITLEThisModelisonlyanExample10/10/第24页变量不能出现在一个约束条件右端表示式中不接收括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表示式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定全部变量非负；可在模型“END”语句后用“FREEname”将变量name非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界比如：“subx110”作用等价于“x1<=10”但用“SUB”和“SLB”表示上下界约束不计入模型约束，也不能给出其松紧判断和敏感性分析。使用LINDO一些注意事项10/10/第25页14.“END”后对0-1变量说明：INTn或INTname15.“END”后对整数变量说明：GINn或GINname使用LINDO一些注意事项16.

简单错误检验和防止：输入模型时可能会有一些输入错误.当问题规模较大时,要查找错误是比较困难。在LINDO中有一些可帮助寻找错误功效，其中之一就是菜单命令“Report|Picture（Alt+5）”,它功效是能够将目标函数和约束表示式中非零系数经过列表（或图形）显示出来。10/10/第26页三个变量范围限定命令(FREE、SUB、SLB)作用

求解以下LP问题：这个模型中对变量x没有非负限制，对y有上限限制，对z有下限限制。用FREE、SUB、SLB三个命令能够实现这些功效。10/10/第27页MAX2x–3y+4zS.T.con2)4x+3y+2z<=10con3)-3x+5y-z<12con4)x+y+5z>8con5)-5x-y-z>2ENDfreex!说明：变量x没有非负限制suby20!说明：变量y上界为20slbz30!说明：变量z下界为30详细输入以下：求解得到结果：最大值为122，最优解为x=-17，y=0，z=39。能够看出y上界（20）在最优解中并没有到达，z下界（30）也没有到达，所以模型中去掉“suby20”和“slbz30”两个语句，得到结不变。但因为最优解中x取值为负值，所以“freex”这个语句确实是不能少。不妨试一下，去掉这个语句后效果会怎样？10/10/第28页

LINGO入门设有线性规划模型以下：10/10/第29页LP问题在lindo和lingo中不一样输入形式Lindo:max2x+3yst4x+3y<103x+5y<12endLingo:max=2*x+3*y;4*x+3*y<10;3*x+5*y<12;（1）将目标函数表示方式从“MAX”变成了“MAX=”（2）“ST”在LINGO模型中不再需要，所以被删除了

（3）每个系数与变量间增加了运算符“*”（即乘号不能省略）

（4）每行（目标、约束和说明语句）后面均增加了一个分号“;”

（5）模型结束标志“END”也被删除了（LINGO中只有当模型以“MODEL:”开始时才能以“END”结束）。

10/10/第30页LINGO语法规则1.最大值MAX=…,最小值MIN=…2.语句必须以分号”;”结束每行可多个语句语句可跨行3.变量名由字母、数字和下划线组成以字母开头长度不超32个字符不区分大小写4.默认决议变量非负其它要求可做说明5.模型以MODEL：开头，以END结束(此结构也可省略）6.注释以！开始，以;结束；7.能够用<表示<=；用>表示>=10/10/第31页程序语句输入备注：LINGO总是依据“MAX=”或“MIN=”寻找目标函数，而除注释语句和TITLE语句外其它语句都是约束条件，所以语句次序并不主要。限定变量取整数值语句为“@GIN(X1)”和“@GIN(X2)”，不能够写成“@GIN(2)”，不然LINGO将把这个模型看成没有整数变量。LINGO中函数一律需要以“@”开头，其中整型变量函数（@BIN、@GIN）和上下界限定函数（@FREE、@SUB、@SLB）与LINDO中命令类似。而且0/1变量函数是@BIN函数。10/10/第32页一个简单LINGO程序例直接用LINGO来解以下二次规划问题：输入窗口以下：10/10/第33页输出结果：运行菜单命令“LINGO|Solve”最优整数解X=(35，65)最大利润=11077.510/10/第34页LINGO求解实例例1model:max=2*x1-3*x2-2*x3+x4;x1-2*x2-3*x3-2*x4=5;x1-x2+2*x3+x4=10;End10/10/第35页Globaloptimalsolutionfoundatiteration:2

Objectivevalue:18.33333VariableValueReducedCostX18.3333330.000000X20.0000000.6666667X30.0000004.333333X41.6666670.000000RowSlackorSurplusDualPrice118.333331.00000020.0000000.333333330.0000001.666667运行结果以下:10/10/第36页看完例1后,能解下面这个问题吗?例210/10/第37页例3model:!thisisanintegerprogrammingproblem;max=4*x1+3*x2;4*x1+x2<=10;2*x1+3*x2<=8;@gin(x1);@gin(x2);end10/10/第38页Globaloptimalsolutionfoundatiteration:0

Objectivevalue:11.00000VariableValueReducedCostX12.000000-4.000000X21.000000-3.000000RowSlackorSurplusDualPrice111.000001.00000021.0000000.00000031.0000000.000000运行结果以下:10/10/第39页例4model:!thisisanuncontrainedoptimalproblem;min=3/2*x1^2+1/2*x2^2-x1*x2-2*x1;@free(x1);@free(x2);end10/10/第40页Localoptimalsolutionfoundatiteration:73

Objectivevalue:-1.000000VariableValueReducedCostX10.99999950.000000X20.99999920.000000RowSlackorSurplusDualPrice1-1.000000-1.000000运行结果以下:10/10/第41页例5model:min=-3*x1^2-x2^2-2*x3^2;x1^2+x2^2+x3^2-3=0;-x1+x2>=0;end10/10/第42页

Localoptimalsolutionfoundatiteration:37

Objectivevalue:-6.000000VariableValueReducedCostX11.2128090.000000X21.2128090.000000X30.24122010.000000RowSlackorSurplusDualPrice1-6.000000-1.00000020.0000002.00000030.000000-2.425619运行结果以下:10/10/第43页例1加工奶制品生产计划1桶牛奶3千克A1

12小时8小时4千克A2

或赢利24元/千克赢利16元/千克50桶牛奶时间480小时至多加工100千克A1

制订生产计划，使天天赢利最大35元可买到1桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元?A1赢利增加到30元/千克，应否改变生产计划？天天：三、建模实例10/10/第44页1桶牛奶3千克A1

12小时8小时4千克A2

或赢利24元/千克赢利16元/千克x1桶牛奶生产A1

x2桶牛奶生产A2

原料供给

劳动时间

加工能力

决议变量

目标函数

天天赢利约束条件非负约束

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

50桶牛奶天天10/10/第45页模型求解

软件实现

LINDOmax72x1+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元。10/10/第46页结果解释

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三种资源“资源”剩下为零约束为紧约束（有效约束）10/10/第47页结果解释

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元！10/10/第48页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，在允许范围内不变！(约束条件不变)10/10/第49页结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端允许改变范围原料最多增加10时间最多增加5335元可买到1桶牛奶，天天最多买多少？最多买10桶(目标函数不变)10/10/第50页假如生产某一类型汽车，则最少要生产80辆，那么最优生产计划应作何改变？例2汽车厂生产计划

汽车厂生产三种类型汽车，已知各类型每辆车对钢材、劳动时间需求，利润及工厂每个月现有量。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234制订月生产计划，使工厂利润最大。10/10/第51页设每个月生产小、中、大型汽车数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)10/10/第52页模型求解

3）模型中增加条件：x1,x2,x3

均为整数，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，经过比较可能得到更优解。但必须检验它们是否满足约束条件。为何？10/10/第53页IP可用LINDO直接求解整数规划(IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP结果输出10/10/第54页LINDO中对0-1变量限定：inty1inty2inty3方法：引入0-1变量，化为整数规划

M为大正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生产某类汽车，则最少生产80辆，求生产计划。x1=0或

80x2=0或

80x3=0或

8010/10/第55页应怎样安排原油采购和加工

？

例3原油采购与加工

市场上可买到不超出1500吨原油A：购置量不超出500吨时单价为10000元/吨；购置量超出500吨但不超出1000吨时，超出500吨部分8000元/吨；购置量超出1000吨时，超出1000吨部分6000元/吨。售价4800元/吨售价5600元/吨库存500吨

库存1000吨汽油甲(A

50%)原油A原油B汽油乙(A

60%)10/10/第56页决议变量

目标函数问题分析利润：销售汽油收入-购置原油A支出难点：原油A购价与购置量关系较复杂甲(A

50%)AB乙(A

60%)购置x

x11x12x21x224.8千元/吨5.6千元/吨原油A购置量,原油A,B生产汽油甲,乙数量c(x)~购置原油A支出利润(千元)c(x)怎样表述？10/10/第57页原油供给

约束条件x

500吨单价为10千元/吨；500吨

x

1000吨，超出500吨8千元/吨；1000吨

x

1500吨，超出1000吨6千元/吨。目标函数购置x

ABx11x12x21x22库存500吨库存1000吨10/10/第58页目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义c(x)，普通非线性规划软件也难以输入和求解；想方法将模型化简，用现成软件求解。

汽油含原油A百分比限制约束条件甲(A

50%)AB乙(A

60%)x11x12x21x2210/10/第59页y1,y2,y3=1~以价格10,8,6(千元/吨)采购A增加约束0-1线性规划模型，可用LINDO求解y1,y2,y3=0或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000购置1000吨原油A，与库存500吨原油A和1000吨原油B一起，生产汽油乙，利润为5,000千元。x1,x2,x3~以价格10,8,6(千元/吨)采购A吨数y=0x=0x>0

y=110/10/第60页例4:员工聘用方案决议变量：周一至周日天天(新)聘用人数x1,x2,x7目标函数：7天(新)聘用人数之和约束条件：周一至周日天天需要人数10/10/第61页连续工作5天周一工作应是(上)周四至周一聘用设系统已进入稳态聘用方案整数规划模型(IP)10/10/第62页首先在LINDO模型窗口输入模型:MINX1+X2+X3+X4+X5+X6+X7SUBJECTTOMON)X1+X4+X5+X6+X7>=50TUE)X1+X2+X5+X6+X7>=50WED)X1+X2+X3+X6+X7>=50THU)X1+X2+X3+X4+X7>=50FRI)X1+X2+X3+X4-X5>=80SAT)X2+X3+X4-X5+X6>=90SUN)X3+X4-X5+X6+X7>=90ENDGIN7其中“GIN7”表示7个变量都是普通整数变量。

（依然默认为取值是非负）10/10/第63页求解后状态窗口中与整数相关三个域有了相关结果:“BestIP：94”表示当前得到最好整数解目标函数值为94（人）。“IPBound：93.5”表示该整数规划目标值下界为93.5（人）。“Branches：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。10/10/第64页OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X24.0000001.000000X340.0000001.000000X42.0000001.000000X534.0000001.000000X610.0000001.000000X74.0000001.000000ROWSLACKORSURPLUSDUALPRICESMON)0.0000000.000000TUE)2.0000000.000000WED)8.0000000.000000THU)0.0000000.000000FRI)0.0000000.000000SAT)0.0000000.000000SUN)0.0000000.000000NO.ITERATIONS=18BRANCHES=1DETERM.=1.000E0求解结果汇报窗口以下：10/10/第65页生产中经过切割、剪裁、冲压等伎俩，将原材料加工成所需大小例5钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大10/10/第66页某钢管零售商从钢管厂进货，将钢管按照用户要求切割后售出。从钢管厂进货时得到原料钢管都是19米长。1) 现有一客户需要50根4米长、20根6米长和15根8米长钢管。应怎样下料最节约？2) 零售商假如采取不一样切割模式太多，将会造成生产过程复杂化，从而增加生产和管理成本，所以该零售商要求采取不一样切割模式不能超出3种。另外，该客户除需要1）中三种钢管外，还需要10根5米长钢管。应怎样下料最节约？1、钢管下料10/10/第67页问题1）求解

问题分析首先，应该确定哪些切割模式是可行。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割一个组合。比如，我们能够将19米长钢管切割成3根4米长钢管，余料为7米显然，可行切割模式是很多。其次，应该确定哪些切割模式是合理。通常假设一个合理切割模式余料不应该大于或等于客户需要钢管最小尺寸。在这种合理性假设下，切割模式一共有7种，如表所表示。10/10/第68页为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节约？合理切割模式2.所用原料钢管总根数最少模式

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

目标1（总余量）模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015整数约束：xi为整数10/10/第70页模型求解将整数线性规划模型（加上整数约束）输入LINDO以下：

Title钢管下料-最小化余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7 10/10/第71页求解能够得到最优解以下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000

按模式2切割12根,按模式5切割15根，余料27米

10/10/第72页目标2（总根数）钢管下料问题1约束条件不变xi为整数10/10/第73页将整数线性规划模型（加上整数约束）输入LINDO：Title钢管下料-最小化钢管根数Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7模型求解10/10/第74页求解，能够得到最优解以下：OBJECTIVEFUNCTIONVALUE1)25.00000 VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.00000010/10/第75页当余料没有用处时，通常以总根数最少为目标最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但降低了2根与目标1结果“共切割27根，余料27米”相比10/10/第76页钢管下料问题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米长钢管数量10/10/第77页满足需求模式合理：每根余料不超出3米整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数10/10/第78页增加约束，缩小可行域，便于求解原料钢管总根数下界：

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

需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米10/10/第79页将模型输入LINGO以下：model:Title钢管下料-最小化钢管根数LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13>=50;x1*r21+x2*r22+x3*r23>=10;x1*r31+x2*r32+x3*r33>=20;x1*r41+x2*r42+x3*r43>=15;4*r11+5*r21+6*r31+8*r41<=19;4*r12+5*r22+6*r32+8*r42<=19;4*r13+5*r23+6*r33+8*r43<=19;4*r11+5*r21+6*r31+8*r41>=16;4*r12+5*r22+6*r32+8*r42>=16;4*r13+5*r23+6*r33+8*r43>=16;x1+x2+x3>=26;x1+x2+x3<=31;x1>=x2;x2>=x3;@gin(x1);@gin(x2);@gin(x3);@gin(r11);@gin(r12);@gin(r13);@gin(r21);@gin(r22);@gin(r23);@gin(r31);@gin(r32);@gin(r33);@gin(r41);@gin(r42);@gin(r43);end

10/10/第80页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根。10/10/第81页

问题某企业采取一套冲压设备生产一个罐装饮料易拉罐，这种易拉罐是用镀锡板冲压制成。易拉罐为圆柱形，包含罐身、上盖和下底，罐身高10cm，上盖和下底直径均为5cm。该企业使用两种不一样规格镀锡板原料：规格1镀锡板为正方形，边长24cm；规格2镀锡板为长方形，长、宽分别为32cm和28cm。因为生产设备和生产工艺限制，对于规格1镀锡板原料，只能够按照模式1、模式2或模式3进行冲压；对于规格2镀锡板原料只能按照模式4进行冲压。使用模式1、模式2、模式3、模式4进行每次冲压所需要时间分别为1.5s、2s、1s、3s。2、易拉罐下料10/10/第82页

该工厂每七天工作40小时，每七天可供使用规格1、规格2镀锡板原料分别为5万张和2万张。当前每只易拉罐利润为0.10元，原料余料损失为0.001元/平方厘米（假如周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。问工厂应怎样安排每七天生产？10/10/第83页板材规格2：长方形，32

28cm，2万张。问题分析模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上盖下底罐身罐身高10cm，上盖、下底直径均5cm。

板材规格1：正方形，边长24cm，5万张。10/10/第84页

罐身个数底、盖个数余料损失（cm2）冲压时间（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形边长24cm问题分析计算各种模式下余料损失上、下底直径d=5cm，罐身高h=10cm。模式1余料损失242-10

d2/4-dh=222.6cm210/10/第85页问题分析目标:易拉罐利润扣除原料余料损失后净利润最大

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

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

约束条件

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

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

配套约束y1~易拉罐个数；y2~不配套罐身；y3~不配套底、盖。罐身底、盖1102401645产量x1x2x3x4即使xi和y1，y2，y3应是整数，不过因生产量很大，能够把它们看成实数，从而用线性规划模型处理。10/10/第88页LINDO发出警告信息：“数据之间数量级差异太大，提议进行预处理，缩小数据之间差异”模型求解 OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X40.0000000.000000Y20.0000000.223331Y30.0000000.03648410/10/第89页模型中数据不平衡警告信息10/10/第90页 输入LINDO:!易拉罐下料：均衡数据Max0.100y1-0.2226x1-0.1833x2-0.2618x3-0.1695x4-0.1571y2-0.0196y3s.t. 1.5x1+2.0x2+1.0x3+3.0x4<=14.4 x1+x2+x3<=5 x4<=2 x1+2x2+4x4-y1>=0 10x1+4x2+16x3+5x4-2y1>=0 x1+2x2+4x4-y1-y2=0 10x1+4x2+16x3+5x4-2y1-y3=0将全部决议变量扩大10000倍（xi~万张，yi~万件）

10/10/第91页模式2生产40125张，模式3生产3750张，模式4生产0张，共产易拉罐160250个(罐身和底、盖无剩下)，净利润为4298元

OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y20.0000000.223331Y30.0000000.036484求解得到：10/10/第92页下料问题建模确定下料模式结构优化模型规格不太多，可枚举下料模式，建立整数线性规划模型，不然要结构整数非线性规划模型，求解困难，可用缩小可行域方法进行化简，但要确保最优解存在。一维问题（如钢管下料）二维问题（如易拉罐下料）详细问题详细分析（比较复杂）10