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

《数学规划及软件市公开课一等奖百校联赛特等奖课件.pptx》由会员分享，可在线阅读，更多相关《数学规划及软件市公开课一等奖百校联赛特等奖课件.pptx（160页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7/1/2024 11:37 PM7/1/2024 11:37 PM 王文祥王文祥.7数学规划模型、案例与数学规划模型、案例与软件求解软件求解10/10/第1页7/1/2024 11:37 PM7/1/2024 11:37 PM一一.数学规划模型与优化软件介绍数学规划模型与优化软件介绍二二.LINDO/LINGO.LINDO/LINGO软件软件Outline四四.LINGO LINGO建模语言建模语言 三三.建模实例建模实例10/10/第2页7/1/2024 11:37 PM7/1/2024 11:37 PM数学规划数学规划是优化问题一个分支，起始于是优化问题一个分支，起始于2020世纪世纪3

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

3、介绍10/10/第3页7/1/2024 11:37 PM7/1/2024 11:37 PM约约束束条条件件决议变量决议变量数学规划模型普通形式数学规划模型普通形式目标函数目标函数可行域三要素：三要素：决议变量决议变量；目标函数目标函数；约束条件约束条件可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)“受约束于受约束于”之意10/10/第4页7/1/2024 11:37 PM7/1/2024 11:37 PM数学规划类型数学规划类型连续规划连续规划:全部决议变量取值均全部决议变量取值均 为连续数值为连续数值(实数实数)离散规划离散规划:部分或全部决议变量部分或全部

4、决议变量 只取离散数值只取离散数值10/10/第5页7/1/2024 11:37 PM7/1/2024 11:37 PM线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决议变量决议变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)普通整数规划，普通整数规划，0-1

5、（整数）规划（整数）规划连连续续规规划划离离散散规规划划数学规划数学规划(Mathematical Programming Mathematical Programming)10/10/第6页7/1/2024 11:37 PM7/1/2024 11:37 PM惯用优化软件惯用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱/mathematica优化程序包优化程序包3.EXCEL软件优化功效软件优化功效4.SAS(统计分析统计分析)软件优化功效软件优化功效10/10/第7页7/1/2024 11:37 PM7/1/2024 11:37 PMLINDO企业软件产品

6、简明介绍企业软件产品简明介绍美国芝加哥美国芝加哥(Chicago)大学大学LinusSchrage教授于教授于1980年前后开发年前后开发,以后成立以后成立LINDO系统企业系统企业（LINDOSystemsInc.），），网址：网址：http:/LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer10/10/第8页7/1/2024 11:37 PM7/1/2024 11:37 PMLINDO和和LINGO能求解数学规划模型能求解数学规划模型LINGOLINDO数学规划模型数学规划模

7、型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续规划连续规划整数规划整数规划(IP)10/10/第9页7/1/2024 11:37 PM7/1/2024 11:37 PMLINDO 是专门用于求解数学规划软件包。是专门用于求解数学规划软件包。LINDO 执行速度很快、易于方便输入，所以在数学、科研执行速度很快、易于方便输入，所以在数学、科研和工业界得到广泛应用。和工业界得到广泛应用。LINDO 主要用于解线性规划、二次规划。也能够主要用于解线性规划、二次规划。也能够用于线性方程组求解以及代数方程求根等。用于线性方程组求解以及代数方程求根等。LINDO 中包含

8、了建模语言和许多惯用数学函数中包含了建模语言和许多惯用数学函数（包含大量概论函数），可供使用者建立规划问题（包含大量概论函数），可供使用者建立规划问题时调用。时调用。普通用普通用LINDO（Linear Interactive and Discrete Optimizer）处理线性规划）处理线性规划二二.LINDO/LINGO LINDO/LINGO软件介绍软件介绍10/10/第10页7/1/2024 11:37 PM7/1/2024 11:37 PM最大规模模型非零系数能够到达最大规模模型非零系数能够到达1,000,0001,000,000个个最大变量个数能够到达最大变量个数能够到达100,

