线性规划及其对偶问题.ppt

第2章线性规划及其对偶问题 LinearProgramming itsDualProblem 2 1线性规划 2 2对偶理论 2 3灵敏度分析 2 4LINGO软件求解线性规划模型的方法 2 1线性规划 LinearProgramming 2 1 1线性规划问题的数学模型 2 1 2线性规划问题解的概念 2 1 3求解线性规划问题的图解法 2 1 4求解线性规划问题的单纯形法 2 1 5单纯形法的进一步讨论 2 1 6线性规划模型的应用 为了完成一项任务或达到一定的目的 怎样用最少的人力 物力去完成或者用最少的资源去完成较多的任务或达到一定的目的 这个过程就是规划 例 有一正方形铁皮 如何截取x使容积为最大 x a 此为无约束极值问题 2 1 1线性规划问题的数学模型 一 问题的提出 例 已知资料如下表所示 问如何安排生产才能使利润最大 或如何考虑利润大 产品好销 模型 maxZ 2x1 3x2 x1 0 x2 0 s t 2x1 2x2 12x1 2x2 84x1 164x2 12 此为带约束的极值问题 问题中总有未知的变量 需要我们去解决 要求 有目标函数及约束条件 一般有非负条件存在 由此组成规划数学模型 如果在规划问题的数学模型中 变量是连续的 数值取实数 其目标函数是有关线性函数 一次方 约束条件是有关变量的线性等式或不等式 这样 规划问题的数学模型是线性的 反之 就是非线性的规划问题 其中一个条件符合即可 二 数学模型1 目标函数 约束条件 2 线性规划数学模型的一般形式 也可以记为如下形式 目标函数 约束条件 如将上例用表格表示如下 设变量 向量形式 矩阵形式 规划 确定型随机型 静态规划动态规划 线性规划非线性规划 整数规划非整数规划 整数规划非整数规划 3 规划类型 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但需将一般形式变成标准形式 2 1 2线性规划问题解的概念 一 求解方法 1 解的概念 可行解 满足约束条件 的解为可行解 所有解的集合为可行解的集或可行域 最优解 使目标函数达到最大值的可行解 基 B是矩阵A中m m阶非奇异子矩阵 B 0 则B是一个基 则称Pj j 1 2 m 为基向量 Xj为基变量 否则为非基变量 二 线性规划问题的解 基本解 基解 令所有非基变量的值全为0 求得的基变量解与这些0非基变量所组成的解X x1 x2 xm 0 0 T称为LP的基本解 最多为个 基本可行解 满足非负约束条件的基本解 简称基可行解 可行基 对应于基可行解的基称为可行基 非可行解 可行解 基解 基可行解 2 解的基本定理 若线性规划问题存在可行解 则问题的可行域是凸集 凸多边形 凸集 凸集 不是凸集 顶点 最优解一定是在凸集的某一顶点实现 顶点数目不超过个 先找一个基本可行解 与周围顶点比较 如不是最大 继续比较 直到找出最大为止 3 解的情况 唯一解无穷解无界解无可行解 有最优解 无最优解 建立直角坐标 图中阴影部分及边界上的点均为其解 是由约束条件来反映的 例2 3 2 1 3求解线性规划问题的图解法 0 12345678 123456 作图 有唯一最优解 x1 4 x2 2 最优目标函数值Z 14 x2 x1 42 例 例 无穷多最优解 无界解 x1 x1 x2 x2 x1 x2 无可行解 例 一 基本思想 将模型的一般形式变成标准形式 再根据标准型模型 从可行域中找一个基本可行解 并判断是否是最优 如果是 获得最优解 如果不是 转换到另一个基本可行解 当目标函数达到最大时 得到最优解 二 线性规划模型的标准形式 1 标准形式 2 1 4求解线性规划问题的单纯形法 2 特征 目标函数为求极大值 也可以用求极小值 所有约束条件 非负条件除外 都是等式 右端常数项为非负 变量为非负 3 转换方式 目标函数的转换 如果是求极小值即 则可将目标函数乘以 1 可化为求极大值问题 也就是 令 可得到上式 即 约束方程的转换 由不等式转换为等式 称为松弛变量 称为剩余变量 变量的变换 若存在取值无约束的变量 可令其中 例2 2将下列线性规划问题化为标准形式 为无约束 无非负限制 解 用替换 且 将第3个约束方程两边乘以 1 将极小值问题反号 变为求极大值 标准形式如下 引入变量 例 将下列线性规划问题化为标准型 为无约束 解 三 单纯形法 例2 3 变成标准型 约束方程的系数矩阵 可作为为基变量 为非基变量 I为单位矩阵且线性独立 令 则 基本可行解为 0 0 12 8 16 12 此时 Z 0 然后 找另一个基本可行解 即将非基变量换入基变量中 但保证其余的非负 如此循环下去 直到找到最优解为止 注意 为尽快找到最优解 在换入变量时有一定的要求 如将目标系数大的先换入等 找出一个初始可行解 是否最优 转移到另一个目标函数 找更大的基本可行解 最优解 是 否 循环 直到找出为止 核心是 变量迭代 结束 其步骤总结如下 四 单纯形表 判定标准 若求 或 例题 230000 12 2 8 2 12 4 3 x2 3 0 1 0 0 0 1 4 2 6 2 0 1 0 0 1 2 1 0 0 1 0 0 1 2 20000 3 4 6 2 2 16 4 000 201 4 4 412 001 201 210010 1 2000 412010001 4 2283 x3x1x5x2 0203 x1x2x3x4x5x6 b xB cB 230000 cj j 000 201 4 4 412 001 201 210010 1 2000 412010001 4 2283 x3x1x5x2 0203 x1x2x3x4x5x6 b xB cB 230000 cj j 练习 00 1 12 7 24 x2x1 12 x1x2x3x4 b xB cB 2100 cj 15 4 3 4 0 1 1 4 1 8 1 0 1 12 5 24 j 一 模型情况变量 xj 0 xj 0 xj无约束结1 组成约束条件 b目标函数 maxmin果2 变量xj 0令xj xj xj 0 xj 0不处理xj无约束令xj xj xj xj 0 xj 0 唯一最优无穷最优无界解无可行解 2 1 5单纯形法的进一步讨论 3 约束条件 加入松弛变量加入人工变量先减去再加上 例2 5 4 目标函数 max min设规划模型约束条件为 需加入人工变量而得到一个m m的单位矩阵 即基变量组合 因人工变量为虚拟变量 且存在于初始基本可行解中 需要将它们从基变量中替换出来 若基变量中不含有非零的人工变量 表示原问题有解 若当 而还有人工变量 非零 时 则表示原问题无可行解 加入人工变量后 目的是找到一个单位向量 叫人工基 其目标价值系数要确定 但不能影响目标函数的取值 一般可采用两种方法处理 大M法和两阶段法 大M法 即假定人工变量在目标函数中的系数为M 任意大正数 如果是求极大值 需加 M 如果是求极小值 需加M 如基变量中还存在M 就不能实现极值 最优解为x 4 1 9 0 0 0 0 T Z 2 用计算机处理数据时 只能用很大的数代替M 可能造成计算机上的错误 故多采用两阶段法 第一阶段 在原线性规划问题中加入人工变量 构造如下模型 两阶段法 对上述模型求解 单纯形法 若W 0 说明问题存在基本可行解 可以进行第二个阶段 否则 原问题无可行解 停止运算 第二阶段 在第一阶段的最终表中 去掉人工变量 将目标函数的系数换成原问题的目标函数系数 作为第二阶段计算的初始表 用单纯形法计算 例2 6 第一阶段 第二阶段 最优解为x 4 1 9 0 0 0 0 T Z 2 6 无可行解的判断 运算到检验数全负为止 仍含有人工变量 无可行解 8 退化 即计算出的 用于确定换出变量 存在有两个以上相同的最小比值 会造成下一次迭代中由一个或几个基变量等于零 这就是退化 会产生退化解 虽任意换出变量 目标函数值不变 但此时不同的基却表示为同一顶点 其特例是永远达不到最优解 需作如下处理 当中出现两个以上最大值时 选下标最小的非基变量为换入变量 当 中出现两个以上最小值时 选下标最小的基变量为换出变量 根据上表列出初始单纯形表A 二 线性规划小结 A 初始单纯形表 max型 A 课堂练习 M 1 7 1 7 M 16 7 50 7 0 0 1 7 1 7 5 7 6 7 0 1 45 7 x1 2 1 7 1 7 2 7 1 7 1 0 4 7 x2 3 x6 x5 x4 x3 x2 x1 b xB cB M 0 M 5 3 2 cj 0 M 0 5 2M 3 4M 2 3M 5 1 1 0 1 5 2 10 x6 M 7 0 0 1 1 1 1 7 X4 M x6 x5 x4 x3 x2 x1 b xB cB M 0 M 5 3 2 cj j j 一般而言 一个经济 管理问题凡是满足以下条件时 才能建立线性规划模型 要求解问题的目标函数能用数值指标来反映 且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的 这些约束可用线性等式或不等式描述 2 1 6线性规划模型的应用 一 资源的合理利用 一般提法 某厂计划在下一生产周期内生产B1 B2 Bn种产品 要消耗A1 A2 Am种资源 已知每件产品所消耗的资源数 每种资源的数量限制以及每件产品可获得的利润如表所示 问如何安排生产计划 才能充分利用现有的资源 使获得的总利润最大 二 生产组织与计划问题 一般提法 某工厂用机床A1 A2 Am加工B1 B2 Bn种零件 在一个周期内 各机床可能工作的机时 台时 工厂必须完成各种零件的数量 各机床加工每个零件的时间 机时 个 和加工每个零件的成本 元 个 如表所示 问如何安排各机床的生产任务 才能完成加工任务 又使总成本最低 三 合理下料问题 一般提法设用某种原材料截取零件A1 A2 Am的毛坯 根据以往的经验 在一种原材料上可以有B1 B2 Bn种不同的下料方式 每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示 问应如下料才能既满足需要又使原材料消耗最少 现有一批某种型号的圆钢长8米 需要截取2 5米长的毛坯100根 长1 3米的毛坯200根 问如何才能既满足需要 又能使总的用料最少 设变量为第j种方法的所有原料件数 例题1 一30 二22 三14 四06 四 合理配料问题 一般提法某饲养场用n种饲料B1 B2 Bn配置成含有m种营养成分A1 A2 Am的混合饲料 其余资料如表所示 问应如何配料 才能既满足需要 又使混合饲料的总成本最低 例题2 某人每天食用甲 乙两种食物 如猪肉 鸡蛋 其资料如下 问两种食物各食用多少 才能既满足需要 又使总费用最省 设 xj表示Bj种食物用量 五 运输问题 已知资料如表所示 模型如下 某运输问题的资料如下 例题3 六 作物布局问题 此外 还有连续投资 投入产出等模型问题 2 2对偶理论 DualityTheory 2 2 1对偶问题的提出 2 2 2线性规划问题解的概念 2 2 3线性规划的对偶理论 2 2 4对偶问题的经济解释 影子价格 2 2 5对偶单纯形法 2 2 1对偶问题的提出 例2 7某工厂拥有A B C三种类型的设备 生产甲 乙两种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 求获最大利润的方案 解 设x1 x2分别为甲乙两种产品的生产量 则有 若例2 7问题的设备都用于外协加工 工厂收取加工费 试问 设备A B C每工时各如何收费才最有竞争力 minf 65y1 40y2 75y3s t 3y1 2y2 1500 不少于甲产品的利润 2y1 y2 3y3 2500 不少于乙产品的利润 y1 y2 y3 0 解 设y1 y2 y3分别为每工时设备A B C的收取费用 则有 原问题 Minf 65y1 40y2 75y3s t 3y1 2y2 1500 不少于甲产品的利润 2y1 y2 3y3 2500对偶问题 不少于乙产品的利润 y1 y2 y3 0 1 对偶定义对称形式 互为对偶 LP maxz cx DP minf bTys t Ax bs t ATy cTx 0y 0 max min 2 2 2线性规划的对偶理论 一对对称形式的对偶规划之间具有下面的对应关系 1 若一个模型为目标求 极大 约束为 小于等于 的不等式 则它的对偶模型为目标求 极小 约束是 大于等于 的不等式 即 max 和 min 相对应 2 从约束系数矩阵看 一个模型中为 则另一个模型中为AT 一个模型是m个约束 n个变量 则它的对偶模型为n个约束 m个变量 3 从数据b C的位置看 在两个规划模型中 b和C的位置对换 4 两个规划模型中的变量皆非负 2 非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划 对于非对称形式的规划 可以按照下面的对应关系直接给出其对偶规划 1 将模型统一为 max 或 min 的形式 对于其中的等式约束按下面 2 3 中的方法处理 2 若原规划的某个约束条件为等式约束 则在对偶规划中与此约束对应的那个变量取值没有非负限制 3 若原规划的某个变量的值没有非负限制 则在对偶问题中与此变量对应的那个约束为等式 线性规划的原问题与对偶问题的关系 其变化形式可归纳为表2 12所示的对应关系 例2 8写出下面线性规划的对偶规划模型 解 先将约束条件变形为 形式 再根据非对称形式的对应关系 直接写出对偶规划 3 单纯形法计算的矩阵描述假设原问题及对偶问题为对称LP问题 原问题和对偶问题分别为 2 1 LP 2 2 DP 2 3 单纯形法计算时总是选取I为初始基 对应的基变量为Xs 设迭代若干步后基变量为XB XB在初始单纯形表中的系数矩阵为B 将B在初始表中单独列出来 而A中去掉B的若干列后剩下的列组成矩阵N 则 2 3 的初始单纯形表为 对称LP问题 2 1 的矩阵表达式加上松弛变量后为 XB XNXs CB XB B 1b 0 I B 1N B 1 CN CBB 1N CBB 1 当迭代若干步 基变量为XB时 则该步的单纯形表中由XB系数组成的矩阵为I 对应Xs的系数矩阵在新表中应为B 1 故当基变量为XB时 新的单纯形表为 当B为最优基时 在上表中有 CN CBB 1N 0 CBB 1 0 因xB的检验数可写为故以上3个式子可重写为 CB CBB 1B 0 C CBB 1A 0 CBB 1 0 CBB 1称为单纯形乘子 若令YT CBB 1 则有 ATY CTY 0 以上可以看出 此时检验数行中 若取初始基变量检验数的相反数 则恰好得到对偶问题的一个可行解 4 对偶定理 原问题与对偶问题解的关系 考虑 LP 和 DP 定理2 1 弱对偶定理 若x y分别为 LP 和 DP 的可行解 那么cx bTy 推论若 LP 可行 那么 LP 无有限最优解的充分必要条件是 DP 无可行解 定理2 2 最优性准则定理 若x y分别为 LP DP 的可行解 且cx bTy 那么x y分别为 LP 和 DP 的最优解 定理2 3 主对偶定理 若 LP 和 DP 均可行那么 LP 和 DP 均有最优解 且最优值相等 以上定理 推论对任意形式的线性规划的对偶均有效 定理2 4 互补松弛性 在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 反之如果约束条件取严格不等式 则其对应的对偶变量一定为零 例2 10已知线性规划问题 其对偶问题的最优解为 试运用对偶问题的性质 求原问题的最优解 解 上述问题的对偶问题为 将代入约束条件可得 第1和第2个约束条件为严格不等式 由互补松弛性得 又因为 所以原问题的两个约束条件取等式 故有 求解得 所以原问题的最优解为 影子价格是一个向量 它的分量表示最优目标值随相应资源数量变化的变化率 若x y 分别为 LP 和 DP 的最优解 那么 cx bTy 根据f bTy b1y1 b2y2 bmym 可知 f bi yi yi 表示bi变化1个单位对目标f产生的影响 称yi 为bi的影子价格 2 2 3对偶问题的经济解释 影子价格 影子价格的经济含义 1 影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格 对资源的使用有两种考虑 第一 是否将设备用于外加工或出租 若租费高于某设备的影子价格 可考虑出租该设备 否则不宜出租 第二 是否将投资用于购买设备 以扩大生产能力 若市价低于某设备的影子价格 可考虑买进该设备 否则不宜买进 2 影子价格表明资源增加对总效益产生的影响 根据推论 设x0和y0分别为原规划 LP 和对偶规划 DP 的可行解 当cx0 bTy0时 x0 y0分别是两个问题的最优解 可知 在最优解的情况下 有关系因此 可以将z 看作是bi i 1 2 m的函数 对bi求偏导数可得到这说明 如果右端常数增加一个单位 则目标函数值的增量将是 由最优单纯形表求对偶问题最优解例 求解以下标准LP问题的最优解并求出其对偶问题的最优解 maxz 50 x1 100 x2s t x1 x2 x3 3002x1 x2 x4 400 x2 x5 250 x1 x2 x3 x4 x5 0 CBB 1 I B p1 p4 p2 0T B 1 最优解x1 50 x2 250 x4 50影子价格y1 50y2 0y3 50 B 1对应的检验数 CBB 1 解 求解此问题的单纯形法计算过程如下表 单纯形表的理解 例题 上表中6个常数a1 a2 a3 b 1 2取值在什么范围可使 1 现可行解最优 且唯一 何时不唯一 2 现基本解不可行 3 无有限最优解 4 现基本解可行 由x1取代x6目标函数可改善 对偶单纯形法的基本思想从原规划的一个基本解出发 此基本解不一定可行 但它对应着一个对偶可行解 检验数非正 所以也可以说是从一个对偶可行解出发 然后检验原规划的基本解是否可行 即是否有负的分量 如果有小于零的分量 则进行迭代 求另一个基本解 此基本解对应着另一个对偶可行解 检验数非正 2 2 4对偶单纯形法 如果得到的基本解的分量皆非负则该基本解为最优解 也就是说 对偶单纯形法在迭代过程中始终保持对偶解的可行性 即检验数非正 使原规划的基本解由不可行逐步变为可行 当同时得到对偶规划与原规划的可行解时 便得到原规划的最优解 对偶单纯形法应用前提 有一个基 其对应的基满足 单纯形表的检验数行全部非正 对偶可行 变量取值可有负数 非可行解 注 通过矩阵行变换运算 使所有相应变量取值均为非负数即得到最优单纯形表 1 建立初始对偶单纯形表 对应一个基本解 所有检验数均非正 转2 2 若b 0 则得到最优解 停止 否则 若有bk 0则选k行的基变量为出基变量 转3 3 若所有akj 0 j 1 2 n 则原问题无可行解 停止 否则 若有akj 0则选 min j akj akj 0 r akr 那么xr为进基变量 转4 4 以akr 为转轴元 作矩阵行变换使其变为1 该列其他元变为0 转2 对偶单纯形法求解线性规划问题过程 例2 11 求解线性规划问题 解 标准化 maxz 2x1 3x2 4x3s t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 minf 2x1 3x2 4x3s t x1 2x2 x3 32x1 x2 x3 4x1 x2 x3 0 表格对偶单纯形法 单纯形法和对偶单纯形法步骤 是 是 是 是 否 否 否 否 所有 所有 得到最优解 计算 计算 典式对应原规划的基本解是可行的 典式对应原规划的基本解的检验数 所有 所有 计算 计算 以aek为中心元素进行迭代 以aek为中心元素进行迭代 停 没有最优解 没有最优解 单纯形法 对偶单纯形法 对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题 在引入剩余变量化为标准型之后 约束等式两侧同乘 1 能够立即得到检验数全部非正的原规划基本解 可以直接建立初始对偶单纯形表进行求解 非常方便 对于有些线性规划模型 如果在开始求解时不能很快使所有检验数非正 最好还是采用单纯形法求解 因为 这样可以免去为使检验数全部非正而作的许多工作 从这个意义上看 可以说 对偶单纯形法是单纯形法的一个补充 除此之外 在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法 可以简化计算 2 3灵敏度分析 SensitivityAnalysis 2 3 1价值系数ck的变化分析 2 3 2右端项b的变化分析 2 3 3增加一个变量 2 3 4增加一个约束条件 进一步理解最优单纯形表中各元素的含义考虑问题maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 无妨设 xj 0 j m 1 n xi bi i 1 m是基本可行解 对应的目标函数典式为 z f m 1xm 1 nxn以下是初始单纯形表 mm其中 f cibi j cj ciaij 为检验数 向量b B 1bi 1i 1A p1 p2 pn pj B 1pj pj a1j a2j amj T j m 1 n 2 3 1价值系数ck的变化分析m考虑检验数 j cj criariji 1 1 若ck是非基变量的系数 设ck变化为ck ck k ck ck criarik k ck只要 k 0 即 ck k 则最优解不变 否则 将最优单纯形表中的检验数 k用 k 取代 继续单纯形法的表格计算 j 1 2 n 对于表格单纯形法 通过计算得到最优单纯形表 应能够找到最优基B的逆矩阵B 1 B 1b以及B 1N 检验数 j等 最优单纯形表 由 3 9 5 c3 0 可得到 当 c3 9 5时 原最优解不变 例2 12 Maxz 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 目标函数中x3的系数在什么范围内变化时原最优解保持不变 2 若cs是基变量的系数 设cs变化为cs cs 那么 j cj criarij cs cs asj j csasj i s 对所有非基变量 只要对所有非基变量 j 0 即 j csasj 则最优解不变 否则 将最优单纯形表中的检验数 j用 j 取代 继续单纯形法的表格计算 max j asj asj 0 cs min j asj asj 0 例2 13已知线性规划问题maxz 2x1 3x2 0 x3 0 x4 0 x5 s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 下表为最优单纯形表 从表中看到 要使最优基保持不变 则有 1 5 c2 2 0 且 1 8 c2 8 0 由此可得 3 c2 1时 原最优解不变 考虑基变量系数c2发生变化 即由3变为3 c2 将其放入单纯形表中有 2 3 2右端项b的变化分析设分量br变化为br br 根据第1节的讨论 最优解的基变量xB B 1b 那么只要保持B 1 b b 0 则最优基不变 即基变量保持 只有值的变化 否则 需要利用对偶单纯形法继续计算 对于问题 LP Maxz cTxs t Ax bx 0 最优单纯形表中含有B 1 aij i 1 m j n 1 n m那么 新的xi B 1b i brair i 1 m 由此可得 最优基不变的条件是Max bi air air 0 br Min bi air air 0 例2 14上例最优单纯形表如下 00 250这里B 1 20 510 5 0 1250 下面要考虑资源b1增加4个单位 即由原来的8变为12时 最优基的变化情况 上表不是最终单纯形表 用对偶单纯形法进一步求解 可得 x 4 3 2 0 0 T f 17 计算得 以上的最终单纯形表变为 例2 15在例2 13的模型中增加x6 p6 2 6 3 T c6 5 解 首先计算出 2 3 3增加一个变量增加变量xn 1则有相应的pn 1 cn 1 那么计算出B 1pn 1 n 1 cn 1 criarin 1 填入最优单纯形表 若 n 1 0则最优解不变 否则 进一步用单纯形法求解 用单纯形法进一步求解 可得 x 1 1 5 0 0 0 2 T f 16 5 在最终单纯形表的最后中增加一列 并将放入其中 得到 计算x6所对应的检验数 6 1 25 并将其放入以上的单纯形表中 1 25 由于 6 1 25 0 所以x6进基 根据 法则确定x5出基 例2 16例2 13增加约束3x1 2x2 15解 在新增的约束条件中加入松弛变量后得到 2 3 4增加一个约束条件增加一个约束之后 应把最优解带入新的约束 若满足则最优解不变 否则填入最优单纯形表作为新的一行 引入一个新的非负变量 原约束若是小于等于形式可引入非负松弛变量 否则引入非负人工变量 并通过矩阵行变换把对应基变量的元素变为0 进一步用单纯形法或对偶单纯形法求解 3x1 2x2 x6 15 在例2 13的最终单纯形表中增加一行和一列 得如下的单纯形表 经对偶单纯形法一步 可得最优解为 3 5 2 25 0 0 3 2 T 最优值为13 75 通过矩阵行变换把最后一行中对应基变量x1 x2 x5的元素变为0 最后计算出所有变量所对应的检验数 结果如下表所示 A中元素发生变化 只讨论N中某一列变化情况 与增加变量xn 1的情况类似 假设pj变化 那么 重新计算出B 1pj j cj criarij填入最优单纯形表 若 j 0则最优解不变 否则 进一步用单纯形法求解 例子从略 2 4利用LINGO软件求解线性规划模型 求解线性规划模型的LINGO程序 LINGO软件灵敏度分析方法 注 带 的为本科生选修内容 2 4 1求解线性规划模型的LINGO程序 对于决策变量少 约束条件数量不多的线性规划模型来说 LINGO软件求解起来非常简单 只需要按照LINGO程序的书写规则将线性规划模型直接输入LINGO的程序窗口就可以方便地求解 例2 17用LINGO求解例2 3和例2 5 解 求解例2 3的LINGO程序清单如下 model max 2 x1 3 x2 2 x1 2 x2 12 x1 2 x2 8 4 x1 16 4 x2 12 end Globaloptimalsolutionfound Objectivevalue 14 00000Totalsolveriterations 2VariableValueReducedCostX14 0000000 000000X22 0000000 000000 运行得到 即最优解为与用图解法和单纯形法求解的结果相同 求解例2 5的LINGO程序清单model min 3 x1 x2 x3 x1 2 x2 x3 3 2 x1 x3 1 end Globaloptimalsolutionfound Objectivevalue 2 000000Totalsolveriterations 0VariableValueReducedCostX14 0000000 000000X21 0000000 000000X39 0000000 000000 2 4 2LINGO软件灵敏度分析方法 灵敏度分析是在求解模型时作出的 因此在求解模型时灵敏度分析应是处于激活状态 但是默认是不激活的 激活灵敏度分析的步骤 1 从LINGO软件的主窗口运行LINGO Options 2 选择GeneralSolverTab 3 在DualComputations列表框中 选择PricesandRanges选项 4 点击OK按钮即告完成 例2 18某公司用甲 乙和丙三种资源生产A B和C三种产品 生产数据如表2 31所示 表2 31 若要求B产品的生产量不超过5件 如何安排三种产品的生产可使利润最大 解 用x1 x2和x3分别表示三种产品的生产量 建立LP模型 并输入到LINGO程序窗口中 程序清单如下 max 60 X1 30 X2 20 X3 8 X1 6 X2 X3 48 4 X1 2 X2 1 5 X3 20 2 X1 1 5 X2 0 5 X3 8 X2 5 激活灵敏度分析并求解此模型 这时 查看报告窗口 ReportsWindow 可以看到如下的计算结果 Globaloptimalsolutionfoundatiteration 3Objectivevalue 280 0000VariableValueReducedCostX12 0000000 000000X20 0000005 000000X38 0000000 000000RowSlackorSurplusDualPrice1280 00001 000000224 000000 00000030 00000010 0000040 00000010 0000055 0000000 000000 结果的第一行表示3次迭代后得到全局最优解 第二行表示最优目标值为280 Value 给出最优解中各变量的值 即x1 2 x2 0 x3 8 ReducedCost 列出最优单纯形表中判别数所在行的变量的系数 表示当变量有微小变动时 目标函数的变化率 其中基变量的reducedcost值应为0 对于非基变量 相应的r