第2章对偶规划及灵敏度分析

1、第2章对偶规划与灵敏度分析第2章 对偶规划与灵敏度分析本章要点：o线性规划对偶问题的提出o线性规划问题的对偶理论o对偶解的经济解释o对偶单纯形法o灵敏度分析2.1 线性规划的对偶问题与对偶理论一、对偶问题的提出例2.1 某家具公司(设为甲公司)生产桌子和椅子两种家具，有关资料如下表所示，问该家具公司应如何安排生产才能每月的销售收入最大？桌子椅子可供工时量（小时/月）木工工时（小时/件）43120油漆工工时(小时/件)2150售价（元/件）5030家具加工时间加工工种设两种产品产量分别为x1,x2，则其线性规划模型为：213050 xxZMax0, 050212034. .212121xxxxx

2、xtso假设现有乙公司准备租借用(购买)该木器厂的木工和油漆工两种劳力的劳务，需要考虑这两种劳务以什么样的价格租入最合算？而同时甲公司要以什么条件才会租让？甲公司肯定会以自己利用两种劳力的劳务组织生产所获得的利润最大为条件，设每个木工的租用价格为y1，每个油漆工的租用价格为y2，则乙公司愿意租用的出资为：甲公司愿意出租的条件会是公司单个劳力出售的劳务收入之和自己组织生产所创造的利润.即:2.1 线性规划的对偶问题与对偶理论2150120yySMin30350242121yyyy同时：y1和y2要满足非负条件.2.1 线性规划的对偶问题与对偶理论(2)o即:213050 xxZMax0, 050

3、212034. .212121xxxxxxts2150120yySM in0, 03035024. .212121yyyyyyts（P）（D）MaxCXZ OXbAXts . .MinYbSTOYCYAtsTT. .任何线性规划问题都有对偶问题，而且都有相应的经济意义。2.1 线性规划的对偶问题与对偶理论(3)二、原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数最大化（MaxZ)目标函数最小化（MinS)无限制变量00型型型约束型型型约束无限制变量00n个变量n个约束m个约束m个变量约束条件限定向量（右边项）目标函数价值向量（系数）目标函数价值向量约束条件限定向量2.

4、1 线性规划的对偶问题与对偶理论（4）321342xxxZMax0, 0832353410. .21321321321xxxxxxxxxxxt sn写出下列问题的对偶问题：3218510yyySMin. .t s23321yyy424321yyy333321yyy0, 031yy2.2 线性规划的对偶理论o线性规划对偶理论的主要基本定理：定理1：对称性定理 对偶问题的对偶是原问题定理2：设X和Y分别是原问题P和对偶问题D的可行解则：必有CXbTY 。定理3：对偶原理 原问题P和对偶问题D存在如下对应关系：1）P有最优解的充要条件是D有最优解；2）若P无界则D无可行解，若D无界则P无可行解；3）

5、若X*和Y*分别是P和D的可行解，则它们分别为P和D的最优解的充要条件是CX*=Y*b2.2 线性规划的对偶理论（2）o线性规划对偶理论的主要基本定理：定理4：互补松驰性定理： 如果X和Y分别为P和D的可行解，它们分别为P和D的最优解的充要条件是 （C-YTA）X=0和YT（b-AX）=0max543210002xxxxxz)5 , 1(052426155.52142132jxxxxxxxxxstjmin543210052415yyyyys)5 , 1(012526.5321432iyyyyyyyysti对偶变量y1y2y3对偶变量x1x2原问题P：max543210002xxxxxz)5 ,

