2.线性规划的对偶理论(第二部分)

§4、影子价格 --对偶最优解的经济含义 --对偶最优解的经济含义

Z = y b Z = y bi

i

说明：yi 的值相当于在给定的生产条件下， bi每增加一个单位时目标函数的增量。

影子价格第i个约束条件的影子价格的经济含义是：其 它条件不变的情况下，该资源单位的变化所引 起的目标函数最优值的变化量 在现有的技术和管理条件下，某种资源的影子 价格越大，说明该资源对目标增益的影响越大， 同时该资源越紧缺和贵重，应该给与高度关注， 通过降低消耗或设法补充，提高收益

某种资源的影子价格为零，说明该资源相对富裕；一 方面可以转让该资源；另一方面，通过挖潜和增加对 影子价格大于零资源的投入，使原有的剩余资源充分 利用，甚至于成为新的紧缺资源 影子价格不是市场价格，而是在现有技术和管理条件 下，新增单位资源所能够创造的价值，是特定企业的 一种边际价格；不同企业或同一企业不同时期，同种 资源的影子价格可能不同；当市场价格高于影子价格， 可以卖出；相反，则应买进，以获取更大收益

= 2 x1 MaxZ 例：(第一章例2)

+ 3x2

2 x 1 + 2 x 2 ≤ 12 4 x ≤ 16 1 s .t 5 x 2 ≤ 15 x1 , x 2 ≥ 0

当第一个约束右端项增加1,变为 2 x1 + 2 x2 ≤ 13, 最优解为 z* = 16 若第二个约束右端项加1,变为 4 x1 ≤ 17 最优解不变，即设备B的边际价格为零。 若第三个约束的右端项加1,变为 5 x1 ≤ 16 最优解为 z* = 15.2

综上， 影子价格是灵敏度分析的一种 综上 ， 影子价格 是灵敏度分析的一种 形式， 通过获取 一个单位的追加的 获取一个单位 形式 ， 它 通过 获取 一个单位 的追加的 产品因素， 测量放宽一个约束条件 产品因素 ， 去 测量 放宽一个约束条件 的价值， 比较追加资源的价值和资源 的价值 ， 比较 追加资源的价值和资源 的实际成本， 的实际成本 ， 就能比较有把握地作出 各种可行的决策。

§5、对偶单纯形法一、什么是对偶单纯形法？ 什么是对偶单纯形法？ 对偶单纯形法是应用对偶原理 对偶单纯形法是应用对偶原理求解原始 是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 线性规划的一种方法 在原始问题的单 纯形表格上进行对偶处理 对偶处理。 纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！ 注意：不是解对偶问题的单纯形法！

二、单纯形法的求解过程就是： 单纯形法的求解过程就是： 在保持原始可行的前提下( 列保持 在保持原始可行的前提下(b列保持 ), 原始可行的前提下 列保持≥0) 通过逐步迭代实现对偶可行 检验数行 ) 通过逐步迭代实现对偶

