运筹学第二章对偶理论灵敏度分析.ppt

《运筹学第二章对偶理论灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学第二章对偶理论灵敏度分析.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划进一步研究|对偶原理|对偶单纯形方法|灵敏度分析对偶原理对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。问题的导出ABC拥有量工 时1113材 料1479单件利润233问题的导出ABC拥有量工 时1113材 料1479单件利润233假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂

2、给工时和材料制订的最低价格应是多少，才值得出卖工时和材料?问题的导出ABC拥有量工 时1113材 料1479单件利润233出卖资源获利应不少于生产产品的获利;约束价格应该尽量低，这样，才能有竞争力;目标价格应该是非负的 问题的导出ABC拥有量工 时1113材 料1479单件利润233用y1和y2分别表示工时和材料的出售价格总利润最小 min W=3y1+9y2保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20问题的导出ABC拥有量工 时1113材 料1479单件利润233问题的导出ABC拥有量工 时1113材 料1479单件利

3、润233对偶问题的定义对称形式的对偶问题对偶问题的定义对称形式的对偶问题对偶问题的定义对偶问题的特点若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。对偶问题的定义 一般线性规划问题的对偶问题对偶问题的定义对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数maxZ目标函数minZ约束条件：m个第i个约束类型为“”第i个约束类型为“”第i个约束类型为“”变量数：m个第i个变量0第i个变量0第i个变量是自由变量 变量数：n个第j个变量0第j个变

4、量0第j个变量是自由变量约束条件右端项约束条件：n个第j个约束类型为“”第j个约束类型为“”第j个约束类型为“”约束条件右端项对偶问题的写出|例1标准型对偶问题 对偶问题的写出|例2例例 max=2x1+x2+3x3+x4 s.t.x1+x2+x3+x45 2x1-x2+3x3 =-4 x1 -x3+x4 1 x10,x2,x4无约束无约束,x3 0 min=5y1+4y2+y3 s.t.y1-2y2+y3 2 y1+y2 =1 y1-3y2-y3 3 y1 +y3=1 y10，y2无约束，无约束，y3 0其对偶问题为其对偶问题为对偶问题的写出练练习习写出对偶问题max=x1-x2+5x3-7

5、x4 s.t.x1+3x2-2x3+x4=25 -2x1-7x2 -2x4 60 2x1+2x2-4x3 30 x4 10 -x4 5 x1,x2 0,x3,x4无约束无约束练练习习max=x1-x2+5x3-7x4 s.t.x1+3x2-2x3+x4=25 -2x1-7x2 -2x4 60 2x1+2x2-4x3 30 x4 10 -x4 5 x1,x2 0,x3,x4无约束无约束对偶问题的基本性质对称性对称性：对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。互为对偶问题互为对偶问题(P)(D)弱对偶定理定理1.弱对偶定理若互为对偶的线性规划分别有可行解 则其相应的目标函数值满足 推

6、论 推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。最优性准则定理定理2 最优性准则定理若X和Y分别是互为对偶的线性规划的可行解，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解 证明：由弱对偶定理可知，对任意可行解有，CXYb因此对于X和Y也将分别有 CXYb CXYb 又因为 CX=Yb 故有 Yb Yb CXCX 主对偶定理定理3 （主对偶定理）若原始问题和对偶问题两者均可行，则两

7、者均有最优解，且此时目标函数值相同。证明：由两者均有可行解，则根据弱对偶定理可知两者均有界，因此均有最优解。设B是其最优基，X是其对应的基本可行解令A=(B N)，则：对应于基B的检验数满足 主对偶定理定理3 （主对偶定理）设B是其最优基，X是其对应的基本可行解令A=(B N)，则：对应于基B的检验数满足 对偶问题的一个可行解,其目标值：互补松驰性互补松驰性(松紧定理松紧定理)：若若X，分别是分别是(P),(D)问题的可行问题的可行解，那么解，那么X,为最优解的充要条为最优解的充要条件是：件是：XS=0,YSX=0 (即若 AiX i=0 AiX=bi 0 Pj=Cj 0 PjCj=Xj=0)

8、互互补补松松驰驰性性(松松紧紧定定理理)XS=0,YSX=0原问题第i个约束方程是等式约束若原问题第i个约束方程是不等式约束例1.求解下列线性规划问题 max=x1+2x2+3x3+4x4 s.t.x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0,j=1,2,3,4 解其对偶问题为 min=20y1+20y2 s.t.y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1,y20(1.2,0.2).y11212y2互互补补松松驰驰性性(松松紧紧定定理理)用图解法得最优解 y1=1.2,y2=0.2 根据松紧定理，原问题的最优解必满足 XS=0 及YS

9、X=0及 (y3,y4,y5,y6)=0 x1x2x3x4 x5 (y1,y2)x6 =0 因y10,y20。所以x5=x6=0，即原问题为等式约束互互补补松松驰驰性性(松松紧紧定定理理)将y1=1.2,y2=0.2代入对偶问题的约束条件，得 y30,y40,所以x1=x2=0min=20y1+20y2 s.t.y1+2y2-y3=1 2y1+y2-y4=2 2y1+3y2-y5=3 3y1+2y2-y6=4 y1,y20 (y3,y4,y5,y6)=0 x1x2x3x4互互补补松松驰驰性性(松松紧紧定定理理)x1=x2=0 x1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=2

10、0即 x1=x2=0，x3=4,x4=4 原问题的最优解为(0,0,4,4)Tmax=x1+2x2+3x3+4x4 s.t.x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0,j=1,2,3,4互互补补松松驰驰性性(松松紧紧定定理理)7.原问题单纯形表的检验数行对应其对偶问题的一个基解.其对应关系见表：XB XN XS 0 CN-CBB-1N -CBB-1 YS1 YS2 -Y对偶问题的基解YS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。对偶问题的基解 XB XN XS 0 CN-CBB-1N -CBB-1 YS1 YS2 -Y 例

11、.max=x1+4x2+3x3 s.t.2x1+2x2+x34 x1+2x2+2x36 xj0对偶问题为 min=4y1+6y2 s.t.2y1+y21 2y1+2y24 y1+2y23 y1,y20 对偶问题的基解初始单纯形表为 4 2 2 1 1 0 6 1 2 2 0 1 0 1 4 3 0 0 对偶问题的基本解为对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3对偶问题的基解1 3/2 1 0 1 -1/22 1 0 1 1 1-10 2 0 0 1 -1 由原问题的最终表可知，y1=1,y2=1(最优解)，ys1=2其最终表为对偶问题的基解 影子价格影子价

12、格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cT x*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产 生的影响.称 yi*为 bi的影子价格。当B是原问题的最优基时，Y=CBB-1就是 影子价格向量。影子价格 影子价格的经济含义影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜

13、出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。影子价格 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。影子价格影子价格举例ABC拥有量工 时1113材 料1479单件利润233 y1=5/3,y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反

14、之则反从原始问题最优表求影子价格当B是原问题的最优基时，=CBB-1就是影子价格向量。由检验数的计算方法可知：=C-A若A中有单位子矩阵，则在最优表中有：CB XB cj23300 xj b x1x2x3x4X50 x43111 103/10 x59147019/12x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3初始表最优表 例 某工厂以一种贵重金属为原料生产两种产品，两种产品都必须经过粗加工和精加工两道工序，每个粗加工工时的成本计为1.5元，精加工工时为2.5元，每克贵金属成本为10元。以其最大加工能力的工时计入成本，而贵金属按实际使用量计入成本。AB

