2 x1 45/7 1 0 0 0 6/7 -50/7 -1/7 -1/7 ?j 由此得，原问题的最优解为X*?(102/7。
10、求解下述LP问题
454, , 0)T，目标函数最优值为77max z?10x1?15x2?12x3?5x1?3x2?x3?9???5x1?6x2?15x3?15 s..t??2x1?x2?x3?5??x1,x2,x3?0解：用大M法求解。将原问题化为标准型，可得：
max z?10x1?15x2?12x3?5x1?3x2?x3?x4?9??5x?6x?15x?x?15 ?1235s..t??2x1?x2?x3?x6?5?xj?0,j?1,2,?,7?在第三个等式约束中引入一个人工变量x7，可得：
max z?10x1?15x2?12x3?Mx7?5x1?3x2?x3?x4?9??5x?6x?15x?x?15?1235s..t??2x1?x2?x3?x6?x7?5?xj?0,j?1,2,?,7?用单纯形表求解，可得：
cj 10 15 12 0 0 0 －M cB 0 0 XB b 9 15 x1 [5] －5 x2 3 6 x3 1 15 x4 1 0 x5 0 1 x6 0 0 x7 0 0 ?i 9/5 - x4 x5 －M x7 5 2 2M+10 1 M+15 3/5 9 -1/5 9-M/5 39/80 9/16 -43/80 27/8-43M/80 1 M+12 1/5 [16] 3/5 3M/5+10 0 1 0 0 0 0 1/5 1 -2/5 -2M/5-2 3/16 1/16 0 0 0 1 0 0 -1/80 1/16 -1 -M 0 0 -1 -M 0 0 -1 -M 1 0 0 0 1 0 0 0 1 0 5/2 9 3/2 7/3 ?j 10 0 －M x1 x5 x7 9/5 24 7/5 1 0 0 0 ?j 10 12 -M x1 x3 x7 3/2 3/2 1/2 1 0 0 0 -7/16 -3/80 -21/8-7M/16 -5/8-3M/8 ?j 所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量x7仍在基变量中，故原问题无可行解。
写对偶问题
1、写出下列线性规划问题的对偶问题
max z=2x1+2x2－4x3
x1 + 3x2+ 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0
解：其对偶问题为
min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0
2、写出下列线性规划问题的对偶问题
min z=2x1+8x2－4x3
x1 + 3x2－3x3 ≥30 －x1 + 5x2+ 4x3 = 80 4x1 + 2x2－4x3≤50
x1≤0、x2≥0，x3无限制
解：其对偶问题为
max w=30y1+80 y2+50 y3 y1－ y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4
y1≥0，y2无限制，y3≤0
对偶的性质
1、已知线性规划问题
max z=x1+2x2+3x3+4x4
x1 + 2x2+ 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0
其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。
解：其对偶问题为
min w=20y1+ 20y2
y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0
**
将y1=6/5，y2=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以
2x3*+3x4* = 20 3x3* +2x4* = 20
解得x3* = x4* = 4。故原问题的最优解为
X*=（0，0，4，4）T 2、已知线性规划
maxz?3x1?4x2?x3?x1?2x2?x3?10 ?2x?2x?x?16?123?x?0,j?1,2,3?j的最优解为X*?(6,2,0)T，试利用互补松弛定理，求对偶问题的最优解。
解：原问题的对偶问题为：
minw?10y1?16y2?y1?2y2?3?2y?2y?4?12??y1?y2?1??y1,y2?0
將X*?(6,2,0)T代入原问题的约束条件，可得：
*??6?2*2?10 ? y1?0（1） ?*??2*6?2*2?16 ? y2?0又由
***?x1?0 ? y1?2y2?3?***?x2?0 ? 2y1?2y2?4（2） ?***x?0 ? y?y?1112?**将结论（1）和（2）结合起来，可解得y1?y2?1。
3、已知线性规划问题
max z?2x1?x2?5x3?6x4?2x1?x3?x4?8 ?s..t?2x1?2x2?x3?2x4?12?x?0, j?1,2,3,4?j**其对偶问题的最优解为y1?1，试用对偶理论求解原问题的?4、y2最优解。
解：原问题的对偶问题为：
min w?8y1?12y2?2y1?2y2?2?2y?12? ?s..t?y1?y2?5?y?2y?62?1??y1,y2?0将对偶问题的最优解代入约束条件，可得：
*?2*4?2*1?2 ? x1?0?*?2*4?1 ? x2?0 ?*?4?1?5 ? x3?0?4?2*1?6 ? x*?04?（1）
又由
****??y1?0 ? 2x1?x3?x4＝8（2） ?*****12 ??y2?0 ? 2x1?2x2?x3?2x4＝将结论（1）和（2）结合起来，可得：
***???x3?x4＝8?x3?4，解得?* ?**12 ???x4?4?x3?2x4＝即原问题的最优解为X*?(0,0,4,4)T。
对偶单纯形法
1、用对偶单纯形法求下面问题
minf(x)?4x1?6x2?x1?2x2?80?s.t. ?3x1?x2?75??x1,x2?0
解： CB 0 0 OBJ= CB 6 0 OBJ= CB 6 4 OBJ= XB x3 x4 0 XB x2 x4 240 XB x2 x1 254 Cj? b ?80 ?75 zj? zj - cj Cj? b 40 ?35 zj? zj - cj Cj? b 33 14 zj? 4 6 x1 x2 ?1 (?2) ?3 ?1 0 0 ?4 ?6 4 6 x1 x2 1/2 1 0 (?5/2) 3 6 0 ?1 4 6 x1 x2 0 1 1 0 4 6 0 0 min{( zj - cj)/ai*j} x3 x4 ai*j<0 1 0 {4,3*} 0 1 0 0 0 0 0 0 x3 x4 0 ?1/2 1 {2/5*,6} ?1/2 0 ?3 0 ?3 0 0 x3 x4 1/5 ?3/5 1/5 ?2/5 ?14/5 ?2/5