整数线性规划.pptx

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

1、LINDO求解整数线性规划概述LINDO可用于求解线性纯整数规划或混合整数规划可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与模型的输入与LP问题类似问题类似,但需但需在在END标志后定义整型变量标志后定义整型变量。0/1型的变量可由型的变量可由INTEGER（可简写为（可简写为INT）命令来标识，）命令来标识，有以下两种可能的用法：有以下两种可能的用法：INT vname INT n前者只将决策变量前者只将决策变量vname标识为标识为0/1型型,后者将当前模型中前后者将当前模型中前n 个变量标识为个变量标识为0/1型（模型中变量顺序由型（模型中变量顺序由模型中输入时出现的先后顺

2、序决定模型中输入时出现的先后顺序决定,该顺序可由输出结果中的该顺序可由输出结果中的变量顺序查证是否一致）。变量顺序查证是否一致）。一般的整数变量可用命令一般的整数变量可用命令GIN（是（是GENERAL INTEGER的意的意思）思）,其使用方式及格式与其使用方式及格式与INT 命令相似。命令相似。第第2页页/共共17页页第1页/共17页例2.6 员工聘用问题员工聘用问题 首先在首先在LINDO模型窗口输入模型模型窗口输入模型:MIN X1+X2+X3+X4+X5+X6+X7SUBJECT TOMON)X1 +X4+X5+X6+X7=50TUE)X1+X2 +X5+X6+X7=50WED)X1

3、+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个变量都是一般整数变量。个变量都是一般整数变量。（仍然默认为取值是非负的）（仍然默认为取值是非负的）第第3页页/共共17页页第2页/共17页求解后状态窗口中与整数相关的三个域有了相关结果求解后状态窗口中与整数相关的三个域有了相关结果:“Best IP：94”表示当前表示当前得到的最好的整数解的目得到的最好的整数解的目标函数值为标函数值为94（人

4、）。（人）。“IP Bound：93.5”表示表示该整数规划目标值的下界该整数规划目标值的下界为为93.5（人）。（人）。“Branches：1”表示分枝表示分枝数为数为1（即在第（即在第1个分枝中个分枝中就找到了最优解）。就找到了最优解）。我们前面说过，我们前面说过，LINDO求解求解IP用的是分枝定界法。用的是分枝定界法。显然，上面第二条显然，上面第二条“整数规划目标值的下界为整数规划目标值的下界为93.5（人）（人）”表明至少要表明至少要聘用聘用93.5名员工，由于员工人数只能是整数，所以至少要聘用名员工，由于员工人数只能是整数，所以至少要聘用94（人）。（人）。而第一条说明目前得到的解

5、就是聘用而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了。（人），所以已经是最优的了。第第4页页/共共17页页第3页/共17页 LP OPTIMUM 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

6、=1 PIVOTS=18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.求解结果的报告窗口如下：求解结果的报告窗口如下：（接下页）（接下页）第第5页页/共共17页页第4页/共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.

7、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.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

8、页报告窗口中前两行告诉我们：在报告窗口中前两行告诉我们：在8次迭代后找到对应的线性次迭代后找到对应的线性规划（规划（LP）问题的最优解，最优值）问题的最优解，最优值=93.3333359。LINDO求解求解IP用的是分枝定界法，紧接着几行显示的是分用的是分枝定界法，紧接着几行显示的是分枝定界的信息，在第枝定界的信息，在第1个分枝中设定个分枝中设定x2=4,并在该分枝中并在该分枝中找到了整数解，而且就是全局整数最优解，所以算法停止。找到了整数解，而且就是全局整数最优解，所以算法停止。旋转迭代（旋转迭代（PIVOT）共）共18次。次。后面显示的是最后的最优解：后面显示的是最后的最优解：x=(0,4

9、,40,2,34,10,4).松弛和剩余变量（松弛和剩余变量（SLACK OR SURPLUS）仍然可以表示）仍然可以表示约束的松紧程度，但目前约束的松紧程度，但目前IP尚无相应完善的敏感性分析理尚无相应完善的敏感性分析理论，因此论，因此REDUCED COST和和DUAL PRICES的结果在整数的结果在整数规划中意义不大。规划中意义不大。第第7页页/共共17页页第6页/共17页例2.7 游泳队员的选拔问题（0-1规划）在LINDO模型窗口中输入模型：MIN 66.8x11+75.6x12+87 x13+58.6x14 +57.2x21+66 x22+66.4x23+53 x24 +78 x

10、31+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+x44+x54=1ENDINT 20其中其中“INT 20”表示表示20个变量个变量都是都是0

11、-1整数变整数变量量 第第8页页/共共17页页第7页/共17页求解得到结果为：求解得到结果为：x14=x21=x32=x43=1,其它变量为其它变量为0，成绩为成绩为253.2（秒）（秒）=413”2。即应当选派甲乙丙丁。即应当选派甲乙丙丁4人组成接人组成接力队，分别参加自由泳、蝶泳、仰泳、蛙泳的比赛。力队，分别参加自由泳、蝶泳、仰泳、蛙泳的比赛。由于这个问题中有由于这个问题中有20个个0-1变量，而最优解中肯定只有其中的变量，而最优解中肯定只有其中的4个变量取非零值个变量取非零值“1”，所以要在一大堆变量中去找少量的几个，所以要在一大堆变量中去找少量的几个取非零值的变量，这是不太方便的。有没

