[管理学]1第一章 线形规划问题及单纯型解法.pptVIP

* 1.2.4 标准型的单纯型算法 确定入变量的最大值和出变量 设第 i* 行使 ? 最小，则第 i* 行对应的基变量称为出变量，第 i* 行称为主行 迭代过程 主行 i* 行与主列 j* 相交的元素ai*j* 称为主元，迭代以主元为中心进行 迭代的实质是线性变换，即要将主元 ai*j*变为1，主列上其它元素变为0，变换步骤如下： (1)变换主行 * 1.2.4 标准型的单纯型算法 迭代过程 (2)变换主列 除主元保留为1，其余都置0 (3)变换非主行、主列元素 aij (包括 bi) 四角算法公式： * 1.2.4 标准型的单纯型算法 5、迭代过程 (4)变换CB，XB (5)计算目标函数、机会成本 zj 和检验数 cj ? zj 6、返回步骤 2 * 表1.2.4 例1.2.2 单纯型表的迭代过程 答：最优解为 x1=20, x2=20, x3=0, OBJ=1700 * 单纯型表中元素的几点说明 任何时候，基变量对应的列都构成一个单位矩阵 当前表中的 b 列表示当前基变量的解值，通过变换 B ?1 b 得到 (资源已变成产品) 当前非基变量对应的向量可通过变换 B ?1 AN 得到， 表示第 j 个变量对第 i 行对应的基变量的消耗率 非基变量的机会成本由 给出 注意基变量所对应的行 * 1.3 人工变量的引入及其解法 1.3.1 当约束条件为“?”型，引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为?1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法 大M法 二阶段法 * 1.3.2 大M法的求解过程 例1.3.1 * 表1.3.1 例1.3.1的单纯型表迭代过程 答：最优解为 x1=2, x2=2, x3=0, OBJ=36 * 大M法的一些说明 大M法实质上与原单纯型法一样，M 可看成一个很大的常数 人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易 * 1.3.3 二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无解 为了简化计算，在第一阶段重新定义价值系数如下： * 表1.3.2 用二阶段法求解例1.3.1的第一阶段 * 表1.3.2 用二阶段法求解例1.3.1的第二阶段 最优解对应的B–1在哪？ * 1.5 单纯型法的一些具体问题 1.5.1 关于无界解问题 可行区域不闭合(约束条件有问题) 单纯型表中入变量 xj* 对应的列中所有 * 表1.5.1 例1.5.1 的单纯型表及其迭代过程 ? * 1.5.2 关于退化问题 退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法 * 1.5.3 关于多重解问题 多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1 * 表1.5.3 例1.5.3 的单纯型表及其迭代过程 * 1.5.4 关于无可行解问题 约束条件互相矛盾，无可行域 单纯型表达到最优解检验条件时，人工变量仍在基变量中 * 表1.5.4 例1.5.4 第一阶段的单纯型表 * 1.4 修正单纯型法 原单纯型法迭代所需存储量大 原单纯型法有不必要的计算量 1.4.1 修正单纯型的原理 * 1.4.1 修正单纯型的原理 关键是求新基的逆矩阵 B?1 仍然可以采用四角算法 混合算法 当前基的逆矩阵 B?1 在原单纯型表的什么位置上？ 在初始可行基向量位置上 ( AN | I ) ? ( I | AN?1 ) * * ?管理与人文学院 忻展红 1999，4 运筹学Operational R