9、000100,000个，最大目标函数个，最大目标函数和约束条件个数能够到达和约束条件个数能够到达3 3个个最大整数变量个数能够到达最大整数变量个数能够到达100,000100,000个个 LINDO 6.1 学生版至多可求解多达学生版至多可求解多达300 个变量和个变量和150 个约束规划问题个约束规划问题10/10/第11页7/1/2024 11:37 PM7/1/2024 11:37 PM1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快计算能力强4.内置建模语言提供内部函数较少语句直观描述大规模优化模型5.引入集合轻易建模6.数据交换方便(与EXCEL和数据库)LINGO

10、 LINGO软件主要功效和特点软件主要功效和特点10/10/第12页7/1/2024 11:37 PM7/1/2024 11:37 PM例例1 简单线性规划（简单线性规划（LP）问题：）问题：在在空白模型窗口中输入这个空白模型窗口中输入这个LP模型：模型：max 2x+3yst 4x+3y=10 3x+5y12end10/10/第13页7/1/2024 11:37 PM7/1/2024 11:37 PM如图：如图：10/10/第14页7/1/2024 11:37 PM7/1/2024 11:37 PMLINDO程序有以下特点：程序有以下特点：程序以程序以“MAX”（或（或“MIN”）开始，表示

11、目标最大化（或）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表示式和约束表示式；最小化）问题，后面直接写目标函数表示式和约束表示式；目标函数和约束之间用目标函数和约束之间用“ST”分开；（或用分开；（或用“s.t.”）程序以程序以“END”结束（结束（“END”也能够省略）。也能够省略）。系数与变量之间乘号必须省略。系数与变量之间乘号必须省略。系统对目标函数所在行自动生成行名系统对目标函数所在行自动生成行名“1）”,对约束默认对约束默认行名分别是行名分别是“2)”“3)”，用户也能够自己输入行名；行名，用户也能够自己输入行名；行名放在对应约束之前。放在对应约束之前。书写相当灵活，无

12、须对齐，不区分字符大小写。书写相当灵活，无须对齐，不区分字符大小写。默认全部变量都是非负默认全部变量都是非负,所以无须输入非负约束。所以无须输入非负约束。约束条件中约束条件中“=”可分别用可分别用“”代替。代替。一行中感叹号一行中感叹号“！”后面文字为是注释语句，可增强程序后面文字为是注释语句，可增强程序可读性，不参加模型建立。可读性，不参加模型建立。10/10/第15页7/1/2024 11:37 PM7/1/2024 11:37 PM模型求解：模型求解：用鼠标点击工具栏中图标用鼠标点击工具栏中图标 ，或从菜单中选择或从菜单中选择Solve|Solve（Ctrl+S）命令命令LINDO首先开

13、始编译这个首先开始编译这个模型，编译没有错误则开模型，编译没有错误则开始求解；始求解；求解时会首先显示如右图求解时会首先显示如右图所表示所表示LINDO“求解器运行状态窗口求解器运行状态窗口”。10/10/第16页7/1/2024 11:37 PM7/1/2024 11:37 PM求解器运行状态窗口显示对应信息及含义：求解器运行状态窗口显示对应信息及含义：名称名称含含义义Status当前状态显示当前求解状态：“Optimal”表示已抵达最优解；其它可能显示还有三个：Feasible(可行解),Infeasible(不可行),Unbounded(最优值无界)。Iterations迭代次数显显示迭

14、代次数：示迭代次数：“2”表示表示经过经过了了2次迭代。次迭代。Infeasibility不可行性约束不满足量(即各个约束条件不满足“数量”和)：“0”表示解是可行。Objective当前目标值显示目标函数当前值：7.45455。BestIP整数规划当前最正确目标值显示整数规划当前最正确目标值：“N/A”（NoAnswer）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（IP）。10/10/第17页7/1/2024 11:37 PM7/1/2024 11:37 PM名称含义IPBound整数规划界显示整数规划界（对最大化问题显示上界；对最小化问题，显示下界）Branches分枝数

15、显示分枝定界算法已经计算分枝数：Elapsed Time所用时间显显示示计计算所用算所用时间时间（秒）：（秒）：“0.00”说说明明计计算太快了，用算太快了，用时还时还不到不到0.005秒。秒。UpdateInterval刷新本界面时间间隔显示和控制刷新本界面时间间隔：“1”表示1秒；用户能够直接在界面上修改这个时间间隔。InterruptSolver中止求解程序当模型规模比较大时，求解时间会很长，能够在程序运行过程中用鼠标点击该按钮终止计算。Close关闭该该按按钮钮是关是关闭闭状状态态窗口，并不窗口，并不终终止止计计算算10/10/第18页7/1/2024 11:37 PM7/1/2024

16、 11:37 PM紧接着弹出一对话框，问询你是否需要做灵敏性分析紧接着弹出一对话框，问询你是否需要做灵敏性分析（DO RANGE(SENSITIVITY)ANALYSIS?）先选）先选择择“否（否（N）”按钮，这个窗口就会关闭。然后，再按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。把状态窗口也关闭。10/10/第19页7/1/2024 11:37 PM7/1/2024 11:37 PM汇报窗口用鼠标选择用鼠标选择“Window|Reports Window”（汇报窗口），（汇报窗口），就能够查看该窗口内容就能够查看该窗口内容 10/10/第20页7/1/2024 11:37 PM7/1/2

17、024 11:37 PM输出结果表示意思是：“LP OPTIMUM FOUND AT STEP2”表示单纯形法在两次迭代（旋转）后得到最优解。表示单纯形法在两次迭代（旋转）后得到最优解。“OBJECTIVE FUNCTION VALUE 1)7.454545”表示最优目标值为表示最优目标值为7.454545.（注意：在（注意：在LINDO中目标函数中目标函数所在行总是被认为是第所在行总是被认为是第1行，这就是这里行，这就是这里“1）”含义）。含义）。10/10/第21页7/1/2024 11:37 PM7/1/2024 11:37 PM“VALUE”给出最优解中各变量给出最优解中各变量(VAR

18、IABLE)值值:X=1.272727,Y=1.636364.“REDUCED COST”给出最优单纯形表中目标函数行（第给出最优单纯形表中目标函数行（第1行）中变量对应系数行）中变量对应系数.“SLACK OR SURPLUS（松驰或剩下）（松驰或剩下）”给出约束对应松给出约束对应松驰变量值驰变量值:第第2、3行松驰变量均为行松驰变量均为0,说明对于最优解来讲，说明对于最优解来讲，两个约束（第两个约束（第2、3行）均取等号，即都是紧约束。行）均取等号，即都是紧约束。10/10/第22页7/1/2024 11:37 PM7/1/2024 11:37 PM“DUAL PRICES”给出对偶价格（

19、或影子价格）值给出对偶价格（或影子价格）值:表示表示最最优解下优解下“资源资源”增加增加1单位时单位时“效益效益”增量。增量。第第2、3行对偶价格分别为行对偶价格分别为.090909，.545455。“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代。表示用单纯形法进行了两次迭代。10/10/第23页7/1/2024 11:37 PM7/1/2024 11:37 PM使用使用LINDOLINDO一些注意事项一些注意事项1.“”（或（或“=”（或（或“=”）功效相）功效相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不

20、能超出变量名以字母开头，不能超出8个字符个字符4.变量名不区分大小写（包含变量名不区分大小写（包含LINDO中关键字）中关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结结束束7.行中注有行中注有“!”符号后面部分为注释。如符号后面部分为注释。如:!ItsComment.8.在模型任何地方都能够用在模型任何地方都能够用“TITLE”对模型命名对模型命名（最多（最多72个字符），如：个字符），如：TITLEThisModelisonlyanExample10/10/第

21、24页7/1/2024 11:37 PM7/1/2024 11:37 PM9.变量不能出现在一个约束条件右端变量不能出现在一个约束条件右端10.表示式中不接收括号表示式中不接收括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表示式应化简，如表示式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定全部变量非负；可在模型缺省假定全部变量非负；可在模型“END”语句后用语句后用“FREEname”将变量将变量name非负假定取消非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上下

22、界设定变量上下界比如：比如：“subx110”作用等价于作用等价于“x1=10”但用但用“SUB”和和“SLB”表示上下界约束不计入模型约表示上下界约束不计入模型约束，也不能给出其松紧判断和敏感性分析。束，也不能给出其松紧判断和敏感性分析。使用使用LINDOLINDO一些注意事项一些注意事项10/10/第25页7/1/2024 11:37 PM7/1/2024 11:37 PM14.“END”后对后对0-1变量说明：变量说明：INTn或或INTname15.“END”后对整数变量说明：后对整数变量说明：GINn或或GINname使用使用LINDOLINDO一些注意事项一些注意事项16.简单错误

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

24、命令(FREE(FREE、SUBSUB、SLB)SLB)作用作用求解以下求解以下LP问题：问题：这个模型中对变量这个模型中对变量x没有非负限制，对没有非负限制，对y有上限限制，有上限限制，对对z有下限限制。用有下限限制。用FREE、SUB、SLB三个命令三个命令能够实现这些功效。能够实现这些功效。10/10/第27页7/1/2024 11:37 PM7/1/2024 11:37 PMMAX 2x 3y+4zS.T.con2)4 x+3y+2z =10con3)-3x+5 y-z 8con5)-5x-y-z 2ENDfree x !说明：变量说明：变量x没有非负限制没有非负限制sub y 20

25、!说明：变量说明：变量y上界为上界为20slb z 30 !说明：变量说明：变量z下界为下界为30详细输入以下：详细输入以下：求解得到结果：最大值为求解得到结果：最大值为122，最优解为，最优解为x=-17，y=0，z=39。能够看出能够看出y上界（上界（20）在最优解中并没有到达，）在最优解中并没有到达，z下界（下界（30）也没有到达，所）也没有到达，所以模型中去掉以模型中去掉“sub y 20”和和“slb z 30”两个语句，得到结不变。两个语句，得到结不变。但因为最优解中但因为最优解中x取值为负值，所以取值为负值，所以“free x”这个语句确实是不能少。不妨试这个语句确实是不能少。不

26、妨试一下，去掉这个语句后效果会怎样？一下，去掉这个语句后效果会怎样？10/10/第28页7/1/2024 11:37 PM7/1/2024 11:37 PMLINGOLINGO入门入门设有线性规划模型以下：设有线性规划模型以下：10/10/第29页7/1/2024 11:37 PM7/1/2024 11:37 PMLP问题在lindo和lingo中不一样输入形式Lindo:max2x+3yst4x+3y103x+5y12endLingo:max=2*x+3*y;4*x+3*y10;3*x+5*y12;（1）将目标函数表示方式从“MAX”变成了“MAX=”（2）“ST”在LINGO模型中不再需要

27、，所以被删除了（3）每个系数与变量间增加了运算符“*”（即乘号不能省略）（4）每行（目标、约束和说明语句）后面均增加了一个分号“;”（5）模型结束标志“END”也被删除了（LINGO中只有当模型以“MODEL:”开始时才能以“END”结束）。10/10/第30页7/1/2024 11:37 PM7/1/2024 11:37 PMLINGO语法规则1.最大值MAX=,最小值MIN=2.语句必须以分号”;”结束 每行可多个语句 语句可跨行3.变量名由字母、数字和下划线组成 以字母开头 长度 不超32个字符 不区分大小写4.默认决议变量非负 其它要求可做说明5.模型以MODEL：开头，以END结束(

28、此结构也可省略）6.注释以！开始，以 ;结束；7.能够用表示表示=10/10/第31页7/1/2024 11:37 PM7/1/2024 11:37 PM程序语句输入备注：程序语句输入备注：LINGO总是依据总是依据“MAX=”或或“MIN=”寻找目标函数，而寻找目标函数，而除注释语句和除注释语句和TITLE语句外其它语句都是约束条件，所语句外其它语句都是约束条件，所以语句次序并不主要以语句次序并不主要。限定变量取整数值语句为限定变量取整数值语句为“GIN(X1)”和和“GIN(X2)”，不能够写成，不能够写成“GIN(2)”，不然，不然LINGO将把这个模型看将把这个模型看成没有整数变量。成

29、没有整数变量。LINGO中函数一律需要以中函数一律需要以“”开头，其中整型变量函开头，其中整型变量函数（数（BIN、GIN）和上下界限定函数（）和上下界限定函数（FREE、SUB、SLB）与）与LINDO中命令类似。而且中命令类似。而且0/1变量函数是变量函数是BIN函函数。数。10/10/第32页7/1/2024 11:37 PM7/1/2024 11:37 PM一个简单一个简单LINGO程序程序例例直接用LINGO来解以下二次规划问题：输入窗口以下：输入窗口以下：10/10/第33页7/1/2024 11:37 PM7/1/2024 11:37 PM输出结果：输出结果：运行菜单命令运行菜单

30、命令“LINGO|Solve”最优整数解最优整数解X=(35，65)最大利润最大利润=11077.510/10/第34页7/1/2024 11:37 PM7/1/2024 11:37 PMLINGO求解实例求解实例例例 1 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页7/1/2024 11:37 PM7/1/2024 11:37 PMGlobal optimal solution found at iteration:2 Objective value:18.33333 Varia

31、ble Value Reduced Cost X1 8.333333 0.000000 X2 0.000000 0.6666667 X3 0.000000 4.333333 X4 1.666667 0.000000 Row Slack or Surplus Dual Price 1 18.33333 1.000000 2 0.000000 0.3333333 3 0.000000 1.666667运行结果以下运行结果以下:10/10/第36页7/1/2024 11:37 PM7/1/2024 11:37 PM看完例看完例1 1后后,能解下面这个问题吗能解下面这个问题吗?例例 2 210/10/

32、第37页7/1/2024 11:37 PM7/1/2024 11:37 PM例例 3 3model:!this is an integer programming problem;max=4*x1+3*x2;4*x1+x2=10;2*x1+3*x2=0;end10/10/第42页7/1/2024 11:37 PM7/1/2024 11:37 PM Local optimal solution found at iteration:37 Objective value:-6.000000 Variable Value Reduced Cost X1 1.212809 0.000000 X2 1.

33、212809 0.000000 X3 0.2412201 0.000000 Row Slack or Surplus Dual Price 1 -6.000000 -1.000000 2 0.000000 2.000000 3 0.000000 -2.425619运行结果以下运行结果以下:10/10/第43页7/1/2024 11:37 PM7/1/2024 11:37 PM例例1加工奶制品生产计划加工奶制品生产计划1桶牛奶3千克A112小时8小时4千克A2或赢利24元/千克赢利16元/千克50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100千克千克A1制订生产计划，使天天赢利最大制

34、订生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增加到赢利增加到30元元/千克，应否改变生产计划？千克，应否改变生产计划？天天：天天：三、建模实例三、建模实例10/10/第44页7/1/2024 11:37 PM7/1/2024 11:37 PM1桶牛奶3千克A112小时8小时4千克A2或赢利24元/千克赢利16元/千克x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2原料供给原料供给劳动时间劳动时间加工能力加工能力决议变量决议

35、变量 目标函数目标函数 天天赢利天天赢利约束条件约束条件非负约束非负约束线性线性规划规划模型模型(LP)时间时间480小时小时至多加工至多加工100千克千克A150桶牛奶桶牛奶天天天天10/10/第45页7/1/2024 11:37 PM7/1/2024 11:37 PM模型求解模型求解 软件实现软件实现 LINDOmax72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

36、ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。10/10/第46页7/1/2024 11:37 PM7/1/2024 11:37 PM结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230

37、.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩下原料无剩下时间无剩下时间无剩下加工能力剩下加工能力剩下40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩下为零约束为紧约束（有效约束）剩下为零约束为紧约束（有效约束）10/10/第47页7/1/2024 11:37 PM7/1/2024 11:37 PM结果解释结果解释 OBJECTI

38、VEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”增量增量原料增加原料增加1单位单位,利润增加利润增加48时间增加时间增加1单位单位,利润增加利润增加2加工能力增加不影响利润加工能力增加不影响利润影子价格影子价格35元

39、可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用暂时工人付出工资最多每小时几元？聘用暂时工人付出工资最多每小时几元？2元！元！10/10/第48页7/1/2024 11:37 PM7/1/2024 11:37 PMRANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERAN

40、GESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允许改变范围数系数允许改变范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1赢利增加到赢利增加到30元元/千克，应否改变生产计千克，应否改变生产计划划x1系数由系数由24 3=72增加增加为为30 3

41、=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)10/10/第49页7/1/2024 11:37 PM7/1/2024 11:37 PM结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERH

42、SINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义影子价格有意义时约束右端允许时约束右端允许改变范围改变范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，天天最多买多少？桶牛奶，天天最多买多少？最多买最多买10桶桶(目标函数不变目标函数不变)10/10/第50页7/1/2024 11:37 PM7/1/2024 11:37 PM 假如生产某一类型汽车，则最少要生产假如生产某一类型汽车，则最少

43、要生产8080辆，辆，那么最优生产计划应作何改变？那么最优生产计划应作何改变？例例2汽车厂生产计划汽车厂生产计划汽车厂生产三种类型汽车，已知各类型每辆车对钢材、汽车厂生产三种类型汽车，已知各类型每辆车对钢材、劳动时间需求，利润及工厂每个月现有量。劳动时间需求，利润及工厂每个月现有量。小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂利润最大。制订月生产计划，使工厂利润最大。10/10/第51页7/1/2024 11:37 PM7/1/2024 11:37 PM设

44、每个月生产小、中、大型汽车数量分别为设每个月生产小、中、大型汽车数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)10/10/第52页7/1/2024 11:37 PM7/1/2024 11:37 PM模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.

45、5161290.000000X2167.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，经过比较可能得到更优解。，经过比较可能得到更优解。但必须检验它们是否满足

46、约束条件。为何？但必须检验它们是否满足约束条件。为何？10/10/第53页7/1/2024 11:37 PM7/1/2024 11:37 PMIP可用可用LINDO直接求解直接求解整数规划整数规划(IP)“gin3”表示表示“前前3个个变量为整数变量为整数”，等价于：，等价于：ginx1ginx2ginx3IP最优解最优解x1=64，x2=168，x3=0，最优值，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x30y=110/10/第60页7/1/2024 11:37 PM7/1/2024 11:37 PM例例4:4:员工

47、聘用方案决议变量决议变量：周一至周日天天：周一至周日天天(新新)聘用人数聘用人数x1,x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日天天需要人数：周一至周日天天需要人数10/10/第61页7/1/2024 11:37 PM7/1/2024 11:37 PM连续工作连续工作5天天周一工作应是周一工作应是(上上)周四至周一聘用周四至周一聘用设系统已进入稳态设系统已进入稳态聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)10/10/第62页7/1/2024 11:37 PM7/1/2024 11:37 PM首先在首先在LINDO模型窗口输入模型

48、模型窗口输入模型:MIN X1+X2+X3+X4+X5+X6+X7SUBJECT TOMON)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=90ENDGIN 7其中其中“GIN 7”表示表示7个变量都是普通整数变量。个变量都是普通整数变量。（依然默认为取值是非负）（依然默认为取值是非负）10/10/第63页7/1/2024 11:37 PM7/1/2

49、024 11:37 PM求解后状态窗口中与整数相关三个域有了相关结果求解后状态窗口中与整数相关三个域有了相关结果:“Best IP：94”表示当前表示当前得到最好整数解目标函数得到最好整数解目标函数值为值为94（人）。（人）。“IP Bound：93.5”表示表示该整数规划目标值下界为该整数规划目标值下界为93.5（人）。（人）。“Branches：1”表示分枝表示分枝数为数为1（即在第（即在第1个分枝中个分枝中就找到了最优解）。就找到了最优解）。10/10/第64页7/1/2024 11:37 PM7/1/2024 11:37 PM OBJECTIVE FUNCTION VALUE 1)94

50、.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON)0.000000 0.000000 TUE)2.000000 0.000000 WED)8.000000 0.000000 THU)0.000000 0.0