水资源系统分析及应用：第三章 整数规划

1、第三章 整数规划3.1 整数规划模型3.2 0-1型整数规划3.3 指派问题3.4 软件解法3.1 引言 在工程设计和企业管理中，常会遇到要求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，也经常简称为整数规划问题。 线性规划是运筹学的重要分枝，也是运筹学最基本的部分。整数规划是近三十年来发展起来的、规划论的一个重要的理论分支。根据对决策变量的要求不同，分为四种类型： 纯整数规划：所有决策变量均要求为

2、离散的非负 整数。 混合整数规划：部分决策变量要求为离散的非负 整数。 纯 01 整数规划：所有决策变量均要求为0或1。 混合 01 整数规划：部分决策变量要求为0或1。 3.2 引例：生产组织计划问题与选址问题 引例3.2.1（生产组织计划问题）某工厂在一个计划期内拟生产甲、乙两种大型设备。除了A、B两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表3.2.1给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取最大利润？ 部件设备AB利润（百万）甲6

3、115乙4320部件的最大供应量2510表 3.2.1 设 x1，x2 分别为该计划期内甲、乙设备的生产数量，Z 为生产这两种设备可获得的总利润。依题意，给问题的数学模型为： max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 这是一个纯整数规划问题。 引例3.2.2（选址问题）某商业连锁集团拟在 n 个连锁店所在城市中建立 m 个配货中心，每个城市最多建立一个配货中心。若在第 i 个城市建立配货中心，其配货能力为 Di，单位时间的固定成本为 ai，i = 1，n，第 j 个连锁店的需求量为 bj，j = 1，n。从第 i 个配货中

4、心到第 j 个连锁店的单位运输成本为 cij。应如何选择配货中心位置和安排运输计划，才能得到经济上花费最少的方案。 设在单位时间内，从配货中心 i 运往连锁店 j 的物资数量为 xij，Z 为单位时间内的总费用。引入布尔变量 则上述问题可归结为如下的数学模型： 这是一个混合 01 规划问题。整数规划（integer programming,IP) 要求一部分或全体决策变量必须取整数值的规划问题St.)纯整数规划 )混合整数规划 ) 0-1整数规划3.3 整数规划模型纯整数规划求解某集装箱运输公司，箱型标准体积24m3，限制重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2

5、000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？设装运甲货物x1件、乙货物x2件maxZ=2000 x1+1000 x2 5x1+4x224 2x1+5x2 13 x1.x2 0且为整数 St. 1.当人们开始接触整数规划问题时，常常会有如下两种初始想法： 想法一：因为可行方案的数目常常是有限的，因此，从理论上讲，经过一一比较后，总能求得最好方案。例如背包问题充其量有2n-1种方式。但是这种穷尽法是行不通的。假设一台计算机每秒比较一百万个方式，那么要比较20！种方式，大约需要800年，要比较260种方式，需要360多个世纪。 整数规划的解题思路想法二：先放弃变量的整

6、数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。整数规划问题和线性规划问题相似，在求整数规划的最优解时，可以用线性规划的图解法，单纯形法求出最优解。如果答案不全是整数时，就把整数的条件加到原线性规划的约束条件中去，用单纯形法继续求解，以便得到整数最优解。这附加的约束条件相当于把某个要求取整数的决策变量在可行域中割掉其非整数部分。 2.整数规划与线性规划的关系解相应的LP问题，得：X1=4.8，X2=0 不是可行解，舍入取整得X1=4，X2=0优点：可节省求解的人力、物力和财力

7、是否最优？求解思路1）舍入取整法即先不考虑整数性约束，而去求解其相应的LP问题，然后将得到的非整数最优解用“舍入取整”的方法。2）完全枚举法此法仅在决策变量很少的情况下才实际有效。B（4，1）A（4.8，0）x10 1 2 3 4 5 6 7 231x22x1+5x2 135x1+4x224Z=2000 x1+1000 x23）图解法 A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划的可行解就是可行域中的整数点非整数点不是可行解，对于求解没有意义，切割掉可行域中的非可行解，不妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解4）分枝

