第3章对偶理论与灵敏度分析

1、北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！第三章对偶理论与灵敏度分析3.1 对偶理论问题的提出（1 学时）3.1.1 对偶线性规划问题的导出对一个问题可以从不同的角度去看，解决一个问题也可以有多种。例 3.6 一个工厂生产三种怎么生产获得最大利润。表 3-3所用工时和材料以及利润如下表所示，决策应该其线性规划模型为maxìïz = 2x1 + 3x2 + 3x3£ 33£ 9³ 0s.t.í3ïî3æ x1 öz = (2, 3, 3) ç x

2、47;max或ç2 ÷ç x ÷è 3 øìæ x1 ö1 öç÷ïæ114æ3öïç1÷ x£ ç ÷7÷29ïèøç xè ø÷ïè 3 øs.t.íïïïïîæ x öæ 0

3、öç1 ÷ç ÷ç x2 ÷ ³ ç 0÷ç x ÷ç 0÷è 3 øè ø从另一个角度去思考这个问题，就是当另外一个工厂提出购买这个厂的所有工时和材料时，工厂应该怎么做决策才会使得这样一个出现双赢的局面。简要的双赢的原理：价格尽量低，使得其具有竞争力，同时希望客户能出更高的价格，这样企业就可以获得的利润。亦即，生产一件 A 的工时和材料的销售收入应该不少于 A 生产一件 B 的工时和材料的销售收入应该不少于 B 生

4、产一件 C 的工时和材料的销售收入应该不少于 C的的的利润； 利润； 利润。定义工时和材料分别为 y1,y2，于是有æ y1 öminW = 3y1 + 9 y2minW = (3,9)ç÷yè 2 ø消耗总量工时1113材料1479利润233北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！ìæ11 öæ 2öïç÷æ y1 öç ÷ì y1 + y2³ 24

5、7;ç y ÷ ³ ç 2÷ïç1ï y+ 4 y ³ 3s t ïïç17 ÷è 2 øç3 ÷12. .í ys.t.íèïïøè ø或+ 7 y ³ 3ï12æ y öï y³ 0, y ³ 0ç 1 ÷ ³ 0î 12ïy

6、è 2 øî上述两个线性规划模型是在同一企业的资源状况和生产技术条件下产生的，是同一个问题从不同角度来观察所产生的，因此两者是密切相关的，我们称这两个线性规划问题是互为对偶的两个线性规划问题，其中一个问题是另一问题的对偶问题。3.1.2对偶问题的定义max z = c1x1 + c2 x2+ " +cn xnìæ a11a12""a1n öæ x1 öæ b1 ö÷çx÷ç÷bïç aaa

7、9;ç2n ÷ç2 ÷ £ ç÷21222s t ïç÷ç#÷ç#÷. .íç #（3-5）÷ç÷ç÷ïç a÷ç x ÷ç b ÷a"aïè m1ïîmn øè n øè m øm 2³ 0nmin z =

8、b1y1 + b2 y2+" +bm ymìæ a11am1 öæ y1öæ c1 öa21""ïç a÷ç÷ç÷ycaam 2 ÷ç 2÷ ³ ç 2 ÷ïç1222s t ïç÷ç#÷ç# ÷. .íç #（3-6 ）÷ç÷&

9、#231;÷ïç a÷ç y ÷ç c ÷a"aïè 1nmn øè m øè n ø2nïî y1 , y2 ,", ym ³ 0用矩阵的形式表示对偶问题max Z = CXmin W = bT Y Tì AT Y T ³ CT£ bìAXs.t.íXs.t.í与写法正确吗？³ 0îY³ 0Tî原

10、问题模型与对偶问题在结构上的对应如表 3-4表 3-4北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！3.2 线性规划的对偶理论（3 学时）对于对偶问题，有下面几个重要的定理定理 3.1 弱对偶定理若互为对偶的线性规划（3-5）与（3-6）分别有可行解2 ,", xn ) 和Y = ( y1 , y2 ,", ym )T则其相应的目标函数值满足：Z = c1 x1 + c2 x2 + "+ cn xn £ b1 y1 + b2 y2 + "+ bm ym = W证明 由 X ,Y 分别为（3-5）和（3-6）的可行

11、解，（3-5）与（3-6）互为对偶问题，因此下面的证明是最吗？是不是有点繁琐？！mm当 x j ³ 0 时，有å aij yi ³ c j ，则c j x ji=1当 x j £ 0 时，有å aij yi £ c j ，则c j x j£ å x j aij yi i=1mm£ å x j aij yii=1i=1mm当 x j 符号不限时，有å aij yi = c j ，则c j x j i=1= å x j aij yi i=1nnmZ = åcj x j&

