整数线性规划学习教案.pptx

《整数线性规划学习教案.pptx》由会员分享，可在线阅读，更多相关《整数线性规划学习教案.pptx（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、会计学1整数整数(zhngsh)线性规划线性规划第一页，共17页。LINDOLINDO求解整数线性规划求解整数线性规划求解整数线性规划求解整数线性规划(xin xn(xin xn u u hu)hu)概述概述概述概述LINDO可用于求解线性纯整数规划或混合整数规划可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与模型的输入与LP问题类似问题类似(li s),但需在但需在END标志后定义整型标志后定义整型变量。变量。0/1型的变量可由型的变量可由INTEGER（可简写为（可简写为INT）命令来标识，）命令来标识，有以下两种可能的用法：有以下两种可能的用法：INT vname INT n

2、前者前者(qin zh)只将决策变量只将决策变量vname标识为标识为0/1型型,后者将当前模型中前后者将当前模型中前n 个变量标识为个变量标识为0/1型（模型中变量顺序由模型中输入型（模型中变量顺序由模型中输入时出现的先后顺序决定时出现的先后顺序决定,该顺序可由输出结果中的变量顺序查证是否一致）。该顺序可由输出结果中的变量顺序查证是否一致）。一般的整数变量可用命令一般的整数变量可用命令GIN（是（是GENERAL INTEGER的意思）的意思）,其使其使用方式及格式与用方式及格式与INT 命令相似。命令相似。第第2页页/共共17页页第1页/共17页第二页，共17页。例例例例2.6 2.6 员

3、工聘用员工聘用员工聘用员工聘用(pn yn(pn yn)问题问题问题问题 首先在首先在LINDO模型模型(mxng)窗口输窗口输入模型入模型(mxng):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其中其中(qzhng)“GIN 7”表示表示7个变量都是

4、一般整数变量。个变量都是一般整数变量。（仍然默认为取值是非负的）（仍然默认为取值是非负的）第第3页页/共共17页页第2页/共17页第三页，共17页。求解后状态求解后状态(zhungti)窗口中与整数相关的三个域有了相关结窗口中与整数相关的三个域有了相关结果果:“Best IP：94”表示表示(biosh)当前得到的最好当前得到的最好的整数解的目标函数值为的整数解的目标函数值为94（人）。（人）。“IP Bound：93.5”表示表示(biosh)该整数规划目标该整数规划目标值的下界为值的下界为93.5（人）。（人）。“Branches：1”表示表示(biosh)分枝数为分枝数为1（即（即在第在

5、第1个分枝中就找到了个分枝中就找到了最优解）。最优解）。我们前面说过，我们前面说过，LINDO求求解解IP用的是分枝定界法。用的是分枝定界法。显然，上面第二条显然，上面第二条“整数规划目标值的下界为整数规划目标值的下界为93.5（人）（人）”表明表明(biomng)至少要聘用至少要聘用93.5名员工，由于员工人数只能是整数，所以至名员工，由于员工人数只能是整数，所以至少要聘用少要聘用94（人）。而第一条说明目前得到的解就是聘用（人）。而第一条说明目前得到的解就是聘用94（人），所（人），所以已经是最优的了。以已经是最优的了。第第4页页/共共17页页第3页/共17页第四页，共17页。LP OPT

6、IMUM FOUND AT STEP 8 OBJECTIVE VALUE=93.3333359 SET X2 TO=4 AT 1,BND=-94.00 TWIN=-93.50 18 NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18 BOUND ON OPTIMUM:93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE.BRANCHES=1 PIVOTS=18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUT

7、ION.求解求解(qi ji)结果的报告窗口如下：结果的报告窗口如下：（接下页）（接下页）第第5页页/共共17页页第4页/共17页第五页，共17页。OBJECTIVE FUNCTION VALUE 1)94.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

8、 SURPLUS DUAL PRICES MON)0.000000 0.000000 TUE)2.000000 0.000000 WED)8.000000 0.000000 THU)0.000000 0.000000 FRI)0.000000 0.000000 SAT)0.000000 0.000000 SUN)0.000000 0.000000 NO.ITERATIONS=18 BRANCHES=1 DETERM.=1.000E 0第第6页页/共共17页页第5页/共17页第六页，共17页。报告窗口报告窗口(chungku)中前两行告诉我们：在中前两行告诉我们：在8次迭代后找到对应的线次迭代后

9、找到对应的线性规划（性规划（LP）问题的最优解，最优值）问题的最优解，最优值=93.3333359。LINDO求解求解IP用的是分枝定界法，紧接着几行显示的是分枝定界的信用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第息，在第1个分枝中设定个分枝中设定x2=4,并在该分枝中找到了整数解，而且就并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（是全局整数最优解，所以算法停止。旋转迭代（PIVOT）共）共18次。次。后面显示的是最后的最优解：后面显示的是最后的最优解：x=(0,4,40,2,34,10,4).松弛和剩余变量（松弛和剩余变量（SLACK OR SURP

10、LUS）仍然可以表示约）仍然可以表示约束的松紧程度，但目前束的松紧程度，但目前IP尚无相应完善尚无相应完善(wnshn)的敏感性分的敏感性分析理论，因此析理论，因此REDUCED COST和和DUAL PRICES的结果在整的结果在整数规划中意义不大。数规划中意义不大。第第7页页/共共17页页第6页/共17页第七页，共17页。例例例例2.7 2.7 游泳游泳游泳游泳(yuy(yuy ng)ng)队员的选拔问题（队员的选拔问题（队员的选拔问题（队员的选拔问题（0-10-1规划）规划）规划）规划）在LINDO模型窗口(chungku)中输入模型：MIN 66.8x11+75.6x12+87 x13

11、+58.6x14 +57.2x21+66 x22+66.4x23+53 x24 +78 x31+67.8x32+84.6x33+59.4x34 +70 x41+74.2x42+69.6x43+57.2x44 +67.4x51+71x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 21 x21+x22+x23+x24=1 x31+x32+x33+x34 21 x41+x42+x43+x44=1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+x23+x33+x43+x53=1 x14+x24+x34+x4

12、4+x54=1ENDINT 20其中其中(qzhng)“INT 20”表示表示20个变量都是个变量都是0-1整数变量整数变量 第第8页页/共共17页页第7页/共17页第八页，共17页。求解得到结果为：求解得到结果为：x14=x21=x32=x43=1,其它变量为其它变量为0，成绩为，成绩为253.2（秒）（秒）=413”2。即应当选派甲乙丙丁。即应当选派甲乙丙丁4人组成接力队，分别人组成接力队，分别(fnbi)参加自由泳、蝶泳、仰泳、蛙泳的比赛。参加自由泳、蝶泳、仰泳、蛙泳的比赛。由于这个问题中有由于这个问题中有20个个0-1变量变量(binling)，而最优解中肯定只有，而最优解中肯定只有其

13、中的其中的4个变量个变量(binling)取非零值取非零值“1”，所以要在一大堆变量，所以要在一大堆变量(binling)中去找少量的几个取非零值的变量中去找少量的几个取非零值的变量(binling)，这是，这是不太方便的。有没有办法只把取非零值的变量不太方便的。有没有办法只把取非零值的变量(binling)显示出显示出来呢？来呢？这是可以做到的：选择菜单命令这是可以做到的：选择菜单命令“Reports|Solution(Alt+0)”（这个命令的功能是要把最优解显示出来），这时会弹出（这个命令的功能是要把最优解显示出来），这时会弹出一个选择对话框（图一个选择对话框（图2-21），缺省的选项是

