数模讲义之LINDO软件包介绍

1、数模讲义之LINDO软件包介绍LINDO软件包首先由Linus Schrage开发，现在，美国的LINDO系统公司（LINDO System Inc.）拥有版权，是一种专门求解数学规划（优化问题）的软件包。它能求解线性规划、（0，1）规划、整数规划、二次规划等优化问题，并能同时给出灵敏度分析、影子价格以及最优解的松弛分析，非常方便实用。1 注意事项（1） 低版本的LINDO要求变量一律用大写字母表示；（2） 求解一个问题，送入的程序必须以MIN或MAX开头，以END 结束；然后按Ctrl + S（或按工具栏中的执行快捷键）进行求解；（3） 目标函数与约束条件之间要用SUBJECT TO（或ST

2、）分开，其中字母全部大写；（4） LINDO已假定所有变量非负，若某变量，例如X5有可能取负值，可在END命令下面一行用FREE X5命令取消X5的非负限制；LINDO要求将取整数值的变量放在前面（即下标取小值），在END下面一行用命令INTEGER K，表示前K个变量是（0，1）变量；在END下面一行用命令GIN H表示前H个变量是整数变量；（5） 在LINDO中，“”等价于“” ；（6） 在LINDO的输出结果中有STATUS（状态栏），它的表出状态有：OPTIMAL（说明软件包求得的结果是最优解）、FEASIBLE（说明软件包求得的结果只是可行解）、INFEASIBLE（说明软件包求得的

3、结果是不可行解）。（7） 在LINDO命令中，约束条件的右边只能是常数，不能有变量；（8） 变量名不能超过8个字符；（9） LINDO对目标函数的要求，每项都要有变量，例如，LINDO不认识MIN 2000-X+Y，要改为MIN X+Y；（10） LINDO不认识400（X+Y）要改为400X+400Y。2 求解线性规划问题例 1 求解下列线性规划问题：在LINDO中输入下列命令：MAX 2X+3YSUBJECT TO4X+3Y103X+5Y 1.00000 NEW INTEGER SOLUTION OF 25. AT BRANCH 0 PIVOT 15 BOUND ON OPTIMUM: 2

4、5.00000 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 15 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X11 0. -1. X12 0. -1. X13 1. -2. X14 0. -5. X15 0. -7. X21 0. -1. X22 0. -2. X23 0. -3. X24 0. -7. X25 1. -10. X3

5、1 0. -1. X32 0. -3. X33 0. -4. X34 1. -9. X35 0. -10. X41 0. -1. X42 1. -4. X43 0. -5. X44 0. -10. X45 0. -10. X51 1. 0. X52 0. 0. X53 0. 0. X54 0. 0. X55 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. 7) 0. 0. 8) 0. 0. 9) 0. 0. 10) 0. 0. 11) 0. 0. NO. ITERATIONS

6、= 15 BRANCHES= 0 DETERM.= 1.000E 0这个结果说明：LINDO求解此（0，1）整数线性规划问题（LP）只15步迭代得到最优解fmax = 25，x13 = x25 = x34 = x42 = x51 =1，其它xij = 0。松弛变量都取0值，即，这个最优解使得约束条件都取等号；其对偶问题的最优解（影子价格）DUAL PRICES都为0。例 4 两辆铁路平板车的装货问题（美国大学生MCM1988-B题）有7种规格的集装箱C1、C2、C3、C4、C5、C6、C7要装到两辆平板车上去，所有集装箱的宽和高是相同的，但厚度（t，以厘米计）及重量（w，以千克计）是不同的，见

7、下表：C1C2C3C4C5C6C7t48.752.061.372.048.752.064.0w200030001000500400020001000件数8796648每辆平板车有10.2米长的地方可用来装集装箱（像面包片那样），载重为40吨。由于当地货运的限制，对C5、C6、C7类的集装箱的总数有一个限制：这3类箱子在两辆车上所占空间（厚度）的总和不能超过302.7厘米。问：怎样装车可以使得两辆平板车上剩下的空隙总和最小？一、 必要的假设和问题的分析（1） 两个集装箱紧挨在一起没有缝隙；（2） 平板车上剩下的空隙是指：任一种集装箱都放不下的小空间；（3） 将第 j类集装箱Cj的厚度记为tj，重