12、#163; åå x j aij yi(3-7)j =1j =1 i=1nn同理，当 yi ³ 0 时，有å aij x j £ bi ，则å x j aij yi £ bi yij =1j =1nn当 yi £ 0 时，有å aij x j ³ bi ，则å x j aij yi £ bi yij =1j =1nn当 yi 符号不限时， å aij x j = bi ，则å x j aij yi £ bi yij =1j =1原问题（或对偶问题

13、）对偶问题（或原问题）目标函数 maxZ目标函数 minW约束条件： m 个第 i 个约束条件类型为“” 第 i 个约束条件类型为“” 第 i 个约束条件类型为“”变量数：m 个第 i 个变量“” 第 i 个变量“”第 i 个变量是变量变量数：n 个第 j 个变量0 第 j 个变量0第 j 个变量是变量约束条件数：n 个第 j 个约束条件类型为“” 第 j 个约束条件类型为“” 第 j 个约束条件类型为“”目标函数系数 约束条件右端项约束条件右端项目标函数系数北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！mm nW = åbi yi³ 

14、29;å x j aij yi(3-8)i=1i=1 j =1结合（3-7）与（3-8）立即可得定理的结论mnåbi yii=1³ åcj x j j =1推论 1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论 2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论 3若原始问题可行，则其目标函数的充要条件是对偶问题没有可行解。定理 3.2 最优性准若 X 和Y 分别为互为对偶问题的线性规划（3-5）与（3-6）的可行解，且使CX = bT Y T ， 则 X 和Y 分别是相应线性

15、规划的最优解。CX £ bT Y T证明 对于 X 和Y 将分别有CX £ bT Y TCX £ bT Y TCX = bT Y T ，故有又由于bT Y T£ bT Y TCX £ CX由于 X 与Y 分别是（3-5）与（3-6）的可行解，而 X 与 Y 分别是（3-5）与（3-6）的任意可行解，根据最优解的概念知 X 与Y 是（3-5）与（3-6）的最优解。定理 3.3 对偶定理若原始问题有最优解，那么对偶问题也有最优解；且目标函数值相同。证明 设原问题的最优解X ，对应的基 B 是最优基，则必有对应B 的检验数满足s N = CN - C

16、B B N £ 0 。即得到YA ³ C ，其中Y = C B ，若这时Y = C B 是对偶问-1-1-1BB题的一个可行解，对应的目标函数值为W = Yb = CB B b-1X因为原问题的最优，使得目标函数取值Z* = CX = CB B b-1由此，得到Y b = CB B b = CX-1可知Y 是对偶规划的最优解。定理 3.4 互补松弛定理ÙÙÙÙÙ若X ，Y 分别是原问题和对偶问题的可行解，那么Y Xi = 0 和 Yi X = 0 ，当且仅当X ，ÙY 为最优解。Xi 这样的符号前面用过吗？能知道是

17、什么含义吗？证明 设原问题和对偶问题的原问题是对偶问题北交大管理运筹学考研详见，网学天地（max z = CX和资料，、考点、命题规律独家）；咨询min w = Yb讲解！AX + Xi = b X, Xi ³ 0将原问题目标函数中的系数YA - Yi = C Y, Yi ³ 0C 用 C=YA-Y，代替后，得到z = (YA - Yi )X = YAX - Yi X（3-9）将对偶问题的目标函数中系数，用b = AX + Xi 代替后，得到w = Y(AX + Xi ) = YAX + YXi（3-10）ÙÙÙÙÙ

18、7;ÙÙ若Y Xi = 0 ， Yi X = 0 ；则Yb = YAX = C X 由定理 3.10 可知X ， Y 是最优解。ÙÙ又若X ， Y 分别是原问题和对偶问题的最优解，根据定理 3.10，则有ÙÙÙÙCX = Y A X = Y bÙÙ由（3-9）和（3-10）可知，必有Y Xi = 0 ， Yi X = 0 。例 3.7 已知线性规划max z =ì3 + 4x4x3 + 3x4 £ 20ï2x+ 2x £ 20ï34í&

