第03章对偶问题与灵敏度分析

1、1第第3 3章章 对偶问题与灵敏度分析对偶问题与灵敏度分析3-1 3-1 线性规划的对偶问题概念线性规划的对偶问题概念3-2 3-2 建立对偶问题的规则建立对偶问题的规则3-3 3-3 对偶基本理论或性质对偶基本理论或性质3-4 3-4 线性规划解法之三：线性规划解法之三： 对偶单纯形法对偶单纯形法3-5 3-5 线性规划的灵敏度分析线性规划的灵敏度分析23-1 3-1 线性规划的对偶问题概念线性规划的对偶问题概念一、营养配置问题举例一、营养配置问题举例例例1 某养鸡场所用的饲料由某养鸡场所用的饲料由A、B、C三种配料组成，三种配料组成，下表给出了各种配料所含的营养成份、单位成本以下表给出了各

2、种配料所含的营养成份、单位成本以及及l份混合词料必须含有的各种营养成份。份混合词料必须含有的各种营养成份。3(1)问如何配制混合词料使成本最小？问如何配制混合词料使成本最小？(2)若有一个饲料厂制造含有这三种营养成分的营若有一个饲料厂制造含有这三种营养成分的营养养饲饲料，在料，在1份混合饲料中三种营养丸的价格如何份混合饲料中三种营养丸的价格如何制定才使其售价最大？制定才使其售价最大？4解解:(1)设设xj表示一份混合饲料中第表示一份混合饲料中第j种配料的含量，种配料的含量， j=A，B，C。则。则 min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/

3、2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0求解结果为：求解结果为：5 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400表中所有检验数均不小于表中所有检验数均不小于0，已达到最优已达到最优 最优解为最优解为X=(0,4,16,0,0,10)T Zmin=216+34=446(2)若有一个饲料厂制造含有这三种营养成分为若有一个饲料厂制造含有这三种营养成分为1个单个单位的营养丸，在位的营养丸，在1份混合饲料中三种营养丸的价格如份混合饲料中三种营养

4、丸的价格如何制定才使其售价最大？何制定才使其售价最大？解：解：(2)设设qi表示一份混合饲料中第表示一份混合饲料中第I种营养丸的价格，种营养丸的价格，i=D,E,F,则则max Z=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 6 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 0求解结果为：求解结果为：7 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-16表中所有检验数均不大于表中所有检验数均不

5、大于0，已达到最优已达到最优 最优解为最优解为q=(0,4,16,0,0,10)T Zmax=64+201=448LP1与与LP2的关系：的关系：min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0 max w=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 20 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 09 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100

6、-1013x241101-40 zj cj zj333020-11-4400 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-1610关系：关系：两个两个LP问题的最优解的目标函数值相同问题的最优解的目标函数值相同用单纯形法求解一个用单纯形法求解一个LP问题就知道另一问题就知道另一个问题的解个问题的解二、对偶问题的概念及实质二、对偶问题的概念及实质1.对每一个对每一个LP问题所伴随着的另一个问题所伴随着的另一个LP问问题，就称为对偶问题；原来的题，就称为对偶问题；原

7、来的LP问题就称问题就称为原问题为原问题2.实质：实质：对偶问题实质上也是一个对偶问题实质上也是一个LP问题问题11 3-2 3-2 建立对偶问题的规则建立对偶问题的规则一、建立对偶问题的规则一、建立对偶问题的规则 (LP) Max z = c x (DP) Min w = bTq s.t. Ax b s.t. AT q cT x 0 q 0 “Max - ” “Min- ”121.注意原问题与对偶问题的决策变量的表示方式：注意原问题与对偶问题的决策变量的表示方式：Xj,qi分别表示原问题、对偶问题的决策变量分别表示原问题、对偶问题的决策变量2.将问题变换为统一形式，其中将问题变换为统一形式，

8、其中b可以为负数可以为负数原问题原问题“max ”对偶问题对偶问题“min ”原问题原问题“min ” 对偶问题对偶问题“max ”对偶问题建立的规则；请同学们抄写下来对偶问题建立的规则；请同学们抄写下来1，原问题目标函数求最大，原问题目标函数求最大或者最小或者最小，则所有的约束条件符号，则所有的约束条件符号统一成小于或者等于统一成小于或者等于大于或者等于大于或者等于2，原问题一个行约束对应对偶问题的一个变量，如果行约束为，原问题一个行约束对应对偶问题的一个变量，如果行约束为不等式，这个变量就大于等于零不等式，这个变量就大于等于零否则就没有限制否则就没有限制为自由变量为自由变量3，原问题每个变

9、量的列向量对应对偶问题的一个行约束，如果，原问题每个变量的列向量对应对偶问题的一个行约束，如果原问题的变量大于等于零，则行约束小于等于零如果原问题的原问题的变量大于等于零，则行约束小于等于零如果原问题的变量没有限制，则行约束为等号。变量没有限制，则行约束为等号。4原问题目标函数与对偶问题目标函数相反。原问题目标函数与对偶问题目标函数相反。136.对偶问题的约束条件方程的右端值是原问题目标对偶问题的约束条件方程的右端值是原问题目标函数中决策变量的系数函数中决策变量的系数Cj；7.原问题与对偶问题的关系原问题与对偶问题的关系 xjqix1X2xn原始约束原始约束Min wq1a11a12a1nb1

10、q2a21a22a2nb2qmam1am2amnbm对偶约束对偶约束max zC1C2Cn14二、原问题不符合建立规则的处理二、原问题不符合建立规则的处理1.原问题为原问题为“max ”形式形式原问题为原问题为“max ”形式形式约束条件方程约束条件方程两端乘以两端乘以-12.原问题为原问题为“min ”形式形式原问题为原问题为“min ”形式形式约束条件方程约束条件方程两端乘以两端乘以-13.原问题的每一个约束条件方程对应对偶问题的一原问题的每一个约束条件方程对应对偶问题的一个决策变量个决策变量qi若第若第i个约束条件为不等式个约束条件为不等式,则限定则限定qi0若约束条件方程是若约束条件方

11、程是“=”形式形式:将将“=”变为变为“”和和“”两个约束条件方程两个约束条件方程,在按照在按照1、2条处理条处理15例例2：根据下表写出原问题：根据下表写出原问题(max)与对偶问题与对偶问题(min)的的表达式表达式 xjqix1X2bq1128q24016qm0412Cj2316(1) min Z=2X1十十4X2十十3X3 s.t. X1十十2X23X3 5 2X1 3X2 2X33 X1十十X2十十X3 =2 X1，X2，X3 0(2) max Z=X1十十2X2十十3X3十十4X4 s.t. X1十十X2X3 3X4 =5 6X1十十7X2十十3X35X4 812X1 9X2 9X

12、3十十9X420 X1，X2，X3 ，X40例例3：建立下列：建立下列LP 问题的对偶问题问题的对偶问题17(3)没有非负限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ183-3 3-3 对偶基本理论或性质对偶基本理论或性质一、对称性一、对称性对偶问题的对偶是原问题对偶问题的对偶是原问题二、二、弱对偶性弱对偶性若若 x, q x, q 分别为（分别为（LP) LP) 和（和（DPDP）的可行）的可行解，那么解，那么cx bcx bT Tq q推论推论三、三、最优性准则定理最优性准则定理若若x x, ,q q分别

13、分别(LP),(DP)(LP),(DP)的可行解的可行解, ,且且cxcx= =b bT Tq q，那么那么x x, ,y y分别为分别为(LP)(LP)和和(DP)(DP)的最优解的最优解19四、对偶定理四、对偶定理若若(LP)(LP)和和(DP)(DP)均可行均可行 那么那么(LP)(LP)和和(DP)(DP)均有最优解均有最优解, ,且最优值相等且最优值相等五、从一个问题的最优解单纯形表中可五、从一个问题的最优解单纯形表中可以得到另一个问题的最优解以得到另一个问题的最优解从从(LP)(LP)的最优解单纯形表中找的最优解单纯形表中找(DP)(DP)的最优解：的最优解：q qi i=|Z=|

