数学规划与软件课件

*

王文祥

2013.7数学规划模型、案例与

软件求解*数学规划模型、案例与

软件求解*一.数学规划模型与优化软件简介二.LINDO/LINGO软件Outline四.LINGO建模语言

三.建模实例*一.数学规划模型与优化软件简介二.LINDO/LING*

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

一.数学规划模型与优化软件简介*•数学规划是优化问题的一个分支，起始于20*约束条件决策变量数学规划模型的一般形式目标函数可行域

三要素：决策变量；目标函数；约束条件可行解（只满足约束）与最优解(取到最优值)“受约束于”之意．*约束条件决策变量数学规划模型的一般形式目标函数可行域三要*数学规划类型连续规划:全部决策变量取值均为连续数值(实数)离散规划:部分或全部决策变量只取离散数值*数学规划类型连续规划:全部决策变量取值均*

线性规划(LP)

目标和约束均为线性函数

非线性规划(NLP)

目标或约束中存在非线性函数

二次规划(QP)

目标为二次函数、约束为线性

整数规划(IP)

决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)

纯整数规划(PIP),混合整数规划(MIP)

一般整数规划，0-1（整数）规划连续规划离散规划数学规划(MathematicalProgramming)*线性规划(LP)目标和约束均为线性函数连*常用优化软件

LINDO/LINGO软件MATLAB优化工具箱/mathematica优化程序包EXCEL软件的优化功能SAS(统计分析)软件的优化功能*常用优化软件LINDO/LINGO软件*LINDO公司软件产品简要介绍

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

LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer*LINDO公司软件产品简要介绍美国芝加哥(Chicag*LINDO和LINGO能求解的数学规划模型LINGOLINDO数学规划模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续规划整数规划(IP)*LINDO和LINGO能求解的数学规划模型数学规划模型线性*LINDO是专门用于求解数学规划的软件包。LINDO执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。LINDO中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。一般用LINDO（LinearInteractiveandDiscreteOptimizer）解决线性规划二.LINDO/LINGO软件简介*LINDO是专门用于求解数学规划的软件包。LINDO执*最大规模的模型的非零系数可以达到1,000,000个最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个最大整数变量个数可以达到100,000个

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

LINGO软件的主要功能和特点*1.求解线性规划和非线性规划问题LINGO软件的主要功*例1简单的线性规划（LP）问题：在空白的模型窗口中输入这个LP模型：max2x+3yst4x+3y<=103x+5y<12end*例1简单的线性规划（LP）问题：在空白的模型窗口*如图：

*如图：*LINDO程序有以下特点：

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

“求解器运行状态窗口”。*模型求解：用鼠标点击工具栏中的图标，LIND*求解器运行状态窗口显示的相应信息及含义：

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

Infeasibility

不可行性约束不满足的量(即各个约束条件不满足的“数量”的和)：“0”表示解是可行的。Objective当前目标值显示目标函数当前的值：7.45455。BestIP整数规划当前最佳目标值显示整数规划当前的最佳目标值：“N/A”

（NoAnswer）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（IP）。

*求解器运行状态窗口显示的相应信息及含义：名称含义Stat*名称含义IPBound整数规划的界显示整数规划的界（对最大化问题显示上界；对最小化问题，显示下界）Branches分枝数显示分枝定界算法已经计算的分枝数：ElapsedTime所用时间显示计算所用时间（秒）：“0.00”说明计算太快了，用时还不到0.005秒。UpdateInterval刷新本界面时间间隔显示和控制刷新本界面的时间间隔：“1”表示1秒；用户可以直接在界面上修改这个时间间隔。InterruptSolver中断求解程序当模型规模比较大时，求解时间会很长，可以在程序运行过程中用鼠标点击该按钮终止计算。Close关闭该按钮是关闭状态窗口，并不终止计算*名称含义IPBound显示整数规划的界（对最大化问题显示*紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。*紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORA*报告窗口用鼠标选择“Window|ReportsWindow”（报告窗口），就可以查看该窗口的内容*报告窗口用鼠标选择“Window|ReportsW*输出结果表示的意思是：“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代（旋转）后得到最优解。“OBJECTIVEFUNCTIONVALUE1)7.454545”

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

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

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

!It’sComment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：

TITLEThisModelisonlyanExample*使用LINDO的一些注意事项“>”（或“<”）号与“>=”*变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x1<=10”

但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。使用LINDO的一些注意事项*变量不能出现在一个约束条件的右端使用LINDO的一些注意事*14.“END”后对0-1变量说明：INTn

或INTname15.“END”后对整数变量说明：GINn

或GINname使用LINDO的一些注意事项16.

简单错误的检查和避免：输入模型时可能会有某些输入错误.当问题规模较大时,要查找错误是比较困难的。在LINDO中有一些可帮助寻找错误的功能，其中之一就是菜单命令“Report|Picture（Alt+5）”,它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。*14.“END”后对0-1变量说明：INTn或IN*三个变量范围限定命令(FREE、SUB、SLB)的作用

求解如下的LP问题：这个模型中对变量x没有非负限制，对y有上限限制，对z有下限限制。用FREE、SUB、SLB三个命令可以实现这些功能。*三个变量范围限定命令(FREE、SUB、SLB)的作用求*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”这个语句确实是不能少的。不妨试一下，去掉这个语句后效果会怎样？*MAX2x–3y+4z具体输入如下：求解得到*

LINGO入门设有线性规划模型如下：*LINGO入门设有线性规划模型如下：*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”

结束）。

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

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

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

Objectivevalue:-1.000000VariableValueReducedCostX10.99999950.000000X20.99999920.000000RowSlackorSurplusDualPrice1-1.000000-1.000000运行结果如下:*Localoptimalsolutionfound*例5model:min=-3*x1^2-x2^2-2*x3^2;x1^2+x2^2+x3^2-3=0;-x1+x2>=0;end*例5model:*

