运筹学习题集
数学建模
1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而
解：设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有
线性规划模型如下：
max f (x )=(168-42)x 1 +(140-28)x 2 +(1050-350)x 3 +(406-140)x 4
=126 x 1 +112 x 2 +700 x 3 +266 x 4
s.t. ??
?
??=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i
2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两
个工厂之间有一条流量为200万m 3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。
解：设x 1、2标可描述为
min z =1000x 1+800x 2 x 1 ≥1 0.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥0
3、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需
127星期日开始上班的人数。
min x 1+x 2+x 3+x 4+x 5+x 6+x 7
x 3+x 4+x 5+x 6+x 7≥28 x 4+x 5+x 6+x 7+x 1≥15 x 5+x 6+x 7+x 1+x 2≥24 x 6+x 7+x 1+x 2+x 3≥25 x 7+x 1+x 2+x 3+ x 4≥19 x 1+x 2+x 3+x 4+x 5≥31 x 2+x 3+x 4+x 5+x 6≥28
x 1、x 2、x 3、x 4、x 5、x 6、x 7≥0
4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的
i ???=i
i i x x x 不携带物品携带物品01 （i ＝1， (7)
则0－1规划模型为：
max z ＝20x 1＋15x 2＋16x 3＋14x 4＋8x 5＋14x 6＋9x 7 s.t. 5x 1＋5x 2＋2x 3＋5x 4＋10x 5＋2x 6＋3x 7≤25
x i ＝0或1，i ＝1，0，…，7
标准化问题
1、将下列线性规划化为标准形式
??????
?±≤≥≤-+=+--≥-++-=不限321
3213
213213
21 ,0 ,019
|1210|15736 10 ..235)(min x x x x x x x x x x x x t s x x x x f ?????????≥''''≤+''-'+'+-≤+''+'-'-=''-'+'+≤+''-'+'+-''+-'--=-0,,,,,, 191210191210157736 10 ..2'235)](max[654332
16
33215332133214332
1332
1x x x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x f 2、化下列线性规划为标准形 ma x z =2x 1+2x 2－4x 3 x 1 + 3x 2－3x 3 ≥30 x 1 + 2x 2－4x 3≤80 x 1、x 2≥0，x 3无限制
解：按照上述方法处理，得该线性规划问题的标准形为 ma x z =2x 1+2x 2－4x 31+4x 32
x 1 + 3x 2－3x 31 + 3x 32－x 4 = 30 x 1 + 2x 2－4x 31 + 4x 32 + x 5 = 80 x 1、x 2，x 31，x 32，x 4，x 5 ≥0
图解法
1、用图解法求解下面线性规划。 ma x z =2x 1+2x 2 x 1－x 2 ≥ 1 －x 1 + 2x 2≤ 0 x 1、x 2≥ 0
解：图1—3中阴影部分就是该
问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的
目标值分别为2和4，可以看
出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界
解或无最优解。
2、用图解法求解下述LP 问题。
12121
2max 2328416
.. 412
0,1,2j z x x x x x s t x x j =++≤??≤??
≤??≥=?
解：
可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为*
(4,2)T
X =，目标函数最大值为*
2*43*214z =+=。 3、 用图解法求解以下线性规划问题： （1）
max z= x 1 +3x 2
s.t. x 1 +x 2 ≤10 -2x 1 +2x 2 ≤12
x 1
≤ 7
x 1, x 2
≥0
x 2
10
(2,8)
6
x1 -6 0 7 10
最优解为（x1,x2）=（2,8），max z=26
(2) min z= x1-3x2
s.t. 2x1-x2≤4
x1+x2≥3
x2≥5
x1≤4
x1
最优解为（x1，x2）=（0，5），min z=-15
（3）max z= x1+2x2
s.t. x1-x2≤1
x1+2x2≤4
x1≤3
x1, x2≥0
x1
多个最优解，两个最优极点为（x1，x2）=（2，1），和(x1，x2)=(0，2)，max z=5
（4）min z= x1+3x2
s.t. x1+2x2≥4
2x1+x2≥4
x1, x2≥0
x1
12
单纯形法
1、用单纯形法求解
ma x z=50x1+100x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
j
2、用单纯形法求解
ma x z=2x1+x2
－x1 + x2≤5
2x1－5x2≤10
x1、x2≥0
解：用单纯形表实现如表1—10
22
3、用单纯形法（大M法）求解下列线性规划
ma x z=3x1－2x2－x3
x1－2x2 + x3≤11
－4x1 + x2 + 2x3 ≥3
－2x1+ x3= 1
x1、x2、x3≥0
解：化为标准形式
ma x z=3x1－2x2－x3
x1－2x2 + x3 + x4= 11
－4x1+ x2 +2x3 －x5 = 3
－2x1+x3= 1
x1、x2、x3、x4、x5≥0
在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题ma x z=3x1－2x2－x3－M x6－M x7
x1－2x2 + x3 + x4= 11
－4x1+ x2 +2x3 －x5 + x6= 3
－2x1+x3+x7 = 1
x1、x2、x3、x4、x5、x6、x7≥0
用单纯形进行计算，计算过程见表
j
4、用单纯形法（大M法）求解下列线性规划
ma x z=3x1+2x2
2x1+ x2 ≤2
3x1 +4 x2 ≥12
x1、x2≥0
解:化为标准形式后引入人工变量x5得到
ma x z=3x1+2x2－M x5
2x1+ x2 +x3= 2
3x1 +4 x2 －x4+x5 =12
x1、…、x5≥0
用单纯形法计算，过程列于表中。
从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量