第四章 整数规划

第四章 整数线性规划

（Inregre Linear Progemming ）

§1 整数规划特点及应用

前面讨论的LP 的最优解可能是分数或小数。但是在经济管理和工程实践中，常常会出现要求变量值取整数的现象。如决策变量是机器台数、人数或车辆数等。最初有些人认为：只要对非整数解“舍入取整”即可。但后来发现这是不行的。因为舍入取整后的解不见得是可行解，即使是可行解，也不一定是最优整数解。因此，这里另设一章，研究此问题，并称这种求整数最优解的LP 问题为整数线性规划，简记为“ILP ”。

整数规划分为许多类型：通常把所有变量都要求取整数的整数规划，称其为全（纯）整数规划；把部分变量要求取整数的整数规划，称为混合型ILP 。把所有变量取值均为0或1的整数规划称为0-1规划。等等。

求解整数规划的一种简单方法是：先不考虑整数条件，直接求解相应的线性规划问题，当最优解为非整数且数值都较大时，把非整数最优解取整到最接近的整数可行解即可。但是，当最优解为非整数且数值都较小时，这种舍入化整的办可能导致解的可行性被破坏。例如，我们来研究下面整数规划问题。

例4-1求解下面ILP 问题： 相应的LP ：

??

?????≥≤+≤++=为整数2

1212

1212

1,0,5

.45.014

3223max x x x x x x x x x x z ?????≥≤+≤++=0,5.45.0143223max 2

12

1212

1x x x x x x x x z

解：若先不考虑整数约束条件求解相应的LP问题，由图解法得可行域如图4-1。最优解X*=（3.25，2.5）。

所谓整数解，即要求变量取整数值。而由X*舍入化整得到的解，如（4，3）或（4，2）或（3，3）都不在可行域上，所以都不是可行解，而（3，2）虽是可行解，但它并不是最优整数解，因为该例有一个可行解X=（4，1），其目标值Z=14，大于可行解（3，2）的目标值13。

为了求得该整数规划的最优整数解，我们将经过B点的目标函数等值线向可行域内平行移动，首次碰到的整数点即为所求。在本例中，最优整数解点就是（4，1）相应的Z=14。本例说明，在一般情况下，企图用舍入化整的办法直接得到最优整数解是不可取的，必须专门研究其解法。

促使人们研究整数规划还有其他原因，就是整数规划模型，还能为处理某些特殊问题提供一种很好的方法，因为有些问题不利用整数规划就很难处理。例如，投资工作中的许多决策问题，还有资源分配问题中，有多重约束条件的选择问题，等等。都属于这种情况。

下面我们就用例子来说明整数规划模型的应用。

例4-2 试利用0-1变量将下列各题分别表示成一般线性约束条件。

（1）X1+X2 ≤ 2 或2X1+3X2 ≥ 5

（2）变量X只能取值0、3、5或7中的一个

（3）若X1≤2，则X2≥1，否则X2≤4

（4）以下四个约束条件中至少满足两个：

X1+X2≤5，X1≤2，X3≥2，X3+X4≥6

解：

（1）设???≤+≤+=起作用时

当不起作用时

当221,02211x x x x ，y

∞

→--≥++≤+M y M x x My

