第一章运筹学.ppt

管理科学与工程学院 管理科学与工程学院 -1 -Z -a+8 -1 2a 4 x1 -2 1 -1 1 x2 2 -1 2 1 2 x5 x6 x5 x4 x3 x2 x1 b xB cB 2 2 cj 1、把表中缺少的项目填上适当的数或式子 2、要使上表成为最优表，a应满足什么条件 3、何时有无界解 4、何时无穷多最优解 5、何时以x3替换x1 * * * er 管理科学与工程学院 1—3退化解 max Z=3x1+9x2 x1+4x2+x3 =8 x1+2x2 +x4 =4 x1…x4≥0， 在单纯形法的运算过程中，有时会出现两个或多个相同的最小θ ，继续迭代的结果便有基变量为0，称这种情况为退化解。 cj 3 9 0 0 cB xB b x1 x2 x3 x4 0 x3 8 1 4 1 0 2 0 x4 4 1 2 0 1 2 σj 3 9 0 0 √ √ 检验数相等，易出现循环。 管理科学与工程学院 cj 3 9 0 0 cB xB b x1 x2 x3 x4 9 x2 2 1/4 1 1/4 0 8 0 x4 0 1/2 0 -1/2 1 0 σj 3/4 0 -9/4 0 X1入基 X4出基 √ √ cj 3 9 0 0 cB xB b x1 x2 x3 x4 9 x2 2 0 1 1/2 -1/2 3 x1 0 1 0 -1 2 σj 0 0 -3/2 -3/2 有退化的 最优解 X*=（0,2）T 管理科学与工程学院 maxZ=2x1+x2 4x1+3x2+x3 =12 4x1+x2 +x4 =8 4x1-x2 +x5=8 x1…x5≥0 cj 2 1 0 0 0 cB xB b x1 x2 x3 x4 x5 0 x3 12 4 3 1 0 0 3 0 x4 8 4 1 0 1 0 2 0 x5 8 4 -1 0 0 1 2 σj 2 1 0 0 0 X1入基 X4出基 √ √ 中间出现退化解，最终得到普通解。 管理科学与工程学院 cj 2 1 0 0 0 cB xB b x1 x2 x3 x4 x5 0 x3 4 0 2 1 -1 0 2 2 x1 2 1 1/4 0 1/4 0 8 0 x5 0 0 -2 0 -1 1 - σj 0 1/2 0 -1/2 0 √ √ X2入基 X3出基 管理科学与工程学院 cj 2 1 0 0 0 cB xB b x1 x2 x3 x4 x5 1 x2 2 0 1 1/2 -1/2 0 2 x1 3/2 1 0 -1/8 3/8 0 0 x5 4 0 0 1 -2 1 σj 0 0 -1/4 -1/4 0 这种现象称为临时退化现象。（最终有解） 为了不出现循环，须改模型。 管理科学与工程学院 还有一种出现死循环（字典序法来解决） 总结：当θ相等时，出现三种情况 （1）退化最优解 为解决循环现象情况，勃兰特提出一个有效的规则： （2）临时退化现象，最终有最优解。 （3）死循环（字典序法解决） （1）当存在多个检验数大于零且相等，始终选取下标最小的作为入基变量。 （2）当计算θ值出现两个以上相同的最小比值时，始终选取下标最小的作为出基变量。 管理科学与工程学院 建 立 模 型 个 数 取 值 右 端 项 等式或 不等式 极大或极小 新加变量系数 两 个 三个 以上 xj≥0 xj无 约束 xj ≤ 0 bi ≥0 bi 0 ≤ = ≥ maxZ minZ xs xa 求解 图解法、 单纯形法 单纯形法 不 处 理 令xj = xj′ - xj″ xj′ ≥0 xj″ ≥0 令 xj = - xj 不 处 理 约束条件两端同乘以-1 加松弛变量xs 加入人工变量xa 减 去 xs 加入 xa 不 处 理 令 z′=- Z minZ =－ max z′ 0 -M 根据上表列出初始单纯形表 A 三、线性规划小结 管理科学与工程学院 A 管理科学与工程学院 练习 管理科学与工程学院 -M+1/7 -1/7 -M-16/7 -50/7 0 0 -102/7 -Z 1/7 -1/7 5/7 6/7 0 1 45/7 x1 2 -1/7 1/7 2/7 1/7 1 0 4/7 x2 3 x6 x5 x4 x3 x2 x1 b xB cB -M 0 -M -5 3 2 cj 0 -M 0 -5+2M 3-4M 2+3M -Z 5