对偶线性规化问题.pptVIP

第二章对偶线性规划;对偶的定义;标准的原始问题和对偶问题;根据定义写出对偶问题的练习;对偶问题的对偶;对偶问题的性质总结;minz=2x1+3x2-x3

s.t.x1+2x2+x3=6

2x1-3x2+2x3≥9

x1,x2,x3≥0;其他形式的对偶—原始问题有“≤”约束;其他形式的对偶总结;minz=2x1+4x2-x3

s.t.3x1-x2+2x36

-x1+2x2-3x312

2x1+x2+2x38

x1+3x2-x315;写对偶问题的练习〔2〕;原始和对偶问题可行解目标函数值比较;可行解的目标函数值之间的关系

设XF、WF分别是极小化原始问题和极大化对偶问题的可行解，极小化原始问题可行解的目标函数值大于或等于极大化对偶问题可行解的目标函数值

z=CTXF≥WFTAXF≥WFTb=y

最优解的目标函数值之间的关系

设Xo、Wo分别是原始问题和对偶问题的最优解，原始问题和对偶问题的最优解目标函数值相等

z=CTXo=WoTAXo=WoTb=y;互补松弛关系;互补松弛关系－向量表示;minz=CTX

s.t. AX-XS=b

X,XS≥0;互补松弛关系的分量表示;互补松弛关系的分量表示;互补松弛关系的分量表示;w1...wi...wmwm+1...wm+j...wn+m;利用互补松弛关系求解线性规划;minz=6x1+8x2+3x3

s.t.x1+x2≥1

x1+2x2+x3≥-1

x1,x2,x3≥0;最优解的Kuhn-Tucker条件;对偶单纯形法;x6;18/2/3;; 单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。

对偶单纯形法那么是从另一个角度来进行的。对偶单纯形法在迭代过程中，保持对偶可行性和互补松弛条件满足，并且在迭代过程中不断改进原始可行条件，一旦原始可行条件得到满足，也就求得了最优解。;用单纯形表求解原始问题的四种形式;单纯形表和对偶(1);minz=CTX

s.t.AX-XS=b

X,XS≥0;minz=CTX

s.t.AX+XS=b

X,XS≥0;minz=CTX

s.t.AX+XS=b

X,XS≥0;maxz=CTX

s.t.AX-XS=b

X,XS≥0;maxz=CTX

s.t.AX-XS=b

X,XS≥0;maxz=CTX

s.t.AX+XS=b

X,XS≥0;maxz=CTX

s.t.AX+XS=b

X,XS≥0;minz=6x1+8x2+3x3

s.t.x1+x2-x4=1

x1+2x2+x3-x5=-1

x1,x2,x3,x4,x5≥0;如何从最优单纯形表中读出对偶问题的解〔1〕;如何从最优单纯形表中读出对偶问题的解〔2〕;对偶单纯形法〔初始解原始不可行的问题〕;已获得最优解：

〔x1,x2,x3,x4,x5,x6〕=〔5,7,6,0,0,0〕minz=35

对偶问题的最优解为：

〔w1,w2,w3,w4,w5,w6〕=〔-1,5,7,0,0,0〕maxy=35;3、初始解原始、对偶都不可行的问题;解法1：先解决原始可行性;在得到原始可行解时同时得到对偶可行解，已获得最优解：

〔x1,x2,x3,x4,x5,x6〕=〔5,7,6,0,0,0〕minz=17

对偶问题的最优解为：

〔w1,w2,w3,w4,w5,w6〕=〔-7,5,10,0,0,0〕maxy=17;解法2：先解决对偶可行性;得到原始可行解，已获得最优解：

〔x1,x2,x3,x4,x5,x6〕=〔5,7,6,0,0,0〕minz=17

对偶问题的最优解为：

〔w1,w2,w3,w4,w5,w6〕=〔-7,5,10,0,0,0〕maxy=17;对偶的经济解释;