x x ,)1(52312221

（2）

??

?=+++++=??

?==1

4321473523,07,5,3,01y y y y y y y x x ，y i 否则

时当设

（3）

组

第组

第组条件起作用时当第组条件不起作用时当第设2)1(42)1(21112211,011??

?-+≤--≥???-≥+≤??

?=M

y x M y x My

x My x ，y

（4）

设???==4

,3,2,1,01，i ，y i 满足时不满足时

则

?

??

??

???

?????===≤+++-≥+-≥+≤+≤+∑∑∑则有两个满足

则有三个满足则全满足,2,1,02

43214

6433232211521i i i y y y y y y y My x x My x My x My x x 下面看一个实际问题。假定某化工厂有两条生产线A1和A2均可用来生产三种化肥B1，B2，B3。用A1生产1吨B1，B2，B3分别需要5，7，6小时，用A2生产1吨B1，B2，B3分别需要4，5，3小时。A1和A2分别有200，300小时可供利用。该厂决定只用两条生产线中的一条生产，但用哪条生产线生产尚未决定。

若设该厂生产B1，B2，B3种化肥分别为X1，X2，X3吨。则依题意，必须满足下面两

个约束条件之一：

5X+7X+6X ≤200 4X+5X+3X ≤300

这种情况就类似上面的例题，需要设一个0-1变量处理。比如设

设???=生产线生产若用，生产线生产

若用201,1A A Y

上面两个约束条件可表示为

5X+7X+6X ≤200+MY (M 为任意大的正数) 4X+5X+3X ≤300+M （1-Y ）

Y=0或1

若Y=0，则上面第一个约束条件有效，而第二个约束条件是多余的; 若Y=1，则上面第二个约束条件有效，而第一个约束条件是多余的。这种结果还可以推广到一般情况，假定在某一问题中有m 个约束条件：

m i b a

i n

j ij

,,2,1,

),(1

==≥≤∑=

其中只有k 个必须满足，但事先并不知道是哪k 个。

这是可设k 个0-1变量

??

?==m i i i Y i ,,2,10,1 ，个约束条件必须满足时

当第，个约束条件不必满足时

当第 并将上面m 个约束条件表示为下面的约束即可。

????

?

?

?????==-==+=≥≤∑∑==m i Y k m Y m i Y M b a i m i i i i n

j ij ,,2,110,,2,1,

),(11

，或

例4-3设某国际巧克力公司生产两种产品，朱古力和朱尔斯，其相关数据如下：

可以利用的有限资源：机器工时700；直接人工工时5000。求产品如何组合才能使公司的效

益达到最大。

解：设利润为Y ，产品朱古力和朱尔斯的产量分别为X 1 X 2

MAX Y=1.00X 1+2.00X 2

S.T 0.02X 1 + 0.05X 2<=700

0.20X 1 + 0.25X 2<=5000 X 1 ,X 2 >= 0, 且为整数

例4-4 有n 个工厂拟在n 个不同的厂址上建设。已知从i 厂到j 厂的物资运量为d i j ，又知从p 厂址到q 厂址单位物资的运费为C pq 。试将这个问题归结成一个整数规划模型，目标是使总运费为最少。

解：设???==n j 。i ，j i x ij ,,1,0,

,1 否则处时厂址建在如果工厂

则此问题的模型为：

)