8、定界法 分枝定界法是求解整数规划问题的一种有效算法，在二十世纪六十年代初由 Land 和Doig 提出并经 Dakin 修正而完善。它不仅适用于求解纯整数规划问题，同时也适用于求解混合整数规划问题。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。 分枝定界法对可行域恰当地进行系统搜索，基本上是一种“分而治之”的策略。 通常，它把可行域反复地划分为越来越小的一系列子域，称之为分枝；子域的一个边界为整数，在子域上解线性规划，对于最大值问题，线性规划解的目标函数值是整数规划的上界，整数规划任意可行点的目标函数值是其下界，这称为定界。在子域分解的过程中，上界非增，下界非减，经有限

9、多次分解即可得到整数规划的最优解。 思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解。解：先不考虑整数要求，解相应的LP问题，得：x1=4.8，x2=0，Z=9600，不是可行解 maxZ=2000 x1+1000 x 25x1+4x224 2x1+5x2 13 x1、x2 0且为整数 St.X1=4.8不符合要求，切掉45之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x14和x15，原问题分解为两个maxZ=2000 x1+1000 x2 5x1+4x224 2x1+5x2 13 ( IP1 ) x14 x1，x2 0且为整数St.maxZ=2000 x1

10、+1000 x2 5x1+4x224 2x1+5x2 13 ( IP2 ) x1 5 x1，x2 0且为整数St.IP1:x1=4 ,x2=1 z=9000 IP2:无可行解此时得IP问题的最优解，即x1=4,x2=1,Z=9000。首先不考虑整数约束，解相应的线性规划问题用单纯形法求得其最优解为x1=2.5，x2=2.5，z=87.5求解： 问题（0）x1=2.5，x2=2.5 z=87.5 问题（1）x1=2，x2=2.67 z=83.3 问题（2）x1=3，x2=1.75 z=80 问题（3）x1=2，x2=2 z=70 问题（4）x1=1，x2=3 z=75 问题（5）x1=3.5，x

11、2=1 z=72.5 问题（6）无可行解 整数规划问题的数学模型的一般形式为： 定义 凡是放弃问题 (P) 中的某些约束条件后得到的问题 ( )，成为 (P) 的松弛问题。 定理 若用 R 表示问题 (P) 的可行域，用 x* 和 z* 表示问题 (P) 的最优解与最优值；用 表示问题 ( ) 的可行域，用 和 表示问题 ( ) 的最优解与最优值。则对于任何松弛问题 ( )，有： (1) R ; (2) ( ) 无可行解 (P) 无可行解； (3) z* （对于求最小值的问题 (P)， 则有 z* ）； (4) R 也是 (P) 的最优解。 根据上述定理，可以给出分枝定界法的基本步骤（参见教材

12、）。 实现上述步骤的程序框图，如图 3.3.1。 为了更好地说明用分枝定界法求整数规划最优解的过程，我们选择只有两个变量的引例3.2.1 进行求解。 例3.3.1 用分枝定界法求解整数规划问题 (P)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 解：1. 求解如下的松弛问题 (P0)： (P0)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0，i = 1, 2得最优解 x1 = 2.5，x2 = 2.5，最优值 z = 87.5。由于原问题 (P) 目标函数的系数为整数，x

13、i 0, 1, 2, ，故 z* 87，即最优值的上界 = 87。令最优值的下界 z = 0，则有 z = 0 z* 87 = 。我们将这些结果记录在树形图图 3.3.3 中。 2. 因为此时两个变量都不是整数，我们从中选择一个变量进行分枝。假定选择 x1，在 (P0) 的约束之外，增加两个互相排斥的约束条件：x1 2 与 x1 3，形成两个子模型 (P1) 和 (P2)： (P1)：max Z = 15x1 20 x2 (P2)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 2 x1 3 x

14、i 0，i = 1, 2 xi 0，i = 1, 2此时，模型 (P0) 的可行域被分成两个相应的子域 R1 和 R2，如图 3.3.2 所示。显然，被抛去的非阴影区域内（2 x1 z =75，所以，在 (P2) 的约束之外，增加两个互相排斥的约束条件：x2 1 与 x2 2，形成两个子模型 (P5) 和 (P6)： (P5)：max Z = 15x1 20 x2 (P6)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 3 x1 3 x2 1 x2 2 xi 0，i = 1, 2 xi 0，i

