当前位置：文档库 › 运筹学习题集

运筹学习题集

数学建模

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、x 2分别代表工厂1和工厂2处理污水的数量(万m 3

)。则问题的目标可描述为

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

所示。为了保证售货人员充分休息，售货人员每工作五天，休息两天，并要求休息的两天是连续的，问应该如安排售货人员的作息，既满足了工作需要

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、将下列线性规划化为标准形式

??????

?±≤≥≤-+=+--≥-++-=不限3213213

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

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 问题。

121212max 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

(2,8)

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，x2）=（0，5），min z=-15

（3）max z= x1+2x2

s.t. x1-x2≤1

x1+2x2≤4

x1≤3

x1, x2≥0

0 1 2 3 4

多个最优解，两个最优极点为（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，x2）=（4，0），min z=4

单纯形法

1、用单纯形法求解

ma x z=50x1+100x2

x1 + x2≤300

2x1 + x2≤400

x2≤250

x1、x2≥0

2、用单纯形法求解

ma x z=2x1+x2

－x1 + x2≤5

2x1－5x2≤10

x1、x2≥0

解：用单纯形表实现如表1—10

3、用单纯形法（大M法）求解下列线性规划ma x z=3x1－2x2－x3

x1－2x2 + x3≤11

－4x1 + x2 + 2x3 ≥3

－2x1+ x3= 1

x1、x2、x3≥0

解：化为标准形式

－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

4、用单纯形法（大M法）求解下列线性规划

ma x z=3x1+2x2

2x1+ x2 ≤2

3x1 +4 x2 ≥12

x1、x2≥0

解:化为标准形式后引入人工变量x5得到

3x 1 +4 x 2 －x 4+x 5 =12 x 1、…、x 5≥0

用单纯形法计算，过程列于表中。

从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量

2、用单纯形法求解下述LP 问题。

121212max 2328416.. 412

0,1,2j z x x x x x s t x x j =++≤??≤??

≤??≥=?

解：首先将原问题转化为线性规划的标准型，引入松弛变量x 3, x 4,x 5，可得：

1231425max 2328416

.. 412

0,1,2,,5j z x x x x x x x s t x x x j =+++=??

+=??

+=??≥=?

L 构造单纯形表，计算如下：

原问题的最优解为(4,2,0,0,4)X =*2*43*214z =+=。

3、用单纯形法求解下述LP 问题。

12121212

max 34240

.. 330

,0z x x x x s t x x x x =++≤??

+≤??≥? 解：首先将原问题转化为线性规划的标准型，引入松弛变量3x 、4x ，可得：

121231241234

max z 34240

.. 330

,,,0x x x x x s t x x x x x x x =+++=??

++=??≥? 构造单纯形表，计算如下：

由此可得，最优解为*(18, 4, 0, 0)T

X=，目标函数值为*3*184*470

z=+=。

4、用单纯形法求解下述LP 问题。

121212

max 2.53515

.. 5210,0z x x x x s t x x x x =++≤??

+≤??≥? 解：引入松弛变量3x 、4x ，化为标准形式：

1231241234

max 2.53515

.. 5210

,,,0z x x x x x s t x x x x x x x =+++=??

++=??≥?

(2)(20/19,45/19,0,0)T X =，所以两点之间的所有解都是最优解，即最优解集合为：(1)(2)(1)X X αα+-，其中01α≤≤。

5、用单纯形法求解下述线性规划

123

123123123123max 232883104..48,,0

z x x x x x x x x x s t x x x x x x =-+-++≤??

-+≤??

--≤??≥? 解：引入松弛变量x 、x 和x ，列单纯形表计算如下：

故，原问题的最优解为*3333(1011,27,,267,0,0)T X x x x x =+++，

*6z =，其中30x ≥。

7、用单纯形法求解下述LP 问题。

121231241234

min z 34240

.. 330

,,,0x x x x x s t x x x x x x x =--++=??

++=??≥? 解：构造单纯形表计算如下：

故，最优解为*(18, 4, 0, 0)T X =，目标函数值为

*3*184*470z =--=-。

8、用大M 法求解下述LP 问题

123123123123

max 2357

..2510,,0z x x x x x x s t x x x x x x =+-++=??

-+≥??≥? 解：先将原问题化为标准型，引入松弛变量4x ，得：

12312312341234

max 2357

..2510,,,0z x x x x x x s t x x x x x x x x =+-++=??

-+-=??≥? 再引入人工变量5x 、6x ，得：

12356123512346123456

max 2357..2510,,,,,0z x x x Mx Mx x x x x s t x x x x x x x x x x x =+---+++

=??-+-+=??≥?

构造单纯形表计算如下：