6、 1(052426155.52142132jxxxxxxxxxstj对偶变量y1y2y3对偶问题D：原问题与对偶问题互补松驰对应关系用单纯形法求解：Cj原问题变量原问题松驰变量xBbx1x2x3x4x5x315/2 0015/4-15/2x17/21001/4-1/2x27/2010-1/43/2-z-3/2000-1/4-1/2对偶变量的剩余变量对偶问题变量y4y5y1y2y3Cj对偶问题变量对偶变量的剩余变量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原问题松驰变量原问题变量x3x4x5x1x22.3

7、对偶单纯法一、对偶单纯法的基本思想n求解线性规划的单纯法的思路是：对原问题的一个基本可行解（即所有右端常数0） ，判别是否所有的检验数j0。若是，又基变量中无人工变量，即找到了问题的最优解；若为否，再找出相邻的目标函数值更大的基本可行解，并继续判别，只要最优解存在，就一直迭代进行到找出最优解为止。n根据对偶原理性质可知：在同一个单纯形表中，如果原问题为可行解（即所有右端常数0），而且判别行所有检验数j0，则原问题和对偶问题都达到最优解。n对偶单纯法的基本思想是：先找出对偶问题的基本可行解（即单纯形表中判别行所有的检验数j0），但原问题为非可行解（即不满足所有右端常数0），然后一直保持对偶问题为

8、可行解的条件下，利用对偶单纯法进行迭代，一直到原问题也为可行解（即满足所有右端常数0），这时也就同时得到了原问题和对偶问题的最优解。2.3 对偶单纯法（2）o可知：对偶单纯形法是利用对偶原理求解原问题的一种方法，而不是求解对偶问题解的单纯形法。riibbb0|minrssrjrjjjaaa0|min1）写出问题初始单纯形表：单纯形表中判别行所有的检验数j0；若b列的数字都为非负（即0 ），则已得到最优解；否则，转下一步；2）确定退出基变量。3）确定进入基变量。4）继续迭代，直至求出最优解。二、对偶单纯法计算步骤2.3 对偶单纯法（3）o例：2153xxz0,966030824. .212121

9、xxxxxxtsMin2153xxzz0,966030824. .4321421321xxxxxxxxxxtsMax2153xxz0,966030824. .4321421321xxxxxxxxxxtsMax化标准型式：化为对偶单纯法求解形式2.3 对偶单纯法（4）：求解过程CBCj-3-500 xBbx1x2x3x40 x3-8-4-2100 x4-96-30(-60)01-Z0-3-500j1/101/12CBCj-3-500 xBbx1x2x3x40 x3-4.8-301-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/22.3 对偶单纯法（5）：求

10、解过程CBCj-3-500 xBbx1x2x3x40 x3-4.8(-3)01-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/2CBCj-3-500 xBbx1x2x3x4-3x11.610-1/31/90-5X20.8011/6-1/45-Z-8.800-1/6-7/90j用对偶单纯形法求解：初始单纯形表最终单纯形表单纯形法矩阵解析2.4 对偶解的经济解释一、对偶线性规划的解：P55Cj原问题变量原问题变量xBbx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x27/2010-1/43/2z3/20001/41/2对

11、偶变量的剩余变量对偶问题变量y4y5y1y2y3Cj对偶问题变量对偶变量的剩余变量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原问题松驰变量原问题变量x3x4x5x1x22.4 对偶解的经济解释（2）二、影子价格CXZ bYT就是影子价格即，YBC：YBT1bBCXNBCCbBCBNBNB111)(1。影子价格的大小客观地反映了资源在系统内的稀缺程度。2。影子价格是一种边际价值。3。影子价格是对系统资源的一种最优估价。4。影子价格的价格与系统状态有关。是一种动态价格。首先将线性规划与经济问题联系起来的是 T

12、.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）二人因此而共同分享了1975年的第7届诺贝尔经济学奖。2.5 灵敏度分析一、灵敏度分析的含义o是指系统或事物因周围条件变化显示出来的敏感性程度的分析。o对于线性规划问题的灵敏度分析是指参数A，b，C变化引起的对原问题解的变化的分析。其中：A为技术参数矩阵，b为资源向量，C为价值向量o可以用参数变化后的问题重新用单纯形法求解？ 没必要，意义不大，有些问题看不出来。o把相应的变化反映到最终单纯形表中，再根据情况用相应的方法求解。2.5 灵敏度分析（2）加入变化参数反映到最终单纯形表，视情况分别处理如下：原问题对偶问题结论

13、或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算2.5 灵敏度分析（3）二、三种变化（A，b，C的变化）1。 Cj的变化线性规划目标函数据中变量系数Cj的变化仅仅影响到检验数的变化，所以将Cj的变化直接反映到最终单纯表中。例2-1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项目III

14、每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）212.5 灵敏度分析（3）212xxZMax0,052426155.2121212xxxxxxxts解：设x1和x2分别表示美佳公司制造家电I和II的数量。则该问题可用线性规划模型表示如右：则用单纯形法求解的最终单纯形表如下：CBCj21000ixBbx1x2x3x4x50 x315/2 0015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/22.5 灵敏度分析（4）例2-2：在例2-1中，（1）若家电I的利润降至1.5元/件,而家电II的利润增至2元

15、/件时,美佳公司最优的生产计划有何变化;(2) 若家电I的利润不变,则家电II的利润在什么范围内变化时,则该公司的最优生产计划将不发生变化.解:(1)则将家电I,II的利润变化直接反映到最终单纯形表中得到下表:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21.521.52-33/40001/8-9/46145/42.5 灵敏度分析（5）CBCj1.5 2000ixBbx1x2x3x4x50 x46004/51-61.5 x1210-1/5012X23011/500

16、-Z-900-1/100-3/2迭代后得到下表可知为最优表,可得出最优解为:X*=(2,3,0,6,0)T 最优目标值Zmax=92.5 灵敏度分析（6）(2) 则加入参数a变化到最终表为:CBCj21000 xBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21+a1+a-1/4+a/4-1/2-3a/20023214141aa131a2232 C根据最优判别条件,要保持最优基不变,则: 0j则有:2.5 灵敏度分析（7）2. bi的变化例2-3 在例2-1中,(1)若设备A和调试工序的

17、每天能力不变,而设备B每天的能力增加到32h,分析公司最优计划的变化;(2)若设备A和B每天可用能力不变,则调试工序能力在什么范围内变化时,问题的最优基不变. 解: (1)因有:080bbBbbBb11,则也有22100802/34/102/14/102/154/511bBb变化到最终单纯形表值为:2.5 灵敏度分析（8）2121123523272152210bb，b则变化到最终单纯形表中如下:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z000-1/4-1/2-1/435/211/2-1

18、/22.5 灵敏度分析（9）CBCj21000ixBbx1x2x3x4x50 x315051002X15110010X420-401-6-Z-100-100-2则迭代后得到如下表:2.5 灵敏度分析（10）(2)设调试工序每天可用能力为(5+a)h,因有:ab00aaaabBb23212151002/34/102/14/102/154/51aaaaaabb，b2323212721521523212152327215则6411,03b，a，b即可求得由2.5 灵敏度分析（11）3.技术系数发生变化的分析例2-4 在例2-1基础上，若家电II每件需须设备A，B和调试工时变为8h、4h和1h，该产品的利润变为3元/件，试重新确定美佳公司最优生产计划。解：分两步：第一步：计算检验数。设新家电产品II的产量为x，则对应检验数为：02/32122PBCCB第二步：计算新增变量在最终单纯形表中的列向量。（如上一步中计算为0则无需进行这一步）2/12/12/111482/34/102/14/102/154