运筹学线性规划单纯形法资料.ppt

单纯形法的进一步讨论－人工变量法 例1.10 用大M法解下列线性规划 解：首先将数学模型化为标准形式 系数矩阵中不存在单位矩阵，无法建立初始单纯形表。 单纯形法的进一步讨论－人工变量法 故人为添加两个单位向量，得到人工变量单纯形法数学模型： 其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。 单纯形法的进一步讨论－人工变量法 cj 3 2 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 θi 0 x6 4 -4 3 1 -1 0 1 0 4 -M x5 10 1 -1 2 0 1 0 0 5 -M x7 1 2 -2 1 0 0 0 1 1 3-2M 2+M -1+2M↑ -M 0 x6 3 -6 5 0 -1 0 1 3/5 -M x5 8 -3 3 0 0 1 0 8/3 -1 x3 1 2 -2 1 0 0 0 —— 5-6M 5M↑ 0 -M 0 0 2 x2 3/5 －6/5 1 0 －1/5 0 —— -M x5 31/5 3/5 0 0 3/5 1 31/3 -1 x3 11/5 －2/5 0 1 －2/5 0 —— 5 ↑ 0 0 0 0 2 x2 13 0 1 0 1 2 3 x1 31/3 1 0 0 1 5/3 -1 x3 19/3 0 0 1 0 2/3 0 0 0 -5 -25/3 → → → 单纯形法的进一步讨论－人工变量法 解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 * * （3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算； （4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。 图解法 2 4 6 x1 x2 2 4 6 无界解(无最优解) max Z=x1+2x2 例1.6 x1+x2=4(≥) x1+3x2=6(≥) 3x1+x2=6(≥) max Z min Z x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解(即无最优解) max Z=3x1+4x2 例1.7 图解法 学习要点： 1. 通过图解法了解线性规划有几种解的形式 （唯一最优解；无穷多最优解；无界解；无可行解） 2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动 线性规划问题求解的几种可能结果 (a) 唯一最优解 x2 6 — 5 — 4 — 3 — 2 — 1 — 0 | | | | | | | | | 1 2 3 4 5 6 7 8 9 x1 可行域 (b)无穷多最优解 6 — 5 — 4 — 3 — 2 — 1 — 0 x2 | | | | | | | | | 1 2 3 4 5 6 7 8 9 x1 线性规划问题求解的几种可能结果 可行域 可行域 (c)无界解 Max Z = x1 + x2 -2x1 + x2 ? 4 x1 - x2 ? 2 x1、 x2 ? 0 x2 x1 线性规划问题求解的几种可能结果 判断：若LP的可行域无界，则该LP存在无界解。 (d)无可行解 Max Z = 2x1 + 3x2 x1 +2 x2 ? 8 4 x1 ? 16 4x2 ? 12 -2x1 + x2 ? 4 x1、 x2 ? 0 可行域为空集 线性规划问题求解的几种可能结果 单纯形法基本原理 凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。 凸集 凸