第二章线性规划ppt课件

3 运筹学的主要内容 线性规划 非线性规划 整数规划 多目标规划 动态规划 图与网络模型 存储论 排队论 对策论 决策分析 排序与统筹方法 随机规划 模糊规划 预测 1.2 运筹学的数学模型 模型的定义 : 模型是一件实际事物或情况的代表或抽象。实际事 物是 A， 若 B能够真实地描述 A， 则称 B为 A的模型。 数学模型就是用字母、数字和运算符号将系统或过 程的某些特征及相互关系表达出来，他试图定量地 表示系统的各种关系，以便对系统和问题进行量化 分析。 第 2章 线性规划 线性规划问题 可行区域与基本可行解 单纯形方法 初始解 对偶性及对偶单纯形方法 灵敏度分析 2.1 线性规划问题 线性规划问题举例 线性规划模型 1 线性规划问题举例 生产计划问题 运输问题 营养配餐问题 资金使用问题 1 线性规划问题举例（一） 某工厂拥有 A、 B、 C三种类型的设备，生产甲、乙两种 产品。已知条件如下表所示： 产品甲 产品乙 设备能力 设备 A 3 2 65 设备 B 2 1 40 设备 C 0 3 75 利润（元 /件） 1500 2500 问题：工厂应如何安排生产可获得最大的总利润？ 1 线性规划问题举例（一） 解：设生产两种产品的数量分别为 x1,x2， 总利润为 z. 目标函数 约束条件 1 线性规划问题举例（二） 设要从甲地调出物资 2000吨，从乙地调出物资 600吨，从丙地调 出物资 500吨，分别供应给 A地 1700吨、 B地 1100吨、 C地 200吨、 D地 100吨。已知每吨运费如下表所示。 17263843 15375151乙 1572521甲 DCBA 销地产地 单位：元 /t 丙 假定运费与运量成正比例，问怎样才能找到一个总运费最省的 调拨计划？ 2 3 2 1 3 4 1 600 500 1700 1100 200 100 2000 供应量 供应地 运价 需求量 需求地 2125 715 5151 3715 4338 26 17 1 线性规划问题举例（二） 17263843 15375151乙 1572521甲 DCBA 销地产地 丙 x22 x11 x12 x13 x21 x23 x31 x32 x33 x14 x24 x34 1 线性规划问题举例（二） 用 (i=1,2,3; j=1,2,3,4)分别表示从甲乙丙三个产地运往 A,B,C,D四个销地的物资数量。 1 线性规划问题举例（二） 1 线性规划问题举例（二） 简化表达式 1 线性规划问题举例（三） 假定一个成年人每天需要从食物中获得假定一个成年人每天需要从食物中获得 3000千卡的热量、千卡的热量、 55克克 蛋白质和蛋白质和 800毫克的钙。市场情况见下表。问如何选择才能在毫克的钙。市场情况见下表。问如何选择才能在 满足营养的前提下使购买食品的费用最小？满足营养的前提下使购买食品的费用最小？ 食品名称 热 量 (千卡 ) 蛋白 质 (克 ) 钙 (毫克 ) 价格 (元 ) 猪肉 鸡 蛋 大米 白菜 1000 800 900 200 50 60 20 10 400 200 300 500 30 9 6 3 1 线性规划问题举例（三） 解：设解：设 xj为第为第 j种食品每天的购入量，则配餐问题的种食品每天的购入量，则配餐问题的 线性规划模型为：线性规划模型为： min z=30x1+9x2 +6x3+3x4 s.t. 1000x1+800x2 +900x3+200x4 3000 50x1+ 60x2 + 20x3+ 10x4 55 400x1+200x2 +300x3+500x4 800 x1， x2 ， x3 ， x4 0 1 线性规划问题举例（四） 设有设有 400万元资金，要求万元资金，要求 4年内使用完，若在一年内年内使用完，若在一年内 使用资金使用资金 万元，则可得到效益万元，则可得到效益 万元，（效益不万元，（效益不 能再次使用），当年未使用的资金可存入银行，年能再次使用），当年未使用的资金可存入银行，年 利率为利率为 10%，试制定出资金的使用计划，以使，试制定出资金的使用计划，以使 4年年 资金效益之和最大。资金效益之和最大。 1 线性规划问题举例（四） 设变量设变量 分别表示第分别表示第 年所使用的资金数年所使用的资金数解：解： 1 线性规划问题举例（四） 线性规划问题的结构特征 都有一组决策变量； 都有一组约束条件，它们是 线性 等式或不等式； 都有一个确定的目标，这个目标可以表示成决策变量 的 线性 函数，根据问题不同，有的要求实现极大化，有 的要求实现极小化。 线性规划问题的本质：研究在一组 线性 约束下，一 个 线性 函数的极值问题 。 2 线性规划模型 一般形式 标准形式 形式转换 2 线性规划模型（一般形式） 目标函数 约束条件 2 线性规划模型（标准形式） min z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a 1n xn = b1 a21 x1 + a22 x2 + + a 2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ， x2 ， ， xn 0 目标函数 约束条件 2 线性规划模型（标准形式） 2 线性规划模型（标准形式） 用用 向量向量 表示表示 用用 矩阵矩阵 表示表示 2 线性规划模型（标准形式） 2 线性规划模型（标准形式） 标准形式的特点 ： 目标函数极小化 约束条件全部是等式 所有的变量都是非负的 2 线性规划模型（形式转换） 令 xj= xj- xj，对模型中的进行变量代换。 目标函数为 max z=c1x1+c2x2+ +cnxn 令 z=-z ,变为 min z= -c1x1- c2x2- -cnxn 约束条件为 a11x1+a12x2+ +a1nxnb1 加入非负变量 xn+1，称为松弛变量，有 a11x1+a12x2+ +a1nxn+xn+1=b1 约束条件为 a11x1+a12x2+ +a1nxnb1 减去非负变量 xn+1，称为剩余变量，有 a 11x1+a12x2+ +a1nxn - xn+1=b1 变量 xj无约束。 2 线性规划模型（形式转换） 例：将如下线性规划问题化成标准形式： 2.2 可行区域与基本可行解 基本概念 图解法求解两个变量的线性规划问题 可行区域的几何结构 基本可行解及线性规划的基本定理 1 基本概念 1 基本概念 对于标准的对于标准的 LP问题来说问题来说 满足这两个条件的满足这两个条件的 x是可行解是可行解 或者可行点或者可行点 三者皆满足是三者皆满足是 最优解最优解 2 图解法求解两个变量线性规划问题（ 1） max z=x1+3x2 s.t. x1+x26 -x1+2x28 x1, x20 可行域 目标函数等值线 最优解 6 4 -8 6 0 x1 x2 最优解为最优解为 x=(4/3,14/3)T 最优值最优值 z=4/3+14=46/3 2 图解法求解两个变量线性规划问题（ 2） max z=3x1+3x2 s.t. x1+ x26 -x1+2x28 x1, x20 可行域 目标函数等值线 6 4 -8 6 0 x1 x2 最优解最优解 ? 最优值最优值 ? 2 图解法求解两个变量线性规划问题（ 3） max z=3x1+3x2 s.t. -x1+2x28 x1, x20 可行域 目标函数等值线 4 -8 0 x1 x2 最优解最优解 ? 最优值最优值 ? minz=3x1+3x2? 2 图解法求解两个变量线性规划问题（ 4） max z=3x1+3x2 s.t. -x1+2x28 x1-2x2-9 x1, x20 可行域可行域 ? 2 图解法求解两个变量线性规划问题 在边界，而且是在某个顶点获得。 多边形，而且是 “凸 ”形的多边形。 线性规划的可行域是一个什么形状？ 最优解 (如果存在 )在什么位置获得？ 两变量线性规划问题解的性质 2 图解法求解两个变量线性规划问题 1）唯一解 2）多重最优解 3）无有限最优解 4）无可行解 求解线性规划问题可能出现哪些情况？ 3 可行区域的几何结构 基本假设 凸集 可行域的凸性 问题 3 可行区域的几何结构（基本假设） 3 可行区域的几何结构（凸集） 3 可行区域的几何结构（凸集） 3 可行区域的几何结构（凸集） 3 可行区域的几何结构（凸集） 定义 2.2.4： 设 为凸集， 如果对任意 和任意 ，都有 则称 x为 S的 顶点 。 3 可行区域的几何结构（可行域的凸性） 定理 2.2.1 是凸集。 定理 2.2.2 任意多个凸集的交集还是凸集。 3 可行区域的几何结构（可行域的凸性） 3 可行区域的几何结构（问题） 4 基本可行解及线性规划的基本定理 定义 基本定理 结论 问题 4基本可行解及线性规划的基本定理（定义） 基基 (基阵基阵 )： 设设 B是秩为是秩为 m的约束矩阵的约束矩阵 ARmn中的一个中的一个 m 阶满秩子方阵，则称阶满秩子方阵，则称 B为一个为一个 基基 （ 基阵基阵 ） 。 基向量：基向量： B中中 m个线性无关的列向量称为个线性无关的列向量称为 基向量基向量 。 基变量：基变量： 变量变量 x中与基向量对应的中与基向量对应的 m个分量称为个分量称为 基变量基变量 . 其余的分量称为其余的分量称为 非基变量非基变量 。 基本解：基本解： 令所有的非基变量取值为零得到的解。令所有的非基变量取值为零得到的解。 基本可行解：基本可行解： 既是基本解又是可行解。既是基本解又是可行解。 可行基：可行基： 基本可行解对应的基基本可行解对应的基 B。 = 目标函数 约束条件 基矩阵 右边常数= 基变量 4基本可行解及线性规划的基本定理（定义） 基本解 基本可行解 可行基 4基本可行解及线性规划的基本定理（定义） 例：考虑如下线性规划问题，用图解法求解，并把它例：考虑如下线性规划问题，用图解法求解，并把它 化成标准形式，且指出基、基解：化成标准形式，且指出基、基解： 4基本可行解及线性规划的基本定理（定义） 0 x1 x2 4基本可行解及线性规划的基本定理（定义） 4基本可行解及线性规划的基本定理（定义） 0 x1 x2 （ 0， 0） （ 4， 0） （ 4， 2） （ 0， 4） （ 8， 0） 4基本可行解及线性规划的基本定理（定理） 4基本可行解及线性规划的基本定理（结论） 线性规划问题的可行域是凸集。 基本可行解与可行域的顶点对应，可行域有有限多 个顶点 (基本可行解 )。 最优解一定可以在某个顶点上 (基本可行解 )得到。 非可行解非可行解 可行解 基可行解 基解基解 最优解？ 4基本可行解及线性规划的基本定理 （结论与问题） 4基本可行解及线性规划的基本定理（总结） 求解 LP的基本思路 1、构造初始可行基；、构造初始可行基； 2、求出一个基可行解（顶点）；、求出一个基可行解（顶点）； 3、最优性检验：判断是否最优解；、最优性检验：判断是否最优解； 4、基变换，转、基变换，转 2。要保证目标函数值比原来更优。要保证目标函数值比原来更优。 2.3 单纯形方法 1947年由 Dantzig提出，被称为 20世纪最好的十个算法之一， 是迄今为止解决线性规划问题的最成熟的方法。 2.3 单纯形方法 典式 基本定理 单纯形方法 单纯形表（单纯形方法的实现） = 1 典式 (定义 ) = 1 典式（定义） 0 01 1 00 0 10 0 0 0 1 典式（定义） 典式的特点： 1、 约束条件中含有一个单位矩阵； 2、目标函数中不含基变量。 0 00 0 01 1 00 0 10 = 1 典式（定义） 0 00 0 01 1 00 0 10 = 1 典式（例） 1 典式（定义） 问题：如何判断一个基本可行解是否为最优解呢？ 典则形式的 LP问题中，目标函数中的变量系数的符号， 对于 判断某一个基本可行解是不是最优解非常重要。 本例中 是什么？ 典则形式的 LP问题中，目标函数系数向量的负向量。 称为检验数向量 . 2 基本定理 定理 2.3.1 例如： 2 基本定理 例如： 定理 2.3.2 则原问题无界。 2 基本定理 例如： 定理 2.3.3对 应 则 2 基本定理 定理 2.3.4 对于任何非退化的线性规划问题，从任何基 本可行解开始，经过有限多次迭代，或者得到一个基本 可行解，或者作出该线性规划问题无界的判断。 3 单纯形方法 Step 1 将线性规划问题化成典式 ,求出各个非基变量的检验数。 Step 2 判断所有非基变量的检验数是否非正 ,若是 ,则结束；否 则转 step 3。 Step 3 选取一个检验数大于零的非基变量为进基变量； Step 4 若进基变量所对应的约束条件系数全为非正数 ,则原问题 无界 ,结束；否则 ,按最小比值原则确定出基变量； Step 5 进行迭代 (用方程组的初等 行 变换法确定新的基对应的典 式及检验数 ),转 step 2。 4 单纯形表例 1 求解 LP问题 Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 2 x1 x2 x3 x4 x5 RHS Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 2 x1 x2 x3 x4 x5 RHS 0 0 1 -1 -1 2 1 0 -5 2 0 1 -3 1 0 0 2 -1 4 1 检验数检验数 转轴元转轴元 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1 Z 0 0 0 -0.5 -0.5 -1.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 最优解：最优解： x*=(6.5, 2.5, 0.5, 0, 0)T 最优值：最优值： z*= -1.5 例 2： 解解 LP问题问题 4 单纯形表 Z 0 1 2 0 0 0 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 x1 x2 x3 x4 x5 Z 0 0 0 1.5 -2.5 -3.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 此问题无界此问题无界 RHS 例 3： 解解 LP问题问题 4 单纯形表 Z 0 0 0 0 -1 18 x1 x4 x2 1 0 1 0 0 0 0 3 1 -1 0 1 -3/2 0 1/2 4 6 3 x1 x2 x3 x4 x5 Z 0 0 0 0 -1 18 x1 x3 x2 1 0 0 -1/3 1/3 0 0 1 1/3 -1/3 0 1 0 1/2 0 2 2 6 此问题有多解。此问题有多解。 RHS 2.4 初始解（两阶段法） 问题：线性规划 问题化为标准型时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？ 2.4 初始解（两阶段法） 第一阶段： 加入人工 变 量 ,构造初始可行基 . 用 单纯 形法求解 ,若 g=0, 进 入第二 阶 段 ,否 则 ,原 问 题 无可行解。 第二 阶 段 ：去掉人工 变 量， 还 原目 标 函数系数，做 出初始 单纯 形表。 例：求解下列线性规划问题 将原 问题 化成 标 准型：解解 : 化标准型 用两阶段方法来求解。 第一阶段 的线性规划问题为 x1 x2 x3 x4 x5 x6 x7 g 0 0 0 0 0 -1 -1 0 X4 X6 X7 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 9 RHS x1 x2 x3 x4 x5 x6 x7 RHS g -2 4 0 0 -1 0 0 10 X4 X6 X7 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1 4 1 9 g 6 0 4 0 3 -4 0 6 X4 X2 X7 3 0 2 1 1 -1 0 -2 1 -1 0 -1 1 0 6 0 4 0 3 -3 1 3 1 6 g 0 0 0 0 0 -1 -1 0 X4 X2 X1 0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6 0 3 1 x1 x2 x3 x4 x5 x6 x7 RHS 得原问题的基可行解 X=(1,3,0,0,0,)T。 第二阶段： 将上表中的人工变量去除，目标函数换成原问题的 目标函数从上表的最后一个单纯形表出发，继续计算。 Z -3 0 1 0 0 0 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 1 x1 x2 x3 x4 x5 RHS Z 0 0 3 0 3/2 3 X4 X2 X1 0 0 0 1 -1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 0 3 1 Z -9/2 0 0 0 -3/4 -3/2 X4 X2 X3 0 0 0 1 -1/2 -1/2 1 0 0 -1/4 3/2 0 1 0 3/4 0 5/2 3/2 x1 x2 x3 x4 x5 RHS 得原标准线性规划问题的最优解 X=（ 0， 5/2， 3/2， 0， 0） T， 最优值是 -3/2。 所以最初的线性规划问题的最优解 X=（ 0， 5/2， 3/2） T， 最优 值是 3/2。 例：求解下列线性规划问题 将原 问题 化成 标 准型：解解 : 化标准型 用两阶段方法来求解。 第一阶段 的线性规划问题为 x1 x2 x3 x4 x5 x6 RHS g 0 0 0 0 -1 -1 0 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 x1 x2 x3 x4 x5 x6 RHS g 7 4 -1 0 0 0 9 X5 X6 X4 3 1 0 0 1 0 4 3 -1 0 0 1 1 2 0 1 0 0 3 6 3 g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2 x1 x2 x3 x4 x5 x6 RHS g 0 5/3 -1 0 -7/3 0 2 X1 X6 X4 1 1/3 0 0 1/3 0 0 5/3 -1 0 -4/3 1 0 5/3 0 1 -1/3 0 1 2 2 g 0 0 -1 -1 -2 0 0 X1 X6 X2 1 0 0 -1/5 2/5 0 0 0 -1 -1 -1 1 0 1 0 3/5 -1/5 0 3/5 0 6/5 g 0 0 -1 -1 -2 0 0 X1 X6 X2 1 0 0 -1/5 2/5 0 0 0 -1 -1 -1 1 0 1 0 3/5 -1/5 0 3/5 0 6/5 x1 x2 x3 x4 x5 x6 RHS 0 0 0 0 -1 -1 3 0 0 1 1 1 -1 第二阶段： 将上表中的人工变量去除，目标函数换成原问题的 目标函数从上表的最后一个单纯形表出发，继续计算。 z -4 -1 0 0 0 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5 x1 x2 x3 x4 RHS z 0 0 0 -1/5 18/5 X1 X3 X2 1 0 0 -1/5 0 0 1 1 0 1 0 3/5 3/5 0 6/5所以最初的线性规划问题的最优解 X=(3/5， 6/5)T， 最优值是 18/5。 例：求解下列线性规划问题 将原 问题 化成 标 准型：解解 : 化标准型 用两阶段方法来求解。 第一阶段 的线性规划问题为 x1 x2 x3 x4 x5 x6 RHS g 0 0 0 0 -1 -1 0 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 x1 x2 x3 x4 x5 x6 RHS g 1 -2 -1 -1 0 0 5 X5 X6 2 -3 -1 0 1 0 -1 1 0 -1 0 1 2 3 g 0 -1/2 -1/2 -1 -1/2 0 4 X1 X6 1 -3/2 -1/2 0 1/2 0 0 -1/2 -1/2 -1 1/2 1 1 4 原问题无解。 两阶段方法总结 第一阶段结束时，辅助问题目标函数值大于 0，原 问题无解； 第一阶段结束时，辅助问题目标函数值等于 0，且 人工变量都是非基变量，那末，所得基本可行解 为原问题初始基本可行解，去掉人工变量，目标 函数行换为原问题目标函数，继续求解。 第一阶段结束时，辅助问题目标函数值等于 0，但 是人工变量不都是非基变量，那么令其强行出基 ，然后继续求解。 小 结 线性 规划 问题 图解法只有两个变量 约束矩阵 A中 含有一个 m阶 的单位矩阵 右端向量非负 单纯形方法 约束矩阵 A中 没有一个 m阶 的单位矩阵 两阶段法 2.5 对偶性及对偶单纯形方法 对偶问题的提出 原问题与对偶问题的数学模型 原问题与对偶问题的关系 对偶单纯形法 1 对偶问题的提出 例：某家电厂生产两种产品，有关数据如下表： 设备 A 设备 B 调试工序 售价（元） 0 6 1 2 5 2 1 1 15 24 5 产品 产品 资源 如何安排生产， 使获利最多 ？ 厂 家 1 对偶问题的提出 设备 A 设备 B 调试工序 售价（元） 0 6 1 2 5 2 1 1 15 24 5 产品 产品 资源 收 购 付出代价 最小，且对方 能接受。 出让代价应不低于 用同等数量的资源 自己生产的收益。 1 对偶问题的提出 收 购 厂 家 一对对偶问题 2 原问题与对偶问题的数学模型 其它形式 的对偶 ? 2 原问题与对偶问题的数学模型 原问题（原问题（ P） 对偶问题（对偶问题（ D） 例 写出线性规划问题的对偶问题： 2 原问题与对偶问题的数学模型 3 原问题与对偶问题的关系 收 购 厂 家 一对对偶问题 3 原问题与对偶问题的关系 z 0 0 0 -1/4 -1/2 -17/2 x3 x1 x2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 15/2 7/2 3/2 y -15/2 0 0 -7/2 -3/2 17/2 w2 w3 -5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2 1/4 1/2 3 原问题与对偶问题的关系 原问题与对偶问题在某种意义上来说，实质上是一样 的，因为第二个问题仅仅在第一个问题的另一种表达 而已。 理论证明： 原问题与对偶问题解的关系 3 原问题与对偶问题的关系 定理 2.5.2 对偶的对偶为原始问题。（对称性） 3 原问题与对偶问题的关系 定理 弱对偶定理（弱对偶性）：设 和 分别是问题 （ P）和（ D）的可行解，则必有 3 原问题与对偶问题的关系 定理 2.5.1 如果一个 LP问题有最优解，则它的对偶问题 也有最优解，且它们的最优值相等。（强对偶定理） 推论（ 最优性判别定理） 原始问题和对偶问题的可 行解 x, w分别是最优解的充要条件是 cTx=wTb。 无界 （对偶） 无可 行解 （原始） 3 原问题与对偶问题的关系 3 原问题与对偶问题的关系 显然，这两个问题都无可行解。 综上所述，一对对偶问题的关系，只能有下面三种情况之 一出现： 都有最优解，分别设为 X* 和 Y*，则必有 CTX* =bTY*； 一个问题无界，则另一个问题无可行解； 两个都无可行解。 3 原问题与对偶问题的关系 定理 2.5.3 原始 LP与其对偶必为下面三种情况之一出现 P D 有最 优 解 问题 无 界 无可行解 有最 优 解 (1) 问题 无 界 (3) 无可行解 (3) (2) 3 原问题与对偶问题的关系 定理 2.5.4 设 x和 w分别是原始问题和对偶问题的可行解， 则它们是原始问题和对偶问题的最优解的充要条件是对 一切 i=1,2,m 和一切的 j=1,2,n 有 3 原问题与对偶问题的关系 4 对偶单纯形方法 基本思路 对偶单纯形方法计算步骤 4 对偶单纯形方法（基本思路） 对偶单纯形法是求解线性规划的另一种基本方法。它 是根据对偶原理和单纯形法的原理而设计出来的，因 此称为对偶单纯形法。不要简单理解为是求解对偶问 题的单纯形法。 4 对偶单纯形方法（计算步骤） 例： 解：将原问题化成标准形： 0 -6 -1 1 0 -2 -15 -24 -5 0 0 4 对偶单纯形方法（计算步骤） z 2 -5 -2 -1 0 1 -1 x4 x5 x1 x2 x3 x4 x5 RHS 4 对偶单纯形方法（计算步骤） z -15 -24 -5 0 0 2 x4 x5 0 -6 -1 1 0 -5 -2 -1 0 1 -2 -1 0 1 1/6 -1/6 0 1/3 -5 0 -2/3 -1/3 1 -1/3 x2 -15 0 -1 -4 0 10 x1 x2 x3 x4 x5 RHS 4 对偶单纯形方法（计算步骤） z -15 0 -1 -4 0 10 x2 x5 0 1 1/6 -1/6 0 -5 0 -2/3 -1/3 1 1/3 -1/3 z -15/2 0 0 -7/2 -3/2 21/2 x2 x3 -5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2 1/4 1/2 x1 x2 x3 x4 x5 RHS 2.6 灵敏度分析 灵敏度分析概念 如何进行灵敏度分析 价值向量的灵敏度分析 右端向量的灵敏度分析 Cj 市场条件 aij 工艺技术条件 bi 根据资源投入后能产生经济效果来决定的一 种决策选择 灵敏度分析 是指对系统或事物因周围条件变化显示 出来的敏感程度的分析。 1 灵敏度分析概念 灵敏度分析解决什么问题？ 当线性规划问题的参数 aij， bi， cj中一个或几个发 生改变时，线性规划问题 最优解变化的分析 ；或上 述 参数在多大范围内变化 时，线性规划问题最优解 不变的分析。 1 灵敏度分析概念 2 如何进行灵敏度分析 1、根据改变后的参数生成新的问题，用单纯形法 从头计算，看最优解是否改变； 2、将改变后的参数直接反映到原线性规划问题的最终 单纯形表中，看最优解是否改变。 （采用此方法） 2 如何进行灵敏度分析 3 价值向量的灵敏度分析 例 线 性 规 划 最优单纯形表： z 0 -1/2 0 -11/4 -9/4 31/4 x