运筹学课件：空中交通系统整数规划

空中交通系统优化与管理

整数规划4.1

整数规划的数学模型及解的特点纯整数线性规划问题：所有

xj

的解为整数混合整数规划问题：部分

xj

的解为整数0-1整数规划问题：所有

xj

的解为0或者14.1.1

模型的一般形式：maxz

CX

X

0 且为整数

AX

bs.t.若线性规划问题xj不取整，则称该线性规划为对应该整数问题的松弛问题，解为整数问题解的松驰解4.1.1

整数规化数学模型的一般形式：4.1.2

整数规化的例子及模型建立：例4.1：某厂用集装箱托运甲、乙两种货物，每个集装箱的体积、积重量、可获利及托运限制如下表所示。问两种货物各托运多少箱可使获得的利润最大？货物体积(米3)重量(百斤)利润(百元)甲5220乙4510托运限制2413解：设x1

，x2分别为甲、乙两种货物托运的箱数。则数学模型为：maxz

20x1

10x2

1 2

x

,

x

0 且为整数

s.t.

2x1

5x2

135x1

4x2

244.1

整数规划的数学模型及解的特点4.1

整数规划的数学模型及解的特点产品A产品B资源限量劳动力84360设

备35200原材料210300利润元/台60804.1.2

整数规化的例子及模型建立：例4.2 设备生产计划问题某设备可以生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如表4-1,问题是如何安排生产计划，使得获利最多?表4-14.1

整数规划的数学模型及解的特点x1

台，B产品x2台maxz

60x1

80x28x1

4x2

3603x1

5x2

2002x1

10x2

300x1

0,x2

0解：建模分析步骤为：1、确定决策变量：设生产A产品2、确定目标函数：3、确定约束条件：人力约束设备约束原材料约束非负性整数约束且取整数4.1.2

整数规化的例子及模型建立：4.1

整数规划的数学模型及解的特点4.1.2

整数规化的例子及模型建立：例4.2

人员安排问题对于一个零售企业的部门经理，需要根据实际情况安排职员的工作时间。根据统计和调查，每天需要在班上工作的职员数目分别为：工作日星期一星期二星期三星期四星期五星期六星期日要求人数20131012161820每个职员要求5天一次轮班，即连续工作5天，然后连续休息2天；正常工作日（星期一~星期五）每个员工每天工资60元，星期六、星期日每人每天工资分别为85元和95元。在满足如上要求的前提下，如何安排每天（星期一~星期日）开始轮班的人数，才能使企业每周所支出的总工资最少，试建立该问题的数学模型。4.1

整数规划的数学模型及解的特点17155 6 74.1.2

整数规化的例子及模型建立：解：设星期一到星期日开始轮班的人数分别为x1、x2、x3、x4、x5、x6、x7，根据分析计算，对应每人每周的工资分别为：300元/人、325元/人、360元/人、360元/人、360元/人、360元/人、335元/人。要求每周支出总工资最小，且满足每天的职员数目要求，即：Min z

300x1

325x2

360(x2

x4

x5

x6)

335x7

x1

x4

x5

x6

x7

20

x

x1

x2

x5

x6

x7

13

x2

x3

x6

x7

10

x

1

x

x2

x3

x4

xx2

x3

x4

x5

x6

x2

x3

x4

x

12

16

18

x3

x4

x

x

x

20x

j

(

j

1,

,

7)为非负整数4.1.2

整数规化的例子及模型建立：例4.3 设备购置问题某个航空公司为了扩大经营规模想购置一批航空维修设备，投资的资金总额为N元，想购买的设备种类为n种分别为A1,

A2,

......,

An，其中设备Ai单价为Pi

(i=1,2,…,n)，现有m个不同的分公司B1,

B2,

......

,

Bm需要安装这些设备，其中Bj公司最多可需要bj台(j=1,2,…,m)。预计将一台设备Ai装置于Bj公司可以盈利cij元，则该航空公司应如何购买安装这些设备，使得航空公司获得的整体利润最大。4.1

整数规划的数学模型及解的特点解：分别设yi为购买设备Ai的台数，xij为将设备Ai装置于Bj公司的台数，z为预计总利润（元）。根据题意得数学规划模型为n mz

cijxiji

1 j

1mnmaxxij

yi

0，

i

1，2，

，ns.t.ijx

b

j，

j

1，2，

，

mijiiji

0，

y

0，

x ，

y

均为整数

j

1

i

1

n

i

1

x

piyi

M4.1

整数规划的数学模型及解的特点4.1.2

整数规化的例子及模型建立：4.1.2

整数规化的例子及模型建立：例4.4 机场选址问题为了实现n个城市间实现航线连接要修建机场，不同城市间的客流量为bj人/天(j=1,2,…,n)，现拟在m个城市中进行选择修建机场，来满足客流量的需求，备选的每个城市最多只能修建一个机场。若选择i城市修建机场，将来的运输能力为ai人/天，固定费用为di元/天(i=1,2,…,m)，已知i城市至j城市运输成本为cij元/人。如何选择机场的位置，能使总的运输成本最低？4.1

整数规划的数学模型及解的特点解：设y

1，若在i城市修建机场i

0，否则xij表示从城市i到城市j的运量（人次/天），m nz表示预计总费用（元/天）mini

1 j

1m

di

yii

1z

cijxijnijmijx

b

j，

j

1，2，

，

ni

0为整数，

y

0或1

j

1

s.t.

i

1

x

ij

x

ai

y

i，

i

1，2，

，

m

根据题意，该问题的数学模型为4.1

整数规划的数学模型及解的特点4.1.2

整数规化的例子及模型建立：解的特点：松驰问题的可行解是凸集，两个可行解的线性组合还是可行解；整数规划问题的可行解是松驰问题可行解的一个子集，两个线性组合不一定是可行解。整数规划的最优解≤其松弛问题的最优解整数规划的解是可数个的，最优解不一定发生在极点4.1

整数规划的数学模型及解的特点松驰问题最优解：

x1*=24/5，x2*=0，z*=96整数问题最优解：

x1*=4，x2*=1，z*=904.1

整数规划的数学模型及解的特点4.1.3

解的特点：整数规划的数学模型及解的特点

4.1.4整数规化的解题方法：

割平面法分枝定界法隐枚举法用割平面法(cutting

plane

approach)解整数规划时，若其松弛问题的最优解x*不满足整数规划条件，则从x*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划、然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则，重复上述步骤，直到获得整数最优解为止。每次增加的线性约束条件应当具备两个基本性质：其一是己获得的不符合整数要求的线性规划最优解不满足该线性约束条件，从而不可能在以后的解中再出现；其二是凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次形成的线性规划可行域中。4.2整数规化的割平面法4.2.1

整数规化的割平面法：

a x

a xm1 1 m

2 2s.t.

a x

a x21 1 22 2

考虑纯整数规划问题：maxz

c1x1

c2x2

cnxna11x1

a12x2

a1nxn

b1

a2

n

xn

b2

amnxn

bmx1

,

x2

,

,

xn

0且为整数

设aij和bi均为整数纯整数规划的松弛问题是一个线性规划问题记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合，则m个约束方程可表示为:对应的最优解为:

X*

[x

*

,

x

*

,...,

x

*

]T1 2 ni

Q,

j

Kj

Kxi

aij

x

j

bij

0j

Qj

K

其中:x

*

b

j若各b

皆j 为整数．是纯整数规划的最优解；•若各 b

j

(

j

Q

)

不全为整数，不是纯整数规划的可行解，自然也不是原整数规划的最优解。4.2.1

整数规化的割平面法：000i0j 0ai,j

x若bi (i

Q)不是整数,

其约束方程为:x

bi i

Q (1)

00i0

,

j i0

,

j i0,

ji0,

j00i0 i0 i0 i0ai,

j

=N

f,

N

ai

,

j且为整数,0

f

1

(2)(3)bi

=N

f ,

N

bi

且为整数,0

f

14.2.1

整数规化的割平面法：0j

K其中:xi

为整数,

bi0

不是整数,

ai0

,

j不一定是整数分解bi0

和ai0

,

j为两部分,一部分为最大的整数,一部分为余下的小数.xi0xi0

