最优化理论_第3章_整数规划

1、第第3章章 整数规划整数规划哈尔滨工程大学哈尔滨工程大学 理学院理学院戴运桃戴运桃Email: 3.1 整数规划整数规划定义定义 规划中的变量（部分或全部）限制为整数时，称为整规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。法能有效地求解一切整数规划。整数规划的数学模型整数规划的数学模型njxmi

2、bxatsxcxfjnjijijnjjj,2,1,0,2,1,),(.)(max(min)11且为整数 若要求所有若要求所有 xj 的解为整数，称为的解为整数，称为纯整数规划纯整数规划 若要求部分若要求部分 xj 的解为整数，称为的解为整数，称为混合整数规划混合整数规划 对应没有整数解要求的线性规划称之为对应没有整数解要求的线性规划称之为松弛问题松弛问题 整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解引例引例 某厂拟用火车装运甲、乙两种货物集装箱，每箱某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：的体积、重量、可获利

3、润以及装运所受限制如下：货物集装箱货物集装箱体积体积(米米3)重量重量(百斤百斤)利润利润(百元百元)甲甲5220乙乙4510 托运限制托运限制 2413 问两种货物各装运多少箱，可使获得利润最大？问两种货物各装运多少箱，可使获得利润最大？返回 设甲、乙两种货物装运箱数分别为设甲、乙两种货物装运箱数分别为x1和和x2。显然，。显然，x1、x2 都要求为整数都要求为整数,于是可建立整数规划模型如下：于是可建立整数规划模型如下： Max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2为整数为整数 (5) 是不是可通过把不考

4、虑整数要求求得的最优解经过是不是可通过把不考虑整数要求求得的最优解经过“化化整整”得到满足整数要求的最优解呢？得到满足整数要求的最优解呢？v容易求得相应的线性规划问题的最优解为容易求得相应的线性规划问题的最优解为 x1=4.8，x2=0，max z=96v现在来分析上述线性规划问题的最优解是否是整数规划现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解问题的最优解因为因为x1表示的是托运甲种货物的箱数，目前得到的最表示的是托运甲种货物的箱数，目前得到的最优解不是整数，所以不合条件的要求。优解不是整数，所以不合条件的要求。是不是可以把所得的非整数最优解经过是不是可以把所得的非整数最优解

5、经过“化整化整”就可就可得到合于条件的整数最优解呢得到合于条件的整数最优解呢?o如将如将(x1=4.8，x2=0)凑整为凑整为(x1=5，x2=0)，这样就破，这样就破坏了条件坏了条件(关于体积的限制关于体积的限制)，因而它不是可行解；，因而它不是可行解；o如将如将(x1=4.8，x2=0)舍去尾数舍去尾数0.8，变为，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最这当然满足各约束条件，因而是可行解，但不是最优解，因为当优解，因为当x1=4，x2=0, 时时z=80；而当；而当x1=4，x2=1(这也是可行解这也是可行解)时，时，z=90。 图中画图中画(+)号的点表

6、示可行的整数解。凑整得到的号的点表示可行的整数解。凑整得到的(5，0)点点不在可行域内，而不在可行域内，而C点又不合于条件。为了满足题中要求，点又不合于条件。为了满足题中要求，表示目标函数的表示目标函数的z的等值线必须向原点平行移动，直到第一的等值线必须向原点平行移动，直到第一次遇到带次遇到带“+”号号B点点(x1=4，x2=1)为止。这样，为止。这样，z的等值线就的等值线就由由z=96变到变到z=90，它们的差值为，它们的差值为z=96-90=6，表示利润的降，表示利润的降低，这是由于变量的不可分性低，这是由于变量的不可分性(装箱装箱)所引起的。所引起的。v由上例看出，将其相应的线性规划的最

7、优解经过由上例看出，将其相应的线性规划的最优解经过“化整化整”来解原整数线性规划，虽是最容易想到的，来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行是可行解。因此有必要对整数线性规划的解法进行专门研究。专门研究。v在求解整数线性规划时，如果可行域是有界的，首在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举所有可行的整数解，即先容易想到的方法就是穷举所有可行的整数解，即列出图中所有标有列出图中所有标有“+ +”的整数点，然后比较它们的的整数点，然后比较它们

8、的目标函数值，从而确定最优解。目标函数值，从而确定最优解。v对于规模较小的问题，变量个数很少，可行解的组对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。合数也较小时，这个方法是可行的，也是有效的。如在例如在例1 1中，变量只有中，变量只有x x1 1和和x x2 2。由条件，由条件，x x1 1所能所能取的整数值为取的整数值为0 0、1 1、2 2、3 3、4 4共共5 5个；由条件，个；由条件，x x2 2所能取的整数值为所能取的整数值为0 0、1 1、2 2共共3 3个。因此所有可个。因此所有可能的整数组合能的整数组合( (不都是可行的不都是可行的)

9、 )数是数是3 35=155=15个，个，穷举法还是勉强可用的。穷举法还是勉强可用的。v对于大型问题，可行的整数组合数会很大。对于大型问题，可行的整数组合数会很大。例如在指派问题中，将例如在指派问题中，将n项任务指派项任务指派n个人去完成，个人去完成，不同的指派方案共有不同的指派方案共有n!种，当种，当n=10时，可能的指时，可能的指派方案数超过派方案数超过300万；当万；当n=20，超过，超过21018。显。显然，穷举法是不可取的。然，穷举法是不可取的。v应寻找仅检查可行的整数组合的一部分，就能定出最应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。优

10、的整数解的方法。分支定界解法就是其中之一。v分枝定界法可用于解纯整数或混合整数线性规划问题。分枝定界法可用于解纯整数或混合整数线性规划问题。20世纪世纪60年代初由年代初由Land Doig和和Dakin等提出，是解等提出，是解整数线性规划的重要方法之一。整数线性规划的重要方法之一。分枝定界法分枝定界法 继续求解定界，重复下去，直到得到最优解为继续求解定界，重复下去，直到得到最优解为止止。基本思想基本思想v例例 求解问题求解问题A min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x1，x2整数例题演示例题演示v问题问题A对应的松弛问题对应的松弛问题B

11、 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20vB1 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x15 分枝分枝vB2 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 vB21 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23分枝分枝vB22 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x24 vB211 min z = -10 x1-

12、20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23 x17 分枝分枝vB212 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23 x18 x1 5x16问题问题B的解为的解为:z0=-136 x1=5.6 x2=4问题问题B2为为:z1=-135x1=6.00 x2=3.75问题问题B1为为:z1=-130 x1=5.00 x2=4.00-136=Z*=-130-136=Z*=0-135=Z*=-130问题问题B21为为:z1=-132 x1=7.2 x2=3.00问题问题B22为为:无可无可行解行解x2 3x

13、24问题问题B211为为:z1=-130 x1=7.00 x2=3.00问题问题B212为为:z1=-130 x1=8.00 x2=2.50 x1 7x18-132=Z*=-130-130=Z*=-130分枝定界法一般步骤分枝定界法一般步骤问题问题(B)(B)无可行解，则无可行解，则(A)(A)也无可行解，停止；也无可行解，停止； 0-1型整数规划是整数规划的一种型整数规划是整数规划的一种特殊形式，它的变量特殊形式，它的变量xj仅取值仅取值0或或1。这。这种只能取种只能取0或或1的变量称为的变量称为0-1变量变量或或二二进制变量。进制变量。3.2 0-1整数规划整数规划 例例：某公司拟在市东、

14、西、南三区建立门市部。拟：某公司拟在市东、西、南三区建立门市部。拟议中有议中有7个位置个位置Ai（i=1，2,7）可供选择规定）可供选择规定 在东区，由在东区，由A1，A2，A3三个点中至多选两个；三个点中至多选两个； 在西区，由在西区，由A4，A5，两个点中至少选一个；，两个点中至少选一个； 在南区，由在南区，由A6，A7，两个点中至少选一个。，两个点中至少选一个。 如果选择如果选择Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利润元，每年可获利润ci元，但投资总额不能超过元，但投资总额不能超过B元。问应选择哪几个点可使年元。问应选择哪几个点可使年利润为最大？利润为最大？72101

15、，点点不不选选择择点点选选择择设设 iAAxiii则该问题的则该问题的数学模型数学模型为：为： 71maxiiixcz2321 xxx154 xx72101，或或 ixi 176 xx 7iiiBxb 在整数规划中，如果变量在整数规划中，如果变量xi仅取仅取0或或1，这时变量，这时变量xi称称为为01变量，这时的整数规划称为变量，这时的整数规划称为01型整数规划。型整数规划。28 在本章开始的在本章开始的例例1中，关于运货的体积限制为中，关于运货的体积限制为 5x1+4x224 (1) 今设运货有车运和船运两种方式，上面的条件系用车运时今设运货有车运和船运两种方式，上面的条件系用车运时的限制条

16、件，如用船运时关于体积的限制条件为的限制条件，如用船运时关于体积的限制条件为 7x1+3x245 (2) 这两个条件是互相排斥的。为了统一在一个问题中，引入这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量变量y，令，令当采用车运方式当采用船运方式, 0, 1y含有互斥约束条件的问题含有互斥约束条件的问题 Max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2为整数为整数 (5)29 于是，于是，(1)式和式和(2)式可由下述条件式可由下述条件(3)式和式和(4)式来代替：式来代替： 5x1+4x224+yM

17、 (3) 7x1+3x245+(1 y)M (4) 其中其中M是充分大的数。是充分大的数。 可以验证可以验证: 当当y=0时，时，(3)式就是式就是(1)式，而式，而(4)式自然成立，因而是式自然成立，因而是多余的。当多余的。当y=1时，时，(4)式就是式就是(2)式，而式，而(3)式是多余的。式是多余的。 引入的变量引入的变量y不必出现在目标函数内，即认为在目标函不必出现在目标函数内，即认为在目标函数内数内y的系数为的系数为0。 30v如果有如果有m个互相排斥的约束条件个互相排斥的约束条件(型型)：i1x1+i2x2+inxnbi，i=1，2，,m 为了保证这为了保证这m个约束条件只有一个起

18、作用，我们引入个约束条件只有一个起作用，我们引入m个个0-1变量变量yi(i=1,2,，m)和一个充分大的常数和一个充分大的常数M，且，且下面这一组下面这一组m+1个约束条件个约束条件 i1x+i2x2+inxnbi+yiM i=1,2,，m (5) y1+y2+ym=m 1 (6) 就合乎上述的要求。这是因为，由于就合乎上述的要求。这是因为，由于(6)式，式，m个个yi中中只有一个能取只有一个能取0值，设值，设yi*=0，代入，代入(5)式，就只有式，就只有i=i*这这个约束条件起作用，而别的式子都是多余的。个约束条件起作用，而别的式子都是多余的。 对于对于0-1型整数规划，一般采用型整数规

19、划，一般采用隐枚举法隐枚举法，而不必采，而不必采用完全枚举法。包括用完全枚举法。包括: (1)只要发现某个变量组合不满足其中一个约束条件只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。时，就不必再去检验其他约束条件是否可行。 (2)若已发现一个可行解，则可根据它的目标函数值若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中每当发现就不必再去检验它的可行性；在以后的求解中每当发现更好的可行解就替换原来的过滤条件。更好的可行解就替换原来的

20、过滤条件。0-1型整数规划的解法型整数规划的解法 例例 : 用隐枚举法求解下列用隐枚举法求解下列01型整数规划型整数规划 106434422523max3213221321321321或或，xxxxxxxxxxxxxxxxz3)001(11 zX，增增加加一一个个约约束束条条件件：3523321 xxx该条件称为过滤条件该条件称为过滤条件解：解：先通过试探找一个可行解先通过试探找一个可行解，所有可能所有可能的可行解的可行解约束条件约束条件可行解可行解否否Z值值 (0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1) 0 5 -1 1 0

21、 1 5 -2 3 1 1 1 0 5 3 1 5 8 0 2 1 1 8 1 6 2 6 8*101* zX，所有可能所有可能的可行解的可行解约束条件约束条件可行解可行解否否Z值值 (0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1) 0 5 -1 1 0 1 5 -2 3 3 8 0 2 1 1 8 1 6 8*101* zX， 0 0 0 0 0所有可能所有可能的可行解的可行解约束条件约束条件可行解可行解否否Z值值 (1，0，1)(1，1，1)(0，1，1)(1，0，0)(0，1，1)(1，1，0)(0，0，0)(0，1，0)

22、8 6 5 3 3 1 0 -2 8*101* zX， 0 2 1 1 836v注意注意： 一般常重新排列一般常重新排列xi的顺序使目标函数中的顺序使目标函数中xi的系数是递增的系数是递增(不不减减)的，在上例中，改写的，在上例中，改写 z=3x1 2x2+5x3= 2x2+3x1+5x3 因为因为 2，3，5是递增的序，变量是递增的序，变量(x2，x1，x3)也按下述顺也按下述顺序取值：序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)， 这样，最优解容易比较早的发现。这样，最优解容易比较早的发现。 再结合过滤条件的改进，更可使计算简化。再结合过滤条件的改进，更可使计算简

23、化。37z=3x1 2x2+5x3= 2x2+3x1+5x3指派问题指派问题n指派问题的标准形式及其数学模型指派问题的标准形式及其数学模型n匈牙利解法求解指派问题匈牙利解法求解指派问题 n一般的指派问题一般的指派问题 有有n项任务，恰好项任务，恰好n个人承担，第个人承担，第i人完成第人完成第j 项任务项任务的花费的花费(时间或费用等时间或费用等)为为cij，要求确定人和事之间的一要求确定人和事之间的一一对应的指派方案，使总花费最省？一对应的指派方案，使总花费最省？指派问题的标准形式及其数学模型指派问题的标准形式及其数学模型 任任务务 人人员员 E J G R 甲甲 乙乙 丙丙 丁丁 2 10

24、9 7 15 4 14 8 13 14 16 11 4 15 13 9 例例4 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字。分别记作文字。分别记作E、J、G、R。现有甲、乙、丙、丁现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需需时间如下表。问应指派何人去完成何工作，使所需总时间最少？总时间最少？指派问题的标准形式及其数学模型指派问题的标准形式及其数学模型 指派问题的系数矩阵如下：指派问题的系数矩阵如下：nnnnnnnnjiccccccccc

25、cC212222111211)(Cij的含义可以不同，如费用、成本、时间等。的含义可以不同，如费用、成本、时间等。为建立标准指派问题的数学模型，引入为建立标准指派问题的数学模型，引入nn个个0-1变量：变量：jix指派问题的数学模型可写成如下形式：指派问题的数学模型可写成如下形式：若派第若派第i人做第人做第j事事0 若不派第若不派第i人做第人做第j事事 （ij=1，2,，n） ninjijijxczmin11 n),1,jn;,1,(i101 1n), 1( 111 或或ijnjijniijx)n,i(xjx 第第j项工作由项工作由一个人做一个人做第第i人做人做一项工作一项工作指派问题的每个可

26、行解，可用矩阵表示如下：指派问题的每个可行解，可用矩阵表示如下：nnnnnnnnjixxxxxxxxxxX212222111211)(矩阵矩阵X中，每行各元素中只有中，每行各元素中只有1个元素为个元素为1,其余各元素等其余各元素等0；每列各元素中也只有每列各元素中也只有1个元素为个元素为1,其余各元素等其余各元素等0 。指派问题有指派问题有n！个可行解。个可行解。匈牙利法解题步骤匈牙利法解题步骤 1955年，库恩利用匈牙利数学家康尼格的关于年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。种算法，

27、称为匈牙利解法。 标准指派问题是一种特殊的整数规划问题，又标准指派问题是一种特殊的整数规划问题，又是特殊的是特殊的0-1规划问题。规划问题。 匈牙利解法的关键是利用了匈牙利解法的关键是利用了指派问题最优解的如指派问题最优解的如下性质下性质： 若从指派问题的系数矩阵若从指派问题的系数矩阵C的某行（或某列）各元的某行（或某列）各元素分别减去该行（或列）的最小元素素分别减去该行（或列）的最小元素，得到一个新的得到一个新的矩阵矩阵C，则以则以C和和C 为系数矩阵的两个指派问题有相为系数矩阵的两个指派问题有相同的最优解。同的最优解。 （系数矩阵的变化并不影响数学模型的约束方程（系数矩阵的变化并不影响数学

28、模型的约束方程组，而只是目标函数值减少了常数组，而只是目标函数值减少了常数k，所以最优解不所以最优解不变）变）匈牙利法匈牙利法-2-4-9-7 若某行若某行(列列)已有已有0元素，那就不必再减了。例元素，那就不必再减了。例1的计算为：的计算为： 9 11 8 7 13 16 14 9 15 14 4 104 13 15 2)c(ij2 4 1 04 7 5 011 10 0 62 11 13 01. 使系数矩阵各行、各列出现零元素使系数矩阵各行、各列出现零元素 作法：系数矩阵各行元素减去所在行的最小元素，再作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。从所得

29、矩阵的各列减去所在列最小元素。(因一行中因一行中xij 取值取值一个一个1，其余为，其余为0，cij 同时减去一常数不影响同时减去一常数不影响xij取值取值)。匈牙利法解题步骤如下：匈牙利法解题步骤如下：2 4 1 04 7 5 011 10 0 62 11 13 0-4 -2 这就保证每行每列至少有一个这就保证每行每列至少有一个0元素，同时不出现元素，同时不出现负负元素元素。 2. 试求最优解。试求最优解。 0 0 1 0 2 3 5 0 9 6 0 6 0 7 13 0 作法：由独立作法：由独立0元素的行（列）开始，独立元素的行（列）开始，独立0元素处画元素处画 标记标记 ，在有，在有 的

30、行列中划去其它的行列中划去其它0元素；再在剩余的元素；再在剩余的0元素中重复此做法，直至不能标记元素中重复此做法，直至不能标记 为止。为止。（1）当遇到在所有的行和列中，）当遇到在所有的行和列中，0元素都不止一个时（存在元素都不止一个时（存在0元素的闭回元素的闭回路），可任选其中一个路），可任选其中一个0元素加圈，同时划去同行和同列中其他元素加圈，同时划去同行和同列中其他0元素。元素。（2）如能找出）如能找出n个位于不同行不同列的零元素，令对应的个位于不同行不同列的零元素，令对应的xij= 1，其余其余xij = 0，得最优解，结束；否则，看下面的例题转第得最优解，结束；否则，看下面的例题转第

31、3步。步。 9 10 7 10 4 10 6 6 14 159 14 12 17 7 6 6 6 9 8 9 7 9 7 12 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0 2 0 5 7 6 7 6 4 例例 求表中所示效率矩阵的指派问题的最小解。求表中所示效率矩阵的指派问题的最小解。 任务任务人人ABCDE甲甲127979乙乙89666丙71712149丁15146610戊4107109经行运算即可得每行每列都有经行运算即可得每行每列都有0元素的系数矩阵。元素的系数矩阵。 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0

32、2 0 5再按上述步骤运算，得到：再按上述步骤运算，得到：所画所画 0元素少于元素少于n，未得到最优解。未得到最优解。 563604008927510000032202053. 作能覆盖所有作能覆盖所有0元素的最少直线数的直线集合元素的最少直线数的直线集合 (1) 对没有对没有 的行打的行打 号；号； (2) 对已打对已打 号的行中所有号的行中所有0元素的所在列打元素的所在列打 号；号； (3) 再对打有再对打有 号的列中号的列中 0 元素的所在行打元素的所在行打 号；号； (4)重复重复(2),(3)直到得不出新的打直到得不出新的打 号的行号的行(列列)为止；为止； (5) 对没有打对没有打

33、 号的行画一横线，对打号的行画一横线，对打 号的列画一号的列画一 纵线，这就得到覆盖所有纵线，这就得到覆盖所有0元素的最少直线数元素的最少直线数 56360400892751000003220205 4.未被直线覆盖的最小元素为未被直线覆盖的最小元素为cij0,在在打打 号号行中各元素都行中各元素都减去减去cij0,打打 号号列中的各元素都加上列中的各元素都加上cij0。Cij=2 解为解为 3 4 1 4 0 4 0 0 8 110 5 3 8 0 0 0 0 3 4 2 0 2 0 7 5.返回步骤返回步骤2，重复上述步骤。，重复上述步骤。一般的指派问题一般的指派问题 在实际应用中，常会遇

34、到各种非标准形式的指派问在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。用匈牙利解法求解。 最大化指派问题最大化指派问题 设最大化指派问题系数矩阵设最大化指派问题系数矩阵C中最大元素为中最大元素为m。令矩。令矩阵阵B=(bij)=(m-cij), 则以则以B为系数矩阵的最小化指派问题和为系数矩阵的最小化指派问题和以以C为系数矩阵的原最大化指派问题有相同的最优解。为系数矩阵的原最大化指派问题有相同的最优解。 人数和事数不等的指派问题人数和事数不等的指派问题 若人少事多，则添上一些虚拟的若

35、人少事多，则添上一些虚拟的“人人”。这些虚拟的。这些虚拟的人作各事的费用系数可取人作各事的费用系数可取0，理解为这些费用实际上不会，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的发生。若人多事少，则添上一些虚拟的“事事”。这些虚。这些虚拟的事被各人做的费用系数同样也取拟的事被各人做的费用系数同样也取0。 一个人可做几件事的指派问题一个人可做几件事的指派问题 若某个人可做几件事，则可将该人看做相同的几个若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都人来接受指派。这几个人作同一件事的费用系数当然都一样。一样。 某事一定不能由某人作的指派问题

36、某事一定不能由某人作的指派问题 若某事一定不能由某个人做，则可将相应的费用系若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数数取做足够大的数M。 例例 ：某大型工程有五个工程项目，决定向社会：某大型工程有五个工程项目，决定向社会公开招标，建设公司公开招标，建设公司A1，A2，A3参加招标承建，根参加招标承建，根据实际情况，可允许每家建设公司承建一项或二项工据实际情况，可允许每家建设公司承建一项或二项工程。求使总费用最少的指派方案。程。求使总费用最少的指派方案。 工程公司B1B2B3B4B5A14871512A279171410A369128733221178129678129610

37、141797101417971215784121578454321AAAAAABBBBB上面的系数矩阵有上面的系数矩阵有6行行5列，为了使列，为了使“人人”和和“事事”的数目相同，引入的数目相同，引入一件虚拟的事一件虚拟的事B6，使之成为标准指派问题的系数矩阵：，使之成为标准指派问题的系数矩阵：解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看成两家建筑公司，其系数矩阵为成两家建筑公司，其系数矩阵为332211078129607812960101417970101417970121578401215784654321AAAA

38、AABBBBBB然后，用匈牙利解法求解。可得费用最省为然后，用匈牙利解法求解。可得费用最省为4+7+9+8+7=35（百万元）（百万元）v1. 用图解法和单纯形法求解线性规划问题用图解法和单纯形法求解线性规划问题 作业：作业：0,164826233. .3min212121212121xxxxxxxxxxtsxxzv2. 用单纯形法求解线性规划问题用单纯形法求解线性规划问题 0,1321731323. .43max3213213231321xxxxxxxxxxtsxxxzv3. 求解整数规划问题求解整数规划问题 max z=3x1+2x2 2x1+3x214 2x1+x29 x1，x20 x1

39、，x2整数 4. 设有设有A、B、C、D四人去完成甲、乙、丙、丁四四人去完成甲、乙、丙、丁四项任务，不同的人完成不同的任务时间不同，资料如下项任务，不同的人完成不同的任务时间不同，资料如下，求总时间最小的分配方案。，求总时间最小的分配方案。8 6 14 15 14 12 17 7 9 6 9 88 9 7 21)(ijcABCD 甲甲 乙乙 丙丙 丁丁 5. 设有设有A、B、C、D四人去完成甲、乙、丙、丁四四人去完成甲、乙、丙、丁四项任务，不同的人完成不同的任务赢得不同，资料如下项任务，不同的人完成不同的任务赢得不同，资料如下，求总赢得最大的分配方案。，求总赢得最大的分配方案。4 8 3 99

40、 11 8 78 7 10 68 5 6 4)(ijcABCD 甲甲 乙乙 丙丙 丁丁 6. 设有设有A、B、C、D、E五人去完成甲、乙、丙、丁五人去完成甲、乙、丙、丁四项任务，每人完成各项工作如表所示。规定每项工作四项任务，每人完成各项工作如表所示。规定每项工作只能有一个人去完成，每人最多承担一项工作，又假定只能有一个人去完成，每人最多承担一项工作，又假定D因某种原因决定不承担丁项目，问应该如何分配，才因某种原因决定不承担丁项目，问应该如何分配，才能使能使4项工作总得花费时间最少？项工作总得花费时间最少？8 6 13 15 2015 7 14 5 154 2 15 10 59 15 3 2

41、01)(ijcA B C D E 甲甲 乙乙 丙丙 丁丁v例例 求解整数规划问题求解整数规划问题A max z=3x1+2x2 2x1+3x2 70 2x1+x270 x1，x20 x1，x2整数 v解：先不考虑条件，即解相应的线性规划解：先不考虑条件，即解相应的线性规划B,(见见图，得最优解图，得最优解x1=4.81，x2=1.82，z0=356 可见它不符合整数条件。可见它不符合整数条件。这时这时z0是问题是问题A的最优目标函数值的最优目标函数值z*的上界，记作的上界，记作z0= 。而在而在x1=0，x2=0时，时，显然是问题显然是问题A的一个整数可行解，的一个整数可行解，这时这时z=0，

42、是，是z*的一个下界，的一个下界，记作记作 =0，即，即0z*356。zz分枝分枝 因为因为 当前均为非整数，故不满足整数要求，当前均为非整数，故不满足整数要求，任选一个进行分枝。设选任选一个进行分枝。设选 进行分枝，把可行集进行分枝，把可行集分成分成2个子集：个子集： 因为因为4与与5之间无整数，故这两个子集内的整数解之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划求解如下：这两个子集的规划求解如下：21,xx1x44.80921x514.80921x问题问题B1为为:Max z=40 x1+90 x2 9

43、x1+7x256 7x1+20 x2 70 x1 4 x1,x20问题问题B2为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 068v x14，x15B1:z1=349 x1=4.00 x2=2.10B2:z2=341 x1=5.00 x2=1.5769v显然，仍没有得到全部变量是整数的解。因显然，仍没有得到全部变量是整数的解。因z1z2，故，故将将 改为改为349，那么必存在最优整数解，得到，那么必存在最优整数解，得到z*，并且，并且 0z*349v继续对问题继续对问题B1和和B2进行分解。因进行分解。因z1z2，故先分解，故先分解B1为为两支。增加条件两支。增加条件x22，称为问题，称为