《数学模型1-3线性规划相关问题》由会员分享，可在线阅读，更多相关《数学模型1-3线性规划相关问题（35页珍藏版）》请在金锄头文库上搜索。
1、1线性规划相关问题 灵敏度分析 对偶问题2标准型maxZ=CTX AX=b，X01. 参数A，b，C在什么范围内变动，对当前 方案无影响？ 2. 参数A，b，C中的一个(几个)变动，对当前 方案影响？ 3. 如果最优方案改变，如何用简便方法求新 方案？灵敏度分析3两个重要公式XB =B-1 b-B-1 NXNZ=CBTB-1 b+(CNT-CTB B-1 N)XN当XN =0时，B-1 b0X=Z= CBTB-1 b4几个条件 检验数j 0 ( j=m+1,n). 即 (CNT-CTB B-1 N) 0. 若非基本变量系数m+k0 , 相应的基本变量 表示系数向量Pm+k的所有分量不能全小于零
2、。 否则无有限最优解存在。即当 (B-1N)k0 , 最优解发生变化CB XB 84 0 0 (2) -2 -35 X1 4 1 0 0 2 -18 X2 8 0 1 (1) -1 1 XB 100 0 -2 0 0 -55 X1 4 1 0 0 2 -110 X3 8 0 1 1 -1 1 10(2)、基变量系数CjCj 改变，全部j0，最优方案不变。例中C1改变A = C- CTB B-1 A=(C1 ,8,6,0,0)-(C18) 1 0 0 2 -10 1 1 -1 1=(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 811C1改变 C1=10，5
3、 =20 ,换基XB 104 0 0 -2 -12 210 X1 4 1 0 0 2 -18 X2 8 0 1 1 -1 (1)120 0 -2 -4 -10 010 X1 12 1 1 1 1 00 X5 8 0 1 1 -1 1 12(二)、约束条件右端项 bj 的灵敏度分析(1)、bj 改变，B-1 b仍0时，最优方案不变。例中b1改变2 -1-1 1b12010 b1 20 B-1 b=02b1 -200-b1+20013(2)、 b1改变, b1=30 ，CB XB 120 0 0 -2 -2 -35 X1 40 1 0 0 2 -18 X2 -10 0 1 1 (-1) 1 100
4、 0 -2 -4 0 -55 X1 20 1 2 2 0 10 X4 10 0 -1 -1 1 -1 2 -1-1 13020B-1 b=40 -1014(三)、添加新变量的灵敏度分析例 对于新产品D，已知1个单位D要消耗 甲：3 乙：2 可以得利润10问：投产产品D是否有利？6 = C6- CBB-1 P6 = 10 - (5 8) 2 -1 3-1 1 2= 10 - 12 = -2 0 得C6 12（2） C6 =15 时6 =3 P6 = B-1 P6 = 2 -1 3 = 4-1 1 2 -116X1 X2 X3 X4 X5 X6XB 84 0 0 -2 -2 -3 3X1 4 1
5、0 0 2 -1 (4)X2 8 0 1 1 -1 1 -187 -3/4 0 -2 -7/2 -9/4 0 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 17(四)、添加新约束的灵敏度分析例 新增加电力约束：13 A、B、C每单位需电2、1、3问：原方案是否改变？2X1 +X2 +3X3 13原方案A：4 B：8 C：0 16 13 原方案要改变2X1 +X2 +3X3 +X6 =1318XB 84 0 0 -2 -2 -3 0 X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 XB
6、84 0 0 -2 -2 -3 0 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6-3 0 0 2 (-3) 1 1 820 0 -10/3 0 -11/3 -2/3 5 X1 2 1 0 4/3 0 -1/3 2/3 8 X2 9 0 1 1/3 0 2/3 -1/3 0 X4 1 0 0 -2/3 1 -1/3 -1/3 19(五)、aij改变(计划生产的产品工艺结构改变)1. 非基变量Xj工艺改变 只影响单纯形表Pj 列，j . 关键看j 0? 还是0? 用(三)类似方法 解决。2. 基变量Xj工艺改变，复杂20对偶理论例1 2 加工能力(小时/
7、天)A 2 2 12B 1 2 8C 4 0 16D 0 4 122 3销售收入产品 设备21设X1 ，X2 为产品1，2的产量2X1 +2X2 12X1 +2X2 84X1 164X2 12X1X20maxZ= 2X1 +3X2 2 2 12 1 2 X184 0 X2 160 4 12(2 3) X1X222不进行生长而直接出售设备和劳动力，以获 得更好的竞争力。设 y1 ,y2 ,y3 ,y4分别为A, B, C, D设备的单价，称之为“影子价格”。2y1 +y2 +4y3 22y1 +2y2 +4y4 3y1 y402 1 4 02 2 0 4y1 y2 y3 y4 23Min W=1
8、2 y1 + 8 y2 + 16 y3 + 12 y4=bTY23定义：minW=bTYATYCY0A 矩阵Y, b,C 列向量maxZ=CTXAXbX0A 矩阵X, b,C 列向量原问题对偶问题24对偶关系对应表原问题对偶问题目标函数类型max min目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n 约束数 n的对应关系约束数m 变量数m原问题变量类型与0 对偶问题约束类型变量0 约束的对应关系无限制原问题约束类型与0 对偶问题变量类型约束变量0 的对应关系无限制25对偶问题性质 定理1：(对偶定理)互为对偶的两个LP问题，若其 中一个有有穷最
9、优解，则另一个也有有穷最优解， 且最优解值相等。如果两者之一有无界的最优解， 则另一个没有可行解。 定理2：(互补定理)对于互为对偶的两个LP问题的 最优解，如果一个问题的任一约束不等式严格成 立(即松弛变量为正)，则相应的对偶变量为零， 而与任一解的正分量相对应的对偶问题约束必为 等式(即松弛变量为零)。26定理1证明设原问题为maxZ=CTXAXbX0引入松弛变量 XS=b-AX, 化为标准型，27设以上LP问题最优解对应的基本变量为 XB，其余为XN，不妨设基本变量为前m 个变量 (否则可适当交换变量的位置将其 调为前m个)，设(A, I)= (B, N)， 相应地， (CT,0)= (CBT, CNT)28LP问题有最优解，则满足且目标函数的最大值为 CBTB-1b现在来看对偶问题余下的任务就是要构造对偶问题的一个可行解 Y0，使之取到原问题的最大值CBTB-1b29令Y0(BT)-1CB30下面说明其满足对偶问题的约束 ATY0 C31定理2证明对于原问题和对偶问题，
