管理运筹学6整数规划

1、精选ppt 例 用分枝定界法求解 且且均均取取整整数数,0,255.22108.02.134max21212121xxxxxxxxZ解解: 先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 用图解法得到最优解用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。如下图所示。精选ppt1010108 . 02 . 121 xx255 . 2221 xx松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14),Z0=35.7x1x2oABC精选ppt得得到到两两个

2、个线线性性规规划划及及增增加加约约束束4311 xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.5精选ppt10 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不不可可

3、行行，得得到到线线性性规规划划，显显然然及及进进行行分分枝枝，增增加加约约束束选选择择目目标标值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，精选ppt10 x1x2oACLP134可可行行域域是是一一条条线线段段即即，, 40,464255 . 22108 . 02 . 1:21134max121121212121 xxxxxxxxxxLPxxZ：及及，得得线线性性规规划划及及进进行行分分枝枝，增增加加约约束束，选选择择由由于于212211542111121LPL

4、PxxLPZZ 6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212精选pptLP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22无可行解无可行解x27精选ppt小结学习要点：学习要点

5、： 掌握一般整数规划问题概念及模型结构掌握一般整数规划问题概念及模型结构 掌握分支定界法原理掌握分支定界法原理 能够用分支定界法求解一般整数规划问题能够用分支定界法求解一般整数规划问题精选ppt精选ppt精选ppt精选ppt循环循环(X1,X2,X3)s.t.0s.t.1s.t.2s.t.3s.t.4满满足足Z值值1(0,0,0)0no2(0,0,1)5-1101yes53(0,1,0)-2no4(0,1,1)315no5(1,0,0)31110yes36(1,0,1)80211yes87(1,1,0)1no8(1,1,1)626no精选ppt精选ppt精选ppt循循环环(X2,X1,X3)s

6、.t.0s.t.1s.t.2s.t.3s.t.4满满足足Z值值1(0,0,0)0no2(0,0,1)5-1101yes5循循环环(X2,X1,X3)s.t.0s.t.1s.t.2s.t.3s.t.4满满足足Z值值3(0,1,0)3no4(0,1,1)80211yes8精选ppt循循环环(X2,X1,X3)s.t.0s.t.1s.t.2s.t.3s.t.4满满足足Z值值5(1,0,0)-2no6(1,0,1)3no7(1,1,0)1no8(1,1,1)6no精选ppt分配问题与匈牙利法设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作

7、只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的效率件工作的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应。问应如何分配才能使总效率（如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？设决策变量设决策变量 ),.,2 , 1,(ji0ji1njixij 件事件事个人做第个人做第不指派第不指派第件事件事个人做第个人做第指派第指派第精选ppt分配问题与匈牙利法 指派问题的数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijni

8、njijij或或取取精选ppt分配问题与匈牙利法如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵bij，则以bij为效率矩阵的分配问题与以aij为效率矩阵的分配问题具有相同的最优解。精选ppt分配问题与匈牙利法设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的效率件工作的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij

9、0。问应。问应如何分配才能使总效率（如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？设决策变量设决策变量 ),.,2 , 1,(ji0ji1njixij 件事件事个人做第个人做第不指派第不指派第件事件事个人做第个人做第指派第指派第精选ppt分配问题与匈牙利法 指派问题的数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或取取精选ppt分配问题与匈牙利法如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵bij

10、，则以bij为效率矩阵的分配问题与以aij为效率矩阵的分配问题具有相同的最优解。精选ppt分配问题与匈牙利法1) 变换指派问题的系数矩阵变换指派问题的系数矩阵(cij)为为(bij)，使在，使在(bij)的各行各列的各行各列中都出现中都出现0元素，即元素，即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2) 进行试指派，以寻求最优解。进行试指派，以寻求最优解。 在在(bij)中找尽可能多的独立中找尽可能多的独立0元素，若能找出元素，若能找出n个独立个独立0元元

11、素，就以这素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余，其余为为0，这就得到最优解。，这就得到最优解。精选ppt分配问题与匈牙利法 找独立0元素，常用的步骤为： 从只有一个从只有一个0元素的行开始，给该行中的元素的行开始，给该行中的0元素加圈，记作元素加圈，记作 。然后划去然后划去 所在列的其它所在列的其它0元素，记作元素，记作 ；这表示该列所代表的；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个从只有一个0元素的列开始（画元素的列开始（画的不计在内），给该列

12、中的的不计在内），给该列中的0元素加圈，记作元素加圈，记作；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 ，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少这个元素少这个0元素加元素加圈圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划掉同行同列。然后划掉同行同列的其它的其它0元素。可

13、反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。精选ppt分配问题与匈牙利法 若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这指，那么这指派问题的最优解已得到。若派问题的最优解已得到。若m n, 则转入下一步。则转入下一步。3) 用最少的直线通过所有用最少的直线通过所有0元素。其方法：元素。其方法： 对没有对没有的行打的行打“”； 对已打对已打“” 的行中所有含的行中所有含元素的列打元素的列打“” ； 再对打有再对打有“”的列中含的列中含 元素的行打元素的行打“” ； 重复重复、直到得不出新的打直到得不出新的打

14、号的行、列为止；号的行、列为止； 对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数 l 。注：注：l 应等于应等于m，若不相等，说明试指派过程有误，回到第，若不相等，说明试指派过程有误，回到第2步，另行试步，另行试指派；若指派；若 lm n，表示还不能确定最优指派方案，须再变换当前的系，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。精选ppt分配问题与匈牙利法4) 变换矩阵(bij)以增加0元素 在没有被直线通过的