15、 资源约束粗加工（小时）17140，000精加工（小时）24100，000贵金属（克）32120公斤利润60 70 如设A、B产品分别生产x1和x2千件，则利润可按下式计算（单位：万元）S=6x1+7x2-（3x1+2x2）+（141.5+102.5)=3x1+5x2-46 使得毛利最大的生产计划即为如下线性规划的最优解：max S1=3x1+5x2 （S1=S-46）s.t.x1+7x2 140 (粗加工能力约束）2x1+4x2 100（精加工能力约束）3x1+2x2 120（贵金属用量约束）x1，x2 0用单纯形法求解可得如下最优表：XB b x1 x2 x3 x4 x5 x2 7.5 0

16、 1 0 0.375 -0.25 x1 35 1 0 0 -0.25 0.5 x3 52.5 0 0 1 -2.335 1.25 142.5 0 0 0 -1.125 -0.25由松驰变量的检验数可知：粗加工能力的影子价格为0；精加工能力的影子价格为1.125，单位是万元/千小时；贵金属的影子价格为0.25万元/公斤。例 Max z=50 x1+100 x2 s.t.x1+x2+x3 =300 2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0影子价格举例c cB B(B B)-1-1I IB B=(p p1 1,p p4 4,p,p2 2)B B-1-1最优解

17、x1=50 x2=250 x4 =50(松弛标量，表示原料A有50个单位的剩余）影子价格影子价格 y y1 1=50 =50 y y2 2=0 =0 y y3 3 =50,=50,B B-1-1对应的检验数对应的检验数 c cB B(B B)-1-1 。对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。对于标准线性规划问题：可行基B 若B对应的基本解是可行解最优基B 若B对应的基本解是最优解对偶可行基B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 对偶单纯形法对于标准线性规划问题：最优基B可行基B 对偶可行基B单纯形法可行基B 保

18、持可行性 对偶可行基B对偶单纯形法可行基B 保持对偶可行性 对偶可行基B XB XN XS 0 CN-CBB-1N -CBB-1 YS1 YS2 -Y对偶单纯形法对于标准线性规划问题：对偶单纯形法可行基B 保持对偶可行性 对偶可行基B 找一个基，建立初始对偶单纯形表，检验数全部非正；若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非正的。主元变换对偶单纯形法举例例 用对偶单纯形法求解：CB XB cj-3-9000 yj b y1y2y3y4y50Y3-2-1-11000Y4

19、-3-1-40100Y5-3-1-70010-3-9000对偶单纯形法举例 CB XB cj-3-9000 xj b y1y2y3y4y50Y3-2-1-11000Y4-3-1-40100Y5-3-1-70010-3-9000-3Y1211-1000Y4-10-3-1100Y5-10-6-10160-6-300最小比值0-6/-3-3/-100最小比值-3/-1-9/-1000对偶单纯形法举例 CB XB cj-3-9000 xj b y1y2y3y4y5-3Y1211-1000Y4-10-3-1100Y5-10-6-10160-6-300-3Y15/310-4/31/30-9Y21/3011

20、/3-1/300Y51001-21800-1-20最小比值-6/-3-3/-100 对偶单纯形法的基本思想 从原规划的一个基基本本解解出发，此基本解不一定可行，但它对应着一个对对偶偶可可行行解解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。对偶单纯形法 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行。当同时得到对偶规划与原规划的可行解时

21、，便得到原规划的最优解。对偶单纯形法 对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。对偶单纯形法例.min=3x1+4x2+5x3 s.t.x1+2x2+3x35 2x1+2x2+x36 x1,x2,x30解 问题化为 min=3x1+4x2+5x3 s.t.-x1-2x2-3x3+x4 =-5 -2x1-2x2-x3 +x5=-6 x1,x2,x3,x4,x50对偶单纯形法练习 XB b x1 x2 x3 x4 x5 x4 5 1 2 3 1 0 x5 6 2 2 1 0 1 3 4 5 0 0 x4

22、2 0 1 5/2 1 1/2 x1 3 1 1 1/2 0 1/2 0 1 -7/2 0 3/2 x2 2 0 1 5/2 -1 1/2 x1 1 1 0 2 1 1 0 0 1 1 1 所以最优解为x1=1,x2=2,x3=0，min=11对偶单纯形法练习灵敏度分析 在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是

23、目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓来不及随时对其变化作出反应，即所谓“计划不如变化快计划不如变化快”，企业应当预先了解，企业应当预先了解，当各项因素变化时，应当作出什么样的反当各项因素变化时，应当作出什么样的反应应。灵敏度分析灵敏度分析 当当系系数数A，b，C发发生生改改变变时时，目目前前最最优优基基是是否否还还最最优优？目目前前的的最最优优解解是是否否还还最最优？优？为为保保持持目目前前最最优优基基或或最最优优解解还还是

24、是最最优优，系数系数A，b，C的允许变化范围是什么？的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化 基变量系数发生变化；非基变量系数发生变化；右端常数b变化增加一个变量增加一个约束技术系数A发生变化灵敏度分析 CB XB cjCBCN xj b XBTXNTCBTXBB-1b B-1BB-1N-CB B-1b CB-CB B-1BCN-CB B-1N若B是最优基，则最优表形式如下灵敏度分析总是在最优表上进行灵敏度分析总是在最优表上进行 灵敏度分析例 线性规划 CB XB cj23300 xj b x1x2x3x4X50 x43111 100 x59147012x1110-1 4/

25、3-1/33x22012-1/31/3-800-1-5/3-1/3灵灵敏敏度度分分析析例 线性规划 CB XB cj23300 xj b x1x2x3x4X50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3灵敏度分析例27 线性规划 CB XB cj23300 xj b x1x2x3x4X50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/33-2*（-1）-3*2=-1B-1b解的可行性解的可行性CN CBaij检验数检验数原问题原问

26、题 对偶问题对偶问题 结论或继续计算的步骤结论或继续计算的步骤可行解可行解 可行解可行解 表中的解仍为最优解表中的解仍为最优解可行解可行解 可行解可行解 用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解非可行解非可行解 可行解可行解 用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解非可行解非可行解 非可行解非可行解 引入人工变量，编制新的单纯形引入人工变量，编制新的单纯形 表求最优解表求最优解为保持目前为保持目前最优基还是最优最优基还是最优，系数，系数aij,bi,cj的的允允许变化范围是什么？许变化范围是什么？当当aij,bi,cj中的一个或几个发生变化时中的一个或几个发生变

27、化时，已求得的线已求得的线性规划问题的最优解会有什么变化？如何求解新的性规划问题的最优解会有什么变化？如何求解新的最优解？最优解？价价值值系系数数C的的改改变变 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3价值系数价值系数CN（非基变量的价值系数）发生非基变量的价值系数）发生改变改变C3C3-4如果C34,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C34。价价值值系系数数C的的改改变变 CB XB

28、cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/31-8001-5/3-1/3价值系数CN发生改变 2x1211/20 7/6-1/65x3101/21-1/61/6-90-0.50-3/2-1/25价价值值系系数数C的的改改变变 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3价值系数价值系数CB（基变量的价值系数基变量的价值系数)发生发生改变改变 C1-3

29、C1C11-4/3C11/3C1-1C1-3 0,1-4/3C10,1/3C1-10 C13若C13/4 则x4进基，x1出基若30br-bi/air 若air0brminbi/air air0例.线性规划问题 max=-x2+3x2-2x5 s.t.x1+3x2-x3 +2x5 =7 -2x2+4x3+x4 =12 -4x2+3x3 +8x5+x6=10 xj0XB b x1 x2 x3 x4 x5 x6 x1 7 1 3 1 0 2 0 x4 12 0 2 4 1 0 0 x6 10 0 4 3 0 8 1 -1 0 3 0 2 0资源数量b变化的分析最终表是XB b x1 x2 x3 x

30、4 x5 x6 x2 4 5/2 1 0 1/10 4/5 0 x3 5 1/5 0 1 3/10 2/5 0 x6 11 1 0 0 1/2 10 1 -1/5 0 0 4/5 12/5 0B=P2,P3,P6 5/2 1/10 0 B-1=1/5 3/10 0 1 -1/2 1 求b2的变动范围 1/10 B-12列=3/10 -1/2 max-4/(1/10),-5/(3/10)b2min-11/(-1/2)-50/3b222要保持最优基不变，则 -14/3b234 若b2超出此范围，则b0 可用对偶单纯形法继续求解 例上题中，若令b2增加b2=30,则 5/2 1/10 0 0 3B-

31、1b=1/5 3/10 0 30 =9 1 1/2 1 0 -15将上式结果反映到最终表中，得下表XB b x1 x2 x3 x4 x5 x6 x2 4+3 5/2 1 0 1/10 4/5 0 x3 5+9 1/5 0 1 3/10 2/5 0 x6 11-15 1 0 0 -1/2 10 1 -1/5 0 0 4/5 12/5 0 x4 8 2 0 0 1 20 -2XB b x1 x2 x3 x4 x5 x6x2 31/5 *1 0 0 *x3 33/5 *0 1 0 *-9/5 0 0 0 92/5 8/5资源数量b变化的分析右端常数b2改变范围 CB XB cj23300 xj b

32、x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3b24-b2/3b2/3-13b2 12-b2/3-5练习 灵敏度分析增加一个变量增加一个变量 若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。增增加加一一个

33、个变变量量 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33/53x22012-1/31/36-800-1-5/3-1/35x623x65/31/32/35x63/53/50-3/5 4/5-1/513x29/5-1/5111/5-3/52/50-42/5-2/50-3/5-11/5-1/50 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3 例例.某工厂计划生产某工厂计

34、划生产A,B,C三种产品，需要甲三种产品，需要甲,乙两种乙两种资源。资源限量、每种产品的单位利润和单位产品的资源资源。资源限量、每种产品的单位利润和单位产品的资源消耗量如下表所示，试确定使利润最大的生产计划。消耗量如下表所示，试确定使利润最大的生产计划。练习：产 品 资源 A B C 资源限量(吨)甲 1/3 1/3 1/3 1 乙 1/3 4/3 7/3 3单位产品的利润(元)2 3 1 解以x1,x2,x3分别表示A,B,C三种产品的产量，则该问题的线性规划模型如下：max=2x1+3x2+x3s.t.1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,

35、x30引入松驰变量，可得初始单纯形表最终单纯形表为1 1/3 1/3 1/3 1 03 1/3 1/3 1/3 0 1 2 3 1 0 0 1 1 0 1 4 1 2 0 1 2 1 1 -8 0 0 3 5 1假设这个工厂研制了一种新产品假设这个工厂研制了一种新产品D，单位新产品单位新产品D所需耗用的甲乙两种资源分别为所需耗用的甲乙两种资源分别为1/2和和1/2，新产品，新产品的利润为的利润为4元，问应怎样调整生产计划？元，问应怎样调整生产计划？max=2x1+3x2+x3s.t.1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,x301 1/3 1/3

36、 1/3 1 03 1/3 1/3 1/3 0 1 2 3 1 0 0 1 1 0 1 4 1 2 0 1 2 1 1 -8 0 0 3 5 1P6=B-1P6=4 1-1 11/21/2=3/2 0b x1 x2 x3 x4 x5 x61 1 0 1 4 1 3/22 0 1 2 1 1 0-8 0 0 3 5 1 12/3 2/3 0 2/3 8/3 2/3 12 0 1 2 1 1 026/3 2/3 0 7/3 23/3 1/3 0灵敏度分析增加一个约束增加一个约束在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，若把目前的最优解代

37、入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。灵敏度分析例 增加约束 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147010 x65221002x1110-1 4/3-1/33x22012-1/31/30 x6522100-800-1-5/3-1/30 x60010010 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012

38、x1110-1 4/3-1/33x22012-1/31/3将新的约束条件引入松驰变量后，写入最终单纯形表，并把XB,XS 的系数列向量化为单位向量，再求解。灵敏度分析增加约束 CB XB cj233000 xj b x1x2x3x4x5x62x1110-1 4/3-1/303x22012-1/31/300 x652210012x1110-1 4/3-1/303x22012-1/31/300 x6-100-1-201-800-1-5/3-1/30最小比值15/6灵敏度分析A中元素改变中元素改变如果N中数据改变，可以用增加一个变量来处理如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解讨论

39、题在极大化问题的下列表中，六个常数,1,2,3,1,2,之值未知（假定无人工变量），分别写出对六个未知数的约束条件，使以下各小题关于该表的说法为真。现行解最优，但不唯一；现行解不可行（指出哪个变量造成）；一个约束条件有矛盾；现行解是退化的基本可行解；现行解可行，但问题无有限最优解；现行解是唯一最优解；现行解可行，但将x1取代x6后，目标函数能改进。讨论题 现行解最优，但不唯一；现行解不可行（指出哪个变量造成）；一个约束条件有矛盾；现行解是退化的基本可行解；现行解可行，但问题无有限最优解；现行解是唯一最优解；现行解可行，但将x1取代x6后，目标函数能改进。CB XB cj xj b x1x2x3x4x5x6x3411 020 x42-1-501-10 x633-300-411200-30讨论题已知线性规划问题最终单纯形表bx1x2x3 x4 x23/2015/14-3/14 x1110-1/72/700-5/14-25/14讨论题试用灵敏度分析的方法判断1.目标函数 或 分别在什么范围内变化，上述最优解不变；2.约束条件右端项 ，当一个不变时，另一个在什么范围内变化上述最优基不变；3.问题的目标函数变为上述最优解的变化；4.约束条件右端项 变为 时上述最优解的变化