运筹课件 OR2

1、2011/03-第2章 对偶问题-1-第 二 章 线性规划的对偶理论Duality 对偶Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划Dual Theory 对偶理论2011/03-第2章 对偶问题-2-2.1 问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需经 A、B、C、D 四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大? 2011/03-第2章 对偶问题-3-1.最大生产利润模型设 企业生产甲产品为X1件， 乙产品为X2件，则 m

2、ax z= 2 X1 +3 X2 s.t 2 X1 +2 X2 12 X1 +2 X2 8 4 X1 16 4 X2 12 X1 0 , X2 02.资源最低售价模型(原问题) ( 对偶问题)设第i种资源价格为yi,（ i=1, 2, 3, 4,） 则有min w= 12y1 + 8y2 + 16y3 +12 y4s.t 2y1 + y2 + 4y3 +0 y4 2 2y1 +2y2 + 0y3 +4 y4 3yi 0, (i=1, 2, 3, 4 )y1y2y3y42011/03-第2章 对偶问题-4-2.2 原问题与对偶问题的关系一般表示式：原问题： max z = c1 X1 + c2

3、X2 + + cn Xn s.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b2 am1 X1 + am2 X2 + + amn Xn bm xj 0，j=1,2,n 对偶问题： min w = b1 y1 + b2 y2 + + bm ym s.t a11 y1 + a21 y2 + + am1 ym c1 a12 y1 + a22 y2 + + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn yi 0，(i=1,2,m )2011/03-第2章 对偶问题-5-典式模型对应对偶结构矩阵表示

4、（1） max z = C X s.t AX b X 0min w = Y b s.t YA C Y 0 对偶问题原问题2011/03-第2章 对偶问题-6-对偶模型其他结构关系（2）若模型为 max z = C X s.t AX b X 0max z = C X s.t - AX -b X 0变形min w = Y b s.t YA C Y 0 Min w=Y (-b) st. Y (-A) CY 0令 Y=- Y 对偶问题对偶变量Y2011/03-第2章 对偶问题-7-（3）max z = C X s.t AX b X 0变形设X= -Xmax = -CX st. -AX b X 0min

5、 w = Y b s.t YA C Y 0则有min w = Y b s.t -YA - CY 02011/03-第2章 对偶问题-8-对偶问题典式：用矩阵形式表示： （1） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （2） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （3）max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 02011/03-第2章 对偶问题-9-原问题与对偶问题关系表 原问题(对偶问题) 对偶问题(原问题) 目标函数系

6、数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数max min 变量 x j : 约束方程 i : x j 0 x j 无约束 = x j 0 约束方程: 变量 y i : y i 0 = y i 无约束 y i 0 2011/03-第2章 对偶问题-10-2.3 对偶问题的基本性质 Max z = CXMin w = Y b s t . AX b s t . YA C X 0Y 0(1) 弱对偶性： 若 X0原问题可行解，Y0对偶问题可行解则 CX0 Y0 b证明： Y0 0， AX0 b， Y0 AX0 Y0 b，而 Y0 A

7、C ， CX0 Y0AX0 ， CX0 Y0 AX0 Y0 b 2011/03-第2章 对偶问题-11-（2）最优性： 若 X0原问题可行解，Y0对偶问题可行解，且 CX0 = Y0 b 则 X0原问题最优解， Y0对偶问题最优解证明：设 X* 原问题最优解， Y* 对偶问题最优解 则 CX0 CX* Y* b Y0 b 但 CX0 = Y0 b， CX0 = CX* = Y* b = Y0 b X0 = X* ， Y0 = Y* 即 X0原问题最优解， Y0对偶问题最优解证毕。 2011/03-第2章 对偶问题-12-（3）无界性若原问题最优解无界，则对偶问题无可行解 证：有性质1，C X0