14、Zn+in+i| n| n为为(LP)(LP)的实际决策变量数的实际决策变量数从从(DP)(DP)的最优解单纯形表中找的最优解单纯形表中找 (LP)(LP)的最优的最优解：解：X Xj j=|Z=|Zm+im+i| m| m为为(LP)(LP)的约束条件方程个数的约束条件方程个数六、互补松弛性六、互补松弛性若若X,qX,q分别是分别是(LP)(LP)和和(DP)(DP)的可行解，那么的可行解，那么qXqXs s=0=0和和q qs sX=0X=0，当且仅当，当且仅当X,qX,q为最优解为最优解20例例4 4：已知：已知LPLP问题问题max Z=xmax Z=x1 1+x+x2 2s.t. x

15、s.t. x1 1+x+x2 2+x+x3 322-2x-2x1 1+x+x2 2-x-x3 31 1 x x1 1,x,x2 2,x,x3 300试用对偶理论证明试用对偶理论证明上述上述LPLP问题无最优问题无最优解解例例5 5：已知：已知LPLP问题问题min Z=2xmin Z=2x1 1+3x+3x2 2 +5x+5x3 3+2x+2x4 4 +3x+3x5 5s.t. xs.t. x1 1+x+x2 2+2x+2x3 3 +x+x4 4 +3x+3x5 5 44 2x 2x1 1-x-x2 2+3x+3x3 3 +x+x4 4 +x+x5 5 3 3 x x1 1,x,x2 2,x,

16、x3 3 ,x,x4 4 ,x,x5 500已知其对偶问题的最优解为已知其对偶问题的最优解为q q1 1=4/5;q=4/5;q2 2=3/5;z=5.=3/5;z=5.试用对偶试用对偶理论找出原问题的最优解理论找出原问题的最优解21解：先写出其对偶问题：解：先写出其对偶问题： max w=4q1+3q2 q1+2q22 (1) q1 -q23 (2)2q1+3q25 (3) q1 +q22 (4)3q1 +q23 (5)将将q1,q2的值代入约束条的值代入约束条件，得件，得(2),(3),(4)为严格不为严格不等式；由互补松弛性等式；由互补松弛性qsx=0得得x2=0,x3=0,x4=0。又

17、因为又因为q1,q20，由互补松弛，由互补松弛性性qxs=0得得xs1=0 ,xs2=0,j即原问即原问题的两个约束条件应取等式，题的两个约束条件应取等式，故有故有 x x1 1 +3x+3x5 5 =4=4 2x 2x1 1 +x+x5 5 =3=3求解得求解得x x1 1=1.x=1.x2 2=1=1故原问题的最优解为故原问题的最优解为X=(1,0,0,0,1)X=(1,0,0,0,1)T TZ Zminmin=5=522例例6 6：已知某：已知某LPLP问题的最优单纯形表如下，试问题的最优单纯形表如下，试分别写出其原问题和对偶问题的最优解分别写出其原问题和对偶问题的最优解 cj63200

18、0cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400对偶问题的用途对偶问题的用途减少计算工作量：如判断减少计算工作量：如判断LP问题有无最优解问题有无最优解对求对求“min ”时，可转换为对偶问题易求解时，可转换为对偶问题易求解233-4 3-4 线性规划解法之三：线性规划解法之三：对偶单纯形法对偶单纯形法一、对偶单纯形法的基本思想一、对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行，从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以

19、也但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发可以说是从一个对偶可行解出发然后检验原规划的基本解是否可行，即是否有负的然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数基本解，此基本解对应着另一个对偶可行解（检验数非正）非正）如果得到的基本解的分量皆非负，则该基本解为最如果得到的基本解的分量皆非负，则该基本解为最优解。也就是说，优解。也就是说，对偶单纯形法在迭代过程中始终保对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正）

