第一章_管理运筹学——线性规划.ppt

（2） 某列Pj→ Pj′（只考虑非基向量情形） 问题：改变后是否影响最优基（解）、有利？ 方法： 只需计算 ，则有利 ，则不利 §5 整数规划 Integer Programming(简称IP) 一、　整数规划的一般模型 LP: max z=CX AX=b X≥0 IP: max z=CX AX=b X≥0 X为整数 整数规划的解法：分枝定界法或割平面法 基本思想是把一个整数规划问题化为一系列的线性规划问题来求解 整数规划的分类： 纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数 0-1整数规划：变量的取值仅限于0或1 σ θ x5 x4 x3 x2 x1 B-1b CB XB 四、单纯形法的实现——单纯形表 例：煤电油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 s.t. Max Z=7 x1 +12x2 9 x1 +4x2 +x3 =360 4x1 +5x2 +x4 = 200 3 x1 +10x2 +x5 = 300 x1 ,…,x5≥0 s.t. 化为标准型 x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 θ的计算: 40 30 σ θ x5 x4 x3 x2 x1 B-1b CB XB 四、单纯形法的实现——单纯形表 例：煤电油例 Max Z=7 x1 +12x2 9 x1 +4x2≤360 4x1 +5x2 ≤200 3 x1 +10x2 ≤300 x1 , x2≥0 s.t. Max Z=7 x1 +12x2 9 x1 +4x2 +x3 =360 4x1 +5x2 +x4 = 200 3 x1 +10x2 +x5 = 300 x1 ,…,x5≥0 s.t. 化为标准型 x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 40 30 [ ] 枢纽元素 σ θ x5 x4 x3 x2 x1 B-1b CB XB x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 40 30 [ ] x3 x4 x2 0 0 12 30 0.3 1 0 0 0.1 σ 以10为主元进行初等行变换 50 2.5 0 0 1 -0.5 240 7.8 0 1 0 -0.4 3.4 0 0 0 -1.2 即: σ θ x5 x4 x3 x2 x1 B-1b CB XB x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 40 30 [ ] x3 x4 x2 0 0 12 30 0.3 1 0 0 0.1 σ 以10为主元进行初等行变换 50 2.5 0 0 1 -0.5 240 7.8 0 1 0 -0.4 3.4 0 0 0 -1.2 即: 30.8 20 100 σ θ x5 x4 x3 x2 x1 B-1b CB XB x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 40 30 [ ] x3 x4 x2 0 0 12 30 0.3 1 0 0 0.1 σ 以10为主元进行初等行变换 50 2.5 0 0 1 -0.5 240 7.8 0 1 0 -0.4 3.4 0 0 0 -1.2 30.8 20 100 [ ] x3 x1 x2 0 7 12 24 0 1 0 -0.12 0.16 σ 20 1 0 0 0.4 -0.2 84 0 0 1 -3.12 1.16 0 0 0 -1.36 -0.52 σ σ θ x5 x4 x3 x2 x1 B-1b CB XB x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 单纯形表: 7 90 40 30 [ ]