管理运筹学课后答案

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

minz?x1?2x2?4x3??3x1?2x2?2x3?19??4x?3x?4x?14 （1）

?123s..t??5x1?2x2?4x3??26?x1?0,x2?0,x3无约束?解：（1）令x1'??x1,x3?x3'?x3\,z'??z，则得到标准型为（其中M为一个任意大的正

数）

maxz'??2x1'?2x2?4x3'?4x3''?0x4?0x5?Mx6?Mx7??3x1'?2x2?2x3'?2x3''?x4?19

s..t??4x1'?3x2?4x3'?4x3''?x5?x6?14?5x1'?2x2?4x3'?4x3''?x7?26??x1',x2,x3',x3'',x4,x5,x6,x7?0初始单纯形表如表2-1所示：

表2-1 cj -2 2 4 -4 0 0 -M -M CB XB b x1' x2 x3' xx? 3'' 4 x5 x6 x7 0 x4 19 3 2 2 -2 1 0 0 0 19/3 -M x6 14 [ 4 ] 3 4 -4 0 -1 1 0 14/4 -M x7 26 5 2 4 -4 0 0 0 1 26/5 -z -2+9M 2+5M 4+8M -4-8M 0 -M 0 0

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

maxz?2x1?x2?x3?minz?5x1?2x2?3x3?2x4 （1）

?3x1?x2?x3?60x?x?2x?10 （2） ?s..t??123s..t?x1?2x2?3x3?4x4?7

?x?2x1?2x2?x3?2x4?31?x2?2x3?20???x?x1,x2,x3,x4?01,x2,x3?0解：（1）最优解为x*?(15,5,0)T,z*?25。

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

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

maxz?2xminz?4x1?3x2?5x31?x2（1） ?x?3x （1?1?x2?x3?7?x2?3s..t?2） ?2x?4x1?3x2?x3?6 1?5x2?x3?10s..t???x,x,x?0?x1?2x2?x4?4123??x1,x2,x3,x4?0解：（1）最优解为x*?(6.429,0.571,0)T,z*?14.571。 （2）最优解为x*?(0.4,1.8,1,0)T,z*?3.4。

1

2.6 已知线性规划问题

minZ?2x1?3x2?5x3?2x4?3x5?x1?x2?2x3?x4?3x5?4?s..t?2x1?x2?3x3?x4?x5?3?x?0,j?1,2,,5?j 解：先写出它的对偶问题

**其对偶问题最优解为y1?4/5,y2?3/5;Z*?5。试用对偶理论找出原问题最优解。

maxw?4y1?3y2?y1?2y2?2?y?y?3?12

??2y1?3y2?5s..t??y1?y2?2?3y1?y2?3???y1,y2?0**将y1?4/5,y2?3/5代入约束条件可知，第2、3、4个约束为严格不等式，因此，由互

*****补松弛性得x2?x3?x4?0。又因为y1,y2?0，所以原问题的两个约束条件应取等式，因

此有

**??x1?3x5?4 ? ?**??2x1?x5?3故原问题最优解为X*?(1,0,0,0,1)T,z*?5。

*??x1?1 ?*??x5?1

2.12 现有线性规划问题

maxz??5x1?5x2?13x3??x1?x2?3x3?20

?s..t?12x1?4x2?10x3?90?x,x,x?0?123 （1）约束条件①的右端项系数由20变为30；

（2）约束条件②的右端项系数由90变为70； （3）目标函数中x3的系数由13变为8； （4）x1的系数列向量由(?1,12)变为(0,5)； （5）将原约束条件②改变为10x1?5x2?10x3?100； （6）增加一个约束条件2x1?3x2?5x3?50。

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

maxz??5x1?5x2?13x3?0x4?0x5TT① ②

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

?20??x1?x2?3x3?x4?s..t?12x1?4x2?10x3?x5?90?x,x,x,x,x?0?12345

2

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

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

?10??30??30? B?1b????90????30??41??????列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。

表2-11 cj CB 0 0 XB x4 x5 cj-zj 13 0 x3 x5 cj-zj 5 0 x2 x5 cj-zj

表2-12 cj CB 5 0 XB x2 X5 cj-zj 5 13 x2 x3 cj-zj 0 13 x4 x3 cj-zj