Localoptimalsolutionfoundatiteration:37

Objectivevalue:-6.000000VariableValueReducedCostX11.2128090.000000X21.2128090.000000X30.24122010.000000RowSlackorSurplusDualPrice1-6.000000-1.00000020.0000002.00000030.000000-2.425619运行结果如下:*Localoptimalsolutionfound*例1加工奶制品的生产计划1桶牛奶3千克A1

12小时8小时4千克A2

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

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

可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/千克，应否改变生产计划？每天：三、建模实例*例1加工奶制品的生产计划1桶牛奶3千克A112*1桶牛奶3千克A1

12小时8小时4千克A2

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

x2桶牛奶生产A2

原料供应

劳动时间

加工能力

决策变量

目标函数

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

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

50桶牛奶每天*1桶牛奶3千克A112小时8小时4千克A2或获利*模型求解

软件实现

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元。*模型求解软件实现LINDOmax72x1+64x*结果解释

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三种资源“资源”剩余为零的约束为紧约束（有效约束）*结果解释OBJECTIVEFUNCTIONV*结果解释

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元！*结果解释OBJECTIVEFUNCTI*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，在允许范围内不变！(约束条件不变)*RANGESINWHICHTHEBASISIS*结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶(目标函数不变)*结果解释RANGESINWHICHTHEBASI*

如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例2汽车厂生产计划

汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。

小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234

制订月生产计划，使工厂的利润最大。*如果生产某一类型汽车，则至少要生产80辆，那么最优的*设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)*设每月生产小、中、大型汽车的数量分别为x1,x2,x3*模型求解

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，通过比较可能得到更优的解。

但必须检验它们是否满足约束条件。为什么？*模型求解3）模型中增加条件：x1,x2,x3均*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结果输出*IP可用LINDO直接求解整数规划(IP)“gin3”表*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或

80*LINDO中对0-1变量的限定：方法：引入0-1变量，化为*应如何安排原油的采购和加工

？

例3原油采购与加工

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

库存1000吨汽油甲(A

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

60%)*应如何安排原油的采购和加工？例3原油采购与加工*决策变量

目标函数问题分析

利润：销售汽油的收入-购买原油A的支出难点：原油A的购价与购买量的关系较复杂甲(A

50%)AB乙(A

60%)购买x

x11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？*决策变量目标函数问题分析利润：销售汽油的收入-购*原油供应

约束条件x

500吨单价为10千元/吨；

500吨

x

1000吨，超过500吨的8千元/吨；1000吨

x

1500吨，超过1000吨的6千元/吨。目标函数购买x

ABx11x12x21x22库存500吨库存1000吨*原油供应约束条件x500吨单价为10千元/吨；目标*

目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解。

汽油含原油A的比例限制约束条件甲(A

50%)AB乙(A

60%)x11x12x21x22*目标函数中c(x)不是线性函数，是非线性规划；汽油含原油*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=1*y1,y2,y3=1~以价格10,8,6(千元*例4:员工聘用方案决策变量：周一至周日每天(新)聘用人数x1,x2,x7目标函数：7天(新)聘用人数之和约束条件：周一至周日每天需要人数*例4:员工聘用方案决策变量：周一至周日每天(新)聘用人数*连续工作5天周一工作的应是(上)周四至周一聘用的设系统已进入稳态聘用方案整数规划模型(IP)*连续工作5天周一工作的应是(上)周四至周一聘用的设系统已进*首先在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个变量都是一般整数变量。

（仍然默认为取值是非负的）*首先在LINDO模型窗口输入模型:MINX1*求解后状态窗口中与整数相关的三个域有了相关结果:“BestIP：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IPBound：93.5”表示该整数规划目标值的下界为93.5（人）。“Branches：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。*求解后状态窗口中与整数相关的三个域有了相关结果:“Best*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求解结果的报告窗口如下：*OBJECTIVEFUNCTIONVALUE求解结果*生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小例5钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大*生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小例*

某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。

1) 现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？

2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？1、钢管下料*某钢管零售商从钢管厂进货，将钢管按照顾客的要求切*问题1）的求解

问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。

其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表所示。*问题1）的求解 问题分析首先，应当确定哪些切割模式是可*为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小*为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料*xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量

目标1（总余量）模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015整数约束：xi为整数*xi~按第i种模式切割的原料钢管根数(i=1,2,…7*模型求解将整数线性规划模型（加上整数约束）输入LINDO如下：

Title钢管下料-最小化余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7 *模型求解将整数线性规划模型（加上整数约束）输入LINDO*求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000

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

*求解可以得到最优解如下：OBJECTIVEFUNCTI*目标2（总根数）钢管下料问题1约束条件不变xi为整数*目标2（总根数）钢管下料问题1约束条件不变xi为整数*将整数线性规划模型（加上整数约束）输入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模型求解*将整数线性规划模型（加上整数约束）输入LINDO：Titl*求解，可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)25.00000 VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000*求解，可以得到最优解如下：OBJECTIVEFUNCTI*当余料没有用处时，通常以总根数最少为目标最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比*当余料没有用处时，通常以总根数最少为目标最优解：x2=1*钢管下料问题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米长的钢管的数量*钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增*满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数*满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管*增加约束，缩小可行域，便于求解原料钢管总根数下界：

特殊生产计划：对每根原料钢管模式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米*增加约束，缩小可行域，便于求解原料钢管总根数下界：特殊生*将模型输入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

*将模型输入LINGO如下：model:x1+x2+x3>*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根。*LINGO求解整数非线性规划模型Localoptimal*

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

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