运筹学 第4章 整数规划

第四章整数规划

整数规划（Integer Programming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题，在项目投资、人员分配等方面有着广泛的应用。

整数规划是近二、三十年发展起来的数学规划的一个重要分支，根据整数规划中变量为整数条件的不同，整数规划可以分为三大类：所有变量都要求为整数的称为纯整数规划（Pure Integer Programming）或称全整数规划（All integer Programming）；仅有一部分变量要求为整数的称为混合整数规划（Mixed Integer Programming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为0－1规划。

本章主要讨论整数规划的分枝定界法、割平面法、0－1规划及指派问题。

第一节整数规划问题及其数学模型

一、问题的提出

在线性规划模型中，得到的最优解往往是分数或小数，但在有些实际问题中要求有的解必须是整数，如机器设备的台数、人员的数量等，这就在原来线性规划模型的基础上产生了一个新的约束，即要求变量中某些或全部为整数，这样的线性规划称为整数规划（Integer Programming）简称IP，是规划论中的一个分枝。

整数规划是一类特殊的线性规划，为了满足整数解的条件，初看起来，只要对相应线性规划的非整数解四舍五入取整就可以了。当然在变量取值很大时，用上述方法得到的解与最优解差别不大，当变量取值较小时，得到的解与实际最优解差别较大，当变量较多时，如n＝10个，则整数组合有210＝1024个，而且整数解不一定在这些组合当中。先来看下面的例子。

例4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？

表4－1

12

量都要求为整数，建立模型如下：

2123max x x z +=

⎪⎪⎩⎪⎪

⎨

⎧≥≤+≤+为整数

21212121,0

,5.45.014

32x x x x x x x x 要求该模型的解，首先不考虑整数约束条件④，用单纯形法对相应线性规划求解，其最优解为：

x 1＝3.25 x 2＝2.5 max z ＝14.75

由于x 1＝3.25，x 2＝2.5都不是整数，不符合整数约束条件。用四舍五入凑整的办法能否得到最优解呢？

取x 1＝4，x 2＝2代入约束条件，破坏约束②；取x 1＝3，x 2＝2代入约束条件，满足要求，此时z ＝13，但这不是最优解，因为x 1＝4，x 2＝1时，z ＝14。

由此可知，用这种四舍五入或凑整的方法找不到最优解。再用图解方法来看寻找整数解的过程。

图4－1中ABCD 为相应线性规划的可行域，可行域中画（＋）号的点为可行的整数解，凑整得到的（4，2）不在可行域范围内，（3，2）点尽管在可行域内，但没有使目标达到极大化。为了使目标函数达到极大值，使目标函数等值线向原点方向移动，直到遇到（4，1）点为止，使目标函数达到最大，即z ＝14。

二、整数规划数学模型的一般形式

由上述例子可得出整数规划数学模型的一般形式：

CX Z =max b AX =

0≥X 且为整数或部分为整数

若称该整数规划问题为原问题，则线性规划问题：

CX Z =max b AX = 0≥X

为原问题对应的松驰问题。

显然，原问题与松弛问题有如下关系： （1）松弛问题可行域包含原问题可行域；

（2）若两者都有最优解，则松弛问题最优解大于原问题最优解； （3）若松弛问题最优解为整数解，则该最优解就是原问题最优解。

①②③④ 图4－1

第二节 整数规划的解法

整数规划常用的解法有分枝定界法和割平面法，它们适用于解纯整数规划问题和混合整数规划问题。 一、分枝定界法

在线性规划中，变量x j 是在一个连续的范围内取值，因此可行解的个数为无限多。在整数规划中变量只能取离散的整数值，可行解的数量是有限的。从有限多的可行解中寻找最优解最笨的也是最简单的想法就是枚举法：把问题的解全部列举出来，进行比较，从而找到最优解。但对于一般整数规划问题来说，可行解的总数随变量的增长成指数倍增长，使枚举法失去意义。分枝定界法（Brach and Bound Method ）的提出解决了整数规划的求解问题。

分枝定界法是在二十世纪六十年代初由Land Doig 和Dakin 等人提出的，适用于解纯整数或混合整数规划问题，其求解步骤如下：

第一步：令整数规划模型为A ，首先不考虑整数约束条件，求相应线性规划模型B 的最优解。若B 没有可行解，则A 也没有可行解，计算结束；若B 有最优解且符合A 中整数约束条件，B 的最优解即为A 的最优解，计算结束；若B 有最优解，但不符合A 的整数约束条件，转第二步进行计算。

第二步：用观察法找A 中的一个整数可行解，一般取x j ＝0（j ＝1，2，…，n ）试探，求得目标函数值作为下界z ，不考虑整数约束条件得到的B 模型的最优目标函数值作为上界z ，使整数规划A 的最优目标函数值z *符合以下条件：

z z z ≤≤*