19、#239;x - x £ 134ï, x ³ 0î34的最优X * =（0，0，4，4） T 。试利用互补松弛原理求对偶问题的最优解。解 对偶问题为Min w=20y 1 +20y 2 +y 3ì y1 + 2 y2 + y3 ³ 1ï 2y + y - y ³ 2123ïí2y1 + 3y2 + y3 ³ 3ï3y + 2 y - y ³ 4ï123ïîy1, y2 , y3 ³ 0*由于 x 3 =x 4 =4>0，

20、故对偶问题约束方程式（3）、（4）是等式约束，即对 Y 成立等式ì2y + 3y+ y =3*ï123í3y + 2 y- y= 4*ïî123把 X * 代入原问题 3 个约束中可知原问题式（3）是不等式，故 y * =0，然后解方程组3ì 2y + 3y =3*ï12í3y + 2 y= 4ï*î12得到ì*y =6/5ï1íy= 1/ 5*ïî 2故对偶最优Y * =(6/5,1/5,0), z * =w * =28.例 3.8考虑线性规划

21、max z3x3北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！x2 +ìïxïíïïî2=1³ 0已知它的最优X * =（4，1，9） T ，求对偶问题的最优解。解 对偶问题是min w = 11y1 + 3y2 + y3ì y1 - 4 y2 - 2 y3 ³ 3ï- 2y + y ³ -1ï12íy+ 2 y + y ³ -1ï123ïy³ 0, y £ 0, y 无约束

22、î 123由于 x * >0,x * >0, x * >0，故上面 3 个技术约束应是等式，即123ì y * - 4 y * - 2 y * = 3123ï- 2y * + y * = -1í12ïy * + 2 y * + y * = -1î123从中解得ì y * = 1/31ïy= -*í1 /32ï y * = -2 / 3î3z * =w * =23.3对偶问题的解释价格（1 学时）在对偶问题导出的例中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优

23、解所代表是企业在当前的资源状况 b，技术状况 A 和市场状况 C 已知的情况下， 源对企业的价值。资3.3.1价格的原理* ,", x* )T和对于的线性规划问题（3-5）和其对偶问题（3-6），若2nY * = ( y* , y* ,", y* ) 分别是式（3-5）和式（3-6）的最优解，则据定理 3.3 知其最优值相等，12n即Z* = c x* + c x* + " + c= W * = b y* + b y* + " + bx*y*1 12 2n n1 12 2m m由此可知原线性规划问题（3-5）的最优值与右端常数之间的为Z* = b y*

24、+ b y* + "+ by *(3-11)1 12 2m m因此， y * 代表着当第 i 个右端常数b 增加一个时，最优目标函数值的相应增量。ii若把 Z * 看作b ,", b 的函数，则由 ¶Z * = y* ，可知 y * 是资源b 的价值的一种度量，1m¶biiii北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！称为bi 的价格，其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率，其含义是为约束条件所付出的代价。-1值得注意的是，当 B 是原问题的最优基时，Y* = CB B就是价格，可见价格只是对资

25、源价值的边际度量，当 A，b 或C 改变时， 例 3.9用线性规划的对偶问题进行求解max z = 2x1 + 3x2 + 3x3价格也会发生相应的改变。£ 3£ 9³ 0ì3s t ï. .í3ïî3解 线性规划的对偶问题为min w = 3y1 + 9y2ì y1 + y2³ 2ï y+ 4 y ³ 3s t ï12. .í y+ 7 y ³ 3ï12ïî y1 ³ 0, y2 ³ 0求解可得

26、5151y1 = 3 , y2 = 3 ，即工时的价格为 ，材料的3价格为 。31如果目前市场上材料的价格低于 ，则企业可以购进一部分材料来扩大生产，反之若31市场价高于 ，则企业可以卖掉部分材料。35如果有客户以高于 的价格购买该企业的工时，则可以出售一些工时，反之若客户出35价低于 则不应出售工时，若企业能够通过加班或租用别人的3来扩大工时，则当所获5得的额外工时的成本低 时，企业可以增3时，否则不应增时。在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表的是企业在当前的资源状况 b，技术状况 A 和市场状况 C 已知的情况下资源对企业的价值。因

27、此， y * 代表着当第 i 个右端常数b 增加一个时，最优目标函数值的相应增量。ii在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表是企业在当前资源对企业的价值。的资源状况 b，技术状况 A 和市场状况 C 已知的情况下3.3.2 对偶理论的应用若 B 是线性规划的最优基，则p = C B -1 是对偶问题的最优解。由检验数的计算B子矩阵，不妨设 A 的前 m 列为可知：s = C - pA 。若 A 中有矩阵，则在最优表中有s i = ci - p ip i = ci - s ii = 1,2,", mi = 1,2,",