由此得，原问题的最优解为*454

(, , 0)77

T X =，目标函数最优值为102/7。

9、用两阶段法求解下述LP 问题

123123123123

max 2357

..2510,,0z x x x x x x s t x x x x x x =+-++=??

-+≥??≥? 解：先将原问题化为标准型，引入松弛变量4x ，得：

12312312341234

max 2357

..2510,,,0z x x x x x x s t x x x x x x x x =+-++=??

-+-=??≥? 再引入人工变量5x 、6x ，得第一阶段的模型为：

123512346123456

min 7

..2510,,,,,0z x x x x x x s t x x x x x x x x x x x =++++=??

-+-+=??≥? 构造单纯形表，计算如下：

由此可得第一阶段的最优解，转入第二阶段，单纯形表如下：

由此得，原问题的最优解为*454

(, , 0)77

T X =，目标函数最优值为102/7。

10、求解下述LP 问题

123

123123123123max 101512539

561515..25,,0

z x x x x x x x x x s t x x x x x x =++++≤??-++≤??

++≥??≥? 解：用大M 法求解。将原问题化为标准型，可得：

12312341235

1236max 101512539561515

..250,1,2,,7j z x x x x x x x x x x x s t x x x x x j =+++++=??-+++=??

++-=??≥=?

L 在第三个等式约束中引入一个人工变量7x ，可得：

12371234123512367max 101512539561515..250,1,2,,7j z x x x Mx x x x x x x x x s t x x x x x x j =++-+++=??-+++=??

++-+=??≥=?

用单纯形表求解，可得：

x 所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量

7仍在基变量中，故原问题无可行解。

写对偶问题

1、写出下列线性规划问题的对偶问题

max z=2x1+2x2－4x3

x1 + 3x2 + 3x3 ≤30

4x1 + 2x2 + 4x3≤80

x1、x2，x3≥0

解：其对偶问题为

min w=30y1+ 80y2

y+ 4y≥2

3y 1 + 4y 2 ≥－4 y 1、y 2≥0

2、写出下列线性规划问题的对偶问题

min z =2x 1+8x 2－4x 3

x 1 + 3x 2－3x 3 ≥30 －x 1 + 5x 2 + 4x 3 = 80 4x 1 + 2x 2－4x 3≤50

x 1≤0、x 2≥0，x 3无限制

解：其对偶问题为

max w=30y 1+80 y 2+50 y 3 y 1－ y 2 + 4 y 3 ≥2 3y 1+5y 2 + 2y 3 ≤8 －3y 1 + 4y 2－4y 3 =－4

y 1≥0，y 2无限制，y 3≤0

对偶的性质

1、已知线性规划问题

max z =x 1+2x 2+3x 3+4x 4

x 1 + 2x 2 + 2x 3 +3x 4≤20 2x 1 + x 2 + 3x 3 +2x 4≤20 x 1、x 2，x 3，x 4≥0

其对偶问题的最优解为y 1*=6/5，y 2*

=1/5。试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为

min w=20y 1+ 20y 2

y 1 + 2y 2 ≥1 （1） 2y 1 + y 2 ≥2 （2） 2y 1 +3y 2 ≥3 （3） 3y 1 +2y 2 ≥4 （4） y 1、y 2≥0

将y 1*=6/5，y 2*

=1/5代入上述约束条件，得（1）、（2）为格不等式；由互

补松弛定理可以推得x 1*=0，x 2*=0。又因y 1*>0，y 2*

>0，故原问题的两个约束条件应取等式，所以

2x 3* +3x 4*

= 20 3x 3* +2x 4*

= 20

解得x 3* = x 4*

= 4。故原问题的最优解为

X *=（0，0，4，4）T

2、已知线性规划

123123123max 34210

2216z x x x x x x x x x =++?++≤?

++≤?

的最优解为*(6,2,0)T X =，试利用互补松弛定理，求对偶问题的最优解。

解：原问题的对偶问题为：

1212121212min 1016232241,0

w y y y y y y y y y y =++≥??+≥??

+≥??≥?

將*(6,2,0)T X =代入原问题的约束条件，可得：

*1*

262*210 0

2*62*216 0

y y ?+=?≥??+=?≥?? （1）又由

***112*

212***1120 230 2240 1x y y x y y x y y ?>?+=?>?+=??=?+≥?

（2）将结论（1）和（2）结合起来，可解得**

121y y ==。

3、已知线性规划问题

12341341234max 25628

..222120, 1,2,3,4j

z x x x x x x x s t x x x x x j =+++?++≤?

+++≤??≥=? 其对偶问题的最优解为*

14y =、*2

1y =，试用对偶理论求解原问题的最优解。

解：原问题的对偶问题为：