8、量记为wj，总件数记为nj。设第j类集装箱在第一个平板车上装了xj个，在第二个平板车上装了yj个，令T1 = t1*x1+t2*x2+t7*x7；T2 = t1*y1+t2*y2+t7*y7则有下列一般模型：具体到本题，我们得到：在LINDO中输入以下命令：MIN -48.7X1-52X2-61.3X3-72X4-48.7X5-52X6-64X7-48.7Y1-52Y2-61.3Y3-72Y4-48.7Y5-52Y6-64Y7SUBJECT TOX1+Y18X2+Y27X3+Y39X4+Y46X5+Y56X6+Y64X7+Y7848.7X1+52X2+61.3X3+72X4+48.7X5+52

9、X6+64X7102048.7Y1+52Y2+61.3Y3+72Y4+48.7Y5+52Y6+64Y710202000X1+3000X2+1000X3+500X4+4000X5+2000X6+1000X7400002000Y1+3000Y2+1000Y3+500Y4+4000Y5+2000Y6+1000Y740000 48.7X5+48.7Y5+52X6+52Y6+64X7+64Y7302.7ENDGIN 14LINDO运行后输出如下结果：STATUS INFEASIBLE共迭代3488次，得到的仍然是不可行解（注：LINDO是用分枝定界法求解整数规划的）。另想办法求解：Step1 先求max

10、 48.7x5+48.7y5+52x6+52y6+64x7+64y7stx5+y56x6+y64x7+y7848.7x5+48.7y5+52x6+52y6+64x7+64y7302.7endgin 6得到结果： LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 302.1000 VARIABLE VALUE REDUCED COST X5 3. -48. Y5 0. -48. X6 3. -52. Y6 0. -52. X7 0. -64. Y7 0.

11、 -64. ROW SLACK OR SURPLUS DUAL PRICES 2) 3. 0. 3) 1. 0. 4) 8. 0. 5) 0. 0. NO. ITERATIONS= 1753 BRANCHES= 566 DETERM.= 1.000E 0此时的最优解为：x5 = 3 ，x6 = 3，x7 = y5 = y6 = y7 = 0。Step2 将这个结果代入到原模型中，则：max 48.7x1+52x2+61.3x3+72x4+48.7y1+52y2+61.3y3+72y4st48.7x1+52x2+61.3x3+72x4717.948.7y1+52y2+61.3y3+72y4102

12、02000x1+3000x2+1000x3+500x4300002000y1+3000y2+1000y3+500y440000x1+y18x2+y27x3+y39x4+y402Y-X-0.9A+B+C-0.41.2X+0.9Y1.1X+Y=1Y7860X243820X3320X421X53X667X8268X91X1+X2+X3=12X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14+X15+X16+X17+X18=12END得到结果： LP OPTIMUM FOUND AT STEP 8 OBJECTIVE FUNCTION VALUE 1) 7148.214 VAR

13、IABLE VALUE REDUCED COST X1 1. 0. X2 7. 0. X3 3. 0. X4 1. 0. X5 3. 0. X6 0. 1210. X7 0. 0. X8 3. 0. X9 0. 910. X10 0. 880. X11 0. 1005. X12 0. 810. X13 0. 450. X14 0. 750. X15 0. 220. X16 0. 630. X17 3. 0. X18 0. 680. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. -0. 3) 0. -0. 4) 65. 0. 5) 0. -41. 6) 0. -9

14、15. 7) 1. 0. 8) 0. -139. 9) 0. -139. 10) 1. 0. 11) 0. 150. 12) 0. 1130. NO. ITERATIONS= 8 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 135. 14. INFINITY X2 135. 14. INFINITY X3 150. INFINITY 14. X4 300. 830. INFINITY X5

15、 215. 915. INFINITY X6 -80. 1210. INFINITY X7 153. 976. INFINITY X8 153. 976. INFINITY X9 220. 910. INFINITY X10 250. 880. INFINITY X11 125. 1005. INFINITY X12 320. 810. INFINITY X13 680. 450. INFINITY X14 380. 750. INFINITY X15 910. 220. INFINITY X16 500. 630. INFINITY X17 1130. INFINITY 220. X18 450. 680. INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWA