第四章整数规划与分配问题

第四章 整数规划与分配问题

§4.1整数规划的特点及作用

用单纯形法求解线性规划的结果往往得到分数或小数解。但在很多实际问题中，全部或部分变量的取值必须是整数，如人或者机器设备不可分割。此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x ，令1x =表示在该地建厂，0x =表示不在该地建厂，逻辑变量也只允许取整数值的一类变量。在一个整数规划中要求全部变量取整数值的，称纯整数线性规划或纯整数规划；只要求一部分变量取整数值的，称为混合整数（线性）规划；在纯整数规划问题中，若所有变量只允许取0，1两个值，则称其为0-1规划。

有人认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整数寻找最优解，其实这种方法是不可行的，原因有以下两点：

一、用凑整的方法计算量很大，而况还不一定能找到最优解。 如某线性规划问题的最优解为()()1

2 4.6 5.5x x =，用凑整数的方法时需比较与

12,x x 的上述数值最接近的四种组合：(4,5),(5,5),(4,6),(5,6)如果问题中有10个变量，就

要比较1021024=个整数解组合，而且最优解还不一定在这些组合中。

二、放松约束也无法求出其最优解

例

12

121212

max 322314

.0.5 4.5,0,z x x x x s t x x x x =++≤??

+≤??≥?整数

如果不考虑整数约束，称为上述线性规划问题的松弛问题，松弛问题的最优解为：

123.25, 2.5x x ==

取整以后123,2x x ==是可行解，但1212123,3;4,2;4,3x x x x x x ======都不是可行解，而123,2x x ==对应的目标函数值123213z x x =+=却不是最优解，然而最优解是

12124,1,max 3214x x z x x ===+=。

直接对松弛问题进行求解都无法求得整数规划问题的最优解，这就需要对整数线性规划问题有特殊的求解方法。

此外，整数线性规划问题的数学模型的研究有着重要的意义，很多管理问题无法归纳为线性规划问题的数学模型，但却可以设置逻辑变量建立起整数规划问题的数学模型。下面举例说明逻辑变量在解决问题中的重要作用。

1.m 个约束条件中只有k 个起作用 设m 个约束条件可以表示为

1

,(1,2,,)n

ij j

i j a x

b i m =≤=∑L

定义 1 1,2,,)0 i i y i m i ?==??L 假设第个约束条件不起作用，（假设第个约束条件起作用

又M 为任意大的正数，则

11212

(1,2,,),,,01

n

ij j i i j m m a x b My i m y y y m k

y y y =?≤+=???

+++=-??=???

∑L L L 或 因为若0i y =，则1n

ij j i j a x b =≤∑条件起作用

若1i y =，则1

n ij j i j a x b M =≤+∑，1

n

ij j i j a x b =≤∑条件不起作用

2.约束条件的右端项可能是r 个值12(,,,)r b b b L 中的某一个，即

121

n

ij j

r j a x

b b b =≤∑L 或或或

定义 1 0 i

i b y ?=??假定约束条件右端项为否则

由此，上述约束条件可以表示成：

1122112121

,,,01

n

ij j r r j r r a x b y b y b y y y y y y y =?≤+++???

+++=????=?∑L L L 或 3.两组条件中满足其中一组

若14x ≤，则21x ≥；否则（即14x >时），23x ≤

定义 1 1,2)0 i i y i i ?==??第组条件不起作用

，（第组条件起作用

又M 为任意大的正数，则问题可表达为：

112

112

22121241431,0,1

x My x My

x My x My y y y y ≤+??≥-??>-??

≤+??+=?=?? 4.用以表示含固定费用的函数

例如用j x 代表产品j 的生产数量，其生产费用函数通常可表示为：

(0)

()0 (0)j j j j j j j K c x x C x x +>??=?=??

式中j K 是同产量无关的生产准备费用。问题的目标是使所有产品的总生产费用为最小，即：

1min ()n

j j j z C x ==∑

令 1 0

0 0j j j x y x >??=?=??

，那么j j x My ≤

使问题化为：

1

min 0. (01)1,2,,)

n

j j j j

j j j j z c x K y x My s t M y j n ==+≤≤???==??∑L 为充分大的正数）或

一般整数规划问题建模：

例1 某饭店24小时中需要服务员数量如下：如果每个服务员连续工作8小时，试问在2点、6点、10点、14点、18点、22点钟开始上班的服务员为多少时，一天所需服务员人数最少？

设在2点、6点、10点、14点、18点、22点钟开始上班的服务员分别为654321,,,,,x x x x x x ,则可建立整数规划数学模型

??

?????????≥=+=+=+=+=+=++++++=整数

0,

,

,

,412

710

8

4.min 65

4321

6554

43

3

221

6

1

654321x x x x x x x x x x x x x x x

x x x t s x x x x x x Z 利用LINGO 求解整数线性规划问题，得

Min=x1+x2+x3+x4+x5+x6;

x1+x6>=4;x1+x2>=8;x2+x3>=10; x3+x4>=7 ;x4+x5>=12;x5+x6>=4;

@gin(x1); @gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6); Global optimal solution found.

Objective value: 26.00000 Extended solver steps: 0 Total solver iterations: 6

Variable Value Reduced Cost X1 4.000000 1.000000 X2 4.000000 1.000000 X3 6.000000 1.000000 X4 1.000000 1.000000 X5 11.00000 1.000000 X6 0.000000 1.000000 Row Slack or Surplus Dual Price 1 26.00000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000

7 7.000000 0.000000

2.在高校篮球联赛中，某学院男子篮球队要从8名队员中选择平均身高最高的出场阵容，队员的号码、身高及擅长的位置如表所示：

同时要求出场阵容满足以下条件：

（1）中锋只能有一个上场； （2）至少有一名后卫；

（3）如果1号队员和4号队员都上场，则6号队员不能上场；

（4）2号队员和6号队员必须保留一个不出场。写出该问题的数学模型。

解：设)8,7,6,5,4,3,2,1(01=???=j j j x j 号队员不出场第号队员出场

第

则可建立整数规划模型：

??????????

?=≤+≤++≥++=+=++++++++++++++=1

0,,,,,,,12115.78.180.183.185.186.188.190.192.1max 8765432162641

876218765432187654321或x x x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x x x x Z

利用LINGO 进行求解0—1规划问题，得

Max=1.92*x1+1.9*x2+1.88*x3+1.86*x4+1.85*x5+1.83*x6+1.8*x7+1.78*x8 ; x1+x2+x3+x4+x5+x6+x7+x8=5;

x1+x2=1;x6+x7+x8>=1;x1+x4+x6<=2;x2+x6<=1;

@bin (x1); @bin (x2); @bin (x3); @bin (x4); @bin (x5); @bin (x6); @bin (x7); @bin (x8); Global optimal solution found.

Objective value: 9.310000 Extended solver steps: 0 Total solver iterations: 0

Variable Value Reduced Cost X1 1.000000 -1.920000 X2 0.000000 -1.900000 X3 1.000000 -1.880000 X4 1.000000 -1.860000 X5 1.000000 -1.850000 X6 0.000000 -1.830000 X7 1.000000 -1.800000 X8 0.000000 -1.780000

3.某工厂生产1A 、2A 两种产品，产品分别由1B 、2B 两种部件组装而成，每件产品所用部件数和有关部件的产量限额以及产品利润由下表所示。问怎样安排1A 、2A 的生

解：设生产1A 、2分别为1、2件，则

???

??≥≤+≤++=整数,0,10325

46.2015max 2

1212121x x x x x x t s x x Z 很容易用LINGO10.0求出它的最优解。

Max=15*x1+20*x2; 6*x1+4*x2<=20; x1+3*x2<=10;

@gin(x1);@gin(x2);

下料问题也是典型的整数规划问题 下面讲指派问题

§4.2 分配问题（指派问题）与匈牙利法

2-1问题的提出与数学模型

分配问题也称指派问题（Assignment Problem ）,是一种特殊的整数规划问题，假定有m 项任务分配给m 个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成。

例：有m 个人，去完成m 项任务，不同的人完成不同的任务效率如下表：

111212122212

m m m m mm a a a a a a a a a ??

? ?

?

???

L L L L L L L

称为分配问题的效率矩阵。 令 1 ,1,2,,)0 ij i j x i j m i j ?==??L 分配第个人去完成第项任务

（不分配第个人去完成第项任务

则分配问题的数学模型一般可以写为：

11

11

min 1 (1,2,,). 1 (1,2,,)0 1 (,1,2,,)m

m

ij ij

i j m

ij j m

ij i ij z a x x i m s t x j m x i j m =====?==???==???==??

∑∑∑∑L L L 或 2-2 匈牙利法

理论上，这也是运输问题，但是它比运输问题更特殊，可以用更特殊的方法加以解决。可以用求解运输问题的表上作业法求解分配问题，但通常更有效的是用匈牙利方法求解。

解分配问题的匈牙利方法是从这样一个明显的事实出发的：如果效率矩阵的所有元素0ij a ≥，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些元素位置的1ij x =其余的0ij x =，则11m

m

ij ij i j z a x ===∑∑就是问题的最优解。如效率矩阵为：

0149392002323038012140?? ? ? ? ??? ， 1000001001000001??

?

?

?

?

??

就是指派问题的最优解。

但问题是如何产生并寻找这些位于不同行不同列的零元素。匈牙利数学家克尼格（Konig ）证明了下面两个基本定理，为解决以上问题奠定了基础。因此，基于这两个定理基础上所建立的求解分配问题的计算方法被称为匈牙利法。

定理1 如果从分配问题的效率矩阵()ij a 中的某一行分别减去（或加上）一个常数i

u （被称为该行的位势），从某一列分别减去（或加上）一个常数j v （称为该列的位势），得到一个新的效率矩阵()ij b ，若其中ij ij i j b a u v =--，则以()ij b 为效率矩阵分配问题的最优解等价于以()ij a 为效率矩阵分配问题的最优解。 证明：

11

11

()m

m

m

m

ij ij ij i j ij i j i j z b x a u v x ===='==--∑∑∑∑

11111

m m m m m

ij ij i ij j ij i i j j i a x u x v x ======--∑∑∑∑∑

1

1

1

()m

m

m

ij ij i j i i j a x u v ====--∑∑∑后两项是常数

所以 11

11

min min m m m m

ij ij ij ij i j i j b x a x ====?∑∑∑∑

例：现有四人每人都能完成四项工作中的一项，但由于各自对不同工作的熟练程度或技术专长的不同，完成每项工作花费的时间也不同。如下表

匈牙利方法的步骤：

1.变换效率矩阵，使变换后的效率矩阵每行、每列至少有一个“0”元素

011723141053011306086104121046044()()05649141513905220142781197010042ij ij a b ??

-???? ? ? ? ?- ? ? ?=→→= ? ?

- ? ? ? ?-???? ?--??

2.试求最优解（通过标注零的方法）所以可以求得

14223143

00010

100(),min 549112910000

01

0,,,ij x z A B A B A B A B ?? ?

?

====== ? ???

---- 例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间如下表，应如何分配，使这四个人分别完成这四项任务的总时间为最短。

1.个零元素（变换效率矩阵）

0875********

25110104154148411054235013141611112300011954151394011455??

-????

? ? ? ?- ?

?

?→→ ? ?

- ? ? ? ?-????

?-??

2.试求最优解

***082511054230001145?? ? ? ?

? ???

3.作覆盖所有零元素的最少直线集合 （1）对没有*0的行打√

（2）对打了√的行上0元素所在的列打√ （3）对打了√的列上*0所在的行打√ （4）对打了√的行上0元素所在的列打√ 直至打不出新的行和新的列

对没有打√的行划横线，对打了√的列划竖线，这样就得到能够覆盖所有零元素的最少直线组合。

定理2 若矩阵A 可分为“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。恰好等于我们标出*0的个数。

证明:已知矩阵中有若干个0元素，设覆盖全部0元素最少需要m 条直线，又设位于不同行不同列的0有M 个，因覆盖每个0至少用一条直线，故有

m M ≥

下面要证明M m ≥，假定覆盖所有0元素的m 条直线有r 行（用12,,,r i i i L 表示）c 列（用12,,,c j j j L 表示），m r c =+；显然在每一行上至少存在一个不在12,,,c j j j L 列上的0元素；设某一行上这些不在12,,,c j j j L 列上的0元素下标的集合为

12{0,,,,}i il c S l a l j j j ==≠L

对12,,,r i i i L 行分别有集合12,,,r i i i S S S L ，从这些集合中任取k 个（k r ≤），其集合中的不同元素个数必不少于k ，否则这k 行的直线可用少于k 条列线代替，与m 是覆盖0元素的最少直线的假定矛盾。

由此可知，在r 条行线上存在不少于r 个位于不同的列，且这些0不位于12,,,c

j j j L 列上。同理可以证明在c 条列线上存在不少于c 个位于不同行的0，且这些0不位于

