线性规划中的对偶问题

线性规划有一个有趣的特性，就是任何一个求极大的问题都有一个与其匹配的求极小的线性规划问题。

例；原问题为

MAX X=8*Z1+10*Z2+2*Z3

s.t. 2*Z1+1*Z2+3*Z3 〈=70

4*Z1+2*Z2+2*Z3 〈=80

3*Z1+ 1*Z3 〈=15

2*Z1+2*Z2 〈=50

Z1，Z2，Z3 〉=0

Z则其对偶问题为

MIN =70*Y1+80*Y2+15*Y3+50*Y4

s.t 2*y1+4*y2+3*y3+2*y4>=8

1*y1+1*y2+ 1*y4>=10

3*y1+2*y2+1*y3 >=2

y1,y2,y3,y3>=0

可以看出：1、若一个模型为目标求 极大 约束为 小于等于的不等式，则它的对偶模型为目标求极小 约束为极大的不等式

即 “MAX，〈=” “与MIN，〉=”相对应

2、从约束条件系数矩阵来看，一个模型中为A 另一个为A的转质，一个模型是 m个约束n个变量 则他的对偶模型为n个约束 m个变量

3、从数据b c 的位置看 两个规划模型中b和 c的位置对换

即8、10、2 与 70、80、15、50 对换

4、两个规划模型中变量非负。