《单纯形法计算中的几个问题》由会员分享，可在线阅读，更多相关《单纯形法计算中的几个问题（17页珍藏版）》请在金锄头文库上搜索。
1、一、单纯形法计算中的几个问题 1.目标函数极小化时解的最优性判别 对于目标函数值极小化的线性规划问题，这时只需以 所有检验数作为判别表中解是否最优的标志。 2.退化按最小比值来确定换出基的变量时，有时出现存在 两个以上相同的最小比值，从而使下一个表的基可行解中 出现一个或多个基变量等于零的退化解。退化解的出现原 因是模型中存在多余的约束，使多个基可行解对应同一顶 点。当存在退化解时，就有可能出现迭代计算的循环，尽 管可能性极其微小。为避免出现计算的循环，1974年勃兰 特（Bland）提出了一个简便有效的规则：1-7.单纯形法计算中的几个问题（1）当存在多个 时，始终选取下标值为最小 的变量作
2、为换入变量；（2）当计算值出现两个 以上相同的最小比值时，始终选取下标值为最小 的变量作为换出变量。 3.无可行解的判别本章第四节单纯形法迭代原理中，讲述了用 单纯形法求解时如何判别问题结局属唯一最优解 、无穷多最优解和无界解。当线性规划问题中添 加人工变量后，无论用大M法或两阶段法，初始 单纯形表中的解因含非零人工变量，故实质上是 非可行解。当求解结果出现所有时，如基变量中 仍含有非零的人工变量（两阶段法求解时第一阶 段目标函数值不等于零），表明问题无可行解。 例1-11 用单纯形法求解线性规划问题解 用图解法可看出本例无可行解。现用单纯形法求解，在添加松 驰变量和人工变量后，模型可写成以
3、为基变量列出初始单纯形表，进行迭代计算，过程见 表1-11。表中当所有 时，基变量中仍含有非零的 人工变量， 故例1-12的线性规划问题无可行解。2 1 0 0 -M基 0 2 -M 61 1 1 0 0 2 2 0 -1 12+2M 1+2M 0 -M 02 2 -M 21 1 1 0 0 0 0 -2 -1 10 -1 -2-2M -M 0二、单纯形法小结 1. 对给定的线性规划问题应首先化为标准形式 ，选取或构造一个单位矩阵作为基，求出初始 基可行解并列出初始单纯形表。对各种类型线 性规划问题如何化为标准形式及如何选取初始 基变量可参见page35表1-14。2 . 单纯形法计算步骤的框
4、图见page35图1-一、修正单纯形法的基本思想 运用单纯形法时，如果知道可行基的逆 就 能利用 原始数据计算基变量的取值及检验 数，从而能够确定一个基本可行解，并判断它 是否为最优解。因此在整个计算过程中，只要 保存原始数据和现行的逆即可。修正单纯刑法 的基本思想就是给定初始基本可行基后，通过 修改新基的逆 进而完成其他运算。在整个 计算过程中，始终保持先行基的逆 。1-8修正单纯形法二、修正单纯形发的步骤 （1）求一个初始基B并求出它的逆 ， 写出基底描述J。 （2）求单纯形乘子 。 （3）求 及 得到最优解，停止；否则，记为k主元列， 转入（4）。 （4）计算 得无界解，停 止：否则转入
5、（5）。 （5）求 并记l为主元行。 （6）构造矩阵 用 左乘 得到新基 的逆阵，将J中的第L个数改为k ，转入 （2）。解 最简单做法是，在每一根原材料上截取2.9m ，2.1m和1.5m的元钢各一根组成一套，每根原材 料省下料头0.9m。为了做100套钢架，需用原材 料100根，有90米料头,若改为用套裁，这可以节 约原材料。下面有几种套裁方案，都可以考虑采 用，见表1-13。1-9.单纯形法应用实例例1-12 合理利用线材问题现要做100套钢架，每套用长为2.9m，2.1m和1.5m的 元钢各一根，已知原料长7.4m，问应如何下料，使用 的原材料最省。方案 下料数(根) 长度m 2.92
6、.11.513212 21 21 3合计 料头7.4 07.3 0.17.2 0.27.1 0.36.6 0.8为了得到100套钢架，需要混合使用各种下料方案。设 按方案下料的原材料要数为，方案为，方案为， 方案为，方案为。根据表1-13的方案，可列出以下 数学模型：计算得到最优下料方案是：按 方案下料30根；方案 下料10根；方案下料50根。即需90根原材料才能制造 100套钢架。例1-13 配料问题 某工厂要用三种原材料C、P、H混合调配出三种 不同规格的产品A、B、C。已知产品的规格要 求，产品单价，每天能供应的原材料数量及原材 料单价，分别见表1-14和表1-15，该厂应如何安 排生产
7、，使利润收入为最大？产品名称 规格要求单价(元/kg) A原材料C不少于50% 原材料P不少于25%50B原材料C不少于25%原材料P不少于50% 35D不限 25原材料名称每天最多供应量(kg) 单价(元/kg)C P H100 100 6065 25 35解 如以 表示产品A中C的成分， 表示产品A中P的成分，依次 类推。有(1-36)这里 (1-37) (1-36)将（1-36）逐个代入(1-37)并整理得到表1-15表明这些原材料供应数量的限额,加入到产品A、B、D的 原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不 超过60kg。由此在约束条件中共有9个变量，为计算和叙述方便， 分 别用表示令 由此约束条件可表示为：我们的目的是使利润最大，即产品价格减去原材料的价格为最大 。 产品价格为: 原材料价格为： 原材料H产品A产品B产品D原材料C原材料P目标函数为： 为了得到初始解，在约束条件中加入松驰变量 ，得到数学 模型： 上述数学模型，可用单纯形表计算，计算结果是：每天只生产产品 A 200kg，分别需要用原料C 100kg；P 50kg；H 50kg。