15、所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。精选ppt分配问题与匈牙利法 例 已知四人分别完成四项工作所需时间如下表，求最优分配方案。 任务人员ABCD甲215134乙1041415丙9141613丁78119精选ppt 解：1）变换系数矩阵，增加0元素。79429118713161491514410413152 2424104750111006211130 00102350960607130 00102350960607130 2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个

16、数为元素的个数为4 , 指派问题的最优指指派问题的最优指派方案即为甲负责派方案即为甲负责D工作，乙负责工作，乙负责B工作，工作，丙负责丙负责A工作，丁负责工作，丁负责C工作。这样安排工作。这样安排能使总的工作时间最少，为能使总的工作时间最少，为4491128。精选ppt 例 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务人员ABCD甲67112乙4598丙31104丁5982精选ppt分配问题与匈牙利法 解：1）变换系数矩阵，增加0元素。2142 28

17、9541013895421176)( ijc 06733902451009545 01733402401004542）试指派（找独立）试指派（找独立0元素）元素）找到找到 3 个独立零元素个独立零元素 但但 m = 3 n = 4精选ppt分配问题与匈牙利法 3）作最少的直线覆盖所有0元素独立零元素的个数独立零元素的个数m等于最少等于最少直线数直线数l，即，即lm=3n=4；4）没有被直线通过的元素中选择最小值为）没有被直线通过的元素中选择最小值为1，变换系数矩，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直阵，将没有被直线通过

18、的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派精选ppt分配问题与匈牙利法 6244251343000 0 00试指派试指派 6244251343 得到得到4个独立零元素，个独立零元素， 所以最优解矩阵为：所以最优解矩阵为： 0100001000011000即完成即完成4个任务的总时间最少个任务的总时间最少为：为：241+8=15精选ppt分配问题与匈牙利法 例 已知五人分别完成五项工作耗费如下表，求最优分配方案。 任务人员ABCDE甲759811乙9127119丙85468丁73696

19、戊467511精选ppt分配问题与匈牙利法4347511576469637964589117129118957 7132036304520142405263402-1 -2 解：1）变换系数矩阵，增加0元素。精选ppt分配问题与匈牙利法 5032015304310140305242402 5032015304310140305242402 2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。精选ppt分配问题与匈牙利法 5032015304310140305242402 选择直线外的最小元素选择直线外的最小元素为为1；直

20、线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。精选ppt分配问题与匈牙利法 5033004203310240306231301 l =m=4 n=5选择直线外最小元素为选择直线外最小元素为1，直线外元素减直线外元素减1，直线交，直线交点元素加点元素加1，其他保持不，其他保持不变，得到新的系数矩阵。变，得到新的系数矩阵。精选ppt分配问题与匈牙利法 6044003202300230206130300 总费用为总费用为=5+7+6+6+4=28=5+7+6+6+4=28注：此问题有多个最优解注：此问题有多个最优解精选ppt分配问题与匈牙利法 604400

21、3202300230206130300 总费用为总费用为=7+9+4+3+5=28=7+9+4+3+5=28精选ppt分配问题与匈牙利法 6044003202300230206130300 总费用为总费用为=8+9+4+3+4=28=8+9+4+3+4=28精选ppt分配问题与匈牙利法 课堂练习：用匈牙利法求解下列指派问题。79 10 1213 12 16 1715 16 14 1511 12 15 163821038729764275842359106910练习练习1：练习练习2：精选ppt分配问题与匈牙利法79 10 1213 12 16 1715 16 14 1511 12 15 163

22、8210387297642758423591069104848 21 21答案：答案：精选ppt分配问题与匈牙利法匈牙利法的条件是：模型求最小值、效率匈牙利法的条件是：模型求最小值、效率cij0。当遇到各种非标准形式的指派问题时，处理方法是先将当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。其转化为标准形式，然后用匈牙利法来求解。精选ppt处理方法：设处理方法：设m为最大化指派问题系数矩阵为最大化指派问题系数矩阵C中最大元素。中最大元素。令矩阵令矩阵B（m-cij）nn则以则以B为系数矩阵的最小化指派问题和为系数矩阵的最小化指派问题和原问题有相同的最优解

23、。原问题有相同的最优解。例例 某人事部门拟招聘某人事部门拟招聘4人任职人任职4项工作，对他们综合考评的项工作，对他们综合考评的 得得分如下表（满分分如下表（满分100分），如何安排工作使总分最多。分），如何安排工作使总分最多。 88809086907983829578879590739285丁丁丙丙乙乙甲甲C精选ppt分配问题与匈牙利法 解: M95，令)95(ijcC 71559516121301780522310C用匈牙利法求解用匈牙利法求解C，最优解为：，最优解为： 0100100000010010X即甲安排做第二项工作、乙做第三项、丙做第四项、丁做即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项第三项, 最高总分最高总分Z92959080357精选ppt分配问题与匈牙利法 当人数当人数m大于工作数大于工作数n时，加上时，加上mn项虚拟工作，例如：项虚拟工作，例如： 1235461714836111095 00000000001235461714836111095 当人数当人数m小于工作数小于工作数n时，加上时，加上nm个人，例如个人，例如 1716131074569102015 00001716131074569102015精选ppt分配问题