第7讲线性规划与单纯形法.ppt

最优解X*=(1,3,0,0,0,0,0)T ，最优值f=0 .第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解即第二阶段问题为 从表2.12中的最后一张表出发，将表2.12中的人工变量 x6 、x7 所在的列除去，将目标函数的系数替换为MaxZ= -3x1+x3 中的系数，再继续用单纯形法计算，求解过程见表2.13. -3 检验数σj≤0 ，最优解为：X*=(0,5/2,3/2,0,0,0,0)T ，最优值Z*=3/2 . 不难看出，上面两种计算方法的每一步迭代的结果类似，最后结果相同． 在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，用代入法或公式计算． 另外即使第一阶段最优值为零，只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能无界． 前面我们已经给出了唯一解、多重解、无界解的判别准则，在学习了人工变量法之后，我们就可以给出无可行解的判别准则． 无可行解的判别准则：当线性规划问题中添加人工变量后，用人工变量法求解，如果迭代到某单纯形表已满足所有非基变量的σj≤0 ，但基变量中仍含有非零的人工变量,则该线性规划问题无可行解． 前面我们已经学习了求解线性规划问题的几种方法，掌握了这些方法之后，我们就可以解决任意型的线性规划模型了．现在我们对前面的内容做一个简单的小结，并给出几个需要进一步说明的问题． （1）对给定的线性规划问题应首先化为标准形式，选取或构造一个单位矩阵作为基，求出初始基可行解并列出初始单纯形表．对各种类型线性规划问题如何化为标准形式及如何选取初始基变量可参见表2.14． （2）线性规划的求解过程可用如下框图表示： 图2.6 单纯形法计算步骤框图 （3）目标函数为取极小化解的最优性判别，只需将原来要求检验数σj≤ 0 改成σj≥ 0 即可． （4）按θ 规则来确定换出变量时如果存在两个相同的最小比值θi ，则在下一轮单纯形表的基可行解中即有可能出现一个或多个基变量等于零的退化解．退化解的原因是模型中存在多余的约束，使多个基可行解对应同一顶点．当存在退化解时，就有可能出现迭代计算的循环，从而永远迭代不到最优解．为此，1974年勃兰德（Bland）提出了一个简便而有效的原则： 第一，当存在多个σj 0 时，始终选择下标最小的变量作为换入变量； 第二，当计算 θ 值出现两个以上相同的最小比值时，始终选取下标最小的变量作为换出变量． §2.5 案例分析 【案例2.1】合理下料问题． 现要做100套钢架，每套由长2.8m、2.2m和1.8m的元钢各一根组成，已知原材料长6.0m，问应如何下料，可以使原材料最省？ 解：由于要裁成的三种元钢的总长度是2.8m+2.2m+1.8m=6.8m，超过了原材料6m的长度．因此，我们容易实现的裁法是：在原材料上分别裁下2.8m、2.2m的元钢各一根，这样要100根原材料才能裁到100根2.8m、2.2m的元钢．再来考虑如何裁得1.8m的元钢，由于一根原材料可以裁得3根1.8m的元钢，这样要裁得100根1.8m的元钢，就需要原材料34根．采取上述裁法需134原材料方可裁得2.8m、2.2m、1.8m的元钢各100根． 但如果改用套裁，则可节约原材料．经过简单分析，我们得到几种可供套裁的方案，见表2.15． 为了获得100套钢架，需要混合使用各种下料方案．设按六种方案下料的原材料的根数分别为x1 , x2 , … , x6 ，根据表2.15，可建立如下数学模型： 经运算，最优解是 x2 = 50 , x3 = 25 , x6 = 50 , x1 = x4 = x5=0 ，这样，共需原材料125根． 思考题：如果每套钢架由2.8m的元钢1根、2.2m的元钢2根、1.8m的元钢3根，则如何修改数学模型？ 【案例2.2】配料问题． 某工厂要用三种原材料甲、乙、丙混合调配出三种不同规格的产品A、B、C．已知产品的规格要求、产品单价、每天能供应的原材料数量及原材料单价（分别见表2.16和表2.17），问该厂应如何安排生产，使利润收入为最大？ 产品名称 规格要求 单价(元/kg) A 原材料甲不少于50% 原材料乙不超过25% 50 B 原材料甲不少于25% 原材料乙不超过50% 40 C 不限 30 表2.17 原材料名称 每天最多能供应量(kg) 单价(元/kg) 甲 100 65 乙 100 25 丙 60 35 解：设xA甲 表示产品A中甲原料的重量，xA乙 表示产品A中乙原料的重量，依次类推． 根据表2.16有： 这里，xA甲+xA乙+xA丙=A ，表示A产品的总重量；xB甲+xB乙+xB丙=B ，表示B产品的总重量 表2.17表明这些原材料供应数量的限制，加入