运筹学课程设计

湖南大学课程设计 第12页

在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，它的解法一般为穷举法或隐枚举法。若有n个决策变量, 则可以产生2n个可能变量的组合, 当n较大时，完全枚举是不可能的. 求解0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicit enumeration)。 在2n个可能的变量组合中, 往往只有一部分是可行解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。 若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constraint), 对于目标函数值比它差的的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。

在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，下面将列举一个模型范例，以探讨这一类问题。

问题四：

求解下述0-1整数规划问题：

湖南大学课程设计 第13页

maxZ?3x1?2x2?5x3

?x1?2x2?x3?2?x?4x?x?4123??s.t?x1?x2?3?4x?x?63?2??x1,x2,x3?0or1尝试求解：求解过程见下表： (x1,x2,x3) Z值 0 5 -2 3 3 8 1 6 约束条件 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 过滤条件 Z?0 Z?5 Z?8 （0,0,0）

(1,1,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,1) 所以，最优解为（x1，x2，x3)=(1,0,1)， 最优值为8。

五．Lindo软件的应用

LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度快，易于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界得到广泛应用。 LINDO主要用于求解线性规划、

湖南大学课程设计 第14页

非线性规划、二次规划和整数规划等问题，也可以用于一些线性和非线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数(包括大量概率函数)，可供使用者建立数学规划问题模型时调用。

问题五：

（汽车生产计划）汽车厂生产三种类型汽车，一直各类型每辆车对应的钢材，劳动时间要求是。利润及工厂每月现有量。 小型汽车 中型汽车 3 250 3 大型汽车 5 400 4 现有量 600 60000 钢材（吨） 1.5 时间（小时） 280 利润（万元） 2 制定月生产计划，使工厂利润最大。

尝试求解：假设x1、x2、x3分别表示生产小型汽车x1辆，生产中型汽车x2辆，生产大型汽车x3辆，Z表示生产汽车所获得的总利润。该问题的模型为：

Max z ?

2x1?3x2?4x3s.t.1.5x1?3x2?5x3?600280x1?250x2?400x3?60000x1,x2,x3为非负整数

湖南大学课程设计 第15页

这一ILP问题可直接用Lindo求解： max 2x1+3x2+4x3 st

1.5x1+3x2+5x3<600 280x1+250x2+400x3<60000 end gin 3

其中：“gin 3”表示“前3个变量为整数”，等价于： gin x1 gin x2 gin x3 输出结果为：

OBJECTIVE FUNCTION VALUE 1) 632.0000

VARIABLE VALUE REDUCED COST

X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000

得到这一问题的最优解为x1=64，x2=168，x3=0，最优值z=632 。

湖南大学课程设计 第16页

六．设计心得与参考文献

经过一周的时间，实用运筹学课程设计终于完成了．在这期间，我收获了很多，也学到了很多.通过本次课程设计，我更深刻的体会到了运筹学的思维及精髓，学会了运用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际中的人、财、物等有限的资源进行统筹安排.对于整数规划模型更加有了深刻的认识，并且学会了建立相关模型求解实际问题，以得到想要的结果.并且在建立模型求解模型的过程中也认识到了整数规划的重要性，它也应用到了生活的方方面面.在使用LINGO软件求解的同时，更加熟练的掌握了LINGO软件，让我能更好的使用LINGO软件来求解实际问题.在以后的生活中，我应该学以致用来解决更多的问题。

参考文献：

[1] 钱颂迪等．运筹学第四版．北京：清华大学出版社，2012． [2] 谢金星. 薛毅．优化建模LINGO/LINDO软件[M]．北京：清华大学出版社，2005．

[3] 胡运权．运筹学基础及其应用[M]．北京：高等教育出版社，2004．

[4] 百度百科.