1-4-线性规划-大M法、两阶段法与几种特殊情况

1、1 1-4 1-4 线性规划线性规划- - 大大M M法、两阶段法及几种特殊情况法、两阶段法及几种特殊情况 2021/3/10 School of Business ECUST o3.3 3.3 单纯形法单纯形法 o 3.3.1 3.3.1 单纯形法的一般思路单纯形法的一般思路+ +例子例子 o 3.3.2 3.3.2 单纯形表结构单纯形表结构+ +例子例子 o 3.3.3 3.3.3 单纯形法的计算步骤单纯形法的计算步骤 o 3.3.4 3.3.4 单纯形法的矩阵描述单纯形法的矩阵描述 o 3.4 3.4 大大MM法法 o 3.5 3.5 两阶段法两阶段法 o4 4 几种特殊情况几种特殊情况

2、 o 4.1 4.1 无可行解无可行解 o 4.2 4.2 无界解无界解 o 4.3 4.3 多重最优解多重最优解 o 4.4 4.4 进基变量的相持进基变量的相持 o 4.5 4.5 出基变量的相持出基变量的相持 School of Business ECUST 3.4 3.4 大大M M法法 一般问题的初始基本可行解一般问题的初始基本可行解 maxz=4x1+2x2-3x3+5x4 s.t. 2x1-x2+x3+2x450(1) 3x1 -x3+2x480(2) x1+x2 +x4=60(3) x1,x2,x3,x40 School of Business ECUST 标准化标准化 max

3、z=4x1+2x2-3x3+5x4 s.t.2x1-x2+x3+2x4x5=50(1) 3x1-x3+2x4+x6=80(2) x1+x2+x4 =60(3) x1,x2,x3,x4,x5,x60 School of Business ECUST 添加人工变量添加人工变量 maxz=4x1+2x2-3x3+5x4 -Mx7-Mx8 s.t. 2x1-x2+x3+2x4x5 +x7 =50(1) 3x1 -x3+2x4 +x6 =80(2) x1+x2 +x4 x8=60(3) x1,x2,x3,x4,x5,x6,x7,x80 School of Business ECUST 添加人工变量添加人

4、工变量 minz=4x1+2x2-3x3+5x4 +Mx7+Mx8 s.t. 2x1-x2+x3+2x4x5 +x7 =50(1) 3x1 -x3+2x4 +x6 =80(2) x1+x2 +x4 x8=60(3) x1,x2,x3,x4,x5,x6,x7,x80 School of Business ECUST 42-3500MM B C B X 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x b M 7 x 2-112-101050 0 6 x 30-12010080 M 8 x 1101000160 j 4-3M2-3-M 5-3MM000 School of Busin

5、ess ECUST 12 12 12 2 12 max2 2 -1 3 ,0 Zxx xx xx x x x 解：首先将原LP问题转化为标准型，引入非负变量x3，x4，x5 12 123 124 25 - 2 - - 1 3 0,1,2,3,4 ax , m 5 2 j Z xxx xxx xx x x j x 例：考虑下面的LP问题 School of Business ECUST 12 123 124 25 - 2 - - 1 3 0,1,2,3,4 ax , m 5 2 j Z xxx xxx xx x x j x 系数矩阵： 111 0 0 1 101 0 0100 1 A 初始可行基

6、？初始可行基？ 大大M法：构造一个单位矩阵来作初始可行基法：构造一个单位矩阵来作初始可行基 如何构造？如何构造？ 通过添加人工变量通过添加人工变量 School of Business ECUST 12 123 124 25 - 2 - - 1 3 0,1,2,3,4 ax , m 5 2 j Z xxx xxx xx x x j x 添加人工变量x6, x7 1236123 1247124 2525 - 2 - 2 - - 1- - 1 3 3 0,1,2,3,4,5 0,1,2,.,7 jj xxxxxxx xxxxxxx xxxx xjxj School of Business ECUS

7、T 添加人工变量之后，系数矩阵变为： 111 0 0 1 0 1 101 0 01 0100 10 0 A 单位矩阵，单位矩阵， 可作初始可行基可作初始可行基 变量x6, x7是为了构造单位阵，而人为增加的，要保证最优解 满足原约束，在问题的最优解中，这两个变量必须取0值。 为了达到这种效果，我们将目标函数改写为： 1267 max2ZxxMxMx 其中，M为充分大的正数 显然，为了保证 Z取最大值，x6, x7 必然取0 School of Business ECUST 1236123 12126 1247124 252 7 5 - 2 - 2 - - 1- - 1 3 3 0,1,2,3,

8、4,5 0,1,2,. max2max2 . jj xxxxxxx xxxxxxx xxxx x ZxxZxxMxMx jxj ,7 为什么可以这样转化？为什么可以这样转化？ 1234567 , T Xx x x x x x x =0 =0 原问题的最优解原问题的最优解 School of Business ECUST - 0 1 -1/2 -1/2 0 1/2 1/23/2X22 1 0 -1/2 1/2 0 1/2 -1/21/2X1-1 - -1 1 0 -1 0 0 11X22 1/2 2 0 -1 1 0 1 -11X6-M 1/1 -1 1 0 -1 0 0 11X7-M 2/1

9、1 1 -1 0 0 1 02X6-M 0 0 1/2 3/2 0 -1/2-M -3/2-Mj 0 0 1/2 1/2 1 -1/2 -1/23/2 X5 0 1+2M 0 -M 2+M 0 0 -2-2Mj 2/1 1 0 0 1 1 0 -12 X5 0 -1 2+2M -M -M 0 0 0 j 3/1 0 1 0 0 1 0 03 X5 0 X1 x2 x3 x4 x5 x6 x7 b XBCB -1 2 0 0 0 -M -MC School of Business ECUST 0 1 0 0 1 0 03X22 1 0 0 1 1 0 -12X40 1 1 -1 0 0 1 02

10、X22 2 0 -1 1 0 1 -11X40 - 0 1 -1/2 -1/2 0 1/2 1/23/2X22 1/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2X1-1 -1 0 0 0 -2 -M -Mj -1 0 1 0 1 -1 01X30 -3 0 2 0 0 -2-M -Mj -1 0 1 0 1 -1 01X50 0 0 1/2 3/2 0 -1/2-M -3/2-Mj 3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2X50 X1 x2 x3 x4 x5 x6 x7bXBCB -1 2 0 0 0 -M -MC 最优解最优解 最优值最优值

11、X0,3,1,2,0 T Z6 School of Business ECUST 大M法的基本步骤 o 通过加入人工变量，构造初始可行基； o 在目标函数中赋予人工变量很大的罚系数M，建立 辅助线性规划问题； o 利用单纯形法，求解上述辅助线性规划问题，若： n有最优解：如果最优解的基变量中不含有非零人工变量， 则最优解中剔除掉人工变量部分，构成原问题的最优解； 如果最优解的基变量中仍含有非零人工变量，则原问题无 可行解； n无界解：如果最终单纯形表中基变量不含有非零人工变量， 则原问题为无界解；否则，如果最终单纯形表中基变量含 有非零人工变量，则原问题为无可行解。 School of Bus

12、iness ECUST School of Business ECUST 例：求解下列线性规划问题例：求解下列线性规划问题 123 123 13 23 123 min Z=3x +2x +x xxx6 x -x4 . . x -x3 x ,x ,x 0 st 12378 1234 1357 2368 MMmaxZ = -3x -2x -x - x - x x +x +x +x =6 x -x -x +x =4 x -x -x +x =3 xj0, j=1,2,8. 引入人工变量，引入人工变量， 并利用大并利用大M M法求解法求解 78 x ,x 123 1234 135 236 maxZ =