14、），缺省的选项是“Nonzeros Only（只（只显示非零值）显示非零值）”。按下对话框中的。按下对话框中的“OK”按钮，则报告窗口中的只按钮，则报告窗口中的只显示取非零值的变量显示取非零值的变量(binling)，这样阅读起来就很方便了。，这样阅读起来就很方便了。请注意，这个功能并不仅仅在整数规划中可以使用，在其他模型中请注意，这个功能并不仅仅在整数规划中可以使用，在其他模型中也是可以使用的，不妨试试就知道了。也是可以使用的，不妨试试就知道了。第第9页页/共共17页页第8页/共17页第九页，共17页。讨论讨论(toln)若考虑到丁、戊最近的状态，若考虑到丁、戊最近的状态，c43 由原来的由

15、原来的69.6变为变为75.2（秒），（秒），c54由原来的由原来的62.4变为变为57.5（秒）（秒）,试讨论试讨论对结果的影响。对结果的影响。这类似于线性规划中的敏感性分析这类似于线性规划中的敏感性分析,但是可惜的是，对于但是可惜的是，对于整数规划模型，一般没有与线性规划相类似的理论，此时整数规划模型，一般没有与线性规划相类似的理论，此时LINDO中所输出的敏感性分析结果通常是没有意义的，中所输出的敏感性分析结果通常是没有意义的，因此不能利用这个输出的敏感性分析结果。因此不能利用这个输出的敏感性分析结果。于是我们只好用于是我们只好用c43，c54 的新数据重新输入模型，用的新数据重新输入模

16、型，用LINDO求解得到：求解得到：x21=x32=x43=x51=1,其它变量其它变量为为0，成绩为，成绩为257.7（秒）（秒）=417”7。即应当选派乙丙丁戊。即应当选派乙丙丁戊4人组成接力队，分别人组成接力队，分别(fnbi)参加蝶泳、仰泳、蛙泳、参加蝶泳、仰泳、蛙泳、自由泳的比赛。自由泳的比赛。第第10页页/共共17页页第9页/共17页第十页，共17页。例例例例2.8 2.8 2.8 2.8 汽车汽车汽车汽车(qch)(qch)(qch)(qch)生产计划（混合整数规划）生产计划（混合整数规划）生产计划（混合整数规划）生产计划（混合整数规划）一汽车厂生产小、中、大三种类型一汽车厂生产

17、小、中、大三种类型(lixng)的汽车，已知各的汽车，已知各类型类型(lixng)每辆车对钢材、劳动时间的需求，利润以及每每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示：月工厂钢材、劳动时间的现有量如下表所示：小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234由于各种条件限制，如果生产由于各种条件限制，如果生产(shngchn)某一类型汽车，某一类型汽车，则至少要生产则至少要生产(shngchn)80辆。试制订月生产辆。试制订月生产(shngchn)计

18、划，使工厂的利润最大。计划，使工厂的利润最大。第第11页页/共共17页页第10页/共17页第十一页，共17页。模型模型(mxng)建建立与求解立与求解设每月生产小、中、大型汽车的数量设每月生产小、中、大型汽车的数量(shling)分别为分别为x1,x2,x3，（由于生产是一个月一个月连续进行的，所以这里可以合理地认为这（由于生产是一个月一个月连续进行的，所以这里可以合理地认为这个产量不一定非取整数不可，而是可以取实数）个产量不一定非取整数不可，而是可以取实数）设工厂的月利润为设工厂的月利润为z,在题目所给参数均不随生产数量在题目所给参数均不随生产数量(shling)变化变化的假设下，立即可得线

19、性规划模型：的假设下，立即可得线性规划模型：第第12页页/共共17页页第11页/共17页第十二页，共17页。但是，如果生产某一类型汽车，则至少要生产但是，如果生产某一类型汽车，则至少要生产80辆，这个约束怎么表辆，这个约束怎么表达？达？可以引入可以引入0-1变量，化为整数规划。设变量，化为整数规划。设y1只取只取0,1两个两个(lin)值，值，则则“x1=0 或或80”等价于等价于其中M为相当大的正数(zhngsh)，本例可取1000（x1不可能超过1000）。类似(li s)地有于是这个模型构成一个混合整数规划模型（既有一般的实数变量于是这个模型构成一个混合整数规划模型（既有一般的实数变量x

20、，又有，又有0-1变量变量y），用），用LINDO直接求解时，输入的最后（直接求解时，输入的最后（END语语句后）只需要加上句后）只需要加上0-1变量变量y的限定语句。的限定语句。第第13页页/共共17页页第12页/共17页第十三页，共17页。在LINDO模型窗口(chungku)中输入模型：max 2 x1+3 x2+4 x3st1.5 x1+3 x2+5 x3 600280 x1+250 x2+400 x3 60000 x1-1000 y1 0 x2-1000 y2 0 x3-1000 y3 0 x2-80 y2 0 x3-80 y3 0endint y1int y2int y3第第14页

21、页/共共17页页第13页/共17页第十四页，共17页。OBJECTIVE FUNCTION VALUE 1)611.2000 VARIABLE VALUE REDUCED COST Y1 1.000000 108.800003 Y2 1.000000 0.000000 Y3 0.000000 0.000000 X1 80.000000 0.000000 X2 150.399994 0.000000 X3 0.000000 0.800000 ROW SLACK OR SURPLUS DUAL PRICES 2)28.799999 0.000000 3)0.000000 0.012000 4)92

22、0.000000 0.000000 5)849.599976 0.000000 6)0.000000 0.000000 7)0.000000 -1.360000 8)70.400002 0.000000 9)0.000000 0.000000 NO.ITERATIONS=25 BRANCHES=1 DETERM.=1.000E 0求解得到输出求解得到输出(shch)如下如下：即：只生产小型和即：只生产小型和中型汽车，产量分中型汽车，产量分别为别为80辆和辆和150辆辆(近似值近似值),可获得可获得(hud)最大最大利润利润611.2万元。万元。不妨试试把产量不妨试试把产量(chnling)x也

23、也限定只取整数，限定只取整数，结果会如何呢？结果会如何呢？第第15页页/共共17页页第14页/共17页第十五页，共17页。尽管尽管LINDO 对整数规划问题很有威力对整数规划问题很有威力,但要想有效地使用，但要想有效地使用，有时还是需要一定的技巧的。这是因为有时还是需要一定的技巧的。这是因为,人们很容易将一个本人们很容易将一个本质上很简单的问题列成一个不太好的输入模型质上很简单的问题列成一个不太好的输入模型,从而有可能会从而有可能会导致一个冗长的分枝定界计算。遗憾的是，我们往往难以预先导致一个冗长的分枝定界计算。遗憾的是，我们往往难以预先估计什么样的模型才能避免冗长的分枝定界计算，也难以判别估

24、计什么样的模型才能避免冗长的分枝定界计算，也难以判别什么样的模型是什么样的模型是“不太好不太好”的输入模型。当然这时的输入模型。当然这时 LINDO 会主会主动砍去一些计算过程动砍去一些计算过程,以缩短计算时间，而且越是高版本的以缩短计算时间，而且越是高版本的LINDO软件，这种自动处理的软件，这种自动处理的“智能智能”越强。我们的建议是：如越强。我们的建议是：如果分枝定界计算时间很长仍得不到最优解，你可以试试对输入果分枝定界计算时间很长仍得不到最优解，你可以试试对输入模型进行一些等价模型进行一些等价(dngji)变换：如交换变量的次序，交换约变换：如交换变量的次序，交换约束的顺序等，有时也许会对减少求解所需的时间有所帮助。束的顺序等，有时也许会对减少求解所需的时间有所帮助。备注备注备注备注(bizh)(bizh)第第16页页/共共17页页第15页/共17页第十六页，共17页。THE ENDTHE ENDThank you very much!Thank you very much!第第17页页/共共17页页第16页/共17页第十七页，共17页。