16 单纯形表运算 000P1P20P。0P40Ps0 d RHS 比值 000000 80 0a2300016313000011 80/(2/3) 50030 3 001253512531-100 0450004500065003 4 d4 100 200 200/1 0 2/31001/3-1/30000 200200(2/3) P 00测 001000 0 011 检验数P3 000 013812380 0010 0 00 00 00000001 P4-10 0000 0000000 P0000000000
Page:16 QSC 华东理工大学 工商经济学院 运筹学 单纯形表运算 0 0 0 P1 P2 0 P3 0 P4 0 P5 0 x1 x2 d1 - d1 + d2 - d2 + d3 - d3 + d4 - d4 + d5 - d5 + RHS 比 值 0 0 0 1 -1 -1 1 0 0 0 0 0 0 8 0 - 0 2/3 0 0 0 1/3 -1/3 0 0 0 0 -1 1 8 0 80/(2/3) P3 500/3 0 0 0 -125/3 -125/3 1 -1 0 0 0 0 45000 45000/(500/3 ) P4 1 0 0 0 0 0 0 0 1 -1 0 0 200 200/1 0 2/3 1 0 0 1/3 -1/3 0 0 0 0 0 0 200 200/(2/3) P1 0 0 0 1 0 0 0 0 0 0 0 0 P2 0 0 0 0 1 1 0 0 0 0 0 0 P3 -500/3 0 0 0 125/3 125/3 0 1 0 0 0 0 P4 -1 0 0 0 0 0 0 0 0 1 0 0 P5 0 0 0 0 0 0 0 0 0 0 1 0 d3 - d1 - d5 + d4 - x2 检验数 …
17 07 数这 公 线性规划 筹 学
Page :17 QSC 华东理工大学 工商经济学院 运筹学 运筹学 整数线性规划
18 整数线性规划问题的一般形式 max(min) Z=c1X1+c2X,+…CnⅩ nn aux t x2+…·a1,X 2~2 (=.≥ 21 222 +…a2nxn≤(=2)b2 st x1+anm2x2+…mnxn≤(=.≥)b x1,x…,x中部分或全部取整数
Page:18 QSC 华东理工大学 工商经济学院 运筹学 整数线性规划问题的一般形式 max(min) z = c1 x1 + c2 x2 ++c n xn + + = + + = + + = m m m n n m n n n n a x a x a x b a x a x a x b a x a x a x b st ( . ) ( . ) ( . ) . . 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 x1 , x1 , xn 中部分或全部取整数
整数线性规划问题的分类 全整数线性规划 混合整数线性规划 >0-1整数线性规划
Page:19 QSC 华东理工大学 工商经济学院 运筹学 整数线性规划问题的分类 ➢全整数线性规划 ➢混合整数线性规划 ➢0-1整数线性规划
整数规划与其松弛问题 当放弃整数约束时得到的线性规 划称为整数规划的松弛问题 整数规划的可行域是松弛问题的 可行域,反之不成立
Page:20 QSC 华东理工大学 工商经济学院 运筹学 整数规划与其松弛问题 当放弃整数约束时得到的线性规 划称为整数规划的松弛问题。 整数规划的可行域是松弛问题的 可行域，反之不成立