线性规划灵敏度分析

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

1、Chapter2线性规划灵敏度分析上海工程技术大学——管理学院Chapter2灵敏度分析本章提要Content单纯形法的矩阵描述改进单纯形法对偶问题提出线性规划对偶理论对偶问题的基本性质影子价格对偶单纯形法灵敏度分析案例分析及Matlab求解习题Chapter2灵敏度分析单纯形法的矩阵描述？单纯形法矩阵的描述标准型maxZ=CXAX=bX0已知：A、b、cA=(NB)B=EChapter2灵敏度分析用非基变量表示基变量Z=CBB-1b+(CN-CBB-1N)XNXB=B-1b-B-1NXNCBB-1bCN-CBB-1NOB-1bB-1NECBB-1bC-CBB-1AB-1bB-1ACha

2、pter2灵敏度分析C-CBB-1A=(CNCB)-CBB-1(NB)=(CN-CBB-1N,CB-CBB-1B)B-1A=B-1(NB)=(B-1N,B-1B)单个检验数：λj=Cj-CBB-1Pj某列Pj=B-1PjChapter2灵敏度分析改进单纯形法对maxZ=CXAXbX0A=(P1P2…Pn)(1)、已有初始可行基B，求B-1，XB=B-1b(2)、计算λj=Cj-CBB-1Pj若全部λj0，则计算Z0=CBB-1b,停；否则，取λm+k=maxλj，Xm+k换入。λj>0Chapter2灵敏度分析(3)、计算Pm+k=B-1Pm+k，若Pm+k0，则无有限最优解,停；

3、否则θ=minbiAim+karm+k>0=brarm+kXr换出(4)、最小θ比值法：(5)、新基B。转(1)。Chapter2灵敏度分析对偶问题提出问题一：某公司在计划期内要安排生产III两种产品已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？如何安排方案？举例有哪些方面可以考虑呢？Chapter2灵敏度分析先根据图表来列出模型MaxZ=2X1+3X2X1+2X2≤84X1≤164X2≤12X1,X2≥0我们从另一个角度来讨论这个问题.假如该工厂的决策者决定不生产产品III

4、，而将其所有资源出租或外售.这时工厂的决策者就要考虑给每种资源如何定价的问题.设用,,分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.他在做定价决策时,作如下比较:若用一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有Y1+4Y2≥2举例Chapter2灵敏度分析同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有2Y1+4Y3≥3把工厂所有设备台时和资源都出租和出让,其收入为f=8Y1+16Y2+12Y3从工厂决策者的角

5、度来看W当然是越大越好,但从接受者眼光来说W是越少越好,所以工厂决策者只可以在满足≥所有产品的利润条件下,使其总收入尽可能的小.因此可以列出如下线性规划问题f=8Y1+16Y2+12Y3Y1+4Y2≥22Y1+4Y3≥3Yi≥0,i=1,2,3Chapter2灵敏度分析各模型中有关数据的“位置”示意图如下。Chapter2灵敏度分析问题二:考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？Chapter2灵敏度分析Yi表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：如果资源拥有者将所有

6、资源出售，则他得到的总收入Chapter2灵敏度分析资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。线性规划的对偶理论对偶定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”Chapter2灵敏度分析Chapter2灵敏度分析Chapter2灵敏度分析如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对

7、偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。Chapter2灵敏度分析然而在一般线性规划问题中遇到非对称形式时我们的处理如下：非对称形式的对偶规划——