28、m可知北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！其中， ci 为目标函数中 xi 的系数， s i 为最优表中 xi 的检验数。3.4对偶单纯形法（1 学时）对偶单纯型法就是利用对偶理论来求解线性规划问题的，而不是求解线性规划对偶问题的。设线性规划问题为max z = CX= bìAXs.t.íx ³ 0î线性规划解的概念可知，当 B 对应的基本若 B 是 A 中的一个基，回顾第二是可行解时，我们称 B 为可行基，当 B 对应的基本可行解是最优解时，我们称 B 为最优基，在此我们定义如下概念：若C B -1 是对偶问题

29、的可行解，则称 B 为对偶可行基，且使单纯形乘子p = CB -1 成BB为对偶问题的可行解，即满足pA ³ C 。结合最优性判别定理，最优基既应该是可行基，也应该使检验数s N £ 0 ，而这就意味着 B 也是对偶可行基。反之当 B 是可行基，且也是对偶可行基时，对应于 B 的基本可行解的检验数s N £ 0（ CB B A ³ C ），因此 B 也是最优基。-1于是有如下定理。定理 3.5B 是线性规划的最优基的充要条件是，B 是可行基，而且也是对偶可行基。我们已经了解了对偶问题的基本概念和基本定理，这一节中着重来讨论对偶单纯型法。线性规划以为例，对

30、于线性规划max z = CX= bìAXs.t.íx ³ 0î若 B 是 A 中的一个基，回顾线性规划解的概念可知，当 B 对应的基本是可行解时，我们称 B 为可行基，当 B 对应的基本可行解是最优解时，我们称 B 为最优基， 用对偶单纯形法求解原问题，它有应用的前提条件，有一个基，其对应的基本解满足以下两条：（1） 单纯形表的检验数行全部非正（保证它是对偶可行基）；（2） 变量取值有负数（对于原问题来说是不可行）。表 3-4c j ®-3-9000qCBXBb0x3-20x4-30x5-3x1x2x3x4x5-1-1100-1-4010-1

31、-7001-Zcj - zj-3-9000北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！对偶单纯形法的步骤步骤 1 求一个满足最优检验条件的初始基本解，列出初始单纯形表；步骤 2 可行性检验，若所有的右端系数均大于等于 0，即b j ³ 0, i = 1,2,", m ,则已得到最优解，停止运算，否则，转到步骤 3；步骤 3 求另一个满足最优检验条件且更接近可行解的基本解。bi < 0 ，设第 l 行的最小，确定换出变量 找非可行解中最小者，即minbi则 l 行成为主行，该行对应的基变量为换出变量；（1）（2）确定换入变量 最小比例原

32、则（设目标函数为 max 型，检验数为 cj zj），若é cjù- z jc- z¢ê a< 0 ú =kk=minê则第 k 列为主列，第 k 列的变量úûk¢lj¢a lja lkjëxk 为换入变量。若找不到主列或换入变量，则原线性规划的运算，否则转到步骤（3）；以主元 alk为中心迭代得到另一个满足最优检验条件且更接近可行解的基本解。即将主元 alk变换为 1，主元 alk所在列的其他技术系数变换为 0，并用换入变量及其价值系数置换出变量及其价值系数，得到新的单纯形表与

