第三章 整数规划
x2
x3
x4 x4
x5 x5
-My4
?0 ?0 ?0 ?0 ?0 ?0 ?0
-My5
x1 -50y1
-50y2
-50y3
-50y4
-50y1
x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1
取M＝10000，以上整数规划的最优解为：
y1=1，y2=1，y3=1，y4=1，y5=0；
x1=155件，x2=745件，x3=50件，x4=65件，x5=0件 最大利润为z=19285元。
3、 如果产品1安排生产，产品2就不能生产； 相应的约束条件为：
y1+y2?1
完整的整数规划模型为
max z= 24x1 +18x2 +21x3 +17x4 +22x5 st
5x1 +x2 +3x3 +2x4 +4x5
3x2 +4x3 +x4 +5x5
+x3 +3x4 +2x5 x3
x4
x5
x2
3x1 +2x2 x1
?1800 ?2500 ?2200
?0 ?0 ?0 ?0 ?0 ?1
-My1
-My2
- My3
-My4
-My5
y1 +y2
x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1
取M＝10000，以上整数规划的最优解为：
y1=0，y2=1，y3=1，y4=1，y5=0；
x1=0件，x2=435件，x3=205件，x4=375件，x5=0件 最大利润为z= 18510元。
请注意，问题的条件是“如果产品1安排生产，产品2就不能生产”，而模型的约束条件y1+y2?1的涵义是“产品1和产品2两者最多只能有一个安排生产”，满足
6 第三章 整数规划
这个约束条件的有三种情况：产品1安排生产，产品2不生产；产品1不生产，产品2安排生产；产品1和产品2都不生产。模型的最优解在这三种情况中选择了产品1不安排生产，让产品2生产，这样的经济效益最好。
4、 如果产品4安排生产，产品5必须生产，而且至少生产50件； 相应的约束条件为
y5?y4 x5?50y5
完整的整数规划模型为
max z= 24x1 +18x2 +21x3 +17x4 +22x5 st
5x1 +x2 +3x3 +2x4 +4x5
x1
3x2 +4x3 x2
x3
+x4 +5x5 x4
3x1 +2x2 +x3 +3x4 +2x5
x5 x5
?1800 ?2500 ?2200 +y5
?0 ?0 ?0 ?0 ?0 ?0 ?0
-My1
-My2
-My3
-My4
-y4
-My5 -50y5
x1，x2，x3，x4，x5?0，为整数，y1，y2，y3，y4，y5=0,1
取M＝10000，以上整数规划的最优解为：
y1=1，y2=1，y3=1，y4=0，y5=0；
x1=188件，x2=809件，x3=17件，x4=0件，x5=0件 最大利润为z= 19431元。
和上面一样，整数规划的最优解不让假定的条件（如果产品4安排生产）出现，也就是选择产品4不生产，产品5也不生产。 例3.4 考虑固定成本的最小生产费用问题
在最小成本问题中，设第j种设备（j=1，2，?，n）运行的固定成本为dj，运行的变动成本为cj，则生产成本与产量xj的关系为
0?fj(xj)???dj?cjx当xj?0jfj(xj) 变动成本cjxj 固定成本dj xj
dj 当xj?0
也就是说，一台设备如果不开工，则既
7 第三章 整数规划
没有固定成本，也没有变动成本，成本为0，如果设备开工，无论生产量是多少，就会有固定成本dj，以及变动成本cjxj。设0－1变量yj表示第j台设备（j=1，2，?，n）是否开工，目标函数表示为
nnjjjyjminz??cx??dj?1j?1
同时，为了表示设备开工与否和产量的逻辑关系，建立相应的约束条件
xj≤Myj
j=1，2，?，n
这里M是一个很大的正数。
从以上约束条件可以看出，当yj=0时，xj=0；即第j种设备不运行，相应的运行成本
z=djyj+cjxj=0
当yj＝1时，0≤xj≤M，实际上对产量xj没有限制，这时相应的运行成本为
z=dj+cjxj 请看以下的数字例子。
某炼焦厂用原煤为原料生产焦炭，同时可以得到焦炉煤气和煤焦油。该厂有四台炼焦炉A，B，C，D，四台炼焦炉每吨原煤可以产出的焦炭、煤气和煤焦油以及这四台炼焦炉的固定成本、处理每吨原煤的变动成本如下表所示：
表格 4
炼 焦 炉 产品 成本 A 0.64 23 0.12 400 85 100 B 0.68 25 0.15 1200 81 150 C 0.71 27 0.17 2600 78 200 3
D 0.73 28 0.19 3100 76 250 焦炭（吨/吨原煤） 煤气（m3/吨原煤） 煤焦油（吨/吨原煤） 固定成本（元） 变动成本（元/吨原煤） 生产能力（吨原煤） 要求焦炭的产量不低于280吨，煤气的产量不低于10000m，煤焦油的产量不低于60吨，编制使总成本（包括固定成本和变动成本）最低的四台炼焦炉的原煤分配计划。
设分配给四台炼焦炉的原煤分别为x1，x2，x3，x4吨。如果忽略固定成本，这是一个线性规划问题。
min z= s.t.
85x1 0.64x1
+81x2 +78x3 +76x4
+0.68x2 +0.71x3 +0.73x4 ≥ 280
8 第三章 整数规划
23x1 0.12x1
x1
+ 25x2 + 27x3 + 28x4 ≥10000
≥0
+0.15x2 +0.17x3 +0.19x4 ≥ 60
x2
x3
x4
x1≤100 x2≤150 x3≤200 x4≤250
这个线性规划问题的最优解为x1=x2=0，x3=137.32，x4=250，最小总成本为z=29711.27元。
如果考虑固定成本，要引进四个0—1变量y1，y2，y3，y4，和四个约束条件 x1≤My1，x2≤My2，x3≤My3，x4≤My4
并且在目标函数中加上固定成本函数，构成如下的整数规划问题 min z= s.t.
85x1 +81x2 +78x3 +76x4 +400y1 +1200y2 +2600y3 +3100y4
y1
-My2
y2
-My3
y2
-My4
y4
23x1 + 25x2 + 27x3 + 28x4 x1 x1
x2 x2
x3
≥280 ≥60 ≤0 ≤0 ≤0 ≤0
=0,1
0.64x1 +0.68x2 +0.71x3 +0.73x4 0.12x1 +0.15x2 +0.17x3 +0.19x4
x4
≥10000
-My1
x1≤100 x2≤150 x3≤200 x4≤250
x3 x4≥0
令M＝10000，这个0－1混合规划的最优解为
y1=0，y2=1，y3=0，y4=1；x1=0，x2=143.38，x3=0，x4=250
即设备A和设备C不开工，设备B和设备D开工，分别分配原煤143.38吨和250吨给设备B和设备D，最小总成本为34913.97元。其中设备B的固定成本为1200元，变动成本为11613.97元；设备D的固定成本为3100元，变动成本为19000元。
下面我们就来介绍两种整数规划的求解方法。
9 第三章 整数规划
§3.2 割平面法
割平面法是求解正数规划的基本方法之一。割平面得基本思想是：首先放弃变量的整数要求，求得线性规划的最优解。如果最优解恰是一个整数解，则线性规划的最优解就是相应的整数规划的最优解。如果线性规划的最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解，求解新的线性规划问题，如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。 z x1 … xr … xm
设放弃变量整数要求得到的线性规划的最优单纯形表如下：
xm+1 xj z x1 … xr … xm … … 1 0 … 0 … 0 0 … 0 … 0 … … … 0 … 0 … 1 zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 … … … … zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 … … … … xn zm+1-cm+1 y1,m+1 … yr,m+1 … ym,m+1 RHS zo b1 … br … bm 1 … 0 … … 0 … 1 … … 0 … 0 其中x1，xr，xm为基变量，xm+1，xj，xn为非基变量。设其中基变量xr的值br不是整数，且
br=Ir+Fr
其中Ir是br的整数部分，Fr是小数部分，即
Ir=0，1，2，…，
0 设Irj是yrj的整数部分，Frj是小数部分，则 其中 Irj=0，?1，?2，…， yrj=Irj+Frj 由于yrj可能是整数，因此 0≤Frj≤1 这样，第r个约束成为 10