,,2,1,(1,0,,2,1,1,,2,1,

1m i n 1

11,1

,n j i X n

i x

n

j x

c d x x

Z ij n

j ij

n

i ij

pq

ij n

j i j i n

q

p q p jq ip

=======

∑∑∑∑==≠=≠=

例4-5某钻井队要从以下10个可供选择的井位中确定5个钻井探油，目标是使总的钻探费用最小。若10个井位的代号为S1，S2，S3，S4，S5，S6，S7，S8，S9，S10，相应的钻探费用为C1，C2，C3，C4，C5，C6，C7，C8，C9，C10，并且井位的选择上要满足下列条件：

（1） 或选择S1和S7，或选择钻探S8；

（2） 选择了S3或S4，就不能选择S5，反过来也一样； （3） 在S2、S6、S9、S10中最多只能选择两个 试建立这个问题的数学模型。

解：??

???==10,,1,0,1 j ，S S x j j j 井位钻探时当不选择井位钻探时

当选择设

10

,,1,

105

2

1

111min 10

1

109625453878110

1 ===≤+++≤+≤+=+=+=∑∑==j x x

x x x x x x x x x x x x x c Z j j j

j j

j 或

例4-6 某厂需生产2000件产品，该产品可利用A 、B 、C 设备中的任意一种（或两种或三种）设备加工。已知每种设备的生产准备费用、生产该产品时的单位成本以及每种设备限定的最大加工数量如下表所示，试建立使总费用最小的生产计划问题数学模型。

解：用j=1，2，3表示A 、B 、C 三种设备，X j 表示在设备j 上加

工的产品数量，再设

?

??==3,2,10,1，j j ，j y j 加工时不用设备加工时用设备 则有

3

,2,1100120080060020002000300010005020100min 3

3

22

11

3213

21321==≥≤≤≤=+++++++=j ，，y

x y x y x y x x x x y y y x x x Z j

j 或且为整数

§2 分枝定界法*

分枝定界法是求解混合整数规划与纯整数规划的一种常用的有效方法，多数求解ILP 的软件也是用分枝定界法编写的。

分枝定界法的思想是先不考虑整数约束条件，直接求解其相应的LP （又称其为松弛问题）。若相应的LP 的最优解不是整数解，则由其最优目标函数值可确定出原ILP 目标函数的上（下）界，称此为定界。然后增加约束条件把原ILP 分成两个子问题，称其为分枝。接下来求解子问题，由此，不断缩小原ILP 目标函数的上界，直至求出最优整数解或判断出无解为止。

下面我们通过例子来说明分枝定界法的具体求解过程。

例4-6 用分枝定界法求解上节中例1-1问题。

解：1、先不考虑整数约束条件，用图解法求得相应LP 的最优解为：

X *=（3.25，2.5），Z *=14.75

因为LP 可行域上所有整数点是原ILP 的全部可行解，所以原ILP 的最优解应在这些整数点当中。

上面求出LP 的最优解X *虽不是整数解，但由图可知，Z *是原ILP 目标值的上界。这是因为ILP 的全部可行解（即可行域上全部整数点）的目标函数值都不会超过Z *。所以称这一步为定界。

2、分枝

在ILP 中，X 1，X 2要求取整数值。若X 2取整数值，就要在X 2≤2或X 2≥3中取值，为此，我们将X 2≤2和X 2≥3分别加入原ILP 中，将ILP 分成两个子问题。即

ILP1： ILP2： ??

????

?≥≤≤+≤++=为整数0,25

.45.0143223max 2122

12121x x x x x x x x x z ??

????

?≥≥≤+≤++=为整数

0,35

.45.014

3223max 2122

1212

1x x x x x x x x x z

显然这两个子问题把LP 的可行域划分成部分，但是，这样划分，并未丢掉原ILP 的可行解。我们称这一划分过程为分枝。

因为ILP1和ILP2的全部整数可行解仍包含ILP 的全部可行解，所以我们可通过求解ILP1和ILP2的松弛问题LP1和LP2来寻找原ILP 的最优整数解，于是由图解法得：

LP1的X 1*=（3.5，2），Z 1*=14.5 LP2的X 2*=（2.5，3），Z 2*=13.5

3、修改原ILP 目标函数值的上界

由LP1和LP2的最优目标函数值Z 1*和Z 2*知，当X 2≤2时，原ILP 的目标值不会超过14.5；当X 2≥3时，原ILP 目标函数值不会超过13.5。从而可知，在可行域上，无论X 2取何整数值，原ILP 的目标值均不会超过14.5，于是我们应把前面确定的目标值上界由14.75修改为14.5。

因为求解两个子问题仍未得到原ILP 的最优整数解，为此将新上界对应的ILP1再分枝。考虑到X 1*=（3.5，2）中X 1=3.5仍非整数，不合要求，再把X 1≤3或X 1≥4分别加入ILP1中，将ILP1分成两个子问题如下：

ILP3： ILP4：

?????

??

??≥≤≤≤+≤++=为整数

0,325.45.0143223max 2112

21212

1x x x x x x x x x x z ?????

??

??≥≥≤≤+≤++=为整数

0,425.45.014

3223max 2112

21212

1x x x x x x x x x x z 显然子问题ILP3和ILP4的整数可行解中包含了ILP1中的全部整数可行解，因此我们可通过

求解ILP3和ILP4的松弛问题LP3和LP4来寻找原ILP1的最优整数解，于是由图解法得：

LP3的X 3*=（3，2），Z 3*=13 LP4的X 4*=（4，1），Z 4*=14

此结果表明，在LP1的可行域上，无论X 1取何整数值，ILP1的最优目标值都不会超过Z 4*=14，而ILP2的目标值Z 2*=13.5也不超过14，所以可断定原ILP 的目标值不会超过14，为此我们再把原ILP 的目标值上界修改为14。

由于LP4的X 4*=（4，1）是整数解，且其Z 4*=14是原ILP 目标值的上界，已经达到了最大值，因此可确定X 4*=（4，1）就是原ILP 的最优整数解，分枝计算结束。整个求解过程

可用一个树形图来表示：

x 1≤3

(LP1) (LP3)

x 2≤2 (3.5，2) x 1≥4 (3，2)，13 14.5

（LP ） x 2≥3 (LP4)

（3.25，2.5） (LP2) (4，1)，14 14.75 (2.5，3)，13.5

分枝定界法小结

（一） 先将求解最大化的ILP 的松弛问题LP （若是最小化的ILP ，可先化成最大化的ILP ），有以下结果之一：

1．若LP 无可行解，则原ILP 也无可行解，计算结束；

2．若LP 的最优解是整数解，则它也是原ILP 的最优解，计算结束；

3．若LP 的最优解不是整数解，则其目标函数值是ILP 目标函数值的上界，转下步。

（二） 在LP 的最优解中选取小（分）数部分大的变量作为分枝变量，假定j j b x =的小

（分）数部分大，则以j j b x =构造两个约束条件)int(j j b x ≤和1)int(+≥j j b x 分别加入ILP ，将ILP 分成两个子问题ILP1和ILP2；

（三） 求解子问题的松弛问题LP1和LP2，并修改ILP 目标值的上界，若新上界所对应

的解为整数解或符合混合整数规划条件，则这个解就是原ILP 的最优解，计算结束，否则，对新上界对应的子问题继续分枝，直到求出最优解为止。

§3 利用E xcel 求解整数规划问题

例4-7 某地区有两个城镇，它们每周分别产生700吨和1200吨固体废物。拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理，如下图4-2所示。每个处理场所的处理成本分为固定成本和变动成本两部分，其数据如表1所示。两城镇至各处理场所的运输成本、应处理量与各处理场所的能力如表2所示。试求使两城镇处理固体废物总费用最小的方案。

城镇1（700吨）

焚烧（1000吨） 填海（500吨） 掩埋（1300吨）

城镇2（1200吨）

图4-2

表1

解：以i =1，2分别表示城镇1和城镇2；j =1，2，3分别表示焚烧、填海和掩埋三种废物处理方式。用X ij 为按j 方式每周处理城镇i 的废物吨数，再设

???==3,2,1,,0,

1j j j Y j 方式处理时不采取第方式处理时采取第

则该问题的数学模型为：

??????????

?===≥≤+≤+≤+=++=++++++++++++++++=)

