凌晨: 节单形法的代数说明 四、基解( basic solution) 1、定义:在m个方程、n个变量之线性方程组中 若令n-m个变量为0,然后求出的线性方程 组解称为基解,其中被令成0的变量称为非基 变量,没有被令成0的变量称为基变量 2、上例中,m=3,n=5,令(实际上可以任选2 个):X2 0,s1=0,代入方程组易得 X1=50,x2=0,S1=0,S2=20, 100 即为LP问题一个基解,不过,非可行解
Ling Xueling 四、基解（basic solution） 1、定义：在 m 个方程、n 个变量之线性方程组中 若令 n－m 个变量为 0，然后求出的线性方程 组解称为基解，其中被令成 0 的变量称为非基 变量，没有被令成 0 的变量称为基变量 2、上例中，m = 3，n = 5，令（实际上可以任选 2 个）：x2 = 0，s1 = 0，代入方程组易得： x1 = 50，x2 = 0，s1 = 0，s2 = 20，s3 = －100 即为 L.P. 问题一个基解，不过，非可行解！ 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法的代数说明 五、基可行解 1、定义:满足非负要求的基解称为基可行解 很明显,我们要的是基可行解,是最优的基可行解 2、上例中,若令x1=0,x2=0,则可得基解: X1=0,X2=0,s1=150,S2=20,S3=300 正是一个基可行解!称之为初始基可行解 3、基可行解的几何解释 作出本LP问题的可行区域,可见: 0 0正是可 行域的端点(1)!这不是偶然的,我们有一般的结论
Ling Xueling 五、基可行解 1、定义：满足非负要求的基解称为基可行解 很明显，我们要的是基可行解，是最优的基可行解 2、上例中，若令 x1 = 0，x2 = 0，则可得基解： x1 = 0，x2 = 0，s1 = 150，s2 = 20，s3 = 300 正是一个基可行解！称之为初始基可行解 3、基可行解的几何解释 作出本 L.P. 问题的可行区域，可见： x1 = 0，x2 = 0 正是可 行域的端点（1）！这不是偶然的，我们有一般的结论。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 五、基可行解 4、可行域及其初始基可行解的图形表示 (3) 端点(1)即为初始基可行解
Ling Xueling 五、基可行解 4、可行域及其初始基可行解的图形表示： 端点（1）即为初始基可行解。 第二节 单形法用于最简单例子 凌晨: 凌晨: (1) (2) (3) (4) (5)
凌晨: 节单形法的代数说明 五、基可行解 5、定理 LP.问题中,约束线性方程组的基可行解就是其可行域的 端点,反之亦然 6、定理 P问题最优解必是基可行解中的一个 7、单形法的迭代 从任意一个初始基可行解出发(只要令n-m个变量为零即 可),在不断改善目标函数前提下,设法将其变化(迭代 )成另一个基可行解,直至求出最优的
Ling Xueling 五、基可行解 5、定理一 L.P. 问题中，约束线性方程组的基可行解就是其可行域的 端点，反之亦然 6、定理二 L.P. 问题最优解必是基可行解中的一个 7、单形法的迭代 从任意一个初始基可行解出发（只要令 n-m 个变量为零即 可），在不断改善目标函数前提下，设法将其变化（迭代 ）成另一个基可行解，直至求出最优的。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 LP.的表格形式 表格形式的意义 将LP.模型化成表格形式,可为单形法迅速提供一个初始基 可行解!然后才开始迭代过程 2、例子 max50x1+40x2+0s1+0s2+0s3(5.1) 3x1+5X2+s 150 (5.2) 20 8x 300 (5.4) ≥0 注意上例中,基变量s的系数阵是一个单位阵
Ling Xueling 一、L.P. 的表格形式 1、表格形式的意义 将 L.P. 模型化成表格形式，可为单形法迅速提供一个初始基 可行解！然后才开始迭代过程 2、例子 max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1) s.t. 3x1 + 5x2 + s1 = 150 (5.2) x2 + s2 = 20 (5.3) 8x1 + 5x2 + s3 = 300 (5.4) x1，x2，s1，s2，s3 0 注意上例中，基变量 si 的系数阵是一个单位阵。 第二节 单形法用于最简单例子 凌晨: 凌晨: