最全运筹学习题及答案(3)

第 11 页 共 64 页

-z 最优解是 -102/7 0 0 -50/7 -1/7 X=（45/7，4/7，0，0，0 )T

Max z=102/7

（2）解法一：大M法

z?=-z 有max z?=-min （-z?）=-min z 化成标准形：

Max z?=-2x1-3x2-x3+0x4+0x5-Mx6-Mx7 S.T.

x1+4x2+2x3-x4+x6=4 3x1+2x2-x5+x7=6 x1,x2,x3,x4，x5,x6，x7?0 （单纯性表计算略）

线性规划最优解X=（4/5，9/5，0，0，0 ，0)T 目标函数最优值 min z=7 非基变量x3的检验数?3=0，所以有无穷多最优解。 两阶段法：

第一阶段最优解X=（4/5，9/5，0，0，0，0 )T是基本可行解,min w=0 第二阶段最优解（4/5，9/5，0，0，0，0 )T min z=7 非基变量x3的检验数?3=0，所以有无穷多最优解。

（3）解：大M法 加入人工变量，化成标准型：

Max z=10 x1+15 x2+12 x3+0 x4+0 x5+0 x6-M x7 s.t. 5 x1+3 x2+ x3+ x4=9 -5 x1+6 x2+15 x3+ x5=15 2 x1+ x2+ x3- x6+ x7=5 x1,x2,x3,x4，x5,x6，x7?0 单纯形表计算略

第 12 页 共 64 页

当所有非基变量为负数，人工变量x7=0.5，所以原问题无可行解。 两阶段法（略）

（4）解法一：大M法

单纯形法，（表略）非基变量x4的检验数大于零，此线性规划问题有无界解。 两阶段法略

1.7求下述线性规划问题目标函数z的上界和下界；

Max z=c1x1+c2x2

a11x1?a12x2?b1 a21x1?a22x2?b2

1?c1?3，4?c2?6，8?b1?12，10?b2?14，?1?a11?3，2?a12?5，其中：

2?a21?4，4?a22?6

解：

? 求Z的上界

Max z=3x1+6x2 s.t. -x1+2x2?12 2x1+4x2?14 x2，x1?0 加入松弛变量，化成标准型，用单纯形法解的，最优解 X=（0，7/2，5，0 )T

目标函数上界为z=21 存在非基变量检验数等于零，所以有无穷多最优解。 ? 求z的下界 线性规划模型： Max Z= x1+4x2 s.t. 3x1+5x2?8 4x1+6x2?10 x2，x1?0

加入松弛变量，化成标准型，解得：

第 13 页 共 64 页

最优解为

X=（0，8/5，0，1/5 )T

目标函数下界是z=32/5

1.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变

caaac量，1，2，3，d，1，2为待定常数，试说明这些常数分别取何值时，以下

结论成立。

（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为x1，换出变量为x6。 基b x3 d x4 2 x6 3 cj?zj x1 x2 x3 x4 x5 a2 x6 4 -1 a3 c1 a11 0 0 0 0 1 0 0 0 0 1 0 -3 -5 c2 -1 -4 -3 解： （1）有唯一最优解时，d?0，c10，c20 （2）存在无穷多最优解时，d?0，c1?0，c2=0或d?0，c1=0，c2?0. （3）有无界解时，d?0，c1?0，c2（4）此时，有d?0，c10且a1?0 0，3/a30并且c1?c2，a3d/4 1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下： 班次 时间 所需人数 1 6点到10点 60 2 10点到14点 70 3 14点到18点 60 4 18点到22点 50 5 22点到2点 20 6 2点到6点 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。

第 14 页 共 64 页

解 ：

设xk（k=1，2，3，4，5，6）为xk个司机和乘务人员第k班次开始上班。 建立模型：

Min z=x1+x2+x3+x4+x5+x6 s.t. x1+x6?60 x1+x2?70 x2+x3?60 x3+x4?50 x4+x5?20 x5+x6?30 x1,x2,x3,x4,x5,x6 ?0 1.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示： 原料 甲 乙 丙 原料每月成本（元/限制用量千克） （千克） A 2 2000 ?60% ?15% B 1.5 2500 C 1 1200 ?20% ?60% ?50% 加工费 0.5 0.4 0.3 售价 3.4 2.85 2.25 问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。 解: …… 此处隐藏：254字，全部文档内容请下载后查看。喜欢就下载吧 ……