运筹学 单纯形法表格形式

P79 用单纯形法的表格形式求解第二章例 用单纯形法的表格形式求解第二章例 1 1 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CBb 比比 值值 j z 0 jjj zc 在上表中有一个 m m 的单位矩阵 对应的基变量为 s1 s2 s3 在在 s1 s2 s3右边的右边的 CB列中填入这些基列中填入这些基 变量的目标函数中相应的系数 变量的目标函数中相应的系数 2 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S1011100300 S2021010400 S3001001250 j z 0 jjj zc 在在 zj行中填入第行中填入第 j 列与列与 cB列中列中 对应的元素相乘相加所得的值 如对应的元素相乘相加所得的值 如 z2 0 1 0 1 0 1 0 所在 所在 zi行中的第行中的第 2 位数填入位数填入 0 在在 行中填入行中填入 cj zj所得所得 jjj zc 的值 如的值 如 050c 111 z 0100 2 00 3 00 4 00 5 z 表示把初始基本可行解代入目表示把初始基本可行解代入目 标函数求得的目标函数值 即标函数求得的目标函数值 即 b 列列 cB 列 列 3 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S1011100300 S2021010400 S3001001250 j z00000 0 jjj zc 4 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S1011100300 S2021010400 S3001001250 j z00000 0 jjj zc 50100000 5 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S1011100300 S2021010400 S3001001250 j z00000 0 jjj zc 50100000 Z 0 6 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50 100000 b比值比值 S1011100300 300 1 S2021010400 400 1 S300 1 001250 250 1 j z00000 0 jjj zc 50 100000 Z 0 初始基本可行解为初始基本可行解为 s1 300 s2 400 s3 250 x1 0 x2 0 由于由于 250 1 最小 因此确定最小 因此确定 s3 为出基变量 为出基变量 由于由于 因此确定 因此确定 x2为为1 2 入基变量 出基变量所在行 入基变量入基变量 出基变量所在行 入基变量 所在列的交汇处为主元 这里是所在列的交汇处为主元 这里是 a32 1 在表中画圈以示区别 在表中画圈以示区别 7 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S1011100300 S2021010400 X210001001250 j z 1 jjj zc 第一次迭代 其变量为第一次迭代 其变量为 x2 s1 s2 通通 过矩阵过矩阵行的初等变换行的初等变换 求出一个新的 求出一个新的 基本可行解 基本可行解 具体的做法 具体的做法 用行的初等变换使用行的初等变换使 得得 x2的系数向量的系数向量 p2变换成单位向量 变换成单位向量 由于主元在由于主元在 p2的第的第 3 分量上 所以分量上 所以 这个单位向量是这个单位向量是 也就是主 也就是主 T e1 0 0 3 元素变成元素变成 1 在上表中第在上表中第 3 个基变量个基变量 s3已被已被 x2代替 故基变量列中的第代替 故基变量列中的第 3 个基个基 变量应变为变量应变为 x2 由于第 由于第 0 次迭代表次迭代表 中的主元中的主元 a32已经为已经为 1 因此第 因此第 3 行行 不变 不变 为了使第为了使第 1 行的行的 a12为为 0 只需 只需 把第把第 3 行行 1 加到第加到第 1 行即可 同行即可 同 样可以求得第样可以求得第 2 行 行 8 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 S101010 150 S202001 1150 X210001001250 j z 1 jjj zc 9 X1X2S1S2S3迭迭 代代 次次 数数 基变基变 量量 CB 50 100000 b比值比值 S101010 15050 1 1 S202001 1150 150 2 X210001001250 j z010000100 jjj zc 50000 100 2500 0 求得第求得第 1 次迭代的基本可行解为次迭代的基本可行解为 s1 50 s2 150 x2 250 x1 0 s3 0 z 25000 从上表可以看出 第一次迭的从上表可以看出 第一次迭的 0 50 1 因此不是最优解 设 因此不是最优解 设 x1为入基变量 为入基变量 从此值可知从此值可知 b1 a11 50 为最小正数 为最小正数 因此 因此 s1为出基变量 为出基变量 a11为主元 继为主元 继 续迭代如下表所示 续迭代如下表所示 10 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 x1501010 150 S202001 1150 X210001001250 2 j z jjj zc 11 X1X2S1S2S3迭代迭代 次数次数 基变基变 量量 CB 50100000 b 比比 值值 x1501010 150 S2000 21150 X210001001250 j z 2 jjj zc 12 X