凌晨: 节单形法用于最简单例子 迭代( iteration) 1、概念 迭代一一换基:选入基变量,同时选出基变量 是否迭代的依据:观察C;-Z;值,正值,说明x入基可以使 得of.增加,所以应当选为入基变量。得如下的: 2、选入基变量 由C;一Z;之意义,可知变量是否入基的标准是: 0且使maxC-Z}对应之
Ling Xueling 三、迭代（iteration） 1、概念 迭代－－换基：选入基变量，同时选出基变量 是否迭代的依据：观察 Cj －Zj 值，正值，说明 xi 入基可以使 得 o.f. 增加，所以应当选为入基变量。得如下的： 2、选入基变量 由 Cj －Zj 之意义，可知变量是否入基的标准是： Cj －Zj > 0 且使 max {Cj －Zj } 对应之 j 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 迭代( iteration) 3、选出基变量 1)原则 要使入基变量尽可能大!以使对of.的贡献尽量大 2)求法 (1)设入基变量在第j列,则对A之第j列a 对a1>0(否则不予理会),求b;/a;(i=1,2,……) (2)在诸b;/a;中求出最小的一个,其所在的第i行对 应的变量即为出基变量 具体例子参见下页
Ling Xueling 三、迭代（iteration） 3、选出基变量 1）原则 要使入基变量尽可能大！以使对 o.f. 的贡献尽量大 2）求法 （1）设入基变量在第 j 列，则对 A 之第 j 列 a i j : 对 a i j > 0（否则不予理会），求 b i / a i j （i = 1,2, ......) （2）在诸 b i / a i j 中求出最小的一个，其所在的第 i 行对 应的变量即为出基变量 具体例子参见下页。 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 迭代( Iteration) Basic 50400 0 0 bbi/ail 0150150/3 0 0 0 020 085001300300/8 0 0 0 50400 0 说明:对应入基变量的列一一枢列 对应出基变量的行一一枢行; 枢行与枢列交叉处的元素称为枢元( pivot)(=8)
Ling Xueling 三、迭代（iteration） x1 x2 s1 s2 s3 Basic CB 50 40 0 0 0 b bi / ai1 s1 0 3 5 1 0 0 150 150/3 s2 0 0 1 0 1 0 20 － s3 0 8 5 0 0 1 300 300/8 Zj 0 0 0 0 0 0 Cj － Zj 50 40 0 0 0 说明：对应入基变量的列－－枢列； 对应出基变量的行－－枢行； 枢行与枢列交叉处的元素称为枢元（pivot）( = 8) 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 迭代( iteration) 4、改善初始可行解的想法 已得:让s3出基,x1入基,可使of改善300/8=37个单位 300若通过换基,可以使得o得到改孝150,S2=20,s3 即:当前初始可行解x1=0,x2=0,s1 可题:新的基可行解是什么呢?x1=? 答:当基变量所对应的系数列是单位向量时,才能使在初始 单形表中容易地求出基可行解,所以,为了方便地求出新的 基可行解,需要对(AB)通过初等变换使得x1所在之列系数 变成原基变量s3原先所在列的系数(001)
Ling Xueling 三、迭代（iteration） 4、改善初始可行解的想法 已得：让 s3 出基，x1 入基，可使 o.f. 改善 300/8 = 37.5个单位 即：当前初始可行解 x1 = 0，x2 = 0，s1 = 150，s2 = 20，s3 = 300 若通过换基，可以使得 o.f. 得到改善 问题：新的基可行解是什么呢？x1 = ? 答：当基变量所对应的系数列是单位向量时，才能使在初始 单形表中容易地求出基可行解，所以，为了方便地求出新的 基可行解，需要对 (AB) 通过初等变换使得 x1 所在之列系数 变成原基变量 s3 原先所在列的系数 ( 0 0 1) T 。 第二节 单形法用于最简单例子 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 迭代( iteration) 5、初等变换改善初始可行解 1)目标 使得新的基变量对应于原来的基变量所对应的单位向量 2)要求 不管怎么变换,都要使新的表格是原约束线性方程组的等价 系统 3)初等行变换 非零常数乘以任意一行、某行的倍数加至另一行 注意:施用初等变换时,右手边数值b;也要跟着变 变换从枢行除以枢元开始,如下图所示
Ling Xueling 三、迭代（iteration） 5、初等变换改善初始可行解 1）目标 使得新的基变量对应于原来的基变量所对应的单位向量 2）要求 不管怎么变换，都要使新的表格是原约束线性方程组的等价 系统 3）初等行变换 非零常数乘以任意一行、某行的倍数加至另一行 注意：施用初等变换时，右手边数值 b i 也要跟着变！ 变换从枢行除以枢元开始，如下图所示。 第二节 单形法用于最简单例子 凌晨: 凌晨: