1、第六章第六章 整数规划整数规划Integer Programming6-1 整数规划模型整数规划模型6-2 分枝定界法分枝定界法6-3 割平面法割平面法6-4 0-1规划规划6-5 指派问题指派问题6-6 整数规划的计算机解法整数规划的计算机解法6-7 IP的应用及案例分析的应用及案例分析6-1 整数规划模型整数规划模型（Model of Integer Programming）v在线性规划与非线性规划模型中，变量的取值是在实数范围或在正实数范围。v但是，在很多管理与经济活动中，要求所探讨的问题变量只能取整数值或取整数值中的一部分。如人数、机器台数、投资项目个数等，这时的非整数解就没有意义。v
2、如果一个规划模型中的变量有整数要求，则该规划模型就是整数规划模型。v整数规划模型包括：整数规划、0-1规划、混合规划 三种类型。例如 1.变量是人数、机器设备台数或产品件数等都要求是整数 2.对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资；3.人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。2022年7月29日11时42分Page 2 of 72 6-1 整数规划模型（整数规划模型（Model of Inter Programming）1.纯整数规划模型及其解
3、的分析求解整数解的线性规划问题，通常人们首先想到的是先不管整数条件的限制，直接使用单纯形法求解，然后将所得到的非整数解经四舍五入化为整数。但是这种办法往往是行不通的，这是因为由舍入化整所得的整数解不一定是可行解，即便是可行解，也不一定是最优解。【例6-1】整数规划问题 取取非非负负整整数数2112121xx2x20 x10 xx5xwmax 0 2 1 1 2 1x 2x 21x 201021xx （2，1.8）图6-12022年7月29日11时42分Page 3 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）如果先不考虑决策变量 的
4、整数限制，无论是用图解法还是用单纯形法都可很容易地求得最优解为：，。这里也很容易验证：21,xx8.1,221xx11w（1）如果按四舍五入将非整数解 化为整数，应取 ，而 不是可行解；8.12x22x2,221xx（2）如果把 的小数部分0.8舍去，取 ，它虽是可行解，但不是最优解，这是因为 ，而 ，且（0，2）也是可行解。2x1,221xx7)1,2(w10)2,0(wn由此可见，用凑整数法解整数规划是不可取的。目前，解整数规划问题通常采用的方法是分支定界法和割平面法。不过割平面法通常用于手工解法，适应于一些小型的问题，对于较大的整数规划问题一般采用分支定界法用计算机来求解，特别是对于那些
5、只要求部分决策变量是整数的规划问题，分支定界法尤为方便。1.纯整数规划模型及其解的分析(续）2022年7月29日11时42分Page 4 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）【例例6-2】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表61所示。问两种物品各装多少件，所装物品的总价值最大？物品 重量（公斤/每件）体积（m3/每件）价值(元/每件)甲乙1.20.80.0020.002543表61【解解】设甲、乙两种物品各装x1、x2件，则数学模型为：且均取整数,.m
6、ax0 xx25x52x210 x80 x21x3x4Z21212121(6.1)1.纯整数规划模型及其解的分析2022年7月29日11时42分Page 5 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）如果不考虑x1、x2取整数的约束，线性规划的可行域如图6-2中的阴影部分所示。2022年7月29日11时42分Page 6 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）v用图解法求得点B为最优解：X(3.57，7.14)，Z35.7。由于x1，x2必须取整数值，实际上整数规
7、划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33,并非最优。实际上问题的最优解是（5，5），Z=35。即两种物品各装5件，总价值35元。v由图6-2知，点（5，5）不是可行域的顶点，直接用图解法或单纯形法都无法求出整数规划问题的最优解，因此求解整数规划问题的最优解需要采用其它特殊方法。v还有些问题用线性规划数学模型无法描述，但可以通过设置逻辑变量建立起整数规划的数学模型。2022年7月29日11时42分Page 7 of 72 6-1 整数规划模型（整数规划模型（Mode
8、l of Integer Programming）2.0-1规划问题n当进一步限定线性规划问题中的决策变量只取0、1两个值时，就构成了一类特殊的整数规划0-1整数规划。这时的决策变量称为0-1变量。在实际问题中，有些问题往往只需回答“是”或“否”，问题就算解决了。描述这类问题的变量只需要取两个值就可以了。如果问题的变量不是仅取0和1，而是可取其它某个范围的非负整数，则也可以利用二进制的记数法将它用若干个0-1变量来代替，从而将其化为0-1整数规划。v引入0-1变量的实际问题 1)投资场所的选定：有n个投资场所，对每一投资场所的投资有一定限额与一定的收益，而根据一些限制的条件，只能对其中某些投资
9、场所投资，问如何从n个投资场所中选择出m个场所（在一定约束条件下），使投资收益最大2022年7月29日11时42分Page 8 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）mibxaxaxaininii,.,2,1,.2211mimyyyMybxaxaxamiininii,2,11.2122112)相互排斥的约束条件 为了使m个互相排斥的约束条件：中只有一个起作用，可以引入m个0-1变量yi（i=1m）和一个充分大的正数M，用下面这一组m+1个方程来表示这m个相互排斥的约束条件。2022年7月29日11时42分Page 9 of 7
10、2 6-1 整数规划模型（整数规划模型（Model of Integer Programming）v【例【例6-3】在例6-2中，假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型，使所装物品价值最大。1)所装物品不变；2)如果选择旅行箱，载重量和体积的约束为解：此问题可以建立两个整数规划模型，但用一个模型描述更简单。引入01变量（或称逻辑变量）yi，令2,10,1iiiyi种方式装载时不采用第，种方式装载时采用第i=1,2分别是采用背包及旅行箱装载。且均取整数,.0 xx20 x52x212x80 x21212121202
11、2年7月29日11时42分Page 10 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）由于所装物品不变，式(6.1)约束左边不变，整数规划数学模型为：21i10y0 x1yyy20y25x52x2y12y10 x80 x21x3x4Zii212121212121,.max或且取整数2022年7月29日11时42分Page 11 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）【例例6-4】企业计划生产2000件某种产品，该种产品可利用、设备中的任意一种加工。已知每种设备的生产
12、准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。设备生产准备结束费（元）生产成本（元件）限定最大加工数（件）2022年7月29日11时42分Page 12 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）【解】设【解】设xj表示在第j（j=1,2,3）种设备上加工的产品数量，其生产费用为：)()()(0 x00 xxcKxCjjjjjjj式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设01变量yj，令时种设备上加工，即不在第时种设备上加工，即当在第0
13、 xj00 xj1yjjj目标函数为：)()()(min332211x5y200 x2y300 x10y100Z2022年7月29日11时42分Page 13 of 72 6-1 整数规划模型（整数规划模型（Model of Integer Programming）321j01y0 x1200 x800 x600 x2000 xxx321jMyxjj321321jj,，或用QSB软件求解得到：X（0，800，1200），Y（0，1，1），Z=8100.如果问题的所有变量取0或1，此问题称为01整数规划问题，简称01规划。式中 是一个特殊的约束条件，显然当xj0时，yj=1,当xj0时，为使Z极
14、小化，只有yj=0才有意义。jjMyx2022年7月29日11时42分Page 14 of 72 6-2 分枝定界法分枝定界法v由于整数规划是在原线性规划模型的基础上加上整数条件，因此，整数规划的可行域必在原线性规划问题的可行域之中，因而整数规划问题的最优解不会超过对应的线性规划问题的最优解。所以，任何有界整数规划问题仅有有限个整数可行解。分枝定界法的步骤：1.求整数规划的松弛问题（对应LP模型）最优解；3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小
15、值时，目标值是分枝问题的下界；4.检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；2022年7月29日11时42分Page 15 of 72 6-2 分枝定界法分枝定界法解：先不考虑整数条件，用图解法或单纯形法可求得相应的线性规划的最优解为：是非负整数：求解整数规划例21212121xx36x8x324x3x4tsx9x6z56,.max1.50max,1
16、.32372,65.3238421zxx 6 4 2 2x 0 3 1x 6 9 12 8 B A C R 243421 xx 368321 xx zxx2196 2022年7月29日11时42分Page 16 of 72 6-2 分枝定界法分枝定界法v随着原整数规划被分为两枝（）和（），原整数规划的可行域R也被分为两个可行域R1和R2（见下图）C 4 6 4 2 2x 0 3 1x 6 9 12 8 B A D R1 R2 由于最优解的两个变量都是非整数，因此可任对其中一个进行分枝，例如对变量将原整数规划分解为如下两个整数规划：取整数取整数2112121xx3x36x8x324x3x4,).
17、(2196maxxxz 取整数取整数2112121xx4x36x8x324x3x4,).(2196maxxxz2022年7月29日11时42分Page 17 of 72 6-2 分枝定界法分枝定界法v同样，先不考虑整数条件，分别解出与（）和（）相应的线性规划，得到最优解如下表 C 4 6 4 2 2x 0 3 1x 6 9 12 8 3 A D R1 R2 线性规划（）线性规划（）4.48375.3827321zxx48667.238421zxx 取整数取整数212121211xx3x3x36x8x324x3x4,)(2196maxxxz 取取整整数数）（212121212xx4x3x36x8
18、x324x3x4,2196maxxxzn由于这两个解都不是整数解，所以还必须将（）和（）继续进行分枝、求解。先将（）对变量x2分为两枝如下，其可行域如图所示。2022年7月29日11时42分Page 18 of 72 6-2 分枝定界法分枝定界法v先不考虑整数条件，分别求得（1）和（2）的最优解如表 v问题（1）已是整数解，问题（2）虽非整数解，但其整数解不会超过其当前最优解44，更不会超过（1）的当前目标函数值45，所以就没有必要再对（2）进行分枝求解了。v由于（）的目标函数值Z=48大于（1）的目标函数值45，所以（）的整数解目标函数值仍可能大于45，所以，还必须对（）继续分枝求解。线性规
19、划（1）线性规划（2）453321zxx4443421zxx2196maxxxz2196maxxxz 取整数取整数212121211xx2x4x36x8x324x3x4,)(取整数取整数212121212xx3x4x36x8x324x3x4,)(2022年7月29日11时42分Page 19 of 72 6-2 分枝定界法分枝定界法v在不考虑整数条件下，不难求得结果如表 v由此结果看出，线性规划（1）的最优解虽不是整数解，但它的最优整数解的目标函数值不会超过（1）的整数解目标函数值Z=45，而线性规划（2）无解。因此，整数规划（1）的最优解就是原整数规划的最优解，其目标函数值为Z=45。线性规
20、划（1）线性规划（2）无解4525.421zxx2022年7月29日11时42分Page 20 of 72【例【例6-6】用分枝定界法求解例6.2【解】【解】先求对应的松弛问题（记为LP0）：0,255.22108.02.1:034max21212121xxxxxxLPxxZ用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。且均取整数,0,255.22108.02.134max21212121xxxxxxxxZ6-2 分枝定界法分枝定界法2022年7月29日11时42分Page 21 of 72 1010108.02.121xx255.2221xx松弛问题LP0的最优解X
21、=(3.57,7.14),Z0=35.7x1x2oABC1010 x1x2oABC0,3255.22108.02.1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.50,4255.22108.02.1:234max211212121xxxxxxxLPxxZ得到两个线性规划及增加约束4311xx1010 x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.330,64255.22108.02.1:334max2121212121xxxxxxxxLPxxZ，不可行，得到线
22、性规划，显然及进行分枝，增加约束选择目标值最大的分枝7762222xxxLP6不可行72x1010 x1x2oACLP134可行域是一条线段即，,40,464255.22108.02.1:434max121121212121xxxxxxxxxxLPxxZ：及，到线性规划及进行分枝，增加约束，选择由于545431113LPLPxxLPZZ60,65255.22108.02.1:534max2121212121xxxxxxxxLPxxZ，LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP3 尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。上述
23、分枝过程可用下图表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP3:X=(4.33,6)Z3=35.33x26LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x14x15无可行解x276-3 割平面法割平面法v解法思想：割平面法的基本思想仍然是用解线性规划问题的方法去解整数规划问题，就如同分枝定界法，它仍然是在相应线性规划可行域的边界附近寻找整数解点，所不同的是割平面法不是分割可行域，而是象削土豆皮一样，一层一层地将可行域边界附近的非整数解部分削去，从而使整数解点逐渐暴露在新
24、可行域的边界上。首先不考虑整数条件，解线性规划问题，若得整数解即为所求，若有非整数解，则增加线性约束条件（即割平面法），使得由原可行域中切割掉一部分，切掉的这部分只包含非整数解，而没有切割掉任何整数可行解。这个方法的核心就是指出怎样找到适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。2022年7月29日11时42分Page 27 of 72 设纯整数规划njxbxaxcZjinjjijnjjj,10max11且为整数，松弛问题njxbxaxcZjinjjijnjjj,10max11，的最优解TmTbbbbBbbBX),()0,(2111若xi不为整数，为
25、非基变量kkkikiixxabx6-3 割平面法割平面法2022年7月29日11时42分Page 28 of 72 将 分离成一个整数与一个非负真分数之和：ikiab及 10,10,ikiikikikiiifffaafbb则有kkikkkijiiixfxafbxkkikikkijiixffxabx等式两边都为整数并且有1ikkikifxff6-3 割平面法割平面法2022年7月29日11时42分Page 29 of 72 加入松弛变量si得ikkikifxfs此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。将Gomory约束加入到松弛问题的最优
26、表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。0kkikixff则6-3 割平面法割平面法2022年7月29日11时42分Page 30 of 72 324313322354613651xxxxxx例如，3246536511)1(xxxx1行：移项：46536532411xxxx令046536532xx加入松弛变量s1得324653651xxs同理，对于x2行有：324313312xxs6-3 割平面法割平面法2022年7月29日11时42分Page 31 of 72【例6-7】已知整数规划且为整数0,92143223max21212121xxxxxxxxz【
27、解】不考虑整数约束，松弛问题的最优表如下6-3 割平面法割平面法2022年7月29日11时42分Page 32 of 72 cj3200bCBXBx1x2x3x42x2011/21/25/23x1101/43/413/4j001/45/4最优表最优解X=(1/2，3/4，0，0)T，x1、x2不满足整数要求，选择x2行进行分割：254213212xxx21421432122xxxx214213215xxx得到Gomory约束添加到最优表中，得6-3 割平面法割平面法2022年7月29日11时42分Page 33 of 72 cj32000bCBXBx1x2x3x4x52x2011/21/205
28、/23x1101/43/4013/40 x5001/21/211/2j001/45/402x2010123x110011/27/20 x3001121j00011/2x1行：2752141xxxGomory约束215216xx添加到最优表中，得6-3 割平面法割平面法2022年7月29日11时42分Page 34 of 72 cj320000bCBXBx1x2x3x4x5x62x20101023x110011/407/30 x300111010 x600001/211/2j00011/202x201010213x110010140 x300110430 x60000121j0001016-3
29、割平面法割平面法2022年7月29日11时42分Page 35 of 72 得到整数最优解：X(4，1)，Z14注1：254213212xxx1435xxx042132121xxGomory约束可写为注2：Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。用图解法表示：6-3 割平面法割平面法2022年7月29日11时42分Page 36 of 72 13/4,5/2松弛问题第一次切割112221 xx4,1第二次切割x1+x256-3 割平面法割平面法2022年7月29日11时42分Page 37 of 72 6-3 割平面法割平面法v利用最终单纯形表求割平面方程的基本步骤：
30、1)从最终单纯形表中引出诱导方程。为非整数为非基变量，为基变量，其中：ikikikikibxxbxax2)将 、都分解成整数部分N与非负真分数f之和。ikaibikikikfNa10ikfiiifNb10if所以上述式变为：kkikiikkikixffNxNx3)现在提出整数条件，即所有变量均为整数。可见式左边为整数，因而其右端也就必为整数。必有：0 xffkikiki此即所求割平面方程。2022年7月29日11时42分Page 38 of 72 6-3 割平面法割平面法4)给割平面方程加入非负松弛变量S得到 ikikikfsxf然后以S为基变量把此方程填入最终计算表继续迭代，重复以上过程，直
31、到得到整数最优解。注意：1.不论诱导方程中的 符号如何，在填入最终表的割平面方程中，所有非基变量的系数及右端项的取值一定是负的真分数（变量系数可为零）。ika2.的取值：当 为正时，直接取其小数部分；当 为负时，取其小数部分的关于1的补数。ikfikaika根据以上两条，就可以直接根据最终单纯形表中非整数解行中的数据写出割平面方程，加入到最终单纯形表中。2022年7月29日11时42分Page 39 of 72 作业：教材P134 T5.3 1.领会割平面法的基本原理1.分离源行，求出Gomory约束2.在最优表中增加Gomory约束，用 对偶单纯形法迭代6-3 割平面法割平面法2022年7月
32、29日11时42分Page 40 of 72 6-4 0-1规划规划v0-1规划求解思想0-1整数规划的常用解法有：枚举法（穷举法），隐枚举法 枚举法就是对于各种可能情况的组合及结果一一列出。对于有n个变量的0-1规划用枚举法，需计算2n种组合情况下的目标值，并进行大小比较，选其最大值所对应的方案作为最优解。显然当n较大时，这种方法几乎是不可能的。隐枚举法：先试探一个解，根据此解，以目标函数方程及其取值作为增加的约束条件称之为过滤约束条件。当求解优于当前最优值的时候，则修改这一过滤条件的右端常数项的取值。下面举例说明一种解0-1型整数规划的隐枚举法 2022年7月29日11时42分Page 4
33、1 of 72 6-4 0-1规划规划v解：先用试探的方法找出一个可行解：相应的目标函数值 。对于极大化问题，当然希望 ，为此，增加过滤约束条件：此过滤约束就是原目标函数按变量系数从小到大重新排列后的结果。下面以表格的形式来描述并记录隐枚举的过程：321523maxxxxz).(.12xx2x321 ).(.24xx4x321 )(.33xx21 ).(.46xx432 )(.,510 xxx321或或)0,0,1(),(321xxx3z3z .3x5x3x2312【例6-8】2022年7月29日11时42分Page 42 of 72 6-4 0-1规划规划v于是求得最优解：Z值（0，0，0）
34、0（0，0，1）5-11015（0，1，0）3（0，1，1）802118（1，0，0）-2（1，0，1）3（1，1，0）1（1，1，1）6点约束条件满足约束条件？),(312xxx),(),(110 xxx312 8maxz2022年7月29日11时42分Page 43 of 72【例【例6-9】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表63所示，如何安排他们的工作使总成绩最好。表63 工作人员ABCD甲85927390乙95877895丙82837990丁869080886-5 指派问题指派问题2022年7月29日11时
35、42分Page 44 of 72 【解【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！432124种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用01规划模型求解此类分配问题显得非常简单。设 工作时人做不分配第工作时人做分配第jijixij01数学模型如下：目标函数为要求每人做一项工作，约束条件为：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ6-5 指派问题指派问题2022年7月29日11时42分Pag
36、e 45 of 72 111144434241343332312423222114131211xxxxxxxxxxxxxxxx每项工作只能安排一人，约束条件为：111144342414433323134232221241312111xxxxxxxxxxxxxxxx变量约束：4,3,2,110jixij、，或6-5 指派问题指派问题2022年7月29日11时42分Page 46 of 72 求解例6-9指派问题的方法：匈牙利算法匈牙利算法匈牙利算法是匈牙利数学家克尼格（Konig）证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于这两个定理基础上建立起来的解分配问题的计算方法被称为匈牙
37、利法。假设问题求最小值，m个人恰好做m项工作，第i个人做第j项工作的效率为cij，效率矩阵为cij。【定理定理6.1】如果从分配问题效率矩阵cij的每一行元素中分别减去（或加上）一个常数ui（被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵bij，若其中bij=cijuivj,则bij的最优解等价于cij的最优解。这里cij、bij均非负。6-5 指派问题指派问题2022年7月29日11时42分Page 47 of 72【定理【定理6.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（
38、称为独立元素）的最大个数。如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，得到最优解。定理6.1告诉我们如何将效率表中的元素转换为有零元素，定理6.2告诉我们效率表中有多少个独立的“0”元素。【例【例6-10】已知四人分别完成四项工作所需时间如下表，求最优分配方案。88809086907983829578879590739285C6-5 指派问题指派问题2022年7月29日11时42分Page 48 of 72【解解】最优分配方案是怎样安排四人的工作，使得完成工作总时间最少，是求最小值问题。第一步：找出效率矩阵每行的最小元素，并分别从每行中减去
39、最 小元素，有：80106110431709171701912Min 3 4 0 8第二步：找出矩阵每列的最小元素，再分别从每列中减去，有：0063300090514901598079787388809086907983829578879590739285Min6-5 指派问题指派问题2022年7月29日11时42分Page 49 of 72 第三步：用最少的直线覆盖所有“0”，得：006330009051490159第四步：这里直线数等于3（等于4时停止 运算），要进行下一轮计算。（1）从矩阵未被直线覆盖的数字中找出一个最小的数k，表中k3。(2)直线相交处的元素加上k，未被直线覆盖的元素减
40、去k，被直线覆盖而没有相交的元素不变，得到下列矩阵0030630090211901266-5 指派问题指派问题2022年7月29日11时42分Page 50 of 72 回到第三步:用最少的直线覆盖所有“0”，得003063009021190126未被直线覆盖元素中最小元素k=2,直线相交处的元素加上2，未被直线覆盖的元素减去2，被直线覆盖而没有相交的元素不变，得到下列矩阵023065007009701046-5 指派问题指派问题2022年7月29日11时42分Page 51 of 72 02306500700970104画线画线，最少直线数等于最少直线数等于4。第五步：最优分配第五步：最优分
41、配02306500700970104最优解：最优解：1111X最优值最优值Z7387828833088809086907983829578879590739285C6-5 指派问题指派问题2022年7月29日11时42分Page 52 of 72 不平衡的指派问题不平衡的指派问题当人数m大于工作数n时，加上mn项工作，例如：123546171483611109500000000001235461714836111095当人数m小于工作数n时，加上nm个人，例如：1716131074569102015000017161310745691020156-5 指派问题指派问题2022年7月29日11时
42、42分Page 53 of 72 求最大值的指派问题求最大值的指派问题匈牙利法的条件是：模型求最小值、效率cij0令)(max,ijijjicMCcM则ijijijxcwminijijijxczmax与的最优解相同。设C=(cij)mm 对应的模型是求最大值将其变换为求最小值ijijijxczmax6-5 指派问题指派问题2022年7月29日11时42分Page 54 of 72【例例6-11】某人事部门拟招聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最多。88809086907983829578879590739285丁丙乙甲C【解】【解】M95，令，
43、令)95(ijcC71559516121301780522310C6-5 指派问题指派问题2022年7月29日11时42分Page 55 of 72 21004011780178021907C用匈牙利法求解：71559516121301780522310C2004017807802907C1111X最优解：最优解：即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项。总分为：总分为：Z929590803576-5 指派问题指派问题2022年7月29日11时42分Page 56 of 72 本章介绍了整数规划的数学模型的特征及其应用；1整数规划的最优解是先求相应的线性规划的最优解然 后取整得
44、到.2部分变量要求是整数的规划问题称为纯整数规划.3求最大值问题的目标函数值是各分枝函数值的上界.4求最小值问题的目标函数值是各分枝函数值的下界.5变量取0或1的规划是整数规划.求解方法有：解一般整数规划用分枝定界法、割平面法；解01规划用隐枚举法；解指派问题用匈牙利法。试一试，下例结论是否正确：6-5 指派问题指派问题2022年7月29日11时42分Page 57 of 72 6整数规划的可行解集合是离散型集合.7将指派（分配）问题的效率矩阵每行分别加上一个数后 最优解 不变.8匈牙利法求解指派问题的条件是效率矩阵的元素非负.9匈牙利法可直接求解极大化的指派问题.10高莫雷（R.E.Gomo
45、ry）约束是将可行域中一部分非整 数解切割掉.11指派问题也是一个特殊的运输问题.12指派问题也可用运输问题求其最优解.13在用隐枚举求解具有n个变量的0-1规划时需枚举2的n次 幂个可能.作业：教材作业：教材P135 T5.7The End of Chapter 5 6-5 指派问题指派问题2022年7月29日11时42分Page 58 of 72 6-6 整数规划的计算机求解整数规划的计算机求解1.整数规划计算机求解的困难性分析整数规划的求解一般要比线性规划困难的多；整数规划求解的难以程度取决于其本身的结构；整数规划求解软件随其能解决模型的规模大小（决策变量的多少和约数的多少），价格上有很
46、大的差别；一般而言，二元优化的求解要比非负整数求解简单，非负整数求解要比混合整数求解简单。2.用Excel电子表格软件求解整数规划的步骤：1)将规划模型格式化为电子表格文件。同线性规划一样，将模型的决策变量单元、目标函数单元、约束左端右端单元放在合适的位置；2)从工具菜单中选择规划求解，在求解窗口中输入目标函数单元格、决策变量单元格以及约束的左端项和右端项的单元个；2022年7月29日11时42分Page 59 of 72 6-6 整数规划的计算机求解整数规划的计算机求解3)对于非负整数和二元决策变量要在规划参数窗口中作为约束项加入；进入添加约束窗口中，输入要求非负整数或二元的决策变量单元格，
47、在约束符号栏中选择“非负整数”或“二元”，重复上述过程，加入所有要求；4)点击选项进入参数选择窗口，确保“假定线性模型”复选框被选中，如果所有变量非负，则选定“假定非复”复选框。同时根据需要可以对求解时限、迭代次数、求解精度等项做出调整，但一般情况下用其默认值即可。5)点击求解按钮，进入求解选项框，根据需要选定相应项。vExcel求解实例见教材例9-4（P.351)，参考Excel文件整数型规划例1。2022年7月29日11时42分Page 60 of 72 6-6 整数规划的计算机求解整数规划的计算机求解v另外，不同的偏差参数对最优解也会产生一定的影响，如下表是对上例在不同的偏差要求下得到的
48、结果。偏差A1A2A4A6总利润（$千）5%81711131821%8177532700%8171103277偏差参数对模型解的影响2022年7月29日11时42分Page 61 of 72 6-7 6-7 整数规划的应用及案例分析整数规划的应用及案例分析 一、投资场所的选择一、投资场所的选择 例1、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj(j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3 三个点至多选择两个；在西区由A4，A5 两个点中至少选一个；在南区由A6，A7 两个点中至少选一个；在北区
49、由A8，A9，A10 三个点中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?A1A2A3A4A5A6A7A8A9A10投资额10012015080709080140160180利润36405022203025485861解：解：设：0-1变量 xi=1(Ai 点被选用）或 0(Ai 点没被选用）。这样我们可建立如下的数学模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t.100 x1+
50、120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1+x2+x3 2 x4+x5 1 x6+x7 1 x8+x9+x10 2 xj 0 xj 为0-1变量，i=1,2,3,102022年7月29日11时42分Page 62 of 72 二、固定成本问题 例2高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如右表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月
