6整数规划模型 6.1引言 在许多最优化的应用问题中，人们要限制决策变量必须取整数值。例如，GM公司雪佛 莱汽车的年生产量是相关模型的决策变量，如果解答中该决策变量的值是1,524,328.37辆， 那么，这个值人们是无法接受的。人们并不介意雪佛莱汽车年产量是1,524,328辆还是 1,524,329辆。当然，如果另一项研究的最优解是建议制造1.37架飞机，那时，世界上就会 有很多人对这个数字及其周边的数字感兴趣。很显然，如果人们限制决策变量取整数值，很 多最优化模型的价值和有效性都将得到改变。 所有商用最优化模型系统都具有让用户限制一定的决策变量为整数变量的能力。如何实 现用户的整数要求，不同的程序有着不同的处理方法。例如，在LINGO中，如果要限制变 量X取整数，只要在模型中增加语句@GN(X就可以了。 按照变量的类型可以对整数规划模型进行如下分类： 纯整数模型s.混合模型。在一个纯整数模型里，所有的变量都取整数。在一个混合模 型里，有一些变量限制取整数，而另一些变量可以连续取值。 01模型s.一般整数模型。在许多应用问题中，很多变量只能取0和1两个整数。所以， 在一些整数规划模型中要限制若干个变量只能取0或1两个 数值。 限制变量取整数的要求可能比读者最初的想象要大得多。表示开/关的01整数变量在模 型中经常出现。或许现实中的整数规划多半都是具有01变量的整数规划。 6.2开拓整数规划(IP)的能力 人们在使用LP的时候常常会遇到一些用线性规划无法解决的困难。接下来，我们将介 绍如何利用整数变量来解决这些困难的方法。当然，一旦引入了整数变量，相应的模型就
6 整数规划模型 6.1 引言 在许多最优化的应用问题中，人们要限制决策变量必须取整数值。例如，GM 公司雪佛 莱汽车的年生产量是相关模型的决策变量，如果解答中该决策变量的值是 1,524,328.37 辆， 那么，这个值人们是无法接受的。人们并不介意雪佛莱汽车年产量是 1,524,328 辆还是 1,524,329 辆。当然，如果另一项研究的最优解是建议制造 1.37 架飞机，那时，世界上就会 有很多人对这个数字及其周边的数字感兴趣。很显然，如果人们限制决策变量取整数值，很 多最优化模型的价值和有效性都将得到改变。 所有商用最优化模型系统都具有让用户限制一定的决策变量为整数变量的能力。如何实 现用户的整数要求，不同的程序有着不同的处理方法。例如，在 LINGO 中，如果要限制变 量 X 取整数，只要在模型中增加语句@GIN(X)就可以了。 按照变量的类型可以对整数规划模型进行如下分类： 纯整数模型 vs.混合模型。 在一个纯整数模型里，所有的变量都取整数。在一个混合模 型里，有一些变量限制取整数，而另一些变量可以连续取值。 0/1 模型 vs.一般整数模型。在许多应用问题中，很多变量只能取 0 和 1 两个整数。所以， 在一些整数规划模型中要限制若干个变量只能取 0 或 1 两个 数值。 限制变量取整数的要求可能比读者最初的想象要大得多。表示开/关的 0/1 整数变量在模 型中经常出现。或许现实中的整数规划多半都是具有 0/1 变量的整数规划。 6.2 开拓整数规划（IP）的能力 人们在使用 LP 的时候常常会遇到一些用线性规划无法解决的困难。接下来，我们将介 绍如何利用整数变量来解决这些困难的方法。当然 ，一旦引入了整数变量，相应的模型就
变成了P模型。多数困难只要用0/1变量就可以解决而无需用一般的整数变量。0/1二元变 量可以表示范围非常广泛的诸如“去或是不去”、“生产或是购买”之类的决策问题。有时称 0/1二元变量为“哈姆雷特”变量。为了纪念逻辑学家George Boole,有时称0/1二元变量 为布尔变量。George Boole发明了变量只取两个数值“真”或“假”的布尔代数。当然，用 数值1表示“真”，用数值0表示“假”在概念上也是一个飞跃。 6.2.1用0/1二元变量表示一般的整数变量 有一些运算法则在应用时限制只能利用01整数变量。从概念上来看，任何在一定范围 内取值的整数变量都可以用一些01变量来表示。例如，假设限制X的取值集合是 [0,1,2,.,15。如果引入4个0/1变量：y,2,y3和y4,则变量X的任何一个值都可以用1+ 2×y+4×y3+8×y4代替。注意，[0,1,2，.，15)中的任何一个值都可以用一组y1,y2,y3和y4的值 表示。如果变量X的最大值可以取到31，你就需要5个0/1变量。如果最大值达到63，你 就需要6个01变量。事实上，如果你用k个01变量，那么，你可以表示的最大值就是2-1。 你可以记：VMAX=2k1。通过对这个等式取对数你就会发现，如果用0/1变量表示一般的 整数变量，所需01变量的个数近似为以2为底变量X最大取值的对数。 尽管这种替换是正确的，但还是要尽量避免。这是因为大多数整数规划模型在进行了这 种替换后的效率都不是很高。 6.2.2批量规模最小化约束 如果对经济活动的规模不加任何限制，效果并不是很好。因此，许多决策者对活动要指 定一个最小批量规模。例如，一个规模较大的中介公司要求买进和卖出的业务量至少要达到 100。用一个0/1变量就可以处理这个约束。令： x=活动的实际水平（例如，购买的股票数量）， y=1,只有当x>0时成立。Y是0/1变量， B=变量x的最小值（例如，100）， U=变量x已知的上限值。 下面两个约束将迫使最小批量规模条件成立： x≤Uy By≤X
变成了 IP 模型。多数困难只要用 0/1 变量就可以解决而无需用一般的整数变量。0/1 二元变 量可以表示范围非常广泛的诸如“去或是不去”、“生产或是购买”之类的决策问题。有时称 0/1 二元变量为“哈姆雷特”变量。为了纪念逻辑学家 George Boole ，有时称 0/1 二元变量 为布尔变量 。George Boole 发明了变量只取两个数值“真”或“假”的布尔代数。当然，用 数值 1 表示“真”，用数值 0 表示“假”在概念上也是一个飞跃。 6.2.1 用 0/1 二元变量表示一般的整数变量 有一些运算法则在应用时限制只能利用 0/1 整数变量。从概念上来看，任何在一定范围 内取值的整数变量都可以用一些 0/1 变量来表示。例如，假设限制 X 的取值集合是 [0,1,2,.,15]。 如果引入 4 个 0/1 变量：y1, y2, y3 和 y4，则变量 X 的任何一个值都可以用 y1 + 2×y2 + 4×y3 + 8×y4 代替。注意，[0,1,2,.,15]中的任何一个值都可以用一组 y1, y2, y3 和 y4 的值 表示。如果变量 X 的最大值可以取到 31，你就需要 5 个 0/1 变量。如果最大值达到 63，你 就需要 6 个 0/1 变量。事实上，如果你用 k 个 0/1 变量，那么，你可以表示的最大值就是 2 k -1。 你可以记：VMAX = 2k -1。通过对这个等式取对数你就会发现，如果用 0/1 变量表示一般的 整数变量，所需 0/1 变量的个数近似为以 2 为底变量 X 最大取值的对数。 尽管这种替换是正确的，但还是要尽量避免。这是因为大多数整数规划模型在进行了这 种替换后的效率都不是很高。 6.2.2 批量规模最小化约束 如果对经济活动的规模不加任何限制，效果并不是很好。因此，许多决策者对活动要指 定一个最小批量规模。例如，一个规模较大的中介公司要求买进和卖出的业务量至少要达到 100。用一个 0/1 变量就可以处理这个约束。令： x =活动的实际水平(例如，购买的股票数量)， y = 1, 只有当 x >0 时成立。Y 是 0/1 变量， B = 变量 x 的最小值 (例如，100)， U= 变量 x 已知的上限值。 下面两个约束将迫使最小批量规模条件成立： x ≤ Uy By ≤ x
如果y=0,那么第1个约束将迫使变量x=0。而如果y=1,第2个约束将迫使变量x 不少于B。所以，y实际上就是一个开关变量，它迫使变量x要么取值O,要么取值大于B。 选择常数U要特别注意，为了提高计算效率，在保证合理性的前提下，常数U的选择应该尽 量地小。 6.2.3固定收费问题 与最小批量规模情况很相似的一个问题就是一个活动的成本函数是固定成本加上呈线 性变化的可变成本。详见图6-1。 Cost 图6-1固定成本加上线性变化的可变成本的成本曲线 定义x,y和U如前，令K表示当x>O时的固定成本。那么，下面的语句将会出现在目 标函数中： Minimize Ky +cx+. subject to x≤Uy 目标函数中的项目Ky暗示：除非成本K发生，否则x的值不能大于0。同样，为了提 高计算的效率，常数U应该尽量小。 6.2.4简单的工厂定位问题(SPL) 求解简单的工厂定位问题($PL)就会遇到固定收费问题。下面给出详细说明：
如果 y = 0，那么第 1 个约束将迫使变量 x = 0。而如果 y = 1，第 2 个约束将迫使变量 x 不少于 B。所以，y 实际上就是一个开关变量，它迫使变量 x 要么取值 0，要么取值大于 B。 选择常数 U 要特别注意，为了提高计算效率，在保证合理性的前提下，常数 U 的选择应该尽 量地小。 6.2.3 固定收费问题 与最小批量规模情况很相似的一个问题就是一个活动的成本函数是固定成本加上呈线 性变化的可变成本。详见图 6-1。 图 6-1 固定成本加上线性变化的可变成本的成本曲线 定义 x, y 和 U 如前，令 K 表示当 x > 0 时的固定成本。那么，下面的语句将会出现在目 标函数中： Minimize Ky + cx +. subject to x ≤ Uy . . . 目标函数中的项目 Ky 暗示：除非成本 K 发生，否则 x 的值不能大于 0。同样，为了提 高计算的效率，常数 U 应该尽量小。 6.2.4 简单的工厂定位问题(SPL) 求解简单的工厂定位问题(SPL)就会遇到固定收费问题。下面给出详细说明：
n=工厂打算定位（或开工）的工地数目， =消费者（或需求点）的数目，每一个消费者必须指定一个工厂， k=可以开工的工厂数目， f=一个工厂在工地i开工的固定成本（例如，每年），i=1,2,.,n, c=在工地i开工的工厂被指派给消费者j的成本（例如，每年），i=L,2,.,n和j=L, 2,.,m。 这个问题的目标就是确定工厂将要定位或开工的工地集合，以便为每一个消费者提供服 务。 定义决策变量： y:=1如果一个工厂被定位在工地i,否则0， x=1如果消费者j被指定到工地i的工厂，否则0。 这个问题是一个很简单的P模型： Minimize ∑fy+∑∑cx (1) subject to ∑x=1 j=1,2,.,m (2) ∑，≤my i=1,2, (3) ∑y=k (4) yi=0or1 i=1,2,.,n (5) x=0or1i=1,2,.,n,j=1,2,.,m (6) 约束(2)将迫使消费者j被指定到一个确定的工地。如果一个消费者被指定到工地，约 束(3)将迫使有一个工厂定位到工地i。 我们再次提醒读者：尽管这种结构的模型并不是很大，但求解时仍需要非常多的计算时 间。产生困难的原因是这个问题属于整数规划。如果我们去掉约束(5)和(6)，然后再去求解（相 当于一个LP),得到的是分数解答，与最优整数规划解答相差甚远。 用下面的语句代替(3)： x≤y1i=1,2,.,nj=1,2,.,m(3) 如果有20个可能的工地和60个消费者，集合(3)有20个约束，而集合(3)有20×60=1,200
n = 工厂打算定位（或开工）的工地数目， m = 消费者（或需求点）的数目，每一个消费者必须指定一个工厂， k = 可以开工的工厂数目， fi = 一个工厂在工地 i 开工的固定成本(例如，每年) ，i = 1,2,.,n， cij = 在工地 i 开工的工厂被指派给消费者 j 的成本(例如，每年) ，i = 1,2,.,n 和 j = l, 2,.,m。 这个问题的目标就是确定工厂将要定位或开工的工地集合，以便为每一个消费者提供服 务。 定义决策变量： yi = 1 如果一个工厂被定位在工地 i, 否则 0, xij = 1 如果消费者 j 被指定到工地 i 的工厂，否则 0。 这个问题是一个很简单的 IP 模型: Minimize = = = + n i n i m j i i ij ij f y c x 1 1 1 (1) subject to = = n i ij x 1 1 j = 1,2,.,m (2) = m j ij myi x 1 i = 1,2,.,n (3) = = n i i y k 1 (4) yi = 0 or 1 i = 1,2,.,n (5) xij= 0 or l i = 1,2,.,n, j = 1,2,.,m (6) 约束(2)将迫使消费者 j 被指定到一个确定的工地。如果一个消费者被指定到工地 i，约 束(3)将迫使有一个工厂定位到工地 i。 我们再次提醒读者：尽管这种结构的模型并不是很大，但求解时仍需要非常多的计算时 间。产生困难的原因是这个问题属于整数规划。如果我们去掉约束(5)和(6)，然后再去求解（相 当于一个 LP），得到的是分数解答，与最优整数规划解答相差甚远。 用下面的语句代替 (3)： xij ≤ yi i = 1,2,.,n j = 1,2,.,m (3') 如果有20个可能的工地和60个消费者，集合(3)有20个约束，而集合(3')有20 × 60 = 1,200
个约束。然而，从经验上看，当用(3)代替(3)而将这个问题化成一个LP来求解时，解答自然 是整数。 6.2.5能力受限制的工厂定位问题(CPL) 如果一个工厂把满足需求的数量作为重点考虑的因素，那么从SPL问题就会引出CPL 问题。特别地，CL问题假设每一个消费者的需求数量己知，每一个工厂生产的产品数量 受产品总量的限制。额外的参数定义如下： D=消费者j的需求量， K=定位于工地i工厂的产量 相应的P模型如下： Minimize ∑fy+∑∑c (7) subject to ∑=1 j=1,2,m (8) ∑%Dx,≤Ky i=1,2,.,n (9) X≤y (10) y=0or1i=1,2,.,n, (11) X=00r1i=1,2,.,nj=1,2,.m (12) 这是一个“单来源”版本问题。由于变量X被限制为0或1，每一个消费者必须将它的 全部消费需求固定在一个工厂。如果“多-来源”被允许的话，变量可以是分数，分数本 身表明消费者j在工厂i的消费比例。在这种情况下，条件(12)应该去掉。如果看重单来源， 就不希望有多来源。例如，在小学到中学的指派问题中，同一个小学的同学都希望去同样一 所中学。 6.2.6实例1 Zzyzx公司在下列城市分别有一个货栈：(A)Baltimore,(B)Cheyenne,.(C)Salt Lake City, (D)Memphis and(E)Wichita,这些货栈为全美国的消费者供货。我们将前美国的消费者集中 起来，认为他们分别在下列城市：(1)Atlanta,(2)Boston,.(3)Chicago,(4)Denver,(5)Omaha
个约束。然而，从经验上看，当用(3')代替(3)而将这个问题化成一个 LP 来求解时，解答自然 是整数。 6.2.5 能力受限制的工厂定位问题(CPL) 如果一个工厂把满足需求的数量作为重点考虑的因素，那么从 SPL 问题就会引出 CPL 问题。 特别地，CPL 问题假设每一个消费者的需求数量已知，每一个工厂生产的产品数量 受产品总量的限制。额外的参数定义如下： Dj = 消费者 j 的需求量， Ki = 定位于工地 i 工厂的产量 相应的 IP 模型如下： Minimize = = = + n i n i m j i i ij ij f y c x 1 1 1 (7) subject to = = n i ij x 1 1 j = 1,2,.,m (8) = m j j ij i i D x K y 1 i = 1,2,.,n (9) xij≤yi (10) yi = 0 or 1 i = 1,2,.,n, (11) xij= 0 or l i = 1,2,.,n j = 1,2,.,m (12) 这是一个“单-来源”版本问题。由于变量 xij 被限制为 0 或 1，每一个消费者必须将它的 全部消费需求固定在一个工厂。 如果“多-来源”被允许的话，变量 xij 可以是分数，分数本 身表明消费者 j 在工厂 i 的消费比例。在这种情况下，条件(12)应该去掉。如果看重单来源， 就不希望有多来源。例如，在小学到中学的指派问题中，同一个小学的同学都希望去同样一 所中学。 6.2.6 实例 1 Zzyzx 公司在下列城市分别有一个货栈：(A) Baltimore, (B) Cheyenne, (C) Salt Lake City, (D) Memphis and (E) Wichita，这些货栈为全美国的消费者供货。我们将前美国的消费者集中 起来，认为他们分别在下列城市： (1) Atlanta, (2) Boston, (3) Chicago, (4) Denver, (5) Omaha