8、 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b 。 注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。2011/03-第2章 对偶问题-13-（4）强对偶性（对偶定理） 若原问题有最优解，则对偶问题一定有最优解，且有 z max = w min证： 由 = C- CB B-1 A 0 令 CBB-1 = Y * ，得 Y * A C-Y * = -CBB-1 0， Y * 0 因此， Y *是对偶问题的可行解，又 CX * = CB (B-1 b) = CB B-1b = Y * b Y *是对偶问题的最优解。2011/0

9、3-第2章 对偶问题-14-Max z=CX st. AX b X 0Max z=CX st. AX +Xs = b X 0标准形Max z=CBXB+CNXN+0XS st.BXB+NXN+IXS=b ，XB,XN,XS 0改写B-1存在Max z=CBXB+CNXN+0XS st. B-1BXB+ B-1NXN+ B-1I XS= B-1 bXB,XN,XS 0左乘B-1LP模型矩阵变换：|B|0，（XB+ B-1NXN+ B-1 XS= B-1 b）2011/03-第2章 对偶问题-15-单纯形法的矩阵描述：XBXNXSBNIINB-1bbXS XBCBCN0CBCN0= C- CB B

10、-1 A00NSxjcjpj0pjjcjXB= b = B-1 bN = B-1 N N = CN -CBB-1 N 0CBS = -CB B-1 0初始表最终表2011/03-第2章 对偶问题-16-（5）互补松弛性 n 若 y i * 0, 则 aij xj* = bi j=1 n 若 a ij xj* 0, a ij xj* - bi =0, 即 a ij xj* = bi 当 a ij xj* - bi 0, y i*=0j=1j=1j=1 n n n2011/03-第2章 对偶问题-17-（6）单纯形表中的对应关系 max z= 2 x1 +3 x2 min w= 12y1 + 8y

11、2 + 16y3 +12 y4 s.t 2 x1 +2 x2 12 s.t 2y1 + y2 + 4y3 +0 y4 2 x1 +2 x2 8 2y1 +2y2 + 0y3 +4 y4 3 4 x1 16 yi 0, i=1, 2, 3, 4 4 x2 12 x1 0 , x2 0 -y5 -y6 -y1 - y2 - y3 - y42011/03-第2章 对偶问题-18-2.4 影子价格(Shadow price) 取决于企业对资源使用的状况，受生产任务、产品结构差异、管 理效率等因素影响。 边际利润的概念：增加单位资源对利润的贡献。 对资源使用决策的参考依据：买进、卖出 对资源使用状况的估

12、算：互补松弛性 机会成本： j = cj- CB B-1pj = cj- Ypj= cj- aijyi， aijyi 为生产xj而放弃其他产品生产的利润。 制定内部结算价格的参考2011/03-第2章 对偶问题-19-2.5 对偶单纯形法由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例： min z=2x1+3x2 max z=-2x1-3x2+0 x3 +0 x4 s.t x1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10, x20 xj 0, (j=1,2,3,4) max z=-2x1-3x2+0

13、 x3 +0 x4 s.t - x1-x2+x3=-3 - x1-2x2+x4=-4 xj 0, (j=1,2,3,4) 2011/03-第2章 对偶问题-20-Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3 -4x3 x400cj - zj -2-300-1/2 0 1 -1/2 1/2 1 0 -1/2x3 x2-1 2cj - zj -1/2 0 0 -3/2 0 -31 0 -2 1 0 1 1 -1x1 x221cj - zj 0 0 -1 -1-2 -3列单纯表计算：2011/03-第2章 对偶问题-21-对偶单纯形法步骤：1.列初始单

14、纯形表，使得所有检验数j 0 ；2.出基变量：取min bi0 = bl x(l)3.入基变量：min |alk0 选择y作入基变量， py= B-1 py= =-0.5 1.5 2 0.25T 继续迭代：2011/03-第2章 对偶问题-26- cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 -8 2 x1 4 0 x6 -12 3 x2 60 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -1.5 -0.125 00 x3 -2 2 x1 4 0 x