3,2,1;2,1(10,0130050010001200

700

192011503850)5.126()5.716()0.512()0.156()0.516()5.712(min 323132

221212111232221

1312113

2123222113

1211j i Y X Y X X Y X X Y X X X X X X X X Y Y Y X X X X X X Z j ij 或 在E xcel 工作表上建立运价表和变量表，如图4-3所示。

图4-3 运价表和变量表

将工作表的B9:D10及B12：D12区域作为可变单元格，在单元格B13中输入目标函数表达式“=SUMPRODUCT（B3:D4, B9:D10）+ SUMPRODUCT（B6:D6, B12:D12）”。

在单元格B14：B18中输入约束条件左边表达式，在单元格D14 ：D18中输入约束条件右边值，然后进行规划求解，“规划求解”对话框如图4-4所示。

图4-4 规划求解”对话框

规划求解结果如图4-5所示。

图4-5 求解结果

§4 分配问题

（一）分配问题的数学模型

在管理工作中，会遇到这样的问题，某部门需要完成若干项任务，并有若干个对象可承担这些任务。由于第个对象的特点不同，各对象完成任务的效率也不同。于是就产生了分配哪个对象去完成哪项任务，可使完成任务的总效率最高。这里的效率可以是时间、费用、成本、收益等。这类问题就是分配问题，

例4-8 有一份中文说明书，要翻译成英、日、德、俄四种文字，分别交甲、乙、丙、丁四人完成，由于各人的专长不同，完成不同文字翻译所需时间见下表，问如何分配可使四人分别完成四项工作的总时间最少？

每个分配问题都有类似于例1问题的一个效率表。将这种表用矩阵表示，即C=(C

ij )

nхn

，

并称之为效率矩阵，其中第i行第j列元素C

ij

≥0，(i,j=1,2,…,n)表示第j个人去完成第i项任务的效率。因为分配问题需要决策的是分配哪个对象去完成哪项任务，为此，用i=1,2,3,4分别表示英,日,德,俄；j=1,2,3,4分别表示甲,乙,丙,丁四人，决策变量设为：

??

?==4,,1,0,1 j ，i i j ，i j x ij 项任务时人去完成第不分配第项任务时

人去完成第当分配第 对于求最小值的分配问题，其数学模型为：

()()

1

04,,1,

14,,1,1)

