运筹学第2章习题

第2章对偶理论与灵敏度分析习题详解(习题)

2.1用改进单纯形法求解以下线性规划问题。 （1）Max z=6x1-2x2+3x3

2x1-x2+3x3?2

x1+4x3?4 x1，x2，x3?0 （2）min z=2x1+x2

3x1+x2=3 4x1+3x2?6

x1+2x2?3 x1,x2?0

2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的计算表见表2-1所示，试将空白处数字填上。

表2-1 3 5 4 0 0 0 cj CB 5 0 0 XB x2 x5 x6 cj-zj b 8/3 14/3 20/3 x1 2/3 -4/3 5/3 -1/3 x2 1 0 0 0 . .… . x3 0 5 4 4 x4 1/3 -2/3 -2/3 -5/3 x5 0 1 0 0 x6 0 0 1 0 x2 x3 x1 cj-zj 15/41 -6/41 -2/41 8/41 5/41 -12/41 -10/41 4/41 15/41 2.3写出下列线性规划问题的对偶问题。 （1）min z= 2 x1+2 x2+4 x3

2 x1+3 x2+5 x3 ?2 3 x1+ x2+7 x3 ?3

x1+4 x2+6 x3 ?5 x1 ,x2, x3 ?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无约束 （3）min z=??cijxij

i?1j?1mn?xj?1mnij?ai i=1,…,m

?xi?1ij?bj j=1,…,n

xij?0 （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

2.4判断下列说法是否正确，并说明为什么.

（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

2.6已知线性规划问题

Max z=c1x1?c2x2?c3x3

?a11??a?x1??21??a12??a?x2??22??a13??a?x3??23??1??0?x4????b1??0?=?1?x5?b? ?2???xj?0,j?1,...,5

用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求a11，a12，a13，a21，a22，a23，b1，b2的值； （2） 求c1,c2,c3的值。

表2-2 b XB x1 1 1/2 -3 x2 0 1 0 x3 1 0 0 x4 1/2 -1 0 x5 -1/2 2 -4 x3 x2 cj?zj 3/2 2 2.7已知线性规划问题

Max z=2x1+x2+5x3+6x4 s.t. 2x1+x3+x4?8 2x1+2x2+x3+2x4?12

xj?0，j=1,…4

**对偶变量y1，y2，其对偶问题的最优解是y1=4，y2?1，试应用对偶问题

的性质，求原问题的最优解。

2.8试用对偶单纯形法求解下列线性规划问题。

（1）min z=x1+x2 2x1+x2?4 x1+7x2?7 x1,x2?0