第十四章 线性规划的对偶问题
14.1 对称的对偶规划
在线性规划早期发展中,对问题是一项重要的发现.早在1928著名数学家
John.Von.Neumann 在研究对策理论时就已经有原始和对偶的思想.
对偶理论有着重要的应用.首先是在原始,对偶两个线性规划中求解任一规划时,含自动地给出另一个规划的最优解.当对偶问题比原问题有较少分量时,求解对偶问题比求解原始问题方便的多.
对偶理论另一个应用是Lemke,1954提出的对偶域形法。另外,对偶理论还应用于通用的运转问题模型上，对偶理论对影子价值的分析在经济理论上有着重要作用.
14.1.1对偶问题的提出:
例14.1.1:某厂生产A.B.C 三种畅销产品,每台产品需四种资源,具体数据表
问怎样安排生产,效益最大! 设决策变量123,,x x x 得出模型:
123
123123
123123
max 20004000300034260022400..3330024200
0.1,2,3
i z x x x x x x x x x s t x x x x x x x i =++++≤??++≤??++≤??++≤??>=? 现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生产这些产品时可以得到的最大效益.
这就需建立另一个线性规划模型,设1234,,y y y y 代表销售这四种资源总售价尽可能低,即 1234min 600400300200w y y y y =+++
原来生产产品A 每台需用的资源按现在的单价计算,每台收益为: 123432y y y y +++
为了使工厂效益不减少,就要求订1234,,,y y y y 时,使这个效益额不低于原来生产一台产品A 可以得到的效益,因此满足约束:
1234322000y y y y +++≥
对B,C 产品可列出类似约束. 123412344324000
22343000
y y y y y y y y +++≥+++≥
因此得到的线性规划问题模型如下: 1234123412343220004324000..223430000(1~4)
i y y y y y y y y s t y y y y y i +++≥??+++≥??+++≥??≥=? 易见,后一个问题的数据完全由另一问题数据确定.对每一个线性规划问题
都伴随有另一个线性规划问题,一般地。对每个(LP) max ..0Cx s t Ax b x ??
≤??≥? 都伴随一个对偶
规划(LP)。
定义14.1.1个(LP),都存在着线性规划问题(LD) min .. 0ub s t uA c u ??
≥??≥?
其中1(,...)m u u u =是m 维向量,称(LP)为原始线性规划.称(LD)为(LP)的对偶线性规划.
下面进一步探讨(LP)与(LD)之间的关系：
(LP) 21122111211121222212
max ...,,.....,,...,,...0(1~)(n n n n b n m m mn m j z c x c x c x a a a x b s t a a a x x a a a b x j n 最大化约束条件号）?=+++?
??????? ?? ??≤? ? ???? ? ?
????????≥=≤?
其对偶问题:
(LD) ()11221112112212221212min ...,,...(,,...),,...,,...,,...0(1~)()
m m n m n n m m mn i w u b u b u b a a a u u u a a a c c c a a a u i m 最小化约束条件号≥=+++??
???
? ?≥? ?? ?
???
?≥=? 用下表示二者之间关系,更为清楚:
划问题，也就无所谓“原始线性规划问题”如果没有原始线性规划问题，也就无所谓对偶线性规划问题了.
线性规划的对偶关系具有“对合”性质,什么是对合性质呢? min max max 00
T T
T T T T b b b A c A c A c 因μμμμμμμμ?-=-≥?-≤-?-≤-≥?≥ 因而问题可写成（10）max :():.. () 0T T T T T T b LP s t A c μμμ?-?
'-≤-??≥?
可见，（LP ） '与（LP ）是同一类型的问题，依照定义1，又可写出（LP ）'的对角线形状态。记为（LP ） '
（LP ）' min () s.t. () 0T T T T T x c x A bT x ?-?
-≥-??≥?
（LP ）’ 又可等价地写成：max .. 0cx s t Ax b x ??
≤??≥?
既（LD ）’就是前面的（LP ），而（LD ）’等价于前面的（LD ）这表面，对于一个给定的（LP ）可以根据对偶规则写出（LD ）；而对于新问题（LD ），又可根据对偶规则写出其对偶。而此对偶又刚好回到原问题本身。即（LP ）的对偶是（LD ） ，（LD ）的对偶是（LP ）。
这就是线形规则对偶关系的“对合”性质。这样我们可以把一个相互对偶的线性规则中任何一个称为原问题，而把另一个称为对偶问题，称它们互为对偶。
下面我们举例说明怎样由一个规则写出其对偶问题。 例14.1.2：写出：min 1234567x x x x -++
s.t 12341234
12341427637142817423 0
x x x x x x x x x x x x x x +--≥-??-++≥??--++≤-??≥?的对偶规划
解：因目标函数最小化故先把约束条件都写成“ >”形式：
1134123412341234
14Min 5x -6x 7x x s.t. x 2x -x -x 7
() 6x -3x x 7x 14 28x 17x -4x -2x 3
x x 0
LP ++??+>??
++>??+>???>?
由于这是个（LD ）问题。故其对偶是（LP ）问题。目标函数极大化，约束不等式，用“≥”号，因（LD ）中三个“≥”不等式，故引入三个变量123..u u u 分别
与之对应。因原角中有四个变量1234...x x x x ，因此对偶问题中有四个约束不等式。 对偶函数目标系数由给出的（LD ）约束右端列向量（-7，14，3)转置而成，对偶的约束方程右端常数，向量由（LD ）的目标函数系数向量（5，-6，7，1）转置而得，从而写出（LP ）问题：
Max 1237143u u u -++
（LP ） （s.t ）123123123123
12362852317647721
..0u u u u u u u u u u u u u u u ++≤??-+≤-??
-+-≤??-+-≤??≥?
由于（LP ）max 0cx Ax b x ??≤??≥? 与（LD ）min 0ub uA c u ??
≥??≥?
形式上是等价的。所以把它们称为一
对对称的对偶规划。
下面来补充它们的关系。
14.1.2（LP ）、（LD ）的对偶定理
定理14.1.1 对于（LP ）的任意可行解x ,及（LD ）的任意可行解u 有cx ≤ub
证：因 x 、u 满足： ,0AX b X ≤≥ （14.1.1）
,0uA c u ≥≥ （14.1.2）
用u 左乘（1），x 右乘（2）的：c x ≤u Ax ≤u b 故c x ≤u b .
定理1 给出了（LP ）（LD ）这对互为对偶的线性规问题目标函数的一个界限。若（LP ）有可行解x ，则（LD ）的目标值ub 就有了下界cx ；反之，若（LD ）有可行解u ，则（LP ）的目标值cx 就有了上界ub 。
推论：若（LP ）有无界解，则（LD ）无可行解。 若（LD ）有无界解，则（LP ）无可行解。
证明：只证前面，后面一样，反证法。 若（LP ）有无界解，而（LD ）有可
行解，而根据定理14.1.1，对（LP ）的任何可行解x ，cx ≤u b ，这与（LP ）目标函数无上界矛盾。
注： 这个推论的逆不一定成立。即一对对偶问题中有一个无可行解，不能判定另一个有无界解。
例14.1.3： 123max x x x ++
（LP ） s.t 1233123
26..0x x x x x x x -+≤??
≤-??≥?
12min 2u u -
（LD ） s.t 21
1212111.0
u u u u u u ≥??-≥??+≥??≥?
上面（LP ）无可行解，而（LD ）并没有无界解，而是无可行解。
定理14.1.2：对偶规划（LP ）有最优解（LD ）?两者同时有可行解. 证明：?显然，有最优解的（LP ）（LD ）。必有可行解。?若LP LD （）（）分别有
可行解'x u 、对（LP ）的任一可行解'x u 、，有定理'cx ub ≤，
，表明（LP ）极大化的目标函数在可行域上有上界，不可能无界。而一个有可行解的线性规划有不可能为上界的情形，必然有最优解，从而（LP ）必有最优解。
推论2 如果x u **、分别是LP LD （）（）的可行解，且cx u b **=，则x u **、分
别是LP LD （）（）的最优解。
证明：对LP （）的任一可行解x ，LD （）的任意可行解u ，有定理1，知：
cx u b cx ub cx u b ****≤=≥=， 表明cx u b **、分别是LP LD （）（）的目标函数
的最优解。因而分别是的最优解。
定理14.1.3 若对偶规划LP LD （）（）中有一个最优解，则另一个也有最优
解，并且两者的目标函数最优解相等。
证明：若LP （）有最优解，引进松弛变量()10T
m y y y =???≥，
将LP （）标准化的max 0cx
Ax Iy b x y ??
+=???≥?：，
即()
()max 0,,0
T cx Y x A I b y x y ?+????=? ????
?≥?
， 亦即（*）max 0
cv Av b v ???
=??≥??
其中()1000T m ?=??? ()()
1,0T v m c c ?+= (),A A I = x v y ??= ???
这样（LP ）就化成了等价的（*）问题，由于假定（LP ）有最优解，则（*）亦有最优解
从而可用单纯形式法（包括处理退化的情形的方法）及到（*）的一个基本最优解。设其基变量为：11p s j j i i x x y y p s m ??????+=，，。对应的最优解为B ，满足
0B b +≥，在其中取出基变量对应的分量
100p j j s c c ??????个
，组成的准向量极为B c 即()
100p B j j c c c ，=??????。
下面证明基B 的单纯形乘子1B c B -?=是LD （）的最优解。
先证明1B u c B LD *-=是（）的可行解。故v *使用单纯的形法的()*的一个最优基可行解。则所有判别数应为非负。
记10B c B A c --≥或()()10T B c B A I c -≥，， 亦即110B B c B A c c B --≥≥、 即
0u A c u **≥≥、 故1B u c B *-=LD 是（）的可行解。
再证明1
B u c B *
-= LD 是（）的可行解 设x v y **
*??
= ???
0x Ax b x x LD ***≤≥则满足：、，即是（）的可行
要证u *是（LD ）DE 的最优解，有推论2可知，只需证明 **cx u b =
而x *中只有基变量1p j j x x **???才可能不等于0，所以11p p
j j j j cx c x c x ***
=+???+ 又因1B b -为是v *中基变量取值所组成的m n 维向量。 即(
)111
p s
T
j j i i B b x x y y ，-****=??????则()
1
00p T
B
j j c c
c ，=??????与1B b -的内积为：
11*1***
p p B j j j j u b c B b c x c x cx -==+???+=
又设()
1
T n
x x x
*
*
*=???，()1m u u u ***
=???将Ax b ≤ 写成()1~i i A x b i m *≤=
令()1~i i b Ax i m ω*=-=再将i A c ω≥写成()1~T j j u p c j n ≥= 令1~j j j Q u p c j n
（）*=-= 下面证明（LP ）（LD ）最优解x u 、**的互补松弛性质。 设A 的第i 行向量为()()11~j n
i i i i A a a a i n =??????=。A 的第j 列为1
j
p p ???
故已证x u 、**分别为（LP ）（LD ）的可行解。由推论2即知1B u c B *-=是（LD ）
的最优解，且两者最优目标值相等。定理的另一部分证明类似。
定理14.1.4（互补松弛性质）若一对对偶规划（LP ）（LD ）分别有最优解x u 、**
则一定有
()()01~01~T
i i i i i j j j j j
u i m b Ax Q x j n Q u p c ωω***===-===- 证明：只证后一式，前一式子类似。因为00j j Q x 、**≥≥，因此，要 0j j Q x *=成立，只需证明j j Q x 、*不同时大于零。
用反证法，若不然。设00j j Q x ，*>>，由于：0j j j Q u p c *=->有j j u p c *> 两端同乘j x *得：j j j j u p x c x ***> （14.1.3）
而除0j Q >外，其余()01,2,,k Q k n k j ≥=???≠， 于是有k k u p c *≥，
两边同乘()0k k x x **≥ 得()1,,k k k k u p x c x k n k j ***≥=???≠ （14.1.4）
()()14.1.314.1.4+ 1
1
n
n
k k
k k k k u
p x c x cx *
*
*
*==>=∑∑ (14.1.5)
由（14.1.15）两端： 1
n
k k k u p x u Ax u b **
***==≤∑ (14.1.6)
由（14.1.15）（14.1.3）两端： u b cx **> （14.1.7） （14.1.7）与x u 、**分别为（LP ）（LD ）的可行解矛盾。（定理14.1.3）故()01~j j Q x j n *==。
由此可得如下松紧关系：
原问题约束?对偶问题变量 原问题变量?对偶问题约束 （1） 若（LP ）有最优解x *，使得对指标j 满足j x *，称j 对（LP ）是松的。则对（LD ）的一切最优解u *必有j j u p c *=，称j 对（LD ）是紧的
（2） 若（LP ）有最优解x *，使得对指标j ，满足0j A *>，则称（LD ）是松的，则对（LP ）的一切最优解x *，必有i i A x b *=，称j 对（LP ）是紧的。
(3)若（LP ）有最优解x *，使得对指标i 满足i A x b *<，则称i 对（LP ）松的，
对（LD ）的一切最优解u *，必有0i A x *=，称（LD ）是紧的。
（4）若（LD ）有最优解u *使得对指标j ，满足j j u p c *>，称j 对（LD ）是松的，则对（LP ）的一切最优解x *，必有0j x *=，称j 对（LP ）是紧的。
（LD ）与（LP ）的松紧关系为：x u 、**分别是（LD ）（LP ）的最优解。
（1）若0j x *>，则j j u p c *
=。
（2）若0i u *>，则i i A x b *=。 （3）若i i A x b <，则0i u *=。 （4）若j j u p c *>，则0j x *=。
对偶松紧关系又称为互补松弛条件。下面通过一个例子说明对偶松弛关系：例14.1.4：
（LP ）123123123123max .. 222 423 0
x x x s t
x x x x x x x x x ++??++≤??++≤????≥?
引进松弛变量12y y ?，（LP ）化为： ()
123
1231123212max ..222
42201~3,0,0i x x x s t x x x y x x x y x i y y +++++=+++=≥=≥≥
用单纯形法解此问题的最优单纯形表：
表14.1.1
得（LP ）的最优解*(0,2/3,2/3)T x =
（LP ）的对偶：（LD ）1212121212min 2224121210
u u u u u u u u u u +??+≥??
+≥??+≥???≥?
由定理14.1.3的证明可知：1B u c B *-=（注此处B B c c =→原问题目标系数）
是对偶角（LD ）的最优解。现计算10(,)u u u ***
=如下：
()()1
1/3,2/31,21,11/3,1/32/3,1/32,1B u c B B -*-??
????==== ? ? ?-?????
?
因(0,2/3,2/3)T x *=，则230,0.x x **
>>则由松紧关系，必有下取等号：
2212331
2
21
21
u p c u u u p c u u ****
**=?+==?+=
将12
,u u **带入此二式，即知等式成立。 又*11,33u ??= ???
即**120.0u u >>则由松紧关系：
****
11123****
22123222
422A x b x x x A x b x x x =?++==?++= 将***123
,,x x x 的值带入即可见等式成立。 又在上面最优表中（LP ）的松弛变量1y 为对应的判断数45，σσ有如下性质：
1***444121
1***
555122
1(,)00
1(,)00B B C B P C u u u C B P C u u u σσ--??
=-=-= ?????=-=-= ???
可见，用单纯形法迭代的到（LP )最优解时，对偶(LD)的最优解可以直接从（LD )的最优单纯形到表上得到。在问题的松弛变量（y 1y 2)的检验数就是对偶(LD )的最优解。这个结果对一般情形也成立。下面予以证明。
为求解(LP ):max 0cx Ax b x ì???
￡í??>??? ,先增加松弛变量1m y y
化为max (,)
()0(,)T x cv v c c o y slp Av b
v A A I ???==? ????
?
=??
≥=???
用单纯形求解。及到一广判别数全非负的最优基本解。对松弛变量y 的判别
数
11B n n i n i C B P C σ-+++=- 又 y i 在目标函数中寻数0n i
C
+= p n+I 为第I 分量为1的m 准单位向量。
(i=1~m)且()1***
1B m C B u u u -== 故1*(1~)n i n i n i
i CB P C u i m σ-+++=-==
即用单纯法迭代的到（slp ）的最优化，松弛变量i y 的判别数n i σ+就是*u 的第i 分量*(1~)i u i m =，*1B u C B -=就是的最优解。
故*u 可以直接的（slp ）的最优单纯表上得到。
一对相互对偶的线性规划（LP ）（LD ）之间解的可能构形有哪些？这可用对偶定理来回答，因为（LP ）（LD ）都单独分别有三种可能：
（LP ) (LD )
Ⅰ.有最优解 ….
Ⅱ.有无界解 … Ⅲ.无可行解 …
综合以上对偶定理知：（LP ）（LD ）之间只可能有下面三种情形： （1）两者都有最优解。 （2）两者都没有可行解。
（3）一个问题有无界解，另一个问题没有可行解。 其他情形都不可能出现了，因为，一个问题有最优解，另一个问题有无界解，或一个问题有最优解，另一个问题无可行解，将与定理3矛盾。
如果两个问题都有无界解，将与推论1矛盾。
14.2 非对称及混合型对偶规划
14.2.1（SLP ）的对偶规划
在单纯形法中，我们总是先将（LP ）问题化为（SLP ）求解，因此，有必要研究（SLP ）的对偶规划问题。
① ② ③
先将（SLP ）：m a x 0cx Ax b x ??=??≥? 改写成（LP ）max 0
cx
Ax b Ax b x ??≤?
?-≤-??≥?
再根据（LP ）的对偶定义写出其对偶规划：
(LD) min 0,0b vb A vA c v ωωω-??
->??>>?
这就是(SLP)的对偶线形规划，这一线形规划问题还可进一步问题化引进m 维行向量u 。
那么u 就不一定有非负约束了。于是将上面（LD)写成：
（SLD)
{
min ub
uA c ≥u 无限制
所以，只要n 满足uA c ≥。则u 就称为对偶(SLD)的可行解。前面，我们已证明了(LP)与(LD)这对对偶规划具有对合性质 。
因为： 上面(SLP)与(LD)是等价的,而 (SLP) 与(LP)是等价的。(LP)（亦即(SLP)的对偶是(LD)亦即(SLD)的可行解 。而(LP)与(LD)是对称对偶规划，具有对合性。即(LD)即(SLD)的对偶是(LP)(亦即(SLP)）。故知:(SLP)与(SLD)这对对偶规划也具有对合性质的。
(SLP)与(SLD)是非对称的对偶规划，因为：(SLP) 约束未取等号。对应对偶变量u 无符号限制。(SLD)的约束未取
14.2.2 (SLP).(SLD)的对偶定理
下面我们把前面已证明的关于(LP) (LD)的一些定理，考虑是否对(SLP) (SLD)也成立。
定理14.2.1对(SLP)的任意可行解x ，(SLD)的任意可行解u 。有：cx ub ≤ 证明：(0)Ax x buA c ub uAx cx ≥=≥∴=≥
推论14.2.1'：若(SLP)有无界解，则(SLD)无可行解；若(SLD)有无界解，则(SLP)无可行解。其逆不成立。
定理14.2.2：对偶(SLP),(SLD)有最优解两者同时有可行解。
推论14.2.2'：若x*分别是(SLP),(SLD)的可行解，且cx*=u*b 。则x*,u*分别是(SLP),(SLD)的最优解。（这些结论的证明与(LP),(LD)类似结论证明一样）
定理14.2.3：若(SLP),(SLD)中一个有最优解，则另一个也有最优解，并且两者的目标函数值相等。
证明：设(SLP)有最优解。则必有最优基可行解（基本定理 2.2.2）从而可用单纯形法（包括处理退化，循环的方法）得到(SLP)的一个基本最优解x*,设最优基为B*。
那么我们证明单纯形乘子1
***B c B u π-==是对偶（SLD)的最优解。根据单纯形法原理，对应(SLP)的最优基B*的判别数向量()**0B c B A c -≥最优解为：
1***,0B x B b x -== 从而1
***B u c B -=满足*u A c ≥是(SLD)的可行解。
并且目标值1
******
B B B u b c B b c x cx -===根据上面的推论即可知：1
**B c B -是（SLD ）的最优解。因此我们证明了14.2.3若(SLP)有最优解，则(SLD)必有最优
解。反之，若(SLD)有最优解u*,则*****0,0.v w v ωω?≥≥=-且**,v ω是
(LD)：
min ..0,0b vb s t A vA c v ωωω-??
-≥??≥≥?
的最优解。 (LD)的对偶为(LP) max cx Ax b Ax b ??
≤??-≤-?
亦即(SLP) max 0cx Ax b x ??
=??≥?
根据第一节的定理14.1.3知，(LP)即(SLP)有最优解。故得证。 我们由上面定理证明过程可见：若B*是(SLP)的最优基，那么单纯乘子1
*
*B c B -就是(SLD)的最优解。因此我们定义：
定义14.2.1：对于(SLP)的一个基B ，若单纯到乘子1
**B c B -为对偶(SLD)的可行解，则称B 为对偶可行基。
若1
**B c B -为对偶(SLD)的最优解，则称B 为对偶最优基。上面定理14.2.3的证明表明：(SLP)的最优基B*必是对偶最优基。这个结论在后面的对偶单纯形法迭代中将是十分重要。
定理14.2.4：(SLP),(SLD)的可行解x*,u*分别是最优解?()**0A c x ω-?=
证明：?若x*，u*分别是(SLP)(SLD)的可行解，且满足()**0u A c x -=则
****cx u Ax u b ==(x*可行，Ax*=b)
由推论14.2.2'可知：x*,u*分别是(SLP),(SLD ）的最优解。
我们下面在细看一下这里的松弛条件：()()*
*
**1
0n
j j j i A c x f c x ωω=-=-=∑
且
()
**0,1J j j x p c j n ω≥≥=???因此上式等价于：
()()()*
*01*j j j p c x j n ω
-==???
（*）式表明：若*j j p c ω>，则必有x*j=0.若x*j>0,则必有u*p j =c j 从而表出如下的松紧关系：
（1）若(SLP)有最优解x*使前对指标j 满足x*j >0则称j 对（SLD)是松的。对(SLD)的 一切最优解u*就必有u*p j =c 称j 对(SLD)是紧的。
（2）若(SLD)有最优解u*,使前对指标j 满足u*p j >c j.则称j 对(SLD)是松的。对(SLP)的一切最优解x*就必有x j *=0.称j 对(SLP) 是紧的。
从上述对偶定理知：(SLP).(SLD)这一对对偶规划的解之间也有下面三种情形：
（1） 两者都有最优解。 （2） 两者都没有可行解。
（3） 其中一个有无界解，而另一个无可行解。
除此之外，不能再有其他的形式了。其理由与4.1一样。
14.2.3混合型对偶线形规划
上面我们已经讨论过了对称及非对称型对偶规划.但实际问题中回出现两种情形共存的问题,即所谓混合型的对称规划问题.
定义14.2.2:对于一个线形规划问题,若它的未来包括两个部分,一部分的约来是方程式i i X b θ=.另一部分约来是不等式i i A x b ≤ (i i A x b ≥) ,其变量也分两类,其一类有非负限制,另一类没有限制，称这种类型的问题为混合型问题.
考虑混合型问题：
()()()()()
()()()()()()()1122max 121..b 11121222221220c x c x s t x x A A A x x b A x x ??+????
+≤+=≥?????
，无限制
依照定义1写出(LP)的对偶(LD)如下：
(1)(1)(1)(1)(1)(1)(1)(21)(22)(1)112121(1)(21)(22)(2)
122222(1)(21)(22)(2)122122(1)(21)(22)min[]0,0,0u b u b u b A u A u A u c A u A u A u c
A u A u A u c u u u ì?+-???+- ????+- í???---?????吵 ??
在此(LD)中令()()()212221222,0,0.u u u u u -=≥≥则u(2)就没有符号限制，从而化为下面形
式：
(1)(1)(2)(2)(1)(2)(1)1121(1)(2)(2)
1222(1)(2)min[]0,u b u b A u A u c
A u A u c u u 无限制?+?+≥??+=??≥?
根据上面求混合型对偶规划过程，我们总结出混合型对偶 的特点如下对偶表：
表14.3.1
（I ）
（II ） （LD ）
例14.2.1：写出下面线形规划的对偶规划：
12341234123412342213min 4135.358
426101511370,0,,f x x x x s t x x x x x x x x x x x x x x x x R =+++??+--=??
-++≥??--++≤-??≥≥∈?
123123123123123min 2.2
122
0,0,f x x x s t x x x x x x x x x x x x R =++??++≤??
-+=?
?++≥??≥≥∈?
解：先将问题转化为统一形式：即最小化问题约束条件为“ =” 或为“≥” 有：
12341234123412342213min 4135.358
426101511370,0,,f x x x x s t x x x x x x x x x x x x x x x x R =+++??+--=??
-++≥??--++≤-??≥≥∈?
根据上面的对偶表，其对偶问题有了3个对偶变量123,,u u u 4个约束方程 具体形式如下：
123123123123123231max 8107..
41543231335561,0,Z u u u s t u u u u u u u u u u u u u u u R =++??++=??--≤?
?
-+-≤??-+-=?
>∈??
1u 无限制→对应第一方程取“=”故无限制
(对应第2，3方程“≤”号故取非负
先令22x y = 20y ≥并将原问题化为统一形式：
123123123123123max 2..21220,0,x y x s t x y x x y x x y x x y x R --??-+≤??
++=??-+-≤-??≥≥∈?
在根据上面的对偶表写出其对偶规划为：
（1） （2）
123123123123132min 202..21210,0,u u u s t u u u u u u u u u u u u R +-??+-≥??
-++≥-??+-=??≥≥∈?
对应原来方程“≤” 对应的原方程“=” 注意：（1）写出的对偶问题，其系数矩阵必须是原问题的系数矩阵的转置。 （2）写出对偶的另一步，问题统一化形式是必须的，否则容易出错。
14.3 对偶单纯形法
14.3.1 什么是对偶单纯形法
我们已经知道，用单纯形法求线形规划(SLP)最优解，相当于求一个基B ，使得满足基变量取值10B b -≥ 且判断数向量10B C B A C --≥ 。这样的基B 是最优基。
由当10B b -≥时，B 是可行基。
当10B C B A C --≥现B 是最优基，当B 既是可行基，又是对偶可行基时。（即
1,B A C C B ππ-≥=B 是对偶可行基
我们前面介绍的单纯形方法，是在10B B -≥的前提条件下，通过可行基的逐次迭代，直到条件10B C B A C --≥成立，这时B 既是可行基有是对偶可行基，因而B 是最优基。
现在我们考虑用下面的方法求（SLP)的最优基。在条件10B C B A C --≥成立的前提条件下，通过对偶基的逐次迭代直到条件10B b -≥成立，那么此B 既是对偶可行基，又是可行基，因而是最优基。沿这一途径求得(SLP)的基本最优基的方法，称为对偶单纯形法。
14.3.2对偶单纯形法的迭代原理
用对偶单纯形法求解(SLP)，起始于一个对偶可行基B ：10B C B A C --≥ ，也可以列出一张单纯形表，但表中最后一行检验数行非负，即()01j G j n ≥=???.
若满足10B X B b -=≥则已得到最优解，终止。若1B X B b -=有负分量，那么以此基本解1B X B b -= 为基础，逐次减少X B 中负分量的个数，直到0B x ≥，就得到最优解，或者判断原问题无可行解为止。
与单纯形法一样，对偶单纯形法也是要找出一个枢轴。来进行旋转变换，因而我们可以直接用单纯形法中的函代公式即：
1lj i k j jl j J
lk lk lk
j k
b x x x αααα∈≠++=∑
这样，由于单纯形法可以在表上进行对偶单纯形法。
当然，两者并不是完全相同的，而有各自的特点。我们分三点讨论： （1） 枢轴选择：单纯形法中要求0k α>，对偶单纯形法中要求0lk α<。 （2）入基出基变量选择：单纯形法中先定入基变量k x 即：先定k ，后定出
基变量ij x ，即后定L;而对偶变量jl x 形法中，先定出基变量L ，后定入基变量k.。 （3） 表格形式中数据：单纯形法中，总是非负的，逐次迭代，减少检验数行中负元素的个数；
对偶单纯形法，检验数行中负元素总是非负的，逐次迭代，减少基变量B x 取值中负元素的个数。
当我们了解了对偶单纯形法和单纯形法之间这些关系以后，我们可以研究对偶单纯形法。考虑以下几个问题：
(1)怎样选取出基变换当12(,,)T B m x b b b = 中负元属时，取：
{}1min
0l
i
i m
b
b ＃=<则确定第L 个基变换。ji
x
为出基变换。
（2）怎样选取枢轴元lk α为使变换后的新变量k x 不再取负值，应使
0,0,
l l lk
b
b α
><故选取0lk α<。
(3) 入基变换k x 的选取：因对偶单纯形法是通过对偶可行基的迭代，所以迭代后所有检验数非负。即'0,0j j σσ≥>
根据迭代公式'
,(1,2)lj j j k
lk j n ασσσα=-=
因00,0,0,0k j k j σσσσ≥≥<≥，则j k lk lj
σσ
αα≤--，当0ij
α
≤时
因此选取 1min 00j k k lj j n lj lj
σσ
θααα≤≤????=<=>?
?--???? 则确定k x 为出基变换
（4）目标函数迭代公式
由于对偶单纯形法的迭代并不是在（SLP)的可行基上进行的，因此考虑(SLP)的目标函数迭代没意义，而应考虑对偶目标值的迭代公式。若迭代后对偶可行基为B,
故1B U C B -=是对偶可行解。
设对偶目标值为z ?
,则1
'1
m
B ji i i Z ub
C B b C b ?-====∑
设迭代后对偶可行基为B ，对偶目标值为Z ,则： 1B Z C B b ?-=，1,11(,)B j ji ji jm C C C C C -+= 根据单纯形法的迭代公式：（3，2，13） 11111(,)T k l mk l m l lk lk lk
b B b b b b b σσ
ααα-=--
与B C 做内积：1l
B k
k lk
Z B b Z Z b
C θσσα
?
-?
==-
-=
其中θ是新基坐标下Z 的取值
l k lk
b x θα
==
11
()m
k k k
B k ij ik i B
C C C C P σ
α-==-=-∑ 因0,0,lk l
b
α<<因此当0k
σ>时Z Z
?
<
可见，对偶单纯形法迭代后必将使对偶目标值减少。剩下的问题就是要考虑对偶单纯形法的终止准则。
定理14.3.1 设B 是(SLP ）的一个基（或是一个对偶可行基），且1B b -中有负分量，即
0,(1),s b s m ?<≤≤若第s 行中的所有系数0,(1,2,),sj j n α≥=则(SLP)无可行解。
证明：对于B ，11B AX B b --?=，即,(1,2,)i ji ij j j J
x b x i m α∈=-=∑
其中J 是非变换下的集合。
（反证法）如果定理中条件成立时，(SLP)有可行解代入式中的方程有： 000s js sj j j J
x b x α∈=-<∑ ，00js x <与0x 是可行解矛盾。
因此，对偶单纯形法的终止准则是：若对偶单纯形法中基变换10B x B b -=≥ ，则B 是最优基，得到最优解。
我们给出定义。
定义14.3.1： 若对偶可行基B 对应的所有非基变量判别数1B C B - ，则称对偶可行解0j σ>是退化的对偶可行解。
对于非退化的对偶可行解。我们有定理：
若(SLP)有一个新始对偶可行基B ，且1B C B -是非退化的对偶可行解，用对偶单纯形法迭代时，若每次得到的对偶可行解都是非退化的，则对偶单纯形算法必在有限次迭代后终止于下述两种情形之一：或者判断(SLP)无可行解，或得到(SLP)的一个基本最优解。
证明：设对偶单纯形法迭代进行到某一步时，若某基变换js x 的取值0s b <，
且0(1,2,)sj j n α≥=。则由定理4，3，1知(SLP)无可行解。终止。否则，可进行对偶单纯形法迭代，按上面介绍的枢轴元选取方式，选取枢轴元素0lk α<。
因假定每次得到的对偶可行解均是非退化的，即非基变量的检验数0j σ>，于是有对偶目标值：00k Z Z Z θσ=< 因（0l
lk
b θα=
> ）
这表明每迭代一次对偶目标函数值必然减少，所以迭代过程中对偶可行基不会重复出现，而对偶可行基的数目是有限的。对偶单纯形法是在对偶可行基上进行的，因此必须在有限步内完成。否则，若迭代过程是无限的，就必然会出现两次迭代有同一个对偶可行基的情形。此时，它们对应的对偶单纯形法目标值相等。这是不可能的。这样就证明了对偶单纯形法经有限次迭代后或者判断(SLP)无可行解，或者得到(SLP)的最伏基本可行解，因而对于对偶可行解非退化的情形，对偶单纯形法必在有限步内终止。
14.3.3 对偶单纯形法的迭代步骤
设已知一个对偶可行基B 对应11()T m x B b b b -==B 及其对应单纯形表，表中判别数0(1)j j n σ≥=
步骤１若0B x ≥，则B 为最优基，求出了(SIP)的基本最优解，迭代终止。否则令{}1min 0l i i m
b b ≤≤=< 定出L
步骤２若0,1lj j n α≥= ，则 （SUP)无可行解，迭代终止。否则 令
1min 0j k k lj j n lj lj σσ
θααα≤≤??-??=<=?
?--????
定出k
步骤３ 以lk α为枢轴元进行枢轴运算，用公式
(0)(0,,0)lj
lj
lk
ik ij
ij lj lk
j n i m i l j n αααα
αααα'=='=-=≠=
例14.3.1 用对偶单纯形法求解：123123
123123max(345)
2352260,0,0
x x x x x x x x x x x x ---??++≥??++≥??≥≥≥?
解：引进剩余变量450,0x x ≥≥则转化为
1231234
1234max(345).2352260i x x x st x x x x x x x x x ---??++-=??++-=??≥?
取基变换45,x x 基阵45(,)B p p =对应1(0,0),(0,0)B B C C B -==。 因1233,4,5C C C =-=-=-
故判别数1
0(1,25)j B j j j C B P C C j σ-=-=-≥= 可见B 不是对偶可行基进行对偶单纯形法迭代原始表
为使基变量对应表中的列向量构成基矩阵将表中的两行元素都乘-1即可。 第一步 求L 使之满足：}{2min 5,660l b b =--=-=< 确定L=2
第二步 求k 使之满足：53453
min ,,(2)(2)(1)2k l x θθ??++++==
=??-------??
确定k=L 第三步 以21α为枢轴元进行旋转变换，1x 入基5x 出基，设新单纯形表如下
第一步：求L,使{}1min 20l b b =-=<，定出 L=1
第二步：求k ，使21
3.5 1.51
min ,,(1)( 2.5)(0.5)1
k θθ??===?
?------??定出k=2.
第三步：以121α=-为枢轴元进行枢轴运算设新单纯形表如下：
根据对偶定理知：(SLP)的目标最优值与对偶目标最优值相等。因此原用的最优目标值为
2*11f z ==-
如果取基阵B=I 这时(0,0,0)B C =，因此有：
10,(1,2,)j B j j j C B P C C j n σ-=-=-≥=从而1B C B -就是对偶可行解，这样就得到了
一个初始对偶可行基，然后就可以采用对偶单纯形法求解远问题。
上面举的例就是目标函数系数全为负的剩余变量解法。因此不在举例说明。
14.3.4人工约束方法
假定B 是（SLP)的一个基，B 既不是可行基，也不是对偶可行基。在这种情形下怎样进行对偶单纯形法迭代求解原问题呢？
先将约束AX=b 化为等价形式11B AX B b --=得到一个与(SLP)等价的问题： max (1,2,)0,(1,2,)ji ij j i j J j
f cx x x b i m x j n α∈?
=??
+==??
?≥=?∑
增加一个变量1n x +和一个约束变量1j n j J
x x M +∈+=∑
其中M 为一个充分大的正数，得到新问题如下
1max ,(1,2,)
0(11)ji ij j i j J j n j J
j f cx x x b i m x x M x j n α∈+∈=?
?+==??
?
+=?
?
≥=+??
∑∑ 此中有m+1个等式约束和n+1个变量。我们称问题I 的扩充问题，易见，121,,,j j jm n x x x x + 就是（II)的一组基变量。
设（I)对应基B 的判别数为,(1)j j n σ=
由判别数定义有：1
,(1)m j ji ij j i c c j n σα==-=∑
再设（II)在基变量11,j jm n x x x + 下对应判别数为
，因1n x +在?(11)j j n σ=+
(II)的目标函数中的系数为0，故11
1
?(1)m m
j ji ij j ji ij j j i i c c c c j n σ
αασ+===-=-==∑∑ 因B 既不是(I)的可行基，也不是对偶可行基。所以(I)中的i b 有负值，判别数j σ中也有负值。从而由上面的推导知(II)的基变量所对应的基既不是(II)的可行基，也不是对偶可行基。这是因为：
这一组基变量取值为1m b b ， M,其中有负值，判别数1??(1),0j j n j n σ
σσ+=== ，其中也有负值。 下面我们证明：(II)中以1n x +为出基变量，k x 为入基变量做枢轴运算后，扩充问题(II)在基变量1,j jm k x x x ，就对应了一个对偶可行基。其中k 满足：
{}1min 0k j j n
σσ≤≤=<
在(II)中1n x +是第m+1个基变量，以1n x +为出基变量， 即表明L=m+1.而这一行的约束为1j n j J
x x M +∈+=∑
即非基变量的系数全为1。那么1,1m k α+=， 以1,m k α+为枢轴元，进行枢轴运算得：
基变量为 1,j jm k x x x ，判别数为()11
1?m j j j k
m k ασσσα+-+'
=-1,,,1m j j j k n ≠+ 当
时
即当j x 是迭代后的非基变量时，有：
()1???,(,,1)j j k j k m j j j k n σσ
σσσ'=-=-≠+ 枢轴运算后，1n x +为非基变量，检验数为：
()1,111,1
?????001
m n n n k k k k m k ασ
σσσσσα++++'=-=-=-=-> 新基变量对应的判别数均为0。即
(){}
11?0(,),min 00j m k j j j n
j j j k σσσσ≤≤'===<< 由于
故有：()()()111?0(,,1)?0(1)
?0(,)J J k m j k j m j j j k m j n j j j k σσσσσσ'?=-≥≠+?
'?
=->=+??
'?==?
可见，（II)经过上面的枢轴运算，所得新基对应的判别数全部非负，即
因而(II)有了初始对偶可行基，从而可以采用对偶单纯形法求解扩充问题(II)了。
由于扩充问题(II)有对偶可行解，那么由对偶定理，(II)的目标函数有上界，因而扩充问题(II)不可能有无界解，那么利用对偶单纯形法求解扩充问题的只有两种可能结果：或者扩充问题无可行解，或者找到扩充问题的最优解。
下面讨论扩充问题与原问题的关系：
１）若扩充问题没有可行解，则原问题也没有可行解。
()?0,(11)
j j n σ'
≥=+
证明：（反证法）若(II)无可行解，而（I)有可行解
1111()(,)0
T T n n n n j j J
x x x x x x x x M x ????????
?++∈===->∑ 作其中 则x ?是扩充问题(II)的可行解，矛盾。故成立。
２）若扩充问题有最优解
111(),()T T
n n
x x x x x x ******+== 则是原来的的可行解。用x *代入目标函数后，若()f x *与M 无关。则x *是原问题的最优解。
例14.3.2：用人工约束的方法求解下面问题： 1234123123414max (1.1 2.2 3.3 4.4).252340f x x x x st x x x x x x x x x =+-+??++=?
?
+++=?
?≥?
要求从基12(,)B p p =开始。
111211216(,),,12111B B p p B x B b ---??????===== ? ? ?--??????
解：()()11011,()004411B B c B c B A C σ--∏===--=- 现在用人工约束方法求解这个问题。新增人工变量5x ，增加约束
345x x x M ++=
扩充问题如下
1234134234345max (1.1 2.2 3.3 4.4)
336310
i f x x x x x x x x x x x x x M
x =+-++-=-+=-++=≥ 列出扩充问题单纯形表如下：
以人工变量5x 为出基变量，4x 为入基变量，4min 0,4k j j k σσσσ=<=∴= 作枢轴运算得新表如下
线性规划的对偶原理 3.1 线性规划的对偶问题 一、 对偶问题的提出 换位思考 家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收入最大 213050max x x z += ?? ? ??≥≤+≤+0 ,50212034212121x x x x x x 某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。他 需要与家具厂谈判付给该厂每个工时的价格。如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给他， 又使自己付的租金最少。 目标:租金最少；1y -付给木工工时的租金；2y -付给油漆工工时的租金 2150120min y y w += 所付租金应不低于家具厂利用这些资源所能得到的利益 1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收 入 502421≥+y y 2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收 入 30321≥+y y 3）付给每种工时的租金应不小于零 0,021≥≥y y 二、 原问题与对偶问题的数学模型 1. 对称形式的对偶
原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。 原问题： ?? ? ??≥≥=0min X b AX CX z 对偶问题： ?? ? ??≥≤=0max Y C YA Yb w 2. 非对称形式的对偶 若原问题的约束条件全部是等式约束（即线性规划的标准型），即 ?? ? ??≥==0min X b AX CX z 则其对偶问题的数学模型为 ?? ? ??≤=是自由变量Y C YA Yb w max 可把原问题写成其等价的对称形式： min z =CX AX ≥b AX ≤b X ≥0 即 min z =CX ? ? ????-A A X ≥??????-b b X ≥0 设Y 1=(y 1,y 2,…,y m ), Y 2=(y m+1,y m+2,…,y 2m )。根据对称形式的对偶模型，写出上述问题的对偶问题：
线性规划的对偶问题 Last revised by LE LE in 2021
第二章线性规划的对偶问题 习题 写出下列线性规划问题的对偶问题 (1) max z ＝10x 1＋ x 2 ＋2x 3 (2) max z ＝2x 1 ＋ x 2 ＋3x 3 ＋ x 4 st. x 1＋ x 2 ＋2 x 3 ≤10 st. x 1 ＋ x 2 ＋ x 3 ＋ x 4 ≤5 4x 1＋ x 2 ＋ x 3 ≤20 2x 1 － x 2 ＋3x 3 ＝－4 x j ≥0 （j＝1,2,3） x 1 － x 3 ＋ x 4 ≥1 x 1 ，x 3 ≥0，x 2 ，x 4 无约束 (3) min z ＝3x 1＋2 x 2 －3x 3 ＋4x 4 (4) min z ＝－5 x 1 －6x 2 －7x 3 st. x 1－2x 2 ＋3x 3 ＋4x 4 ≤3 st. －x 1 ＋5x 2 －3x 3 ≥15 x 2 ＋3x 3 ＋4x 4 ≥－5 －5x 1 －6x 2 ＋10x 3 ≤20 2x 1－3x 2 －7x 3 －4x 4 ＝2 ＝ x 1 － x 2 － x 3 ＝－5 x 1≥0，x 4 ≤0，x 2， ，x 3 无约束 x 1 ≤0， x 2 ≥0，x 3 无约束 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3 1 'x代换。 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x 1＋2x 2 ＋ x 4 ≥3 3x 1＋ x 2 ＋ x 3 ＋ x 4 ≥6 x 3 ＋ x 4 ＝2 x 1 ＋ x 3 ≥2 x j ≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x 1 ＋x 3 ＋ x 4 ≤8 y 1 2x 1＋2x 2 ＋x 3 ＋2x 4 ≤12 y 2 x j ≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x 1＋4 x 2 ＋2x 3 ≤60 2x 1＋ x 2 ＋2x 3 ≤40 x 1＋3x 2 ＋2x 3 ≤80 x j ≥0 （j＝1,2,3）（1）写出其对偶问题
第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4 st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤5 4x1＋x2＋x3≤20 2x1－x2＋3x3＝－4 x j≥0 （j＝1,2,3）x1－x3＋x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； 'x代换。 （4）模型中全部x1用3 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋x4≥3 3x1＋x2＋x3＋x4≥6 x3 ＋x4＝2 x1 ＋x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；
第二章 线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 ⑴ max z = 10x i + X 2 + 2x 3 st. x i + X 2 + 2 X 3W 10 4x i + X 2 + X 3 W 20 X > 0 (j = 1,2,3) (3) min z = 3x i + 2 X 2 — 3x 3 + 4x 4 st. x i －2x 2+ 3x 3+ 4x 4W 3 X 2 + 3X 3 + 4X 4》一5 2x i — 3x 2 — 7x 3 — 4x 4= 2 = x i >0, X 4W 0, X 2，, X 3 无约束 (2) max z = 2x i + x 2+ 3x 3+ x 4 st. x i + x 2+ x 3 + x 4 W 5 2x i － x 2+ 3x 3 =－ 4 X i — X 3 + X 4> i X i , X 3 > 0, X 2, X 4 无约束 (4) min z =— 5 x i — 6x 2— 7x 3 st. — X i + 5X 2— 3X 3 > i5 — 5X i — 6X 2+ i0X 3 W 20 X i — X 2 — X 3=— 5 X i W 0, X 2>0 , X 3 无约束 2.2已知线性规划问题 max z = CX , AX=b , X >0。分别说明发生下列情况时，其对偶问题的解的 变化： (1 )问题的第k 个约束条件乘上常数 入(炉0); (2) 将第k 个约束条件乘上常数 入(苗0)后加到第r 个约束条件上； (3) 目标函数改变为 max z = 2CX (入工0)； 4)模型中全部 X i 用 3 X'i 代换。 2.3 已知线性规划问题 min z = 8X i + 6X 2+ 3X 3+ 6X 4 st. x i + 2X 2 + X 4》3 3x i + X 2 + X 3+ X 4 A 6 X 3 + X 4= 2 X i + X 3 A 2 X j A 0(j =i,2,3,4) (1) 写出其对偶问题； (2) 已知原问题最优解为 X*=(i ，i ，2，0) ，试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题 min z = 2X i + X 2+ 5X 3+ 6X 4 对偶变量 st. 2X i + X 3+ X 4W 8 y i 2X i + 2X 2+ X 3+ 2X 4W i2 y 2 X j A 0(j =i,2,3,4) 其对偶问题的最优解 y i *=4； y 2*=i ，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题 maX z = 2X i + 4X 2+ 3X 3 st. 3X i +4 X 2+ 2X 3W 60 2X i + X 2+ 2X 3W 40 X i + 3X 2+ 2X 3W 80 X j A 0 (j = i,2,3) ( i )写出其对偶问题 ( 2)用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； ( 3)用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶 问题的解； ( 4)比较( 2)和( 3)计算结果。 2.6已知线性规划问题 max z = 10x i + 5x 2
用对偶单纯形法求解线性 规划问题 The final edition was revised on December 14th, 2020.
例4-7用对偶单纯形法求解线性规划问题. Min z =5x1+3x 2 .-2 x1 + 3x 2 ≥6 3 x1 - 6 x 2 ≥4 Xj≥0（j=1,2） 解：将问题转化为 Max z = -5 x1 - 3 x 2 . 2 x1 - 3x 2+ x 3 = -6 -3 x1 + 6 x 2+ x 4 ≥-4 Xj≥0（j=1,2，3,4） 其中，x3 ，x4为松弛变量，可以作为初始基变量，单纯形表见表4-17. 表4-17 例4-7单纯形表 在表4-17中,b=-16<0,而y≥0,故该问题无可行解. 注意: 对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,且所有检验数均为负的情况.
若原问题既无可行基,而检验数中又有小于0的情况.只能用人工变量法求解. 在计算机求解时,只有人工变量法,没有对偶单纯形法. 3.对偶问题的最优解 由对偶理论可知,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,得到对偶问题的最优解. (1)设原问题(p)为 Min z=CX . ???≥=0X b AX 则标准型(LP)为 Max z=CX . ???≥=0X b AX 其对偶线性规划（D ）为 Max z=b T Y . ???≥=0X b AX 用对偶单纯形法求解（LP ），得最优基B 和最优单纯形表T （B ）。对于（LP ）来说，当j=n+i 时，有Pj=-e i ，c j =0 从而，在最优单纯形表T （B ）中，对于检验数，有 （σn+1，σn+2…σn+m ）=（c n+1，c n+2…，c n+m ）-C B B -1（Pn +1,Pn+2…,Pn+m ）=- C B B -1 (-I)
线性规划原问题与对偶问题的转化及其应用 摘要 线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解. 关键词：线性规划；原问题；对偶问题；转化
Linear Programming is the Original Problem and the Transformation of the Dual Problem and Applications Abstract: Linear programming in operational research is research earlier, rapid development and wide application, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Can from different angles to linear programming dual problem for policy makers to provide more scientific theory basis. This article mainly probes into the linear programming problem and the relationship between the dual problem, linear programming problem and the transformation of the dual problem, the application of linear programming dual problem. This article is the complex of the original problem into its dual problem to be solved, simplifies the linear programming problem, enables us to rapidly find the optimal solution of linear programming problem. Keywords: linear programming; the original problem; the dual problem; conversion
线性规划的对偶问题文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-
第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4≤5 4x1＋ x2＋ x3≤20 2x1－ x2＋3x3＝－4 x j≥0 （j＝1,2,3） x1－ x3＋ x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3无约束 x1≤0， x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3 'x代换。 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋ x4≥3 3x1＋ x2＋ x3＋ x4≥6
x3 ＋ x4＝2 x1 ＋ x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋ x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。
线性规划原问题与对偶 问题的转化及其应用 Document number：WTWYT-WYWY-BTGTT-YTTYU-2018GT
线性规划原问题与对偶问题的转化及其应用 摘要 线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解. 关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDu alProblemandApplications Abstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandw ideapplication,themethodisanimportantbranchofmature,目录
1引言 线性规划问题是运筹学里的一个重要的分支，它的应用比较广泛，因而是辅助人们进行现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题则称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的内在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进行分析，从而使管理者能够间接地获得更多比较有用的信息. 2文献综述 国内外研究现状 在所查阅到的国内外参考文献[1-15]中，有不少文章是探讨了原问题转化为对偶问题的方法以及对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在[1]、[10]中主要介绍了线性规划中原问题与对偶问题中的一些基本概念，探究了实际问题中的数学模型以及解.孙君曼，冯巧玲，孙慧君，李淑君等在[2]中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在[3]、[5]中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在[6]、[8]中用不同例子来说明了原问题转化为对偶问题的必要性.崔永新等在[9]、[15]中探讨了对偶问题的相关定理以及对偶问题的可行解和最优解之间的若干性质.李师正，王德胜在[11]中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，孙文喻等在[12]、[14]中
线性规划的对偶问题 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
第二章线性规划的对偶问题 习题 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4≤5 4x1＋ x2＋ x3≤20 2x1－ x2＋3x3＝－4 x j≥0 （j＝1,2,3） x1－ x3＋ x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3无约束 x1≤0， x2≥0，x3无约束 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； 'x代换。 （4）模型中全部x1用3 1 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋ x4≥3 3x1＋ x2＋ x3＋ x4≥6
x3 ＋ x4＝2 x1 ＋ x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋ x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量0>* i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量0=* i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0线性规划的对偶问题及其经济含义
线性规划的对偶问题及其经济含义 信息工程学院 数学121 12421001 崔旭
在线性规划早期发展中最重要的发现就是对偶问题，即每一个线性规划问题(称为原始问题)都有一个与它对应的对偶线性规划问题（称为对偶问题）。对偶理论主要研究经济学中的相互确定关系，涉及到经济学的诸多方面。产出与成本的对偶、效用与支出的对偶，是经济学中典型的对偶关系。当然，经济系统中还有许多其他这样的对偶关系。 对偶理论有许多重要应用：在原始的和对偶的两个线性规划中求解任何一个规划时，会自动地给出另一个规划的最优解；当对偶问题比原始问题有较少约束时，求解对偶规划比求解原始规划要方便得多；对偶规划中的变量就是影子价格。 对偶定理：有一对对偶的线性规划问题，若其一有一个有限的最优解，则另一个也有最优解，且相应的目标函数值相等。若任一个问题具有无界解，则另一个问题无可行解。对称形式的对偶：原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。例如： 原问题：minz=CX AX>=b X>=0 对偶问题：max=Yb YA<=C X>=0 对称性定理：对偶问题的对偶是原问题。 弱对偶性定理：若()0 Y分别是原问题和对偶问题的可行解，则有 X和()0 C()()0 0b ≥ X Y 最优性定理：若()0 Y分别是原问题和对偶问题的可行解，且有 X和()0 ()0 CX=()0 bY，则()0 Y分别是原问题和对偶问题的最优解。 X和()0
最优对偶变量（影子价格）的经济解释：由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等。如果在得到最优解时，某种资源并未完全利用，其剩余量就是该约束中剩余变量的取值，那么该约束相对应的影子价格一定为零。因为在得到最优解时，这种资源并不紧缺，故此时再增加这种资源不会带来任何效益。反之，如果某种资源的影子价格大于零，就说明再增加这种资源的可获量，还回带来一定的经济效益，即在原问题的最优解中，这种资源必定已被全部利用，相应的约束条件必然保持等式。 用线性规则方法计算出来的反映资源最优使用效果的价格。用微积分描述资源的影子价格，即当资源增加一个数量而得到目标函数新的最大值时，目标函数最大值的增量与资源的增量的比值，就是目标函数对约束条件（即资源）的一阶偏导数。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为对资源的经济评价，表现为影子价格。影子价格是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。这个定义是基于线性规划中的合理利用有限资源以求得最好的经济效果的规划问题。影子价格正是这种假设条件中单位资源对目标极值的贡献，是资源的单位价格，反映资源在企业内部运用的贡献情况，称之为资源的影子价格。 如果目标函数是利润，这里的就是影子利润（意义不大）；如果目标函数是销售金额，这里的才是影子价格。人们通常讨论的是后一种，目标函数是销售金额，是影子价格。从对公式的解读中，人们看
第四章 线性规划的对偶理论 一、填空题 1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的线性规划问题与之对应，反之亦 然。 2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。 5．若原问题可行，但目标函数无界，则对偶问题不可行。 6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。 7．线性规划问题的最优基为B，基变量的目标系数为C B，则其对偶问题的最优解Y﹡= C B B－1。 8．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX ﹡= Y﹡b。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有 CX≤Yb。 10．若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡=Y*b。 11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 13．线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为A T 。 14．在对偶单纯形法迭代中，若某b i<0，且所有的a ij≥0(j=1，2，…n)，则原问题_无解。 二、单选题 1．线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为A形式。 A．“≥” B．“≤” C，“>” D．“=” 2．设、分别是标准形式的原问题与对偶问题的可行解,则 C 。 3．对偶单纯形法的迭代是从_ A_开始的。 A．正则解 B．最优解 C．可行解 D．基本解 4．如果z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡A。
任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。本章将讨论线性规划的对偶问题及灵敏度分析，从而加深对线性规划问题的理解，扩大其应用范围。 §1 对偶问题的一般概念 1.1 对偶问题的提出 在第一章中我们研究过一个生产计划问题，其数学模型为： 例1 (2.1) 现在，从另一个角度来考虑该问题，假设这家企业想将自己生产产品改为对外加工，此时，工厂决策者必须考虑怎样为这三种资源定价的问题。设分别代表转让两种资源和出租设备的价格和租金。定价的原则是：生产一个单位的甲产品需消耗9个单位的钢材、4个单位的铜材、3个单位的设备台时，获利70个单位；那么，将这些资源全部转让时所获得的利润应不少于70个单位，即 （2.2） 同样的分析，有 （2.3） 此时，企业的总获利（即对方的总付出）为 （2.4） 为使对方容易接受，该厂只能在约束条件（2.2）和（2.3）下求（2.4）式的最小值，即 （2.5） 上述两个模型（2.1）和（2.5）是对同一问题的两种不同考虑的数学描述，其间有着一定的内在联系，我们对此进行比较分析，并从中找出规律，两个模型的对应关系有： （1）两个问题的系数矩阵互为转置； （2）一个问题的变量个数等于另一个问题的约束条件个数； （3）一个问题的右端系数是另一个问题的目标函数的系数；
（4）一个问题的目标函数为极大化，约束条件为“≤”类型，另一个问题的目标函数为极小化，约束条件为“≥” 我们把这种对应关系称为对偶关系，如果把（2.1）式称为原问题，则（2.5）式称为对偶问题。 1.2 对偶问题的形式 一、对称形对偶问题 定义1设原线性规划问题为 （2.6）则称下列线性规划问题 （2.7）为其对偶问题，其中称其为对偶变量，并称（2.6）和（2.7）式为一对对称型对偶问题。 原始对偶问题（2.6）和对偶问题（2.7）之间的对应关系可以用表2-1表示。