管理运筹学课后答案

2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。

（1）

123

123123123123min 2432219

43414..524260,0,z x x x x x x x x x s t x x x x x x =++-++≤??-++≥??

--=-??≤≥?

无约束 解：（1）令11333','",'x x x x x z z =-=-=-，则得到标准型为（其中M 为一个任意大的正

数）

12334567123341233561233712334567max '2'24'4''003'22'2''19

4'34'4''14..5'24'4''26',,','',,,,0

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

++-+=??≥?

初始单纯形表如表2-1所示：

表2-1

c j

-2

2 4

-4 0 0 -M -M θ

C B X B b 1'x

x 2 3'x

3''x

x 4 x 5 x 6 x 7 0 x 4 19 3 2 2 -2 1 0 0 0 19/3 -M x 6 14 [ 4 ] 3 4 -4 0 -1 1 0 14/4 -M

x 7 26

5 2 4

-4

0 0 0 1 26/5 -z

-2+9M

2+5M

4+8M -4-8M

-M

2.3 用单纯形法求解下列线性规划问题。

（1）

123

123123

123123max 2360

210..220,,0

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

+-≤??≥? （2） 1234

123412341234

min 52322347..2223,,,0z x x x x x x x x s t x x x x x x x x =-+++++≤??

+++≤??≥?

解：（1）最优解为**(15,5,0),25T x z ==。

（2）最优解为**(0,1.5,0,0),3T x z ==-。

2.4 分别用大M 法和两阶段法求解下列线性规划问题。

（1） 123

123123123

max 2357..2510,,0z x x x x x x s t x x x x x x =+-++=??-+≥??≥? （2） 12

12123

1241234min 433

436..24,,,0

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

++=??≥? 解：（1）最优解为**(6.429,0.571,0),14.571T x z ==。 （2）最优解为**(0.4,1.8,1,0), 3.4T x z ==。

2.6 已知线性规划问题

123451234512345min 23523234..233

0,1,2,,5j

Z x x x x x x x x x x s t x x x x x x j =++++?++++≥?-+++≥??≥=?

其对偶问题最优解为**

*124/5,3/5;5y y Z ===。试用对偶理论找出原问题最优解。

解：先写出它的对偶问题

12

1212

12121212max 4322

3235..233,0

w y y y y y y y y s t y y y y y y =++≤??-≤??+≤??

+≤??+≤?≥??

将**

124/5,3/5y y ==代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互

补松弛性得***2340x x x ===。又因为**

12,0y y >，所以原问题的两个约束条件应取等式，因

此有

**15**153423

x x x x ?+=??+=?? ? *1*511

x x ?=??=?? 故原问题最优解为**(1,0,0,0,1),5T X z ==。

2.12 现有线性规划问题

123123123123

max 5513320..1241090

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

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

（1）约束条件①的右端项系数由20变为30；

（2）约束条件②的右端项系数由90变为70； （3）目标函数中3x 的系数由13变为8； （4）1x 的系数列向量由(1,12)T

-变为(0,5)T

； （5）将原约束条件②改变为12310510100x x x ++≤； （6）增加一个约束条件12323550x x x ++≤。

解：在上述LP 问题的第①、②个约束条件中分别加入松弛变量x 4,x 5得

12345

1234

123512345

max 551300320..1241090

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

① ②

列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。

由表2-11中的计算结果可知，LP 问题的最优解X *=(0,20,0,0,10)T ，z *=5*20=100。 （1）约束条件①的右端项系数由20变为30，则有

1103030419030B b -??????==??????--?????? 列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。

表2-11

c j

-5 5 13 0 0 θi C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4 20 -1 1 [ 3 ] 1 0 20/3 0

x 5 90

12 4 10 0 1 9 c j -z j

-5 5 13 0 0 13 x 3 20/3 -1/3 [ 1/3 ] 1 1/3 0 20 0

x 5 70/3 46/3 2/3 0 -10/3 1 35 c j -z j

-2/3 2/3 0 -13/3 0 5 x 2 20 -1 1 3 1 0 0

x 5 10 16 0 -2 -4 1 c j -z j

-2

-5

表2-12

c j

-5 5 13 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 5 x 2 30 -1 1 3 1 0 0

X 5 -30

16 0 [ -2 ] -4 1 c j -z j

0 0 -2 -5 0 5 x 2 -15 23 1 0 [ -5 ] 3/2 13

x 3 15 -8 0 1 2 -1/2 c j -z j

-16 0 0 -1 -1 0 x 4 3 -23/5 -1/5 0 1 -3/10 13

x 3 9 6/5 2/5 1 0 1/10 c j -z j

-103/5

-1/5

-13/10

由表2-12中计算结果可知，LP 问题的最优解变为**(0,0,9,3,0),139117T X z ==?=。 （2）约束条件②的右端常数由90变为70，则有

1102020417010B b -??????== ??? ?--??????

列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。

表2-13

c j

-5 5 13 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 5 x 2 20 -1 1 3 1 0 0

X 5 -10

16 0 [ -2 ] -4 1 c j -z j

0 0 -2 -5 0 5 x 2 5 23 1 0 -5 3/2 13

x 3 5 -8 0 1 2 -1/2 c j -z j

-16

-1

-1

由表2-13结果知，LP 问题的最优解变为**(0,5,5,0,0),5513590T X z ==?+?=。 （3）目标函数中x 3的系数由13变为8，由于x 3是非基变量，其检验数变为

38530(2)70σ=-?-?-=-< 所以LP 问题的最优解不变。

（4）x 1的系数列向量由(-1,12)T 变为(0,5) T ，则x 1在最终单纯形表中的系数列向量变为

1'

110004155B P -??????==??????

-?????? 从而x 1在最终单纯形表中的检验数变为

'1'11105(5,0)50

5

B c

C B P σ-??=-=--=-

所以LP 问题的最优解保持不变。

（5）将原约束条件②改变为10x 1+5x 2+10x 3≤100，则x 1在最终单纯形表中系数列向量变为'111(1,14)T P B P -==-，检验数'11115(5,0)(1,14)0T

B c

C B P σ-=-=---=

x 2在最终单纯形表中系数列向量变为'122(1,1)T P B P -==，检验数

'12225(5,0)(1,1)0T B c C B P σ-=-=-=。

又因11020204110020B b -??????

==??????-??????

的各分量均大于0，故LP 问题的最优解不变。

（6）增加一个约束条件2x 1+3x 2+5x 3≤50，则在此约束条件中加入松弛变量x 6，并将此约束加入到最终单纯形表中，继续迭代，过程如表2-14所示。

由表2-14中计算结果可知，LP 问题的最优解变为*(0,25/2,5/2,0,15,0)

T

X =，*525/2135/295z =?+?=。

表2-14

c j

-5 5 13 0 0 0 C B

X B

b

x 1

x 2

x 3

x 4

x 5

x 6

5 x 2 20 -1 1 3 1 0 0 0 x 5 10 1

6 0 -2 -4 1 0 0 x 6 50 2 3 5 0 0 1 5 x 2 20 -1 1 3 1 0 0 0 x 5 10 16 0 -2 -4 1 0 0

x 6 -10

5 0 [ -4 ] -3 0 1 c j - z j

0 -2 -5 0 0 5 x 2 25/2 11/4 1 0 -5/4 0 3/4 0 x 5 15 27/2 0 0 -5/2 1 -1/2 13

x 3 5/2

-5/4 0 1 3/4 0 -1/4 c j - z j

-5/2

-7/2

-1/2

3.1 分别用分支定界法和割平面法求解下列整数规划模型。 （1）12min 43z x x =-- （2）12max z x x =+

121212410..238,0,x x s t x x x x +≤??+≤??≥?且为整数 121212

26..4520,0,x x s t x x x x +≤??+≤??≥?且为整数 解：（1）求解得到最优解**

*122,1,11x x z ===-。

（计算步骤略） （2）仅写出利用割平面法求解的过程。

在原IP 问题约束条件中加入松弛变量x 3,x 4，化为标准型，可得

1234

123

1241234

max 0026..4520

,,,0z x x x x x x x s t x x x x x x x =+++++=??+++=??≥?且为整数

不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表3-1所示。

表3-1

c j

1 1 0 0 θi

C B X B b x 1 x 2 x 3 x 4 0 x 3 6 2 1 1 0 6 0

x 4 20

4 [

5 ] 0 1 4 c j -z j

1 1 0 0 0 x 3

2 [ 6/5 ] 0 1 -1/5 5/

3 1

x 2 4 4/5 1 0 1/5 5 c j -z j

1/5 0 0 -1/5 1 x 1 5/3 1 0 5/6 -1/6 1

x 2 8/3 0 1 -2/3 1/3 c j -z j

-1/6

-1/30

因此，松弛问题的最优解为x 1=5/3,x 2=8/3,x 3=0,x 4=0;z =13/3。 由于x 2不为整数，因此在最终单纯形表中根据x 2所在的行作割平面

342/31/3()0x x -+≤ 即

342x x --≤-

将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代，计算过程如表3-2所示。

表3-2

c j

1 1 0 0 0 C B X B b x 1 x

2 x

3 x

4 x

5 1 x 1 5/3 1 0 5/

6 -1/6 0 1 x 2 8/3 0 1 -2/3 1/3 0 0

x 5 -2

0 0 -1 [ -1 ] 1 c j -z j

0 0 -1/6 -1/30 0 1 x 1 2 1 0 1 0 -1/6 1 x 2 2 0 1 -1 0 1/3 0

x 4 2 0 0 1 1 -1 c j -z j

-1/6

由于12,x x 的值均为整数，所以得到原问题的最优解为**(2,2),4T x z ==

3.4 某厂新购4台不同类型机器，可以把它们安装在4个不同的地点。由于对特定的机器而言，某些地方可能安装起来特别方便且合适，所以不同的机器安装在不同的地点费用是不同的。估计的费用见表3-3，试制定使得总安装费用最小的安装方案。

表3-3 （费用单位：元）

地点

机器

1 2 3 4 机器总数

1 10 9 8 7 1

2

3

4

5

6 1 3 2 1 1 2 1 4 4 3 5 6 1 需要量

1

1

1

1

解：设 1,0,ij i j

x =???

如果机器安装在地点否则

c ij —机器i 安装在地点j 所需的费用。建立该问题的数学模型如下：

目标函数：

44

11min ij ij

i j z c x ===

∑∑

约束条件：

(1)每一部机器只分配在一个地点，即

4

111,2,3,4ij

j x i ===∑

(2)每一个地点只能有一台机器，即 4

111,2,3,4ij

i x

j ===∑

(3) 01ij x =或

工作指派问题可以看成是一类特殊的运输问题，每个供应点的供应量为1，每个需求点的需求量也为1。因此，本题可以采用表上作业法进行计算，也可以利用匈牙利法进行计算。计算得到的最佳安装方案为：机器1安装在地点4、机器2安装在地点1、机器3安装在地点3、机器4安装在地点2，最小总安装费为14元。

3.9 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表3-17所示。试确定使总运费最少的化肥调拨方案。

表3-17

需求 产地

I II III IV 产量(万吨)

A 16 13 22 17 50

B 14 13 19 15 60 C

19 20 23 -- 50 最低需求(万吨) 最高需求(万吨)

30 50

70 70

0 30

10 不限

解：这是一个产销不平衡的运输问题，总产量为160万t ，四个地区的最低需求为110万t ，最高需求为无限。根据现有产量，第IV 个地区每年最多能分配到60万t ，这样最高需求就为210万t ，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D ，其年产量为50万t 。由于各地区的需求量包含两部分，如地区I ，其中30万t 是最低需求，故不能由假想化肥厂D 供给，令相应的单位运价为M （任意大的正数）；而另一部分20万t 满足或不满足均可以，因此可以由假想化肥厂D 供给，按前述，可令相应的单位运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3-18）和单位运价表（表3-19）。并根据表上作业法，可以求得这个问题的最优解，如表3-20所示。

表3-18

销地

产地

I I ’ II III IV IV ’ 产量 A 50 B

60

C 50

D 50 销量

30

20

70

30

10

50

表3-19

销地 产地

I I ’ II III IV IV ’ A 16 16 13 22 17 17 B 14 14 13 19 15 15 C 19 19 20 23 M M D

M

M

M

表3-20

销地 产地

I I ’ II III IV IV ’ 产量 A 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 销量

30

20

70

30

10

50

4.2 利用单纯形法求解下列目标规划模型。

（1）11123

min ()z P d d P d -+-

=++ 12111222123312250

240..2280,,,0,1,2,3i i

x x d d x x d d s t x x d d x x d d i -+-+

-+

-+?++-=?++-=??++-=??≥=? 解：（1）本题的三个约束条件都是目标约束，有三个负偏差变量，因此选择负偏差变量为初始基变量。并计算出各非基变量的检验数，得到初始的单纯形表如表4-1所示。

非基变量x 1,x 2的检验数分别为σ1= -P 1-2P 2和σ2= -2P 1 -2P 2，它们的最高优先级的系数都小于零，但σ2中P 1的系数等于-2，其绝对值等于2，大于σ1中P 1的系数的绝对值1，因此x 2应当进基。用最小比值法确定1d -应当出基。换基后，通过计算求得新的基本可行解，如表4-2所示。

表4-1

c j 0 0 P 1

