运筹学--单纯形法求解-动态演示课件.ppt

单纯形法求解—动态演示 在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是 美国数学家G·B·Dantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。 线性规划的例子 线性规划--标准化 引入变量：s1,s2,s3 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 初始单纯形表 表格中，检验系数σj全部小于或等于0，根据判断规则，Z值为最优值（Z=27500），其解： X1=50,S1=50,X2=250,s2=s3=0为模型的最优解。 * * 提取系数，填入表格： s.t. 1x1+1 x2+1s1+0s2+0s3 =300 2x1+1 x2+0s1+1s2+0s3 =400 x1 ≥0, x2≥0, si≥0 0x1+1x2+0s1+0s2+1s3 =250 1 x1 CB 迭代次数 Zj b 比值 S3 s2 s1 X2 基变量 1 x1 CB 迭代次数 Zj b 比值 S3 s2 s1 X2 基变量 目标系数区 约束条件系数区 右端系数 检验系数区 基变量区 1 x1 CB 迭代次数 Zj b 0 0 0 100 50 比值 s3 s2 s1 x2 基变量 0 250 1 0 0 1 0 400 0 1 0 1 2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基 变 量 1 250 1 0 0 1 0 400 0 1 0 1 2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 b 0 0 0 100 50 比值 s3 s2 s1 x2 基 变 量 1 250 1 0 0 1 0 0 S3 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 s3 s2 s1 x2 基 变 量 1 250 1 0 0 1 0 0 S3 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Z=0 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 1 250 1 0 0 1 0 0 S3 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Z=0 0 0 0 0 0 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 0 0 0 0 0 1 0 0 0 100 250 1 0 0 1 0 0 S3 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Z=0 0 0 0 0 0 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 50 1 0 0 0 100 50 250 1 0 0 1 0 0 S3 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Z=0 0 0 0 0 0 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 ① 2 250 1 0 0 1 0 x2 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 ① 2 250 1 0 0 1 0 100 x2 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 ① 2 250 1 0 0 1 0 100 x2 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 ① 2 250 1 0 0 1 0 100 x2 400 0 1 0 1 2 0 S2 x1 CB 迭代次数 Zj 300 0 0 1 1 1 0 S1 b 0 0 0 100 50 比值 S3 s2 s1 X2 基变量 ① 2 250 1 0 0 1 0 100 x2 150 -1 1 0 0 2 0 S2 x1 CB 迭代次数 Z=25000 Zj 50 -1 0 1 0 1