凌晨: 节单形法用于最简单例子 一、LP的表格形式 3、表格形式定义 LP.约束式化成线性方程组后若满足 )每一个方程中,某个基变量系数是1,其余基变量系数是0 2)所有方程中,系数为1的基变量只能在一个方程中出现 3)所有方程中,右手边值皆非负 则称LP问题已经表格化了,是表格形式 说明:上述1)和2)—一保证基变量系数阵是单位阵 保证基解容易获得 LP.中若所有约束式都是“≤”且右手边值皆非负,则 其 标准形与表格形式一致
Ling Xueling 一、L.P. 的表格形式 3、表格形式定义 L.P. 约束式化成线性方程组后若满足 1）每一个方程中，某个基变量系数是1，其余基变量系数是0 2）所有方程中，系数为 1 的基变量只能在一个方程中出现 3）所有方程中，右手边值皆非负 则称 L.P. 问题已经表格化了，是表格形式 说明：上述 1）和 2）－－保证基变量系数阵是单位阵 －－保证基解容易获得 L.P. 中若所有约束式都是“ ”且右手边值皆非负，则 其 标准形与表格形式一致。 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 二、建立初始单形表 1、定义 将LP.表格形式中的系数所构成的如下形式之表格 C行 A矩阵 b列 称为初始单形表 例如,前述例子的初始单形表是 5040 308 0-100 0010 000 150 20 300
Ling Xueling 二、建立初始单形表 1、定义 将 L.P. 表格形式中的系数所构成的如下形式之表格 C 行 A 矩阵 b 列 称为初始单形表 例如，前述例子的初始单形表是 x1 x2 s1 s2 s3 50 40 0 0 0 3 5 1 0 0 150 0 1 0 1 0 20 8 5 0 0 1 300 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 建立初始单形表 2、求一个初始基可行解 对表格形式来说,因为基变量下的系数刚好构成一个 单位阵,所以基变量的取值也就由b列数值所给出, 可见:在所谓表格形式中的确很容易求出基可行解 单形法求解的思路 不断(令非基变量为0)求出新的基可行解以使of 的值更加理想,具体来说,就是不断“换基”:选择 个当前的非基变量入基的同时,选择一个当前的基 变量出基,逐步改善of值
Ling Xueling 二、建立初始单形表 2、求一个初始基可行解 对表格形式来说，因为基变量下的系数刚好构成一个 单位阵，所以基变量的取值也就由 b 列数值所给出， 可见：在所谓表格形式中的确很容易求出基可行解 单形法求解的思路： 不断（令非基变量为 0）求出新的基可行解以使 o.f. 的值更加理想，具体来说，就是不断“换基”：选择 一个当前的非基变量入基的同时，选择一个当前的基 变量出基，逐步改善 o.f. 值。 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 建立初始单形表 3、单形表的完善 增加:1)基的表达十2)设立检验行+3)反映出of 当前基 BaSic CB 5040 b 000 010000 0-01000 000100 150 308-0 5150 20 300 5040 检验行
Ling Xueling 二、建立初始单形表 3、单形表的完善 增加：1）基的表达 ＋ 2）设立检验行 ＋ 3）反映出 o.f. 当前基 x1 x2 s1 s2 s3 C 行 Basic CB 50 40 0 0 0 b s1 0 3 5 1 0 0 150 s2 0 0 1 0 1 0 20 s3 0 8 5 0 0 1 300 Zj 0 0 0 0 0 0 Cj － Zj 50 40 0 0 0 o.f. 检验行 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 建立初始单形表 4、完善的单形表的说明 )Z行的计算 CB列中的元素与其在A阵中第j列元素两两对应相乘后再全 部相加 2)C;-Z;行的意义 对应A的第j列变量在解中每增加一个单位时,of的净变化 检验行 3)o.f.的计算 B(当前基之系数)与b列系数两两相乘后相加所得
Ling Xueling 二、建立初始单形表 4、完善的单形表的说明 1）Zj 行的计算 CB 列中的元素与其在 A 阵中第 j 列元素两两对应相乘后再全 部相加 2）Cj －Zj 行的意义 对应 A的第 j 列变量在解中每增加一个单位时，o.f. 的净变化 －－检验行 3）o. f. 的计算 CB （当前基之系数）与 b 列系数两两相乘后相加所得。 第二节 单形法用于最简单例子 凌晨: 凌晨: