第 21 页 共 64 页
2 x1+3 x2+5 x3 ?2 3 x1+ x2+7 x3 ?3
x1+4 x2+6 x3 ?5 x1 ,x2, x3 ?0
（1）
解：对偶问题是： Max w=2y1-3y2-5y3 s.t.
2y1-3y2-y3?2 3y1-y2-4y3?2 5y1-7y2-6y3?4
y1,y2,y3?0
(2)max z= x1+2x2+3 x3+4 x4 -x1+x2-x3-3x4=5 6x1+7x2+3x3-5x4?8 12x1-9x2-9x3+9x4?20
x1,x2?0;x3 ?0;x4无约束
解：
对偶问题： Min w=5y1+8y3+20S.t. -y1+6y3+12 y1+7y3-9
y4
y4?1
y4?2 y4 -y1+3y3-9
?3 =4
-3y1-5y3+9
y4第 22 页 共 64 页
y1无约束，y3?0；
y4?0
（3）min z=??cijxij
i?1j?1mn?xj?1nij?ai i=1,…,m
?xi?1mij?bj j=1,…,n
xij?0
解：
''对偶问题: max w=?aiy+?bjym?j
m''ini?1j?1''cs.t. yi''+ym?j?ij
''yy i,m?j 无约束 i=1,2,….m; j=1,2,….n ''
(4) Max z=?cjxj j?1n?axijj?1nnj?bi, i=1,…., m1?m ?axijj?1j?bi, i=m1?1,m1?2,...,m
xj?0,当j=1，….，n1?n xj无约束，当j=n1?1,...,n
m解：
Min w=?bjyi''
i?1s.t.
?ai?1mijyi''?cj j=1,2,3…n1
第 23 页 共 64 页
?ai?1mijnnyi''?cj j=1+1, 1+2,….n
yi''?0 i=1,2…. m1
yi''无约束， i=m1+1, m1+2….m
2.4判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。 （2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。
（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。
(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在； （2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解； （3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；
2.5设线性规划问题1是：
Max z1=?cjxj j?1n?axijj?1nj?bi ，i=1，2…，m xj?0,j?1,2....,n
*（y1*,...,ym）是其对偶问题的最优解。 又设线性规划问题2是 Max z2??cjxj j?1n?axijj?1nj?bi +ki ，i=1，2…，m
xj?0,j?1,2....,n
其中ki是给定的常数，求证：
max z2?max z1+?kiyi*
i?1m解：
证明：把原问题用矩阵表示：
第 24 页 共 64 页
Max z1=CX s.t. AX?b X?0 b=（b1,b2...bm)T
设 可行解为X1,对偶问题的最优解Y1=（y1，y2…ym ）已知。 Max z2=CX
s.t. AX?b+k X?0 k=（k1,k2...km)T
设可行解为X2，对偶问题最优解是Y2,对偶问题是， Min w=Y(b+k) S.t. YA ?C Y ?0 因为
Y2是最优解，所以Y2（b+k）?Y1（b+k）
X2是目标函数z2的可行解，AX2YXY?b+k ；2A2?2（b+k）?Y1b+Yk
原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。
2.6已知线性规划问题 Max z=c1x1?c2x2?c3x3
?a11??a?x1??21??a12??a?x2??22??a13??a?x3??23??1??0?x4????b1??0?=x?1?5?b? ?2???xj?0,j?1,...,5
用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求a11，a12，a13，a21，a22，a23，b1，b2的值； （2） 求c1,c2,c3的值；
XB x3 b 3/2 x1 x2 x3 x4 x5 1 0 1 1/2 -1/2
相关推荐：
loading