运筹学整数规划补例

运筹学难点辅导材料

整数规划补例

max z =x 1+x 2

⎧14x 1+9x 2≤51⎪-6x +3x ≤1

1、对（IP ）整数规划问题，问用先解相应的线性规划然后凑整的办法能否⎪12

s .. t ⎨

⎪x 1≥0, x 2≥0⎪⎩x 1, x 2为整数

求到最优整数解？再用分支定界法求解。

解 先不考虑整数约束，得到线性规划问题（一般称为松弛问题LP ）

max z =x 1+x 2

⎧14x 1+9x 2≤51310

用图解法求出最优解x 1=, x 2=且⎪

s .. t ⎨-6x 1+3x 2≤123⎪x ≥0, x ≥0

2⎩1

29z =。

6

如用“舍入取整法”凑整可得到四个点，即（1，3）、（2，3）、（1，4）、（2，4）。代入约束条件发现他们都不是可行解。可将可行域内的所有整数点一一列举（完全枚举法），本例中（2，2）、（3，1）点为最大值z =4。

0令X ()

29⎛310⎫0(0)

。可行域记为D ，显然X 不是整数解。 = , ⎪及最优值z ()=6⎝23⎭

(0)

T

定界：取=z 即0≤z ≤

*

=

29T

，再用视察法找一个整数可行解X '=(0,0)及z '=0，取=z '=0，6

29 6

分支：（关键点，在B 的最优解中任选一个不符合整数条件的变量x j ，其值为b j ，构造两个约束条件x j ≥⎡）任取最优解中一个不为整数的⎣b j ⎤⎦+1, x j ≤⎡⎣b j ⎤⎦，这里用了取整函数呵！变量值，例如x 1=

3⎡3⎤

，根据⎢⎥=1，构造两个约束条件，形成下面两个子问题（IP1）2⎣2⎦

max z =x 1+x 2max z =x 1+x 2

⎧14x 1+9x 2≤51⎧14x 1+9x 2≤51

⎪⎪-6x +3x ≤1-6x 1+3x 2≤112⎪⎪和（IP2）

⎪⎪s .. t ⎨x 1≤1s .. t ⎨x 2≥2⎪x ≥0, x ≥0⎪x ≥0, x ≥0122⎪⎪1⎪⎪⎩x 1, x 2为整数⎩x 1, x 2为整数

解（IP1）和（IP2），得最优解分别为X ()

1

1041⎛7⎫⎛23⎫

= 1, ⎪, z (1)=和X (2)= 2, ⎪, z (2)=，

39⎝3⎭⎝9⎭

4141=min z (1), z (2)，0≤z *≤ 99

T T

这两个都不是符合整数条件的可行解。

修改上下界：根据个分支的最优解，可取新的上界=再分支：由于z

(1)

{}

23⎡23⎤

，根据⎢⎥=2，构造两个约9⎣9⎦

max z =x 1+x 2max z =x 1+x 2

⎧14x 1+9x 2≤51⎧14x 1+9x 2≤51

⎪-6x +3x ≤1⎪-6x +3x ≤1

122⎪⎪1

⎪⎪束条件，形成下面两个子问题（IP3）和（IP4）。 ⎪x 1≥2⎪x 1≥2s .. t ⎨s .. t ⎨⎪x 2≤2⎪x 2≥3⎪x 1≥0, x 2≥0⎪x 1≥0, x 2≥0⎪⎪⎪⎪⎩x 1, x 2为整数⎩x 1, x 2为整数

解相应的松弛问题（IP3）和（IP4），得（IP4）无可行解，（IP3）的最优解为X

(3)

61⎛33⎫

= ,2⎪, z (3)=。14⎝14⎭

T

在考虑（IP1），由（IP1）的最优解，取x 2=

7⎡7⎤

，根据⎢⎥=2，构造两个约束条件，形成下面3⎣3⎦

max z =x 1+x 2max z =x 1+x 2

⎧14x 1+9x 2≤51⎧14x 1+9x 2≤51

⎪-6x +3x ≤1⎪-6x +3x ≤1

22⎪1⎪1

两个子问题（IP5）⎪和（IP6）⎪，得（IP6）无可行解，（IP5）⎪x 1≤1⎪x 1≤1

s .. t ⎨s .. t ⎨