3 9 -15 15 b 30 -30 -5 x1 -1 16 0 23 -8 -16 -23/5 6/5 -103/5 5 x2 1 0 0 1 0 0 -1/5 2/5 -1/5 13 x3 3 [ -2 ] -2 0 1 0 0 1 0 0 x4 1 -4 -5 [ -5 ] 2 -1 1 0 0 0 x5 0 1 0 3/2 -1/2 -1 -3/10 1/10 -13/10 20 10 20/3 70/3 b 20 90 -5 x1 -1 12 -5 -1/3 46/3 -2/3 -1 16 0 5 x2 1 4 5 [ 1/3 ] 2/3 2/3 1 0 0 13 x3 [ 3 ] 10 13 1 0 0 3 -2 -2 0 x4 1 0 0 1/3 -10/3 -13/3 1 -4 -5 0 x5 0 1 0 0 1 0 0 1 0 θi 20/3 9 20 35 由表2-12中计算结果可知，LP问题的最优解变为X*?(0,0,9,3,0)T,z*?13?9?117。 （2）约束条件②的右端常数由90变为70，则有

?10??20??20?B?1b????????

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

3

表2-13 cj CB 5 0 XB x2 X5 cj-zj 5 13 x2 x3 cj-zj

5 5 b 20 -10 -5 x1 -1 16 0 23 -8 -16 5 x2 1 0 0 1 0 0 13 x3 3 [ -2 ] -2 0 1 0 0 x4 1 -4 -5 -5 2 -1 0 x5 0 1 0 3/2 -1/2 -1 由表2-13结果知，LP问题的最优解变为X*?(0,5,5,0,0)T,z*?5?5?13?5?90。 （3）目标函数中x3的系数由13变为8，由于x3是非基变量，其检验数变为

?3?8?5?3?0?(?2)??7?0 所以LP问题的最优解不变。

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

?10??0??0? 'B?1P?1??41??5???5???????从而x1在最终单纯形表中的检验数变为

' ?1'?c1?CBB?1P1??5?(5,0)????5?05?0???所以LP问题的最优解保持不变。

（5）将原约束条件②改变为10x1+5x2+10x3≤100，则x1在最终单纯形表中系数列向量变'?1T'?1T为P1?BP1?(?1,14)，检验数?1?c1?CBBP1??5?(5,0)(?1,14)?0

x2在最终单纯形表中系数列向量变为P2'?B?1P2?(1,1)T，检验数

'?2?c2?CBB?1P2?5?(5,0)(1,1)T?0。

10??20??20?又因B?1b??的各分量均大于0，故LP问题的最优解不变。

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

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

表2-14 cj CB XB b -5 x1 5 x2 13 x3 0 x4 0 x5 0 x6 4

5 x2 20 -1 1 3 1 0 0 0 x5 10 16 0 -2 -4 1 0 0 x6 50 2 3 5 0 0 1 5 x2 20 -1 1 3 1 0 0 0 x5 10 16 0 -2 -4 1 0 0 x6 -10 5 0 [ -4 ] -3 0 1 cj - zj 0 0 -2 -5 0 0 5 x2 25/2 11/4 1 0 -5/4 0 3/4 0 x5 15 27/2 0 0 -5/2 1 -1/2 13 x3 5/2 -5/4 0 1 3/4 0 -1/4 cj - zj -5/2 0 0 -7/2 0 -1/2

3.1 分别用分支定界法和割平面法求解下列整数规划模型。 （1）minz??4x1?3x2 （2）maxz?x1?x2

?4x1?x2?10?2x1s..t??2x1?3x2?8 s..t??x2?6?4x1?5x2?20 ??x1,x2?0,且为整数??x1,x2?0,且为整数解：（1）求解得到最优解x*?2,x*12?1,z*??11。

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

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

maxz?x1?x2?0x3?0x4?2x1?x2?x3?6s..t?

?4x?1?5x2??x4?20?x1,x2,x3,x4?0且为整数不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表3-1所示。

表3-1 cj 1 1 0 0 CB XB b x1 x2 x3 x?i 4 0 x3 6 2 1 1 0 6 0 x4 20 4 [ 5 ] 0 1 4 cj-zj 1 1 0 0 0 x3 2 [ 6/5 ] 0 1 -1/5 5/3 1 x2 4 4/5 1 0 1/5 5 cj-zj 1/5 0 0 -1/5 1 x1 5/3 1 0 5/6 -1/6 1 x2 8/3 0 1 -2/3 1/3 cj-zj 0 0 -1/6 -1/30