15、 = 1, 2 7. 对子模型 (P5) 进行求解，得最优解为 x1 = 3.5，x2 = 1，最优值 z = 72.5。由于最优值 z = 72.5 75 = z，故不再分枝。因为分枝后，新模型的最优值不可能超过当前新的下界。 8. 对子模型 (P6) 进行求解，因为无可行解，故不再分枝。 至此，已将所有分枝的子模型求解完毕，当前新的下界值相应的解，是现行最好的整数可行解，也就是原整数规划问题的最优解：x1* = 1，x2* = 3。最优目标函数值 z = 75。 注：图 3.3.3 中的子模型 (P3)、(P4)、(P5) 不再分枝，并不是说它们分枝后不可以找到新的整数可行解，而是表明：即

16、使找出新的整数可行解也不会优于目前最好的整数可行解，其目标函数值不会大于目前的下界值，这些可行解已被全部隐含枚举了。实质上，分枝定界法是一种隐枚举法（Implicit Enumeration）。 提示：用分枝定界法求解整数规划问题，其计算量一般比较大，所以此法只能求解规模不太大的整数规划问题。对于规模较大的整数规划问题，可以采取启发式算法，例如遗传算法来求解。 舍入误差 对于整数规划问题，可以先去掉整数限制来求解相应的松弛问题，找出松弛问题的最优解。但是将这个松弛问题的最优解舍入成整数，或者求最靠近它的整数解，或者对与它相邻的 2n 个整数点进行穷举，都不能保证得到整数规划问题的最优解，甚至不

17、是可行解。另外，用穷举法对与它相邻的 2n 个整数点进行考察，当 n 较大时也是不可行的。例 3.3.3 求解整数规划问题 (P) (P)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） xi 0, 1, 2, 解：将整数规划问题 (P) 去掉整数限制后得到如下的松弛问题 (P0)： (P0)：max Z = 5x1 8x2 s.t. x1 x2 6 5x1 9x2 45 xi 0（i =1, 2） 求解线性规划问题 (P0)，得最优解 x1 = 2.25， x2 = 3.75，最优值 z = 41.25。(P0) 的可行域如图 3.

18、3.5 中阴影部分，最优解在 P 点取到，图中圆点为整数点，阴影中的圆点为 (P) 的可行解。 将 x1 = 2.25 和 x2 = 3.75 舍入成整数或者找最靠近它的整数，有 (P0) 的最优解(P0) 的舍入解最靠近 (P0) 的可行解(P) 的最优解(2.25, 3.75)z = 41.25(2, 4)不可行(2, 3)z = 34(0, 5)z = 40考察与 P 相邻的 2n = 4 个整数点，有 点的位置(2.25, 3.75)(2, 3)(3, 3)(2, 4)(3, 4)目标函数值41.253439不可行不可行 提示：从理论上来讲，舍入凑整法是不能用来求解整数规划问题的，上述

19、的例 3.3.3 也说明了这一点。然而，在实践中，不必把整数规划与普通的线性规划界限划得太清。因为在许多实际问题中，模型的建立本身就包含了一些不确定因素，同时常常也允许近似的或粗略的结果。因此，舍入凑整法在实践中经常是有用的。 5）求解整数规划的蒙特卡洛方法 在上节中介绍的分枝定界方法，算法的每一个计算步骤都是固定的，而且可以保证求得最优解。但是，当整数线性规划的决策变量数目很大时，分枝定界法的代价可能是巨大的；特别是当整数规划本身是非线性的时候，尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解法尚未找到。 然而，由于整数规划解的数目是有限的，于是为枚举法提供了方便。当然，当决策

20、变量数目很大、取值范围很宽情况下，企图用完全搜索（即穷举法）计算出最优值是不现实的，但是应用蒙特卡洛算法，在一定的计算量下，完全可以得出一个满意解。 例3.4.1 已知非线性整数规划为：max s.t.Z = x12 x22 3x32 4x42 2x52 8x1 2x2 3x3 x4 2x5x1 x2 x3 x4 x5 400 x1 2x2 2x3 x4 6x5 800 2x1 x2 6x3 200 x3 x4 5x5 2005x1 9x2 45 0 xi 99，i = 1, 2, 3, 4, 5 对该问题，目前尚无有效方法求出准确的最优解。如果用穷举法（完全搜索）试探，共需计算1005 =

21、1010 个点，计算量非常大。然而概率理论能够保证，应用蒙特卡洛方法随机计算106个点，便可找到问题的满意解。 解：用蒙特卡洛方法求解这个问题必须借助计算机来实现。 运行程序 5 次，可得如下表 所示的结果： 运行程序最优解最优值第一次运行x = (2, 93, 13, 99, 10)T48024第二次运行x = (9, 98, 4, 99, 17)T48558第三次运行x = (34, 95, 5, 98, 9)T48097第四次运行x = (50, 91, 1, 98, 15)T48517第五次运行x = (38, 99, 3, 99, 3)T49866 注：蒙特卡洛（Monte Carl

22、o）算法是一种随机搜索算法，它允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时，因此蒙特卡洛算法可在很大程度上降低算法的复杂度。但另一方面，同一实例用蒙特卡洛算法求解两次可能得到完全不同的结果，也就是说，用蒙特卡洛算法能够求得问题的一个解，但无法判断这个解是否正确，求得正确解的概率依赖于算法所用的时间，算法所用的时间越多，得到正确解的概率就越高。 6）割平面法算法思想由放松问题的可行域向整数规划的可行域逼近方法利用超平面切除要求 整数解保留 放松问题最优值增加基本思路：通过增加新的约束来切割可原问题伴随规划的可行域，使它在不

23、断缩小的过程中，将原问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。增加的新约束称为割平面方程或切割方程割平面法是先不考虑取整数解的条件，用单纯形法得到非整数最优解。再分别对应于取整数的决策变量建立一个附加的约束条件，以代替整数条件并将它加到原规划问题的约束条件中，用对偶单纯形法继续求解，从而得到整数最优解。例 用割平面法解整数规划问题解：将原整数规划问题称为原问题A0，不考虑整数条件的伴随规划称为问题B0，求解过程如下：1.用单纯形法求解B0，得最优单纯形表Cj1100CBXBx1x2x3x411x2x17/43/401103/4-1/41/41/4-Z-5/20

24、0-1/2-1/22求一个割平面方程(1)在最终表上任选一个含有不满足整数条件基变量的约束方程。本例中，x1=3/4,x2=7/4均不满足整数条件若选x1，则含x1的约束方程为：(1)(2)将所选的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数均拆成一个整数加一个非负的真分数之和。如： 7/4=1+3/4 -5/2=-3+1/2 1/4=0+1/4则(1)式变为(2)(3)将上述约束方程重新组合。组合的原则是：将非基变量系数及常数项中的非负真分数部分移到等号左端，将其他部分移到等式右端，即得(3)(4)求割平面方程分析式(3)，等式右端由三部分组成，常数项的整数部分

25、，基变量及非基变量(含松弛变量或剩余变量)，前两部分都是整数或应取整数，而松弛变量根据约束方程来看也应取非负整数(对于这一点，当原问题A0得约束方程组中的系数或常数项中有非整数时，要求将该约束方程先化成整数系数及整数常数项，然后再标准化，就可满足)，因此式(3)右端应为整数，同时由于等式左端的特殊性，右端的整数应是大于等于零的整数。这是因为可将(3)式改写成这就是一个割平面方程。式(4)左端是非负数，右端第一项是一个真分数，如果第二项为负整数(即1的整数)，则不能保证左端为非负数。因此，(3)式的左端应大于等于零即(4)割平面法解整数规划问题的基本步骤第一步：用单纯形法解松弛问题，得到最优单纯

26、形表。第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。 某些特殊整数规划问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。项目投资额项目收益约束条件1210160中选1项2300210之中选1项3150604130805260180选必先选例：600万元投资5个项目，求利润最大的方案？3.4 0-1型整数规划设xj =0 当项目未被选中1 当项目被选中210 x1+300 x2+150 x3+130 x4+260 x5600 x1+x2+x3=1 x3+x4=1 x5 x1 xj=0或1, j