Ni

fi0 0(4)

1j

K

j

Kj

K

j

K

j

Kj

KNi

fi0 0

Ni0

,

j

xj

fi0

,

j

xjj

K

Ni0

,

j

xj

fi0

,

j

xjxj

0

fi0

,

j

xj

0

fi0

,

j

x

j

0

fi0

fi0

,

j

xj

fi04.2.1

整数规化的割平面法：（5）式为整数规化的割平面法所要增加的约束

(

fi0

,

j

)xj

fi0j

K0

i0

,

j j而(4)式左边是整数,右边<1,所以有fi

f x

0,即j

K(5)4.2.1

整数规化的割平面法：a) 将现有的有非整解的X*代入，有,和（3）式矛盾，则X*不满足（5）式b) 整数规划模型的整数解一定满足（500

fi

（5）式的实际意义：记R为原松弛问题可行域，R’为新约线性规划可行域。从几何意义上看，(5．10)实际上对R做了一次“切割”，在留下的R’中，保留了整数规划的所有整数可行解，但不符合整数要求的X*被“切割’掉了。随着”切割”过程的不断继续，整数规划最优解最终有机会成为某个线性规划可行域的顶点，作为该线性规划的最优解而被解得。0）式（前提 i

是整数）x00i0 i0 i0 i0bi =N

f ,

N

bi

且为整数,

0

f

1 (3)j

K

(

fi0

,

j

)xj

fi0（5）式的性质：4.2.2

割平面法举例：例：用割平面法求解纯整数规划：maxz

3x1

x21 25x1

4x2

102x1

x2

5

3x

2x

3

s.t.

x1,x2

0 且为整数maxz

3x1

x21 2412

3x1

2x2

x3

3

5x

4x

x

10s.t.

2x

x

x

5

5

x1,x2

0 且为整数解：加入松驰变量化为标准形并用单纯形法解得松驰最优解：Cj3-1000CBXBbx1x2x3x4x53-1x1x213/79/710011/7-2/7002/73/70x431/700-3/7122/7σ00-5/70-3/7由约束的第一行产生割平面约束：3 5 63 5 67 7 71

x

2

x

6

,引入松驰变量x

得:7 7 71

x

2

x

x

6

,

代入单纯形表,用对偶单纯形法解得:Cj3-10000CBXBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x531/700-3/7122/700x6-6/700-1/70-2/71σ00-5/70-3/704.2.2

割平面法举例：Cj3-10000CBXBbx1x2x3x4x5x63-1x1x213/79/710011/7-2/7002/73/7000x431/700-3/7122/700x6-6/700-1/70-2/71σ00-5/70-3/70Cj3-10000CBXBbx1x2x3x4x5x63-1x1x215/41001000-1/4001-5/40x35/2001-1/20-11/20x57/40001/41-3/4σ000-1/40-17/44 6 74 6 74 4 4第四行割平面约束:

1

x

1

x

3

,引入松驰变量x

得:4 4 41

x

1

x

x

3

,

代入单纯形表,用对偶单纯形法解得:Cj3-10000CBXBbx1x2x3x4x5x6x73-1x1x21210010000001-10-10x3400100-5-20x5100001-110x43000101-4σ00000-4-14.2.2

割平面法举例：4.2.3切割平面的几何意义：由原约束：maxz

3x1

x21 2412

3x1

2x2

x3

3

5x

4x

x

10s.t.

2x

x

x

5

5

x1,x2

0 且为整数得：3 1 2

x

3

3x

2x

x5

5

2x1

x2357代入：

1

x7 7

2x

61得： x

1

x4

5x1

4x2

106 31 27 7

x

1

x

12x

x

3 5 67 7 7

1

x

2

x

x

6而：46141434x

x

代入：

得：x1

x2

34.3

整数规划的分枝定界法4.3.1

思路与解题步骤只解松弛问题1、在全部可行域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个

xk=bk

不是整数，令

bk

为

bk

的整数部分构造两个新的约束条件

xk

bk

和

xk

bk

+1，分别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题—

定界过程设两个分枝的松弛问题分别为问题

1

和问题

2

，它们的最优解有如下情况序号问题

1问题

2说 明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题

2

继续分枝4整数解整数解较优的一个为最优解5整数解，

目标函数优于问题

2非整数解问题

1

的解即最优解6整数解非整数解，目标函数优于问题

1问题 1 停止分枝(

剪枝)，

其整数解为界，对问题

2

继续分枝表4.3.1

分枝问题解可能出现的情况情况

2,4,5

找到最优解情况

3在缩减的域上继续分枝定界法情况

6

问题

1

的整数解作为界被保留，用于以后与问题

2的后续分枝所得到的解进行比较，结论如情况

4或5

1 2x

,

x

0

且为整数2x1

x2

74.3.2 分枝定界法举例例4.2.1 max

f

(

x)

6x1

4

x2解：松弛问题的最优解为

x1=2.5,

x2=2,

OBJ=23由

x1=2.5得到两个分枝如下：

问题I1

x1,x2

0 且为整数x

22x1

4x2

132x1

x2

7

问题II1

x1,x2

0 且为整数x

32x1

4x2

132x1

x2

7maxf(x)

6x1

4x2 maxf(x)

6x1

4x2

1 2 3 4 5 6 7x1A(2.5,

2)OBJ:

23C(3,

1)OBJ:

22x2 B(2,

9/4)7 OBJ:

216542x1

4x2

13 321

表4.3.3

分枝问题的松弛解 问题

I问题

IIx123x29/41f(x)2122问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当有很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题4.3.2 分枝定界法举例例：maxZ=40X1+

90X29X1+7X2

567X1+20X2

70X1,X2

0X1

,

X2为整数解：先解(1)的松弛问题X*

=4.8091.817Z*

=355.890，

上界Z*选X1分枝问题(2)(1)X1

4问题(3)(1)X1

5问题(4)(2)X2

2问题(5)(2)X2

3解为X2

=2.1先选(2)继续分枝X1

=4Z=349.0解为X1

=5X2

=1.571Z=341.39(1)S0

=04.8091.817355.890(2)S0

=042.1349.0(3)S0

=051.571341.39(4)S0

=042340(5)3401.4283327.12(6)3405.4441307.76(7)无解X1

4X1

5X2

2X2

1X2

2X2

3分枝定界法一般步骤：、(A),

先解(A)的松弛问题(B)、① (B)无可行解→(A)无可行解。②

(B)最优解符合(A)要求，停。③

(B)最优解不符合(A)要求，转(3)。(3)、估整数解S0

，作下界(4)、选(B)解中不符合整数条件的分量Xj

(Xj=

bj

)分枝，作(B)的后续问题(C)、(D)。(C)：

(B）加约束Xj

[bj](D)：(B)加约束Xj

[bj

]+1(5)、解(C)、(D)剪枝条件：① (C)，[(D)]无可行解② (C)，[(D)]对应的目标值S

S0③

(C)，[(D)]对应的目标值Sc>S0且解为整数解，令Sc

S0且解为非整数解，令(C)，[(D)]取代(B)

返回(4)(6)、全部枝剪完，停优点：(1)、任何模型均可用；(2)、思路简单、灵活；(3)、速度快；(4)、适合上机。4.3.3分枝定界法注意事项：(1)、分枝变量选择原则：① 按目标函数系数：选系数绝对值最大者变量先分。对目标值升降影响最大。② 选与整数值相差最大的非整数变量先分枝。③ 按使用者经验，对各整数变量排定重要性的优先顺序。(2)、分枝节点选择：① 深探法(后进先出法)：最后打开的节点最先选，尽快找到整数解。整数解质量可能不高。② 广探法：选目标函数当前最大值节点，找到的整数解质量高。慢。4.4 0-1规划4.4.1 0-1规划举例0-1型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1，这时xi称为0-1变量，或称二进制变量。可以引入0-1变量的实际问题很多，如相互排斥的计划，相互排斥的约束条件等等。【例4.4.1】(厂址的选定)某公司拟在市东、西、南三区建立门市部，拟议中有7个位置（点），Ai（i=1，2，…，7）可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个；如选用Ai点，设备投资估计为bi元，每年可获利润估计为Ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？

当A点被选用时

0, 当A点未被选用时x

1,i解：引入0-1变量xi,

(i=1,2,

…

,7)则该问题的数学模型可写成：4.4.1 0-1规划举例

i

x

0或1

B

2

1

1(i

1,2,...,7)x4

x5x6

x71

x2

x3

x7max

z

ci

xii

1b

xs.t.

i

17

i i【例4.3.2】(

可用于相互排斥计划中)两种运货方式：火车、船。火车：maxZ=20X1+

10X22X1+5X2

135X1+4X2

24+My7X1+3X2

45+M(1-y

)X1,

X2

0 整数y为0或1 M>04.4.1 0-1规划举例5X

+4X

24

(体积)1 2船：7X

+3X1 2

45

(体积)货物体积(米3)（船）体积(米3)（火车）重量(百斤)利润(百元)甲75220乙34510托运限制452413引入0-1变量y，令当y=0

时采用火车运输y =1

时采用船运输

0-1变量作为逻辑变量(logical

variable)，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。4.4.2 0-1变量及其应用x

1,

当决策方案取P时

0, 当决策不取P时

当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。1x

1, 当Ej选择Aj时(

j

1,

2,

,

n)jT1 n向量(x

,

,

x

) 就描述了问题的特定状态或方案T1 n如(1,1,

,1) 表示(A

,

,

A

)Tn(0,1,

,1) 表示(

A

,

,

A

)

j j

0, 当E

不选择A

时例：

maxZ=12X1

+

12X2

+

9X3

+

15X4

+

90X5+26X6+

112X7(A)3X1

+

4X2

+

3X3

+

3X4

+

15X5

+

13X6+

16X7

35Xj为0或1，(j=1…7)松弛问题(B)为同于(A)约束，目标0

Xj

1(j=1…7)4.4.2

0－1问题的分枝定界法（背包问题)重量价值价/重13124④24123339343155③515906②6132627161127①解:“单位重量价值大的先放”(0)Z=221X7=X5=X4=1(1)219X1=X7=X5=1X1=1 X1=1/3(2)220X7=X5=X4=1X1=0(3)214X2=X7=X5=1X2=1 X2=1/4(4)220X7=X5=X4=1X2=0(5)216X3=X7=X5=1X4=1/3X3=1 X3=1/3(6)219X7=X5=X4=1X6=1/13X3=0(9)217X1=X4=X7=1X5=13/5X4=1(10)217X1=X7=X5=1X2=1/44X4=1/3X

=0(7)174X6=X7=1X5=6/15X6=1(8)217X7=X5=X4=1X6=0(一)、基本思想：maxZ=CX对AX=bX为0或1的2n个可能解，只检查其中一部分例：maxZ=2x1+4x2

+x33x1-8x2+5x3

-1x1,x2,x3为0

,14.4.3

0－1问题的隐枚举法(二)、简单隐枚举法(max)原则：、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0、增加过滤条件Z

Z0(3)、将xi

按ci由小

大排列例：maxZ

=

3x1

-2x2+5x3x1+2x2-x3

2x1+4x2+x3

4①②③④x1

+ x2

34x2+x3

6x1

,

x2

,

x3为0或1解：观察得解(x1

,

x2

,

x3

)=(1

,0

,0)过滤条件：3x1

-

2x2+5x3

3将(x1x2x3)

(x2x1x3

)Z0

=3解(x2

x1

x3

)目标值Z0① ② ③ ④当前最好值(0,0

,0)0<3(0,0

,1)5>5(0,1

,0)3<(0,1

,1)8>8(1,0

,0)-2<(1,0

,1)3<(1,1

,0)1<(1,1

,1)6<最优解

x

=

(1

,0

,1

)T Z=84.5

任务分配问题例4.5.1

有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1

j

1

m

xa xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任务工时人员ABCD人员甲乙丙丁105529843776487551111任务1111任务分配问题的数学模型模型中：xij

为第

i

个工人分配去做第

j

项任务；aij

为第i

个工人为完成第

j

项任务时的工时消耗；

i,j

1,2,

,

m

0 当第i个工人未分配去做第 j项任务{aij}m

m

称为效率矩阵

1 当第i个工人分配去做第 j项任务xij

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1j

1

m

xa

xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任务工时人员ABCD人员甲109781乙58771丙54651丁23451任务1111任务分配问题的数学模型

运输问题是任务分配问题的松弛问题任务分配问题不但是整数规划，而且是0

1规划任务分配问题有2m个约束条件，但有且只有m个非零解，自然是高度退化的任务分配是两部图的匹配问题，有著名的匈牙利算法

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1j

1

m

xa

xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任务工时人员ABCD人员甲109781乙58771丙54651丁23451任务1111

4.4.1匈牙利算法 定理

1 如果从效率矩阵{aij}m

m中每行元素分别减去（或加上）一个常数

ui，从每列元素分别减去（或加上）一个常数

vj

，所得新的效率矩阵{bij}m

m的任务分配问题的最优解等价于原问题的最优解。定理

2 若方阵{aij}m

m中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。4.5.1匈牙利算法匈牙利算法的基本思路：第一步：根据定理

1变换效率矩阵。先对各行元素分别减去本行中的最小元，再对各列元素减去本列最小数点元，使每项行每列中至少有一个零元素，同时不出现负元素。转第二步。第二步：在覆盖变换后的效率矩阵中确定独立零元素。若独立零元素有m个，则已得出最优解；若独立零元数少于m个，则作能覆盖所有零元素的最少直线数目的直线集合，然后转第三步。第三步：继续变换系数矩阵。方法是在未被直线覆盖的元素中找出一个最小元素，对这一最小元素所在行中各元素减去这一值，同时这一行会出现负元素，因此在负元素的列中加上最小元素值。返回第二步。匈牙利算法的举例：例4.5.1第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之7

10 9 78 74 63 4

5

5

25

5

8

行变换第二步：确定独立零元素的个数。若独立零元素有m个，则已得出最优解；若独立零元素少于m个，则作能覆盖所有零元素的最少直线数目的直线集合，然后转步骤3。

2 0 0

3 2 1

1 0 2 01 2

02

列

3变

换

0

3 1

02 0

0 3 2 2

1 0 2 1

1 2

3

匈牙利算法的举例：例4.5.1为了确定独立零元素,

可以在只有一个零元素的行或列中加O,每圈一个0时，把位于同行或同列的元素划去（打上/标记）。1、逐行检查，若该行只有一个未标记的零，对其加O标记，将O标记元素同行同列上其它的零打上/标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；2、逐列检查，若该列只有一个未标记的零，对其加O标记，将O

标记元素同行同列上其它的零打上/

标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；

13 2 0 0

3 2 1

0 2 0

1 2

02

逐行检

查

0

1

03 2 0 03 2 1

0 2 0

1 2 2

逐列检

查

0匈牙利算法的举例：例4.5.13、重复1、2后，直至所有的零被打上O标记或/标记。若O标记的个数为4个，则已找到最优解，否则需确定能覆盖所有零元的最少直线数。4、打破僵局。当某些行（或列）剩下未标记的零元的数量都大于1时，选未标记零元对应个数最少的行（或列）先标记O

。2 0 0

3 20 21 21

1逐行

3逐列

0

0

02

检查

3 20 21 2

3 2 0 0

01

1

0

02

匈牙利算法的举例：例4.5.1划线过程：对没有标记O

的行打

对打

行上所有带/零元素对应的列打

再对打

列上有O标记的零元素对应的行打

重复b

和c

，直至无法继续对没有打

的行划横线，对所有打

的列划垂线

3

023020

1

1

001220

2

然后转到第三步；

匈牙利算法的举例：例4.5.1第三步：进一步变换；在未划线的元素中找最小者，设为

对未被直线覆盖的行（或列）各元素减去

对出现负元素的行（或列）加上

4 2 0 0

2 1 0

0 2 0

0 1

01

第一列+1

0d.

回到第二步；重新标记；

1

3 2 0 0

2 1 0

0 2 0

2

1 0 1 1

1

1以上步骤实际上仍是利用定理

