运筹学第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

（2）min z=3x1+2x2+x3+4x4 2x1+4x2+5x3+x4 ?0 3x1- x2+7x3-2x4 ?2 5x1+2x2+x3+10x4 ?15

x1 ,x2, x3, x4 ?0

2.9现有线性规划问题

max z=- 5x1+5x2+13x3 - x1+x2+3x3 ?20 12 x1+4x2+10x3 ?90

x1 ，x2， x3 ?0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

（1） 约束条件1的右端常数由20变为30 （2） 约束条件2的右端常数由90变为70

（3） 目标函数中x3的系数变为8

??1?（4） x1的系数向量变为??

?12?（5） 增加一个约束条件2x1+3x2+5x3?50 （6） 将约束条件2变为10x1+5x2+10x3?100

2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表2-3所示，

表2-3 设备代号 I II III 每月设备 有效台时 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 单位产品利润3 2 2.9 /千元 （1）如何充分发挥设备能力，使生产盈利最大？

（2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用设备是否合算？

（3）若另有两种新产品IV、V，其中IV为10台时，单位产品利润2.1千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A、B、C设备台时不增加，分别回答这两种新产品投产在经济上是否划算？

（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？

2.11分析下列参数规划中当t变化时最优解的变化情况。

（1）Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3 (t?0) s.t.

x1+2x2+x3 ?430 3x1+2x3 ?460

x1+4x2 ?420 x1，x2，x3?0

（2）Max z(t)=(7+2t)x1+(12+t) x2+(10-t)x3 (t?0) s.t.

x1+x2+x3 ?20 2x1+2x2+ x3 ?30

x1，x2，x3?0

本文来源：https://www.bwwdw.com/article/uqc5.html