第三步：分枝。在B 的最优解中任选一个不符合整数条件的变量x j ，令x j ＝b j ，以[b j ]表示小于b j 的最大整数，构造两个约束条件：

][j j b x ≤ ① 1][+≥j j b x ② 分别加入问题B ，得到两个后继问题B 1和B 2，不考虑整数约束条件求解这两个后继问题。

定界。以每个后继问题为一分枝标明求解的结果，并与其他问题的解进行比较，找出分枝中最优目标函数值最大者作为新的上界z ，从已符合整数条件的各分枝中，找出目标函数值最大者作为新的下界，若无整数解，则取z ＝0。

第四步：比较与剪枝。各分枝的最优目标函数中若有小于z 者或无可行解者，则剪掉这枝（用打×表示），即以后不再考虑了；若大于z 者，且不符合整数条件，则重复第三步，一直到最后得到z z =*为止，得最优整数解x *。

例4.2 用分枝定界法求解纯整数规划：

2123max x x z +=

⎪⎪⎩⎪⎪

⎨

⎧≥≤+≤+为整数

21212121,0,5.45.01432.x x x x x x x x t s ①

②③④

解：首先不考虑整数约束④，得到相应的线性规划问题B ：

2123max x x z +=

⎪⎩⎪

⎨⎧≥≤+≤+0,5.45.01432.2

12121x x x x x x t s 用单纯形法进行求解，得到最优解：x 1＝3.25，x 2＝2.5，max z ＝14.75。 这时上界z ＝14.75，下界z ＝0。

由于x 1＝4.5，x 2＝2.5为非整数解，取x 2＝2.5构造两个分枝。由[2.5]＝2，则两个分枝为：3,211≥≤x x 分别加到B 中构成两个后继问题B 1，B 2：

B 1：2123max x x z +=

⎪⎪⎩⎪⎪

⎨⎧≥≤≤+≤+0

,25.45.01432.2122121x x x x x x x t s

B 2：2123max x x z +=

⎪⎪⎩⎪⎪

⎨⎧≥≥≤+≤+0

,35

.45.01432.2122121x x x x x x x t s

见图4－2所示，即把原来的可行域分为

两部分，把中间没有整数解的部分切割掉，缩小搜索范围。

对B 1、B 2求解，B 1的最优解为：x 1＝3.5，x 2＝2，max z ＝14.5。B 2最优解为：x 1＝2.5，x 2＝3，max z ＝13.5。

B 1，B 2仍没有满足整数条件，需要继续分枝，这时的下界依然为z ＝0，上界为

z ＝max{14.5,13.5}＝14.5。对B 1继续分枝，B 1中只有x 1为非整数，取x 1＝3.5进行

分枝，构造两个约束分别为：31≤x ，41≥x 得到两个新的分枝B 11、B 12：

B 11：2123max x x z +=

B 12：2123max x x z +=

⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≤+≤+0,325.45.01432.21122121x x x x x x x x t s ⎪⎪⎪⎩⎪

⎪⎪⎨⎧≥≥≤≤+≤+0

,42

5.45.01432.21122121x x x x x x x x t s 其可行域如图4－3所示，对B 11进行求解，得x 1＝3，x 2＝3，max z ＝13，B 12

的最优解为x 1＝4，x 2＝1，max z ＝14。

图4－2

这时得到的满足整数约束条件的新的目标函数值为14。大于B 2分枝的目标函数值，因此B 2分枝不需要再分枝了。这时下界为z ＝14，上界为z ＝14，因此该整数规划的最优解为x 1＝4，x 2＝1，max z ＝14。

分枝定界法的过程如下：

二、割平面法

割平面法是1958年由Gomory 提出来的，它的基本思想是在与整数规划问题相对应的线性规划问题中依次引进线性约束条件，使问题的可行域逐步缩小。在求解过程中，首先不考虑变量x i 是整数这一条件，增加的线性约束条件使原可行域切掉一部分，切掉的部分中只包含非整数解，这个方法的关键是怎样找到适当的割平面，满足使可行域缩小又不切掉整数解的条件。

下面以实例说明割平面法的求解过程。

例4.3 2197max x x z +=

⎪⎩⎪

⎨⎧≥≤+≤+-且为整数

0,35

76

3.212121x x x x x x t s 解：首先不考虑整数约束，用单纯形法求解相应的线性规划问题B ，得最终单纯形表如表4－2所示：

①②③

图4—

3

图4—4

表4－2

63max ,0,2/7,2/94321=====z x x x x 由最终表中得：

27221227432=++

x x x ④

将系数和常数项分解成整数和非负真分式之和，上式化为；

2

1

3221227432+=++

x x x 移项后得：

)22

1

227(213432x x x +-=

- 现考虑整数条件，由于x 1、x 2为非负整数，由条件④知x 3、x 4也为非负整数。

在上式中左边为整数，右边（•）为正数，要使等式成立则等式右边必小于等于零，也就是整数约束条件可由下式来代替：

0)221227(2143≤+-x x 即： 2

1

221227************-≤--→≥+x x x x

这就是切割方程，将它作为约束条件，加到相应线性规划B 中，得到问题B 1。 B 1：2197max x x z +=

⎪⎪

⎪⎩⎪⎪⎪

⎨⎧≥-≤--≤+≤+-0

,,,2122122735763.43214

32121x x x x x x x x x x t s 因 ⎩⎨⎧--=-+=1

242

1373536x x x x x x

则约束方程 2

122122743-≤--

x x 变为 32≤x

图4－5

从图4－5中可见，切割方程只割去相应线性规划问题可行域的部分非整数解，原来的整数解全部保留。

对该模型B 1不需要重新求解，只要把增加的约束条件加到B 问题的最优单纯形表中。

选择x 5作为换出变量。

⎭⎬⎫

⎩⎨⎧----=⎪⎭

⎪⎬⎫⎪⎩⎪⎨⎧<-=22/111/15,22/711/28min 0|min lj lj j j a a z c θ

8}30,8min{==

所以x 3作为换入变量，进行迭代得到：

表4－4

由x 1行得：

7

32

7171541=

-+

x x x 将系数和常数项分解成整数和非负真分数之和：

7

4476715541+=+-+

x x x x 移项得：

)7671(7445451x x x x +-=

-- 得到新的约束条件： 74

767154-≤--x x

7

47671654-=+--x x x 在B 1的最优单纯形表中加上此约束，用对偶单纯形法求解：

表4－5

则最优解为3,421==x x ，最优目标函数值为z =55。

由上例求解过程，归纳割平面法求解步骤如下：

第一步：不考虑整数约束，求相应线性规划模型B 的最优解。若最优解恰为整数，则停止计算；若最优解不为整数，进入第二步。

第二步：寻找割平面方程。

①令x i 为相应线性规划最优解中不符合整数条件的一个基变量，由单纯形表的最终表得到：

i k ik k

i b x a

x =+

∑

②将b i 和a ik 都分解成整数部分N 与非负真分数f 之和：

10,1

0,<≤+=<<+=ik ik ik ik i i i i f f N a f f N b

N 表示不超过b 的最大整数，如： 如b ＝3.30 则N ＝3，f ＝0.30； 若b ＝－1.23 则N ＝－2，f ＝0.77。 将b i ，a ik 代入得到：

k ik k

i i k ik k

i x f f N x N x ∑

∑

-

=-+

③得到割平面方程：；

0≤-

∑

k ik k

i x f f

第三步：把割平面方程加入到相应线性规划B 的最终单纯形表中，用对偶单纯形法求解。若解为非负整数解，则停止计算，得到最优整数解；若得到的解不是非负整数解，重复第二步过程，重新计算。

第三节 0－1整数规划

一、0－1整数规划模型

0－1整数规划是整数规划中的特殊情形，它的变量x i 取值只能为0或1，这时的变量x j 称为0－1变量，x j 取0或1这个条件可由下述约束条件描述：

且取整数

01≥≤j j x x

0－1整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题，要求回答“是－否”或“有－无”问题，这类问题可以借助整数规划中的0－1整数变量，使许多复杂的、困难的问题相对变得简单。

0－1变量一般可表示为：

⎪⎩

⎪⎨⎧=为否或无为是或有j j j x x x 01

0－1整数规划的数学模型可表示为：

⎪⎩⎪⎨⎧=====∑∑==)

