对偶规划的构造
1、对称形式下的对偶问题
定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束,当目标函数求极小时,其约束条件均取“>=”号,当目标函数求极大时,均取“=b1
(LP) a21x1＋a22x2＋…＋a2nxn >=b2
……
am1x1＋am2x2＋…＋amnxn>=bm
xi>=0(i＝1,2,…,n)
用 (j＝1,2,……,m)表示对偶规划的变量,则
对称形式下线性规划的对偶规划的一般形式：
max g＝b1ω1＋b2ω2＋…＋bmωm
s.t. a11ω1＋a21ω2＋…＋am1ωm=0
(LD) max wb
s.t. ωA=0
其中
c＝(c1,c2,……,cn),
x＝(x1,x2,……,xn)T,
A＝(aij)m×n,
b＝(b1,b2,…,bm)T,
ω＝(ω1, ω2,…, ωn).
若将这儿对偶规划作为原规划,我们来求它的对偶规划,则这儿(LD)可化为：
min －bTωT
s.t. －ATωT>=-cT
ωT>=0
它的对偶规划为
max xT(－cT)
s.t. xT(-AT)