5

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

2/3?1/3(x3?x4)?0 即

?x3?x4??2

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

表3-2 cj CB 1 1 0 XB x1 x2 x5 cj-zj 1 1 0 x1 x2 x4 cj-zj

2 2 2 b 5/3 8/3 -2 1 x1 1 0 0 0 1 0 0 0 1 x2 0 1 0 0 0 1 0 0 0 x3 5/6 -2/3 -1 -1/6 1 -1 1 0 0 x4 -1/6 1/3 [ -1 ] -1/30 0 0 1 0 0 x5 0 0 1 0 -1/6 1/3 -1 -1/6 由于x1,x2的值均为整数，所以得到原问题的最优解为x*?(2,2)T,z*?4

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

表3-3 （费用单位：元） 地点 1 2 3 4 机器总数 机器 1 2 3 4 需要量 10 3 2 4 1 9 4 1 3 1 8 5 1 5 1 7 6 2 6 1 1 1 1 1

?1,如果机器i安装在地点j解：设 xij??

0,否则?

6

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

目标函数：

minz???i?1444j?1ijijcx

约束条件：

? (2)每一个地点只能有一台机器，即 ?x(1)每一部机器只分配在一个地点，即

4j?1ijx?1i?1,2,3,4

i?1ij?1j?1,2,3,4

(3) xij?0或1

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

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

表3-17 需求 产地 A B C 最低需求(万吨) 最高需求(万吨) I 16 14 19 30 50 II 13 13 20 70 70 III 22 19 23 0 30 IV 17 15 -- 10 不限 产量(万吨) 50 60 50

解：这是一个产销不平衡的运输问题，总产量为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 销地 产地 A B

I I’ II III IV IV’ 产量 50 60 7

C D 销量

表3-19 销地 产地 A B C D

表3-20 销地 产地 A B C D 销量 30 20 70 30 10 50 50 50 I 16 14 19 M I’ 16 14 19 0 II 13 13 20 M III 22 19 23 0 IV 17 15 M M IV’ 17 15 M 0 I 30 30 I’ 20 20 II 50 20 0 70 III 30 30 IV 10 10 IV’ 30 20 50 产量 50 60 50 50

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

???（1）minz?P 1(d1?d1)?P2d3?x1?2x2?d1??d1??50????2x1?x2?d2?d2?40 s..t????2x1?2x2?d3?d3?80?x,x,d?,d??0,i?1,2,3?12ii解：（1）本题的三个约束条件都是目标约束，有三个负偏差变量，因此选择负偏差变量为初始基变量。并计算出各非基变量的检验数，得到初始的单纯形表如表4-1所示。

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

表4-1 cj CB P1 XB b 50 0 x1 1 0 x2 [ 2 ] P1 0 0 P1 P2 0 ?d1 1 ?d1 -1 ?d2 0 ?d2 0 ?d3 0 d3 0 ?? 25 d1 ? 8

0 P2 σj d2 d3 ??40 80 P1 P2 2 2 -1 -2 1 2 -2 -2 0 0 0 0 0 0 1 0 1 0 0 0 -1 0 1 0 0 1 0 0 0 -1 0 1 40 40

表4-2 cj CB 0 0 P2 σj

XB x2 ?0 b 25 15 30 P1 P2 x1 1/2 [ 3/2 ] 1 0 -1 0 x2 1 0 0 0 0 P1 0 0 P1 P2 0 d1 1/2 -1/2 -1 1 1 ?d1 -1/2 1/2 1 0 -1 ?d2 0 1 0 0 0 ?d2 0 -1 0 1 0 ?d3 0 0 1 0 0 ?d3 0 0 -1 0 1 ?? 50 10 30 d2 d3 ?尽管x1与d1?具有相同的负检验数，但根据前面讨论的原则，由于x1是决策变量，选择

?x1进基，用最小比值法确定d2出基，换基后，计算所得新的基本可行解如表4-3所示。

表4-3 cj CB 0 0 P2 σj

