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

《线性规划的对偶和灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.3影子价格—对偶最优解的经济含义1、对偶最优解的经济解释“影子价格”确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。在经济上可以解释为约束条件所付出的代价。看下面的线性规划0123456789x154321x2（8，0）k=6（0，4）k=0Q2（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*是对偶问题最优解。通过上

2、面的例子可以看出：yi*的值表示对第i种资源的估价，它是针对具体问题而存在的一种资源的特殊价格，称为“影子价格”。cj23000CBXBbx1x2x3x4x52x141001/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*

3、2+12y*3)-(8y*1+16y*2+12y*3)=y*1=3/2说明目标函数值的增加一个单位，是因为放宽一个约束条件所产生的附加贡献。就是说，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。所以，yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数最优值的变化。0123456789x154321x2（8，0）C=6（0，4）C=0Q2（4，2）Q2’（4,2.5）Z=2*4+3*2=14Z=2*4+3*2.5=15.5Q2”（4.25,1.875）Z=2*4.25+3*1.875=1

4、4.125Q2’’’(1.5，3.25)Z=2*1.5+3*3.25=12.75影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。影子价格表明资源增加对总效益产生的影响如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效

5、益。3.4对偶单纯形法一、什么是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！二、对偶单纯形法的基本思想1、对“单纯形法”求解过程认识的提升——从更高的层次理解单纯形法初始可行基（对应一个初始基可行解）→迭代→另一个可行基（对应另一个基可行解），直至所有检验数≤0为止。所有检验数≤0意味着什么？以上分析过程说明原问题的最优基也是对偶问题的可行基。换言之，当原问题的基B既是原问题的可行基又是对偶问题的可行基时，B成为原问题的最优基

6、。定理2-5基B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。单纯形法的求解过程就是：在保持原始可行的前提下(b列保持≥0)，通过逐步迭代实现对偶可行(检验数行≤0)。2、对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0），通过逐步迭代实现原始可行（b列≥0）。原始单纯形法对偶单纯形法前提条件所有≥0所有≤0最优性检验所有≤0？所有≥0？换入、出基变量的确定先确定换入基变量后确定换出基变量先确定换出基变量后确定换入基变量原始基本解的进化可行→最优（对偶问题的解从不可行到

7、可行）非可行→可行（最优）（原问题的解从不可行到可行）对偶单纯形法3、计算思路（对于MAX问题）：①建立初始单纯形表，计算检验数行。b列≥0——已得最优解至少一个元素<0,转下步检验数全部≤0（非基变量检验数<0）基变换：先确定换出变量——解答列中的负元素对应的基变量出基，即相应的行为主元行。然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果(最小比值原则),则选为换入变量,相应的列为主元列,主元行和主元列交叉处的元素为主元素。若,要计算最小比值吗？为什么？按主元素进行换基迭代（旋转运算

8、、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。循环以上步骤，直至求出最优解。例3.9用对偶单纯形法求解LP：化为标准型→将两个等式约束两边分别乘以-1，得以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：Cj-2-3-5-600CBXBbx1x2x3x4x5x60x5-2-1-2-3-1