12、有办法只把取非零值取非零值的变量，这是不太方便的。有没有办法只把取非零值的变量显示出来呢？的变量显示出来呢？这是可以做到的：选择菜单命令这是可以做到的：选择菜单命令“Reports|Solution(Alt+0)”（这个命令的功能是要把最优解显示出来），这时会弹（这个命令的功能是要把最优解显示出来），这时会弹出一个选择对话框（图出一个选择对话框（图2-21），缺省的选项是），缺省的选项是“Nonzeros Only（只显示非零值）（只显示非零值）”。按下对话框中的。按下对话框中的“OK”按钮，则报告窗按钮，则报告窗口中的只显示取非零值的变量，这样阅读起来就很方便了。口中的只显示取非零值的变量，

13、这样阅读起来就很方便了。请注意，这个功能并不仅仅在整数规划中可以使用，在其他模请注意，这个功能并不仅仅在整数规划中可以使用，在其他模型中也是可以使用的，不妨试试就知道了。型中也是可以使用的，不妨试试就知道了。第第9页页/共共17页页第8页/共17页讨论若考虑到丁、戊最近的状态，若考虑到丁、戊最近的状态，c43 由原来的由原来的69.6变为变为75.2（秒），（秒），c54由原来的由原来的62.4变为变为57.5（秒）（秒）,试讨论对试讨论对结果的影响。结果的影响。这类似于线性规划中的敏感性分析这类似于线性规划中的敏感性分析,但是可惜的是，对于但是可惜的是，对于整数规划模型，一般没有与线性规划相

14、类似的理论，此时整数规划模型，一般没有与线性规划相类似的理论，此时LINDO中所输出的敏感性分析结果通常是没有意义的，因中所输出的敏感性分析结果通常是没有意义的，因此不能利用这个输出的敏感性分析结果。此不能利用这个输出的敏感性分析结果。于是我们只好用于是我们只好用c43，c54 的新数据重新输入模型，用的新数据重新输入模型，用LINDO求解得到：求解得到：x21=x32=x43=x51=1,其它变量其它变量为为0，成绩为，成绩为257.7（秒）（秒）=417”7。即应当选派乙丙丁戊。即应当选派乙丙丁戊4人组成接力队，分别参加蝶泳、仰泳、蛙泳、自由泳的人组成接力队，分别参加蝶泳、仰泳、蛙泳、自由

15、泳的比赛。比赛。第第10页页/共共17页页第9页/共17页例2.8 2.8 汽车生产计划（混合整数规划）一汽车厂生产小、中、大三种类型的汽车，已知各类型每一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示：劳动时间的现有量如下表所示：小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234由于各种条件限制，如果生产某一类型汽车，则至少要由于各种条件限制，如果生产某一

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

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

18、接求解时，输入的最后（后（END语句后）只需要加上语句后）只需要加上0-1变量变量y的限定语句。的限定语句。第第13页页/共共17页页第12页/共17页在LINDO模型窗口中输入模型：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页页/共共17页页第13页/共17页 OBJECTIVE FUNCTION VALUE 1)611.2000 V

19、ARIABLE 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)920.000000 0.000000 5)849.599976 0.000000 6)0.000000 0.000000 7)0.

20、000000 -1.360000 8)70.400002 0.000000 9)0.000000 0.000000 NO.ITERATIONS=25 BRANCHES=1 DETERM.=1.000E 0求解得到输出如下求解得到输出如下：即：只生产小型即：只生产小型和中型汽车，产和中型汽车，产量分别为量分别为80辆和辆和150辆辆(近似值近似值),可获得最大利润可获得最大利润611.2万元。万元。不妨试试把产不妨试试把产量量x也限定只取也限定只取整数，结果会整数，结果会如何呢？如何呢？第第15页页/共共17页页第14页/共17页 尽管尽管LINDO 对整数规划问题很有威力对整数规划问题很有威力

21、,但要想有效地使但要想有效地使用，有时还是需要一定的技巧的。这是因为用，有时还是需要一定的技巧的。这是因为,人们很容易将人们很容易将一个本质上很简单的问题列成一个不太好的输入模型一个本质上很简单的问题列成一个不太好的输入模型,从而从而有可能会导致一个冗长的分枝定界计算。遗憾的是，我们往有可能会导致一个冗长的分枝定界计算。遗憾的是，我们往往难以预先估计什么样的模型才能避免冗长的分枝定界计算，往难以预先估计什么样的模型才能避免冗长的分枝定界计算，也难以判别什么样的模型是也难以判别什么样的模型是“不太好不太好”的输入模型。当然这的输入模型。当然这时时 LINDO 会主动砍去一些计算过程会主动砍去一些

22、计算过程,以缩短计算时间，而以缩短计算时间，而且越是高版本的且越是高版本的LINDO软件，这种自动处理的软件，这种自动处理的“智能智能”越越强。我们的建议是：如果分枝定界计算时间很长仍得不到最强。我们的建议是：如果分枝定界计算时间很长仍得不到最优解，你可以试试对输入模型进行一些等价变换：如交换变优解，你可以试试对输入模型进行一些等价变换：如交换变量的次序，交换约束的顺序等，有时也许会对减少求解所需量的次序，交换约束的顺序等，有时也许会对减少求解所需的时间有所帮助。的时间有所帮助。备注第第16页页/共共17页页第15页/共17页THE ENDTHE ENDThank you very much!Thank you very much!第第17页页/共共17页页第16页/共17页感谢您的观看。第17页/共17页