,,2,1(10),,2,1(.max 1

1

n j x m i b x a t s x c z j

i j ij n

j j

j n

j 或

二、0－1整数规划求解

0－1整数规划的求解方法有穷举法、隐枚举法和分枝定界法，穷举法把变量中所有0或1的组合找出来，比较目标函数值以求得最优解，变量组合个数为2n 个，当n 大于10时，这几乎是不可能的；隐枚举法（Implicit Enumeration ）只检查变量取值的组合的一部分，就能求得最优解；分枝定界法是用第二节介绍的方法求解0－1规划。下面分别介绍隐枚举法和分枝定界法的求解过程。

（一）隐枚举法求解

例4.4 max z ＝4x 1＋3x 2＋2x 3

⎪⎪⎩

⎪⎪

⎨

⎧=≥+≥++≤+-10,,13

344352.32132

321321或x x x x x x x x x x x t s

解：（1）先用试探的方法找出一个初始可行解，如x 1＝x 2＝0，x 3＝1。满足约束条件，选其作为初始可行解，目标函数z 0＝2。

（2）附加过滤条件

以目标函数0z z ≥作为过滤约束：

2234321≥++x x x

原模型变为：

max z ＝4x 1＋3x 2＋2x 3

⎪⎪⎪⎩⎪

⎪⎪

⎨⎧=≥++≥+≥++≤+-1

0,,2

2341

3344352321321

32321321或x x x x x x x x x x x x x x （3）求解

按照隐枚举法的思路，依次检查各种变量的组合，每找到一个可行解，求出它的目标函数值z 1，若z 1＞z 0，则将过滤条件换成z ＞z 1。

一般讲过滤条件是所有条件中关键的一个，先检查它是否满足，若不满足，其他约束条件也就不用检查了，减少了计算的工作量，这也是隐枚举法与穷举法最大的区别，它不需要将所有可行的变量组合一一枚举，只是通过分析、判断，很多可行的变量组合排除了最优解的可能性，也就是说被隐含了，隐枚举法就此得名。

求解过程如表4－6所示。

所以该0－1规划最优解为9,1**

3*2*1====z x x x 。

（二）用分枝定界法求解

例4.5 设有100万元的资金计划在五个不同的地方P 1、P 2、P 3、P 4、P 5修建某类工厂，由于条件不同，所需投资分别为a 1＝56、a 2＝20、a 3＝54、a 4＝42、a 5＝15，

①

②③④

（单位万元），工厂建成后，每年能得到的利润分别为c 1＝7、c 2＝5、c 3＝9、c 4＝6、c 5＝3（单位万元），问应如何确定投资地点，投资总额不超过100万元，且使建成后每年所获总利润最多？

解：设

5,4,3,2,1,

0,1=⎪⎩⎪⎨

⎧=j P P x j j j 处投资建厂

不在处投资建厂在

则模型可表示为

max z ＝7x 1＋5x 2＋9x 3＋6x 4＋3x 5

56x 1＋20x 2＋54x 3＋42x 4＋15x 5≤100 ① x j ＝0或1，j ＝1，2，3，4，5 ②

首先考虑投资一万元于第j 处地方所能获得利润，即c j /a j 的比值。

在P 1处：c 1/a 1＝1/8；在P 2处：c 2/a 2＝1/4；在P 3处：c 3/a 3＝1/6；在P 4处：c 4/a 4

＝1/7；在P 5处：c 5/a 5＝1/5。

按单位资金获利最大的尽量先取的原则，先把上述比值中最大的所对应的变量取为1，即x 2＝1，其次取比值次大的所对应的变量为1，即x 5＝1，…，依此下去，使之满足条件①，即x 3＝1，x 4＝11/42，x 1＝0。

得到一个解：7

418,)1,4211,

1,1,0(1)1(==z x T z 1作为原问题目标函数的上界，x (1)不是原问题的可行解，因为11/42不是整数。

由于x 4只能取0或1，所以分别令x 4＝0或x 4＝1将原问题分枝为两个子问题。

B 1： max z ＝7x 1＋5x 2＋9x 3＋3x 5

56x 1＋20x 2＋54x 3＋15x 5≤100

x 4＝0 x j ＝0或1，j ＝1，2，3，5

B 2： max z ＝7x 1＋5x 2＋9x 3＋3x 5＋6

56x 1＋20x 2＋54x 3＋15x 5≤58 x 4＝1

x j ＝0或1，j ＝1，2，3，5

用同样方法，可求得问题B 1的松弛问题的解为：

8318,)1,0,1,1,5611(

2)2(==z x T B 2的松弛问题的解为：

6

5

17,)1,1,5423,

1,0(3)3(==z x T 由于x (2)和x (3)都不是整数解，且z 3＜z 2，所以先对B 1进行分枝。分解的方法仍

根据非整数值的变量x 1，使x 1为0或1。分别令x 1＝0或x 1＝1，把B 1分枝为B 11和B 12：

s.t

s.t

s.t

B 11： max z ＝5x 2＋9x 3＋3x 5

⎪⎩⎪

⎨⎧====≤++5,3,2,100

,010*******.14532j x x x x x x t s j

或 B 12： max z ＝5x 2＋9x 3＋3x 5＋7

⎪⎩⎪

⎨⎧====≤++5,3,2,101

,044155420.14532j x x x x x x t s j

或 B 11的解为：

17,)1,0,1,1,0(4)4(==z x T

B 12的解为：

2

1

16,)1,0,61,1,1(5)5(==z x T

B 12的目标函数值小于B 11的值，则B 12剪枝。 再考虑B 2，由于176

5

17

43=>=z z ，

对B 2中以x 3变量进行分枝，令x 3＝0或1，得到B 21和B 22。

B 21： max z ＝7x 1＋5x 2＋3x 5＋6

⎪⎩⎪

⎨⎧====≤++5,2,1,100

,158152056.34521j x x x x x x t s j

或 B 22： max z ＝7x 1＋5x 2＋3x 5＋15

⎪⎩⎪

⎨⎧====≤++5,2,1,101

,14152056.34521j x x x x x x t s j

或 B 21松驰问题的解为：

178

7

16,)1,1,0,1,5623(

46)6(=<==z z x T 则B 21剪枝。

B 22松驰问题的解为：

1716,)0,1,1,5

1