XB x2 x1 b 20 10 20 P1 P2 0 x1 0 1 0 0 0 0 x2 1 0 0 0 0 P1 0 0 P1 P2 0 d1 2/3 -1/3 -2/3 1 2/3 ?d1 -2/3 [ 1/3 ] 2/3 0 -2/3 ?d2 -1/3 2/3 -2/3 0 2/3 ?d2 1/3 -2/3 2/3 1 -2/3 ?d3 0 0 1 0 0 ?d3 0 0 -1 0 1 ?? — 30 30 d3 ?首项系数小于零的检验数只有d1?的为?2/3P2，因此d1?应当进基，由于存在两个最小比值，取下标最小的变量出基，因此x1出基，换基后，再计算新的基本可行解，如表4-4所示。

表4-4 cj CB 0 0 P2 σj

XB x2 ?0 b 40 30 0 P1 x1 2 3 -2 0 0 x2 1 0 0 0 P1 0 0 P1 P2 0 d1 0 -1 0 1 ?d1 0 1 0 0 ?d2 1 2 -2 0 ?d2 -1 -2 2 1 ?d3 0 0 1 0 ?d3 0 0 -1 0 ?? d1 d3 ?9

P2

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

=40,d1?=30，其他偏差变量都等于零。

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

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

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

minZ?p1d1??p2d2??p3d3?? p4(d4??d4??d5??d5??d6??d6?)?500x1?650x2?800x3?d1??d1??16000????6x1?8x2?10x3?d2?d2?200?d??d??d??2433?2? s.t. ?x1?d4??d4??12???x?d?d?10255??x?d??d??666 ?3????x1,x2,x3?0,di,di?0(i?1,2,,6)

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出发到B3、C3或D3，第2阶段从B3、C3或D3出发到B2、C2或D2，第3阶段从B2、C2或D2出发到B1、C1或D1，第4阶段从B1、C1或D1出发到A；

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

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

10

指标函数vk4??vi表示k至第4阶段的总路长；

i?k4递推公式fk?min{vk?fk?1},k?4,3,2,1;f5?0 计算过程如表5-1所示。

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

表5-1 k sk xk vk vk4=vk+fk+1 fk xk* B1 A 3 3+0 3 A 4 C1 A 8 8+0 8 A D1 A 7 7+0 7 A B 4 4+3 B12 C1 2 2+8 7 B1 B1 3 3+3 3 C2 C1 8 8+8 6 B1 D1 7 7+7 DC1 4 4+8 2 D1 6 6+7 12 C1 BB2 10 10+7 3 C2 13 13+6 17 B2 B2 12 12+7 2 C3 C2 5 5+6 11 C2 D2 6 6+12 C7 7+6 D2 3 D2 8 8+12 13 C2 B B3 9 9+17 C3 5 5+11 16 C3 B3 10 10+17 1 C C3 10 10+11 21 C3、D3 D3 8 8+13 D C3 15 15+11 D3 7 7+13 20 D3

11

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

表5-2 设备数 工厂 甲 乙 丙 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12

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

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

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

fk(sk)表示sk台设备分配给第k个工厂至第n个工厂时所得到得最大赢利值。 由以上的假设可写出逆推关系式为

[Pk(xk)?fk?1(sk?xk)],k?3,2,1??fk(sk)?0max?xk?sk ???f4(s4)?0下面采用逆推法进行计算。 第3阶段：

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

f3(s3)?max[P3(x3)]

x3其中x3=s3=0,1,2,3,4,5。

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

表5-3

表中x表示使f3(s3)为最大值时的最优决策。 第2阶段：

12

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

f2(s2)?max[P2(x2)?f3(s2?x2)]

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

因为给乙工厂x2台，其盈利为P2(x2)，余下的s2-x2台就给丙工厂，则它的盈利最大值为f3(s2-x2)。现要选择x2的值使P2(x2)?f3(s2?x2)取最大值。其数值计算如表5-4所示。

表5-4

第1阶段：

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

f1(5)?max[P1(x1)?f2(5?x1)]x1其中x1=0,1,2,3,4,5。

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

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

表5-5

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

****（1）由于x1=5 - 0=5，查表5-4知x2=5-2=3，故?0，根据s2=s1 -x1?2，由s3=s2 -x2*x3?s3?3。即甲工厂分配0台、乙工厂分配2台、丙工厂分配3台。