x ≤2⎪2⎪x 2≥3⎪x 1≥0, x 2≥0⎪x 1≥0, x 2≥0⎪⎪x , x 为整数⎪⎪⎩12⎩x 1, x 2为整数

的最优解为

X ()=(1, 2), z ()=3。

5

T

5

在修改上下界：根据上述两个最优解的情况，有3≤z ≤

(3)

*

61

14

再分支：由（IP3）的最优解X

⎛33⎫= ,2⎪⎝14⎭

T

，取x 1

=

33⎡33⎤

，根据⎢⎥=2，构造两个约束条14⎣14⎦

max z =x 1+x 2max z =x 1+x 2

⎧14x 1+9x 2≤51⎧14x 1+9x 2≤51⎪⎪-6x +3x ≤12⎪1⎪-6x 1+3x 2≤1⎪x 1≥2⎪x 1≥2

件，形成下面两个子问题（IP7）和（IP8） ⎪⎪

s .. t ⎨x 2≤2s .. t ⎨x 2≤2⎪x ≤2⎪x ≥31⎪⎪1⎪x 1≥0, x 2≥0⎪x 1≥0, x 2≥0⎪⎪x , x 为整数⎩12⎩x 1, x 2为整数

，得（IP7）的最优解为X

(7)

8(8)

=(2, 2), z (7)=4，=(3,1), z ()=4。 （IP8）的最优解为X

T

T

T 78**(7)(8)

重新定界：由于的最优解为X (), X ()为整数解，且z =z =4，故X =(3,1), z =4

max z =3x 1+2x 2

⎧2x 1+3x 2≤14⎪2x +x ≤9

2、对整数规划问题，问用先解相应的线性规划然后凑整的办法能否求到最⎪12

s .. t ⎨

⎪x 1≥0, x 2≥0⎪⎩x 1, x 2为整数

优整数解？

解 用单纯形法解对应的LP 问题，求到最优解x 1当凑为当凑为

=

13559

, x 2=, max z = 424

T

T

(x 1, x 2)(x 1, x 2)

T

=(3, 2)

T

时，为可行解，z

=13；当凑为(x 1, x 2)=(3,3)

时，为非可行解；

T

=(4, 2)

T

时，为非可行解；当凑为

(x 1, x 2)

T

=(4,3)

T

时，为非可行解；

下面用分支定界法来解整数规划问题。令=

59T T

，显然(x 1, x 2)=(0,0)为可行解，从而4

0≤z *≤

59

。将原问题分解为下面两个子问题（用x 2≤2, x 2≥3分支，复杂些，不妨去试试！） 4

max z =3x 1+2x 2max z =3x 1+2x 2

⎧2x 1+3x 2≤14⎧2x 1+3x 2≤14⎪2x +x ≤9⎪2x +x ≤9

（IP1）和（IP2） ⎪12⎪12

s .. t ⎨s .. t ⎨⎪x 1≤3⎪x 1≥4⎪⎪⎩x 1≥0, x 2≥0⎩x 1≥0, x 2≥0

（IP1）的最优解为

(x 1, x 2)

T

T T 43⎛3⎫

和（IP2）的为(x 1, x 2)=(4,1), max z =14 = 3, ⎪,max z =3⎝8⎭

T

因为

=14, =

4343***

，所以14≤z ≤，且z 为整数，则z =14, x 1=4, x 2=1为最优解。 33

max z =3x 1-x 2

⎧3x 1-2x 2≤3⎪5x +4x ≥10

3、用割平面法求解 ⎪12

s .. t ⎨

⎪2x 1+x 2≤5⎪⎩x 1, x 2≥0, x 1, x 2为整数

解 引入松弛变量x 3, x 4, x 5和人工变量x 6及一个充分大的数M >0，先解一个大M 问题：

max z =3x 1-x 2-Mx 6

⎧3x 1-2x 2+x 3=3

⎪5x +4x -x +x =10

⎪1246

s .. t ⎨

⎪2x 1+x 2+x 5=5⎪⎩x 1, x 2, x 3, x 4, x 5, x 6, x 7≥0

略去人工变量，得最终单纯形表

T

再略去松弛变量，最优解为X ()

13930⎛139⎫

，显然不是整数规划的= , ⎪, z (0)=3⨯-=

