运筹学第2章对偶理论

Chapter2对偶理论

(DualityTheory)单纯形法的矩阵描述对偶问题的提出线性规划的对偶理论对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析(选讲)掌握WinQSB软件求解对偶规划本章主要内容：√√√ 学习要点：

1.理解对偶理论，掌握描述一个线性规划问题的对偶问题。

2.能够运用对偶单纯形法来求解线性规划问题。

3.会用互补松弛条件来考虑一对对偶问题的界。

4.了解影子价格、灵敏度分析以及用WinQSB求解对偶规划问题。2.1

单纯形法的矩阵描述0.16-0.120102412x2-0.20.4001207x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3ɵx5x4x3x2x1B-1bCBXB每一列的含义？每个表中的B和B-1的查找？单纯形法的矩阵描述单纯形法的矩阵描述单纯形法的矩阵描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1N单纯形法的矩阵描述CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1

单纯形法的矩阵描述2.3对偶问题的提出

对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏。王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...

王老板李老板引例1对偶问题的提出王老板的家具生产模型：x1、

x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0对偶线性规划问题，记为（D）所得不得低于生产的获利（不吃亏原则）要使对方能够接受（竞争性原则）两个原则对偶问题的提出王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————对偶问题的提出Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y240

2y1+2y2+2y350甲乙资源量A1230B3260C0224单位获利4050引例2通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3对偶问题的提出根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格对偶问题的提出2.4线性规划的对偶理论Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t原问题（对偶问题）对偶问题（原问题）一、原问题与对偶问题的对应关系Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y30s.t（y1）

（y2）（y3）

（x1）

13040（x2）22250306024

minωmaxz

3个约束2个变量2个约束3个变量线性规划的对偶理论对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi

(i=1,2,…,m)称为对偶变量上述对偶问题称为对称型对偶问题原问题简记为(P)，对偶问题简记为(D)称问题(P)和(D)为一对对偶问题线性规划的对偶理论对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m)；2、使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；3、使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；5、改变约束问题不等号的方向，即将“≤”改为“≥”；6、原问题为“max”型，对偶问题为“min”型。线性规划的对偶理论原始问题MaxZ=CXs.t.AX≤b

X

≥0bAC≤Maxnm对偶问题MinW=Ybs.t. YA≥C Y≥0≥MinCATbnmY为行向量线性规划的对偶理论当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题例1线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。例2线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。例3线性规划的对偶理论上式已为对称型对偶问题，故可写出它的对偶规划令则上式化为线性规划的对偶理论对偶问题的非对称形式minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≥≤=≤unr≥≤≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用

表示原始问题约束条件的性质影响对偶问题变量的性质，用表示线性规划的对偶理论1原问题为“max”，对偶问题为“min”；2原问题中目标函数系数ci变为其对偶问题约束条件的右端常数；3原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；4原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；5原问题的变量个数n等于其对偶问题的约束条件个数n，原问题约束条件的个数m等于其对偶问题变量的个数m；6在求极大值的原问题中，“≤”，“≥”和“=”的约束条件分别对应其对偶变量“≥0”，“≤0”和“无符号限制”；7在求极大值的原问题中，变量“≥0”，“≤0”和“无符号限制”分别对应其对偶约束条件的“≥”，“≤”和“=”约束.混合型问题的对偶规则：线性规划的对偶理论原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=线性规划的对偶理论MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3402y1+2y2+2y350

y1,y2,y30s.tMaxW′=-30y1-60y2-24y3

y1+3y2+0y3–y4=402y1+2y2+2y3–y5=50y1,y2,y3,y4,y50s.t例4二、对偶问题的解线性规划的对偶理论MaxW′=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6=402y1+2y2+2y3–y5+

y7=50y1,y2,y3,y4,y50s.tcj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2σj3M-305M-602M-24-M-M00-90M线性规划的对偶理论cj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3σj4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2σj600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2σj00-9-15-15/2-M+30-M-15/2-975线性规划的对偶理论cj4050000B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2σj00-35/2-15/20975MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.t

x1+2x2+x3=303x1+2x2+x4=602x2+x5=24

x1–x50s.t线性规划的对偶理论线性规划的对偶理论原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。线性规划的对偶理论XBb原问题的变量原问题的松弛变量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原问题最优表对偶问题最优表MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.tMinW=30y1+60y2+24y3

y1+3y2+0y3402y1+2y2+2y350

y1,y2,y30s.t线性规划的对偶理论性质1对称性定理：对偶问题的对偶是原问题

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≤bX≥0三、对偶原理线性规划的对偶理论minz′=-

CXs.t.-AX≥-b X≥0maxw′=-Ybs.t.-YA≤-C

Y≥0minw=Ybs.t.YA≥C

Y≥0maxz=CXs.t.AX≤bX≥0对偶的定义对偶的定义简要证明：线性规划的对偶理论性质2弱对偶原理(弱对偶性)：设和分别是问题(P)和(D)的可行解，则必有推论1:

原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。证明：(1)当X和Y为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值线性规划的对偶理论推论2:

