《(精品)运筹学对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《(精品)运筹学对偶理论与灵敏度分析.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 对偶理论与灵敏度分析对偶理论与灵敏度分析w要求：要求：了解了解LP对偶问题的实际背景对偶问题的实际背景了解对偶问题的建立规则与基本性质了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握对偶最优解的计算及其经济解释掌握掌握LP的灵敏度分析的灵敏度分析2.1 2.1 对偶问题的提出对偶问题的提出对偶问题的提出对偶问题的提出w某某厂生产两种产品，需要三种资源，已知厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资各产品的利润、各资源的限量和各产品的资源消耗系数如下表：源消耗系数如下表：产品产品产品产品A A产品产品产品产品B B资源限量资源限量资
2、源限量资源限量 y y1 1 劳动力劳动力劳动力劳动力 y y2 2 设设设设 备备备备 y y3 3 原材料原材料原材料原材料 9 9 4 4 3 34 45 51010360360（工时）（工时）（工时）（工时）200 200（台时）（台时）（台时）（台时）300 300（KGKG）利润利润利润利润元元元元/kgkg7070120120问题：如何安排生产计划，使得获利最多问题：如何安排生产计划，使得获利最多？解：设生产解：设生产A产品产品x1(kg）,B产品产品x2（kg），），数学模型为：数学模型为：maxZ=70X1+120X2 9X1+4X2360 4X1+5X2200 3X1+10
3、X2 300 X10 X20 现在现在现在现在A A、B B两产品销路不畅，可以将所有资源出两产品销路不畅，可以将所有资源出两产品销路不畅，可以将所有资源出两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？租或外卖，现在要谈判，我们的价格底线是什么？租或外卖，现在要谈判，我们的价格底线是什么？租或外卖，现在要谈判，我们的价格底线是什么？w设每个工时收费设每个工时收费y1元，设备台时费用元，设备台时费用y2元，元，原材料附加费原材料附加费y3元。元。出租收入不低于生产收入：出租收入不低于生产收入：9y1 1+4y2 2+3y3 3704y1 1+5y2 2+10y3 3
4、120目标：目标：=360y1 1+200y2 2+300y3 3出租收入越多越好？至少不低于某数，并且出租收入越多越好？至少不低于某数，并且保证出租出去，目标函数取最小化。保证出租出去，目标函数取最小化。原问题与对偶问题之比较原问题与对偶问题之比较 原问题：原问题：对偶问题：对偶问题：maxZmaxZ=70X=70X1 1+120X+120X2 2 min min=360y=360y1 1+200y+200y2 2+300y+300y3 3 y y1 1 9X9X1 1+4X+4X2 2360 360 9y9y1 1+4y+4y2 2+3y+3y3 3 7070 y y2 2 4X 4X1
5、1+5X+5X2 2 200 (3.1)200 (3.1)4y4y1 1+5y+5y2 2+10y+10y3 3 120 120（3.2)3.2)y y3 3 3X3X1 1+10X+10X2 2 300 300 y y1 1 0,0,y y2 2 0,0,y y3 3 00 X X1 10 0 X X2 200 2.2 对偶规则对偶规则原问题一般模型：原问题一般模型：对偶问题一般模型：对偶问题一般模型：maxZ=CX min=YbYb AXAX b (1)YA b (1)YA C (2)X 0 Y 0例例线性规划线性规划问题maxz=3x1+5x2stx1+3x2 107x1+4x2 20
6、xj 0;j=1,2.对偶偶问题为：ming=10y1+20y2sty1+7y2 33y1+4y2 5yi 0;i=1,2。对偶偶规划的一般概念划的一般概念例：例：例：例：给给定定定定标标准形的准形的准形的准形的线线性性性性规规划划划划 maxzmaxz=CX=CX（LPLP）=bb（3 3）x xj j 0,j=1,2,n0,j=1,2,n求其求其求其求其对对偶偶偶偶规规划。划。划。划。解：解：解：解：约约束方程束方程束方程束方程组组（3 3）等价于：）等价于：）等价于：）等价于：AXAX bb且且且且AXAX b b。因此（因此（因此（因此（3 3）化（）化（）化（）化（1 1）的形式）的
7、形式）的形式）的形式为为：maxzmaxz=CX=CXbb（-）-bbX0X0设对偶变量为设对偶变量为设对偶变量为设对偶变量为Y Y1 1,Y,Y2 2,对对偶偶偶偶问题为：问题为：问题为：问题为：MinwMinw=Y Y1 1b-Yb-Y2 2bbMinwMinw=（Y Y1 1-Y-Y2 2）bb(Y(Y1 1,Y,Y2 2)A)ACC即：即：即：即：（Y Y1 1-Y-Y2 2）AAC,C,-AY-AY1 1,Y,Y2 200YY1 1,Y,Y2 200令：令：令：令：Y=YY=Y1 1-Y-Y22为无约束，为无约束，为无约束，为无约束，对对偶偶偶偶问题为：问题为：问题为：问题为：Min
8、wMinw=YbYbYAYACCYY为无约束为无约束为无约束为无约束原规划与对偶规划的线性关系原规划与对偶规划的线性关系原（对偶）规划原（对偶）规划原（对偶）规划原（对偶）规划对偶（原）规划对偶（原）规划对偶（原）规划对偶（原）规划目标目标目标目标max zmax zmin wmin w 目标目标目标目标变量变量变量变量n n个个个个 0 0 0 0 自由自由自由自由（无约束）（无约束）（无约束）（无约束）n n个个个个 =约束约束约束约束约束约束约束约束 mm个个个个 =mm个个个个 0 0 0 0 自由自由自由自由（无约束）（无约束）（无约束）（无约束）变量变量变量变量 限制向量限制向量限
9、制向量限制向量 价值向量价值向量价值向量价值向量 价值向量价值向量价值向量价值向量 限制向量限制向量限制向量限制向量对偶规则：对偶规则：原问题有原问题有原问题有原问题有mm个约束条件，对偶问题有个约束条件，对偶问题有个约束条件，对偶问题有个约束条件，对偶问题有mm个变量个变量个变量个变量原问题有原问题有原问题有原问题有n n个变量，对偶问题有个变量，对偶问题有个变量，对偶问题有个变量，对偶问题有n n个约束条件个约束条件个约束条件个约束条件原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项原问题的价值系数对应对偶问题的右端项原问题的右端
10、项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值系数原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数原问题的技术系数矩阵转置后为对偶问题系数原问题的技术系数矩阵转置后为对偶问题系数原问题的技术系数矩阵转置后为对偶问题系数矩阵矩阵矩阵矩阵原问题的约束条件与对偶问题方向相反原问题的约束条件与对偶问题方向相反原问题的约束条件与对偶问题方向相反原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反原问题与对偶问题优化方向相反原问题与对偶问题优化方向相反原问题与对偶问题优化方向相反对偶规则对偶规则对偶规则对偶规则 原问题原问
11、题原问题原问题 对偶问题对偶问题对偶问题对偶问题目标函数目标函数目标函数目标函数 maxmax min min 目标函数目标函数目标函数目标函数约束条件约束条件约束条件约束条件 =变量变量变量变量 无约束无约束无约束无约束 变量符号变量符号变量符号变量符号 无约束无约束无约束无约束 约束条件约束条件约束条件约束条件=由由由由max minmax minmax minmax min对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；由由由由min maxmin maxmin max
12、min max对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；原问题一般模型：原问题一般模型：原问题一般模型：原问题一般模型：对偶问题一般模型：对偶问题一般模型：对偶问题一般模型：对偶问题一般模型：maxZmaxZ=CX min=CX min=YbYb AXAX b (1)YA C (2)b (1)YA C (2)X 0 Y 0 X 0 Y 0 例例例例2 2 max max=7y7y1 1+4y4y2 2-2y-2y3 3minZminZ=3x=3x1 1+2x+2x2 2
13、-6x-6x3 3+x+x5 5 2y2y1 1+y+y2 2-y-y3 3 3 3 2x 2x1 1+x+x2 2-4x-4x3 3+x+x4 4+3x+3x5 5 7 y7 y1 1 +3y+3y3 3 22 x x1 1+2x+2x3 3-x-x4 4 4 -4y4 -4y1 1+2y+2y2 2 -6-6 -x -x1 1+3x+3x2 2 -x-x4 4+x+x5 5 =-2 y=-2 y1 1 -y-y2 2 -y-y3 3 0 0 x x1 1，x x2 2，x x3 3 0;3y0;3y1 1 +y+y3 3=1=1 x x4 4 0;x0;x5 5无限制无限制无限制无限制 y
14、 y1 1 0 0，y y2 2 0 0，y y3 3无约束无约束无约束无约束 由由由由max minmax minmax minmax min对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；对偶约束与原问题变量一致，变量与约束相反；由由由由min maxmin maxmin maxmin max对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；对偶约束与原问题变量相反，变量与约束一致；例：写出线性规划的对偶问题例：写出线性规划的对偶问题例：
15、写出线性规划的对偶问题例：写出线性规划的对偶问题解：对应解：对应解：对应解：对应对偶问题为：对偶问题为：对偶问题为：对偶问题为：对偶规则对偶规则原问题一般模型：原问题一般模型：对偶问题一般模型：对偶问题一般模型：maxZ=CX min=YbYb AXAX b (1)YA b (1)YA C (2)X 0 Y 0约束约束“=”变量为变量为“无约无约束束”2.3对偶问题的基本性质1 1对称性：对偶问题的对偶问题是原问题对称性：对偶问题的对偶问题是原问题证明：原问题为：证明：原问题为：maxZ=CX AX b X 0 对偶问题为：对偶问题为：min=Yb YA C Y 0，取负号，变为：取负号，变为
16、：max(-)=-Yb -YA-C Y 0,则上述对偶问题为：则上述对偶问题为：min(-*)=-CX -AX-b X 0 即：即：maxZ=CX AX b X 02 弱对偶性：弱对偶性：极大化原问题的任一可行解的目极大化原问题的任一可行解的目标函数值大于其对偶问题任意可行解的目标函标函数值大于其对偶问题任意可行解的目标函数值。即：数值。即：CX1 Y1b 证明：设证明：设证明：设证明：设原问题为原问题为maxZ=CX，AX b，X 0.X1为原问题的可行解，有为原问题的可行解，有AX1 b，Y1为对偶问题的可行解，则为对偶问题的可行解，则 Y1AX1 Y1b.对偶问题为：对偶问题为：min=
17、Yb，YA C，Y 0.Y1为对偶问题的可行解，所以，为对偶问题的可行解，所以，为对偶问题的可行解，所以，为对偶问题的可行解，所以，Y1A C，有有Y1AX1 CX1.于是于是 CX1 Y1AX1 Y1b.3 3 无界性：无界性：无界性：无界性：原问题（对偶问题）为无界解，对偶问题（原原问题（对偶问题）为无界解，对偶问题（原原问题（对偶问题）为无界解，对偶问题（原原问题（对偶问题）为无界解，对偶问题（原问题）无可行解问题）无可行解问题）无可行解问题）无可行解证明：若对偶问题有可行解证明：若对偶问题有可行解证明：若对偶问题有可行解证明：若对偶问题有可行解Y1，则则CX1 Y1b，与原问题有无界解
18、矛盾。逆不成立。与原问题有无界解矛盾。逆不成立。即：一个为无可行解，则另一个必为无界解或无可即：一个为无可行解，则另一个必为无界解或无可行解行解。例如：例如：例如：例如：原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）原问题（对偶问题）minw=-X1-X2 maxz=y1+y2 X1-X21 y1-y2-1-X1+X2 1 -y1+y2-1 X10 X20 y10 y204 4 可行解是最优解的性质可行解是最优解的性质可行解是最优解的性质可行解是最优解的性质 ：设：设：设：设X*X*是原问题的可行解，是原问题的可行
19、解，是原问题的可行解，是原问题的可行解，Y*Y*是是是是对偶问题的可行解，当对偶问题的可行解，当对偶问题的可行解，当对偶问题的可行解，当CX*=Y*bCX*=Y*b时，时，时，时，X*,Y*X*,Y*是最优是最优是最优是最优解。解。解。解。证明：若证明：若证明：若证明：若CX*=Y*bCX*=Y*b，由性质由性质由性质由性质2 2，对偶问题的所有可行解，对偶问题的所有可行解，对偶问题的所有可行解，对偶问题的所有可行解Y1，因因因因CX*=Y*bCX*=Y*b，所以所以所以所以Y*b=Y*b=CX*Y1b，故故Y*Y*是对是对是对是对偶问题的最优解；对原问题的可行解偶问题的最优解；对原问题的可行
20、解偶问题的最优解；对原问题的可行解偶问题的最优解；对原问题的可行解X X1，有有有有CX1 Y*b=CX*,CX*,故故X*是是是是原问题的最优解。原问题的最优解。原问题的最优解。原问题的最优解。5 5 对偶定理对偶定理对偶定理对偶定理：若一个问题有最优解，则另一问题也有最：若一个问题有最优解，则另一问题也有最：若一个问题有最优解，则另一问题也有最：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为优解，且目标函数值相等。若原问题最优基为优解，且目标函数值相等。若原问题最优基为优解，且目标函数值相等。若原问题最优基为B B，则其则其则其则其对偶问题最优解对偶问题最优解
21、对偶问题最优解对偶问题最优解Y*=CY*=CB BB B-1-1证明：证明：证明：证明：设设设设X*是原问题的最优解，则其对应的基为是原问题的最优解，则其对应的基为是原问题的最优解，则其对应的基为是原问题的最优解，则其对应的基为B B，有有有有C-CC-CB BB B-1-1 A A 0，设设设设Y*=C CB BB B-1-1 ，则则则则Y*A Y*A C.又又对对偶问题目标函数值偶问题目标函数值w=Y*b=C CB BB B-1-1 b；原问题目原问题目标函数值标函数值z=CX*=C CB BB B-1-1 b=w.由性质由性质4，Y*是是对对偶问题的最优解。偶问题的最优解。6 6 对偶松
22、弛性对偶松弛性对偶松弛性对偶松弛性1 1：若：若：若：若X*，Y*Y*是原问题和对偶问题的可是原问题和对偶问题的可是原问题和对偶问题的可是原问题和对偶问题的可行解，那么行解，那么行解，那么行解，那么Y*XY*Xs s=Y Ys sX X*=0,*=0,当且仅当当且仅当当且仅当当且仅当X*，Y*Y*是最优解。是最优解。是最优解。是最优解。证明证明证明证明：原问题：原问题：原问题：原问题 对偶问题对偶问题对偶问题对偶问题 maxZmaxZ=CX min=CX min=Yb Yb AXAX+X+Xs s=b YA-b YA-Y Ys s=C =C X X，X Xs s 00 Y Y，Y Ys s 0
23、 0 则：则：则：则：z=(z=(YA-YA-Y Ys s )X=)X=YAX-YAX-Y Ys s X X w=Y(AX w=Y(AX+X+Xs s)=Y)=YAXAX+YXYXs s 必要性：若必要性：若必要性：若必要性：若Y*XY*Xs s=Y Ys sX X*=0*=0，则则则则z=z=YAX=wYAX=w，由性质由性质由性质由性质4 4，X*，Y*Y*是最优解。是最优解。是最优解。是最优解。充分性：充分性：充分性：充分性：若若若若X*，Y*Y*分别是原问题和对偶问题的最分别是原问题和对偶问题的最分别是原问题和对偶问题的最分别是原问题和对偶问题的最优解，因优解，因优解，因优解，因 CX
24、*Y*Y*AX*AX*Y*b，CX*=Y*bCX*=Y*b，故故故故Y*XY*Xs s=Y Ys sX X*=0*=0。7 7 对偶松弛性对偶松弛性对偶松弛性对偶松弛性2 2：若原问题有最优解，则最终表中松弛：若原问题有最优解，则最终表中松弛：若原问题有最优解，则最终表中松弛：若原问题有最优解，则最终表中松弛变量检验数的相反数为对偶问题的最优解；其它变量变量检验数的相反数为对偶问题的最优解；其它变量变量检验数的相反数为对偶问题的最优解；其它变量变量检验数的相反数为对偶问题的最优解；其它变量检验数的相反数为对偶松弛变量的值。检验数的相反数为对偶松弛变量的值。检验数的相反数为对偶松弛变量的值。检验
25、数的相反数为对偶松弛变量的值。证明：因为证明：因为证明：因为证明：因为Y*=Y*=C CB BB B-1-1 ，s s=0-C=0-CB BB B-1-1 I Is s=-=-Y*Y*.-.-s s=Y*Y*.=C-CC-CB BB B-1-1 A=C-YA,YA+A=C-YA,YA+=C,YA-(-)=C,=C,YA-(-)=C,故故故故-=Y Ys s 例例例例4 4：已知线性规划问题：已知线性规划问题：已知线性规划问题：已知线性规划问题：试用对偶理论证明此线性规划问题无最优解。试用对偶理论证明此线性规划问题无最优解。试用对偶理论证明此线性规划问题无最优解。试用对偶理论证明此线性规划问题无
26、最优解。解：对偶问题为：解：对偶问题为：解：对偶问题为：解：对偶问题为：因为（因为（因为（因为（0 0，0 0，0 0）为线性规划问题的可行解。而对偶）为线性规划问题的可行解。而对偶）为线性规划问题的可行解。而对偶）为线性规划问题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题问题无可行解，则原问题为无界解或无可行解，故原问题问题无可行解，则原问题为无界解或无可行解，故原问题问题无可行解，则原问题为无界解或无可行解，故原问题无最优解。无最优解。无最优解。无最优解。例例例例5 5：线性规划问题最优解为：线性规划问题最优解为：线性规划问题最优解为：线性规划问题最优解为用对偶问题求
27、原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。解：标准型为：解：标准型为：解：标准型为：解：标准型为：对偶问题为：对偶问题为：对偶问题为：对偶问题为：标准型为：标准型为：标准型为：标准型为：代入原问题标准型有：代入原问题标准型有：代入原问题标准型有：代入原问题标准型有：2.4对偶最优解的经济解释对偶最优解的经济解释影子价格影子价格 影子价格表示最优目标值随相应资源数量变影子价格表示最优目标值随相应资源数量变化的变化率。化的变化率。若若x x*,y,y*分别为（分别为（LPLP）和（和（DPDP）的最优解，的最优解，那么，那么，cxcx*=y
28、=y*b b。根据根据 w=w=y y*b=bb=b1 1y y1 1*+b+b2 2y y2 2*+b bm my ym m*可知可知 w/w/b bi i=y yi i*y yi i*表示表示 b bi i 变化变化1 1个单位对目标个单位对目标 w w 产生的影响，产生的影响，称称 y yi i*为为 b bi i的影子价格。的影子价格。注意：若注意：若 B B 是最优基，是最优基，y y*=C=CB BB B-1-1 为影子为影子价格向量。价格向量。1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）剩余的资源（吨）消耗的资源（吨）单位
29、产品消耗的资源（吨/件）2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w w1 1、w w2 2、.、w wmm称为称为称为称为mm种资源的种资源的种资源的种资源的影子价格（影子价格（影子价格（影子价格（ShadowPriceShadowPrice）3 3、资源影子价格的性质资源影子价格的性质资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资
30、源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于价格一定等于价格一定等于0(0(因为因为因为因为Y*XY*XS S=0)=0)影子价格代表影子价格代表影子价格代表影子价格代表 对这种资源的一个估价。当某种资源的市对这种资源的一个估价。当
31、某种资源的市对这种资源的一个估价。当某种资源的市对这种资源的一个估价。当某种资源的市场价低于影子价格时，应买进这种资源；否则，应卖出这场价低于影子价格时，应买进这种资源；否则，应卖出这场价低于影子价格时，应买进这种资源；否则，应卖出这场价低于影子价格时，应买进这种资源；否则，应卖出这种资源。种资源。种资源。种资源。2.6对偶单纯形法对偶单纯形法单纯形法：始终保持原问题的可行性，单纯形法：始终保持原问题的可行性，b0,=C-CBB-A(C-YA)由正变负，得到原问题和对由正变负，得到原问题和对偶问题的最优解。偶问题的最优解。对偶单纯形法：始终保持对偶问题的可行性，对偶单纯形法：始终保持对偶问题的
32、可行性，YAC（C-YA=C-CBB-1 A 0）即即=C-CBB-1 A 0，原问题可以从非可行解开始，逐原问题可以从非可行解开始，逐步迭代到基可行解。步迭代到基可行解。无须加人工变量无须加人工变量 LP:MAXZ=CX LP:MAXZ=CX AX AX=b Xb XB B=B B-1-1 b b X 0 X 0对偶单纯形法步骤对偶单纯形法步骤对偶单纯形法步骤对偶单纯形法步骤:(1)(1)找一个基，列出初始单纯形表，检验找一个基，列出初始单纯形表，检验找一个基，列出初始单纯形表，检验找一个基，列出初始单纯形表，检验b b列，若列，若列，若列，若b 0b 0，=C-C-CBBCBB-1-1 A
33、 A 00，则得到最优解，则得到最优解，则得到最优解，则得到最优解，stop nor next.stop nor next.(2)(2)确定换出变量：按确定换出变量：按确定换出变量：按确定换出变量：按min(Bmin(B-1-1 b)b)i i|(B|(B-1-1 b)b)i i 0=B 0=B-1-1 b b l l.x.xl l为换出变量。为换出变量。为换出变量。为换出变量。(3)(3)确定换入变量：检验确定换入变量：检验确定换入变量：检验确定换入变量：检验（4 4）以）以）以）以x xlklk为主元素进行行的初等变换，重复（为主元素进行行的初等变换，重复（为主元素进行行的初等变换，重复（
34、为主元素进行行的初等变换，重复（1 1）-（4 4）。）。）。）。例：用对偶单纯形法求解例：用对偶单纯形法求解变标准型为：变标准型为：对偶单纯形法法如下：对偶单纯形法法如下：得得原问题最优解为：原问题最优解为：得对偶问题最优解为：得对偶问题最优解为：解：变标准型解：变标准型例：用对偶单纯形法求解例：用对偶单纯形法求解无最优解。无最优解。maxZ=CX AXAX =b=b X 02.6灵敏度分析灵敏度分析为什么进行灵敏度分析？为什么进行灵敏度分析？（1）研究）研究A,C,b变化时，最优解的变化；变化时，最优解的变化；（2）研究）研究A,C,b在什么范围变化，最优解不在什么范围变化，最优解不变。变
35、。灵敏度分析的两把尺子：灵敏度分析的两把尺子：j j=C Cj j-C-CB BB B-1-1pj j 0；xB B=B B-1-1b 0一一.资源变化的灵敏度分析资源变化的灵敏度分析例例例例1:1:线性规划问题：线性规划问题：线性规划问题：线性规划问题：maxS=2x1+3x2s.t.x1+2x2=84x1=164x2=0初始单纯性表初始单纯性表TAB(1)为：为：最终单纯性表最终单纯性表TAB(1)为：为：例例例例1 1中中中中,若该厂又从别处抽出若该厂又从别处抽出若该厂又从别处抽出若该厂又从别处抽出4 4台时用于生产这两种产台时用于生产这两种产台时用于生产这两种产台时用于生产这两种产品产
36、品品产品品产品品产品,求这时的最优方案求这时的最优方案求这时的最优方案求这时的最优方案.代入最终表得代入最终表得代入最终表得代入最终表得TAB(2)TAB(2)最优生产方案改为最优生产方案改为最优生产方案改为最优生产方案改为:x x1 1=4,x=4,x2 2=3,z*=42+33=17(=3,z*=42+33=17(元元元元).).二二.目标函数中价值系数变化的灵敏度分析目标函数中价值系数变化的灵敏度分析例：基变量例：基变量x2的系数的系数c2变化为变化为c2，在最优解在最优解不变条件下确定不变条件下确定c2变化范围。变化范围。从从上表中知上表中知:三三.技术系数变化的灵敏度分析技术系数变化
37、的灵敏度分析例例:分析在原计划中是否应该安排一种新产品分析在原计划中是否应该安排一种新产品,已知数据如上表已知数据如上表,问该厂是否应该生产问该厂是否应该生产,生生产多少产多少?解解（1）设生产产品设生产产品台，其技术系数向台，其技术系数向量量，的检验数为的检验数为说明安排生产说明安排生产是有利的。是有利的。（2）计算产品）计算产品在最终表中对应在最终表中对应的列向量的列向量将（将（1）、（）、（2）结果加入）结果加入P31页最终表中得：页最终表中得：（3）换入，换入，换出，得下表：换出，得下表：例：原工艺发生变化时，例如：产品例：原工艺发生变化时，例如：产品的工艺的工艺有了改进，其技术系数有
38、了改进，其技术系数，每件利润，每件利润为为4元，试分析对原最优计划有何影响。元，试分析对原最优计划有何影响。将将以上结果添入以上结果添入P32页最终表页最终表的列向量位的列向量位置。置。变为正规表为：变为正规表为：变为正规表为：变为正规表为：最优解为：最优解为：最优解为：最优解为：若遇到原问题与对偶问题都为非可行解时，则需要引入若遇到原问题与对偶问题都为非可行解时，则需要引入若遇到原问题与对偶问题都为非可行解时，则需要引入若遇到原问题与对偶问题都为非可行解时，则需要引入人工变量重新求解。人工变量重新求解。人工变量重新求解。人工变量重新求解。例：上例中产品例：上例中产品例：上例中产品例：上例中产
39、品的技术系数向量变为的技术系数向量变为的技术系数向量变为的技术系数向量变为，而每件获利仍为而每件获利仍为而每件获利仍为而每件获利仍为4 4元，问该厂应如何安排最优生产方案。元，问该厂应如何安排最优生产方案。元，问该厂应如何安排最优生产方案。元，问该厂应如何安排最优生产方案。解：解：解：解：将将将将以上结果添入以上结果添入以上结果添入以上结果添入P32P32页最终表页最终表页最终表页最终表的列向量位置。的列向量位置。的列向量位置。的列向量位置。变为正规表为：变为正规表为：变为正规表为：变为正规表为：原问题与对偶问题都为非可行解，引入人工变量原问题与对偶问题都为非可行解，引入人工变量原问题与对偶问
40、题都为非可行解，引入人工变量原问题与对偶问题都为非可行解，引入人工变量，第三，第三，第三，第三行用方程表示为：行用方程表示为：行用方程表示为：行用方程表示为：换入，换入，换入，换入，换出，得下表：换出，得下表：换出，得下表：换出，得下表：=x x1 1换入，换入，换入，换入，换出，得下表：换出，得下表：换出，得下表：换出，得下表：例：某厂生产例：某厂生产例：某厂生产例：某厂生产AA、BB、CC三种产品，其所需劳动力、材料三种产品，其所需劳动力、材料三种产品，其所需劳动力、材料三种产品，其所需劳动力、材料等有关数据见下表。等有关数据见下表。等有关数据见下表。等有关数据见下表。要求：要求：要求：要
41、求：（1 1）确定获利最大的产品计划；确定获利最大的产品计划；确定获利最大的产品计划；确定获利最大的产品计划；（2 2）写出其对偶问题的最优解写出其对偶问题的最优解写出其对偶问题的最优解写出其对偶问题的最优解;（3 3）产品产品产品产品AA的利润在什么范围内变动时的利润在什么范围内变动时的利润在什么范围内变动时的利润在什么范围内变动时,上述最优计划上述最优计划上述最优计划上述最优计划不变不变不变不变.产品产品产品产品ABCABC 可用量（单位）可用量（单位）可用量（单位）可用量（单位）劳动力劳动力劳动力劳动力6354563545 材材材材 料料料料3453034530产品利润产品利润产品利润产品利润314314 解:其数学模型为变标准型为:3 1 4 0 0 CB XB b 0 45 6 3 5 1 0 0 30 3 4 5 0 1 3 1 4 0 0 0 15 3 -1 0 1 -1 4 6 3/5 4/5 1 0 1/5 3/5 -11/5 0 0 -4/5 3 5 1 -1/3 0 1/3 -1/3 4 3 0 0 1 -1/5 2/5 0 -2 0 -1/5 -3/5最优解X*=(5,0,3,0,0)T,Z*=27(2)对偶问题最优解为Y*=(-1/5,3/5)(3)产品A利润改变为 ,则