0,0(min 4

1

4

14

14

1

或一个人限定每项任务只分配给务限定每人只分配一项任则目标函数值的下界是因=====≥=∑∑∑∑====ij i ij

j ij

ij i j ij

ij x j x

i x

c x c Z

满足所有约束条件的可行解也可用矩阵表示，称之为解矩阵。例如，例1的可行解矩阵为：

?

?

???

???????=????????????=1000

001000010100

4443

42

41

3433323124232221

14131211

x x x x x x x x x x x x x x x x X

可行解矩阵X 中各行各列只有一个元素是1，其余均是0，所以每行每列元素之和都是1，满足约束条件。也就是说矩阵X 中4个1位于不同的行不同的列。显然这4个等于1的变量x 13，x 21，x 32，x 44对应的目标式系数C 13，C 21，C 32，C 44在C 矩阵中也位于不同行不同列。并且可行解X 对应的目标函数值Z （X ）= C 13+C 21+C 32+C 44。

定理1： 设C=(C ij )n хn 是一个效率矩阵，若可行解X *中n 个1对应的n 个C ij 都等于0，则此可行解X *是最优解。

证：因为Z （X *）=0，而对任何其他可行解X ，由于所有C ij >=0,X>=0,故Z(X)>=0,所以X *是最优解。

由此定理可知，若能在效率矩阵C=(C ij )n хn 中找出n 个位于不同行不同列的0元素，则最优解即可获得。但一般说来，这样的0元素并不是马上可以找到的，甚至所给的效率矩阵C 中根本就没有0元素，这时需要设法对效率矩阵C 进行变形。

匈牙利的数学家狄克尼格（D.Konig ）给出了一种简便的算法，就是通过对效率矩阵C 进行变形，首先使C 中含有0元素，然后从中找出n 个位于不同行不同列的0元素，从而获得最优解。人们称这一算法为匈牙利法。

（二）匈牙利算法

在求最小值的分配问题模型中，若效率矩阵中元素C ij ≥0，则目标函数的最小值为0，因此当效率矩阵C 中存在n 个位于不同行不同列的“0”元素时，可以直接给出其最优解。比如，设

?????

???????=??

???????

???=10

00

00100100000

1

,03

21

980760543210X C 因可行解 对应的目标函数值Z=0。 于是该可行解X 就是最优解。这表明只要C 矩阵中含有n 个位于不同行不同列的“0”元素，可以直接给出最优解X *。这是因为在目标函数中，等于1变量对应的系数都是零，因此目标函数值为零，而且是最小值。现在的问题是如何使C 中含有n 个位于不同行不同列的独立“0”元素呢？匈牙利的数学家狄克尼格（D.Konig ）给出了一个定理如下。

定理2 从效率矩阵C 的每行减去一个常数u i (i=1,…,n)，每列减去一个常数v j (j=1,…,n)后，得到的新效率矩阵B=(b ij )=(c ij -u i -v j )与C 的最优解相同。

证明：设Z '为新效率矩阵B 对应的目标函数值，则有：

常数

-=???

?

??+-=--=--=='∑∑∑∑∑∑∑∑∑∑∑∑============Z v u Z x v x u x c x v u c x b Z n i n j j i n j n

i ij

j n i n j ij i n

i n

j ij ij n i n

j ij

j i ij n i n j ij ij 111

1

1

1

11

11

11)(

由此可见，新效率矩阵B 的目标函数与原效率矩阵C 的目标函数只差一个常数，所以它们具有相同的最优解。

定理3 若矩阵C 中一部分元素为0，另一部分元素不为0，则划去C 中所有0元素所需的最少直线数等于C 中不同行不同列上的元素的个数。

根据上述定理，我们可将原效率矩阵C 变换成含有若干0元素的新效率矩阵B ，然后再从B 中找出位于不同行不同列的n 个0元素，这样我们就可以得到问题的最优解。这一算法被称为匈牙利法。

下面我们用上面例1问题的效率矩阵C 来说明匈牙利法的具体步骤。 1．变换C 矩阵。

（1）从C 的每行中减去该行的最小数；

（2）再从每列中减去该列的最小数，把变换后的新矩阵记为B 。 2．试求解（即在B 中查找位于不同行不同列的n 个0元素）

⑴ 检查B 矩阵，给只有0元素的行或列中的0加括号，并用直线划去（0）所在的列（行）。若B 矩阵中所有0都被直线划掉，并且每行都有一个（0）时，就得到了最优解（当分配问题的最优解不唯一时，会出现一些可以组成闭回路的0，无法被直线划掉，这时可先给闭回路上任一个0加括号，然后沿着闭回路走向，隔一个0加一个括号，也可得到了最优解）。若B 矩阵中所有0都被直线划掉，但仍有的行中没有（0），则转下一步。

⑵ 从未被直线划掉的数中找出最小数，假设为θ，并将未被直线划掉的所有数减去θ，将直线交叉点上的数加上θ，其余元素不变。然后再对加减完θ的矩阵重复第⑴、⑵步，直到每一行有一个（0）为止。比如，将例1的效率矩阵C 用匈牙利法。

第1步，变换C 矩阵如下：

经两次变换，在同解的新矩阵中找到了位于不同行不同列的4个0元素，即每一行每一列都有一个（0），于是解矩阵X 中与新效率矩阵中（0）对应的变量x 13 = x 22 = x 34 = x 41 = 1，其余x ij = 0，即为最优解，对应的最优分配方案为：

分配甲、乙、丙、丁四人分别翻译俄、日、英、德四种文字，总效率最高，只需要：C 13+C 22+C 34+C 41=9+4+11+4=28（小时）即可完成。

练习：用匈牙利法求解下列分配问题的效率矩阵

??

?

?

?

??

??5978711414910793641

??????? ?

?66

35546967582543

??????

?

??8111341115121561241369

82 ???

???

?? ?

?6426

4124523107496651673

293

(三)关于匈牙利法的两点说明

1、分配问题中如果人数和工作任务数不相等时的处理方法。例如，有四项工作要分配给六个人去完成，效率表见表4-1。仍然规定每人完成一项工作，每项工作只交给一个人去完成。这就等于从六个人中选择四个人去完成，要求花费的总时间最少。处理的方法是增加两项假想的工作参加分配，因为假想的工作不需要时间去完成，所以每人完成假想的工作的时间为

0，这就是说只要在原效率表中增加两列0（见表4-2），使人数与工作任务数相等，就能用上述匈牙利法求解了。当工作数多于人数时，类似地，可假想一些人参加分配来处理。

例4.9 拟分配甲、乙、丙、丁四个人去完成A 、B 、C 、D 、E 五项任务，每个人完成各项任务的时间(单位：小时)如表4-3所示，由于任务数多于人数，故考虑：

（1） 任务E 必须完成，其它四项任务中可任选三项完成；

（2） 其中有一人完成两项，其他每人完成一项； 试分别确定最优分配方案，使完成任务的总时间最少。

表4-3

解：（1）用匈牙利法求解得最优分配方案为：分配甲、乙、丙、丁分别去完成B 、D 、E 、A 项任务，放弃C 项任务，消耗的总时间最少，是105小时。

（2）用匈牙利法求解得最优分配方案为：分配甲、丙、丁分别去完成B 、E 、A 项任务，乙完成C 、D 两项任务，消耗的总时间最少，是131小时。

例4-10 某房地产公司计划在一个住宅小区建造5栋不同类型的楼房1B ，2B ，3B ，

4B ，5B 。

现有三家建筑公司1A ，2A ，3A 进行投标，允许每家建筑公司可承建1~2栋楼，经过投标得出建筑公司i A 对新楼j B 的预算费用ij C 见下表，求使总费用最少的分配方案。

解：先将B1分配给A1，B5分配给A3，然后再把余下的B2、B3、B4用匈牙利法分配给A1、A2、A3，得最优分配方案是A1承建B1和B3；A2承建B2；A3承建B4和B5，总费用42百万元。

2．若所给问题是求目标函数最大值的分配问题，其效率矩阵为C =（ij c ），此时，我们可先从C 矩阵中找出一个最大的元素C 0，再令

n j i c c b ij

ij ,,2,1,0 =-=

那么用上述匈牙利法求解以（b ij ）为效率矩阵的最小化问题就等于求解以（c ij ）为效率矩阵的最大化问题。

例4-11 求下面目标函数最大化的分配问题

????

?

????

???=9131541116141381441579102C 解： ????

?

????

???=7311250238212197614B §5 0-1规划与隐枚举法

所谓0-1规划就是所有变量取值均为0或1的规划问题，如下面投资问题。

例4-12 在今后三年内有五项工程可以施工，每项工程的期望收入和年度费用（万元）如下表所示，每项工程都需三年才能完成。问选择哪些工程施工可使三年的总收入最大？

解：

???==5,,1,0,1 j ，j j x j 项工程施工时不选择第项工程施工时

选择第设

则该问题的数学模型为：

5

,4,3,2,1102510210825649725873453015204020max 5432154321543215

4321==≤++++≤++++≤++++++++=j ，x x x x x x x x x x x x x x x x x x x x x Z j 或

最优解为X=（1，1，1，1，0），总收入95万元。

练习：设有n 个投资项目，其中第j 个项目需要资金a j 万元，投资以后可获利Cj 万元，现有资金总额为b 万元，问应选择哪些项目投资才能获利最大？

解：???==n j ，j j x j ,,1,0,1 个项目投资时不选第个项目投资时

选择第设

则该问题的数学模型为：

n

j ，x b

x a

x c Z j n

j j j

n

j j

j ,,2,110max 1

1

==≤=∑∑==或

一般的0-1规划模型为

n

j x m i b x a

x c z j n

j i j ij

n

j j

j ,,2,110,,2,1max 1

1

===≤=∑∑==，或

求解0-1规划问题可用隐枚举法，下面举例说明这一方法。 例4-13 用隐枚举法求解下面的0-1规划问题

3

,2,110)4(6

4)3(3)2(44)1(2

2523m a x 3213213213

21==≤+≤+≤++≤-++-=j ，x x x

x x x x x x x x x x x Z j 或

解：

1、将目标函数中变量按其系数大小递增排序（对min 问题按递减排序）。 约束条件中变量也要按目标函数中变量顺序排列。

3

,2,110)4(64)3(3

)2(44)1(2

2532m a x 311

23123123

12==≤+≤+≤++≤-+++-=j ，x x x x x x x x x x x x x x Z j 或

2、任选一个可行解X 0=（x 2,x 1,x 3）=（0，1，0），对应的Z 0=3。因为目标函数最优值是所有可行解的目标函数值的最大者，所以目标函数最优值不会小于Z 0=3，为此，增加一个约束条件：-2x 2+3x 1+5x 3≥3，记为（0）号约束条件，称（0）号约束条件为过滤条件（若目标涵数是求最小值时，（0）号条件为≤号）。

3、列表检查各种可能的解是否满足约束条件，若满足，就求出该可行解的目标函数值Z ，当Z>Z 0时，要修改（0）号条件的右边值为Z 。

(x2,x1,x3)(0)≥3(1)≤2(2)≤4(3)≤3(4)≤6满足约束否Z值说明

(0,0,0)

0×(0,0,1)5-1101√5改(0)≥5

(0,1,0)3×(0,1,1)80

2

1

1√8

改(0)≥8

(1,0,0)-2×(1,0,1)3×(1,1,0)1

×

4、比较求出的目标函数值大小，对max 问题取最大，对min 问题取最小，从而确定最优解为（x 1,x 2,x 3）=（1，0，1），max Z = 8。

例4-14 用隐枚举法求解下面的0-1规划问题

3

,2,110)4(935)3(3

3)2(543)1(4

34765m a x 322

13213213

21==≤+≤-≤++≤-++-=j ，x x x x x x x x x x x x x x Z j 或

解：

1、将目标函数中变量按其系数大小递增排序（对min 问题按递减排序）。 约束条件中变量也要按目标函数中变量顺序排列。

3

,2,110)4(9

35)3(33)2(543)1(4

34756m a x 32

123123123

12==≤+≤+-≤++≤-+++-=j ，x x x x x x x x x x x x x x Z j 或

2、任选一个可行解X 0=（x 2,x 1,x 3）=（1，0，0），对应的Z 0=5。因为目标函数最优值是所有可行解的目标函数值的最大者，所以目标函数最优值不会小于Z 0=5，为此，增加一个约束条件：-6x 2+5x 1+7x 3≥5，记为（0）号约束条件，称（0）号约束条件为过滤条件（若目标涵数是求最小值时，（0）号条件为≤号）。

3、列表检查各种可能的解是否满足约束条件，若满足，就求出该可行解的目标函数值Z ，当Z>Z 0时，要修改（0）号条件的右边值为Z 。

(x2,x1,x3)(0)≥3(1)≤2(2)≤4(3)≤3(4)≤6满足约束否Z值说明

(0,0,0)0×(0,0,1)7-3

4

3√7改(0)≥7

(0,1,0)-6×(0,1,1)1×(1,0,0)5×(1,0,1)12-2

7

×(1,1,0)-1×(1,1,1)

6

×

4、比较求出的目标函数值大小，对max 问题取最大，对min 问题取最小，从而确定最优解为（x 1,x 2,x 3）=（0，0，1），max Z = 7。

运筹学第四章多目标规划

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1） min z ＝p 1（+1d ＋+2d ）＋p 2-3d st. －x 1＋ x 2＋ d －1－ d ＋ 1＝1 －0.5x 1＋ x 2＋ d － 2－d ＋ 2＝2 3x 1＋3x 2＋ d －3－ d ＋3＝50 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1，2，3） （2） min z ＝p 1（2+1d ＋3+2d ）＋p 2-3d ＋p 3+4d st. x 1＋ x 2＋d －1－d ＋ 1 ＝10 x 1 ＋d －2－d ＋2 ＝4 5x 1＋3x 2＋d －3－d ＋3 ＝56 x 1＋ x 2＋d －4－d ＋4 ＝12 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p 1（d ＋1＋d ＋2）＋2p 2d －4＋p 2d －3＋p 3d －1 st. x 1 ＋d －1－d ＋1＝20 x 2＋d －2－d ＋2＝35 －5x 1＋3x 2＋d － 3－d ＋ 3＝220 x 1－x 2＋d －4－d ＋4＝60 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化； （3）若增加一个新的目标约束：－4x 1＋x 2＋d －5－d ＋5＝8，该目标要求尽量达 到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x 3，其系数列向量为（0，1，1，－1）T ，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P 1：满足法律规定要求； P 2：每天的纯收入最大。 试建立该问题的目标规划模型。

运筹学第四章

运筹学第四章习题答案 4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛- d -+d ｝ （2）max ｛-d ++ d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+ d ｝ （1）合理，令f （x ）+- d -+ d =b,当f （x ）取最小值时，- d -+ d 取最大值合理。 (2)不合理，+ d 取最大值时，f （x ）取最大值，- d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，- d 和+ d 都要尽可能的小。 （4）合理，令f （x ）+- d -+ d =b,当f （x ）取最大值时，- d -+ d 取最小值合理。 4.2用图解法和单纯形法解下列目标规划问题 （1）min ｛P 13 +d ，P 2- 2d ，P 3（- 1d ++ 1d ）｝ 24261121=-+++- d d x x 52221=-+++- d d x x 155331=-++-d d x 3,2,1,0,,,21=≥+-i d d x x i i （2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+4 35.1d d )} 401121=-+++-d d x x 1002221=-++--d d x x 30331=-++-d d x 15442=-++-d d x 4,3,2,1,0,,,21=≥+-i d d x x i i (1)图解法