777⎝77⎭

⎛

⎝

1⎫6⎛2⎫

的x +0x 1+割平面⎪3 ⎪5

7⎭77⎝⎭

最优解。引进以x 1行为源行x 1+ 0612

-x 3-x 5≤0，即x 3+2x 5≥6，再将3x 1-2x 2+x

3=3, 2变x 1+x 2+x 5=5形777

代入得x 3=3-3x 1+2x 2, x 5=5-2x 1-x x 1≤1（该割平面确实割去了松弛问题最优解为

X (0)，但未割去原问题的任一整数可行点。）

引入松弛变量x 6≥0，化-

126126

x 3-x 5≤-为-x 3-x 5+x 6=-写入上表，得

1

T

再略去松弛变量，最优解为X ()

57⎛5⎫

显然仍不是整数规划的最优= 1, ⎪, z (1)=3⨯1-=，

444⎝⎭

⎛

⎝

1⎫1⎫3⎛

的割平面x +x +-1+x =1+⎪45 ⎪6

4⎭44⎝⎭

解。继续作割平面，以x 5行为源行 0+

311

-x 4-x 6≤0，利用四个等式约束即可化为x 1+x 2≥3，（该割平面确实割去了松弛问444

题最优解为X

(1)

，也未割去原问题的任一整数可行解。）

引入松弛变量x 7≥0，化

311113

-x 4-x 6≤0为-x 4-x 6+x 7=-写入上表，

T

**

解得X =(1, 2), z =3⨯1-2=1

max z =x 2

⎧3x 1+2x 2≤6

4、用割平面法求解 ⎪

s .. t ⎨-3x 1+2x 2≤0

⎪x , x ≥0, x , x 为整数⎩1212

解 引入松弛变量x 3, x 4，得到对应LP 问题的初始单纯形表计算如下：

T

*

此时LP 问题的最优解x =(1,3/2), z =3/2，但不是整数最优解。

引入割平面。以x 2为源行x 2+ 0+

⎛

⎝1⎫1⎫1⎛

x +0+x =1+⎪3 ⎪4

4⎭42⎝⎭

111111

⇒x 2-1=-x 3-x 4，所以生成割平面-x 3-x 4≤0，

244244

利用两个等式约束解出x 3, x 4代入即可化为等价割平面x 2≤1 现将生成的割平面条件加入松弛变量-

111

x 3-x 4+s 1=-，然后得到下表 T

*

此时LP 问题的最优解x =(2/3,1, 2), z =1，但仍不是整数最优解。引入割平面。以x 1为

源行x 1+ -1⎪x 4+ 0

⎛

⎝2⎫3⎭⎛⎝

23

⎫⎪s 1⎭

0=

2

+3

x 1

22

-x 332，-s 1所以生成割平面3

222

-x 4-s 1≤0，利用三个等式约束解出s 1, x 4代入即可化为等价割平面x 2-x 1≤0

333

现将生成的割平面条件加入松弛变量-

222

x 4-s 1+s 2=-，然后得到下表

T

*

此时LP 问题的最优解x =(1,1), z =1，是整数最优解，所以是原问题的最优解。

（从解题过程可见，表中含有分数元素且算法过程始终保持对偶可行性，因此这个算法也称为分数对偶割平面算法）

max z =x 1+x 2

⎧2x 1+x 2≤6

5、用割平面法求解 ⎪

s .. t ⎨4x 1+5x 2≤20

⎪x , x ≥0, x , x 为整数⎩1212

解 引入松弛变量x 3, x 4，得到对应LP 问题的初始单纯形表计算如下：

T

*

此时LP 问题的最优解x =(5/3,8/3), z =13/3，但不是整数最

优解。引入割平面。由于x 1+ 0+

⎛⎝5⎫5⎫2⎛

与x +-1+x =1+⎪3 ⎪4

6⎭63⎝⎭

1⎫1⎫2⎛⎛

可任选x 2+ -1+⎪x 3+ 0+⎪x 4=2+的右端的真分数相等，

3⎭3⎭3⎝⎝

（如果不等，根据经验选其中较大的一个式子效果较好）。现在

以x 2为源行⇒x 2-x 3-2=

211211

-x 3-x 4，所以生成割平面-x 3-x 4≤0，利用两333333