P 1

P 2

θ

C B X B

b x 1 x 2 1d -

1d +

2d -

2d +

3d -

3d +

P 1

1d -

50

1

[ 2 ]

1

-1

25

0 2d -

40 2 1 0 0 1 -1 0 0 40 P 2 3d -

80 2 2 0 0 0 0 1 -1 40 σj

P 1 -1 -2 0 1 0 1 0 0 P 2

-2

-2

1

表4-2

c j 0

0 P 1 0 0 P 1 P 2 0

θ

C B X B b x 1 x 2 1d -

1d +

2d -

2d +

3d -

3d +

0 x 2

25 1/2 1 1/2 -1/2 0 0 0 0 50 0 2d -

15 [ 3/2 ] 0 -1/2 1/2 1 -1 0 0 10 P 2 3d -

30 1 0 -1 1 0 0 1 -1 30 σj

P 1 0 0 1 0 0 1 0 0 P 2

-1

1

-1

1

尽管x 1与1d +具有相同的负检验数，但根据前面讨论的原则，由于x 1是决策变量，选择

x 1进基，用最小比值法确定2d -

出基，换基后，计算所得新的基本可行解如表4-3所示。

表4-3

c j 0 0 P 1

P 1

P 2

θ

C B X B b x 1 x 2 1d -

1d +

2d -

2d +

3d -

3d +

0 x 2 20 0 1 2/3 -2/3 -1/3 1/3 0 0 — 0 x 1

10 1 0 -1/3 [ 1/3 ] 2/3 -2/3 0 0 30 P 2 3d -

20 0 0 -2/3 2/3 -2/3 2/3 1 -1 30 σj

P 1 0 0 1 0 0 1 0 0 P 2

2/3

-2/3

2/3

-2/3

1

首项系数小于零的检验数只有1d +的为22/3P -，因此1d +应当进基，由于存在两个最小比值，取下标最小的变量出基，因此x 1出基，换基后，再计算新的基本可行解，如表4-4所示。

表4-4

c j 0

0 P 1 0 0 P 1 P 2 0

θ

C B X B b x 1 x 2 1d -

1d +

2d -

2d +

3d -

3d +

0 x 2

40 2 1 0 0 1 -1 0 0 0 1d +

30 3 0 -1 1 2 -2 0 0 P 2 3d -

0 -2 0 0 0 -2 2 1 -1 σj

P 1

1

1

P 2

2 0 0 0 2 -2 0 1

此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x 1=0,x 2

=40,1d +=30，其他偏差变量都等于零。

4.3 某厂生产A 、B 、C 三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。

该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。

解：该问题的数学模型如下：

112233444556612311123222

331442553

66123min ()50065080016000681020024

s.t. 12

106

,,0,,0i i Z p d p d p d p d d d d d d x x x d d x x x d d d d d x d d x d d x d d x x x d d --+-+-+-+-+-+

+-+-+-+-+-+

=+++

+

+++++++-=+++-=+-=+-=+-=+-=≥≥(1,2,,6)

i ??????

???

??=??

5.2 计算从A 到B 、C 和D 的最短路。已知各段路线的长度如图5-1所示。

图5-1

解：求从A 到B 、C 和D 的最短路等价于求从B 、C 和D 到A 的最短路。

设阶段变量k =1,2,3,4，依次表示4个阶段选路得过程，第1阶段从B 、C 或D 出发到B 3、C 3或D 3，第2阶段从B 3、C 3或D 3出发到B 2、C 2或D 2，第3阶段从B 2、C 2或D 2出发到B 1、C 1或D 1，第4阶段从B 1、C 1或D 1出发到A ；

状态变量s k 表示k 阶段初可能处的位置； 决策变量x k 表示k 阶段可能选择的路线；

阶段指标v k 表示k 阶段与所选择的路线相应的路长；

指标函数4

4k i i k

v v ==∑表示k 至第4阶段的总路长；

递推公式15min{},4,3,2,1;0k k k f v f k f +=+== 计算过程如表5-1所示。

由表中计算结果可以看出：从B 到A 的最短路线为B→C 3→C 2→B 1→A ，最距离为16；从C 到A 的最短路线为C→C 3→C 2→B 1→A 或C→D 3→C 2→B 1→A ，最短距离为21；从D 到A 的最短路线为D→D 3→C 2→B 1→A ，最短距离为20。

表5-1

k

s k x k v k v k 4=v k +f k +1 f k x k * 4

B 1

A 3 3+0 3 A C 1 A 8 8+0 8 A D 1 A 7 7+0 7 A 3

B 2

B 1 4 4+3 7

B 1

C 1 2 2+8 C 2

B 1

3 3+3 6

B 1

C 1 8 8+8

D 1

7 7+7 D 2

C 1 4 4+8 12

C 1

D 1 6 6+7 2

B 3 B 2 10 10+7 17 B 2

C 2 13 13+6 C 3

B 2

12 12+7 11

C 2

C 2 5 5+6

D 2

6 6+12 D 3

C 2 7 7+6 13

C 2

D 2 8 8+12 1

B B 3 9 9+17 16

C 3

C 3 5 5+11 C

B 3

10 10+17 21

C 3、

D 3

C 3 10 10+11

D 3

8 8+13 D

C 3 15 15+11 20

D 3

D 3

7

7+13

5.3 某工业部门根据国家计划的安排，拟将某种高效率的设备5台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表5-2所示。

表5-2

设备数 工厂

0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙

4

6

11

12

12

问：这5台设备如何分配给各工厂，才能使国家得到的盈利最大？

解：将问题按工厂分为3个阶段，甲、乙、丙3个工厂分别编号为1、2、3； 设s k 表示分配给第k 个工厂至第n 个工厂的设备台数； x k 表示分配给第k 个工厂的设备台数；

则s k +1=s k - x k 为分配给第k +1个工厂至第n 个工厂的设备台数； P k (x k )表示x k 台设备分配给第k 个工厂所得得盈利值；

f k (s k )表示s k 台设备分配给第k 个工厂至第n 个工厂时所得到得最大赢利值。

由以上的假设可写出逆推关系式为

1044()max [()()],3,2,1()0k k

k k k k k k k x s f s P x f s x k f s +≤≤=+-=???

=?? 下面采用逆推法进行计算。 第3阶段：

设s 3台设备(s 3=0,1,2,3,4,5)全部分配给工厂丙时，则最大赢利值为

3

3333()max[()]x f s P x =

其中x 3=s 3=0,1,2,3,4,5。

因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值。其数值计算如表5-3所示。

表5-3

表中*

3

x 表示使33()f s 为最大值时的最优决策。 第2阶段：

设把s 2台设备(s 2=0,1,2,3,4,5)分配给工厂乙和工厂丙时，则对每个s 2值有一种最优分配方案，使最大盈利值为