,0(47)7(=<==z z x T

同样B 22可剪枝。 由此得最优解：

17,)1,0,1,1,0(**==z x T

分枝定界过程如下：

图4－6

三、0－1整数规划应用

（一）相互排斥的计划 例4.6 某公司拟在市东、西、南三区中建立门市部，有7个点A i （i ＝1，2，…，7）可供选择，要求满足以下条件：

（1）在东区，在A 1，A 2，A 3三个点中至多选两个； （2）在西区，A 4，A 5两个点中至少选一个； （3）在南区，A 6，A 7两个点为互斥点。 （4）选A 2点必选A 5点。

若A i 点投资为b i 万元，每年可获利润为c i 万元，投资总额为B 万元，试建立利润最大化的0－1规划模型。

解：设决策变量为

7,,2,1,

0,1 =⎩⎨

⎧=i A A x i i i 点未被选用

当点被选用当

建立0－1规划模型如下：

i

i i x c x c x c x c z ∑==

+++=7

1

772211max

⎪

⎪⎪⎪⎩⎪

⎪⎪⎪⎨⎧==≤-=+≥+≤++≤⋅∑

=7

,,2,1,1001

1

2.5276

543217

1

i x x x x x x x x x x B x b t s i i i i ，或 （二）相互排斥的约束条件

例4.7 某产品有A 1和A 2两种型号，需要经过B 1、B 2、B 3三道工序，单位工

时和利润、各工序每周工时限制见表所示，问工厂如何安排生产，才能使总利润最大？（B 3工序有两种加工方式B 31和B 32，产品为整数）。

表4-7

1212214025max x x z +=

B 1和B 2两工序每周工时的约束条件为

100

1.02.0250

7.03.02121≤+≤+x x x x

工序B 3有两种加工方式B 31和B 32，每周工时约束分别为

120

4.02.0150

5.03.02121≤+≤+x x x x

工序B 3只能从两种加工方式中选择一种，那么这两个约束就成为相互排斥的约束条件。为了统一在一个问题中，引入0-1变量

⎩⎨

⎧=加工方式

不采用若工序加工方式采用若工序3133131,

1,0B B B B y

⎩

⎨

⎧=加工方式不采用若工序加工方式

采用若工序3133132,1,0B B B B y 于是，相互排斥的约束条件可用下列三个约束条件统一起来 ⎪⎩⎪

⎨⎧=++≤++≤+1

1204.02.01505.03.021

22211121y y y M x x y M x x 其中M 1和M 2都是充分大的正数。

则数学模型为

214025max x x z +=

⎪

⎪⎪⎪⎩⎪

⎪⎪⎪

⎨⎧-≥=++≤++≤+≤+≤+变量

为且均为整数10,,0,1

1204.02.01505.03.0100

1.02.02507.03.0..212121

222111212121y y x x y y y M x x y M x x x x x x t s

一般地，在建立数学模型时，若需从p 个约束条件

∑=≤1

j i j ij

b x a

（i=1,2,…,p ）

中选择q 个约束条件，则可以引入p 个0-1变量

⎩⎨

⎧=个约束

若不选择第个约束若选择第i i y i ,

1,0 （i=1,2,…,p ）

那么约束条件组

⎪⎪⎩⎪⎪⎨⎧-=+≤∑∑==p

i i j i i i j ij q p y y M b x a 1

1

（i=1,2,…,p ） 就可以达到这个目的。因为上述约束条件组保证了在p -q 个0-1变量中有p 个为1，

q 个为0。凡取0值的y i 对应的约束条件为原约束，而取1值的y i 对应的约束条件将自然满足，因而是多余的。

（三）固定成本问题

例4.8 某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示：

表4-8

6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，另外若生产，不管每种容器生产多少，都需要支付一笔固定费用：小号为100万元，中号为150万元，大号为200万元。问如何制定生产计划使获得的利润对大？ 解：设x 1、x 2、x 3分别为小号容器、中号容器、大号容器的生产数量。

各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设

3,2,10

,

00,1=⎩⎨

⎧=>=i x i x i y i i i 种容器时即当不生产第时种容器即当生产第

则目标函数为

321321200150100654max y y y x x x z ---++= 考虑三种资源的约束，得到三个不等式

100

32300432500

842321321321≤++≤++≤++x x x x x x x x x 为了避免出现某种容器不投入固定费用就生产这样一种不合理的情况，因而加

上以下约束条件：

M

y x M y x M

y x 332211≤≤≤ 这里M 为充分大的正数。

以上分析可知，该问题的数学模型为

321321200150100654max y y y x x x z ---++=

⎪⎪⎪

⎪⎪⎩⎪⎪

⎪⎪⎪

⎨

⎧-≥≤-≤-≤-≤++≤++≤++变量为10,,0

,,000

10032300432500842..3

213213322

11321321321y y y x x x My x My x My x x x x x x x x x x t s （四）布点问题

例4.9 某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点最少的计划。

表4－9 消防车在各区间行驶时间表 单位：min

i 6,,2,1,

0,1 =⎩⎨

⎧=i i i x i 不设消防站

表示在地区设消防站表示在地区

目标函数为

min z ＝x 1＋x 2＋x 3＋x 4＋x 5＋x 6

本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表4－9可知，在地区1及地区2内设消防站都能达到此要求，即

x 1＋x 2≥1

因此本问题的数学模型为：

min z ＝x 1＋x 2＋x 3＋x 4＋x 5＋x 6

x 1＋x 2 ≥1 x 1＋x 2 ＋x 6≥1 x 3＋x 4 ≥1 x 3＋x 4＋x 5 ≥1 x 4＋x 5＋x 6 ≥1 x 2 ＋x 5＋x 6 ≥1 x i ＝1或0 （i ＝1，…，6） （五）背包问题

例4.10 一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表4－10所示，能携带的最大重量为25 kg ，试选择该队员所应携带的物品。

表4－10

i ⎩

⎨

⎧=i i

i x x x 不携带物品携带物品01 （i ＝1，…，7） 则0－1规划模型为：

max z ＝20x 1＋15x 2＋16x 3＋14x 4＋8x 5＋14x 6＋9x 7 s.t. 5x 1＋5x 2＋2x 3＋5x 4＋10x 5＋2x 6＋3x 7≤25

x i ＝0或1，i ＝1，0，…，7

这是一个约束的背包问题称为一维的，如果有两个或三个约束称为二维或三维背包问题。

（六）指派问题

指派问题（Assignment Problem ）是一种特殊的整数规划问题。在实践中经常会遇到一种问题：某单位有m 项任务要m 个人去完成（每人只完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。

例4.11 有四件工作A 、B 、C 、D 要求甲、乙、丙、丁四个人去完成，每人完成每项工作所需时间见表4－11所示，应指派何人去完成何种工作，使总的时间最少？

表4－11

s.t

类似于这样的问题，就属于指派问题。上表中数字表称为效率矩阵。推广到一般性问题，有m 项任务，安排m 个人去完成，如何指派使资源消耗最小或效率最大化。

引入0－1变量x ij

⎩⎨

⎧=项任务

个人完成第不指派第项任务

个人完成第指派第j i j i x ij 01 （i ＝1，2，…，m ，j ＝1，2，…，m ）

则指派问题的数学模型为：

ij ij m

j m i x c

z ∑∑===

1

1

min

⎪⎪⎪⎪⎩

⎪⎪⎪⎪⎨⎧=====∑∑==10,,2,11,,2,11.1

1或ij ij m

i ij m

j x m j x m i x t s

由模型可知，指派问题是0－1整数规划的特例，也是运输问题的特例，当然可

用0－1规划或运输问题的求解方法进行求解，但由于其模型的特殊性，可用匈牙利法进行求解，这个方法是由匈牙利数学家狄•考尼格提出来的。具体求解方法见其它参考书。

习 题

1 用分枝定界法求解下列整数规划 （1）21max x x z +=

（2）32133max x x x z ＋+=

⎪⎪⎪

⎩

⎪

⎪

⎪⎨⎧

≥≤+-≤+且为整数0,3121451149..212121x x x x x x t s

⎪⎪⎩

⎪⎪

⎨

⎧≥≤+-≤-≤++-为整数且31321321

32321,0,,3232

344

2..x x x x x x x x x x x x x t s 2 用割平面法求解 （1）213max x x z +=

（2）212010max x x z +=

⎪⎪⎩⎪⎪

⎨

⎧≥≤+≤+≤+且为整数

0,20546

5462..21212121x x x x x x x x t s

⎪⎪⎩⎪⎪

⎨

⎧≥≤≤≤+且为整数

0,48

34.025.0.212121x x x x x x t s 3 求解0－1规划

（1）321523max x x x z +=－

（2）321234max x x x z ++=

⎪⎪⎪⎩⎪⎪⎪

⎨⎧=≤+≤+≤++≤-+1

0,,6434

42

2.3213121321321或x x x x x x x x x x x x x t s ⎪⎪⎩⎪⎪⎨

⎧=≥+≥++≤+-1

0,,13

344352.32132

321321或x x x x x x x x x x x t s 4 现要将一些不同类型的货物装到一条货船上，这些货物的重量、单位体积、冷藏要求、可燃性指数都不相同，有关数据见下表：

该船可以装载的总重量为400 000公斤，总体积为50 000立方米，可以冷藏的总体积为10 000立方米，容许的可燃性指数的总和不能超过750。目标是希望装载的货物取得最大的价值。（注：装到船上的各种货物的件数只能是整数）。

5 考虑资金分配问题，在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用（千元）如表所示，假定每一项已经批准的工程要在整个3年内完成，目标是要选出使总收入达到最大的那些工程。把这个问题表示成一个0－1整数规划模型。

个设备进行加工，有关数据如下表所示：

（2）如果总用电量限制在2800度时，请制定一个成本最低的方案。

（3）如果总用电量没有限制，请制定一个成本最低的方案。

7 有三种资源可用来生产三种产品。有关数据见表所示，由于不同产品的生产组织不同，因而涉及的固定费用不同，见表所示，问如何制定一个生产计划，使总收益最大？

位时间获得利润也不同，其效率如下表，求利润最大的分派问题模型。

运筹学第3版熊伟编著习题答案

运筹学（第3版）习题答案 第1章线性规划 P36 第2章线性规划的对偶理论 P74 第3章整数规划 P88 第4章目标规划 P105 第5章运输与指派问题P142 第6章网络模型 P173 第7章网络计划 P195 第8章动态规划 P218 第9章排队论 P248 第10章存储论P277 第11章决策论P304 第12章 多属性决策品P343 第13章博弈论P371 全书420页 第1章 线性规划 1.1工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤??++≤??≤≤?? ≤≤??≤≤?≥?? 1.2建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示：

问怎样下料使得（1）用料最少；（2）余料最少． 【解 设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 10 1 12342567368947910 min 2800212002600223900 0,1,2,,10 j j j Z x x x x x x x x x x x x x x x x x x j ==?+++≥? +++≥?? +++≥??+++≥??≥=?∑L （2）余料最少数学模型为 2345681012342567368947910 min 0.50.50.52800 212002********* 0,1,2,,10 j 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 j =++++++?+++≥? +++≥?? +++≥??+++≥??≥=?L 1.3某企业需要制定1～6月份产品A 的生产与销售计划。已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A 的单件成本与售价如表1－25所示。 （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设x j 、y j （j ＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为

运筹学第四章(完整版)

13物流工程3班第四组 组员：李鲁超胡军李康郭优沈西王伟 第四章 1.讨论面向顾客设计思想的重要性。P112-113 顾客需求的多样化和个性化，使得市场演变和产品更新的速度越来越快，产品的生命周期越来越短。通过与顾客的交流，倾听顾客的心声，听取他们对改进产品的建议，以此来分析顾客的需求，挖掘新产品创意。 2.讨论产品开发在企业战略中的重要地位。P135 一、21世纪企业产品设计的背景特征： （1）新产品开发是实现企业竞争战略的需要 技术进步和需求多样化使得产品寿命周期不断缩短，企业面临着缩短交货期、提高产品质量、降低成本和改进服务的多重压力。新产品开发是企业经营战略的核心内容之一，也是生产运作战略的出发点，产品开发智能的目的就是要研究、开发、设计出能满足市场需求并具有竞争力的产品。 （2）技术进步越来越快 科学技术飞速发展，并被迅速而广泛地应用于实践中，推动着新产品的开发，也使得产品更新换代的速度越来越快，产品生命周期越来越短。 （3）用户的要求越来越苛刻 随着时代的发展，大众知识水平的提高和激烈竞争带给市场越来越多、越来越好的产品，使用户的要求越来越高。 （4）产品研制开发的难度越来越大 越来越多的企业认识到新产品开发对企业创造收益的重要性，特别是那些大型、结构复杂，技术含量高的产品在研制中一般都需要各种先进的设计技术。 （5）可持续发展的要求 人类社会在经济快速发展的同时，由于忽略了环境保护，也带来了污染、酸雨、土地沙化，臭氧层破坏等恶果。各国政府将环境保护问题纳入发展战略，这对企业提出了更高的要求。 二、新产品开发的重要性 （1）有利于增强企业的核心竞争力 （2）有利于扩大市场份额 （3）适应个性化定制生产的需要 （4）产品更新换代的需要 3.讨论新产品开发的重要性？P109

《运筹学》 第四章习题及 答案

《运筹学》第四章习题 一、思考题 1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最 多等于1-+n m ？ 2． 用左上角法确定运输问题的初始基本可行解的基本步骤是什么？ 3． 最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到 运输问题的最优方案？ 4． 沃格尔法（V ogel 法）的基本思想是什么？它和最小元素法相比给出的运输问题的 初始基本可行解哪一个更接近于最优解？为什么？ 5． 试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什 么？ 6． 用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭 回路是否是唯一的？ 7． 试述用位势法求检验数的原理、步骤和方法。 8． 试给出运输问题的对偶问题（对产销平衡问题）。 9． 如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输 问题。 10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？ 11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。 二、判断下列说法是否正确 1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。 2．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。 3．在运输问题中，只要给出一组（1-+n m ）个非零的 {}j i x ，且满足 ∑==n j i j i a x 1，∑==m i j j i b x 1，就可以作为一个基本可行解。 4．表上作业法实质上就是求解运输问题的单纯形法。 5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。 6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案将不会发生变化。 7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k ，最优调运方案将不会发生变化。 8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必须是正的。 9．用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。 10．当所有产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。 三、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。 （1）用左上角法、最小元素法、沃格尔法求初始基本可行解； （2）由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要

运筹学实验6整数规划

实验六、用EXCEL 求解整数规划 用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产设备的台数等等。对于整数解的线性规划问题，不是用四舍五入或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝定界法和割平面算法。这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规划的数学算法有一定的困难。然而事实上，由于Excel 的[工具][规划求解]可以求解整数规划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算法将不是障碍因素。 一、实验目的 1、 掌握如何建立整数线性规划模型，特别是0～1逻辑变量在模型中的应用。 2、 掌握用Excel 求解整数线性规划模型的方法。 3、 掌握如何借助于Excel 对整数线性规划模型进行灵敏度分析，以判断各种可能 的变化对最优方案产生的影响。 4、 读懂Excel 求解整数线性规划问题输出的运算结果报告和敏感性报告。 二、 实验内容 1、 整数规划问题模型 该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13,题目如下: 需生产2000件某种产品，该种产品可利用A 、B 、C 、D 设备中的任意一种加工，已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问题的数学模型并求解。 该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必须借助于逻辑变量来鉴定准备结束费用的支付。 再设 ，种设备加工的产品数量 为利用第设;4,3,2,1=j j x j ⎪⎩⎪⎨ ⎧=>=）种设备生产（即，若不使用第 ）种设备生产（即若使用第000,1j j i x j x j y 4,3,2,1=j 则问题的整数规划模型为： 43214321281624207008009801000min x x x x y y y y z +++++++= ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨ ⎧==≥≤≤≤≤=+++4 ,3,2,110,01600120010009002000..4 43322114321 j y x y x y x y x y x x x x x t s j j ，或

运筹学 第4章 整数规划

第四章整数规划 整数规划（Integer Programming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题，在项目投资、人员分配等方面有着广泛的应用。 整数规划是近二、三十年发展起来的数学规划的一个重要分支，根据整数规划中变量为整数条件的不同，整数规划可以分为三大类：所有变量都要求为整数的称为纯整数规划（Pure Integer Programming）或称全整数规划（All integer Programming）；仅有一部分变量要求为整数的称为混合整数规划（Mixed Integer Programming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为0－1规划。 本章主要讨论整数规划的分枝定界法、割平面法、0－1规划及指派问题。 第一节整数规划问题及其数学模型 一、问题的提出 在线性规划模型中，得到的最优解往往是分数或小数，但在有些实际问题中要求有的解必须是整数，如机器设备的台数、人员的数量等，这就在原来线性规划模型的基础上产生了一个新的约束，即要求变量中某些或全部为整数，这样的线性规划称为整数规划（Integer Programming）简称IP，是规划论中的一个分枝。 整数规划是一类特殊的线性规划，为了满足整数解的条件，初看起来，只要对相应线性规划的非整数解四舍五入取整就可以了。当然在变量取值很大时，用上述方法得到的解与最优解差别不大，当变量取值较小时，得到的解与实际最优解差别较大，当变量较多时，如n＝10个，则整数组合有210＝1024个，而且整数解不一定在这些组合当中。先来看下面的例子。 例4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？ 表4－1 12 量都要求为整数，建立模型如下：

运筹学第四章

第 5 次课 2学时 本次课教学重点： 建立数学模型 本次课教学难点： 建立数学模型 本次课教学内容： 第四章线性规划在工商管理中的应用 第一节人力资源分配的问题 例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 解：设x i( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5≥28 x2 + x3 + x4 + x5 + x6≥15 x3 + x4 + x5 + x6 + x7≥24 x4 + x5 + x6 + x7 + x1≥25 x5 + x6 + x7 + x1 + x2≥19 x6 + x7 + x1 + x2 + x3≥31 x7 + x1 + x2 + x3 + x4≥28 x1,x2,x3,x4,x5,x6,x7≥0 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？

解：设x i ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥28 x2 + x3 + x4 + x5 + x6 ≥15 x3 + x4 + x5 + x6 + x7 ≥24 x4 + x5 + x6 + x7 + x1 ≥25 x5 + x6 + x7 + x1 + x2 ≥19 x6 + x7 + x1 + x2 + x3 ≥31 x7 + x1 + x2 + x3 + x4 ≥28 x1,x2,x3,x4,x5,x6,x7 ≥0 第二节生产计划的问题 例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？ 解：设x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。 求x i 的利润：利润= 售价- 各成本之和 产品甲全部自制的利润=23-(3+2+3)=15 产品甲铸造外协，其余自制的利润=23-(5+2+3)=13

运筹学第3版熊伟编著习题答案

运筹学（第3版）习题答案 第1章 线性规划 P36 第2章 线性规划的对偶理论 P74 第3章 整数规划 P88 第4章 目标规划 P105 第5章 运输与指派问题P142 第6章 网络模型 P173 第7章 网络计划 P195 第8章 动态规划 P218 第9章 排队论 P248 第10章 存储论P277 第11章 决策论P304 第12章 多属性决策品P343 第13章 博弈论P371 全书420页 第1章 线性规划 1.1 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤??++≤??≤≤?? ≤≤??≤≤?≥?? 1.2 建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示：

问怎样下料使得（1）用料最少；（2）余料最少． 【解 设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 10 1 12342567368947910 min 2800212002600223900 0,1,2,,10 j j j Z x x x x x x x x x x x x x x x x x x j ==?+++≥? +++≥?? +++≥??+++≥??≥=?∑ （2）余料最少数学模型为 2345681012342567368947910 min 0.50.50.52800 212002********* 0,1,2,,10 j 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 j =++++++?+++≥? +++≥?? +++≥??+++≥??≥=? 1.3某企业需要制定1～6月份产品A 的生产与销售计划。已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A 的单件成本与售价如表1－25所示。 （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设x j 、y j （j ＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为

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

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

整数规划例题

〈运筹学〉补充例题 例题 1.1 某工厂可以生产产品A和产品B两种产品。生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。这两种产品在市场上是畅销产品。该工厂经理要制订季度的生产计划，其目标是使工厂的销售额最大。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 产品售价（元） 800 300 MAX 800X1 +300X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.2该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价格调整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产计划，其目标仍然是使工厂的销售额最大。 X 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.3由于某些原因，该工厂面临产品原料供应的问题。因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。有关信息在下表中给出。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 原材料(公斤) 11 8 130 产品售价（元） 600 400 MAX 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 11X1 +8X2 <= 130 X1, X2 >=0 例题 1.４随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。工厂的各种产品所需要的机时、人

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

运筹学实验报告四整数规划《运筹学》实验报告 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))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

