1、 第三章目标规划和整数规划第三章目标规划和整数规划3.1 3.1 目标规划目标规划3.2 3.2 整数规划整数规划 第三章目标规划和整数规划第三章目标规划和整数规划3 31 1 目标规划目标规划 3 31 11 1 单目标规划单目标规划 3 31 12 2 多目标规划多目标规划 级别相同的目标规划级别相同的目标规划 具有优先级目标规划具有优先级目标规划3 32 2 整数规划整数规划 3 32 21 1 整数规划分枝限界法整数规划分枝限界法 3 31 12 2 整数规划分割平面法整数规划分割平面法 3 32 21 0-11 0-1规划规划 3 31 12 2 分派问题分派问题OR3 31 1目标
2、规划目标规划3 31 11 1单目标规划单目标规划 3 31 11 11 1单目标规划数学模型单目标规划数学模型 (1)(1)如何安排可获得最大利润如何安排可获得最大利润 Max ZMax Z（X X）=8x=8x1 1+6x+6x2 2 4 4x x1 1+2x+2x2 2 60 60 2x 2x1 1+4x+4x2 2 4848 x x1 1，x x2 2 00 x x1 1=12,x=12,x2 2=6,=6,Z(X*)=132AB42426860可使用量可使用量48设备（设备（hr)原料（原料（kg)利润（千元）利润（千元）例例OR（线性规划）（线性规划）(2)(2)利润目标为利润目标
3、为140140（百元）（百元）此目标称之为预定目标，实际完成的量与预定目标此目标称之为预定目标，实际完成的量与预定目标 之间可能出现偏差，通常用之间可能出现偏差，通常用d d+、d d-（d d+、d d-00）表示表示，称为偏差变量。称为偏差变量。其中：其中：d d+表示超过预定指标的部分，表示超过预定指标的部分，d d-表示未达到预定指标的部分表示未达到预定指标的部分 在客观条件下，最终完成的结果可能出现以下三种在客观条件下，最终完成的结果可能出现以下三种情况：情况：d d+0,0,d d-=0=0 表明超额完成预定指标表明超额完成预定指标 d d-0,0,d d+=0=0 表明未达到预定
4、指标表明未达到预定指标 d d+=d d-=0=0 表明恰好完成预定指标表明恰好完成预定指标上述三种情况可用模型表示上述三种情况可用模型表示OR 8 8x x1 1+6x+6x2 2特征：增加了目标约束、特征：增加了目标约束、目标中只出现偏差变量且为求极小化问题、目标中只出现偏差变量且为求极小化问题、d d+d d-=0=0d d-,d d+d d-+d d-d d+=目标约束目标约束系统约束系统约束Z=Z=4 4x x1 1+2x+2x2 2 60 60 2 2x x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，0 0 140140MinMinOR3 31 11 12 2
5、 单目标规划解单目标规划解 用单纯形法求满意解用单纯形法求满意解,注意求极小化问题最优性条件：注意求极小化问题最优性条件：0j标准型标准型:Min Z=Min Z=d d-8 8x x1 1+6x+6x2 2+d d-d d+=140=140 4 4x x1 1+2x+2x2 2+x+x3 3 =60 =60 2x 2x1 1+4x+4x2 2 +x +x4 4 =48 =48 x x1 1，x x2 2 x x3 3,x,x4 4,d d-,d d+0 0 X1 X2 X3 X4 d-d+0 0 0 0 1 0 8 6 0 0 1 -14 2 1 0 0 0 2 4 0 1 0 0-8 14
6、06048d-X3X4100OR -6 0 0 0 1c cj j0 00 00 00 01 10 0c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4d d-d d+1 1d d-1 14 40 08 86 60 00 01 1-1 10 0 x x3 36 60 04 42 21 10 00 00 00 0 x x4 44 48 82 24 40 01 10 00 0j-8 8-6 60 00 00 01 11 1d d-2 20 00 02 2-2 20 01 1-1 10 0 x x1 11 15 51 11 1/2 21 1/4 40 00 00 00 0 x
7、 x4 41 18 80 03 3-1 1/2 21 10 00 0j0 0-2 22 20 00 01 11 1d d-8 80 00 0-5 5/3 3-2 2/3 31 1-1 10 0 x x1 11 12 21 10 01 1/3 3-1 1/6 60 00 00 0 x x2 26 60 01 1-1 1/6 6 1 1/3 30 00 0j0 00 05 5/3 32 2/3 30 01 100 x x1 1=12=12，x x2 2 =6,6,d d-=8=8 d d+=0=0 完成利润完成利润132132（百元）（百元）OR 由此可得：由此可得：x x1 1=12=12，x
8、x2 2=6=6，d d+=0=0，d d-=8=8 完成利润完成利润132132（百元）（百元）3 31 12 2 级别相同的多目标规划级别相同的多目标规划3 31 12 21 1数学模型数学模型（1 1）实现利润目标）实现利润目标122122（百元）（百元）（2 2）产品）产品A A的产量不多于的产量不多于1010 设：设：d di i+,d di i-(i=1,2)(i=1,2)分别为超过目标值的部分，及未分别为超过目标值的部分，及未完成目标值的部分。完成目标值的部分。8 8x x1 1+6x+6x2 2 minmin目标约束目标约束系统约束系统约束x x1 14 4x x1 1+2x+
9、2x2 2 60 60 2 2x x1 1+4x+4x2 2 48 48x x1 1，x x2 2，=122=122=10=10d d1 1+,d d1 1-，d d2 2+,d d2 2-00Z=Z=+d d1 1-d d1 1+d d2 2-d d2 2+d d1 1-+d d2 2+OR 8 8x x1 1+6x+6x2 2+d d1 1-d d1 1+=122=122 x x1 1 +d d2 2-d d2 2+=10=10 4x 4x1 1+2x+2x2 2 60 60 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d d1 1+,d d1 1-，d d
10、2 2+,d d2 2-00 min Z=min Z=d d1 1-+d d2 2+目标约束目标约束系统约束系统约束c cj j0 00 00 00 01 10 00 01 1c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4d d1 1-d d1 1+d d2 2-d d2 2+1 1d d1 1-1221228 86 60 00 01 1-1 10 00 00 0d d2 2-1 10 01 10 00 00 00 00 01 1-1 10 0 x x3 36 60 04 42 21 10 00 00 00 00 00 0 x x4 448482 24 40 01
11、10 00 00 00 0c cj j-z-zj j-8-8-6-60 00 00 01 10 01 13 31 12 22 2单纯形表单纯形表ORc cj j0 00 00 00 01 10 00 01 1c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4d d1 1-d d1 1+d d2 2-d d2 2+1 1d d1 1-1221228 86 60 00 01 1-1 10 00 00 0d d2 2-1 10 01 10 00 00 00 00 01 1-1 10 0 x x3 36 60 04 42 21 10 00 00 00 00 00 0 x x4
12、448482 24 40 01 10 00 00 00 0c cj j-z-zj j-8-8-6-60 00 00 01 10 01 1c cj j0 00 00 00 01 10 00 01 1c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4d d1 1-d d1 1+d d2 2-d d2 2+1 1d d1 1-42420 06 60 00 01 1-1 1-8-88 80 0 x x1 11 10 01 10 00 00 00 00 01 1-1 10 0 x x3 32 20 00 02 21 10 00 00 0-4-44 40 0 x x4 428280
13、 04 40 01 10 00 0-2-22 2c cj j-z-zj j0 0-6-60 00 00 01 18 8-7-73 31 12 22 2单纯形表单纯形表c cj j0 00 00 00 01 10 00 01 1c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4d d1 1-d d1 1+d d2 2-d d2 2+1 1d d1 1-42420 06 60 00 01 1-1 1-8-88 80 0 x x1 11 10 01 10 00 00 00 00 01 1-1 10 0 x x3 32 20 00 02 21 10 00 00 0-4-44 4
14、0 0 x x4 428280 04 40 01 10 00 0-2-22 2c cj j-z-zj j0 0-6-60 00 00 01 18 8-7-70 0 x x2 27 70 01 10 00 0 1 1/6 6-1 1/6 6-4 4/3 34 4/3 30 0 x x1 11 10 01 10 00 00 00 00 01 1-1 10 0 x x3 36 60 00 01 10 0-1 1/3 31 1/3 3-4 4/3 34 4/3 30 0 x x4 40 00 00 00 01 1-2 2/3 32 2/3 31 10 0/3 3-1 10 0/3 3c cj j -z
15、 zj j0 00 00 00 01 10 00 01 1x x1 1=10=10、x x2 2=7=7 x x3 3=6=6 x x4 4=0=0d d1 1+=d d1 1-=d d2 2+=d d2 2-=0=0，完成利润完成利润122122，两个目标均已实现。，两个目标均已实现。00 3 31 13 3具有优先级的多目标规划具有优先级的多目标规划 3 31 13 31 1数学模型数学模型 例：例：P P1 1:充分利用设备有效台时，不加班；充分利用设备有效台时，不加班；P P2 2:产品产品B B的产量不多于的产量不多于4 4；P P3 3:实现利润实现利润130130（百元）（百元）
16、4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P P1 1P P2 2P P3 3+d d2 2+d d3 3-MinMinOR3 31 13 32 2目标规划图解法目标规划图解法 仍以例仍以例3 3为例为例 （1 1）根据系统约束，确
17、定可行域，如图）根据系统约束，确定可行域，如图多边形多边形OABOAB为该目标规划的可行域；为该目标规划的可行域；（2 2）不考虑偏差，即：）不考虑偏差，即：d di i+=d di i-=0=0（i=1,2,3)i=1,2,3)，然后按然后按顺序作出目标约束相应的直线，并标出顺序作出目标约束相应的直线，并标出d di i+0,0,d di i-00的方向的方向。（。（3 3）按优先顺序找出该目标的满意解：）按优先顺序找出该目标的满意解：4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x
18、+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P P1 1P P2 2P P3 3+d d2 2+d d3 3-MinMinORFECBADOX2X1d d1 1+00d d3 3+00d d2 2+00d d2 2-00d d3 3-00d d1 1-00G 4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =
19、4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,d di i-(i=1,2,3)0(i=1,2,3)0 Z=Z=(d d1 1-+d d1 1+)P P1 1P P2 2P P3 3+d d2 2+d d3 3-MinMin(1)(1)显然线段显然线段CDCD上的点满足第一目标上的点满足第一目标 (2)(2)FDFD上的点同时满足第一目标与第二上的点同时满足第一目标与第二 目标目标FECBADOX2X1d d1 1+00d d3 3+00d d2 2+00d d2
20、 2-00d d3 3-00d d1 1-00G(1)(1)显然线段显然线段CDCD上的点满足第一目标上的点满足第一目标 (2)(2)FDFD上的点同时满足第一目标与第二目标上的点同时满足第一目标与第二目标(3)(3)E E点满足第一、第三目标点满足第一、第三目标,与第二目标矛盾与第二目标矛盾，G G点满足第二、第三目标点满足第二、第三目标 与第一目标矛盾与第一目标矛盾，因此允许第三目标有偏差，线段，因此允许第三目标有偏差，线段FDFD上的上的F F点点可使可使d d3 3-取最小值，故取最小值，故F F点为所求满意解。其坐点为所求满意解。其坐标为（标为（1313，4 4）x x1 1=13=
21、13，x x2 2=4=4，利润利润128128（百元）。（百元）。Operational Research3 31 13 33 3单纯形法单纯形法 例例 Min Z=Min Z=P P1 1(d d1 1-+d d1 1+)+)+P P2 2 d d2 2+P P3 3 d d3 3-4 4x x1 1+2x+2x2 2+d d1 1-d d1 1+=60 =60 x x2 2+d d2 2-d d2 2+=4 =4 8x 8x1 1+6x+6x2 2+d d3 3-d d3 3+=130 =130 2x 2x1 1+4x+4x2 2 48 48 x x1 1，x x2 2，d di i+,
22、d di i-(i=1,2,3)0(i=1,2,3)0c cj j0 00 00 0p p1 1p p1 10 0p p2 2p p3 30 0c cB Bx xB Bbx x1 1x x2 2x x3 3d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+p p1 1d d1 1-6 60 04 42 20 01 1-1 10 00 00 00 00 0d d2 2-4 40 01 10 00 00 01 1-1 10 00 0p p3 3d d3 3-1 13 30 08 86 60 00 00 00 00 01 1-1 10 0 x x3 34 48 82
23、 24 41 10 00 00 00 00 00 0 c cj j -z zj j p p1 1-4 4-2 20 00 02 20 00 00 00 0ORc cj j0 00 00 0p p1 1p p1 10 0p p2 2p p3 30 0c cB Bx xB Bbx x1 1x x2 2x x3 3d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+0 0 x x1 115151 11/21/20 01/41/4-1/41/40 00 00 00 00 0d d2 2-4 40 01 10 00 00 01 1-1 10 00 0p p3 3d d3
24、3-10100 02 20 0-2-22 20 00 01 1-1-10 0 x x3 318180 03 31 1-1/21/21/21/20 00 00 00 0 p p1 10 00 00 01 11 10 00 00 00 0 p p2 20 00 00 00 00 00 01 10 00 0 c cj j-z-zj j p p3 30 0-2-20 02 2-2-20 00 00 01 10000c cj j0 00 00 0p p1 1p p1 10 0p p2 2p p3 30 0c cB Bx xB Bbx x1 1x x2 2x x3 3d d1 1-d d1 1+d d2
25、2-d d2 2+d d3 3-d d3 3+p p1 1d d1 1-6 60 04 42 20 01 1-1 10 00 00 00 00 0d d2 2-4 40 01 10 00 00 01 1-1 10 00 0p p3 3d d3 3-1 13 30 08 86 60 00 00 00 00 01 1-1 10 0 x x3 34 48 82 24 41 10 00 00 00 00 00 0 c cj j -z zj j p p1 1-4 4-2 20 00 02 20 00 00 00 0c cj j0 00 00 0p p1 1p p1 10 0p p2 2p p3 30 0
26、c cB Bx xB Bbx x1 1x x2 2x x3 3d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+0 0 x x1 11 15 51 11 1/2 20 01 1/4 4-1 1/4 40 00 00 00 00 0d d2 2-4 40 01 10 00 00 01 1-1 10 00 0p p3 3d d3 3-1 10 00 02 20 0-2 22 20 00 01 1-1 10 0 x x3 31 18 80 03 31 1-1 1/2 21 1/2 20 00 00 00 0 p p1 10 00 00 01 11 10 00 00
27、00 0 p p2 20 00 00 00 00 00 01 10 00 0 c cj j -z zj j p p3 30 0-2 20 02 2-2 20 00 00 01 1c cj j0 00 00 0p p1 1p p1 10 0p p2 2p p3 30 0c cB Bx xB Bbx x1 1x x2 2x x3 3d d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+0 0 x x1 11 13 31 10 00 01 1/4 4-1 1/4 4-1 1/2 21 1/2 20 00 00 0 x x2 24 40 01 10 00 00 01 1-
28、1 10 00 0p p3 3d d3 3-2 20 00 00 0-2 22 2-2 22 21 1-1 10 0 x x3 36 60 00 01 1-1 1/2 21 1/2 2-3 33 30 00 0 p p1 10 00 00 01 11 10 00 00 00 0 p p2 20 00 00 00 00 00 01 10 00 0 c cj j -z zj j p p3 30 00 00 02 2-2 22 2-2 20 01 100000000 x x1 1*=13=13，x x2 2*=4=4，Z Z=128=128（百元）。百元）。3 31 14 4 目标规划的目标目标规划
29、的目标（1 1）决策人希望恰好实现预定的第）决策人希望恰好实现预定的第i i个目标个目标 MinMin Z Z=d di i+d di i-（2 2）决策人不希望超过预定的第决策人不希望超过预定的第i i个目标个目标 MinMin Z Z=d di i+（3 3）决策人希望超过预定的第决策人希望超过预定的第i i个目标个目标 minmin Z Z=d di i-OR3.23.2整数规划整数规划3 32 21 1整数规划数学模型整数规划数学模型 Max ZMax Z（X X）=c=c1 1x x1 1+c+c2 2x x2 2+c+cn nx xn n a ai1i1x x1 1+a+ai2i2
30、x x2 2+a+ainin x xn n(=,)b(=,)bi i x x1 1，x x2 2，x xn n 0 0 纯整数规划纯整数规划:所有决策变量所有决策变量x xj j(j=1,2,(j=1,2,n),n)均取整数均取整数.混合整数规划混合整数规划:部分决策变量取整数部分决策变量取整数.0-1 0-1整数规划整数规划:所有决策变量只取所有决策变量只取0 0或或1.1.这类变量又称这类变量又称 为逻辑变量为逻辑变量.(i=1,2,i=1,2,m),m)全部或部分为整数全部或部分为整数 OR3.2.23.2.2分枝限界法分枝限界法 例例 Max ZMax Z（X X）=3x=3x1 1+
31、2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14 （A A）：）：2x 2x1 1+x+x2 2 9 9 x x1 1，x x2 2 0 0 且为整数且为整数 解；（解；（1 1）先不考虑变量的整数约束，求解相应的线性规划）先不考虑变量的整数约束，求解相应的线性规划 Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14（B B0 0）：）：2x 2x1 1+x+x2 2 99 x x1 1，x x2 2 0 0ORCX2987654321X1876543210C/9 由于由于x x1 1 ，x x2 2均不满足整数条
32、件均不满足整数条件，故可由，故可由x x1 1（或或x x2 2）进行分枝，使进行分枝，使x x1 1满足满足：x x1 13 3 或或 x x1 144 将将3 3 x x1 14 4 的非整数部分割掉的非整数部分割掉于是问题于是问题B B0 0分成了两个子问题分成了两个子问题B B1 1 ,B B2 2然后分别求出其最优解。然后分别求出其最优解。最优解：最优解：x x1 1=13/4=13/4，x x2 2=5/2=5/2，Z Z0 0=14=143/43/4（2 2）分枝：）分枝：Operational Research Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2
33、 2x 2x1 1+3x+3x2 2 14 14 （B B1 1）：）：2x 2x1 1+x+x2 2 9 9 x x1 1 3 3 x x1 1，x x2 2 0 0 Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14(B(B2 2）：）：2x 2x1 1+x+x2 2 99 x x1 1 44 x x1 1，x x2 2 0 0最优解最优解:X X2 2*=（4 4，1 1）Z Z2 2=14=14 此分枝已查清。此分枝已查清。最优解最优解:X X1 1*=（3 3，8/38/3）Z Z1 1=14=141/31/3 X187
34、6543210Operational ResearchCX2987654321C/ORCX2987654321X1876543210C/（3 3）定界：问题（）定界：问题（B B2 2）已获得整数最优解，已获得整数最优解，可将可将Z Z2 2=14=14作为问题（作为问题（A A）的下界，同时将的下界，同时将 Z Z0 0=14=143/43/4作为问题（作为问题（A A）的上界。可以断定的上界。可以断定 Z Z2 2=14 Z Z=14 Z Z0 0=14=143/43/4（4 4）返回到（返回到（2 2）继续对）继续对B B1 1中的中的x x2 2进行分枝，进行分枝，使使x x2 2满足
35、：满足：x x2 222或或x x2 233 将将2 2 x x2 2 3 3之间的非整数部分割掉之间的非整数部分割掉于是问题于是问题B B2 2又分成了两个子问题又分成了两个子问题B B3 3和和B B4 4再分别求出其最优解再分别求出其最优解.Operational ResearchCX2987654321X1876543210C/Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14 （B B3 3）2x 2x1 1+x+x2 2 9 9 x x1 1 3 3 x x2 2 2 2 x x1 1，x x2 2 0 0 Max Z
36、Max Z（X X）=3x=3x1 1+2x+2x2 2 2x 2x1 1+3x+3x2 2 14 14(B(B4 4）2x 2x1 1+x+x2 2 99 x x1 1 33 x x2 2 33 x x1 1，x x2 2 0 0最优解最优解X X3 3*=（3 3，2 2）Z Z3 3=13=13最优解最优解X X4 4*=（5/25/2，3 3）Z Z4 4=13=131/21/2Operational Research Z Z3 3=13=13和和Z Z4 4=13=131/21/2均小于界值均小于界值Z Z2 2，不可能成为最优值，将不可能成为最优值，将被剪掉（剪枝）。被剪掉（剪枝）
37、。由此可得出问题（由此可得出问题（A A）的最优解就是问题（的最优解就是问题（B B2 2）的最优的最优解。即：解。即：X X*=（4 4，1 1）；）；Z Z（X X*）=14=14OR树状图树状图:B B1 1 x x1 1=3=3，x x2 2=8/3=8/3Z Z1 1=14=141/31/3B B2 2 x x1 1=4=4，x x2 2=1=1Z Z2 2=14=14B B3 3 x x1 1=3=3，x x2 2=2=2Z Z3 3=13=13B B4 4 x x1 1=5/2=5/2，x x2 2=3=3Z Z4 4=13=131/21/2B B0 0 x x1 1=13/4=
38、13/4，x x2 2=5/2=5/2Z Z0 0=14=143/43/4x x2 233x x2 22 2 x x1 144x x1 13 3 OR3.2.33.2.3割平面法割平面法例：例：Max ZMax Z（X X）=3x=3x1 1+2x+2x2 2 2 2x x1 1+3x+3x2 2 14 14 （A A）：）：2x 2x1 1+x+x2 2 99 x x1 1，x x2 2 0 0 且为整数且为整数解解:(1)不考虑其整数条件不考虑其整数条件,用单纯形法求解相应的线性用单纯形法求解相应的线性 规划问题规划问题最终单纯形表如下最终单纯形表如下c cj j3 32 20 00 0c
39、 cB Bx xB Bbx x1 1x x2 2x x3 3x x4 42 2x x2 25/25/20 01 11/21/2-1/21/23 3x x1 113/413/41 10 0-1/41/43/43/4j0 00 0-1/41/4-5/45/4OR（2）构造）构造Gomory约束（割平面）约束（割平面）在最终单纯形表中，任意选择一个非整数变量（如在最终单纯形表中，任意选择一个非整数变量（如x x2 2），写出该变量所在行的方程式：写出该变量所在行的方程式：x x2 2+1/2x+1/2x3 3 1/2x1/2x4 4=5/2=5/2将各变量的系数及常数项分解为整数与非负真分数之和；再
40、将各变量的系数及常数项分解为整数与非负真分数之和；再将系数为整数的变量移到方程式左端，系数为分数的变量移将系数为整数的变量移到方程式左端，系数为分数的变量移到方程式右端到方程式右端 x x2 2 x x4 4-2=1/2-2=1/2-（1/2x1/2x3 3+1/2x+1/2x4 4）Gomory约束为：约束为：1/2-1/2-（1/21/2x x3 3+1/2x+1/2x4 4）00（3）将将Gomory约束化为方程，填入到最终单纯形表中，继约束化为方程，填入到最终单纯形表中，继续求问题的最优解续求问题的最优解ORc cj j3 32 20 00 00 0c cB Bx xB Bbx x1
41、1x x2 2x x3 3x x4 4x x5 52 2x x2 25 5/2 20 01 11 1/2 2-1 1/2 20 03 3x x1 11 13 3/4 41 10 0-1 1/4 43 3/4 40 00 0 x x5 5-1 1/2 20 00 0-1 1/2 2-1 1/2 21 1j0 00 0-1 1/4 4-5 5/4 40 0c cj j3 32 20 00 0c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 42 2x x2 25 5/2 20 01 11 1/2 2-1 1/2 23 3x x1 11 13 3/4 41 10 0-1 1/4
42、 43 3/4 4j0 00 0-1 1/4 4-5 5/4 41/2-1/2-（1/21/2x x3 3+1/2x+1/2x4 4）+x+x5 5=0=0该单纯形表中当前解不可行，而其对偶解满足可行性条该单纯形表中当前解不可行，而其对偶解满足可行性条件件 ，故用对偶单纯形法求解，最终表如下：，故用对偶单纯形法求解，最终表如下：0jORc cj j3 32 20 00 00 0c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4x x5 52 2x x2 22 20 01 10 0-1 11 13 3x x1 17 7/2 21 10 00 01 1-1 1/2 20 0
43、 x x3 31 10 00 01 11 1-2 2j0 00 00 0-1 1-1 1/2 2表中表中x x1 1仍不满足整数条件，返回到（仍不满足整数条件，返回到（2 2）构造构造Gomory约束（割平面）继续求解约束（割平面）继续求解 由：由：x x1 1+x+x4 4-1/2x-1/2x5 5=7/2=7/2 x x1 1+x+x4 4+(-1+1/2)x+(-1+1/2)x5 5=3+1/2=3+1/2得：得：Gomory约束为：约束为：1/2-1/21/2-1/2x x5 50 0 或或 1/2-1/2 1/2-1/2x x5 5+x+x6 6=0=0 将该约束插入上述的最终单纯形
44、表中得：将该约束插入上述的最终单纯形表中得：ORc cj j3 32 20 00 00 00 0c cB Bx xB Bbx x1 1x x2 2x x3 3x x4 4x x5 5x x6 62 2x x2 22 20 01 10 0-1 11 10 03 3x x1 17 7/2 21 10 00 01 1-1 1/2 20 00 0 x x3 31 10 00 01 11 1-2 20 00 0 x x6 6-1 1/2 20 00 00 00 0-1 1/2 21 1j0 00 00 0-1 1-1 1/2 20 0c cj j3 32 20 00 00 00 0c cB Bx xB
45、Bbx x1 1x x2 2x x3 3x x4 4x x5 5x x6 62 2x x2 21 10 01 10 0-1 10 02 23 3x x1 14 41 10 00 01 10 0-1 10 0 x x3 33 30 00 01 11 10 0-4 40 0 x x5 51 10 00 00 00 01 1-2 2j0 00 00 0-1 10 0-1 1OR 最优解最优解X X*=（4 4，1 1）；）；Z Z（X X*）=14=14 3.2.4 0-13.2.4 0-1规化规化3 32 24 41 0-11 0-1规划问题及其数学模型规划问题及其数学模型3 32 24 42 0
46、-12 0-1规划的隐枚举解法规划的隐枚举解法例例 MaxZMaxZ（X X）=3x=3x1 1-2x-2x2 2+5x+5x3 3 x x1 1+2x+2x2 2-x-x3 3 2 2 x x1 1+4x+4x2 2+x+x3 3 4 4 x x1 1+x+x2 2 3 3 4x 4x2 2+x+x3 3 6 6 x x1,1,x x2,2,x x3 3=0=0 或或 1 1解：首先通过试探的方法找出一个可行解解：首先通过试探的方法找出一个可行解 X X=（x x1,1,x x2,2,x x3 3）=（1 1，0 0，0 0）Z Z（X X）=3x=3x1 1-2x-2x2 2+5x+5x3
47、 3=3=3 增加约束：增加约束：3 3x x1 1-2x-2x2 2+5x+5x3 3 3 3（称为过滤条件称为过滤条件）OR迭迭代代(x x1 1,x x2 2,x x3 3）满满足足条条件件Y Y（）N N（）Z1 1（0 0，0 0，0 0）2 2（0 0，0 0，1 1）3 3（0 0，1 1，0 0）4 4（0 0，1 1，1 1）5 5（1 1，0 0，0 0）6 6（1 1，0 0，1 1）7 7（1 1，1 1，0 0）8 8（1 1，1 1，1 1）例例 MaxZMaxZ（X X）=3x=3x1 1-2x-2x2 2+5x+5x3 3 x x1 1+2x+2x2 2-x-x
48、3 3 2 2 x x1 1+4x+4x2 2+x+x3 3 4 4 x x1 1+x+x2 2 3 3 4x 4x2 2+x+x3 3 6 6 x x1,1,x x2,2,x x3 3=0=0 或或 1 1626N8021Y11N31110Y315N5-1101Y5-2N0N将不满足过滤条件的将不满足过滤条件的X X全部过滤掉，见下表全部过滤掉，见下表38OR迭代迭代（x x2,2,x x1,1,x x3 3）满足条件满足条件Y Y（）（）N N（）（）Z1 1（0 0，0 0，0 0）0 0N N2 2（0 0，0 0，1 1）5 5-1-11 10 01 1Y Y5 5改进过滤条件：改进
49、过滤条件：-2-2x x2 2+3x+3x1 1+5x+5x3 3 5 5 迭代迭代（x x2,2,x x1,1,x x3 3）满足条件满足条件Y Y（）（）N N（）（）Z3 3（0 0，1 1，0 0）3 3N N4 4（0 0，1 1，1 1）8 80 02 21 11 1Y Y8 8改进过滤条件：改进过滤条件：-2-2x x2 2+3x+3x1 1+5x+5x3 3 8 8 注意：注意：（1 1）为进一步减少计算工作量，可及时改进过）为进一步减少计算工作量，可及时改进过滤条件。滤条件。（2 2）价值系数按递增排列，）价值系数按递增排列，如如 MaxZMaxZ（X X）=-2x=-2x2
50、 2+3x+3x1 1+5x+5x3 3 迭代迭代(x x1,1,x x2,2,x x3 3）满足条件满足条件Y Y（）（）N N（）（）Z5 5（1 1，0 0，0 0）-2-2N N6 6（0 0，0 0，1 1）3 3N N7 7（1 1，1 1，0 0）1 1N N8 8（1 1，1 1，1 1）6 6N NX*=(1,0,1)Z=8OROperational Research3 32 25 5分派问题（分派问题（Assignment problemAssignment problem）一般描述一般描述:有有n n项任务项任务,指派指派n n个人个人(广义广义)去完成去完成,第第i i