27、=1，2,5St.max Z=160 x1+210 x2+60 x3+80 x4+180 x5项目投资额项目收益约束条件1210160中选1项2300210之中选1项3150604130805260180选必先选例：600万元投资5个项目，求利润最大的方案？求解0-1规划的隐枚举法210 x1+300 x2+150 x3+130 x4+260 x5600 x1+x2+x3=1 x3+x4=1 x5x1 xj=0或1, j=1，2,5St.max Z=160 x1+210 x2+60 x3+80 x4+180 x5取x11，x41，增加过滤条件160 x1+210 x2+60 x3+80 x4+

28、180 x5 240 方案Z值（1，0，0，1，0） 240（1，1，1，1，1） X（1，1，1，1，0） X（1，1，1，0，1） X .方案Z值（1，0，0，1，0） 240（1，1，1，1，1） X（1，1，1，1，0） X（1，1，1，0，1） X（1，1，1，0，0） X（1，1，0，1，1） X（1，1，0，1，0） X（1，1，0，0，1） X（1，1，0，0，0） X（1，0，1，1，1） X（1，0，1，1，0） X（1，0，0，1，1） 420 .最优方案：对项目1、4、5进行投资，总收益为420万元0-1规划的更多运用假定现有m种资源对可供选择的n个项目进行投资数学模型

29、为：求一组决策变量X1,X2,Xn，使一、资源投资问题（一）对可供项目的选择1、如果在可供选择的前k(kn)个项目中，必须且只能选择一项，则加入新的约束条件：2、如果可供选择的k(kn)个项目是相互排斥的，则加入新的约束条件：3、如果在可供选择的k(kn)个项目中，至少应选择一项投资，则加入新的约束条件：4、如果项目j的投资必须以项目i的投资为前提，则加入新的约束条件：5、如果项目i与项目j要么同时被选中，要么同时不被选中，则加入新的约束条件：XjXi Xj=Xi (ij)（二）对可供资源的选择1、如果对第r种资源br与第t种资源bt的投资是相互排斥的，即只允许对资源br与bt中的一种进行投资

30、，则可将第r个和第t个约束条件改写为： 其中y为新引进的0-1变量，M为充分大正数。其中M为充分大的正数，k为整数。2、如果问题是要求在前m个约束条件中至少满足k(1km)个，则可将原约束条件修改为：例：某公司计划开办五家新商店，分别由5家建筑公司承建。已知建筑公司Ai 对新商店Bj的建造费用报价为Cij万元。问如何分配建造任务，使总费用最少？CijB1B2B3B4B5A14871512A279171410A3691287A46714610A569121063.5 指派问题设0-1变量xij =1 当Ai承建Bj时0 当Ai不承建Bj时(i,j=1,2,5)=4x11+8x12+ 7x13+1

31、5x14+12x15 + 7x21+9x22+17x23+14x24+10 x25 +6x31+9x32+12x33+ 8x34+ 7x35 + 6x41+7x42+14x43+ 6x44+10 x45+6x51+9x52+12x53+10 x54+ 6x55 Min z x11+x12+x13+x14+x15 =1 x21+x22+x23+x24+x25 =1 x31+x32+x33+x34+x35 =1 x41+x42+x43+x44+x45 =1 x51+x52+x53+x54+x55 =1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+

32、x23+x33+x43+x53 =1 x14+x24+x34+x44+x54 =1 x15+x25+x35+x45+x55 =1 表示第j项工作只指派一人完成 表示第i人被指派完成一项工作St.有n项任务，恰好有n个人可承担这些任务，但由于每人的技术专长不同，完成任务的效率不同，为使总效率最高（利润最高、成本最低、时间最少），应如何指派人员。一、指派问题的数学模型及其特点效率矩阵（系数矩阵）C=(Cij)nxn0，必有最优解是一种特殊的运输平衡问题二、指派问题的求解匈牙利法对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工

33、作的效率都提高或降低相同的效率（常数di），也不影响其最优指派。若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。71例 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表，问如何分配任务使完成四项任务的总工时耗费最少？72清华算法定理 1 如果从效率矩阵aijmm中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵bijmm的任务分配问题的最优解等价于原问题的最优解。 证明：略定理 2 若方阵中一部分元