12,,,r i i i L 行上。

若上述两部分0的个数总和为S ，则S m ≥，又显然S M ≤，故有M m ≥ 从而有M m =，定理得证。

4.继续变换效率矩阵，试求最优解，回到第二步。

从未被直线覆盖的所有元素中找出一个最小元素k ，然后将效率矩阵未划横线的行均减去这个最小元素，划竖线的列均加上这个最小元素。

再试求最优解，继续。

**

**06031305443000923?? ? ? ? ? ???

最优解为00100100()00011000ij x ??

? ?= ?

??? min 9411428,min 24114522228z z =+++==++++++-=或者

*********127979502027020289666230004300071712141201057508353151466109800411800441071060636204140????

?? ? ? ? ? ? ? ? ? ?→→ ? ? ? ? ?

? ? ? ???????

最优解 010*******()100000001000001min 7676632min 7676422232ij x z z ?? ? ?

?

= ?

? ???

=++++==++++++-=或 两点说明

1.分配问题中如果人数和工作任务数不相等时的处理方法。举例来说，如果人员数

大于任务数，可以增加虚的任务，使总的任务数与总的人员数相等，不过每个人完成虚任务的时间为0，效益当然也为0；当人员数小于任务数，可增加虚的人员，使人员总数等于任务总数。虚人员完成各任务的效率与效益均为0，这时可能有的任务无法落实。如：

**

*

*

**362600050400714400402200365800053600643700331500524300212100576200264000??

?? ? ?

? ? ?

?→ ? ? ? ? ? ? ? ? ? ????? min 21328z =+++=

2.如果把效率矩阵改为效益矩阵，把求指派问题的最小值化为求指派问题的最大值

即可。

如11max m

m

ij ij i j z a x ===∑∑

等价于'11

min ()m m

ij ij i j z z a x ===-=-∑∑，由于()ij a -为负，不容易比较，现在将每一个数

都加上M ，等价于11

min (),max{}m

m

ij ij ij i j w M a x M a ===-=∑∑化为一般的最小化指派问题。

例：一个公司要分派5个推销员去5个地区推销某种产品，5个推销员在各个地区推销这种产品的预期利润如下表所示。若每个推销员只能去一个地区，应如何分派这5个推销员才能使公司的利润最大？

*******max{}205108108053539

811111110333(20)10

0538100538231111701995137107860301050*52050301

003210010 10

0237100215016940167260000ij ij a a =????

? ?

? ? ? ?

-=→ ? ?

? ?

? ?????

?? ? ? ?→→ ? ? ??

?*82200??

? ? ?

? ?

???

0010000001(),max 12920181372010001000000010ij x z ?? ?

?

?==+++== ? ? ???

例：某车队有5辆汽车，将驶往3个目的地运货。一地的货物只需一辆车送，其运

费（元）如下表：

（1）试求最优指派的调运方案

（2）若表中数字表示所得利润，则应如何指派？

（3）若车2载不下A 地所需货物，车5爬不上通往B 地必经之路上的坡，对（1）（2）的最优解有什么影响？

相应的作业P125，4.3（a ）(b)

P125 4.5提示以后让学生自己完成要真正弄懂 (a)将最后一列先减去一个数如30，使E 列占优势，这就保证了任务E 必须能完成，

然后再增加一个虚的人

252931427

393826203

342728402

2442362315

??

?

?

?

?

??

，再增加一行0也无妨。

（b）取每列的最小值，放至最后一行，作为第5个人，然后在任务分派时将第5个人的任务再还原。

（c

这样即可达到目的。

§4.3 分枝定界法

在线性规划问题中，变量x 是在一个连续的范围内取值，因此可行解个数无限多。但在整数规划问题中变量只能取离散的整数值，可行解的总数是有限的。从有限多的可行解中寻找最优解的最直观、最简单的方法是枚举法，但方法不可行。分枝定界法(branch and bound method)就是为求解同整数规划具有类似性质的一大类问题而设计的一种较好的方法。

第一步：寻找替代问题并求解。

方法是放宽约束条件，去掉整数约束。如果非整数线性规划问题的最优解就是整数，则已求得整数问题的最优解；否则，这个最优解是原整数线性规划问题最优解的一个上界（求最大值）或者下界（求最小值）。

12121212

max 322314.0.5 4.5

,0,z x x x x s t x x x x =++≤??+≤??≥?整数 放松约束条件，求解如下问题 12