2

2222322()max[()()]x f s P x f s x =+-

其中x 2=0,1,2,3,4,5。

因为给乙工厂x 2台，其盈利为P 2(x 2)，余下的s 2-x 2台就给丙工厂，则它的盈利最大值为f 3(s 2-x 2)。现要选择x 2的值使22322()()P x f s x +-取最大值。其数值计算如表5-4所示。

表5-4

第1阶段：

设把s 1台(这里只有s 1=5的情况)设备分配给甲乙丙3个工厂，则最大盈利值为

1

11121(5)max[()(5)]

x f P x f x =+- 其中x 1=0,1,2,3,4,5。

因为给甲工厂x 1台，其盈利为P 1(x 1)，剩下的5-x 1台就分给一合丙两个工厂，则它的盈

利最大值为f 2(5-x 1)。现要选择x 1值使1121()(5)P x f x +-取最大值，它就是所求的总盈利最大值，其数值计算如表5-5所示。

表5-5

然后按计算表格的顺序反推算，可知最优方案有两个：

（1）由于*10x =，根据s 2=s 1 -*1x =5 - 0=5，查表5-4知*22x =，由s 3=s 2 -*

2

x =5-2=3，故*

333x s ==。即甲工厂分配0台、乙工厂分配2台、丙工厂分配3台。

（2）由于*12x =，根据s 2=s 1 -*1x =5 - 2=3，查表5-4知*22x =，由s 3=s 2 -*

2

x =3-2=1，故*

331x s ==。即甲工厂分配2台、乙工厂分配2台、丙工厂分配1台。

以上两个分配方案所得的总盈利均为21万元。

在此问题中，如果原设备的太熟不是5台，而是4台或3台，用其他方法求解时，往往需要从头再算，但用动态规划求解时，这些列出的表仍旧有用，只需要修改最后的表格就

可得到：

当设备台数位4台时，最优分配方案为***1231,2,1x x x ===或***

1232,2,0x x x ===，总盈利为17万元。

当设备台数位3台时，最优分配方案为：***

1230,2,1x x x ===，总盈利为14万元。

5.4设有一辆载重量为15吨的卡车，要装运4种货物。已知4种货物的单位重量和价值如表5-6所示，在装载重量许可的情况下每辆车装载某种货物的条件不限，试问如何搭配这4种货物才能使每辆车装载货物的价值最大？

表5-6

货物代号

重量(吨)

价值(千元)

货物代号

重量(吨)

价值(千元)

1 2 3 3 4 5 2

3

4

4

5

6

解：设决策变量1234,,,x x x x 分别为4种货物的装载件数，则问题为一线性整数规划：

1234

1234max 3456234515

..0,(1,2,3,4)

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

≥=?且为整数 将其转化为动态规划问题，分为4个阶段，每个阶段的指标函数记为

111()3g x x =， 222()4g x x =， 333()5g x x =， 444()6g x x =

状态变量s k 表示第k 种至第4种货物总允许载重量，即

4

(1)(1,2,3,4)k i i k

s i x k ==+=∑

允许状态集合为{0,1,2,,15},1,2,3,4k S k ==，最优值函数()k k f s 表示装载第k 种至第4中

货物的价值，则动态规划模型为

{}11()55()max ()()()0(4,3,2,1)k k k k k k k k k x D s f s g x f s f s k ++∈?=+??==?? 状态转移方程为

1(1),1,2,3,4k k k s s k x k +=-+=

允许决策集合为

()0,1,2,

,,(1,2,3,4)1k k k s D s k k ?

?

??==????+????

即表示在载重量允许的范围内可能装载第k 种货物的件数。 用逆推方法求解如下：

444444444:()max{6},(),k f s x x D s s S ==∈∈

4444()0,1,2,,,{0,1,2,,15}5s D s S ??

??==???????

?；

33344333333:()max{5()},(),k f s x f s x D s s S ==+∈∈

3333433()0,1,2,,,{0,1,2,,15},44s D s S s s x ??

??===-???????

?；

22233222222:()max{4()},(),k f s x f s x D s s S ==+∈∈ 2222322()0,1,2,,,{0,1,2,,15},33s D s S s s x ??

??===-???????

?；

111221111:()max{3()},(15),15k f s x f s x D s ==+∈=

{}121(15)0,1,2,

,7,152D s x ==-。

最后得到问题的最优解为****

12346,1,0,0x x x x ====，最优值为22千克。

7.1 求解下列矩阵对策，其中赢得矩阵A 分别为

（1）1/21111/21111------??

????

????

（2）2216145

1---??

?

???

（3）27212

234

35442

31

6?????

???????

（4）9

318065467

24338562213

2354??

??

??

????

??????

解：（1）由于max min 1,min max 1/2ij ij j

j

i

i

a a =-=，所以A 所对应的支付矩阵没有纯对策。

即局中人1以(0.36,0.36,0.27)的概率分别出策略1、2和3，其赢得值为-0.4545。

（2）由于max min 1,min max 2ij ij j

j

i

i

a a =-=，所以A 所对应的支付矩阵没有纯对策。

即局中人1以0.56、0.44的概率分别出策略1和策略2，赢得值为0.67.

（3）根据赢得矩阵有31max min min max 3ij ij j

j

i

i

a a a ===，所以G 的解为

31(,),3G v αβ=。

（4）根据赢得矩阵有23max min min max 4ij ij j

j

i

i

a a a ===，所以G 的解为

23(,),4G v αβ=。

7.2 甲、乙两家公司生产同一种产品，争夺市场的占有率。假设两家公司市场占有率之和为100％，即顾客只购买这两家公司的产品，无其他选择。若公司甲可以采用的商业策略为A 1、A 2、A 3，公司乙可以采用的商业策略为B 1、B 2、B 3。表7-1给出在不同策略下公司甲的市场占有率。在此情况下，请为这两家公司选择他们的最优策略。

表7-1

B 1 B 2 B 3 A 1 0.4 0.8 0.6 A 2

0.3

0.7

0.4

A 3 0.5 0.9 0.5

解：若完全采用二人常数和对策的方法确定最优纯策略，则由

max min min max 0.5A B

ij ij j

j

i

i

a a ==

可得，局中人甲采用策略A 3、局中人乙采用策略B 1，各获得50%的市场占有率。

从计算结果可以看出，局中人甲采用策略A 3、局中人乙采用策略B 1，各获得50%的市场占有率。

10.1某一决策问题的损益矩阵如表10-1所示，其中矩阵元素值为年利润。

表10-1 单位：元

（1）若各事件发生的概率j P 是未知的，分别用max min 决策准则、max max 决策准则、拉普拉斯准则和最小机会损失准则选出决策方案。