20、，使原规划的基持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解原规划的可行解时，便得到原规划的最优解24二、对偶单纯形法求解线性规划问题过程二、对偶单纯形法求解线性规划问题过程1.1.建立初始对偶单纯形表建立初始对偶单纯形表, ,对应一个基本解对应一个基本解, ,所有检验数均非正所有检验数均非正, ,转转2 2；2.2.若若b b0,0,则得到最优解则得到最优解, ,停止停止; ;否则否则, ,若有若有b bk k00则选则选minminb bk k| |b bk k

21、00的的k k行的基变量为换出变行的基变量为换出变量量, ,转转3 33.3.若所有若所有a akjkj0( 0( j j = 1,2, = 1,2,n n ) )，则原问，则原问题无可行解题无可行解, ,停止停止; ;否则否则, ,若有若有a akjkj0 0 则选则选minmin j j / / a akjkja akjkj00= r r/a akrkr那么选那么选x xr r为换入基变量为换入基变量, ,转转4 4；4.4.以以a akrkr进行转轴运算进行转轴运算, ,作矩阵行变换使其变作矩阵行变换使其变为为1,1,该列其他元素变为该列其他元素变为0,0,转转2 225例例7 7：用对

22、偶单纯形法求解下列：用对偶单纯形法求解下列LPLP问题问题 min Z=6X1十十3X2十十2X3 s.t. X1十十X2十十X3 20 1/2X1十十1/2X2十十1/4X3 6 2X1十十X2十十X3 10 X1，X2，X3 026解法一解法一: :将将LPLP问题化为问题化为 max Z= 6X1 3X2 2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,0 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4-20-1-1-11

23、000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-200000027 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-2000000-2x320111-1000 x5(-1)-1/4-1/4*0-1/4100 x610-100-101 zj cj zj-2-4-2-1-202-20000-2x316001-240-3x241101-400 x610-100-101 zj cj zj

24、-3-3-30-201-14-40028表中所有检验数均不大于表中所有检验数均不大于0，且，且bi0已达到最优已达到最优 最优解为最优解为X=(0,4,16,0,0,10)T , Zmax=64+201=44Zmin= Zmax=44解法二解法二: :将将LPLP问题化为问题化为 min Z= 6X1十十3X2十十2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,029 cj632000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-

25、1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj zj cj0-60-30-2000000例例8:用对偶单纯形法求解下列用对偶单纯形法求解下列LP问题问题min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3 6 X1 X3 4 X2X3 3 X1，X2，X3 030解解:化为化为 min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3十十X4 =6 X1 十十X3 十十X5 =-4 X2 十十X3 十十X6 =-3 X1，X2，X3 , X4 , X5 , X6 0 cj321000cBXBbx1x2x3x4x5x60 x

26、461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-100000031 cj321000cBXBbx1x2x3x4x5x60 x461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-10000000 x420121103x1410-10-100 x6(-3)0-1*1001 zj zj cj300-2-3-400-3-3000 x4(-1)0011113x1410-10-100 x6301-100-1 zj zj cj3020-5-600-3-3-2-232表中所有检验数均不大于表中所

27、有检验数均不大于0,但但x4变量行的变量行的aij全为全为非负非负,故该问题无可行解故该问题无可行解三、三、对偶单纯形法的适用范围对偶单纯形法的适用范围1.1.应用前提：有一个基，其对应的基满足应用前提：有一个基，其对应的基满足: :单纯形表的检验数行全部非正（对偶可行）单纯形表的检验数行全部非正（对偶可行）变量取值可有负数（非可行解）变量取值可有负数（非可行解）注：通过矩阵行变换运算，使所有相应变量注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表取值均为非负数即得到最优单纯性表2.2.对偶单纯形法适合于解如下形式的线性规对偶单纯形法适合于解如下形式的线性规划问题划问题3

28、3njxmibxacxcZjnjijijnjjjj,2,1,0,2,10min11例例9 9：求解下列：求解下列LPLP问题问题max Z=X1十十X2s.t. 2X1十十X24 X1十十7X27 X1，X2034四、对偶单纯形法与单纯形法的比较四、对偶单纯形法与单纯形法的比较1.思路比较思路比较单纯形法是单纯形法是从一个基本可行解转到另一个更从一个基本可行解转到另一个更优的基本可行解，优的基本可行解，即跌代中始终保持原问题的即跌代中始终保持原问题的可行性：可行性：b0，检验数中大于检验数中大于0的逐步变为全部的逐步变为全部0为止为止对偶单纯形法是对偶单纯形法是保持满足最优检验判断，即保持满足

29、最优检验判断，即全部检验数全部检验数0，从一个基本解逐步跌代变为一从一个基本解逐步跌代变为一个基本可行解，即个基本可行解，即b0为止为止2.计算步骤的关系计算步骤的关系35是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以中心元素进行迭代以中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min36五、对偶单纯法的应用：增加约束条件五、对偶单纯法的应用：增加约束条件(一一)对偶单纯形法的用途对偶单纯形

30、法的用途1.对约束条件方程为对约束条件方程为“”型型,不必加人工变量用大不必加人工变量用大M法或两阶段法求解而采用对偶单纯形法求解更容易法或两阶段法求解而采用对偶单纯形法求解更容易2.增加一个约束条件方程后不必重新求解，只需在增加一个约束条件方程后不必重新求解，只需在最优解表上增加用对偶单纯形法求解即可最优解表上增加用对偶单纯形法求解即可(二二)LP问题新增约束条件的求解步骤问题新增约束条件的求解步骤1.检验原来的最优解是否满足新增加的约束条件：检验原来的最优解是否满足新增加的约束条件：若满足，则原最优解就是新问题的最优解若满足，则原最优解就是新问题的最优解若不满足，则进行下一步若不满足，则进

31、行下一步372.将新增约束条件加入松弛变量或多余变量后加到原将新增约束条件加入松弛变量或多余变量后加到原来最优单纯形表中，令来最优单纯形表中，令原基变量和新增的松弛变量或原基变量和新增的松弛变量或多余变量组成新基，并将基变量对应的系数矩阵变为多余变量组成新基，并将基变量对应的系数矩阵变为单位矩阵单位矩阵“”型约束条件方程加松弛变量变为型约束条件方程加松弛变量变为“”型约束型约束条件方程条件方程“”型约束条件方程减多余变量变为型约束条件方程减多余变量变为“”型约束型约束条件方程，然后等式方程两端乘以条件方程，然后等式方程两端乘以(-1)“=”型约束条件方程转化为型约束条件方程转化为“”和和“”，

32、然后将不满，然后将不满足的条件加进去足的条件加进去3.利用对偶单纯形法求最优解利用对偶单纯形法求最优解38例例10：已知：已知LP问题问题 Max z =40 xMax z =40 x1 1+45x+45x2 2 +24x +24x3 3 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3 100 100 3x 3x1 1+3x+3x2 2+2x+2x3 3 120 120 x x1 1 ,x,x2 2 ，x x3 300用单纯形法求解得最优单纯形表如下：用单纯形法求解得最优单纯形表如下： cj40452400cBXBBx1x2x3x4x545x22001-1/31-2/34

33、0 x120101-11 zj cj zj40045025-15-510-1039试求在增加一个约束条件试求在增加一个约束条件X115时新的最优解时新的最优解解解:(1)原最优解为原最优解为X1=20,X2=20,而新增约束而新增约束X115,所所以原最优解不满足新增约束条件以原最优解不满足新增约束条件(2) X115处理得处理得X1 X6=15， X60，从而得到新的，从而得到新的单纯形表并进行初等交换单纯形表并进行初等交换 cj404524000cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x61510000140 cj4045240

34、00cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x6-500-1*1-11 zj cj zj40045025-15-510-100045x265/30102/3-1/3-1/340 x11510000124x35001-11-1 zj cj zj4004502406-69-91-1表中所有检验数均不大于表中所有检验数均不大于0，且，且bi0已达到最优已达到最优 最优解为最优解为X=(15,65/3,5,0,0,0)T , Zmax=1695413-5 3-5 线性规划的灵敏度分析线性规划的灵敏度分析一、线性规划与参数规划一、线性规划与参

35、数规划1.1.线性规划：目标函数系数线性规划：目标函数系数C Cj j、约束条件方程、约束条件方程系数系数a aijij、约束条件方程右端值、约束条件方程右端值b bi i均固定均固定2.2.参数规划：参数规划：C Cj j、a aijij、b bi i不固定不固定使得最优解或最优基不变的使得最优解或最优基不变的C Cj j、a aijij、b bi i的变的变化范围的分析化范围的分析LPLP问题的灵敏度分析问题的灵敏度分析使得最优解或最优基变化的使得最优解或最优基变化的C Cj j、a aijij、b bi i的变的变化范围的分析化范围的分析参数线性规划参数线性规划42二、灵敏度分析的概念与

36、界定范围二、灵敏度分析的概念与界定范围1.概念：概念：某一参数发生变化时，目标函数发生怎样变某一参数发生变化时，目标函数发生怎样变化的分析化的分析2.界定范围：界定范围：“Max ”三、三、LP问题灵敏度分析的内容问题灵敏度分析的内容1.对对C Cj j值的灵敏度分析值的灵敏度分析2.对对b bi i值的灵敏度分析值的灵敏度分析对对3. a3. aijij值的灵敏度分析值的灵敏度分析* *4.4.增加或删去一个变量的分析增加或删去一个变量的分析5.5.增加或去掉一个约束条件的分析增加或去掉一个约束条件的分析43四、理解最优单纯性表中各元素的含义四、理解最优单纯性表中各元素的含义考虑问题考虑问题

37、 Max Max z z = = c c1 1 x x1 1 + + c c2 2 x x2 2 + + + + c cn n x xn n s.t. s.t. a a1111x x1 1 + + a a1212x x2 2 + + + + a a1n1nx xn n b b1 1 a a2121x x1 1 + + a a2222x x2 2 + + + + a a2n2nx xn n b b2 2 . . . . . . a am1m1x x1 1 + + a am2m2x x2 2 + + + + a amnmnx xn n b bm m x x1 1 ，x x2 2 ， ，x xn n

38、 0 0 引入引入 m m 个松弛变量后，通过计算得到个松弛变量后，通过计算得到最优单纯形表。最优单纯形表。 应能够找到最优基应能够找到最优基 B B 的的逆矩阵逆矩阵 B B-1-1 和检验数等和检验数等44五、价值系数五、价值系数cj的灵敏度分析的灵敏度分析1.1.对对cj的灵敏度分析的前提的灵敏度分析的前提 维持最优解维持最优解 不变：基变量及其取值不变不变：基变量及其取值不变cj的变化仍使单纯形表中的非基本量的检验数的变化仍使单纯形表中的非基本量的检验数 j = cj zj都保持不大于都保持不大于0 cj的变化仅影响的变化仅影响zj和检验数和检验数 j = cj zj2.2.对对cj的

39、灵敏度分析的灵敏度分析(1) (1) xj是非基变量时是非基变量时若若x xj j是非基变量时，是非基变量时， cj的变化仅影响的变化仅影响x xj j对应的检验对应的检验数数cj zjcj减少的范围：减少的范围： xj已经不在最优解内，已经不在最优解内， cj减少时减少时xj更不会在最优解范围内，所以更不会在最优解范围内，所以cj的变动下限为的变动下限为 45cj增加的范围：设在原最优单纯形表中，增加的范围：设在原最优单纯形表中， cj变为变为cj + cj ，则检验数为，则检验数为 j = cj + cj zjv若若cj + cj zj0成立，则目标不变；成立，则目标不变；v若若cj +

40、cj zj 0成立，则目标不变，但有多重解成立，则目标不变，但有多重解v若若cj + cj zj0成立，则目标发生变化成立，则目标发生变化cj + cj zj0 cj ( cj zj ),所以所以cj的变的变动上限为动上限为 ( cj zj ) 当当xj为非基变量时，为非基变量时， cj的变化范围为的变化范围为 cj ( cj zj )46例例11：已知下列：已知下列LP 问题：问题： MaxMax z =x z =x1 1+5x+5x2 2 +3x+3x3 3 +4x+4x4 4 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3+2x+2x4 4 800 800 5x 5

41、x1 1+4x+4x2 2+3x+3x3 3+4x+4x4 4 1200 1200 3x 3x1 1+4x+4x2 2+5x+5x3 3+3x+3x4 41000 1000 x x1 1 ,x,x2 2 ，x x3 3 ，x x4 400 其最优单纯形表如下，试分析其最优单纯形表如下，试分析c c1 1和和c c3 3的灵的灵敏度范围敏度范围47 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.754000

42、0.25-0.251-1解：由单纯形表可知解：由单纯形表可知(1) c1 ( c1 z1 )， c1 3.25 c1 4.25(2) c3 ( c3 z3 )， c3 2.75 c3 5.7548(2) (2) xj是基变量时是基变量时若若x xj j是基变量时，是基变量时， cj的变化影响的变化影响所有非基变量对应所有非基变量对应的的zj和检验数和检验数cj zjcj变化范围：变化范围：v设设xj为第为第r个约束条件方程对应的基变量，当个约束条件方程对应的基变量，当cj变为变为cj + cj ，则，则cB变为变为cB + cB其中其中 cB=(0,0,0, cj,0,0,0)v非基变量非基变

43、量xk检验数应满足：检验数应满足：ck (cB + cB)B-1Pk0ck cB B-1Pk cBB-1Pk0(ck zk ) cBB-1Pk0(ck zk )(0,0,0, cj,0,0,0) B-1Pk049(ck zk )(0,0,0, cj,0,0,0) B-1Pk0(ck zk )(0,0,0, cj,0,0,0) Pk0(ck zk ) cjark0 cjark ck zk 当当ark 0时，则时，则 cj（ck zk ）/ ark 当当ark 0时，则时，则 cj（ck zk ）/ ark 当当ark =0时，则时，则 cj的变化不影响的变化不影响zk结论：当结论：当xj为基变量

44、时为基变量时, cj的变化范围为的变化范围为(xj为第为第r个方程个方程)Max（ck zk ）/ ark | ark 0 cj minck zk ）/ ark | ark 050例例12：已知：已知LP 问题的问题的最优单纯形表如下，试分最优单纯形表如下，试分析析c c2 2和和c c4 4的灵敏度范围的灵敏度范围 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-151六

45、、资源数量六、资源数量bi的灵敏度分析的灵敏度分析1.1.对对bi的灵敏度分析的前提的灵敏度分析的前提 维持最优解基变量不变，但是其取值可变维持最优解基变量不变，但是其取值可变bi的变化仅影响基变量的取值的变化仅影响基变量的取值2.2.对对bi的灵敏度分析的灵敏度分析原最优解为原最优解为X XB B=B=B-1-1b,b,设设b bk k的变化量为的变化量为b bk k，则其他系，则其他系数不变时新解中基变量的取值为数不变时新解中基变量的取值为XXB B=B=B-1-1（b+ b+ b b）00，其中，其中b=b=（0 0，0 0，b bk k ，0 0，0 0）T TXXB B=B=B-1-

46、1（b+ b+ b b）= X= XB B=B=B-1-1b+ Bb+ B-1-1 b b =(b =(b1 1+ + b bk kaa1,n+k1,n+k, b, b2 2+ + b bk kaa2,n+k 2,n+k ,， bbm m+ + b bk kaam,n+k m,n+k ) )T T由此可得由此可得, , bbi i+ + b bk kaai,n+ki,n+k 0,I=1,2,m 0,I=1,2,m b bk kaai,n+ki,n+k bbi i,I=1,2,m,I=1,2,m52(1)当当aai,n+ki,n+k 0 0时，则时，则b bk k bbi i/ a/ ai,n+

47、ki,n+k (2)(2)当当aai,n+ki,n+k 0 0时，则时，则b bk k bbi i/ a/ ai,n+ki,n+k 3.3.当当XXB B=B=B-1-1（b+ b+ b b）00时，最优解基变时，最优解基变量不变，但最优解的取值发生变化，取值为量不变，但最优解的取值发生变化，取值为XXB B=B=B-1-1（b+ b+ b b）=B=B-1-1b+ Bb+ B-1-1 b b = X = XB B+ +b bk kPPn+kn+k4.4.当当XXB B=B=B-1-1（b+ b+ b b）00时，原最优解不时，原最优解不可行，用可行，用对偶单纯形法对偶单纯形法求新的最优解求新

48、的最优解53例例13：已知：已知LP 问题的问题的最优单纯形表如下，试分最优单纯形表如下，试分析析b b2 2和和b b3 3的灵敏度范围的灵敏度范围 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-154七、七、增加或删去一个变量的分析增加或删去一个变量的分析1.1.增加一个变量增加一个变量 设增加的变量为设增加的变量为x xn+1n+1, ,其价值系数为其价值系数为c

49、cn+1n+1 , ,系数列向系数列向量量P Pn+1n+1, ,则检验数为则检验数为n+1n+1=c=cn+1n+1-c-cB BB B-1-1P Pn+1n+1(1)(1)若若n+1n+1 0, 0,则原最优解不变则原最优解不变(2)(2)若若n+1n+1 0,0,则将则将x xn+1n+1引入基变量引入基变量, ,进行跌代进行跌代2.2.删去一个变量删去一个变量(1)(1)若若x xr r为非基变量，去掉为非基变量，去掉x xr r不影响最优解不影响最优解55(2)(2)若若x xr r为基变量，对最优解产生影响，其处理方法为：为基变量，对最优解产生影响，其处理方法为：取取x xr r为

50、换出变量，用对偶单纯形法求解为换出变量，用对偶单纯形法求解取取x xr r的价值系数的价值系数c cr r为为M M，用大，用大M M法计算法计算八、八、增加或去掉一个约束条件的分析增加或去掉一个约束条件的分析1.删去一个约束条件删去一个约束条件(1)对最优解没有影响：松弛变量、多余变量的对最优解没有影响：松弛变量、多余变量的取值都是大于取值都是大于0的约束条件称为松约束的约束条件称为松约束(2)对最优解有影响：松弛变量、多余变量的取对最优解有影响：松弛变量、多余变量的取值都是等于值都是等于0的约束条件称为紧约束的约束条件称为紧约束562.增加一个约束条件增加一个约束条件(1)若原最优解满足约

51、束条件，最优解不变若原最优解满足约束条件，最优解不变(2)若原最优解不满足约束条件，用对偶单纯形法求解若原最优解不满足约束条件，用对偶单纯形法求解例例14：已知下列：已知下列LP 问题问题 MaxMax z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1, ,x x2 2 , ,x x3 3, ,x x4 4, ,x x5 5 0 0其其最优单纯形表如

52、下最优单纯形表如下57 cj23000cBXBBx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80 zj cj zj20303/2-3/21/8-1/800试分析：试分析：(1)分析分析C2的灵敏度范围的灵敏度范围(2) 当第一个约束条件的当第一个约束条件的b b1 1 增加增加4 4时，对原最优解有影响吗？时，对原最优解有影响吗？若有，求出新的最优解若有，求出新的最优解(3)(3)增加增加x x6 6时时, , p p6 6=( 2, 6, 3 )=( 2, 6, 3 )T T, , c c6 6=5=5，对原最优解的影响对原最优解的影响 (4)(4)增加增加3 3x x1 1+ 2+ 2x x2 21515时对原最优解的影响时对原最优解的影响58解解: :(1)(1) -3 -3c c2 211(2)x = ( 4, 3, 2, 0, 0 )(2)x = ( 4, 3, 2, 0, 0 )T T Z Z* * = 17 =