第三章 对偶理论
§1 对偶问题的提出回顾对第一章§1例3营养问题
食物营养成分
x1 x2 xn
1 2 n
各种营养的最低要求
w1 1
w2 2
┇
wm m
a11 a12 … a1n
a21 a22 … a2n
… …
am1 am2 … amn
b1
b2
┇
bm
单价
C1 C2 … Cn
的分析，得到如下形式的线性规划问题：
现在从另一个角度提出问题：
设有一个制造商，要生产m种不同的药丸来代替上述n种不同的食物，试问每种药丸的价格如何确定，才能获利最大。
仍可利用上面的表格，设第i种药丸的价格是，并记为了达到畅销的目的，药丸的价格当然不宜超过与之相当的食物的价格，即应有，于是问题变成
据此我们得到如下定义：
10、称(L)和(D)所规定的线性规划问题是互为对偶问题。若其一叫原问题，则另一叫对偶问题，也称它们构成一组对称的对偶规划。
20、对于标准形的线性规划问题
考虑
和叫作一组非对称的对偶规划。
以下证明，对称对偶规划与非对称对偶规划是可以互相推出的。
由对称情形推出非对称情形。
因
故可变成:
此为(L)型,按定义其对偶规划应为
即
令，则已无非负限制，从而上式变成
这便是的形式，说明的对偶规划确为。
反之，设的对偶是，可证(L)的对偶是(D)。
对(L)引入剩余变量将其化成标准形式：
从而其对偶问题具形式：
此即
它恰为(D)。
除此之外，还有将两种情形结合起来的混合型对偶规划，例如设
其中为阶矩阵i,j=1,2。，分别为维向量。若原问题为
则它的对偶规划为
综上，我们可以总结出构成一般对偶规划的规则如下：
（ⅰ）把原问题的约束条件统一成及=（或及=），目标函数改写成求极小（或极大）。
（ⅱ）原问题的一个行约束对应一个变量，若行约束是不等式，则，否则无符号限制。
（ⅲ）原问题每个变量对应一个行约束：若，
则对应（或），若无限制，则对应（是原问题目标函数的系数）。
（ⅳ）原目标函数CX若为求极小（极大），则对应目标函数Wb求极大（极小）（这里b是原问题约束中的常数项列）。
例1 原问题
把不等式统一成，再列成下表：
x1 x2 x3 x4
w1
w2
w3
1 2 -1 -1=-7
6 -3 1 -714
28 17 -4 -23
5 -6 7 4 = f min
无限制
据此可直接写出对偶规划：
§2 对偶定理对于原问题和它的对偶问题的关系有以下几个定理，它们在理论和应用中都是很重要的。
定理1 （L）和（D），和同时有最优解的充要条件是同时有可行解。
证明 只需证充分性，设（L）和（D）分别有可行解，既有。于是对（L）的任一可行解X，有
即CX在可行解集合有下界，从而在基可行解的集合上有下界，由于基可行解是有限的故必于某点达到其下界，再根据的典式。其检验数或者全小于等于0，或者经过若干次迭代后，变得小于等于0，但目标函数值仍为，从而由单纯法的理论，知即为最优解，这便证明了（L）有最优解。
同样对D的任一可行解集W，有
故在可行解集合有上界，从而类似可证（D）有最优解。
推论 若和分别是（L）和（D）的可行解，且，则它们分别是（L）和（D）的最优解。
同理可证结论对和成立：
定理2 设（L）和（D）（或和）中一个有最优解，则另一个也一定有最优解，且目标函数值相同。
证明 设（L）有最优解，引入剩余变量Y则（L）可化为标准形式：
运用单纯形法可求得最优解，是基可行解，对应于某一基B，据最优判别准则有
令，上式可变成
故是（D）的可行解，又因
故由定理1的推论知是（D）的最优解,且
反之，设（D）有最优解，将（D）化成标准形式：
仿上可类似证明(L)有最优解。
从证明中易见。以上结论对（L）和（D）亦成立。
综上，互为对偶规划的解之间的联系，不外乎以下三种情况：
1 两个规划都有最优解。
2 两个规划都没有可行解。
3 一个规划有可行解，但目标函数在可行解集上无界，而另一个规划无可行解。
此外由定理2的证明知，若B是（L）的最优基，则单纯形乘子便是（D）的最优解，于是从原问题（L）的最终单纯形表中可以直接得到对偶问题（D）的解。实际上，假如在原始阵A中有一个mm阶的单位阵I,则在最后的表中，矩阵B出现在开始时为单位阵I的地方，同时B下面m个检验数为C,这样从最后一行中对应的这些元素与C的对应分量相加，就获得了对偶问题的最优解W=C。
定理3 松紧定理
（ⅰ）、考虑非对称的对偶规划（L′）和（D′）,设X和W分别是它们的可行解，则它们分别是（L′）和（D′）的最优解的充要条件是
（C-WA）X=0 (1)
证明 由定理1和2知，可行解X和W为最优解的充要条件是
CX= Wb= WA X
即
（C-WA）X=0
因X，C- WA0,故（1）式等价于
（C）X=0,j=1、……、n
由此可得结论：
1、若（L′）有最优解X,使得对指标j,满足X>0 （称为j对（L′）是松的）,则对（D′）的一切最优解w，必有WP=C(称为j对（D′）是紧的)。
2、若（D′）有最优解W，使对指标j，满足WPC(称j对（D′）是松的)，则对（L′）的一切最优解X，必有X=0（称j对（L′）是紧的）。
（ⅱ）、考虑对称对偶规划（D）和（L）,设X和W分别是（D）和（L）的可行解，则它们同时也是最优解的充要条件为
(2)
证明 将对称形式（L）、（D）转化为非对称形式（L′）和（D′）
（L′） （D′）
由以上（ⅰ）的结论知，和分别为（L′）和（D′）的最优解的充要条件是
即
由此得
故定理得证若记(表示A的标号为i的行向量)，则对称松紧关系（2）可表为：
、若，则
若，则
若，则
若，则
以上的对偶定理对于混合型的对偶规划同样成立。
对偶理论应用很广，如
（一）、已知对偶问题的最优解，求原问题的最优解。反之一样。
（二）、检验最优解性质的某些假说，例如在最优解处，原始的约束条件是否都是严格的不等式。
对偶定理及松紧定理有明显的经济解释。它指出，对于资源利用问题（D）,利用资源生产产品与转让（出售）资源这两种作法在理论上具有同等效益（）。其次，当时，表明按最优生产方案进行操作时，第i种资源消耗不尽，尚有剩余，因此，再增加这种资源不会增加目标函数值，从这个意义上讲，该资源的价值 。再有，当时，表明生产产品i要消耗的资源的价值高于该产品的价格，明智之举是不生产它，这也就是
§3关于影子价格的讨论先给出影子价格的定义，考虑资源最优利用问题的线性规划模型, (3)
设下表是该问题的最优单纯形表（4）：
… …
-max f
(4)
则根据对偶定理，便是对偶问题的最优解。并且有
(5)
(6)
由上式可以看出，第i种资源增加一个单位时，最大产值f将增加w.资源的这种价值w，称为边际价值，亦称为资源的影子价格.可见线性规划问题（3）中，资源的影子价格就是其对偶问题的最优解。它们是最优单纯形表（4）中，后m个检验数的相反数。
影子价格在经济上有着重要的意义。供不应求的资源称为短线资源。这时其影子价格大于O，反之亦然.供大于求的资源称为长线资源。其影子价格等于0，反之亦然。因此可据影子价格来判断某种资源是长线还是短线资源。
影子价格可指导资源管理部门对稀缺资源实行择优分配，资源的影子价格与资源的进价之差越大，获利越多，资源利用效果也就越好；反之当影子价格低于资源进价时，分配（如贷款）则是不可取的。此时，从经济上考虑，非但不宜购入反而应卖出，可见即使是短线资源也不是不加分析地一律购入的。
影子价格还用于价格预测，甲厂的产品是乙厂的资源，则在单一情形，产品的价格应在成本与影子价格之间，否则价格将处于诸厂影子价格中的最大值与最小值之间，这体现出经济结构的优劣对竞争力的具大影响。
研究结果表明，影子价格是相应资源量的减函数，对于线性问题（3），这个减函数是分段阶梯函数。在每段内它等于常数，即对偶最优解的相应分量，这时对偶最优解是唯一的，而且（5），（6）成立。但在两台阶的衔接处，函数必有间断，说明在此处对偶最优解不唯一，这时的相应资源量称为临界值，用表示，那么当资源量取临界值时，如何认识和确定它的影子价格呢？
事实上，假定当时，影子价格为，时为，则由函数的递减性和阶梯性，必有，这时对临界值，若取则目标值f将增加，若取则将减少，故增与减的值不等，这正是它与通常情形区别之所在。再看目标函数f，它实际上是资源量的连续分段线性函数，该函数在临界处虽说连续，且左右导数均存在，却不相等，这就是说对临界值（6）不成立。这时宜补充定义如下
(7)
其中，为资源的临界值。
表面看，（7）在处似有两个影子价格，但是一联系具体问题，不是考虑资源增加就是减少，两者必具其一也仅具其一，因而影子价格仍是唯一的。
进一步，如何判断资源量是否为临界值呢。上述分析表明，这等价于对偶问题的解是否唯一。
容易证明，如果问题（3）的最优解是非退化的，即所有基变量均为正，则对偶问题最优解唯一，故只有当是退化的，即有0基变量时，对偶问题才可能有多个最优解。在此基础上，可以给出对偶问题有非唯一解的充要条件（详见[24]）。最后可得下面的结果。
定理9 设资源优化利用问题（3）有个对偶最优解:
对于任意i，令
则当时，第i种资源的投入量恰为临界值，此时资源增加时的影子价格为，减时的影子价格为;而当w时第i种资源的投入量不取临界值，其影子价格仍为。
证明略。
例1
可以求得它有4个对偶最优解:
，，，
运用定理9，易知，四种资源减少时的影子价格分别是，增加时的全是0。故此四种资源全是临界值。而对偶解的两个非零分量和1竟然不是影子价格，这在没有深入分析之前是很难理解和想象的。以上分析表明，当资源处于临界值时，减少该资源对收益的影响，必须由来计算，增加对收益的影响必须由来计算，两者的数值是不同的，不注意这点往往会导致决策失误和经济损失。可见，正确认识临界资源的影子价格，把握质量的数量界限，并用它指导经济活动是必要的和有益的。
§4 对偶单纯形法先利用对偶理论解释单纯形法.
定理4 设（L）的任一基本解对应基，作，若和分别是（L）和（D）的可行解。则 和分别是（L） 和（D）的最优解。
证明 因是（D）的可行解，即
这说明不仅是（L）的对应于基B的基可行解，且所有检验数，故是（L）的最优解。又
故是（D）的最优解。
由以上证明可以看到的检验数全部非正与 是对偶问题（D）的可行解是等价的。据此可对单纯形法作如下解释：从一个基本解出发迭代到另一个基本解，在迭代过程中始终保持解的可行性(基可行解)，同时使它对应的对偶问题的解 的不可行性逐渐消失（即检验数逐渐变为非正）。直到满足对偶约束成为（D）的可行解,就是（L）的最优解了。
基于上述想法，考虑到对称性，也可把迭代过程建立在满足对偶问题（D）解的可行性上，即保持的检验数全部非正，逐步消除原问题基本解的不可行性（使非负 ），最后达到双方同时为可行解。从而由定理4，和就同时为最优解了，这就是对偶单纯形法的基本思想。
按以上设想，为求原问题（L ）的最优解，出发点将是一个某些变量取负值的基本解，但满足最优性判别条件（ j=1，2n ），这种基本解叫作正则解。相应的基称为正则基，简单地说，对偶单纯形法就是从正则解到正则解的迭代过程。
设给定正则解为，其典式为
(8)
(9)
这里S、R分别为基变量、非基变量下标集合。注意是正则解，
故可为负，而
由典式（8），容易看出以下两结论成立
（ⅰ）、若对每一，则即为最优解。
（ⅱ）、若对某，均有系数，则原问题无可行解。
类似于单纯形法的讨论可得对偶单纯形法的迭代步骤如下：
（一）、从一个正则解及典式（8）-（9）开始。
（二）、如果则为最优解，结束，否则转（三）。
（三）、取使的变量为离基变量（若有若干个，
可任取一个，通常取满足或者取使目标函数上升最大的为）转（四）。
（四）、若对所有，有，原问题无可行解，结束，否则转（五）。
（五）、计算，取为进基变量，转（六）。
（六）、以为主元实行Guass消元，得新的正则解及其对应典式，转（二）。
容易看出，经以上迭代一次后目标函数将上升,注意这里，因此，如果任意一个正则解所对应的非基变量的检验数都小于0（此时称问题为非退化的，否则为退化的），则迭代中目标函数将严格上升，从而不会产生循环，迭代必终止于有限步。若有某一非基变量的检验数=0，即于退化情形，以上迭代不能保证有限步结束，遇这种情形，可象对待单纯形法那样，给一个摄动，用字典序法处理，这里就不详述。
§5 线性规划问题的联合算法
求解线性规划问题：
(10)
的单纯形法和对偶单纯形法虽然相当有效，但各自也有缺陷,前者要费很大精力去找作为出发点的第一个基可行解，后者为得到初始正则解,付出的代价往往更高，还有一种原始对偶算法[14]，虽说它可以免去上述困扰，但每步迭代都要解一个限定的线性规划问题，因此其效果也未必比单纯形法和对偶单纯形法好。
为了克服以上不足，长期以来，人们一个很自然的想法是希望对如下面表1的初始表（其中仍称为检验数，），能象单纯形法那样对某正检验数所在的列，按照最小比值选主元，实行Gauss消元，由之，可确定一基变量（仍标在该行左端），如此进行下去，一旦所选基变量的个数达到秩A，便得到一基可行解。以后继续进行单纯形迭代就可以了。
表1
…
…
…
… … … …
…
f
…
0
但是此种想法并非总能实现，除上述理想情形之外，还会有以上几种可能情形出现：
表中某行全变成0。
出现某行i，该行系数而右端常数项
。
所有检验数，但所选基变量的个数小于秩A。
虽说还有正检验数，但这些正检验数所在列之系数均小于或等于0，而所选基变量的个数又小于秩A。
易见，1.意味着（10）中有多余方程，因此删掉该行就行了，而2.说明问题无解，这两种情形容易处理。
对3、由于此时所有检验数，故对没有选出基变量的行，可象对偶单纯形法那样，在保证检验数仍旧非正的前提下，选出一基变量。循此而进，最后可得一正则解，继而用对偶单纯形法迭代求优。
关键是4.难于处理，虽然此种情形在实际问题中很少出现，但要作为一种算法提出，则是必须予以考虑的，这也许正是前述想法至今未能形成有效算法的根本原因之一。对此，我们进行了颇有成效的研究，找到了处理情形4的简易方法，这主要依据下面的结果。
定理6 假设针对表1实行单纯形迭代而出现情形4，记
（ⅰ）、如果存在，使当行没选出基变量} 时，则原问题（10）无解。
（ⅱ）、否则，应存在,使得
(11)
有意义，故可以i行的倍加入目标函数行（其余不变），这时新检验数，且当时，。
证明 （ⅰ） 不妨设秩A为m，为已选基变量，引入辅助变量，目标函数修改为：
其中M是充分大的正数，不妨设相应的单纯形表如表2所示，易见，将，各行乘M加于目标函数行后，，即变成基变量，从而便是辅助问题的一个基可行解之基变量，由假设，故新检验数,而，这说明表2所示辅助问题无最优解，根据第二章定理3之推论，原问题（10）亦无最优解。
表2
… …
… … 0 0
… …
… … 0 0
… 0 … 1 0
… … …
… 0 … 0 1
f
… … -M -M
（ⅱ）、在（ⅰ）的假定不成立时，这是容易验证的事实。
综合以上分析便得到如下的联合算法：
（Ⅰ）、对表1，令（若R为空集转（III）），对，计算最小比值：
(12)
对满足（12）的所有，计算
则为一（进）基变量[注1]，以为主元实行Gauss消元，并将填在S行最左边。如果此行原来已有基变量，就用替换之，转（Ⅱ）。
（Ⅱ）检查所得单纯形表，若出现以下情形则分别处理之；否则，转回（Ⅰ）。
某行全变成0，则删掉此行，转（Ⅰ）。
有某行，此行的系数，且常数项
，结束，原问题（10）无解。
R变为空集，转（Ⅲ）。
对任意，皆有这时
①、若所选基变量的个数秩A；或者秩 A，但存在某个，使得（），结束，原问题（10）无解。
②、否则，任取，总有，使，以i行的倍（或者按（11），以i行的倍）加入目标函数行，其余不变，其结果，如还有正检验数，转回（Ⅰ）；否则转（Ⅲ）。
（Ⅲ）、检查基变量个数，若等于秩A（即表中每行左端均标出基变量），结束，已得最优解。
③否则，T={i|i行未标出基变量}非空。任取i,令
(14)
则为一基变量，以为主元实行Gauss消元。并将填于i行最左边，若T仍非空，重复③的步骤，直到出现类似2的无解情形或T为空集止，若为后者已得一正则解，继之用对偶单纯形法迭代求优。
[注]1（进）基变量及主元的选择原则上可象单纯形法那样只按（12）进行。这里按（12）、（13）选主元的好处在于，一则每次迭代可使目标函数下降最大，二则能避免或减少已选的基变量象走马灯似地换出换进，从而减少迭代次数。其所增加的计算量，与减少一次迭代的计算量相比一般是微不足道的。
[注]2、(14)是当时的选主元规则，当 时，选主元规则宜为：
(15)
即与对偶单纯形法的一样。
和单纯形法中常用的二阶段法相比，联合算法不用引入人工变量去搞什么两阶段，且从迭代一开始就使目标函数沿着下降的方向疾进，如不出现3和4（如例1）得到第一个基可行解即使不是最优的，也与最优解相当接近，因而实际上减少的计算量几与第二阶段相等。若出现3，正好发挥对偶单纯形法的优势，不必引入正参数大M，便能寻出一正则解。而对一向感到棘手的情形4（如下面的例2），只须用一个极简单的程序② （几乎不增计算量），就可轻易处理掉。而且可证若问题有最优解，则程序②只能出现有限次，故不会影响收敛性[20]。
周知，单纯形法迭代的前提是有个基可行解，而对偶单纯形迭代必须从正则解开始。这些基本解都是各具特殊性质的。因此面对既不是基可行解，也不是正则解的基本解（即既有正检验数又有负常数项的基本解），两种方法便都显得无能为力（灵敏度分析中便常常有这种情形出现），而联合算法是从“零”开始（即一个基变量也没有），故可从任一基本解出发处理问题，事实上，只须以（-1）乘有负常数项那些行，便可化成已有若干个基变量并可用联合算法求解的问题了。
这样，联合算法把单纯形法和对偶单纯形法紧密结合起来，相机使用，扬二者之长而避二者之短，不仅能减少存贮和计算量，而且显示出更大的适应性以及处理问题灵活方便的特点。
如果不看最小比值，联合算法几乎与求方程组基本解的Gauss消元法无异，因此达到了很大限度的简化。
例1、
先列初始表，继之按（12）、（13）选基求优，其迭代过程如下表所示（其中打*者为所选主元）。
x
1 -1 2 -1 1*
2 1 -2 2 0
3 0 1 -1 0
10
8
4
f
-2 1 -1 3/2 1
0
X5
1 -1 2 -1 1
2 1* -2 2 0
3 0 1 -1 0
10
8
4
f
-3 2 -3 5/2 0
-10
x5
x2
3 0 0 1 1
2 1 -2 2 0
3 0 1* -1 0
18
8
4
f
-7 0 1 -3/2 0
-26
x5
x2
x3
3 0 0 1 1
8 1 0 0 0
3 0 1 -1 0
18
16
4
f
-10 0 0 -1/2 0
-30
所得第一个基可行解,(0,16,4,0,18)T
即为最优解，最优值为min f =-30
例2
,
x
x6
1 -1 2 -1 1 1
2 1* -2 2 2 0
4 -1 1 -1 2 0
10
8
14
f
-2 2 -3 -1 -1 0
0
x6
x2
3 0 0 1 3 1
2 1 -2 2 2 0
6* 0 -1 1 4 0
18
8
22
f
-6 0 1 -5 -5 0
-16
f
0 0 0 -4 -1 0
6
x6
x2
x1
0 0 1/2 1/2 1 1
0 1 -5/3* 5/3 2/3 0
1 0 -1/6 1/6 2/3 0
7
2/3
11/3
f
0 0 0 -4 -1 0
6
（出现情形4采用步骤②后转步骤③）
最优解为 (11/3,2/3,0,0,0,7)T,min f =6.
§1 对偶问题的提出回顾对第一章§1例3营养问题
食物营养成分
x1 x2 xn
1 2 n
各种营养的最低要求
w1 1
w2 2
┇
wm m
a11 a12 … a1n
a21 a22 … a2n
… …
am1 am2 … amn
b1
b2
┇
bm
单价
C1 C2 … Cn
的分析，得到如下形式的线性规划问题：
现在从另一个角度提出问题：
设有一个制造商，要生产m种不同的药丸来代替上述n种不同的食物，试问每种药丸的价格如何确定，才能获利最大。
仍可利用上面的表格，设第i种药丸的价格是，并记为了达到畅销的目的，药丸的价格当然不宜超过与之相当的食物的价格，即应有，于是问题变成
据此我们得到如下定义：
10、称(L)和(D)所规定的线性规划问题是互为对偶问题。若其一叫原问题，则另一叫对偶问题，也称它们构成一组对称的对偶规划。
20、对于标准形的线性规划问题
考虑
和叫作一组非对称的对偶规划。
以下证明，对称对偶规划与非对称对偶规划是可以互相推出的。
由对称情形推出非对称情形。
因
故可变成:
此为(L)型,按定义其对偶规划应为
即
令，则已无非负限制，从而上式变成
这便是的形式，说明的对偶规划确为。
反之，设的对偶是，可证(L)的对偶是(D)。
对(L)引入剩余变量将其化成标准形式：
从而其对偶问题具形式：
此即
它恰为(D)。
除此之外，还有将两种情形结合起来的混合型对偶规划，例如设
其中为阶矩阵i,j=1,2。，分别为维向量。若原问题为
则它的对偶规划为
综上，我们可以总结出构成一般对偶规划的规则如下：
（ⅰ）把原问题的约束条件统一成及=（或及=），目标函数改写成求极小（或极大）。
（ⅱ）原问题的一个行约束对应一个变量，若行约束是不等式，则，否则无符号限制。
（ⅲ）原问题每个变量对应一个行约束：若，
则对应（或），若无限制，则对应（是原问题目标函数的系数）。
（ⅳ）原目标函数CX若为求极小（极大），则对应目标函数Wb求极大（极小）（这里b是原问题约束中的常数项列）。
例1 原问题
把不等式统一成，再列成下表：
x1 x2 x3 x4
w1
w2
w3
1 2 -1 -1=-7
6 -3 1 -714
28 17 -4 -23
5 -6 7 4 = f min
无限制
据此可直接写出对偶规划：
§2 对偶定理对于原问题和它的对偶问题的关系有以下几个定理，它们在理论和应用中都是很重要的。
定理1 （L）和（D），和同时有最优解的充要条件是同时有可行解。
证明 只需证充分性，设（L）和（D）分别有可行解，既有。于是对（L）的任一可行解X，有
即CX在可行解集合有下界，从而在基可行解的集合上有下界，由于基可行解是有限的故必于某点达到其下界，再根据的典式。其检验数或者全小于等于0，或者经过若干次迭代后，变得小于等于0，但目标函数值仍为，从而由单纯法的理论，知即为最优解，这便证明了（L）有最优解。
同样对D的任一可行解集W，有
故在可行解集合有上界，从而类似可证（D）有最优解。
推论 若和分别是（L）和（D）的可行解，且，则它们分别是（L）和（D）的最优解。
同理可证结论对和成立：
定理2 设（L）和（D）（或和）中一个有最优解，则另一个也一定有最优解，且目标函数值相同。
证明 设（L）有最优解，引入剩余变量Y则（L）可化为标准形式：
运用单纯形法可求得最优解，是基可行解，对应于某一基B，据最优判别准则有
令，上式可变成
故是（D）的可行解，又因
故由定理1的推论知是（D）的最优解,且
反之，设（D）有最优解，将（D）化成标准形式：
仿上可类似证明(L)有最优解。
从证明中易见。以上结论对（L）和（D）亦成立。
综上，互为对偶规划的解之间的联系，不外乎以下三种情况：
1 两个规划都有最优解。
2 两个规划都没有可行解。
3 一个规划有可行解，但目标函数在可行解集上无界，而另一个规划无可行解。
此外由定理2的证明知，若B是（L）的最优基，则单纯形乘子便是（D）的最优解，于是从原问题（L）的最终单纯形表中可以直接得到对偶问题（D）的解。实际上，假如在原始阵A中有一个mm阶的单位阵I,则在最后的表中，矩阵B出现在开始时为单位阵I的地方，同时B下面m个检验数为C,这样从最后一行中对应的这些元素与C的对应分量相加，就获得了对偶问题的最优解W=C。
定理3 松紧定理
（ⅰ）、考虑非对称的对偶规划（L′）和（D′）,设X和W分别是它们的可行解，则它们分别是（L′）和（D′）的最优解的充要条件是
（C-WA）X=0 (1)
证明 由定理1和2知，可行解X和W为最优解的充要条件是
CX= Wb= WA X
即
（C-WA）X=0
因X，C- WA0,故（1）式等价于
（C）X=0,j=1、……、n
由此可得结论：
1、若（L′）有最优解X,使得对指标j,满足X>0 （称为j对（L′）是松的）,则对（D′）的一切最优解w，必有WP=C(称为j对（D′）是紧的)。
2、若（D′）有最优解W，使对指标j，满足WPC(称j对（D′）是松的)，则对（L′）的一切最优解X，必有X=0（称j对（L′）是紧的）。
（ⅱ）、考虑对称对偶规划（D）和（L）,设X和W分别是（D）和（L）的可行解，则它们同时也是最优解的充要条件为
(2)
证明 将对称形式（L）、（D）转化为非对称形式（L′）和（D′）
（L′） （D′）
由以上（ⅰ）的结论知，和分别为（L′）和（D′）的最优解的充要条件是
即
由此得
故定理得证若记(表示A的标号为i的行向量)，则对称松紧关系（2）可表为：
、若，则
若，则
若，则
若，则
以上的对偶定理对于混合型的对偶规划同样成立。
对偶理论应用很广，如
（一）、已知对偶问题的最优解，求原问题的最优解。反之一样。
（二）、检验最优解性质的某些假说，例如在最优解处，原始的约束条件是否都是严格的不等式。
对偶定理及松紧定理有明显的经济解释。它指出，对于资源利用问题（D）,利用资源生产产品与转让（出售）资源这两种作法在理论上具有同等效益（）。其次，当时，表明按最优生产方案进行操作时，第i种资源消耗不尽，尚有剩余，因此，再增加这种资源不会增加目标函数值，从这个意义上讲，该资源的价值 。再有，当时，表明生产产品i要消耗的资源的价值高于该产品的价格，明智之举是不生产它，这也就是
§3关于影子价格的讨论先给出影子价格的定义，考虑资源最优利用问题的线性规划模型, (3)
设下表是该问题的最优单纯形表（4）：
… …
-max f
(4)
则根据对偶定理，便是对偶问题的最优解。并且有
(5)
(6)
由上式可以看出，第i种资源增加一个单位时，最大产值f将增加w.资源的这种价值w，称为边际价值，亦称为资源的影子价格.可见线性规划问题（3）中，资源的影子价格就是其对偶问题的最优解。它们是最优单纯形表（4）中，后m个检验数的相反数。
影子价格在经济上有着重要的意义。供不应求的资源称为短线资源。这时其影子价格大于O，反之亦然.供大于求的资源称为长线资源。其影子价格等于0，反之亦然。因此可据影子价格来判断某种资源是长线还是短线资源。
影子价格可指导资源管理部门对稀缺资源实行择优分配，资源的影子价格与资源的进价之差越大，获利越多，资源利用效果也就越好；反之当影子价格低于资源进价时，分配（如贷款）则是不可取的。此时，从经济上考虑，非但不宜购入反而应卖出，可见即使是短线资源也不是不加分析地一律购入的。
影子价格还用于价格预测，甲厂的产品是乙厂的资源，则在单一情形，产品的价格应在成本与影子价格之间，否则价格将处于诸厂影子价格中的最大值与最小值之间，这体现出经济结构的优劣对竞争力的具大影响。
研究结果表明，影子价格是相应资源量的减函数，对于线性问题（3），这个减函数是分段阶梯函数。在每段内它等于常数，即对偶最优解的相应分量，这时对偶最优解是唯一的，而且（5），（6）成立。但在两台阶的衔接处，函数必有间断，说明在此处对偶最优解不唯一，这时的相应资源量称为临界值，用表示，那么当资源量取临界值时，如何认识和确定它的影子价格呢？
事实上，假定当时，影子价格为，时为，则由函数的递减性和阶梯性，必有，这时对临界值，若取则目标值f将增加，若取则将减少，故增与减的值不等，这正是它与通常情形区别之所在。再看目标函数f，它实际上是资源量的连续分段线性函数，该函数在临界处虽说连续，且左右导数均存在，却不相等，这就是说对临界值（6）不成立。这时宜补充定义如下
(7)
其中，为资源的临界值。
表面看，（7）在处似有两个影子价格，但是一联系具体问题，不是考虑资源增加就是减少，两者必具其一也仅具其一，因而影子价格仍是唯一的。
进一步，如何判断资源量是否为临界值呢。上述分析表明，这等价于对偶问题的解是否唯一。
容易证明，如果问题（3）的最优解是非退化的，即所有基变量均为正，则对偶问题最优解唯一，故只有当是退化的，即有0基变量时，对偶问题才可能有多个最优解。在此基础上，可以给出对偶问题有非唯一解的充要条件（详见[24]）。最后可得下面的结果。
定理9 设资源优化利用问题（3）有个对偶最优解:
对于任意i，令
则当时，第i种资源的投入量恰为临界值，此时资源增加时的影子价格为，减时的影子价格为;而当w时第i种资源的投入量不取临界值，其影子价格仍为。
证明略。
例1
可以求得它有4个对偶最优解:
，，，
运用定理9，易知，四种资源减少时的影子价格分别是，增加时的全是0。故此四种资源全是临界值。而对偶解的两个非零分量和1竟然不是影子价格，这在没有深入分析之前是很难理解和想象的。以上分析表明，当资源处于临界值时，减少该资源对收益的影响，必须由来计算，增加对收益的影响必须由来计算，两者的数值是不同的，不注意这点往往会导致决策失误和经济损失。可见，正确认识临界资源的影子价格，把握质量的数量界限，并用它指导经济活动是必要的和有益的。
§4 对偶单纯形法先利用对偶理论解释单纯形法.
定理4 设（L）的任一基本解对应基，作，若和分别是（L）和（D）的可行解。则 和分别是（L） 和（D）的最优解。
证明 因是（D）的可行解，即
这说明不仅是（L）的对应于基B的基可行解，且所有检验数，故是（L）的最优解。又
故是（D）的最优解。
由以上证明可以看到的检验数全部非正与 是对偶问题（D）的可行解是等价的。据此可对单纯形法作如下解释：从一个基本解出发迭代到另一个基本解，在迭代过程中始终保持解的可行性(基可行解)，同时使它对应的对偶问题的解 的不可行性逐渐消失（即检验数逐渐变为非正）。直到满足对偶约束成为（D）的可行解,就是（L）的最优解了。
基于上述想法，考虑到对称性，也可把迭代过程建立在满足对偶问题（D）解的可行性上，即保持的检验数全部非正，逐步消除原问题基本解的不可行性（使非负 ），最后达到双方同时为可行解。从而由定理4，和就同时为最优解了，这就是对偶单纯形法的基本思想。
按以上设想，为求原问题（L ）的最优解，出发点将是一个某些变量取负值的基本解，但满足最优性判别条件（ j=1，2n ），这种基本解叫作正则解。相应的基称为正则基，简单地说，对偶单纯形法就是从正则解到正则解的迭代过程。
设给定正则解为，其典式为
(8)
(9)
这里S、R分别为基变量、非基变量下标集合。注意是正则解，
故可为负，而
由典式（8），容易看出以下两结论成立
（ⅰ）、若对每一，则即为最优解。
（ⅱ）、若对某，均有系数，则原问题无可行解。
类似于单纯形法的讨论可得对偶单纯形法的迭代步骤如下：
（一）、从一个正则解及典式（8）-（9）开始。
（二）、如果则为最优解，结束，否则转（三）。
（三）、取使的变量为离基变量（若有若干个，
可任取一个，通常取满足或者取使目标函数上升最大的为）转（四）。
（四）、若对所有，有，原问题无可行解，结束，否则转（五）。
（五）、计算，取为进基变量，转（六）。
（六）、以为主元实行Guass消元，得新的正则解及其对应典式，转（二）。
容易看出，经以上迭代一次后目标函数将上升,注意这里，因此，如果任意一个正则解所对应的非基变量的检验数都小于0（此时称问题为非退化的，否则为退化的），则迭代中目标函数将严格上升，从而不会产生循环，迭代必终止于有限步。若有某一非基变量的检验数=0，即于退化情形，以上迭代不能保证有限步结束，遇这种情形，可象对待单纯形法那样，给一个摄动，用字典序法处理，这里就不详述。
§5 线性规划问题的联合算法
求解线性规划问题：
(10)
的单纯形法和对偶单纯形法虽然相当有效，但各自也有缺陷,前者要费很大精力去找作为出发点的第一个基可行解，后者为得到初始正则解,付出的代价往往更高，还有一种原始对偶算法[14]，虽说它可以免去上述困扰，但每步迭代都要解一个限定的线性规划问题，因此其效果也未必比单纯形法和对偶单纯形法好。
为了克服以上不足，长期以来，人们一个很自然的想法是希望对如下面表1的初始表（其中仍称为检验数，），能象单纯形法那样对某正检验数所在的列，按照最小比值选主元，实行Gauss消元，由之，可确定一基变量（仍标在该行左端），如此进行下去，一旦所选基变量的个数达到秩A，便得到一基可行解。以后继续进行单纯形迭代就可以了。
表1
…
…
…
… … … …
…
f
…
0
但是此种想法并非总能实现，除上述理想情形之外，还会有以上几种可能情形出现：
表中某行全变成0。
出现某行i，该行系数而右端常数项
。
所有检验数，但所选基变量的个数小于秩A。
虽说还有正检验数，但这些正检验数所在列之系数均小于或等于0，而所选基变量的个数又小于秩A。
易见，1.意味着（10）中有多余方程，因此删掉该行就行了，而2.说明问题无解，这两种情形容易处理。
对3、由于此时所有检验数，故对没有选出基变量的行，可象对偶单纯形法那样，在保证检验数仍旧非正的前提下，选出一基变量。循此而进，最后可得一正则解，继而用对偶单纯形法迭代求优。
关键是4.难于处理，虽然此种情形在实际问题中很少出现，但要作为一种算法提出，则是必须予以考虑的，这也许正是前述想法至今未能形成有效算法的根本原因之一。对此，我们进行了颇有成效的研究，找到了处理情形4的简易方法，这主要依据下面的结果。
定理6 假设针对表1实行单纯形迭代而出现情形4，记
（ⅰ）、如果存在，使当行没选出基变量} 时，则原问题（10）无解。
（ⅱ）、否则，应存在,使得
(11)
有意义，故可以i行的倍加入目标函数行（其余不变），这时新检验数，且当时，。
证明 （ⅰ） 不妨设秩A为m，为已选基变量，引入辅助变量，目标函数修改为：
其中M是充分大的正数，不妨设相应的单纯形表如表2所示，易见，将，各行乘M加于目标函数行后，，即变成基变量，从而便是辅助问题的一个基可行解之基变量，由假设，故新检验数,而，这说明表2所示辅助问题无最优解，根据第二章定理3之推论，原问题（10）亦无最优解。
表2
… …
… … 0 0
… …
… … 0 0
… 0 … 1 0
… … …
… 0 … 0 1
f
… … -M -M
（ⅱ）、在（ⅰ）的假定不成立时，这是容易验证的事实。
综合以上分析便得到如下的联合算法：
（Ⅰ）、对表1，令（若R为空集转（III）），对，计算最小比值：
(12)
对满足（12）的所有，计算
则为一（进）基变量[注1]，以为主元实行Gauss消元，并将填在S行最左边。如果此行原来已有基变量，就用替换之，转（Ⅱ）。
（Ⅱ）检查所得单纯形表，若出现以下情形则分别处理之；否则，转回（Ⅰ）。
某行全变成0，则删掉此行，转（Ⅰ）。
有某行，此行的系数，且常数项
，结束，原问题（10）无解。
R变为空集，转（Ⅲ）。
对任意，皆有这时
①、若所选基变量的个数秩A；或者秩 A，但存在某个，使得（），结束，原问题（10）无解。
②、否则，任取，总有，使，以i行的倍（或者按（11），以i行的倍）加入目标函数行，其余不变，其结果，如还有正检验数，转回（Ⅰ）；否则转（Ⅲ）。
（Ⅲ）、检查基变量个数，若等于秩A（即表中每行左端均标出基变量），结束，已得最优解。
③否则，T={i|i行未标出基变量}非空。任取i,令
(14)
则为一基变量，以为主元实行Gauss消元。并将填于i行最左边，若T仍非空，重复③的步骤，直到出现类似2的无解情形或T为空集止，若为后者已得一正则解，继之用对偶单纯形法迭代求优。
[注]1（进）基变量及主元的选择原则上可象单纯形法那样只按（12）进行。这里按（12）、（13）选主元的好处在于，一则每次迭代可使目标函数下降最大，二则能避免或减少已选的基变量象走马灯似地换出换进，从而减少迭代次数。其所增加的计算量，与减少一次迭代的计算量相比一般是微不足道的。
[注]2、(14)是当时的选主元规则，当 时，选主元规则宜为：
(15)
即与对偶单纯形法的一样。
和单纯形法中常用的二阶段法相比，联合算法不用引入人工变量去搞什么两阶段，且从迭代一开始就使目标函数沿着下降的方向疾进，如不出现3和4（如例1）得到第一个基可行解即使不是最优的，也与最优解相当接近，因而实际上减少的计算量几与第二阶段相等。若出现3，正好发挥对偶单纯形法的优势，不必引入正参数大M，便能寻出一正则解。而对一向感到棘手的情形4（如下面的例2），只须用一个极简单的程序② （几乎不增计算量），就可轻易处理掉。而且可证若问题有最优解，则程序②只能出现有限次，故不会影响收敛性[20]。
周知，单纯形法迭代的前提是有个基可行解，而对偶单纯形迭代必须从正则解开始。这些基本解都是各具特殊性质的。因此面对既不是基可行解，也不是正则解的基本解（即既有正检验数又有负常数项的基本解），两种方法便都显得无能为力（灵敏度分析中便常常有这种情形出现），而联合算法是从“零”开始（即一个基变量也没有），故可从任一基本解出发处理问题，事实上，只须以（-1）乘有负常数项那些行，便可化成已有若干个基变量并可用联合算法求解的问题了。
这样，联合算法把单纯形法和对偶单纯形法紧密结合起来，相机使用，扬二者之长而避二者之短，不仅能减少存贮和计算量，而且显示出更大的适应性以及处理问题灵活方便的特点。
如果不看最小比值，联合算法几乎与求方程组基本解的Gauss消元法无异，因此达到了很大限度的简化。
例1、
先列初始表，继之按（12）、（13）选基求优，其迭代过程如下表所示（其中打*者为所选主元）。
x
1 -1 2 -1 1*
2 1 -2 2 0
3 0 1 -1 0
10
8
4
f
-2 1 -1 3/2 1
0
X5
1 -1 2 -1 1
2 1* -2 2 0
3 0 1 -1 0
10
8
4
f
-3 2 -3 5/2 0
-10
x5
x2
3 0 0 1 1
2 1 -2 2 0
3 0 1* -1 0
18
8
4
f
-7 0 1 -3/2 0
-26
x5
x2
x3
3 0 0 1 1
8 1 0 0 0
3 0 1 -1 0
18
16
4
f
-10 0 0 -1/2 0
-30
所得第一个基可行解,(0,16,4,0,18)T
即为最优解，最优值为min f =-30
例2
,
x
x6
1 -1 2 -1 1 1
2 1* -2 2 2 0
4 -1 1 -1 2 0
10
8
14
f
-2 2 -3 -1 -1 0
0
x6
x2
3 0 0 1 3 1
2 1 -2 2 2 0
6* 0 -1 1 4 0
18
8
22
f
-6 0 1 -5 -5 0
-16
f
0 0 0 -4 -1 0
6
x6
x2
x1
0 0 1/2 1/2 1 1
0 1 -5/3* 5/3 2/3 0
1 0 -1/6 1/6 2/3 0
7
2/3
11/3
f
0 0 0 -4 -1 0
6
（出现情形4采用步骤②后转步骤③）
最优解为 (11/3,2/3,0,0,0,7)T,min f =6.
