线性规划灵敏度分析演示教案(Max型).ppt

第五讲线性规划的灵敏度分析 线性规划的灵敏度分析 在线性规划问题中 都假定A b C中的元素aij bi cj是已知常数 但实际上这些数往往是一些估计或预测的数字 如市场条件一变 cj值就会变化 aij是随工艺技术条件的改变而改变 而bi值是根据资源投入后能产生多大经济效益来决定的一种决策选择 因此 当这些参数中的一个或几个发生变化时 线性规划问题的最优解会有什么变化 或者这些参数一个或多个在什么范围内变化时 问题的最优解是不变的 这就是灵敏度分析 当然 当线性规划问题中的一个或几个参数发生变化时 可用单纯形法从头计算 看一看最优解有无变化 但这样做既麻烦又没必要 因为单纯形法的迭代是从一个基到另一个基去寻找最优解的 因此当一个或几个参数发生变化时 我们从最优单纯形表去分析 去寻找即可 一 非基变量系数Cj的灵敏度分析 设线性规划的标准形式 设B是 LP 的最优基 对应的单纯形表为 C CBB 1A b01 b02 b0n b0j Cj CBB 1Pj 当xj的价值系数Cj有改变量 Cj 即Cj变成C Cj Cj 一 非基变量系数Cj的灵敏度分析 设xj的价值系数Cj有改变量 Cj 此时Xj的检验数 其它检验数没改变 由Cj CBB 1Pj Cj Cj CBB 1Pj b0j Cj 1 当 Cj b0j 0时 则基B仍是 LP 的最优基 最优值和最优解都不变 此时原单纯形表中的检验数b0j用 Cj b0j代替利用单纯形法迭代 得新问题的最优解 2 当 Cj b0j 0时 则基B仍是 LP 的可行基 但不是最优基 某厂利用三种资源B1 B2 B3生产三种产品A1 A2 A3 其中B1为劳动力 单位 人 B2为流动资金 单位 元 B3为主要设备 单位 台时 在一个生产周期内 各资源的供应数量 单位产品对各资源的消耗数及单位产品的销售价格如下表所示 如何组织该周期内各种产品的生产 使总产值最大 已知该问题的线性规划模型为如下 其中X1 X2 X3分别为产品A1 A2 A3的产量 X4 X5 X6为引入的松驰变量 非基变量系数Cj的灵敏度分析 例1 例1 2 的最优单纯形表为如下 1 若产品A3的销售价格C3发生变化时 C3在什么范围内变化时 原来最优解保持不变 2 若产品A3的销售价格C3变为10时的最优解 解 1 因C3变为非基变量x3的系数 例1 3 其检验数b03 4 设C3的改变量为 C3 要使原最优解不变 则必须 b03 C3 0 即 4 C3 0 C3 4 C3 3 4 7 因此当C3 7 价格小于等于7时 原最优解不变 2 当C3变为10时 则 C3 7 b03 C3 3 2 基变量的价值系数Cj的灵敏度分析 此时Cj的在CB中 故Cj的变化引起所有检验数都有可能变化 设Xj的系数Cj的改变量为 Cj 则检验数由C CBB 1A 1 当 有大于0时 2 当 我们可从不等式组 得到 Cj的变化范围 此时可利用单纯形法迭代 得新问题的最优解 2 基变量的价值系数Cj的灵敏度分析 在解具体问题时 解不等式组 不等式组可通过如下方式得到 先在原最优单纯形表中将xj的检验数替换为 Cj 然后 将 Cj化为0 可得到不等式组 再求解 某厂利用三种资源B1 B2 B3生产三种产品A1 A2 A3 其中B1为劳动力 单位 人 B2为流动资金 单位 元 B3为主要设备 单位 台时 在一个生产周期内 各资源的供应数量 单位产品对各资源的消耗数及单位产品的销售价格如下表所示 如何组织该周期内各种产品的生产 使总产值最大 价值系数Cj的灵敏度分析 例2 已知该问题的线性规划模型为如下 其中X1 X2 X3分别为产品A1 A2 A3的产量 X4 X5 X6为引松入的驰变量 例2 2 的最优单纯形表为如下 1 若产品A1的销售价格C1发生变化时 C1在什么范围内变化时 原来最优解保持不变 2 产品A1的销售价格C1 10时的最优解 解 1 因C1为基变量x1的系数 例2 3 解 1 因C1为基变量x1的系数 设其改变量为 C1 例2 4 4 C1 0 3 C1 0 1 C1 0 故4 C1 8 C1 4 C1 3 C1 1 C1 5 则基B仍是 LP 的最优基 但最优值变成 2 因C1 10 1 C1 3 例2 5 最优解x1 40 x2 0 x3 0 x4 5 x6 50 则最优值z 400 二 约束条件右端常数项bi的灵敏度分析 设B是 LP 的最优基 设bi变为b i bi bi 则变化后的线性规划为 因为常数项b的变动 不影响单纯形表中的检验数 故原问题 Lp 的最优基是改变后问题的对偶可行基 二 约束条件右端常数项bi的灵敏度分析 2 故原问题的最优基是改变后问题的对偶可行基 基B是否为 LP2 的最优基 取决于是否成立 只要 则原问题的最优基B是新问题的最优基 二 约束条件右端常数项bI的灵敏度分析 3 我们可通过解不等式组 即 求出 bi允许变化的范围 当超出允许值之外 B不再是最优基 可用对偶单纯形法继续求最优解 注 当B仍是最优基时 但最优解却不同 右端常数项bI的灵敏度分析 例子 某厂利用三种资源B1 B2 B3生产三种产品A1 A2 A3 其中B1为劳动力 单位 人 B2为流动资金 单位 元 B3为主要设备 单位 台时 在一个生产周期内 各资源的供应数量 单位产品对各资源的消耗数及单位产品的销售价格如下表所示 如何组织该周期内各种产品的生产 使总产值最大 已知该问题的线性规划模型为如下 其中X1 X2 X3分别为产品A1 A2 A3的产量 X4 X5 X6为引松入的驰变量 例子 2 的最优单纯形表为如下 1 根据上述表格试对资金b2进行灵敏度分析 若资金限量改为100元 求最优生产方案 2 若劳务市场每个劳动力在一个生产周期内的工资为2元 问从劳务市场雇用工人参加生产是否值得 若值得 最多可增加多少工人 此时总产值增加多少 例子 2 1 解 1 b2 80 b2 20 由最优单纯形表知 则原最优基B是新问题的对偶可行基 新单纯形表如下 例子 2 2 则原最优基B是新问题的对偶可行基 新单纯形表如下 换基迭代得下列单纯形表 则得到新的最优解 45 0 0 0 10 45 和最优值225 三 增加一个新决策变量时的灵敏度分析 若在 LP 中增加一个决策变量xn 1 其系数列向量为pn 1 xn 1的价值系数为cn 1 则 LP 变成 设B是 LP 的最优基 则B也是 LP3 的一个基 并且与其对应的单纯形表如下 三 增加一个新决策变量时的灵敏度分析 2 显然 B是 LP3 的可行基 1 若Cn 1 CBB 1Pn 1 0 则B是 LP3 的最优基 2 若Cn 1 CBB 1Pn 1 0 则B是 LP3 的可行基 而非最优基 此时又有两种情形 I 若B 1Pn 1 0 则 LP3 无最优解 ii 若B 1Pn 1中至少有一个正数 则利用单纯形法继续迭代求出最优解 三 增加一个新决策变量时的灵敏度分析 例子 某厂利用三种资源B1 B2 B3生产三种产品A1 A2 A3 其中B1为劳动力 单位 人 B2为流动资金 单位 元 B3为主要设备 单位 台时 在一个生产周期内 各资源的供应数量 单位产品对各资源的消耗数及单位产品的销售价格如下表所示 如何组织该周期内各种产品的生产 使总产值最大 已知该问题的线性规划模型为如下 其中X1 X2 X3分别为产品A1 A2 A3的产量 X4 X5 X6为引松入的驰变量 1 设工厂计划生产新产品A4 生产一个A4单位所消耗的人力 资金 设备时数分别为1 2 3 问在怎样的销售价格下 投产产品A4 才有利 如投产产品A4 怎样安排新的最优生产计划 例3 1 的最优单纯形表为如下 解 设产品A4的产量为x7 其销售价格为C7 例3 2 C7 CBB 1P7 C7 5 CB 4 5 0 则在原最优单纯形表中加上X7这一列 X7B 1P7C7 CBB 1P7 X7012C7 5 因此 当A4产品的价格大于5时 投产产品A4才有利 例3 3 X7012C7 5 X70010 四 添加一个新约束条件时的灵敏度分析 在 LP 中添加一个新约束条件Am 1X bm 1 其中Am 1 am 1 1am 1 2 am 1 n 则 LP 变成了 设B是 LP 的一个最优基 但它不是 LP4 的一个基 四 添加一个新约束条件时的灵敏度分析 2 1 若原问题 LP 的最优解 X x1 x2 xn 2 若X 不满足新约束条件 满足新的约束条件 Am 1X am 1 1x1 am 1 2x2 am 1 nxn bm 1 则X 是新问题 LP4 的最优解 则X 不是新问题 LP4 的可行解 则可按如下进行分析 引进松驰未知量Xn 1化新约束条件为等式 即 am 1 1x1 am 1 2x2 am 1 nxn xn 1 bm 1 设B是 LP 的一个最优基 记 四 添加一个新约束条件时的灵敏度分析 3 显然 故是 LP4 的一个基 新问题 LP4 对应基的单纯形表可由 LP 对应的基B的单纯形表T B 来推得 上表不是 LP4 对应基的单纯形表因为基变量对应的列不是单位向量 但可通过初等变换得到对应基的单纯形表 四 添加一个新约束条件时的灵敏度分析 4 而形成过程中 检验数仍然不变 即小于或等于0 因此 基是问题的对偶可行基 例4 1 某厂利用三种资源B1 B2 B3生产三种产品A1 A2 A3 其中B1为劳动力 单位 人 B2为流动资金 单位 元 B3为主要设备 单位 台时 在一个生产周期内 各资源的供应数量 单位产品对各资源的消耗数及单位产品的销售价格如下表所示 如何组织该周期内各种产品的生产 使总产值最大 已知该问题的线性规划模型为如下 其中X1 X2 X3分别为产品A1 A2 A3的产量 X4 X5 X6为引松入的驰变量 例4 2 的最优单纯形表为如下 设增加一个用电限制条件 生产产品 A1 A2 A3的一个单位的耗电量分别为1 2 2 度 而一个生产周期内总耗电量不超过43度 问此时应如何安排生产 使总产值最大 例