15、4 6 3 x2 30 0 1 0 -0.5 -0.5 1 0 0 0 0.25 0 0 0 0 1 -0.25 -0.5 0 1 0 0 0 0.25cjzj0 0 0 0 -0.5 -0.750 x5 4 2 x1 3 0 x6 7 3 x2 30 0 -2 0 1 1 1 0 0.5 0 0 -0.25 0 0 -0.5 1 0 -0.25 0 1 0 0 0 0.25cjzj0 0 -1 0 0 -0.25返回右端项变化分析单纯形表：2011/03-第2章 对偶问题-27- cj 2 5 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 0 2 x1 4 0

16、x6 4 5 x2 20 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -2.5 0.125 00 x3 2 2 x1 2 0 x5 8 5 x2 30 0 1 -2 0 0.5 1 0 0 1 0 -0.5 0 0 0 -4 1 2 0 1 0 0 0 0.25cjzj0 0 0 -2 0 -0.25返回Cj 变化分析单纯形表：2011/03-第2章 对偶问题-28- cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y0 x3 0 2 x1 4 0 x6

17、4 3 x2 20 0 1 -1 -0.25 0 -0.5 1 0 0 0 0.25 0 1.5 0 0 0 -2 0.5 1 2 0 1 0 0.5 -0.125 0 0.25cjzj0 0 0 -1.5 -0.125 0 1.250 x3 1 2 x1 1 5 y 2 3 x2 1.50 0 1 -1.5 -0.125 0.25 0 1 0 0 1.5 -0.125 -0.75 0 0 0 0 -1 0.25 0.5 1 0 1 0 0.75 -0.1875 -0.125 0cjzj0 0 0 -0.25 -0.4375 -0.625 0增加新产品（变量y）变化分析单纯形表：2011/03

18、-第2章 对偶问题-29-2.7 参数线性规划 1. 概念：研究目标函数值随某一参数变化的规律及最优解相应的变化。2. 算法：先令变化量=0，再考察随着的增加引起解的变化情况。3. 最后，画出目标值随的变化所形成的曲线。2011/03-第2章 对偶问题-30-例：有如下线性规划模型： max z=2x1+3x2 s.t x1+x23 x1+2x2 4 + x10, x20（ 0 ）max z=2x1+3x2+0 x3 +0 x4 s.t x1+x2+x3=3 x1+2x2+x4=4 xj 0, (j=1,2,3,4) （1）当 =0 时的最优解；（2）当0时，z 值的变化规律。解：先令z=0，

19、有下述模型的标准形利用单纯形法求解：2011/03-第2章 对偶问题-31-Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj - zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj - zj 1/2 0 0 -3/2031 0 2 -1 0 1 -1 1x1 x221cj - zj 0 0 -1 -123（ =0）2011/03-第2章 对偶问题-32-Cj x1x2x3x4XBbCB2 3 0 02- 1+ x1 x223cj - zj -1 0 -2 1 1 1 1 0 x4 x2cj - zj -1 0 -3

20、 0030 0 -1 -11 0 2 -1 0 1 -1 1（0 2）当0时， b= B-1b= B-1 (0 )T = (- )T，继续迭代如下：（对偶单纯形法） -2 3 （2）其变化曲线如下：2011/03-第2章 对偶问题-33-Z ( )02792011/03-第2章 对偶问题-34-例： 某大学教授利用部分业余时间从事咨询工作。现有三个A、B、C企业欲聘请，各自每小时的咨询费用分别为10，12，16元。教授每月可用于外出咨询的时间为40小时，但对每个企业而言，用于准备的时间与咨询所花的时间的比例分别为0.1，0.5，0.8，教授每月可用于准备的时间应不超过24小时。若假定三个企业每月要求的咨询时间可分别达到80，60，20小时。现问：教授应作何种决策，才能使收益最大？ 从目前看，教授有许多咨询机会，但可用的外出咨询时间及准备的时间有限，所以可考虑雇用助手（用于帮助准备），但要支付每小时4元的费用，现帮助教授分析一下，它是否该雇用助手，若需雇用，每月应雇用多少时间？20