对于任意一个线性规划,如何求他的对偶线性规划?
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/06/22 20:54:03
对于任意一个线性规划,如何求他的对偶线性规划?
给出任意一个线性规划,怎样求出他的对偶线性规划,请详细说说,不要一笔带过.
如果答得好的可以追加分数.
给出任意一个线性规划,怎样求出他的对偶线性规划,请详细说说,不要一笔带过.
如果答得好的可以追加分数.
![对于任意一个线性规划,如何求他的对偶线性规划?](/uploads/image/z/8818517-29-7.jpg?t=%E5%AF%B9%E4%BA%8E%E4%BB%BB%E6%84%8F%E4%B8%80%E4%B8%AA%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92%2C%E5%A6%82%E4%BD%95%E6%B1%82%E4%BB%96%E7%9A%84%E5%AF%B9%E5%81%B6%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92%3F)
对偶规划的构造
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)
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)