• / 29
  • 下载费用:20 金币  

3334线性规划的对偶和灵敏度分析

关 键 词:
线性规划的对偶 与灵敏度分析 的对偶与灵敏度分析 线性规划的对偶与灵敏度分析 和灵敏度分析 线性规划的灵敏度分析 线性规划对偶 灵敏度 分析
资源描述:
3.3 影子价格— 对对偶最优优解的经济经济 含义义 1、 对对偶最优优解的经济经济 解释释 “影子价格”确切的定义义是:一个线线性规规划对对 偶问题问题 的最优优解(简简称为为“对对偶最优优解”)。 在经济经济 上可以解释释为为约约束条件所付出的代价 。 看下面的线性规划 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1 x2 (8,0 ) k=6 (0,4) k=0 Q2(4,2) Z=2*4+3*2=14 当原问题问题 和对对偶问题问题 都取得最优优解时时,这这 一对线对线 性规规划对应对应 的目标标函数值值相等,即 有 Zmax=CX*=2x*1+3x*2 =Wmin=y*b=8y*1+16y*2+12y*3=14 其中X*是原问题问题 的最优优解,y*是对对偶问题问题 最优优解。 通过上面的例子可以看出:yi* 的值表示对第i种资 源的估价,它是针对具体问题而存在的一种资源 的特殊价格,称为“影子价格影子价格”。 cj23000 CBXBbx1x2x3x4x5 2x141001/40- 0x5400-21/21- 3x22011/2 -1/80- cj-zj00-3/2 -1/80 即有 X*=(x1,x2)=(4,2), Y*=(y1,y2,y3)=(3/2,1/8,0) 若原材料供应量能增加一个单位,即右端常 数向量b=(b1,b2,b3)T=(8,16,12)T中的b1从8个单位 增加到9个单位,则目标函数值的变化量为 (9y*1+16y*2+12y*3)-(8y*1+16y*2+12y*3)=y*1=3/2 说明目标函数值的增加一个单位,是因为放 宽一个约束条件所产生的附加贡献。 就是说,影子价格确定了为得到一个附加 单位的约束因素所应花费的成本上限。 所以,yi*的经济意义是在其他条件不变的情 况下,单位资源变化所引起的目标函数最优 值的变化。 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1 x2 (8,0) C=6 (0,4) C=0 Q2(4,2) Q2’(4, 2.5 ) Z=2*4+3*2=14 Z=2*4+3*2.5=15.5 Q2”(4.25, 1.875) Z=2*4.25+3*1.875=14.125 Q2’’’(1.5,3.25) Z=2*1.5+3*3.25=12.75 u影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格,对资源的使 用有两种考虑:第一,是否将设备用于外加工或出租 ,若租费高于某设备的影子价格,可考虑出租该设备 ,否则不宜出租。第二,是否将投资用于购买设备, 以扩大生产能力,若市价低于某设备的影子价格,可 考虑买进该设备,否则不宜买进。 u影子价格表明资源增加对总效益产生的影响 如果为了扩大生产能力,考虑增加设备,就应该 从影子价格高的设备入手。这样可以用较少的局部努 力,获得较大的整体效益。 3.4 对偶单纯形法 一、什么是对偶单纯形法? 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 纯形表格上进行对偶处理。 注意:不是解对偶问题的单纯形法! 二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提升— — 从更高的层次理解单纯形法 初始可行基(对应一个初始基可行解) →迭代→另一个可行基(对应另一个基 可行解),直至所有检验数≤0为止。 所有检验数≤0意味着什么? 以上分析过程说明原问题的最优基也是对偶问 题的可行基。换言之,当原问题的基B既是原 问题的可行基又是对偶问题的可行基时,B成 为原问题的最优基。 定理2-5 基B是线性规划的最优基的充要条件 是,B是可行基,同时也是对偶可行基。 单纯形法的求解过程就是:在保持原始可行 的前提下(b列保持≥0),通过逐步迭代实现 对偶可行(检验数行≤0)。 2、 对偶单纯形法思想: 换个角度考虑LP求解过程:保持对偶可行 的前提下(检验数行保持≤0) ,通过逐步迭 代实现原始可行(b列≥0)。 原始单纯形法对偶单纯形法 前提条件所有 ≥0所有 ≤0 最优性检验所有 ≤0?所有 ≥0? 换入、出基 变量的确定 先确定换入基变量 后确定换出基变量 先确定换出基变量 后确定换入基变量 原始基本解 的进化 可行→最优 (对偶问题的解从 不可行到可行) 非可行→可行(最优) (原问题的解从不可行 到可行) 对偶单纯形法 3、计算思路(对于MAX问题): ①建立初始单纯形表,计算检验数行。 b列≥0——已得最优解 至少一个元素0,转下步 检验数全部≤0 (非基变量检验 数0)  基变换: 先确定换出变量——解答列中的负元素对 应的基变量出基,即 相应的行为主元行。 然后确定换入变量——原则是:在保持对偶 可行的前提下,减少原始问题的不可行性。 如果 (最小比值原则),则选 为换入变量 , 相应 的列为主元列 , 主元行和主元列交叉处的元 素 为主元素。若 ,要计算最小 比值吗?为什么? 按主元素进行换基迭代(旋转运算、枢 运算),将主元素变成1,主元列变成单位向 量,得到新的单纯形表。 循环以上步骤,直至求出最优解。 例3.9 用对偶单纯形法求解LP: 化为标准型 → 将两个等式约束两边分别乘以-1,得 以此形式进行列表求解,满足对偶单纯形 法的基本条件,具体如下: Cj -2 -3 -5 -6 0 0 CB XBb x1x2x3 x4 x5 x6 0 x5 -2 -1 -2 -3 -1 1 0 0 x6 (-3) -2 1 -1 3 0 1 -2 -3 -5 -6 0 0 θ(1) 5 Cj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 (-1/2) 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 0 -4 -4 -9 0 -1 θ (8/5) 8/5 18/5 2 Cj -2 -3 -5 -6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 0 0 0 -5 -8/5 -1/5 因此,最优优解为为X*=(8/5,1/5,0,0,0,0)T, 最优值优值 ω*=21/5。 练习——用对偶单纯形法求解LP: 化为化为 标准型标准型 →→ 将三个等式约束两边分别乘以-1,然后 列表求解如下: -3/-1 -9/-1 --- --- - -- 比 值 -3 -9 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y4 y5 0 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB --- -6/-3 -3/-1 --- --- 比 值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB 最优解是最优解是Y*=Y*=((5/35/3,,1/31/3,,0 0,,0 0,,1 1)) T T ,, 目标函数最优值为目标函数最优值为WWmin min=-Z =-Zmax max=8 =8 (1)初始解可以是非可行解,当检验检验 数都 为负为负 数时时,就可以进进行基的变换变换 ,这时这时 不需 要加入人工变变量,因此可以简简化计计算。 (2)当变变量多于约约束条件时时,用对对偶单纯单纯 形法计计算可以减少计计算工作量。而对对于变变量 较较少,而约约束条件很多的线线性规规划问题问题 ,可 以首先将它变换变换 成为对为对 偶问题问题 ,然后用对对偶 单纯单纯 形法来求解。 从以上求解过过程中我们们可以看到 ,对对偶单纯单纯 形法有以下的优优点: 作业题作业题:: P97 6.(1),(3)
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:3334线性规划的对偶和灵敏度分析
链接地址:https://www.maidoc.com/p-15685963.html

当前资源信息

天马****3

编号: 20180820024746509952

类型: 共享资源

格式: PPT

大小: 930.50KB

上传时间: 2019-11-08

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开