运筹学 第2版 教学课件 作者 孔造杰OR1-Ch6-整数规划.ppt

《运筹学 第2版 教学课件 作者 孔造杰OR1-Ch6-整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章整数规划IntegerProgramming§6-1整数规划模型§6-2分枝定界法§6-3割平面法§6-40-1规划§6-5指派问题§6-6整数规划的计算机解法§6-7IP的应用及案例分析§6-1整数规划模型（ModelofIntegerProgramming）在线性规划与非线性规划模型中，变量的取值是在实数范围或在正实数范围。但是，在很多管理与经济活动中，要求所探讨的问题变量只能取整数值或取整数值中的一部分。如人数、机器台数、投资项目个数等，这时的非整数解就没有意义。如果一个规划模型中的变量有整数要求，则该规划模型就是整数规划模型。整数规划模型包括：整数规划、0-1规划、混合规划三种类

2、型。例如1.变量是人数、机器设备台数或产品件数等都要求是整数2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。7/25/20212河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofInterProgramming）纯整数规划模型及其解的分析求解整数解的线性规划问题，通常人们首先想到的是先不管整数条件的限制，直接使用单纯形法求解，然后将所得到的非整数解经四舍五入化为整数。但是这种办法往往是行不通

3、的，这是因为由舍入化整所得的整数解不一定是可行解，即便是可行解，也不一定是最优解。【例6-1】整数规划问题图6-17/25/20213河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofIntegerProgramming）如果先不考虑决策变量的整数限制，无论是用图解法还是用单纯形法都可很容易地求得最优解为：，。这里也很容易验证：（1）如果按四舍五入将非整数解化为整数，应取，而不是可行解；（2）如果把的小数部分0.8舍去，取，它虽是可行解，但不是最优解，这是因为，而，且（0，2）也是可行解。由此可见，用凑整数法解整数规划是不可取的。目前，解整数规划问题通常采用的方法是分支定界法和

4、割平面法。不过割平面法通常用于手工解法，适应于一些小型的问题，对于较大的整数规划问题一般采用分支定界法用计算机来求解，特别是对于那些只要求部分决策变量是整数的规划问题，分支定界法尤为方便。纯整数规划模型及其解的分析(续）7/25/20214河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofIntegerProgramming）【例6-2】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表6－1所示。问两种物品各装多少件，所装物品的总价值最大？物品重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0

5、020.002543表6—1【解】设甲、乙两种物品各装x1、x2件，则数学模型为：(6.1)纯整数规划模型及其解的分析7/25/20215河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofIntegerProgramming）如果不考虑x1、x2取整数的约束，线性规划的可行域如图6-2中的阴影部分所示。7/25/20216河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofIntegerProgramming）用图解法求得点B为最优解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必须取整数值，实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用

6、凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。由图6-2知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。7/25/20217河北工业大学管理学院孔造杰制作§6-1整数规划模型（ModelofIntegerProgramming）0-1规划问题当进一步限定线性

7、规划问题中的决策变量只取0、1两个值时，就构成了一类特殊的整数规划——0-1整数规划。这时的决策变量称为0-1变量。在实际问题中，有些问题往往只需回答“是”或“否”，问题就算解决了。描述这类问题的变量只需要取两个值就可以了。如果问题的变量不是仅取0和1，而是可取其它某个范围的非负整数，则也可以利用二进制的记数法将它用若干个0-1变量来代替，从而将其化为0-1整数规划。引入0-1变量的实际问题投资场