13、-3x -2x -x x +x +x +x =6 x -x -x =4 x -x -x =3 xj0, j=1,2,6. 解：解： 首先将问题化为标准型首先将问题化为标准型 School of Business ECUST C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0 -M -M x4 x7 x8 6 4 3 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6/1 - 3/1 Z -3+M -2+M -1-2M 0 -M -M 0 0 0 -M -2 x4 x7 x2 3

14、 4 3 1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 3/1 4/1 - Z Z -3+M 0 -3-M 0 -M -2 0 2-M -3 -M -2 x1 x7 x2 3 1 3 1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人 工变量工变量x7=1为基变量，所以原线性规划不存在可行解。为基变量，所

15、以原线性规划不存在可行解。 School of Business ECUST o 例 求解下列线性规划问题： 12 12 12 12 max 0.54 . .3 ,0 zxx xx stxx x x 12 123 124 1234 max 0.54 . .3 ,0 zxx xxx stxxx x x x x 1256 1235 1246 123456 max 0.54 . .3 ,0 zxxMxMx xxxx stxxxx x x x x x x 变标准型 添加人工变量 利用大M法 School of Business ECUST C x1x2x3x4x5x6 1-100-M-M 0.51-1

16、0104 110-1013 XB x5 x6 CB -M -M 1+1.5M2M-1-M-M00 b 4/1 3/1 -0.50-111-11 110-1013 x5 x2 -M -1 1/1 - 2-0.5M0-M-1+M01-2M -0.50-111-11 0.51-10104 x4 x2 0 -1 - 4/0.5 1.50-101-M-M School of Business ECUST -0.50-111-1 0.51-1010 x4 x2 0 -1 1 4 - 4/0.5 1.50-101-M-M C x1x2x3x4x5x6 1-100-M-M XB CBb 01-212-15 1

17、2-20208 x4 x1 0 1 0-320-M-2-M 非基变量x3对应的检验数0, 并且该非基变量对应的系数列向 量的全部系数00， 技术系数均技术系数均 0 0 School of Business ECUST 4.3 4.3 无穷多（多重）最优解无穷多（多重）最优解 maxz=8x1+5x2 s.t. 3x1+5x2150(1) x220(2) 8x1+5x2300(3) x1,x20 School of Business ECUST 85000 x1x2x3x4x5 RHS 比值比值 035100150 150/3 00101020 - 085001300 300/8 85000

18、x5 检验数检验数 x3 x4 当前基本可行解：当前基本可行解：(0,0,150,20,300),Z=0 School of Business ECUST 85000 x1x2x3x4x5 RHS 比值比值 0025/810-3/875/2 00101020 815/8001/875/2 0 000-1 x3 x4 x1 检验数检验数 当前基本可行解：当前基本可行解：(75/2,0,75/2,20,0),Z=300 School of Business ECUST 85000 x1x2x3x4x5 RHS 比值比值 5018/250-3/2512 000-8/2513/258 810-5/25

19、05/2530 0 000-1 x1 检验数检验数 x2 x4 当前基本可行解：当前基本可行解：(30,12,0,8,0),Z=300 School of Business ECUST 无穷多最优解的判别准则无穷多最优解的判别准则 所有检验数所有检验数 存在非基变量，检验数存在非基变量，检验数=0=0 School of Business ECUST o 解的判别： n若 是对应于基B Bk = (P1,P2, ., Pm)的 基可行解，对于一切 j = m+1,.,n, 均有检验数 ，则 为最优解； n若 是对应于基 B Bk = (P1,P2, ., Pm)的基 可行解，对于一切 j = m+1,.,n, 均有检验数 ，并且 存在某个非基变量(比如xm+r)的检验数 ，则该线性规 划问题有无穷多最优解； n若 是对应于基 B Bk = (P1,P2, ., Pm)的基 可行解，若存在某个非基变量(比如xm+r)的检验数 ， 并且对i=1,2,m, 均有 ，则该线性规划问题有无界 解(无最优解)。 12 ,.,0,.,0 T k m Xb bb k X 0 j 12 ,.,0,.,0 T k m Xb bb 0 j 0 m r 12 ,.,0,.,0 T k m