0 A B C X 1 由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a (2)图解法 2 1 由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可 表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a

运筹学课件第四章目标规划

第四章目标规划 一、学习目的与要求 1、掌握目标规划的图解法模型； 2、掌握目标规划的单纯形的求解模型； 3、掌握目标规划的灵敏度分析。 二、课时6学时 第一节目标规划问题及其数学模型 一、问题的提出 应用线性规划可以处理许多线性系统的最优化问题，但线性规划，整数规划和非线性规划都只有一个目标函数，而在实际问题中，常常需要考虑多个目标：如设计一个新产品的工艺过程，不仅希望获利大，而且希望产量高，消耗低，质量好，投入少等。而这些目标之间通常是矛盾的。所以这类问题多目标问题比单目标问题要复杂得多，我们把这一类问题称为目标规划问题。 目标规划与线性规划相比，有以下优点： 1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题。 实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。 2.线性规划是在满足所有约束条件的可行解中求得最优解。而在实际问题 中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。 3.线性规划问题中的约束条件是不分主次、同等对待的，是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。 4.线性规划的最优解可以说是绝对意义下的最优，为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。 因此可以认为，目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。 二、目标规划的数学模型 例1 某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制定一个获利最大的生产计划，具体数据见表：

运筹学整数规划

实验报告 课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __ 1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。 2、若是单人单组实验，同组成员填无。

例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？ 解： 根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数， 每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数： i i x z 6 1 min = ∑ = 约束条件： ? ? ? ? ? ? ? ? ? ? ? = ≥） 且为整数（6 ... 1 ,0 x 30 >= x6 + x5 20 >= x5 + x4 50 >= x4 + x3 60 >= x3 + x2 70 >= x2 + x1 60 >= x6 + x1 i i model: sets: num/1,2,3,4,5,6/:b,x; endsets data: b=60,70,60,50,20,30; enddata [obj]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; 2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。

解： 目标函数： y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max 约束条件：???????y3 *300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model : sets : num/1,2,3/:x,y; endsets [obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3); 5*x(1)+x(2)+4*x(3)<=2000; 3*x(1)<=300*y(1); 0.5*x(2)<=300*y(2); 2*x(3)<=300*y(3); @for (num(i):x(i)>=0;@bin (y(i));); end

运筹学--第四章 多目标规划汇总

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1）min z ＝p1（＋）＋p2 st. －x1＋ x2＋ d－1－ d＋1＝1 －0.5x1＋ x2＋ d－2－d＋2＝2 3x1＋3x2＋ d－3－ d＋3＝50 x1，x2≥0；d－i，d＋i≥0（i =1，2，3） （2） min z ＝p1（2＋3）＋p2＋p3 st. x1＋ x2＋d－1－d＋1 ＝10 x1 ＋d－2－d＋2 ＝4 5x1＋3x2＋d－3－d＋3 ＝56 x1＋ x2＋d－4－d＋4 ＝12 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p1（d＋1＋d＋2）＋2p2d－4＋p2d－3＋p3d－1 st. x1 ＋d－1－d＋1＝20 x2＋d－2－d＋2＝35 －5x1＋3x2＋d－3－d＋3＝220 x1－x2＋d－4－d＋4＝60 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化；