121212max 322314

.29,0

z x x x x s t x x x x =++≤??

+≤??≥

（LP1） （LP1）最优解1213

,,max 424

x x z ===

121212212max 32231429.2,0z x x x x x x s t x x x =++≤??+≤??≤??≥? （LP12） 12

1212

2max 322314

29.3,0

z x x x x x x s t x x x =++≤??+≤??≥??≥ （LP13）

（LP12）最优解127,2,max 22

x x z ===

1212122112max 32231429.23,0z x x x x x x s t x x x x =++≤??+≤??≤??≤??≥? （LP121） 12

121221

max 32231429.24,0

z x x x x x x s t x x x x =++≤??+≤??≤??≥??≥ （LP122） （LP121）最优解为1

x =

（LP122）最优解为14,1,max 14,14x x z z ====

（LP13）最优解125,3,max 13.51422

x x z ====<，尽管不是整数解，但它的目标函数的最大

值小于14，不必分枝，因此该整数线性规划问题的最优解为：

124,1,max 14x x z ===

故，最优解求得：124,1,max 14x x z ===

这一个比较简单的整数线性规划问题，分解为求解四个非整数线性规划问题，有些求解更为复杂。希望同学们要注意到这一点，理解这种原理，求解这样方法。

作业：P127，4.8（b ）

§4.4 割平面法

这是求解整数规划问题最早提出的一种方法，1958年由高莫瑞(Gomory )提出。它的基本思想是在整数规划问题的松弛问题中依次引进线性约束事件（Gomory 约束或割平面），使问题的可行域逐步缩小。但每次切割只割去问题的部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。

第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数性约束，可得到该问题的松弛问题并求解得最后一个单纯形表

12121212

max 322314

.29,0z x x x x s t x x x x =++≤??

+≤??≥?

（增加割平面341222

x x +≥）

若第一步得到整数解，求解到此结束，否则转第二步。

第二步；找出非整数解变量中非整数部分最大的一个基变量，它们对应的方程为

11220i i in n i b x b x b x b +++=L

设[],0,1,2,,ij ij ij f b b j n =-=L ，那么，有

1111222200[][][][]i i i i in n in n i i b x f x b x f x b x f x b f ++++++=+L

从而有 11220i i in n i f x f x f x f +++≥L 称为割平面 引入松弛变量n i x +，11220i i in n n i i f x f x f x x f +----+=-L

加入到单纯形表中去，利用对偶单纯形方法进行换基迭代，得到

继续使用对偶单纯形方法进行换基迭代，得到：

124,1,max 14x x z ===

这就是割平面法。可见，割平面方法比分枝定界方法来得快。

§5 应用举例

例3 东方大学计算机实验室聘用4名大学生（代号1，2，3，4）和2名研究生（代号5，6）值班答疑，已知每人从周一至周五每天最多可安排的值班时间及每人每小时值班的报酬如下表：

大学生每周值班不少于8小时，研究生每周不少于7小时，每名学生每周值班不超过3次，每次值班不少于2小时，每天安排值班的学生不超过3人，且其中必须有一名研究生。试为该实验室安排一张人员安排的值班表，使总的支付报酬为最少！ 解：设ij x 为学生i 在时间星期j 的值班时间，1 0 ij i j y ?=?

?，

学生在周值班，

否则

112131415161122232425262132333435363142434445464min 10109.99.810.811.3 10109.99.810.811.3 10109.99.810.811.3 10109.99.810.811.3 z x x x x x x x x x x x x x x x x x x x x x x x x =+++++++++++++++++++++++152535455565

1234512345123 10109.99.810.811.320,(1,2,3,4,5,6;1,2,3,4,5)

0,(1,2,3,4,5,6;1,2,3,4,5)8,(1,2,3,4)7,(5,6).ij ij ij ij ij i i i i i i i i i i j j j x x x x x x x y i j x a y i j x x x x x i x x x x x i s t x x x ++++++-≥==-≤==++++≥=++++≥=++456123451234565614,(1,2,3,4,5)3,(1,2,3,4,5,6)

3,(1,2,3,4,5)1,(1,2,3,4,5)0,01(1,2,3,4,5,6;1,2,3,4,5)j j j i i i i i j j j j j j j j ij ij x x x j y y y y y i y y y y y y j y y j x y i j ??

??

????

+++==??

++++≤=??+++++≤=?

+≥=??

≥===??或，

