重点规划的单纯形法.pptVIP

1.3 人工变量的引入及其解法 1.3.1 当约束条件为“?”型，引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为?1，不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法 大M法 二阶段法 1.3.2 大M法的求解过程 例1.3.1 表1.3.1 例1.3.1的单纯型表迭代过程 大M法的一些说明 大M法实质上与原单纯型法一样，M可看成一个很大的常数 人工变量被迭代出去后就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易 1.3.3 二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解 为了简化计算，在第一阶段重新定义价值系数如下： 表1.3.2 用二阶段法求解例1.3.1的第一阶段 表1.3.2 用二阶段法求解例1.3.1的第二阶段 1.5 单纯型法的一些具体问题 1.5.1 关于无界解问题 可行区域不闭合(缺约束条件) 单纯型表中入变量 x j* 对应的列中所有 例1.5.1 表1.5.1 例1.5.1 的单纯型表及其迭代过程 1.5.2 关于退化问题 退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环 例1.5.2 1.5.3 关于多重解问题 多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1 例1.5.2 多重最优解 表1.5.3 例1.5.3 的单纯型表及其迭代过程 max z=3x1+5x2 3x1 +5x2 ?15  2x1 + x2 ?5  2x1+2x2 ?11  x1 ,x2 ?0 如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解 当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解。 1.5.4 关于无可行解问题 约束条件互相矛盾，无可行域 单纯型表达到最优解检验条件时，人工变量仍在基变量中 例1.5.4 表1.5.4 例1.5.4 第一阶段的单纯型表 ? CB XB b x3 x4 x5 0 0 0 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 0 15 3 [5 ] 1 0 0 3 5 11/2 x2 x4 x5 5 0 0 3 3/5 1 1/5 0 0 2 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1 cj-zj 0 0 -1 0 0 cj-zj 3 5 0 0 0 Z0=0 11 2 2 0 0 1 Z1=15 x1 x2 * 一、单纯形法的直观背景 一般线性规划的单纯形法 【例3】文教用品厂，利用白坯纸生产信封、公文袋、便条纸。每单位产品的收益值、劳动力消耗、原料消耗及人力、原料总量如下表。 1 3 2 收益值（元/单位） 900 8 4 1 白坯纸（公斤） 100 1/3 1/3 1/3 劳动力（人） 总量 丙（便条纸） 乙（公文袋） 甲（信封）