11 2

3 2 0 0

0 3 2 1

1 0 2 0

02

匈牙利算法的举例：例4.5.1回到第二步；重新标记；逐行检列

1

查

2

查

检

1

0

00

20 2 1 0 0 2 1 00 2 0

2 0 2 0

0 1 0 1

4 2 0 0

4 2 0 0

逐

10

2

4 2 0 0

0 2 1 0

0 2

0 0 1 1

4 2 0 0

0 2 1 0

0 20 0 1

打破僵局

答：最优分配方案为x =x =x =

x13 21 34 42=1，其余为0，即甲

C，乙

A，丙

D，丁

B，OBJ=204.4

.2 一般的指派问题

9

2 15 13 4

10 4 14 15

9 14 16 13

7 8 11最大化指派问题: C

最大化指派问题—用矩阵中最大元素的值减去所有元素的值，对新的矩阵求最小化指派问题的解，其解等于原矩阵最大化指派问题的解。

7

916

9

16

13

7 2 0 3

8 516

1616

1116

1416

8

16

9

16

7

16

216

1516

1316

4

1413

16

1016

416

1416

15

6122B

化为最小化指派问题，其解与最大化指派问题的解相等：12

1

一般的指派问题人数和事数不等的指派问题若人少事多，则增加虚拟的人，做各事费用系数可取为0，理解为这些费用不会发生。若事少人多，则增加虚拟的事，每人做此事费用系数也取为0，理解为这些费用不会发生。一个人可做几件事–将该人化做相同的几个人来接受指派，这几个人做相同的事费用是一样的。当某事一定不能由某人做–将此人做此事的费用取为足够大的正数M。4.5 枢纽机场的确定问题中枢辐射航线网络的特点:非枢纽机场之间的客源通过枢纽机场中转来体现规模经济效应。机场的选择是航空公司长期的战略决策。取消已有的枢纽机场或者增加新的枢纽机场都要消耗航空公司大量的时间和费用,而对非枢纽机场与枢纽机场连接的改变,航空公司的花费相对较少,更具有可行性。航空公司筹建中枢辐射航线网络,在一些备选机场中选择几个机场作为自己中枢辐射航线网络的枢纽。枢纽机场选择的问题描述如下所述：从n个备选机场中选择p个机场(p一般不会很大)作为枢纽,对于每个机场,航空公司的收益部门通过一系列的指标如市场预测、自身所占的份额以及建设枢纽机场所需的前期投入等,得到该机场作为枢纽能给航空公司带来的效益值,然后选择p个使总效益最大的机场作为自己的枢纽。4.5 枢纽机场的确定问题枢纽机场的确定问题可以用0-1整数规划问题来加以分析解决。枢纽机场的确定相当于集覆盖问题，主要是将一个集合的每一个元素指派给另一个集合的某个元素或与另一个集合的某个元素配对，比如机组与航班配对、飞机分配到航线上。集覆盖问题的目标就是寻求配对成本的最小化。4.5.1

枢纽机场确定案例分析

例如某航空公司要建立一个“枢纽”式航线网络的机场，该机场要把其方圆1000英里以内的城市衔接起来，这个航空公司要开辟到下列城市的航班：亚特兰大、波士顿、芝加哥、丹麦、休斯顿、洛杉矶、新奥尔良、纽约、匹兹堡、盐湖城、旧金山和西雅图。该航空公司想要知道覆盖所有这些城市最少需要建立几个航空枢纽，条件是每个城市到最近一个航空枢纽的距离不能超过1000英里。表4-5列出了这些城市间的距离。亚特兰大、波士顿、芝加哥、丹佛、休斯顿、洛杉矶、新奥尔良、纽约、匹兹堡、盐湖城、旧金山和西雅图ATBOCHDEHOLANONYPISLSFSEAT0103767413987892182479841687187824962618BO1037010051949180429791507222574234330952976CH67410050100810672054912802452139021422013DE13981949100801019105912731771141150412351307HO7891804106710190153835616081313143819122274LA2182297920541059153801883278624267153791131NO479150791212733561883013111070173822492574NY8412228021771160827861311036821822934