运筹学知识点

运筹学知识点： 绪论 1.运筹学的起源 2.运筹学的特点 第一章线性规划及单纯形法 1.规划问题指生产和经营管理中如何合理安排，使人力、物力等各种资源得到充分利用，获得最大效益。 2.规划问题解决两类问题：一是给定一定数量的人力、物力等资源，研究如何充分利用，以发挥其最大效果；二是已给定计划任务，研究如何统筹安排，用最少的人力和物力去完成。 3.规划问题的数学模型包含三个组成要素：决策变量、目标函数（单一）、约束条件（多个）。 线性规划问题的数学模型要求：决策变量为可控的连续变量，目标函数和约束条件都是线性的。 4.线性规划问题的标准形式：目标函数为极大、约束条件为等式、决策变量为非负、变量为非负 5.划标准型时添加的松驰变量、剩余变量和人工变量 6.理解可行解、最优解、基、基解、基可行解等概念，且掌握各类解间的关系 7.用图解法理解线性规划问题的四种解的情况：无穷多最优解、无界解、无可行解、唯一最优解 8.用图解法只有解决两个变量的决策问题 9.线性规划问题存在可行解，则可行域是凸集。 10.线性规划问题的基可行解对应线性规划问题可行域的顶点。 11.线性规划问题的解进行最优性检验：当所有的检验数小于等于零时为最优解；尤其当检验数小于零时（即不等于零）有唯一最优解；当某个非基变量检验数为时，有无穷多最优解；当存在某个检验数大于零且对应的系数又小于等于零时，有无界解。 12.单纯形法的计算过程，可能出计算题 13.入单纯形表前首先要化成标准形式。 14.确定换出变量时根据θ值最小原则，且要求公式中对应的系数大于零。 15.当线性规划中约束条件为等式或大于等于时，划为标准型后，系数矩阵中又不包含单位矩阵时，需要添加人工变量构造一个单位矩阵作为基。 16.人工变量的系数为足够大的一个负值，用—M代表 17.一般线性规划问题的数学建模题（生产计划问题、人才资源分配问题、混合

