运筹学习题集03
数学建模
1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： A B C D 产品 项目 168 140 1050 406 单位产值 (元) 42 28 350 140 单位成本 (元) 3 2 10 4 单位纺纱用时 (h) 0 0 2 0.5 单位织带用时 (h) 工厂有供纺纱的总工时7200h，织带的总工时1200h，列出线性规划模型。 解：设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有
线性规划模型如下：
max f(x)=(168?42)x1 +(140?28)x2 +(1050?350)x3 +(406?140)x4
=126 x1 +112 x2 +700 x3 +266 x4
?3x1?2x2?10x3?4x4?7200?s.t. ? 2x3?0.5x4?1200
?xi?0, i?1,2,3,4?2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两
个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。 工厂1 工厂2 500万m3 200万m3
解：设x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则问题的目 标可描述为
min z=1000x1+800x2 x1 ≥1 0.8x1 + x2 ≥1.6 x1 ≤2 x2≤1.4 x1、x2≥0
3、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）
1 / 36
运筹学习题集03 时 间 星期日 星期一 星期二 星期三 星期四 星期五 所需售货员人数 28人 15人 24人 25人 19人 31人 星期六 28人 解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，……，x7星期日开始上班的人数。
min x1+x2+x3+x4+x5+x6+x7
x3+x4+x5+x6+x7≥28 x4+x5+x6+x7+x1≥15 x5+x6+x7+x1+x2≥24 x6+x7+x1+x2+x3≥25 x7+x1+x2+x3+ x4≥19 x1+x2+x3+x4+x5≥31 x2+x3+x4+x5+x6≥28
x1、x2、x3、x4、x5、x6、x7≥0
4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量为25 kg，试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 照相器通信设物品 食品 氧气 冰镐 绳索 帐篷 材 备 重量kg 5 5 2 5 10 2 3 重要性系数 2 解：引入0－1变量xi ?1携带物品xixi?? （i＝1，…，7）
0不携带物品xi?则0－1规划模型为：
max z＝20x1＋15x2＋16x3＋14x4＋8x5＋14x6＋9x7 s.t. 5x1＋5x2＋2x3＋5x4＋10x5＋2x6＋3x7≤25
xi＝0或1，i＝1，0，…，7
标准化问题
1、将下列线性规划化为标准形式
2 / 36
?? x3??x3???x4?10? ?x1? x2? x1? x2? x3??10???7x3??7x3?? ?15 6x1?3x2? 6x?3x?7x?15 ? ??123??x3??x3???x5?19s.t. ?10x1?12x2s.t. ???10x?12x??x??x???x?19?|10x1?12x2?x3|?1912336???x1?0, x2?0, x3?不限?,x3?,x3??,x4,x5,x6?0?? x1,x22、化下列线性规划为标准形 max z=2x1+2x2－4x3 x1 + 3x2－3x3 ≥30 x1 + 2x2－4x3≤80 x1、x2≥0，x3无限制
解：按照上述方法处理，得该线性规划问题的标准形为 max z=2x1+2x2－4x31+4x32
x1 + 3x2－3x31 + 3x32－x4 = 30 x1 + 2x2－4x31 + 4x32 + x5 = 80 x1、x2，x31，x32，x4，x5 ≥0
图解法
1、用图解法求解下面线性规划。 max z=2x1+2x2 x2x1－x2 ≥ 1 －x1 + 2x2≤ 0 x1、x2≥ 0
z=6 解：图1—3中阴影部分就是该
问题的可行域，显然该问题的z=4 可行域是无界的。两条虚线为目标函数等值线，它们对应的
1 目标值分别为2和4，可以看
出，目标函数等值线向右移动，A 2 问题的目标值会增大。但由于1 O 可行域无界，目标函数可以增－1 图1—3 大到无穷。称这种情况为无界
解或无最优解。
2、用图解法求解下述LP问题。
minf(x)?5x1?3x2?2x3运筹学习题集03
??2x'3?2x3??max[?f(x)]??5x1?3x2x1max z?2x1?3x2?x1?2x2?8?4x?16 ?1s.. t??4x2?12?xj?0,j?1,2?3 / 36
运筹学习题集03
解：
可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为X?(4,2)，目标函数最大值为z?2*4?3*2?14。 3、 用图解法求解以下线性规划问题：
（1）
max s.t. z=
x1 x1 -2x1 x1
+3x2
+x2 ≤10 +2x2 ≤12
≤ 7
**
T≥0 x1, x2 x2
10
(2,8) 6
x1 -6 0 7 10 最优解为（x1,x2）=（2,8），max z=26 (2) min z= x1 -3x2 4 / 36
s.t. 2x1 x1 x1 x1, 运筹学习题集03 -x2 ?4 +x2 ?3 x2 x2 ?5 ?4 ?0
x2 5
3
x1 0 2 3 4
最优解为 （x1，x2）=（0，5），min z=-15
max z= x1 +2x2 （3）
s.t.
x1 x1 x1 x1,
-x2 +2x2
x2
?1 ?4 ?3 ?0
x2
2
x1 0 1 2 3 4
多个最优解，两个最优极点为（x1，x2）=（2，1），和(x1，x2)=(0，2)，max z=5
min z= x1 +3x2 （4） s.t. x1 +2x2 ?4
2x1 x1,
+x2 x2
?4 ?0
5 / 36
运筹学习题集03