33、另一个满足最优检验条件且更接近可行解的基本解。再转到步骤 2。解，停止（3）例 3.10 用对偶单纯形法求解如下线性规划问题+ 3 x 4min f (ì2+ x 4³ 6³ 4³ 03s.t.ï - 2+ xí34ï, xî34解 将上述线性规划变换为如下适合对偶单纯形法的形式- 3 x 4min g (ì -2- x 4+ x 5= -6= -4³ 03s.t. ï 2Max- x+ xí346ï,î其中，g(x) = -f (x)，变量 x5 和 x

34、6 为剩余变量。36表 3-5用对偶单纯形法求解例 3.10 的单纯形表过程cj ®-1-50-300序号CBXBbx1x2x3x4x5x6-1-21-11021-4-10100x5 x6-6-4-Z= 0cj - zj-1-50-300比值-3/-1=3-9/-1=9北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！= X 2 = (= (14 , 0 , 8 , 0 , 0 , 0 ) TX *,) T36最优解时的目标函数值为 f (X *) = - g (X*) = 14。例 3.11 用对偶单纯形法求解下列线性规划问题。Min w = 15 y1

35、 + 24 y2 + 5 y3ì6 y2 + y3 ³ 2ïí5 y1 + 2 y2 + y3 ³ 1ï y , y , y ³ 0î 123解 先标准化得Max w = -15 y - 24 y - 5 y + 0 y + 0 y'12345ì6 y2 + y3 - y4 = 2ïí5 y1 + 2 y2 + y3 - y5 = 1ï y³ 0î约束条件两边乘-1，得iMax w = -15 y - 24 y - 5 y + 0 y + 0 y&

36、#39;12345ì-6 y2 - y3 + y4 = -2ï-5 y - 2 y - y + y = -1í1235³ 0ï yî i列出单纯形表，按照上述步骤计算，计算过程见表 3-6。表 3-6cj ®-15-24-500序号CBYBby1y2y3y4y50-b-110-5-2-10100y4y5-2-1-15-24-500-24y21/3011/6-1/60-10x1 x66-1612-11-100-3-2-321-Z=- 6cj - zj0-3-1-2-10-10x1 x3148017/215/2-2-1/203/

37、23/2-1-1/2-Z=-14cj - zj0-3/20-1/-2-2-1/2北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！3.4对偶单纯形法（1 学时）对偶单纯型法就是利用对偶理论来求解线性规划问题的，而不是求解线性规划对偶问题的。设线性规划问题为max z = CX= bì AXs.t.íx ³ 0î线性规划解的概念可知，当 B 对应的基本若 B 是 A 中的一个基，回顾第二是可行解时，我们称 B 为可行基，当 B 对应的基本可行解是最优解时，我们称 B 为最优基，在此我们定义如下概念：若C B -1 是对偶问题的可

38、行解，则称 B 为对偶可行基，且使单纯形乘子p = CB -1 成BB为对偶问题的可行解，即满足pA ³ C 。结合最优性判别定理，最优基既应该是可行基，也应该使检验数s N £ 0 ，而这就意味着 B 也是对偶可行基。反之当 B 是可行基，且也是对偶可行基时，对应于 B 的基本可行解的检验数s N £ 0（ CB B A ³ C ），因此 B 也是最优基。-1于是有如下定理。定理 3.5B 是线性规划的最优基的充要条件是，B 是可行基，而且也是对偶可行基。我们已经了解了对偶问题的基本概念和基本定理，这一节中着重来讨论对偶单纯型法。线性规划以为例，对于线

39、性规划max z = CX= bì AXs.t.íx ³ 0î若 B 是 A 中的一个基，回顾线性规划解的概念可知，当 B 对应的基本是可行解时，我们称 B 为可行基，当 B 对应的基本可行解是最优解时，我们称 B 为最优基， 用对偶单纯形法求解原问题，它有应用的前提条件，有一个基，其对应的基本解满足以下两条：（1） 单纯形表的检验数行全部非正（保证它是对偶可行基）；（2） 变量取值有负数（对于原问题来说是不可行）。表 3-4c j ®-3-9000q0y5-1/3-50-2/3-1/31-150-1-40-24-5y2y31/41/2-5/4

40、101/41/415/2011/2-3/2-17/2-15/200-7/2-3/2北交大管理运筹学考研详见，网学天地（和资料，、考点、命题规律独家）；咨询讲解！对偶单纯形法的步骤步骤 1 求一个满足最优检验条件的初始基本解，列出初始单纯形表；步骤 2 可行性检验，若所有的右端系数均大于等于 0，即b j ³ 0, i = 1,2,", m ,则已得到最优解，停止运算，否则，转到步骤 3；步骤 3 求另一个满足最优检验条件且更接近可行解的基本解。bi < 0 ，设第 l 行的最小，确定换出变量 找非可行解中最小者，即minbi则 l 行成为主行，该行对应的基变量为换出变

41、量；（4）（5）确定换入变量 最小比例原则（设目标函数为 max 型，检验数为 cj zj），若é cjù- z j- zc¢ê a< 0 ú =kk=minê则第 k 列为主列，第 k 列的变量¢úû¢klja lja lkjëxk 为换入变量。若找不到主列或换入变量，则原线性规划的运算，否则转到步骤（3）；解，停止（6）以主元 alk为中心迭代得到另一个满足最优检验条件且更接近可行解的基本解。即将主元 alk变换为 1，主元 alk所在列的其他技术系数变换为 0，并用换入变量及其价值系数置换出变量及其价值系数，得到新的单纯形表与另一个满足最优检验条件且更接近可行解的基本解。再转到步骤 2。例 3.10 用对偶单纯形法求解如下线性规