运筹学整数规划例题

运筹学整数规划例题 练习4.9 连续投资问题 某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限. 项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元. 项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元. 项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益. (1) x 为项目各年月初投入向量。 (2) ij x 为 i 种项目j 年的月初的投入。 (3) 向量c 中的元素 ij c 为i 年末j 种项目收回本例的百分比。 (4) 矩阵A 中元素 ij a 为约束条件中每个变量ij x 的系数。 (5) Z 为第5年末能拥有的资金本利最大总额。 因此目标函数为 4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++ 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金. 第1年年初该投资者拥有10万元资金,故有 11100000A D x x +=. 第2年年初该投资者手中拥有资金只有()116%D x +,故有 22211.06A C D D x x x x ++=. 第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有 333121.15 1.06A B D A D x x x x x ++=+ 同理第4年、第5年有约束为

运筹学习题精选

运筹学习题精选 第一章线性规划及单纯形法 选择 1．在线性规划模型中，没有非负约束的变量称为……………………………………………………( C ) A．多余变量 B．松弛变量 C．自由变量 D．人工变量 2．约束条件为0 AX的线性规划问题的可行解集 b ,≥ =X 是………………………………………( B ) A．补集 B．凸集 C．交集 D．凹集 3．线性规划问题若有最优解，则一定可以在可行域的（ C）上达到。 A．内点 B．外点 C．顶点 D．几何点 4．线性规划标准型中bi（i=1，2，……m）必须是…………………………………………………( B) A．正数 B．非负数 C．无约束 D．非零的 5．线性规划问题的基本可行解X对应于可行域D 的………………………………………………( D) A．外点 B．所有点 C．内点 D．极点 6．基本可行解中的非零变量的个数小于约束条件数时，该问题可求得……………………………( B ) A．基本解 B．退化解 C．多重解 D．无解 7．满足线性规划问题全部约束条件的解称为…………………………………………………( C ) A．最优解 B．基本解 C．可行解 D．多重解 8．线性规划一般模型中，自由变量可以用两个非负变量的（B ）代换。 A．和 B．差 C．积 D．商 9．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得………………………( A )