在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。若（P）为无界解，则（D）无可行解；若（D）为无界解，则（P）无可行解。线性规划的对偶理论推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。已知原问题(LP)，试估计它的目标函数值的界,并验证弱对偶定理.例5线性规划的对偶理论解：问题(LP)的对偶问题(DP)为(DP)线性规划的对偶理论由观察可知分别是原问题和对偶问题的可行解。，弱对偶定理成立。且由推论1知，对偶问题目标函数W的下界为10，原问题目标函数Z的上界为40。且原问题的目标函数值为对偶问题的目标函数值为故线性规划的对偶理论例：利用对偶性质判断下面问题有无最优解例6解：此问题的对偶问题为不能成立，因此对偶问题不可行。故由推论3知原问题无界。为可行解线性规划的对偶理论性质3最优性定理：如果是原问题的可行解，是其对偶问题的可行解，并且:则是原问题的最优解，是其对偶问题的最优解。线性规划的对偶理论性质4强(主)对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，则另一问题也无最优解。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。线性规划的对偶理论证明：当X*为原问题的一个最优解，B为相应的最优基，通过引入松弛变量Xs，将问题(P)转化为标准型令CCBCN0解基系数基变量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1bCXAC-CBB-1A说明Y*可行线性规划的对偶理论问题:（1）由性质4可知，对偶问题最优解的表达式Y*=?（2）求Y*是否有必要重新求解(D)?—不必。可以从原问题（P）的单纯形终表获得。CCBCN0解基系数基变量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1b线性规划的对偶理论性质5

互补松弛性：设X0和Y0分别是P问题和D问题的可行解，则它们分别是最优解的充要条件是：其中：Xs、Ys为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。紧约束与松约束线性规划的对偶理论一个约束称为紧约束，如果该约束在所有最优解上的值使左右取等号。

即我们把严格等式约束称为紧约束（或起作用约束）.不是紧约束的约束称为松约束。即把某一最优解处取严格不等式的约束称为松约束（或不起作用约束）。对于最优解X*和Y*而言，松约束的对偶约束是紧约束.以上关系称为对偶问题的互补松弛关系或松紧关系。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解.紧约束与松约束松紧关系非常重要线性规划的对偶理论证:(必要性）原问题对偶问题线性规划的对偶理论MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.YA-YS=C W,WS≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数线性规划的对偶理论

y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0

(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0线性规划的对偶理论性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：

若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。线性规划的对偶理论已知线性规划的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。解：写出原问题的对偶问题，即标准化例7线性规划的对偶理论设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和Y＊满足：即：因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y＊=(1,1)，最优值w=26。线性规划的对偶理论已知线性规划的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。解:对偶问题是标准化例8线性规划的对偶理论设原问题最优解为X＊＝(x1，x2，x3)T,由互补松弛性定理知，X＊和Y＊满足：将Y＊带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为X＊=(-5,0,-1)，最优值z=-12线性规划的对偶理论试用对偶原理求解线性规划问题已知其对偶规划的最优解为练习线性规划的对偶理论解：该问题的对偶规划为线性规划的对偶理论利用松紧关系，代入对偶规划的约束条件得下列约束是松约束，将最优解松约束紧约束其对偶约束是紧约束线性规划的对偶理论设原问题的最优解为紧约束线性规划的对偶理论对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。对偶问题解的求法线性规划的对偶理论原问题与对偶问题解的对应关系小结对应关系原问题最优解无界解无可行解对偶问题最优解(Y,Y)(N,N)————无界解————(Y,Y)无可行解——(Y,Y)无法判断线性规划的对偶理论思考题判断下列结论是否正确，如果不正确，应该怎样改正？1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.线性规划的对偶理论2.5

影子价格单位产品消耗的资源(吨/件))原始问题是利润最大化的生产计划问题总利润(元)产品产量(件)单位产品的利润(元/件)消耗的资源(吨)剩余的资源(吨)资源限量(吨)影子价格对偶问题——资源定价问题对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润Maxz=Minw总利润(元)资源限量(吨)资源价格(元/吨)影子价格在一对P和D中，若P的某个约束条件的右端项常数bi

（第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z*的改变量称为第

i种资源的影子价格，其值等于D问题中对偶变量yi*。由对偶问题得基本性质可得：1.影子价格的数学分析：影子价格2.影子价格的经济意义1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi就是第

i种资源的影子价格。即：

影子价格影子价格是针对某一具体约束条件而言,因此影子价格可理解为目标函数最优值对资源的一阶偏导数资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0影子价格0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。若第i种资源的单位市场价格为mi

，则有当yi*>mi

时，企业愿意购进这种资源，单位纯利为yi*－mi

，则有利可图；当yi*<mi

时，企业有偿转让这种资源，可获单位纯利mi－yi

*

，否则，企业无利可图，甚至亏损。结论：若yi*>mi

则购进资源i，可获单位纯利yi*－mi

；

若yi*<mi则转让资源i，可获单位纯利mi－yi。影子价格y1y2ym产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源影子价格机会成本利润差额成本产品的差额成本（ReducedCost）差额成本=机会成本-利润影子价格3）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理:Y*Xs=0,YsX*=0表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。影子价格yixn+i=0如果yi>0，则xn+i=0如果xn+i>0，则yi=0影子价格大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果ym+j>0，则xj=0如果xj>0，则ym+j=0最优生产计划条件下有剩余的资源，其影子价格等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）互补松弛关系经济解释影子价格4）影子价格对单纯形表计算的解释单纯形表中的检验数其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。影子价格2.6

对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。对偶单纯形法原理对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得最优解。对偶单纯形法找出一个DP的可行基LP是否可行（XB≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束对偶单纯形法先回顾一下单纯形算法：

它是从线性规划的一个基可行解迭代到另一个基可行解的过程，在迭代过程中，保持基解的可行性，逐步消除基解的检验数的非负性，即为了求解线性规划，我们也可以从线性规划的一个基解迭代到另一个基解，在迭代过程中，保持基解的检验数的非正性，逐步消除基解的不可行性，即对偶单纯形法

如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件则称X为原问题(P)的一个正则解。求解原问题(P)时，可以从(P)的一个正则解开始，迭代到另一个正则解，使目标函数值增加，当迭代到正则解满足原始可行性条件(即xi≥0)时，就找到了原问题(P)的最优解。

这一方法称为对偶单纯形法对偶单纯形法定义原始单纯形法对偶单纯形法前提条件所有bi≥0所有检验数≤0最优性检验所有检验数≤0？所有bi≥0？换入、出基变量的确定先确定换入基变量后确定换出基变量先确定换出基变量后确定换入基变量原始基本解的进化可行→最优（对偶问题的解从不可行到可行）非可行→可行（最优）（原问题的解从不可行到可行）对偶单纯形法原问题解空间对偶问题解空间可行解可行解基本解基本解正则解正则解基可行解基可行解最优解对偶单纯形法对偶单纯法的迭代步骤：（1）找一个正则基B和初始正则解X(0)，将问题（P）化为关于基B的典式，列初始对偶单纯形表.设正则解的典式为：对偶单纯形法将上面的典式转换成前面所学习过的单纯形表：（2）若,则迭代停止，已求得原问题（P）的最优解;否则转下一步。对偶单纯形法则迭代停止，原问题无解；否则转下一步。为换出变量。若（3）确定换出变量：若则取相应的变量对偶单纯形法（4）确定换入变量：若则取xl

为换入变量。以正则解，返回（2）。为主元进行换基运算得到新的对偶单纯形法用对偶单纯形法计算解：为了便于寻找初始正则解，将问题变形为：取{x4,x5}为初始正则解，列单纯形表如下：例9对偶单纯形法-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4由于初始正则解有负分量，于是取min{-3,-4}=-4x5为换出变量，取x1为换入变量，得新基{x4,x1}，51=-2为主元对偶单纯形法基变换的过程：主元变为1，即用-2去除单纯形表中基变量x5所在的行；主元所在列的其它元变为0，消去非基变量x1所在的列的其余元-1，-2；得新基{x4,x1}的单纯形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4对偶单纯形法基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1对偶单纯形法-2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可见正则解的有负分量，由于x4=1,所以取x4为换出变量，取x2为换入变量，得新基{x2,x1}，42=-5/2为主元对偶单纯形法-2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此时正则解是可行解，也是最优解。X*=(11/5，2/5，0，0，0)；z*=-28/5进行基变换，得新正则解的单纯形表：对偶单纯形法例10cjB-1b-120-5000cByBy1y2y3y40y3-50-4-2100y4-30-3-101σj0-120-5000θ-120/-4-50/-2-50y22521-1/200y4-5-10-1/21σj-1250-200-250θ2050-50y21501-3/22-120y15101/2-1σj-135000-15-20例11cjB-1b23-5-M0θcBxBx1x2x3x4x5-Mx471111070x5-10-25-101σj-7MM+2M+3M-500θ3x27111100x5-45-70-6-51σj21-10-7-M-30θ1/77/6(M+3)/53x24/7011/72/71/72x145/7106/75/7-1/7σj102/700-50/7-(M+16)/7-1/7例12cj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x41-2110011110x54-1-2010-3-Mx6-20100111σj-6M+3-1M-1000-Mcj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x43-2010-1100x50-10012-1-1x3-2010011σj1-1000-M+1-1cj3-1-100-MB-1bθcBxBx1x2x3x4x5x63x11001/3-2/3-5/34-1x20100-1-21-1x30012/3-4/3-7/39σj000-1/3-1/3-M+2/32cj3-1-100-MB-1bθcBxBx1x2x3x4x5x60x43001-2-512-1x20100-1-21-1x3-2010011σj1000-1-M-1-2对偶单纯形法的迭代步骤中,如何找一个初始正则解？初始正则解的确定标准形线性规划问题选定的基B，不妨设对偶单纯形法可行基B的典式为右端常数中有负数，而检验数全非正，则基B为正则基，相应的解为初始正则解，就可用对偶单纯形法求解。否则，若出现正检验数，X(0)就不是正则解。为此，求初始正则基和初始正则解，可增加一个约束条件：原问题(P)的典式扩充为下列问题