min =10*x11+9.9*x31+9.8*x41+10.8*x51+10*x22+9.9*x32+9.8*x42+11.3*x62+10*x13+9.9*x33+9.8*x43+10.8*x53+10*x24+10.8*x54+11.3*x64+10*x15+9.9*x35+9.8*x45+11.3*x 65;

x11-2*y11>0;x13-2*y13>0;x15-2*y15>0;x22-2*y22>0;x24-2*y24>0; x31-2*y31>0;x32-2*y32>0;x33-2*y33>0;x35-2*y35>0; x41-2*y41>0;x42-2*y42>0;x43-2*y43>0;x45-2*y45>0; x51-2*y51>0;x53-2*y53>0;x54-2*y54>0; x62-2*y62>0;x64-2*y64>0;x65-2*y65>0; x11-6*y11<0;x13-6*y13<0;x15-7*y15<0; x22-6*y22<0;x24-6*y24<0;

x31-4*y31<0;x32-8*y32<0;x33-3*y33<0;x35-5*y35<0;

第四章整数规划与分配问题

第四章 整数规划与分配问题 §4.1整数规划的特点及作用 用单纯形法求解线性规划的结果往往得到分数或小数解。但在很多实际问题中，全部或部分变量的取值必须是整数，如人或者机器设备不可分割。此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x ，令1x =表示在该地建厂，0x =表示不在该地建厂，逻辑变量也只允许取整数值的一类变量。在一个整数规划中要求全部变量取整数值的，称纯整数线性规划或纯整数规划；只要求一部分变量取整数值的，称为混合整数（线性）规划；在纯整数规划问题中，若所有变量只允许取0，1两个值，则称其为0-1规划。 有人认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时可用四舍五入或凑整数寻找最优解，其实这种方法是不可行的，原因有以下两点： 一、用凑整的方法计算量很大，而况还不一定能找到最优解。 如某线性规划问题的最优解为()()1 2 4.6 5.5x x =，用凑整数的方法时需比较与 12,x x 的上述数值最接近的四种组合：(4,5),(5,5),(4,6),(5,6)如果问题中有10个变量，就 要比较1021024=个整数解组合，而且最优解还不一定在这些组合中。 二、放松约束也无法求出其最优解 例 12 121212 max 322314 .0.5 4.5,0,z x x x x s t x x x x =++≤?? +≤??≥?整数 如果不考虑整数约束，称为上述线性规划问题的松弛问题，松弛问题的最优解为：

123.25, 2.5x x == 取整以后123,2x x ==是可行解，但1212123,3;4,2;4,3x x x x x x ======都不是可行解，而123,2x x ==对应的目标函数值123213z x x =+=却不是最优解，然而最优解是 12124,1,max 3214x x z x x ===+=。 直接对松弛问题进行求解都无法求得整数规划问题的最优解，这就需要对整数线性规划问题有特殊的求解方法。 此外，整数线性规划问题的数学模型的研究有着重要的意义，很多管理问题无法归纳为线性规划问题的数学模型，但却可以设置逻辑变量建立起整数规划问题的数学模型。下面举例说明逻辑变量在解决问题中的重要作用。 1.m 个约束条件中只有k 个起作用 设m 个约束条件可以表示为 1 ,(1,2,,)n ij j i j a x b i m =≤=∑L 定义 1 1,2,,)0 i i y i m i ?==??L 假设第个约束条件不起作用，（假设第个约束条件起作用 又M 为任意大的正数，则 11212 (1,2,,),,,01 n ij j i i j m m a x b My i m y y y m k y y y =?≤+=??? +++=-??=??? ∑L L L 或 因为若0i y =，则1n ij j i j a x b =≤∑条件起作用 若1i y =，则1 n ij j i j a x b M =≤+∑，1 n ij j i j a x b =≤∑条件不起作用 2.约束条件的右端项可能是r 个值12(,,,)r b b b L 中的某一个，即 121 n ij j r j a x b b b =≤∑L 或或或 定义 1 0 i i b y ?=??假定约束条件右端项为否则 由此，上述约束条件可以表示成：

第四章整数规划