****（2）由于x1=5 - 2=3，查表5-4知x2=3-2=1，故?2，根据s2=s1 -x1?2，由s3=s2 -x2*x3?s3?1。即甲工厂分配2台、乙工厂分配2台、丙工厂分配1台。

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

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

13

可得到：

******当设备台数位4台时，最优分配方案为x1?1,x2?2,x3?1或x1?2,x2?2,x3?0，总盈利为17万元。

**当设备台数位3台时，最优分配方案为：x1*?0,x2?2,x3?1，总盈利为14万元。

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

表5-6 货物代号 1 2 重量(吨) 2 3 价值(千元) 3 4 货物代号 3 4 重量(吨) 4 5 价值(千元) 5 6

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

maxz?3x1?4x2?5x3?6x4 ?2x1?3x2?4x3?5x4?15s..t??xi?0,且为整数(i?1,2,3,4) 将其转化为动态规划问题，分为4个阶段，每个阶段的指标函数记为

g1(x1)?3x1， g2(x2)?4x2， g3(x3)?5x3， g4(x4)?6x4

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

sk??(i?1)xi(k?1,2,3,4)

i?k4允许状态集合为Sk?{0,1,2,,15},k?1,2,3,4，最优值函数fk(sk)表示装载第k种至第4中

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

??gk(xk)?fk?1(sk?1)??fk(sk)?xkmax?Dk(sk) ???f5(s5)?0(k?4,3,2,1)状态转移方程为

sk?1?sk?(k?1)xk,k?1,2,3,4

允许决策集合为

?Dk(sk)??0,1,2,??s??,?k??,(k?1,2,3,4) ?k?1??即表示在载重量允许的范围内可能装载第k种货物的件数。 用逆推方法求解如下：

k?4:f4(s4)?max{6x4},x4?D4(s4),s4?S4

??s??D4(s4)??0,1,2,,?4??,S4?{0,1,2,,15}；

?5???k?3:f3(s3)?max{5x3?f4(s4)},x3?D3(s3),s3?S3

14

??s??D3(s3)??0,1,2,,?3??,S3?{0,1,2,,15},s4?s3?4x3；

?4???k?2:f2(s2)?max{4x2?f3(s3)},x2?D2(s2),s2?S2 ??s??D2(s2)??0,1,2,,?2??,S2?{0,1,2,,15},s3?s2?3x2；

?3???k?1:f1(s1)?max{3x1?f2(s2)},x1?D1(15),s1?15

D1(15)??0,1,2,

,7?,s2?15?2x1。

****最后得到问题的最优解为x1?6,x2?1,x3?0,x4?0，最优值为22千克。

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

?1/2?1?1??2?21?? （1）?11/2?1 （2）?????145???1?11?? ??1?6??2?2 （3）??3??272235431?91??6??4? （4）?24????56???3ijji??4338?

?6221?2354??54673180?解：（1）由于maxminaij??1,minmaxaij?1/2，所以A所对应的支付矩阵没有纯对策。

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

（2）由于maxminaij??1,minmaxaij?2，所以A所对应的支付矩阵没有纯对策。

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

（3）根据赢得矩阵有maxminaij?minmaxaij?a31?3，所以G的解为

ijji(?3,?1),vG?3。

（4）根据赢得矩阵有maxminaij?minmaxaij?a23?4，所以G的解为

ijji(?2,?3),vG?4。

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

表7-1 A1 A2

B1 0.4 0.3

B2 0.8 0.7

B3 0.6 0.4

15

A3 0.5 0.9 0.5

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

ABmaxminaij?minmaxaij?0.5

ijji可得，局中人甲采用策略A3、局中人乙采用策略B1，各获得50%的市场占有率。

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

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

表10-1 单位：元

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

（2）若Pj值仍是未知的，并且?是乐观系数，问?取何值时，方案S1和S3是不偏不倚的？

（3）若P1=0.2,P2=0.7,P3=0.1,那么用EMV准则会选择哪个方案？

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

（2）0.10256； （3）方案S1或S3。

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

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

表10-7 概率 方案 猜白 猜黑 白0.7 500 -150 自然状态 黑0.3 -200 1000 16

解：先画出决策树，见图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.

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

17

解：其决策表见表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期望值大，所以合理决策是买专利。

18

本文来源：https://www.bwwdw.com/article/savr.html