34、素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 证明：略 清华算法的基本思路：根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零73 清华算法的步骤：第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将 (

35、 )标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完； 清华算法的步骤：2、逐列检查，若该列只有一个未标记的零，对其加( )标记，将( )标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；3、重复1、2后，可能出现三种情况；a. 每行都有一个 (0)，显然已找到最优解，令对应(0)位置的 xij=1；b. 仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用 1. 2 中的方法继续标记。4、打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零

36、的指数，选指数最小的先标记 ( )；采用这种方法直至所有零都被标记，或出现 情况 a，或 情况 c 。 清华算法的步骤：c. 所有零都已标记，但标有( )的零的个数少于m； 开始划线过程： 对没有标记 ( ) 的行打 对打 行上所有其它零元素对应的列打 再对打 列上有 ( ) 标记的零元素对应的行打 重复 ，直至无法继续 对没有打 的行划横线，对所有打 的列划垂线 划线后会出现两种情况：(1) 标记( )的零少于m个，但划有 m条直线，说明矩阵中已存在 m 个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到 b 重新标记；(2) 少于m条直线，到第三步；76 清华算法的步骤：第三步：进

37、一步变换； 在未划线的元素中找最小者，设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用 定理 1第四步：抹除所有标记，回到第二步，重新标记；77 清华算法的步骤：答：最优分配方案为 x13= x21= x34 = x42 =1，其余为0， 即甲C，乙A，丙D，丁B，OBJ=2078关于清华算法的适用条件要求所有aij 0若某些 aij 0 ，则利用定理 1 进行变换，使所有 bij 0目标函数为min型对于max型目标函数，将效率矩阵中所有 aij 反号，则等效于求min型问题；再利用定理 1 进行变换，使所有 bij 0，

38、则可采用清华算法 打破僵局时选择不当的结果：结果仅出现 3 个标记( )，但却划出 4 条线， 说明什么？！三、非标准形式的指派问题1、最大化指派问题 用最大元素去减各系数2、人数和事数不相等的指派问题 添加虚拟的人或事，其费用系数03、一人可做几件事的指派问题 化作相同的若干个人，其做同样事的费用系数相等4、某事一定不能由某人做的指派问题 其费用系数取足够大的数LINDO可用于求解纯整数规划或混合整数规划(IP) 模型与LP问题类似, 但在END标志后需定义整型变量一、Lindo求解一般整数变量由命令GIN（GENERAL INTEGER ）来标识GIN X：将变量X标识为一般整数变量； G

39、IN n：将前n个变量（按输入顺序）标识为一般整数变量。3.6 软件解法二、Excel求解对决策变量（可变单元格）另外添加约束int（整数）：表示限制该变量为整数变量bin（二进制）：表示限制该变量为0-1变量 0-1型整数变量由命令INT（INTEGER）来标识 INT X：将变量X标识为0/1型整数变量； INT n：将前n个变量（按输入顺序）标识为0-1型整数变量。3.7 整数规划的应用整数规划的应用(1) 一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密

40、集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+

41、58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 为0-1变量，i = 1,2,3,10二、固定成本问题 例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如右表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器

42、有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时） 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型：Max

43、z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 为0-1变量，i = 1,2,3整数规划的应用(2)例6有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如右表所示，问应如何指派工作，才能使总的消耗时间为最少。 解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时) 这可以表示为

44、一个0-1整数规划问题：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+

45、x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4 * * * 求解可用管理运筹学软件中整数规划方法。 整数规划的应用(3)三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。 四、分布系统设计例7某企业在 A1 地已有一个工厂，其产

46、品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如右表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂? 解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yi = 1(当Ai 被选中时)或0（当Ai 没

47、被选中时) 这可以表示为一个整数规划问题：Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t. x11+ x12+ x13 30 ( A1 厂的产量限制) x21+ x22+ x23 10y2 ( A2 厂的产量限制) b）增加约束：y2+y3=1 x31+ x32+ x33 20y3 ( A3 厂的产量限制) x41+ x42+ x43 30y4 ( A4 厂的产量限制) x51+ x52+ x53 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij 0 yi为0-1变量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用管理运筹学软件中整数规划方法。 整