第四章 整数规划 1、用分枝界定法虬下列整数规划 （1） 12max 2z x x =+ （2） 12max z x x =+ 12x x +≤5 12x x -+≤0 1262x x +≤21 1x ，2x ≥0，整数 1x ，2x ≥0，整数 （3） 123max 45z x x x =++ （4） 12max 4090z x x =+ 1232x x +≤10 1297x x +≤56 124x x +≤11 12720x x +≤70 12333x x x ++≤1 1x ，2x ≥0，整数 1x ，2x ，3x ≥0，整数 2、用割平面法求下列整数规划 （1） 12max 32z x x =+ （2） 21max 79z x x =+ 1223x x +≤14 123x x -+≤6 s t ? 122x x +≤9 s t ? 127x x +≤35 1x ，2x ≥0，整数 1x ，2x ≥0，整数 （3） 2max 3z x = （4） 1232x x +≤7 s t ? 12x x -≥2- 1x ，2x ≥0，2x 整数 1x ，2x ，3x ，4x ≥0 1x ，2x ，3x 整数 3、解下列01-规划 （1） 12345max 2554z x x x x x =-+-+ 1234532754x x x x x -+-+≤6 12345242x x x x x -+-+≤0 0j x =或1，j =1，2，…，5 12 123 x x -+≤12951 1414x x + ≤ s t ?s t ?s t ?s t ?12341711928824x x x x ++-≤12313 15.5 44x x x -++≤123419 max 108118 z x x x x =++-s t ?s t ?

第五章 整数规划练习题答案

第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A & B C D E 甲 9 4 6 8 5 \ 乙 8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊 10 ； 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 64 10 154062415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ?? ? 31234311546233 5 3 5? ?? ?? ? ?→ ?? ? ?? ? m=5=n ，得最优解。解矩阵*0001000100X 0000101 00010000?? ? ? ?= ? ? ??? 。

整数规划与分配问题

99 第4章 整数规划与分配问题 §4．1 整数规划的数学模型及解的特点 1--1 整数规划数学模型的一般形式 要求一部分或全部决策变量必须取整数值的线性规划（Linear Programming ，简记LP ）问题称为整数规划（Integer Programming,简记IP ）。整数线性规划数学模型的一般形式为 ()()1 11max min ,,1,,..0,1,, ,,n j j j n ij j i j j n z c x a x b i m s t x j n x x ===?≤=≥=???≥=????? ∑∑ 或中部分或全部取整数 根据对所有变量的要求不同，整数线性规划又分为下列几种类型： （1） 纯整数线性规划（Pure Integer Linear Programming ）：指全部决策变量都必须取 整数值的整数线性规划。有时也称为全整数规划。 （2） 混合整数规划（Mixed Integer Linear Programming ）：指决策变量中有一部分必须 取整数值，另一部分可以不取整数值的整数线性规划。 （3） 0-1型整数规划（Zero-one Integer Linear Programming ）：指决策变量只能取值0 或1的整数线性规划。 整数规划问题的L P 松弛问题（Slack Problem ）这个概念在求解IP 时具有重要作用。 定义1 不考虑变量的所有整数或0-1约束条件而得到的L P 称为IP 的L P 松弛问题。 换言之，不考虑变量为整数的约束条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规划，则称该整数规划为整数线性规划（Integer Linear Programming ）。 1--2 整数规划的例子 在现实生活中，当决策变量代表产品的件数、个数、台数、箱数、艘数、辆数等时，往

运筹学实验一 线性规划求解、运输问题、整数规划求解 2

西华大学能源与环境工程学院学生上机实验报告 西华大学上机实验报告 一、实验目的 掌握线性规划求解的基本方法，熟悉灵敏度分析的步骤和内容；掌握运输问题的模型，概念，求解方法；掌握整数规划的算法。在熟悉lingo软件基本功能基础上，能熟练操作，正确完成模型求解过程及分析过程。 二、实验内容或设计思想 1．lingo软件或运筹学实验软件的安装及菜单熟悉了解. 2．lingo软件或运筹学实验软件应用内容之：任选几种不同类型的LP输入计算程序，运行求解；完成产销平衡的运输问题求解；求解任一整数规划。 三、实验环境与工具 计算机、lingo软件 四、实验过程或实验数据 1用lingo求解线性规划 某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示： 用DESKS、TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。 max=60*desks+30*tables+20*chairs; 8*desks+6*tables+chairs<=48; 4*desks+2*tables+1.5*chairs<=20; 2*desks+1.5*tables+.5*chairs<=8; tables<=5; 求解这个模型，并激活灵敏性分析。这时，查看报告窗口（Reports Window）,可以看到如下结果。 Global optimal solution found at iteration: 3