（3）若增加一个新的目标约束：－4x1＋x2＋d－5－d＋5＝8，该目标要求尽量达到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x3，其系数列向量为（0，1，1，－1）T，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P1：满足法律规定要求； P2：每天的纯收入最大。 试建立该问题的目标规划模型。 4.4 某企业生产两种产品，产品Ⅰ售出后每件可获利10元，产品Ⅱ售出后每件可获利8元。生产每件产品Ⅰ需3小时的装配时间，每件产品Ⅱ需2小时装配时间。可用的装配时间共计为每周120小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低1元。加班时间限定每周不超过40小时，企业希望总获利最大。试凭自己的经验确定优先结构，并建立该问题的目标规划模型。 4.5 某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下： A B每周最大加工能力 I 4 6 150 II 3 2 70 利润（元/台）300 450 工厂经营目标的期望值及优先级如下： P1：每周总利润不得低于10000元；

运筹学第4章整数规划习题.doc

第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下： 2123max x x z += ????? ? ?≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x 4.2 2197max x x z += ??? ??≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。（下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得： 2 7 221227432=++ x x x ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得： ①②③④ ①②③

即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 由x 1行得： 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和： 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4.3 max z ＝4x 1＋3x 2＋2x 3

运筹学实验报告四整数规划

2018-2019学年第一学期 《运筹学》 实验报告（四） 班级：交通运输171 学号： 1000000000 姓名： ***** 日期： 2018.11.22

实验一： 用Lingo 软件求解下列整数规划问题（要求附程序和结果） 12 121212max 2506221 0,1,2i z x x x x x x x x x i =++≤?? -+≤?? +≤??≥=?且取整数 12312323123123 123max 232 45 2244 ,,01 z x x x x x x x x x x x x x x x x x =+-++≤??+≤?? +-≤??+-≤?=??或 解：例题（左）解题程序及运行结果如下： sets : bliang/1,2/:x,a; yshu/1,2,3/:b; xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddata max =@sum (bliang(i):a(i)*x(i)); @for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i))); Global optimal solution found. Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 3.000000 -2.000000 X( 2) 1.000000 -1.000000 A( 1) 2.000000 0.000000