（2）若j P 值仍是未知的，并且α是乐观系数，问α取何值时，方案S 1和S 3是不偏不倚的？

（3）若P 1=0.2,P 2=0.7,P 3=0.1,那么用EMV 准则会选择哪个方案？

解：（1）采用maxmin 准则应选择方案S 2，采用maxmax 决策准则应选择方案S 1，采用Laplace 准则应选择方案S 1，采用最小机会损失准则应选择方案S 1。

（2）0.10256； （3）方案S 1或S 3。

10.8假设有外表完全相同的木盒100只，将其分为两组，一组内装白球，有70盒，另一组内装黑球，有30盒。现从这100盒中任取一盒，请你猜，如这盒内装的是白球，猜对了得500分，猜错了罚200分；如这盒内装的是黑球，猜对了得1000分，猜错了罚150分。有关数据列于表10-7。

（1）为使期望得分最多，应选哪一种方案？ （2）试求出猜白和猜黑的转折概率。

表10-7

概率

方案

自然状态

白0.7 黑0.3 猜白 500 -200 猜黑

-150

1000

解：先画出决策树，见图10-1

图10-1

计算各方案的期望值。

“猜白”的期望值为0.7 * 500 + 0.3 * (-200) = 290

“猜黑”的期望值为0.7 *(-150) + 0. 3 * 1000 = 195

经比较可知“猜白”方案是最优的。现假定出现白球的概率从0. 7变为0.8，这时各方案的期望值为

“猜白”的期望值为0.8 * 500 + 0.2 * (-200) = 360

“猜黑”的期望值为0.8 * (-150) + 0.2 * 1000 = 80

可见猜白方案仍是最优的。再假定出现白球的概率从0.7变为0.6，这时各方案的期望值为

“猜白”的期望值为0. 6 * 500 + 0.4 * (-200) = 220

“猜黑”的期望值为0.6 * (-150) + 0.4 * 1000 = 310

现在的最优方案不是猜白，而是猜黑了。可见由于各自然状态发生的概率的变化，可引起最优方案的改变。那么转折点如何确定？

设p为出现白球的概率，(1-p)为出现黑球的概率。当这两个方案的期望值相等时，即

p * 500 + (1-p) * (-200) = p * (-150) + (1-p) * 1000

求得p=0.6486，称它为转折概率。即当p>0.6486，猜白是最优方案；当p<0.6486，猜黑是最优方案。

10.10有一化工原料厂，由于某项工艺不太好，产品成本高。在价格保持中等水平的情况下无利可图，在价格低落时要亏本，只有在价格高时才盈利，且盈利也不多。现在工厂管理人员在编制五年计划时欲将该项工艺加以改革，用新工艺代替。取得新工艺有两种途径：一是自行研究，但成功的可能是0.6；二是买专利，估计谈判成功的可能性是0.8。不论研究成功或谈判成功，生产规模都有二种考虑方案：一是产量不变；二是产量增加。如果研究或谈判都失败，则仍采用原工艺进行生产，保持原产量。

根据市场预测，佑计今后五年内这种产品跌价的可能性是0.1，保持中等水平的可能性是0.5，涨价可能性是0.4.

决策问题：是购买外国专利，还是自行研制。

解：其决策表见表10-8，决策树见图10-3。

表10-8

图10-3 决策树

计算各点益损期望值：

点4：0.1 * (-100) + 0.5 * 0 + 0.4 * 100 = 30

点8：0.1 * (-200) + 0.5 * 50 + 0.4 * 150 = 65

点9：0.1 * (-300) + 0.5 * 50 + 0.4 * 250 = 95

点10：0.1 * (-200) + 0.5 * 0 + 0.4 * 200 = 60

点11：0.1 * (-300) + 0.5 * (-250) + 0.4 * 600 = 85

点7：0.1 * (-100) + 0.5 * 0 + 0.4 * 100 = 30

在决策点5，因95>65，应去掉产量不变方案，将点9期望值移至点5。同理，把点11的期望值移至点6。

点2：0.2 * 30 + 0.8 * 95 = 82

点3：0.6 * 85 + 0.4 * 30 = 63

决策：点2期望值大，所以合理决策是买专利。

《管理运筹学》第二版课后习题参考答案

《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：

管理运筹学基础 答案

课程学习 《管理运筹学基础》 判断正误 线性规划问题的一般模型中不能出现等式约束。 正确答案：说法错误 2.在线性规划模型的标准型中,b j（j=1，2，…m）一定是非负的。正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 正确答案：说法错误 解答参考： 5. 判断正误 同一问题的线性规划模型是唯一的。 正确答案：说法错误 解答参考： 12.第一个顶点和最后一个顶点相同的闭链叫回路。 正确答案：说法错误 解答参考： 14. 判断正误

Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。 正确答案：说法正确 解答参考： 15.简述编制统筹图的基本原则。 参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。 17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。 参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。 2. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。 正确答案：说法正确 单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。 正确答案：说法错误 解答参考： 6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。 正确答案：说法正确 解答参考： 8.表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m + n -1）个变量。正确答案：说法正确 解答参考： 9.用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界 正确答案：说法正确

《管理运筹学》第四版课后习题解析(上)

《管理运筹学》第四版课后习题解析（上） 第2章 线性规划的图解法 1．解： （1）可行域为OABC 。 （2）等值线为图中虚线部分。 （3）由图2-1可知，最优解为B 点，最优解1x = 127，2157x =；最优目标函数值697 。 图2-1 2．解： （1）如图2-2所示，由图解法可知有唯一解12 0.2 0.6x x =??=?，函数值为3.6。 图2-2 （2）无可行解。 （3）无界解。 （4）无可行解。 （5）无穷多解。

（6）有唯一解 12203 8 3x x ?=????=?? ，函数值为923。 3．解： （1）标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ （2）标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ （3）标准形式 1 2212min 2200f x x x s s ''''=-+++ 12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4．解： 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量（0，0） 最优解为 1x =1，x 2=3/2。 5．解：

运筹学试卷及答案.doc

运 筹 学 考 卷 1 / 51 / 5

考试时间: 第十六周 题号一二三四五六七八九十总分 评卷得分 ： 名 一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确 姓 答案的字母写这答题纸上。（10 分, 每小题2 分） 1、使用人工变量法求解极大化线性规划问题时，当所有的检验数j 0 ，在 线 基变量中仍含有非零的人工变量，表明该线性规划问题（） A. 有唯一的最优解； B. 有无穷多个最优解； C. 无可行解； D. 为无界解 2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）： 号 A．b 列元素不小于零B．检验数都大于零 学 C．检验数都不小于零D．检验数都不大于零 3、在产销平衡运输问题中，设产地为m 个，销地为n 个，那么基可行解中非 零变量的个数（） 订 A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（） A. d 0 B. d 0 C. d 0 D. d 0,d 0 5、下列说法正确的为（） ： 业 A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 专 B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解 装 C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原 问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 ： 院

学 2 / 52 / 5

二、判断下列说法是否正确。正确的在括号内打“√”，错误的打“×”。（18 分，每 小题2 分） 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（） 2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一 个基变量的值为负。（） 3、任何线性规划问题存在并具有惟一的对偶问题。（） 4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。 （）5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之 一：有惟一最优解，有无穷多最优解，无界解，无可行解。（） 6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k ， 最有调运方案将不会发生变化。（） 7、目标规划模型中，应同时包含绝对约束与目标约束。（） 8、线性规划问题是目标规划问题的一种特殊形式。（） 9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（） 三、解答题。（72 分） max z 3x 3x 1 2 1、（20分）用单纯形法求解 x x 1 2 x x 1 2 4 2 ；并对以下情况作灵敏度分析：（1）求 6x 2 x 18 1 2 x 0, x 0 1 2 5 c 的变化范围；（2）若右边常数向量变为2 b ，分析最优解的变化。 2 20 2、（15 分）已知线性规划问题： max z x 2x 3x 4x 1 2 3 4 s. t. x 2x 2x 3x 20 1 2 3 4 2x x 3x 2x 20 1 2 3 4 x x x x , , , 0 1 2 3 4 其对偶问题最优解为y1 1.2, y2 0.2 ，试根据对偶理论来求出原问题的最优解。

管理运筹学后习题参考答案汇总

《管理运筹学》(第二版)课后习题参考答案 第1章线性规划(复习思考题) 1. 什么是线性规划？线性规划的三要素是什么？ 答：线性规划(Lin ear Programmi ng , LF)是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2. 求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：(1)唯一最优解：只有一个最优点； (2)多重最优解：无穷多个最优解； (3)无界解：可行域无界，目标值无限增大； (4)没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3. 什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 ' ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业 来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明 “遅 约束的左边取值大于右边规划值，出现剩余量。 4?试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关 系。 答：可行解：满足约束条件 扎—‘丸 的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5 ?用表格单纯形法求解如下线性规划 解：标准化 1 可行基：对应于基可行解的基，称为可行基。 基可行解 SA] + S 2

运筹学试题

运筹学试题 Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998

运筹学试题 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。 2．线性规划模型有三种参数，其名称分别为价值系数、___和___。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。 4．求最小生成树问题，常用的方法有：避圈法和 ___。 5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。 7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。 8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【】 A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零

11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【】 A．3 B．2 C．1 D．以上三种情况均有可能 12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【】 13．在运输方案中出现退化现象，是指数字格的数目【】 A．等于 m+n B．等于m+n-1 C．小于m+n-1 D．大于m+n-1 14．关于矩阵对策，下列说法错误的是【】 A．矩阵对策的解可以不是唯一的 C．矩阵对策中，当局势达到均衡时，任何一方单方面改变自己的策略，都将意味着自己更少的赢得和更大的损失 D．矩阵对策的对策值，相当于进行若干次对策后，局中人I的平均赢得或局中人Ⅱ的平均损失值 【】 A．2 8．—l C．—3 D．1 16．关于线性规划的原问题和对偶问题，下列说法正确的是【】 A．若原问题为元界解，则对偶问题也为无界解

管理运筹学(本科)(参考答案)学习版.doc

上交作业课程题目可以打印，答案必须手写，否则该门成绩0分。 管理运筹学 作业题 一、名词解释(每题3分，共15分) 1. 可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一 组决策变量的取值，都称为该线性规划的一个可行解，所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为K 。 2. 最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称 为该线性规划的一个最优解。线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。 3. 状态：指每个阶段开始时所处的自然状态或客观条件。 4. 决策树：决策树(Decision Tree ）是在已知各种情况发生概率的基础上，通过构成决策 树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。 5. 最大最小准则：最大最小准则又称小中取大法或悲观法。为不确定型决策的决策准则之 一，其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小值，即在表的最右列，再从该列中选出最大者。这种方法的基本态度是悲观与保守。其基本思路是首先找出最不利情况下的最大收益。 二、 简答题（每题6分，共24分） 1. 简述单纯形法的基本步骤。 答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数j σ对初始基可行解进行最优性检验，若0≤j σ ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至0≤j σ，求得最优解为止。 2. 简述动态规划的基本方程。 答：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与k+1过程有如下递推关系： 对于可加性指标函数，基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}(),({)(11) ( =+=++∈ 终端条件：f n+1 (s n+1) = 0

管理学管理运筹学课后答案——谢家平

管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待 定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制， 保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式， 有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数

《管理运筹学》复习题及参考答案

四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示： 根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?

1． 某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数 最少? 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2，约束形式为“≤”，X 3，X 4为松驰变量．表中解代入目标函数后得Z=10 (1)求表中a ～g 的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x 1+2x 2+4x 3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25

管理运筹学模拟试题及答案

四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题（每题２分，共20分。） 1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规 划问题求解，原问题的目标函数值等于（ C ）。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是（ B ）。 Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负 Ｃ．若B 是基，则B 一定是可逆Ｄ．非基变量的系数列向量一定是线性相关的 3．在线性规划模型中，没有非负约束的变量称为 （ D ） 多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ A ）。 Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ D ）。 A ．等式约束 B ．“≤”型约束 C ．“≥”约束 D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y 是（ B ）。 Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量 7.在运输方案中出现退化现象，是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树Ｔ的任意两个顶点间恰好有一条（ B ）。 Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的 （ B ）。 A ．最小流 B ．最大流 C ．最小费用流 D ．无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ D ） Ａ．等式约束 Ｂ．“≤”型约束 Ｃ．“≥”型约束 Ｄ．非负约束 二、多项选择题（每小题4分，共20分） 1．化一般规划模型为标准型时，可能引入的变量有 （ ） A ．松弛变量 B ．剩余变量 C ．非负变量 D ．非正变量 E ．自由变量 2．图解法求解线性规划问题的主要过程有 （ ） A ．画出可行域 B ．求出顶点坐标 C ．求最优目标值 D ．选基本解 E ．选最优解 3．表上作业法中确定换出变量的过程有 （ ） A ．判断检验数是否都非负 B ．选最大检验数 C ．确定换出变量 D ．选最小检验数 E ．确定换入变量 4．求解约束条件为“≥”型的线性规划、构造基本矩阵时，可用的变量有 （ ） A ．人工变量 B ．松弛变量 C. 负变量 D ．剩余变量 E ．稳态 变量 5．线性规划问题的主要特征有 （ ） A ．目标是线性的 B ．约束是线性的 C ．求目标最大值 D ．求目标最小值 E ．非线性 三、 计算题（共60分） 1. 下列线性规划问题化为标准型。(10分)

管理运筹学--答案

09 <<运筹>>期末考试试卷（A）答案 一、不定项选择题（每小题2分共20分） 1、A 2、B 3、ABCD 4、ABC 5、D 6、C 7、B 8、ABCD 9、ABC 10、ABC 二、名词解释（每小题4分，共20分） 1、运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用期并提供优化决策方案的科学。 2、线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。 3、如果系统中包含元素A、B、C、K….等，按照经典意义（非模糊，非统计意义）的原则来聚类。 4、系统的综合性原则是指系统内部各组成部分的联系与协调，包含要素间的协调及系统与环境问题的协调。 5、TSP问题称为“旅行推销员问题”，是指：有N个城市A、B、…….等，它们这间有一定的距离，要求一条闭合路径，由某城市出发，每个城市经历过一次，最终返回原城市，所经历的路程最短。 三、简答题（每小题5分，共28分） 1、列出一些企业产品结构优化的柔性模型约束条件。 （1）关键设备的生产能力（2）各类能源的约束（3）工艺的约束 （4）产品类结构关系，以及物流过程中上、下游产品供需的约束 （5）某些产品的下限约束（6）非负约束 2、排队规则：损失制等待制：先到先服务、后到先服务、随机服务、优先权 服务混合制 3、运筹学的特点：（1）以最优性为核心。（2）以模型化为特征（3）以计算机为主要实现手段。（4）多学科交融 4、神经元的功能：（1）整合功能（2）兴奋与抑制（3）突触延时与不应期（4）学习、遗忘与疲劳

四、应用题。（每题15分，共45分） 1、设A、B的产量为X、Y 模型：目标MAX利润=500X+900Y 约束条件：9X+4Y≤360 4X+5Y≤200 3X+10Y≤300 X、Y均大于或等于零 图解略 最优解：X=20千克 Y=24千克利润31600元 2、企业在选择运用“农村包围城市”还是“城市中心”的指导思想时，应考虑自己的条件，竞争对手的情况，宏观和中观形势。 如，我国不少实力较弱的汽车企业，在发展之初，面临国内合资企业和国外汽车巨头的压力下，以农村，或三、四线城市为突破口，先在这些国内合资企业和国外汽车巨头不太重视的地区发展市场，在积累资金、经验、管理、技术等生产经营资源后，向大城市等竞争激烈的地区进军。 如果企业与国外合资，或在资金、技术、品牌、管理等方面有较大的优势，企业可以一开始就以广州等一线城市为主战场。 3、（1）如果两国没有任何的协调，A国最终会选择报复，因为只要A国选择报复，不论B国如何选择，对A国来说都最佳选择。反之亦然。 （2）如果两国协调，如果协调成功两国的对策是都不报复，如果两国协调不成功，两国都会选择报复。

《管理运筹学》课后习题答案

第2章 线性规划的图解法 1．解： x ` A 1 (1) 可行域为OABC (2) 等值线为图中虚线部分 (3) 由图可知，最优解为B 点， 最优解：1x = 712，7152=x 。最优目标函数值：769 2．解： x 2 1 0 1 (1) 由图解法可得有唯一解 6.02.021==x x ，函数值为3.6。 (2) 无可行解 (3) 无界解 (4) 无可行解 (5) 无穷多解

(6) 有唯一解 38320 21== x x ，函数值为392。 3．解： (1). 标准形式： 3212100023m ax s s s x x f ++++= 0,,,,9 2213 2330 2932121321221121≥=++=++=++s s s x x s x x s x x s x x (2). 标准形式： 21210064m in s s x x f +++= ,,,4 6710 26 3212121221121≥=-=++=--s s x x x x s x x s x x (3). 标准形式： 21''2'2'10022m in s s x x x f +++-= 0,,,,30 22350 55270 55321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x 4．解： 标准形式： 212100510m ax s s x x z +++= ,,,8259 432121221121≥=++=++s s x x s x x s x x 松弛变量（0，0） 最优解为 1x =1，x 2=3/2.

运筹学考试练习题(天津大学)

07级工管运筹学期末习题课 一、考虑线性规划问题（P ）max 0 z CX AX b X ==?? ≥? （1） 若12,X X 均为（P ）的可行解，[0,1]λ∈，证明12(1)X X λλ+-也是（P ） 的可行解； （2） 写出（P ）的对偶模型（仍用矩阵式表示）。 二、有三个线性规划： (Ⅰ) [Min] z =CX (Ⅱ) [Min] z =CX (Ⅲ) [Min] z =CX 约束条件AX =b 约束条件AX =b 约束条件AX =b X 0 X 0 X 0 已知 X 是(Ⅰ)的最优解，X 是(Ⅱ)的最优解，X *是(Ⅲ)的最优解，Y 是(Ⅰ)的对偶问题的最优解， 试证：（1）()()'-'-≤**C C X X 0； (2) C X X Y b b ()()***-≤-。 三、已知线性规划问题 ?? ? ??=≥+=++++=++++++++=)5,,1(03.00)(max 2 253232221212 143132121115 43322111Λj x t b x x a x a x a t b x x a x a x a st x x x c x c x t c z j 当1t ＝2t ＝0时，用单纯形法求得最终表如下： 要求：1. 确定23222113121121321,,,,,,,,,,a a a a a a b b c c c 的值； 2. 当2t ＝0时，1t 在什么范围内变化上述最优解不变； 3. 当1t ＝0时，2t 在什么范围内变化上述最优基不变。 1x 2x 3x 4x 5x 3x 5/2 0 1/2 1 1/2 0 1x 5/2 1 -1/2 0 -1/6 1/3 j j z c - -4 -4 -2

管理运筹学第二版课后习题参考答案

管理运筹学第二版课后 习题参考答案 Document number【980KGB-6898YT-769T8CB-246UT-18GG08】

《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0 i b ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。 . ??? ??≥≤++≤++0,,862383 21321321x x x x x x x x x 解：标准化 32124max x x x Z ++= . ?? ? ??≥=+++=+++0,,,,862385432153 214 321x x x x x x x x x x x x x 列出单纯形表

《管理运筹学》期中复习题答案

《管理运筹学》期中复习题 答案 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-

《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1．线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2．图解法适用于含有 两个 _ 变量的线性规划问题。 3．线性规划问题的可行解是指满足 所有约束条件_ 的解。 4．在线性规划问题的基本解中，所有的非基变量等于 零 。 5．在线性规划问题中，基本可行解的非零分量所对应的列向量线性 无 关 6．若线性规划问题有最优解，则最优解一定可以在可行域的 顶点_ 达到。 7．若线性规划问题有可行解，则 一定 _ 有基本可行解。 8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9．满足 非负 _ 条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰变量在目标函数中的系数为 正 。 11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12．线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13．线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14．线性规划问题的标准形式中，约束条件取 等 _ 式，目标函数求 最大 _值，而所有决策变量必须 非负 。 15．线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解，反之不然 16．在用图解法求解线性规划问题时，如果取得最值的等值线与可行域的一段边界重合，则 _ 最优解不唯一 。 17．求解线性规划问题可能的结果有 唯一最优解，无穷多最优解，无界解，无可行解 。 18.如果某个约束条件是“ ”情形，若化为标准形式，需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量，则应引进两个非负变量X j ′ , X j 〞, 同时令X j ＝ X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中，a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22．线性规划的代数解法主要利用了代数消去法的原理，实现_ 基变量 的转换，寻找最优解。 23．对于目标函数最大值型的线性规划问题，用单纯型法代数形式求解时，当非基变量检验数_ 非正 时，当前解为最优解。 24．在单纯形迭代中，选出基变量时应遵循_ 最小比值 法则。 二、单选题 1． 如果一个线性规划问题有n 个变量，m 个约束方程(m

2019管理运筹学课后答案

第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk 的检验数σk> 0 ，但其对应的系数列向量P k' 中，每一个元素a ik' (i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。

《管理运筹学》考试试卷A,B卷

《管理运筹学》考试试卷（A） 一、（20 分）下述线性规划问题 Max z=-5x1+5x2+13x3 ST -x1+x2+3x3 ≤ 20 ——① 12x1+4x2+10x3 ≤ 90 ——② x1,x2,x3 ≥ 0 先用单纯形法求出最优解，然后分析在下列条件下，最优解分别有什么变化？ （ 1 ）约束条件①的右端常数由20 变为30 ； （ 2 ）约束条件②的右端常数由90 变为70 ； （ 3 ）目标函数中的x3 的系数由13 变为8 ； （ 4 ）增加一个约束条件③2x1+3x2+5x3 ≤ 50 （ 5 ）将原有约束条件②变为10x1+5x2+10x3 ≤ 100 二、（10 分）已知线性规划问题 Max z= 2x1+x2+5x3+6x4 对偶变量 2x1 +x3+x4 ≤ 8 y1 2x1+2x2+x3+2x4 ≤ 12 y2 x1,x2,x3,x4 ≥ 0 其对偶问题的最优解为y1*=4 ，y2*=1 ，试用对偶问题的性质，求原问题的最优解。

三、（10 分）某地区有三个化肥厂，除供应外地区需要外，估计每年可供应本地区的数字为：化肥厂 A —— 7 万吨，B —— 8 万吨，C —— 3 万吨。有四个产粮区需要该种化肥，需要量为：甲地区—— 6 万吨，乙地区—— 6 万吨，丙地区—— 3 万吨，丁地区—— 3 万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示（单位：元/ 吨）： 根据上述资料指定一个使总的运费最小的化肥调拨方案。 四、（10 分）需要分配5 人去做5 项工作，每人做各项工作的能力评分见下表。应如何分派，才能使总的得分最大？ 五、（10 分）用动态规划方法求解： Max F=4x 1 2 -x 2 2 +2x 3 2 +12 3x 1 +2x 2 +x 3 =9 x1,x2,x3 ≥ 0 六、（10 分）公司决定使用1000 万元开发A 、B 、C 三种产品，。经预测估计开发

运筹学考试复习题及参考答案

《运筹学试题与答案》 一、判断题：在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“T”，错误者 写“F”。 1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。( ) 2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j≤0，则问题达到最优。( ) 3. 若线性规划的可行域非空有界，则其顶点中必存在最优解。( ) 4. 满足线性规划问题所有约束条件的解称为可行解。( ) 5. 在线性规划问题的求解过程中，基变量和非机变量的个数是固定的。( ) 6. 对偶问题的对偶是原问题。( ) 7. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的。( ) 8. 运输问题的可行解中基变量的个数不一定遵循m＋n－1的规则。( ) 9. 指派问题的解中基变量的个数为m＋n。( ) 10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。( ) 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。( ) 12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。( ) 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。( ) 14. 单目标决策时，用不同方法确定的最佳方案往往是不一致的。( ) 15. 动态规则中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ( ) 二、单项选择题 1、对于线性规划问题标准型：maxZ=CX, AX=b, X≥0, 利用单纯形法求解时，每作一次迭代，都能保证它相应的目标函数值Z必为（）。 A. 增大 B. 不减少 C. 减少 D. 不增大 2、若线性规划问题的最优解不唯一，则在最优单纯形表上（）。 A. 非基变量的检验数都为零 B. 非基变量检验数必有为零 C. 非基变量检验数不必有为零者 D. 非基变量的检验数都小于零 3、线性规划问题的数学模型由目标函数、约束条件和（）三个部分组成。 A. 非负条件 B. 顶点集合 C. 最优解 D. 决策变量 4、已知x1= ( 2, 4), x2=(4, 8)是某线性规划问题的两个最优解，则（）也是该线性规划问题的最优解。 A. （4，4） B. (1,2) C. (2,3) D. 无法判断 5、下列数学模型中，（）是线性规划模型。 MaxZ= 10x1+x2-3x3 x21+5x2≤15

管理运筹学整理答案

第二章 2.5 表2-3为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 12max 53z x x =+，约束形式为≤，34,x x 为松弛变量，表中解代入目标函数后得10z =。 (1)求a ~g 的值； (2)表中给出的解是否为最优解。 解：a=2,b=0,c=0,d=1,e=4/5,f=0,g=5；表中给出的解为最优解。 2.6 表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表，45,x x 为松弛变量，求表中a ~l 的值及各变量下标m ~t 的值。 解：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0；变量的下标为m —4,n —5,s —1,t —6 2.10下述线性规划问题：

2.11某单位加工制作100套工架，每套工架需用长为2.9m 、2.1m 和1.5m 的圆钢各一根。已知原材料长7.4m 。问如何下料使得所用的原材料最省？ 解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm 和1.5m 的圆钢做成一套工架，每根原材料剩下料头0.9m ，要完成100套工架，就需要用100根原材料，共剩余90m 料头。若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。 实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。 设按方案A,B,C,D,E 下料的原材料数分别为x 1,x 2,x 3,x 4,x 5，根据表2-5可以得到下面的线性规划模型 12345124345 1235min 00.10.20.30.82100 22100..3231000,1,2,3,4,5 i z x x x x x x x x x x x s t x x x x x i =++++++=??++=?? +++=??≥=? 用大M 法求解此模型的过程如表2-6所示，最优解为：x *=(0,40,30,20,0)T ，最优值为z *=16。