可行(检验数行≤0) 。 实现对偶可行( 对偶单纯形法思想： 对偶单纯形法思想： 换个角度考虑LP 求解过程 保持对偶可行 换个角度考虑 LP求解过程 ： 保持 对偶可行 的 求解过程： 对偶可行的 前提下(检验数行保持≤ 通过逐步迭代实 前提下 ( 检验数行保持 ≤ 0 ) , 通过逐步迭代 实 现原始可行( 从非可行解变成可行解) 现原始可行 ( b列 ≥ 0 ,从非可行解变成可行解 ) 。

三、对偶单纯形法的实施 1、使用条件： ①检验数全部≤0; 使用条件： 检验数全部≤ ②资源列至少一个元素 < 0; 2、实施对偶单纯形法的基本原则： 实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换——每一 在保持对偶可行的前提下进行基变换 每一 次迭代过程中取出基变量中的一个负分量 基变量中的一个负分量作为 次迭代过程中取出基变量中的一个负分量作为 换出变量去替换某个非基变量(作为换入变 某个非基变量 换出变量去替换某个非基变量(作为换入变 ),使原始问题的非可行解向可行解靠近 使原始问题的非可行解向可行解靠近。 量),使原始问题的非可行解向可行解靠近。

3、对偶单纯形法算法步骤： ①建立初始单纯形表，计算检验数行。 建立初始单纯形表，计算检验数行。b列≥0——已得最优解； ——已得最优解 已得最优解； 检验数全部≤ 检验数全部≤0 非基变量检验数< (非基变量检验数<0) b列至少一个元素<0,转下步; 至少一个元素< 转下步;

至少一个检验数> 至少一个检验数>0

b列≥0——原始单纯形法； ——原始单纯形法 原始单纯形法；

2 基变换： 基变换： 先确定换出变量——解答列中的负元素 先确定换出变量 解答列中的负元素 选最小的负元素)对应的基变量出基 出基； (选最小的负元素)对应的基变量出基； 即

min ( B b)i ( B b)i < 0 = ( B b)l , 则选xl或yl出基，i

{

1

1

}

1

相应的行为主元行 为主元行。 相应的行为主元行。

然后确定换入变量 然后 确定换入变量 确定换入变量——原则 是 ： 在 保持对偶 原则是 原则 可行的前提下 减少原始问题的不可行性。 可行的前提下，减少原始问题的不可行性。 如果

c j z j ' ck zk min a lj < 0 = ' ' j a lk a lj

(最小比值原则 则选 x k 或y k 为换入变量， 最小比值原则),则选 为换入变量， 最小比值原则 相应的列为主元列 主元列， 相应的列为主元列，主元行和主元列交叉处' 为主元素。 的元素 a lk 为主元素。

3按主元素进行换基迭代(旋转运算、枢 按主元素进行换基迭代(旋转运算、 运算) 将主元素变成1 运算 ) , 将主

元素变成 1 , 主元列变成单位向 得到新的单纯形表。 量，得到新的单纯形表。 继续以上步骤，直至求出最优解。 继续以上步骤，直至求出最优解。

例5——用对偶单纯形法求解 ： 用对偶单纯形法求解LP: 用对偶单纯形法求解MinW = 12y1 +16y2 +15y3 2 y1 + 4 y2 ≥ 2 2 y + 5y ≥ 3 1 3 s.t. y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

§6、灵敏度分析一、灵敏度分析的含义和内容1、什么是灵敏度分析？ 、什么是灵敏度分析？ 研究线性规划模型某些参数或限制量的 变化对最优解的影响及其程度的分析过程称 为灵敏度分析或优化后分析。 为灵敏度分析或优化后分析。

2、灵敏度分析的内容： 、灵敏度分析的内容：目标函数的系数变化对最优解的影响 约束方程右端系数变化对最优解的影响 约束方程增加一个变量变化对最优解的影响 约束方程增加一个约束条件对最优解的影响

回答两个问题： 回答两个问题：

这些参数在什麽范围内发生变化时， ①这些参数在什麽范围内发生变化时，最优 基不变(即最优解或最优解结构不变) 基不变(即最优解或最优解结构不变)? 参数变化超出上述范围时， ②参数变化超出上述范围时，如何用最简便 的方法求出新的最优解？ 的方法求出新的最优解？ 二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 、在最优表格的基础上进行； 2、尽量减少附加计算工作量； 、尽量减少附加计算工作量；

灵敏度分析举例： 三、 灵敏度分析举例： 例：max Z = 2 x1 + 3x2 2 x1 + 2 x2 ≤ 12 4 x1 ≤ 16 s.t. 5 x2 ≤ 15 x1 , x2 ≥ 0 将该LP化为 引入非负的松弛变量X3, x4, x5. 将该 化为 标准型： 标准型：

max Z = 2x1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 2x1 + 2x 2 + x 3 = 12 4x1 + x 4 = 16 s.t. 5x 2 + x 5 = 15 x1 , x 2 , x 3 , x 4 , x 5 ≥ 0

用表格单纯形法求解最终单纯表如下： 用表格单纯形法求解最终单纯表如下：

C j→ CB XB 2 0 3 x1 x4 x2 σj b 3 4 3

2 x1 1 0 0 0

3 x2 1/2 -2 0 0

0 x3 0 0 1 -1 …… 此处隐藏：1774字，全部文档内容请下载后查看。喜欢就下载吧 ……