16.对偶理论（三）对偶单纯形法
⼉童节快乐呀
这⼀部分我们考虑原问题是标准型的问题，并且介绍对偶单纯形法。
在上⼀节的强对偶定理的证明中，对标准型问题使⽤单纯形法，定义了对偶变量p为pT=cT
BB−1。然后由原问题最优性条件
cT−cT
BB−1A≥0T得到了等价表达的对偶可⾏性条件pTA≤cT。那么我们之前介绍的单纯形法可以看作是在保证原问题可⾏的前提下去寻找
对偶可⾏的解。那么反过来，我们也可以从对偶可⾏的前提下去寻找原问题可⾏的解，这种算法称为对偶算法。在接下来，将介绍对偶单纯
形法。并且说明这个算法事实上求解了对偶问题，更近⼀步，它是从对偶问题的⼀个基本可⾏解移动到另⼀个。
对偶单纯形法
考虑⼀个标准型的线性规划问题，假设矩阵A是⾏满秩（为什么这个假设具有⼀般性，可参考线性规划中的⼏何（三））。记B为基本矩
阵，它包含了矩阵A的m个线性⽆关的列。考虑下表(与之前介绍的单纯形法中的表⼀样)
更详细的有
不过，在这⾥不再要求B−1b是⾮负的，那就说明此时的解是⼀个原问题的基本解但不⼀定是可⾏解。但是，我们要求¯c≥0成⽴，也相当于
pTA≤cT成⽴（具体见上⼀节强对偶定理证明）。 这说明现在有了⼀个对偶问题的可⾏解，并且对偶问题的⽬标函数值为
pTb=cT
BB−1b=cT
Bx
B，这恰好就是上表中的左上⾓元素的相反数。如果不等式B−1b≥0也成⽴，那么这个解也将是⼀个原问题的可⾏解，
并且⽬标函数值相同，这说明我们找到了原问题和对偶问题的最优解。如果不等式B−1b≥0并不成⽴，那么我们将寻找下⼀个基矩阵。
找到满⾜xB(l)<0的l，考虑表中的第l⾏为pivot ⾏(x
B(l)),v
1,⋯,v
n)，其中v
i为B−1A
i的第l个元素。对于满⾜vi<0的所有i（如果存在的话），
我们计算⽐率¯c
i/|v
i|，然后记j为这些⽐率中最⼩的那个的下标（为什么这么选呢，后⾯会说），也就是说v
j<0且
¯cj
|v
j|
=min
{i∣vi<0}¯ci
1. 对偶单纯形法
2. F(x)=3x1+4x2+5x3
X1+2x2+3x3>=5
2x1+2x2+x3>=6
xi>=0
f=[3;4;5];
A=[-1 -2 -3
-2 -2 -1];
b=[-5;-6];
lb=zeros(3,1);
[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)
x =
1.0000
2.0000
0.0000
fval =
11.0000
exitflag =
1
output =
iterations: 8
algorithm: 'large-scale: interior point'
cgiterations: 0
message: 'Optimization terminated.'
lambda =
ineqlin: [2x1 double]
eqlin: [0x1 double]
upper: [3x1 double]
lower: [3x1 double]
x, lambda.ineqlin, lambda.lower
x =
1.0000
2.0000
0.0000
ans =
1.0000
1.0000
ans =
0.0000
0.0000
1.0000
2.单纯形法
f(x)=-9x1+-16x2
x1+4x2+x3=80
2x1+3x2+x4=90
xi>=0
f=[-9;-16;0;0];
Aeq=[1 4 1 0
2 3 0 1];
beq=[80;90];
lb=zeros(4,1);
[x,fval,exitflag,output,lambda] = linprog(f,[],[],Aeq,beq,lb)
第三章 线性规划及其对偶问题
线性规划是最优化问题的一种特殊情形，也是运筹学的一个重要分支，它的实质是从多个变量中选取一组适当的变量作为解，使这组变量满足一组确定的线性式，而且使一个线性目标函数达到最优（最大或最小）．
线性规划的应用极为广泛，自1949年美国数学家G. B. Dantzing提出一般线性规划问题求解的方法——单纯形法之后，线性规划无论在理论上、计算方法和开拓新的应用领域中，都获得了长足的进步，线性规划从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都有广泛的发展和应用．本章主要从线性规划的基本概念、数学模型、单纯形法、对偶理论、灵敏度分析等方面进行介绍．
§3.1 线性规划数学模型基本原理
一、线性规划的数学模型
满足以下三个条件的数学模型称为线性规划的数学模型：
（1）每一个问题都用一组决策变量Tnxxx][21，，，表示某一方案；每一组值就代表一个具体方案．
（2）有一个目标函数，可用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化．
（3）有一组约束条件，可用一组线性等式或不等式来表示．
线性规划问题的一般形式为
1211221111221121122222112212max(min)()()()..()0nnnnnnnmmmnnmnfxxxcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx，，，，，，，，，，，，，．
这里，目标函数中的系数nccc，，，21叫做目标函数系数或价值系数，约束条件中的常数mbbb，，，21叫做资源系数，约束条件中的系数；，，，miaij21(
)21nj，，，叫做约束系数或技术系数．
二、线性规划问题的标准形式
所谓线性规划问题的标准形式，是指目标函数要求min，所有约束条件都是等式约束，且所有决策定量都是非负的，即
对偶单纯形法：
设线性规划问题为：max Z=cx
(P) AX=b
X≥0
原始的单纯形法的思想：
1 要求纯型迭代要求每一步都是基础可行解b=B¯1b≥0
2 达到最优解时，检验数Cj-Zj≤0（max)或者Cj-Zj≥0（min)
3 但对于（max,≥）型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决
4 大M法和二阶段法比较繁琐
5 能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，Cj-Zj≤0（max)或者Cj-Zj≥0（min)
X b
Xb B¯1A B¯1b
δ C-CbB¯1A -CbB¯1b
若上表最优单纯形表，则下面两个式子同时成立
1 B¯1≥0 （可行性条件，又叫对偶最优性条件）
2 C-CbB¯1A ≤0（最优性条件，又叫做对偶可行性条件）
从满足2的基出发去找元问题的最优解
对偶单纯形法的思想：
从满足条件2的基（一般称为正则基）B出发，经过换基运算得到另一个正则基，即一直保证2成立，知道找到一个满足条件（1）的正则基
对偶单纯形法的步骤：
P118页
看例题4.41
注意几个问题：
（1）对偶单纯形法求解线性规划的一种求解方法，而不是去求对有问题的最优解
（2）初始表中一定要满足对问题可行，也就是说检验数满足最优判别准则
（3）最小比值中|δj∕aij | 的绝对值是使得比值非负，在极小化问题时δj≥0 ，分母aij＜0这时必须取绝对值。在极大化问题中，δ≤0 ， 分母aij＜0， δj∕aij 总满足非负，这时绝对值不起作用，可以去掉。如果本例中将目标函数写成maxz’=-2X1-3X2-4X3这里 aij＜0 在求 θk