个等式约束解出x 3, x 4代入即可化为等价割平面x 1+x 2≤4 现将生成的割平面条件加入松弛变量-

112

x 3-x 4+s 1=-，然后得到下表 T

*

得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解x =(0, 4), z =4*

或x =(2, 2), z =4。

T

max z =3x 1-2x 2+5x 3

⎧x 1+2x 2-x 3≤2⎪x +4x +x ≤4123

6、求解下列0-1规划问题⎪⎪

⎨x 1+x 2≤3⎪4x +x ≤6⎪13⎪⎩x 1, x 2, x 3=0,1

解 用观察法求一个可行解。易看出x 1=1, x 2=x 3=0是一个可行解，对应z =3。由于目标函数求最大，故凡是目标函数值小于这个3的都不必讨论，于是有了一个过滤性条件约束

3x 1-2x 2+5x 3≥3 *

优先考虑过虑性条件*，若遇到Z 值超过过虑性条件右边的值，则应修改过虑性条件，继续

做，列表如下：（最好重排x j 的顺序，使目标函数中x j 的系数保持不减, (x 2, x 1, x 3)为最快！）

用过滤法（隐枚举法的一种）求解过程可以列表简化表示

123

⎧2x 1-5x 2+3x 3≤4⎪

7、求解下列0-1规划问题⎪4x 1+x 2+3x 3≥3

⎨

⎪x 1+x 2≥1⎪⎩x 1, x 2, x 3=0,1

解 用观察法求一个可行解。易看出x 1=x 2=0, x 3=1是一个可行解，对应z =2。由于目标函数求最小，故凡是目标函数值大于这个2的都不必讨论，于是有了一个过滤性条件约束

4x 1+3x 2+2x 3≤2 *

优先考虑过虑性条件*，列表如下：最优解(x 2, x 1, x 3)=(0,0,1)，目标函数最优值

T

T

243x 3+2x 1

⎧x 2+x 4+x 3-4x 1≥0⎪

8、求解下列0-1规划问题⎪4x 2+4x 4+2x 3-2x 1≥4

⎨

⎪x 2+x 4-x 3+x 1≥1⎪⎩x 1, x 2, x 3, x 4=0,1

解 用观察法求一个可行解。易看出x 1=x 2=x 3=0, x 4=1是一个可行解，对应z =4。由于目标函数求最小，故凡是目标函数值大于这个2的都不必讨论，于是有了一个过滤性条件约束5x 2+4x 4+3x 3+2x 1≤4 *

优先考虑过虑性条件*，列表如下：最优解(x 2, x 4, x 3, x 1)=(0,1,0,0)，目标函数最优值

T

T

123-x 4

⎧2x 1-x 2+x 3-x 4≥1⎪

9、求解下列0-1规划问题⎪x 1-x 2+6x 3+4x 4≥6

⎨

⎪5x 1+3x 2+x 4≥5⎪⎩x 1, x 2, x 3, x 4=0,1

解 由于目标函数中变量x 1, x 2, x 4的系数均为负数，可作如下变换，再调整次序：

', x 2=1-x 2', x 3=x 3', x 4=1-x 4'；y 1=x 3', y 2=x 4', y 3=x 1', y 4=x 2' x 1=1-x 1

max z =y 1+y 2+3y 3+7y 4-11⎧y 1+y 2-2y 3+y 4≥1

⎪6y -4y -y +y ≥2⎪1234⎨

⎪y 2+5y 3+3y 4≤4⎪⎩y 1, y 2, y 3, y 4=0,1

，可以从(1,1,1,1)开始试算，y *=(1,1,0,1) 为最优解。

所以x '*=(0,1,1,1) ，进而x *=(1,0,1,0)

min z =10x 1+5x 2+8x 3+4x 4+2x 5

⎧3x 1-2x 2+4x 3-x 4+x 5≥410、求解下列0-1规划问题⎪

⎨-2x 1+x 2-4x 3+x 4-x 5≥-5⎪x , x , x , x , x =0,1⎩12345

解 令y 1=x 5, y 2=x 4, y 3=x 2, y 4=x 3, y 5=x 1，得到下式

min z =2y 1+4y 2+5y 3+8y 4+10y 5⎧y 1-y 2-2y 3+4y 4+3y 5≥4⎪

⎨-y 1+y 2+y 3-4y 4-2y 5≥-5⎪y , y , y , y , y =0,1⎩12345

，计算过程见下表

所以y *=(0,0,0,1,0)为最优解，原问题的最优解为x *=(0,0,1,0,0)

最优解(x 2, x 1, x 3)=(1,0,1), z max =8。由于采用了上述算法，实际只作了20次计算！

T

T

max Z =3x 1+2x 2-5x 3-2x 4+3x 5

⎧x 1+x 2+x 3+2x 4+x 5≤4⎪

11、用隐枚举法求解下列0--1规划问题⎪7x 1+3x 3-4x 4+3x 5≤8

⎨

⎪11x 1-6x 2+3x 4-3x 5≥3⎪⎩x 1, x 2, x 3, x 4, x 5=0,1', x 2=1-x 2', x 5=1-x 5'，将模型化为标准形式如下： 解 令x 1=1-x 1

'-2x 2'-5x 3-2x 4-3x 5'max Z =8-3x 1

'-x 2'+x 3+2x 4-x 5'≤-1? ⎧-x 1

⎪-7x '+3x -4x -3x '≤-2⎪1345⎨

'-6x 2'-3x 4-3x 5'≤-1⎪11x 1

⎪', x 2', x 3, x 4, x 5'=0,1⎩x 1

求解过程如右图所示。

L 1

1213

可行解

'=x 4=x 1'=x 3=0, x 5'=1, Z '=5，由x 2

知最优解x 1=x 2=1, x 4=x 3=x 5=0, Z max =5

12、设有甲乙丙丁四个工人，要指派他们分别完成ABCD 四项工作，每个人做各项工作所

⎛15 19

解 系数矩阵为C =(c ij )=

26 ⎝19⎛15

19

C =(c ij

)=

26 ⎝19⎛0 1B =

10 ⎝2

[**************]1

21221623

[**************]3

24⎫⎪18⎪

⎪19⎪17⎭351464069⎫

⎪

0⎪

=B

⎪3⎪0⎭

1）从系数矩阵的每行元素减去该行的最小元素，得

24⎫-15⎛

⎪

18⎪-18 1

→

⎪19-16 10⎪ 17⎭-17⎝224036406

2）从B 的每列元素减去该列的最小元素，得

9⎫⎛0⎪ 0⎪ 1→⎪ 103

⎪ 0⎭⎝29⎫⎪0⎪

=A ，此时系数矩阵A 的每行每列都有元素0。 ⎪3⎪0⎭

L 43L 51

⎛0 1

第2步：进行试分配，求初始分配方案，得A =

10 ⎝2

0的数目3

24036406

9⎫⎪0⎪ ⎪3⎪0⎭

第3步：寻找覆盖所有零元素的最少直线，以确定最多零元素的个数。得覆盖所有零元素的最小直线数3

第4步：调整a ij ，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小元素θ=1，然后对绿线未覆盖区所有元素减去1，而绿线覆盖区的交叉元素加1，将A 变

()

2302

⎛0 01 为(a ij )= 10 ⎝1610⎫

⎪30⎪

04⎪

⎪50⎭

2302

610⎫

⎪30⎪

04⎪

⎪50⎭

L 34L 85

⎛0 01 再返回第二步。进行试分配，得(a ij =) 10 ⎝1

再进行第三步，寻找覆盖所有零元素的最少直线，得覆盖所有零元素的最小直线数3

1

再进行第4步：调整a ij ，使之增加一些零元素。为此，先找出没有被绿线覆盖的元素中

()

⎛0 012 的最小元素θ=2，然后将(a ij )变为(a ij )= 12 ⎝1⎛0 02 再返回第二步。进行试分配，得(a ij =) 12 ⎝1

0100

0100

410⎫

⎪10⎪

06⎪

⎪30⎭

410⎫

⎪10⎪

⎪06⎪30⎭

*

****

于是已求得最优解x 12=x 21=x 33=x 44=1，其余x ij =0，即甲—B ，乙—A ，丙—C ，丁--D 。

*

目标函数值为z =18⨯1+19⨯1+16⨯1+17⨯1=70。注意：这个问题的最优解不惟一，例如甲—A ，乙—D ，丙—C ，丁—B 也有最优值15+18+16+21=70。 13、设有5项工作ABCDE ，需要分配甲乙丙丁戊五个人去完成，每个人只能完成一项工作，每件工作只能由1人去完成。5个人个人分别完成各项工作所需费用如下表。问如何分配工

解 先将收益矩阵作如下变换

⎛759811⎫-5⎛2 ⎪ 9127119-7 ⎪ 285469⎪-4→ 4(c ij )= ⎪ 73696-3 ⎪ 4 467511⎪-4 0⎝⎭⎝0436⎫⎛2

⎪

5042⎪ 21025⎪→ 4

⎪

0363⎪ 4

2317⎪⎭⎝00424⎫

⎪

5030⎪1012⎪

⎪

0351⎪2305⎪⎭

12

⎛2

21

第2步：进行试分配，求初始分配方案，得(c ij )→ 4

4 0⎝⎛2 24最小直线数4

0424⎫

⎪

5030⎪1012⎪

⎪

0351⎪2305⎪⎭

43

第3步：寻找覆盖所有零元素的最少直线，以确定最多零元素的个数。得覆盖所有零元素的

0424⎫⎪

5030⎪1012⎪

⎪

0351⎪2305⎪⎭

3

451

6

1

第4步：调整c

ij ，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中的最小

()

⎛1 221

元素θ=1，然后将(c ij )变为(c ij )→ 4

3 0⎝031

3⎫

⎪

6

030⎪2013⎪

⎪

0240⎪3305⎪

⎭0313⎫

⎪

6030⎪2013⎪

⎪

0240⎪3305⎪⎭

7

L 3L 1L 5

⎛1

22

再返回第二步。进行试分配，得(c ij )→ 4

3 0⎝

再进行第三步，寻找覆盖所有零元素的最少直线，得覆盖所有零元素的最小直线数4

2

再进行第4步：调整c ij ，使之增加一些零元素。为此，先找出没有被直线覆盖的元素中

()

⎛0 132

的最小元素θ=1，然后将(c ij )变为(c ij )→ 3

2 0⎝⎛0 13

再返回第二步。进行试分配，得(c ij )→ 3

2 0⎝

0303⎫

⎪

6020⎪2003⎪

⎪

0230⎪4406⎪⎭

0303⎫

⎪

6020⎪2003⎪，此时，独立零元素的个数m =5。

⎪

0230⎪4406⎪⎭

*

*****

于是已求得最优解x 12=x 23=x 34=x 45=x 51=1，其余x ij =0。目标函数值为

z *=5⨯1+7⨯1+6⨯1+6⨯1+4⨯1=28。注意，甲乙丙丁四个工人，要指派他们分别完成

⎛0

13

ABCD 这个问题有多个最优解，例如(c ij )→ 3

2 0⎝0303⎫

⎪

6020⎪

2003⎪也是最优解。

⎪

0230⎪4406⎪⎭

14、某地区从电网中分配得到的电力共有6GW ，可用于工业，而该地区有机械、化工、轻

纺、建材四大部类，各部类获得电力以后，可以为该地区提供的利润如下表。问应该如何分

⎛3545

6768 89810

提供的利润为0，即可得到平衡分配问题的利润矩阵(c ij )=

1010911 12111012 13121113⎝

目标函数为max z =

00⎫

⎪00⎪00⎪

⎪ 00⎪00⎪

⎪00⎪⎭

∑∑c x

i =1j =1

66

ij ij

'=M -c ij , i , j =1,2, , n 将目标函数变为极小化，由式c ij

问题min z '=

∑∑(M -c )x =∑∑c 'x , M =13=max {c }，于是有

ij

ij

ij ij

ij

i =1j =1

i =1j =1

6666

8981313⎫⎛2

⎪

6751313⎪ 2

24531313⎪

⎪，先将它变换为(c ij )=

3421313⎪ 1

02311313⎪

⎪ ⎪ 01201313⎭⎝⎛200000⎫ ⎪211033 ⎪ 211055⎪

再进行试分配，得(c ij )= ⎪

111066 ⎪ 011077⎪ 011088⎪⎪⎝⎭

再画线，得最小直线数l =3

⎛10

7 5(c ij )= 3

1 0⎝00000⎫

⎪

11033⎪11055⎪

⎪

11066⎪11077⎪

⎪

11088⎪⎭

L 7

L 1

65

3

00100⎫

⎪

00022⎪

L 1

⎪00044，进而再进行试分配，得⎪

00055⎪00066⎪

⎪

00077⎪⎭00100⎫

⎪

00022⎪00044⎪

⎪，

00055⎪00066⎪

⎪

00077⎪⎭

再画线，得最小直线数l =5

⎛522300⎫ ⎪200000 ⎪ 200022⎪4

θ=2，调整得(c ij )= ⎪，进而再进行试分配，

得

100033 ⎪ 000044⎪ 000055⎪⎪⎝⎭

⎛3

2 22

(c ij )= 1

0 0⎝⎛3 2 22

(c ij )= 1

0 0⎝

9L 8L 7L 6

阵的阶数），故需调的最小元素θ=1，

⎛5 2 24

(c ij )= 1

0 0⎝22300⎫

⎪

00000⎪00022⎪******

=⎪，即得最优解x 16=x 25=x 34=x 4=3x 5=2x 161，其余

00033⎪00044⎪

⎪

00055⎪⎭

*

x ij =0。目标函数值为z *=10⨯1+9⨯1+11⨯1+13⨯1=43。

15、设有5项工作ABCDE ，需要分配甲乙丙丁四个人去完成，由于工作任务数多于人数，故考虑：（1）任务E 必须完成，其它四项任务中可以任选3项完成；（2）其中有一人完成两项其它每人完成一项。四个人分别完成各项工作所需费用如下表。试分别确定最优分配访

设戊完成E 的时间为M ( M为非常大的数) ，其余的假想时间为0 ，建立效率矩阵如下：

用匈牙利法求解过程如下：

⎛25 39 34 24 0⎝29314237⎫25⎛04617

12⎫⎛046177⎫

⎪ ⎪ ⎪

38262033⎪20 191816013⎪ 19181608⎪27284032⎪27→ 701135⎪→ 701130⎪

⎪ ⎪ ⎪

42362345⎪23 11913022⎪ 11913017⎪

0000M ⎪ 0000M ⎪000M ⎪⎭0⎝⎭⎝⎭

⎛046177⎫

⎪19181608 ⎪→ 701130⎪ ⎪11913017 ⎪ 0000M ⎪⎝⎭

L 3

4

⎛002173⎫ ⎪19141204 ⎪→ 1101170⎪ ⎪1159013 ⎪ 4004M ⎪⎝⎭⎛002183⎫ ⎪18131103 ⎪→ 1101180⎪ ⎪0148012 ⎪ 4005M ⎪⎝⎭

12

3

L 1

*

2

*****得最优解x 12=x 24=x 35=x 41=x 53=1，其余x ij =0，即甲—B ，乙—D ，丙—E ，丁—A, ，

*

C 放弃。目标函数值为z =29+20+32+24=105小时。

（2）由于所有任务都必须由甲乙丙丁完成，所以假想的人戊的效率应该对每项工作而言，

*

*****

用用匈牙利法求解，可得最优解x 12=x 24=x 35=x 41=x

23=1，其余x ij =0，最佳分配方

*

案为甲—

B ，乙—C 和D ，丙—E ，丁—A, 。目标函数值为z =29+26+20

+32+24=131

小时。

16、某车间需加工4种零件，它们可由车间的四台机床加工，但第一种零件不能由第三台机床加工，第二种零件不能由第四台机床加工，各机床加工零件的费用如下表。问如何安排加

解 这是一个分配问题，机床不能加工的零件费用记为M (M >>1)，于是费用矩阵成为

⎛5 7 9 ⎝7

5M 423526

2⎫⎪3⎪

，利用求分配问题的匈牙利法，解答过程如下： ⎪M ⎪7⎭

3M -20⎫

⎪

201⎪

02M -3⎪

⎪

047⎭

3M -22

00

↑

⎛3 5 费用矩阵的每行减去该行最小元素，得 6 ⎝5

⎛0 2 上述相对费用矩阵的每列减去该列最小元素，得 3 2⎝

024

0←⎫

⎪1←⎪

M -3⎪

⎪5⎪

⎭

⎫⎪1⎪

M -5←⎪

⎪3←⎪

⎭0←

⎛0 2 用三条直线可以划去所有含零的行和列，需继续迭代 1 0⎝

5M -2400

002

↑

上述相对费用矩阵要用四条直线才能划去含零的行和列，因此可得最优分配表。 由表可知零件1由4号、2由3号、3由2号、4由1号机床加工。 17、一个公司经理要派4个推销员到4个地区去推销某种商品。四个推销员各有不同的经验和能力，从而他们在每一地区能获得的利润不同，其估计值如下表所示。公司经理应怎样分

n

n

，等价于min (-Z )=

n

n

ij

ij

解 由于max Z =

∑∑c x

i =1j =1

ij ij

∑∑(-c )x

i =1j =1

，因而利润矩阵可为

⎛-35 -28 -35 ⎝-24

-27-34-24-32-28-29-32-25

-37⎫

⎪-40⎪

，用求分配问题的匈牙利法，解答过程如下： ⎪-33⎪-28⎭

⎛21090⎫⎛0870⎫⎛0 ⎪ ⎪ [1**********] ⎪ ⎪ 10 01132←⎪⇒ 01134⎪⇒ 0 ⎪ ⎪ 80748076 11 ↑←⎪←⎪⎝↑↑⎭↑⎭⎝⎝

5

180

↑

50⎫

⎪60⎪

04←⎪

⎪79⎪

↑⎭

由表可知推销员1负责1号地区、2负责4号地区、3负责3号地区、4负责2号地区总利润最大，为35+40+32+32=139。 18、某厂为它的一个车间购置了3台不同的新机床。车间有4个可用来安装1台机床的地点，，只是地点2不宜安装机床2。机床安装在不同地点的材料运输是不同的，其单位时间费用估计如下表所示。如何安装这3台机床才能使总费用最小？

0⎛3

2M -13 牙利法解答，得如下矩阵 02 00⎝↑01←⎫

⎪07⎪

51⎪

⎪00←⎪↑⎭

由表可知1机床安装在地点2、2机床安装在地点3、3机床安装在地点1、总费用最小。做

费用为10+13+5=28

19、甲乙丙3人做4项工作，要求安排甲做两项工作，乙丙各做一项工作。如何指派所用时间最小？时间花费见下表：

因为甲做两项工作，所以相当于两个甲，只要系数矩阵多加一行，并变换矩阵如下：

⎛4 4 10 ⎝6732⎫⎛2

⎪

732⎪ 2

⇒

859⎪ 5

⎪

731⎭⎝5

510⎫⎛0

⎪

510⎪ 0

⇒

3304⎪⎪ 3620⎭ ⎝∨210∨⎫⎛0

⎪

210∨⎪ 0

⇒

004⎪ 4

⎪

320⎪ ⎝3∨⎭

100⎫⎛0

⎪

100⎪ 0005⎪ 4

⎪

210⎭⎝3

11020001

0⎫⎪0⎪ 5⎪⎪0⎭

由上面的过程与结果看出：若最后系数矩阵中，有两个或以上行列有两个或以上未考虑的0元素时，则有两个或以上最优解。 若本题要求：甲乙丙都最多可做两项工作，也可以一项也不做的话，则添上两件虚拟的 “事”，

⎛4 4 10

转化为如下的指派问题：

10 6 6⎝73200⎫

⎪

73200⎪85900⎪

⎪，可以验证：甲做AC ，丙做BD ，乙什么

85900⎪73100⎪

⎪

73100⎪⎭

也不做；或甲做AB ，丙做CD ，乙什么也不做。。这样总费时最小，为15单位。

做本题要求考虑到就业问题：甲乙丙个要求做一件或两件事情，而不能无事做，则问题更复杂，可假设一人，其做事所用时间示三个人中最小的，即表中每列的最小值，则转化为如下

⎛4 10

指派问题：

6 ⎝4

78773533

2⎫⎪9⎪

，第四个人做的事，即为表中最小值所在行对应的那个人做的1⎪⎪1⎭

事。此问题最优解有两个：甲做A ，乙做B ，丙做CD ；或甲做AC ，乙做B ，丙做D 。这时总费时16单位比“乙不做事”要多（说明有时充分就业与效率是矛盾的！）。 此外，若某事一定不能由某人做，则可将其相应的费时系数取作足够大的M 即可。