运筹学 线性规划习题课

线性规划习题课

1.建模练习 建模练习题

课后习题1.10.1.11，2.9（1）（2）

2．已知线性规划问题

min z=2x1-x2+2x3

-x1+x2+x3=4

-x1+x2-x3≤6 x1≤0,x2≥0,x3无约束

（1） 写出其对偶问题并化为标准型式。 （2） 用单纯形法求出原问题的最优解。

3．应用对偶问题性质，求出下面问题的最优解。

minz 10x1 4x2 5x3 5x1 7x2 3x3 30

x1,x2,x3 0

4.某混合饲料场为某种动物配置饲料。已知此动物的生长速度与饲料中的三种营养成分甲、乙、丙有关，且每头动物每天需要营养甲85g、乙5g、丙15g。现有五种饲料中都含有这三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如下表所示。求既满足动物生长需要又使成本最低的饲料配方。

5．已知下表为求解某线性规划问题的最终单纯形表，表中x4,x5为松弛变量，问题的约束条件为

" "

形式。

（1） 写出原线性规划问题的数学模型； （2） 写出原问题的对偶问题；

（3） 直接由上表写出对偶问题的最优解。

6．已知线性规划问题

max z=2x1+x2 5x2≤15 6x1+2x2≤24

x1+x2 ≤5

x1,x2≥0

（1）写出其对偶问题并化为标准型式； （2）用单纯形法求出原问题的最优解；

（3）根据最终单纯形表写出其对偶问题的最优解，三种资源的影子价格各为多少并说明其涵义； （4）若第三种资源增加3单位，问最优解有何变化，资源的影子价格变为多少。

3．解：（1）其对偶问题为：

maxw 4y1 6y2 y1 y2 2y1 y2 1y1 y2 2y2 0

x1' x2 x4 x5 x6 4x1' x2 x4 x5 x7 6x1',x2,x4,x5,x6,x7 0

用大M

maxw 4y3 4y4 6y2'y4 y3 y2' y5 2

化成标准型式为：y4 y3 y2' y6 1

y3 y4 y2' 2y2',y3,y4,y5,y6 0

minz 2x1' x2 2(x4 x5) Mx6 0x7

（2）原问题的准标准型为：

T

T

所以，原问题的最优解为：(x1,x2,x3) ( 5,0, 1)

5．解：设xi(i 1,2,3,4,5)为每千克混合饲料中所含5种饲料的重量 目标函数为：minz 2x1 6x2 5x3 4x4 3x5

0.50x1 2.00x2 3.00x3 1.50x4 0.80x5 85

约束条件有：

0.10x1 0.06x2 0.04x3 0.15x4 0.20x5 50.08x1 0.70x2 0.35x3 0.25x4 0.02x5 18xi 0(i 1,2,3,4,5)

7．解：（1）首先设a、b、c表示对应原模型的价值系数，则由检验数的计算公式，得

11

b c a 42211

0 c a 4

261

0 a 23

解此方程组，得：a=6，b=-2，c=10

115x2 x3 x4 222

再由单纯形表与原模型标准型的特点，得

1115x1 x2 x4 x5

2632

maxz 6x1 2x2 10x3

有这两个关系式，可得：

x2 2x3 x4 53x1 x2 x3 x5 10

所以：愿问题的模型为：

x2 2x3 53x1 x2 x3 10x1,x2,x3 0

minw 5y1 10y23y1 6

（2）由原问题的模型，得到其对偶问题模型： y1 y2 2

2y1 y2 10y1,y2 0

（3）由对偶理论，从原问题的最终单纯形表中，直接得到对偶问题的最优解：

y* (4,2)