A ．多重解 B ．无解 C ．正则解 D ．退化解 10．若线性规划问题有最优解，则必定存在一个( D )是最优解。 A ．无穷多解 B. 基解 C. 可行解 D. 基可行解 填空 计算 1． 某厂生产甲、乙、丙三种产品，已知有关数据如下表所示,求使该厂获利最大的生产计划。 2． 目标函数为max Z =28x4+x5+2x6，约束形式为“≤”，且x1，x2，x3为松弛变量， 表中的解代入目标函数中得Z=14，求出a~g 的值，并判断是否→j c 0 0 0 28 1 2 B C 基 b 1x 2x 3x 4x 5x 6x 2 6x A 3 0 -14/3 0 1 1 0 2x 5 6 D 2 0 5/2 0 28 4x 0 0 E F 1 0 0 j j z c - B C 0 0 -1 G

《运筹学》试题及答案(四)

《运筹学》试题及答案 一、单选题 1. μ是关于可行流f的一条增广链，则在μ上有（D） A.对一切 B.对一切 C.对一切 D.对一切 2.不满足匈牙利法的条件是(D) A.问题求最小值 B.效率矩阵的元素非负 C.人数与工作数相等 D.问题求最大值 3.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）C A.树的逐步生成法 B.求最小技校树法 C.求最短路线法 D.求最大流量法 4.串联系统可靠性问题动态规划模型的特点是（）D A.状态变量的选取 B.决策变量的选取 C.有虚拟产地或者销地 D.目标函数取乘积形式 5.当基变量x i的系数c i波动时，最优表中引起变化的有(B) A.最优基B B.所有非基变量的检验数 C.第i 列的系数 D.基变量X B 6.当非基变量x j的系数c j波动时，最优表中引起变化的有(C) A.单纯形乘子 B.目标值 C.非基变量的检验数 D. 常数项 7.当线性规划的可行解集合非空时一定(D) A.包含点X=(0,0,···,0) B.有界 C.无界 D.是凸集 8.对偶单纯形法的最小比值规划则是为了保证(B) A.使原问题保持可行 B.使对偶问题保持可行 C.逐步消除原问题不可行性 D.逐步消除对偶问题不可行性 9.对偶单纯形法迭代中的主元素一定是负元素（）A A.正确 B.错误 C.不一定 D.无法判断 10.对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（）B A.换出变量 B.换入变量 C.非基变量 D.基变量 11.对LP问题的标准型：max,,0 Z CX AX b X ==≥，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（）B A.增大 B.不减少 C.减少 D.不增大 12. 单纯形法迭代中的主元素一定是正元素( ）A A.正确 B.错误 C.不一定 D.无法判断 13.单纯形法所求线性规划的最优解（）是可行域的顶点。A A.一定 B.一定不 C.不一定 D.无法判断 14.单纯形法所求线性规划的最优解（）是基本最优解。A A.一定 B.一定不 C.不一定 D.无法判断 15.动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的（）A A.正确 B.错误 C.不一定 D.无法判断 16.动态规划的核心是什么原理的应用（）A A.最优化原理 B.逆向求解原理 C.最大流最小割原理 D.网络分析原理 17.动态规划求解的一般方法是什么？（）C A.图解法 B.单纯形法 C.逆序求解 D.标号法 18.工序（i,j）的最乐观时间、最可能时间、最保守时间分别是5、8和11，则工序（i,j）的期望时间是（C） A. 6 B. 7 C. 8 D. 9

运筹学课后答案2

运筹学（第2版）习题答案2 第1章 线性规划 P36~40 第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页 由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》 习题六 6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。 【解】边[i ，j ]的长度记为c ij ，设 ⎩⎨ ⎧=否则 包含在最小部分树内边0],[1j i x ij 数学模型为： ,12 132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,23 3 344,510ij ij ij i j ij Z c 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 x x x x x x x x x x x x x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,] i j ⎧⎪⎪ ⎪⎪⎪ ⎪⎪⎨ ⎪⎪ ⎪⎪⎪ ⎪⎪ ⎩所有边 6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。 图6－ 42