Objective value: 280.0000 Variable Value Reduced Cost DESKS 2. 0. TABLES 0. 5. CHAIRS 8. 0. Row Slack or Surplus Dual Price 1 280.0000 1. 2 24.00000 0. 3 0. 10.00000 4 0. 10.00000 5 5. 0. 2 用运筹学软件求解线性规划 （例子和过程参照教材） 使用LINGO软件计算运输问题和整数规划问题 model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min=@sum(links: cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束; @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5

运筹学第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

运筹学实验一线性规划求解、运输问题、整数规划求解

西华大学上机实验报告 一、实验目的 掌握线性规划求解的基本方法，熟悉灵敏度分析的步骤和内容；掌握运输问题的模型，概念，求解方法；掌握整数规划的算法。在熟悉lingo软件基本功能基础上，能熟练操作，正确完成模型求解过程及分析过程。 二、实验内容或设计思想 1．lingo软件和运筹学实验软件的安装及菜单熟悉了解. 2．lingo软件和运筹学实验软件应用内容之：任选几种不同类型的LP输入计算程序，运行求解；完成产销平衡的运输问题求解；求解任一整数规划。 三、实验环境与工具 计算机，lingo软件，运筹学软件 四、实验过程或实验数据 1、用lingo求解线性规划 用DESKS、TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。 max=50*desks+30*tables+20*chairs; 7*desks+6*tables+chairs<=46; 4*desks+2*tables+1.5*chairs<=20; 2*desks+1.5*tables+.5*chairs<=8; tables<=5; Global optimal solution found. Objective value: 272.0000 Total solver iterations: 2 Variable Value Reduced Cost DESKS 0.000000 6.000000 TABLES 1.600000 0.000000

Row Slack or Surplus Dual Price 1 272.0000 1.000000 2 25.20000 0.000000 3 0.000000 12.00000 4 0.000000 4.000000 5 3.400000 0.000000 2、用LINGO软件计算运输问题 model: sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets min=@sum(links: cost*volume); @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end Global optimal solution found. Objective value: 638.0000 Total solver iterations: 16 Variable Value Reduced Cost

14级实验3--运输问题和整数规划

实验三：运输问题和整数规划 说明：今天实验作业题目为二道，运输问题与整数规划各任选一道。 一、运输问题 1、安东设备厂均衡运输问题 安东设备厂下设三个位于不同地点的分厂1、2、3，该三个分厂生产同一种设备，设每月的生产能力分别为25台、35台和45台。该设备厂有四个固定用户，该四个用户下月的设备需求量分别为20台、15台、23台和32台。已知各分厂的生产成本相同，从各分厂至各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问：该厂如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。 两处煤矿负责供应。已知煤炭每年供应量分别为A-400万吨，B-450万吨。有煤矿至各城市的单位运价（万元/万吨）如下表，由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总运费为最低的调运方案。 3 们分别被送到甲、乙、丙三个百货商店销售。已知每月各百货商店各类玩具总和的预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同，如下表。又知道丙百货商店要求至少供应C玩具1000件，而拒绝进A玩具。求满足上述条件下使总盈利额为最 4、教材P114[例3]

二、整数规划（四选一）： 1、职工排班问题 有一个游乐场，职工有7种轮休方式，每人每周连续休息2天。已知每天所需最少的工作人员如下表，职工的日薪为40元，问如何排班，即如何安排每种轮休方式的职工人数，才 ）一周按7天算。 i 2、现要在五个工厂中确定四个人来分别完成四项工作中的一项，由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项所需工时如下表所示。找出一个工作分配方案，使总工时最少。 33名为正式队员，使其平均身高尽可能高，这6 （1）至少补充一名后卫队员；（2）大李和小田之间只能入选一名；（3）最多补充一名中锋；（4）如果大李或小赵入选，小周就不能入选。 4、一个公司考虑到北京、上海、广州、和武汉四个城市设立库房，这些库房负责向华北、华中、华南三个地区供货，每个库房每月可以处理货物1000件。在北京设库房每月成本为4.5万元，上海为5万元，广州为7万元，武汉为4万元。每个地区的月平均需求量为：华北每 （1）如果在上海设库房，则必须也在武汉设库房； （2）最多设两个库房； （3）武汉和广州不能同时设库房。 请写一个满足上述要求的整数线性规划，并求出最优解。

第四章 整数规划

第四章 整数线性规划 （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 解：