《应用运筹学》补充练习题参考答案
1、某商店要制定明年第一季度某种商品的进货和销售计划，已知该店的仓库容量最多可储存
该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。已知各个月份进货和销售该种商品的单价如下表所示：
现在要确定每个月进货和销售多少件，才能使总利润最大，把这个问题表达成一个线性规划模型。
解：设X i是第i个月的进货件数，Y i是第i个月的销货件数（i=1, 2, 3），Z是总利润，于是这个问题可表达为：
目标函数： Max Z=9Y1+8Y2+10Y3－8X1－5X2－9X3
约束条件： 200+X1≤500
200+X1－Y1+X2≤500 月初库存约束
200+X1－Y1＋X2－Y2＋X3≤500
200+X1-Y1≥ 0
200+X1-Y1+X2-Y2≥ 0 月末库存约束
200+X1-Y1+X2-Y2+X3-Y3≥ 0
X1，X2，X3，Y1，Y2，Y3≥0
EXCEL求解最优解结果：X1*=300，X2*=500，X3*=0，Y1*=500,Y2*=0，Y3*=500, Z*=4100
2、一种产品包含三个部件，它们是由四个车间生产的，每个车间的生产小时总数是有限的，
下表中给出三个部件的生产率，目标是要确定每个车间应该把多少工时数分配到各个部件上，才能使完成的产品件数最多。把这个问题表示成一个线性规划问题
解：设X ij是车间i在制造部件j上所花的小时数，Y是完成产品的件数。
最终的目的是Y要满足条件：
min{10X11+15X21+20X31+10X41，15X12+10X22+5X32+15X42，5X13+5X23+10X33+20X43}
可将以上非线性条件转化为以下线性规划模型：
目标函数： Max Z = Y
约束条件： Y≤10X11+15X21+20X31+10X41
Y≤15X12+10X22+5X32+15X42
Y≤5X13+5X23+10X33+20X43
X11+X12+X13≤100
X21+X22+X23≤150
X31+X32+X33≤80
X41+X42+X43≤200
X ij≥0（i=1，2，3，4；j=1，2，3）, Y≥0
EXCEL求解最优解结果：X11*=，X12*=，X13*=， X21*=， X22*=， X23*=
X31*=，X32*=，X33*=， Y* =
3、一个投资者打算把它的100000元进行投资，有两种投资方案可供选择。第一种投资保证
每１元投资一年后可赚７角钱。第二种投资保证每１元投资两年后可赚２元。但对第二种投资，投资的时间必须是两年的倍数才行。假设每年年初都可投资。为了使投资者在第三年年底赚到的钱最多，他应该怎样投资？把这个问题表示成一个线性规划问题。
解：设X i1和X i2是第一种方案和第二种方案在第i年年初的投资额（i =1, 2, 3），Z是总利润，于是这个问题的线性规划模型是：
目标函数：Max Z= 2X22+（第三年年末的收益为当年第一方案和第二年第二方案的收益）
约束条件：X11+X12≤100 000 (第一年年初总投资额不超过计划投资额)
X21+X22≤（第二年年初投资额不超过第一年第一方案投资收回的本利值）
X31≤3X12+（第三年年初投资额不超过第二年年底收回的本利值）
X i1，X i2≥0（i=1，2，3）
EXCEL求解最优解结果：X11*=，X12*=，X21*=， X22*=， X31*=， Z*=
4、有A，B两种产品，都需要经过前后两道化学反应过程。每一个单位的A产品需要前道过
程２小时和后道过程３小时。每一个单位的B产品需要前道过程３小时和后道过程４小时。
可供利用的前道过程有16小时，后道过程时间有24小时。每生产一个单位B产品的同时，会产生两个单位的副产品C，且不需要外加任何费用。副产品C最多可售出５个单位，其余的只能加以销毁，每个单位的销毁费用是２元。出售A产品每单位可获利４元，B产品每单位可获利10元，而出售副产品C每单位可获利3元。试建立为了使获得的总利润达到最大的线性规划模型。
解：设X1，X2分别是产品A，产品B的产量，X3是副产品C的销售量，X4是副产品C的销毁量，Z是总利润，于是这个问题的线性规划模型是：
目标函数：Max Z=4X1+10X2+3X3—2X4
约束条件： 2X2= X3+X4
X3≤5
2X1+3X3≤16
3X1+4X2≤24
X1，X2，X3，X4≥0
EXCEL求解最优解结果：X1*=，X2*=，X3*=， Z*=
5、考虑下面的线性规划问题：
目标函数：Max Z=30X1+20X2
约束条件： 2X1+ X2≤40
X1+X2≤25
X1，X2≥0
用图解法找出最优解X1和X2。
解：图解法结果如下，最优解：X1*=15; X2=10; Z*=650
6、某厂生产甲，乙两种产品，每种产品都要在A,B两道工序上加工。其中B工序可由B1或
B2设备完成，但乙产品不能用B1加工。生产这两种产品都需要C,D,E三种原材料，有关数据如下所示。又据市场预测，甲产品每天销售不超过30件。问应如何安排生产才能获
解：设甲、乙两种产品分别生产X1，X2件，其中，甲产品在B1设备上加工X3工时、在B2设备上加工X4工时，则获利为：
Z=80X1+100X2-6(2X1+X2)-2X3-5*(X4+4X2)-2*(3X1+12X2)-1*(5X1+3X2)-
4*(4X1+-26X1-29X2 化简后得到：
目标函数：Max Z=15X1+12X2－2X3－5X4
. 2X1+X2≤80
X3≤60
4X2+X4≤70
3X1+12X2≤300
5X1+3X2≤100
4X1+≤150
X1≤30
X 1=
3
X 3
+X 4 (B1每工时完成31件甲产品，共X 3个工时，B2完成X 4件)
X j ≥0, j=1,2,3,4
EXCEL 求解最优解结果：X 1*= ，X 2*= ，X 3*=， X 4*= , Z*=
7、制造某机床需要A 、B 、C 三种轴，其规格和需要量如下表所示。各种轴都用长米长的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立线性规划模型。
解：用米圆钢截所需规格长度的所有各种可能性如下表所示：
设按第j 种截法截X j 根圆钢，则相应的线性规划模型为： 目标函数： Min Z =∑=5
1j X j
: X 1+X 2 ≥100
X 1+ 2X 3+ X 4 ≥200 2X 2+ X 3+2X 4+4X 5≥400
x j ≥0且为整数（j=1,2 (5)
EXCEL 求解最优解结果：X 1*= 0 ，X 2*=100 ，X 3*= 100 , X 4*= 0 , X 5*= 25 , Z*= 225 8、某木材公司经营的木材贮存在仓库中，最大贮存量为20万米3
，由于木材价格随季节变化，该公司于每季初购进木材，一部分当季出售，一部分贮存以后出售。贮存费为a+bu ，其中
a=7元/米3，b=10元/米3
，u 为贮存的季度数。由于木材久贮易损，因此当年所有库存应于秋末售完。各季木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立线性规划模型。
解：设Y i （i=1,2,3,4）分别为冬，春，夏，秋四季采购的木材量（单位：m 3
），X ij （i ，j=1，
2，3，4）代表第i 季节采购用于第j 季节销售的木材量（m 3
），因此，
冬季以310元/ m3购入Y1, 当季以321元/ m3卖出X11,同时，以7+10*1的成本存储到春季出售的有X12,以7+10*2的成本存储到夏季出售的有X13, 以7+10*3的成本存储到秋季出售的有X14；同样地，春季购入 ......。
相应的线性规划模型为：
目标函数：MaxZ=（321X11+316X12+325X13+307X14－310Y1）
+（333X22+335X23+317X24－325Y2）＋（352X33+327X34－348Y3）
+（344X44－340Y4）
: Y1≤200 000
Y1－X11－X12－X13－X14=0
X11 ≤100 000
X12+X13+X14+Y2≤200 000
Y2－X22－X23－X24 =0
X12+X22≤140 000
X13+X14+X23+X24+Y3≤200 000
Y3―X33―X3 4＝0
X13+X23+X33 ≤200 000
X14+X24+X34+Y4≤200 000
Y4－X44 =0
X14+X24+X34+X44 ≤160 000
x ij≥0，y i≥0（i,j=1,2,3,4）
EXCEL求解最优解结果：X11*=，X12*=，X13*= ，X14*= Y1*= ,
X22*=，X23*=，X24*= ，Y2*= ,
X33*=，X34*=，Y3*= ,
X44*=，Y4*= , Z*=
9、对以下线性规划问题：
Min Z＝2X1+3X2+5X3+2X4+3X5
s. t. X1+X2+2X3+X4+3X5 ≥4
2X1 - X2+3X3+X4+X5 ≥3
X1, X2, X3, X4,X5 ≥ 0
已知其对偶问题的最优解为 Y1*=4/5, Y2*=3/5, W* = 5。试求出原问题的解。
解：设原问题的两个剩余变量分别为：X6 ,X7
原问题的对偶问题为：
Max W＝4Y1+3Y2
. Y1+2Y2≤2松弛变量 Y3
Y1-Y2≤3松弛变量 Y4
2Y1+3Y2≤5松弛变量 Y5
Y1+Y2≤2松弛变量 Y6
3Y1+ Y2≤3松弛变量 Y7
Y1,Y2,Y3,Y4≥ 0
因为Y1*=4/5, Y2*=3/5,
因此，计算对偶问题松弛变量值为：Y3*=0，Y4*=14/3，Y5*=8/5，Y6*=3/5，Y7*=0
根据对偶性质(互补松弛定理)则有：X2*=0，X3*=0，X4*=0，X6*=0，X7*=0
进一步有： 2X1+3X5=5
X1+3X5=4
2X1+X5=3
得到：X1*=1,X5*=1
原问题的解为：X1*=1, X2*=0，X3*=0，X4*=0，X5*=1,Z* = 5
10、某厂拟生产甲、乙、丙三种产品，都需要在A、B两种设备上加工，有关数据如下表。
利用对偶性质分析以下问题：
1）如何充分发挥设备潜力，使产品的总产值最大？
2）该厂如果以每台时350元的租金租外厂的A设备，是否合算？
解：设生产甲、乙、丙三种产品分别为X1,X2,X3件，线性规划模型为：
目标函数: Max Z = 3X1+2X2+X3
约束条件： X1+2X2+X3≤400 松弛变量为X4
2X1+X2+2X3≤500 松弛变量为X5
X1,X2,X3≥0
此原问题的对偶问题为：
目标函数: Min W = 400Y1+500Y2
约束条件： Y1+2Y2≥3 剩余变量为Y3
2Y1+ Y2≥2 剩余变量为Y4
Y1+2Y2≥1 剩余变量为Y5
Y1,Y2≥0
对偶问题可通过图解法求解，得到最优解结果为：
Y1* = 1/3，Y2* = 4/3
进一步可知：Y3* =0，Y4* = 0，Y5* = 2
根据互补松弛定理可知：X3*=0,X4*=0，X5*=0
可得到： X1+2X2=400
2X1+X2=500
可解得：X1*=200，X2*=100
根据以上计算结果可知：
1)应该生产甲产品200件，乙产品100件，丙产品不生产，此时总产值最大为800
千元。
2)因为Y3*=1/3，设备A的影子价格为1/3千元，小于租金350元，因此，该厂不
应该租用外厂的A设备。
11、某打井队要从10个可供选择的井位中确定5个进行探油，使总的探油费用最小。若10
个井位的代号为S1,S2,S3,……,S10，相应的探油费用为C1,C2,C3,……,C10，并且井位
选择要满足下列限制条件：
1） 或选择S1和S7，或选择S8；
2） 选择了S3或S4，就不能选S5，或反过来也一样； 3） 在S5,S6,S7,S8 中最多只能选两个。 试建立线性规划模型。
解：变量X i 取0或1，0表示不选、1表示选第i 井位； 模型如下： 目标函数： ∑=?=
10
1
i Xi Ci MinZ
2
54( 1 53( 1 871
S8(S7 1
S8(S1 1 5
.87655453878110
1
≤+++≤+≤++=+=+=∑=X X X X S S X X S S X X S S S X X X X Xi t s i 不选）不能同时选中，也可都和不选）
不能同时选中，也可都和必须且只能选一）
与表明：（以上两式同时满足时只能选一个）和只能选一个）和 X i =0,1 i=1,2, (10)
EXCEL 求解最优解结果：X 1*= ，X 2*= ，X 3*= , X 4*= , X 5*= ,
X 6*= ，X 7*= ，X 8*= , Z*= 12、某厂可生产四种产品，对于三种主要资源的单位消耗及单位利润见下表：
如果产品3的生产需要用一特殊机器，这机器的固定成本（启用成本）为3000，产品2和产品4的生产也同样需要共用一特定的机器加工，其固定成本（启用成本）为1000，写出此时求利润最大的线性规划模型。
解：1)变量：Xi 为第i 种产品的产量（i=1,2,3,4）,
Y3为0-1变量，0
030
1
33==
>X Y X
Y24为0-1变量，0
240
1
4242=+=
>+X X Y X X
2)目标函数：Max Z = X 1+7X 2+8X 3+4X 4-3000Y 3-1000Y 24 3)约束条件：
资源约束：X1+10X2+3X3≤5000
2X1+6X2+4X3+X4≤3000
2X1+2X3+5X4≤3000
启用约束：X3≤ M1Y3 (M1为一足够大的正数，比如取5000 )
X2+X4≤ M2Y24 (M2为一足够大的正数，比如取5000 )
非负约束：Xi≥0 (i=1,2,3,4)；Y3,Y24=0，1
EXCEL求解最优解结果：X1*= 0，X2*=400，X3*= 0 , X4*= 600 , Y3=0,Y24=1, Z*=4200
13、某化工厂要用三种原料D,P,H混合配置三种不同规格的产品A,B,C。各产品的规格、单价
如左表所示，各原料的单价及每天的最大供应量如右表所示，该厂应如何安排生产才能使利润最大？
解：1)变量：产品A中D,P,H含量分别为 X11,X12,X13
产品B中D,P,H含量分别为 X21,X22,X23
产品C中D,P,H含量分别为 X31,X32,X33
令：X11+X12+X13=X1
X21+X22+X23=X2
X31+X32+X33=X3
2)目标函数：Max Z = -15X11+25X12+15X13- 30X21+10X22-40X31-10X33
3)约束条件：
根据规格条件有：X11≥
X12≤
X21≥
X22≤
进一步得到： - X11+ X12+X13≤0
- X11+3X12- X13≤0
-3X21+ X22+X23≤0
- X21+ X22- X23≤0
原材料供应条件： X11+X21+X31≤100
X12+X22+X32≤100
X13+X23+X33≤60
非负约束： X ij≥0, i,j=1,2,3
EXCEL求解最优解结果：X11*= 100 ，X12*=50，X13*= 50 , X21*=0 , X22*=0 , X23*=0
X31*=0 ，X32*=0，X33*=0 , Z*=500
X1*=X11*+X12*+X13*=200,X2*=0,X3*=0;每天只生产A 200kg
X11*+X21*+X31*=100 使用D 100kg;
X12*+X22*+X32*=50 使用P 50kg;
X13*+X23*+X33*=50 使用H 50kg;
14、某产品有A1和A2两种型号，需经过B1、B2、B3三道工序，单位工时、利润、各工序每周
工时限制如下表所示，问工厂如何安排生产，才能使总利润最大（B3工序有两种加工方式B31和B32，只能选择其中一种；产品为整数）。
解： 1）设变量如下：
A1生产量为X1，A2生产量为X2；
选B31时Y1=0；不选时Y1=1
选B32时Y2=0；不选时Y2=1
2）目标函数：
Max Z = 25X1+40X2
3）约束条件：
3X1+7X2≤250
2X1+ X2≤100
3X1+5X2≤150+M*Y1 (M为足够大的正数,如取5000)
2X1+4X2≤120+M*Y2
Y1+Y2=1
X1,X2≥0且为整数,Y1,Y2=0,1
EXCEL求解最优解结果：X1*= ，X2*= ，Y1 *= , Y2 *=0 , Z*=
15、甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间（分钟）如表所示，应指派何人
加工何种工件，能使总的加工时间最少？要求建立数学模型并求解。
解：（匈牙利方法过程及模型略）
答案：甲：C；乙：A；丙：D；丁：B
16、某厂生产柴油机，1－4月份订货任务为：1月2000台；2月3000台；3月5500台；4
月6000台；该厂的月正常生产能力为3000台，每台的生产成本为1500元，每月加班生产能力为2000台，加班生产成本为每台2000元，月库存费用为每台50元，1月初库存为0。建立求成本最低生产计划的线性规划模型。
解：设X i（i=1,2,3,4）为第i个月正常生产的柴油机数，Y i为第i个月加班生产的数量，W i为第i月月初的库存数。该问题的线性规划模型为：
目标函数：Min Z = 1500(X1+X2+X3+X4)+2000(Y1+Y2+Y3+Y4)+50(W2+W3+W4)
约束条件：X1+Y1-W2 = 2000
X2+Y2+W2-W3 = 3000
X3+Y3+W3-W4=5500
X4+Y4+W4=6000
X i≤3000 （i=1,2,3,4）
Y i≤2000 （i=1,2,3,4）
X i,Y i,W i≥0, （i=1,2,3,4），且均为整数
EXCEL求解最优解结果：X1*= ，X2*= ，X3*= , X4*= , Y1*= , Y2*=
Y3*= ，Y4*= ，W1*= , W2*= , W3*= , W4*= ,
Z*=
17、某铸造厂接到一笔订货，要生产1000公斤（一吨）铸件，其成分是锰的含量至少达到％，
硅达到％－%。铸件的售价是元/公斤。工厂现存三种可以利用的生铁（A、B、C），存量很多，其性质如下表所示。此外，生产过程允许把纯锰直接加到融化金属中。各种可能的炉料费用如下：生铁A－210元/吨，生铁B－250元/吨，生铁C－150元/吨，纯锰80元/公斤。每融化一吨生铁要花费50元。应如何选择炉料才能使利润最大。
解：1)变量：
设所需生铁A X1吨，生铁B X2吨，生铁C X3吨，纯锰 X4公斤
2）目标函数：
Max Z = 1000**X1-250*X2-150*X3-80*X4-50*（X1+X2+X3）
即：Max Z = 450-260X1-300X2-200X3-80X4
3）约束条件：
%X1+%X2+%X3)*1000+X4≥%*1000 (锰的含量)
4%X1+1%X2+%X3≤% (硅的含量上限)
4%X1+1%X2+%X3≥% (硅的含量上限)
(X1+X2+X3)*1000+X4=1000
X1,X2,X3,X4≥0
EXCEL求解最优解结果：X1*= ，X2*= ，X3*= , X4*= , Z*=
18
要求：1）建立此运输问题的线性规划模型（不需要求解）；
2）由于市场情况的变化，B3 和 B4 的销量各增加了50单位（运用表上作业法可求得此时最小运费为2950元）。有关部门在研究调运方案时还需要依次考虑以下情况（已规定其优先等级 P1－P5）：
P1: B4是重点保证单位，必须尽可能满足其需要； P2: A3向B1提供的量不少于100；
P3: 因道路问题，尽量避免安排A2产品运往B4; P4: 给B1和B3的需求供应率要相等；
P5: 与最小运费调运方案相比，总运费的增加不超过最小调运方案的10%。 试建立求解满意调运方案的目标规划模型。
解：1)运输问题线性规划模型：
此问题为供需平衡问题，用C ij 表示A i 运到B j 的单位运价，a i 为Ai 的最大产量，bj
为Bj 的最大销量（i=1,2,3 ; j=1,2,3,4），则线性规划模型： 变量：设 X ij 表示A i 运到B j 的运量（i=1,2,3 ; j=1,2,3,4）
目标函数：Min Z =
∑∑==?314
1
i j ij ij
X C
约束条件：
1234
;3,2,13
,2,14,3,2,1,
04
1
3
1======≥==∑∑j i X i a X
j b X
ij
j i
ij
i j ij
2）目标规划求解：
销量增加后供不应求，因此，供应仍为绝对约束：
3,2,14
1
==∑=i a X
j i ij
需求约束为目标约束：
4,3,2,13
1
==-+∑=+
-j b d d X
i j
j j ij
(已包含了B4要尽可能满足的条件)
X 31+d 5- - d 5+
=100 (A3向B1提供的量不少于100) X 24+ d 6- - d 6+
=0 （尽量避免安排A2产品运往B4）
0450
X +X +X 200X +X +X 77332313312111=-+-+
-d d (给B1和B3的需求供应率要相等)
∑∑==?314
1
i j ij ij
X C
+ d 8- - d 8+= 2950(1+10%) （总运费的增加不超过最小的10%）
非负约束：X ij ， d k -
，d k +
≥0 （i=1,2,3；j=1,2,3,4；k=1,2,3,…8)
目标函数：
Min Z = P 1* d 4- + P 2* d 5-+P 3* d 6++P 4*( d 7-+ d 7+)+P 5* d 8+
19、某电台根据政策每天允许播出12小时，其中商业节目每分钟可收入250元，新闻节目每分
钟支出40元，音乐节目每播一分钟支出元。依政策规定：正常情况下商业节目只能占广
播时间的20%，而每小时至少安排5分钟的新闻节目。试问该电台每天如何安排节目？其优先级如下：P 1—满足政策的要求；P 2—每天的纯收入最大。建立此问题的目标规划模型。 解：设安排商业节目时间X 1小时，新闻节目时间X 2小时，音乐节目时间X 3小时。
目标函数： Min Z = P 1(d 1-+d 2-+d 3+)+P 2d 4-
约束条件： X 1+X 2+X 3+ d 1-- d 1+
=12
X 1 + d 2-- d 2+
=
X 2 + d 3-- d 3+
=1
+ d 4-- d 4+
=250*
X 1,X 2,X 3≥0,d i -,d i +
≥0 (i=1,2,3,4)
20、A －J 共10项工作需在两台机器上加工，各自的加工时间如下，如何安排加工顺序使系统效率最高(只要求写出加工顺序)。
解：（约翰逊原则求解过程略）
结果： I, H, E, G, D, J, F, B, C, A 21、求出下图中从A 到E 的最短路线及其长度。
解：方法一：动态规划
在B1与D1之间增设一虚拟节点C3,使B1到C3的距离为4，而C3到D1的距离为0； 在B3与D3之间增设一虚拟节点C4,使B3到C4的距离为3，而C4到D3的距离为0； 用动态规划方法，可求得 A 到 E 的最短距离为 8最短路为：A-B2-C1-D1-E 。 方法二：Dijkstra 方法（过程略）
结果：A 到 E 的最短距离为 8 ,最短路为：A-B2-C1-D1-E
22题图 23题图
解：线性规划模型：
1）变量：设f ij为通过弧i-j（节点i →节点j ）的流量
2）目标函数：Max Z = f12+f13 (出发点流出的总流量最大)
3）约束条件：f12=f25+f24+f23 (节点2的净流量为0)
f13+f23=f34+f36 (节点3的净流量为0)
f24+f34=f45+f46 (节点4的净流量为0)
f25+f45+f65=f57 (节点5的净流量为0)
f46+f36=f65+f67 (节点6的净流量为0)
f ij≤F ij 对一切可能的弧i-j (弧的容量限制)
f ij≥0 对一切可能的弧i-j
图上标注过程略，最大流量结果为：9
23、求网络（23题图）从节点1到节点7的最短路径（写出线性规划模型，并用图上标注的
方法求解）。
解：方法一：线性规划模型求解，假设通过网络的最大流量为1，
1）变量：设X ij为弧i-j（节点i →节点j ）是否流过，流过取值1，不流过取值0
2）目标函数：通过网络的总长度最小，因此，有：
Min Z = 5X12+2X23+7X25+2X24+7X34+4X36+6X45+2X46+3X57+X65+X67
3）约束条件：
X12+X13=1 (节点1的流出量为1)
X12=X25+X24 (节点2的净流量为0)
X13=X34+X36 (节点3的净流量为0)
X24+X34=X45+X46 (节点4的净流量为0)
X25+X45+X65=X57 (节点5的净流量为0)
X36+X46=X65+X67 (节点6的净流量为0)
X57+X67=1 (节点7的流入量为1)
X ij=0,1 所有可能的弧i-j
方法二：Dijkstra 方法（过程略）
结果：最短距离为10，最短路为：1-3-6-5-7
24、某工厂的某台机器可连续工作4年，决策者在每年年初都要决定机器是否更新。若购置
新机器，就要支付购置费；若继续使用，则需要支付维修与运行费用，而且随着机器使用年限的增加费用也会逐年增加。已知计划期（4年）中每年的购置价格及维修运行费用如下表所示，试制定今后4年的机器更新计划，使总支付费用最小。
解：把该问题看作最短路问题。设节点1和节点5表示计划期的始点和终点（节点5可理解为第4年年末）。下图中各弧（i , j）表示第i年年初购进的机器使用到第j
年年初（即第j-1年年底），弧旁的数字（弧长）为购置价格与使用多年后的维修与
运行总费用，如考虑节点1到节点3的弧，这条弧对应的是在第1年初购进的机器，
使用到第3年年初（使用了两年），所以从节点1到节点3的弧长为购置万元加上第
一年维修运行费1万和第二年维修运行费万元，合计5万元。其余类似求得。
求解结果：最短距离为，最短路为：①- ③- ⑤，即：
计划期内第1年、第3年年初各购置一台新机器，4年总费用万元。
25、某地拟进行石油勘探。统计资料表明，在相似地理区域钻探的井中，有7口油井和16口
干井，每口油井收入都是大约130万元。若请勘探人员自行开发需花费30万元，如出租给别的公司开采可稳得租金10万元，且若能出油还可额外再得10万元。该地领导应如何决策？为提高决策的准确性，专家建议可先进行地震试验，从而判断该地区的地质结构是封闭的或开放的。从地质学知道：有油地区多半是封闭结构，无油地区多半是开放结构，以往情况是有油地区勘测为封闭结构的概率为，无油地区勘探开放结构的概率是。
若做地震试验要花费5万元，该领导又该如何决策？
解：在相似地区钻井有油的概率为 7/(7+16)=，则无油的概率为。
设以A1表示自行开发，A2表示出租，以θ1、θ2分别表示该地区的有油与无油状态。
根据题意可列出以下收益表：
1）先验分析：计算A1、A2两方案的期望收益值
EMV(A1)= 100*+(-30)*= 9
EMV(A2)= 20*+10*= 13
由于EMV(A2)>EMV(A1),因此，如不做地震实验的决策是应该选择出租。
此时，EMV*=13（万元）
2）预验分析：计算完备信息的价值
完备信息下最大期望收益ERPI= 100*+10*= 37 （万元）
完备信息价值EVPI=37-13=24（万元）
由于EVPI（24万元）相比地震实验的费用（5万元）大比较多，可尝试进行。
3）后验分析：计算条件概率并决策
设A3为进行地震实验，以S1，S2分别表示勘探结果为封闭结构和开放结构
由题意可得以下条件概率：
P(S1|θ1)= , P(S2|θ1)= , P(S1|θ2)= , P(S2|θ2)=
进一步利用贝叶斯公式计算决策所需条件概率P(θ| S )
得到：P(θ1|S1)= , P(θ2|S1)= , P(θ1|S2)= , P(θ2|S2)=
地震实验是封闭结构的决策：计算期望收益值
EMV(A1S1)=100*+(-30)*=30(万元)
EMV(A2S1)=20*+10*=(万元)
EMV(A1S1)>EMV(A2S1),因此，此时的决策为选择自行开采（A1）
地震实验是开放结构的决策：计算期望收益值
EMV(A1S2)=100*+(-30)*=(万元)
EMV(A2S2)=20*+10*=(万元)
EMV(A2S2)>EMV(A1S2),因此，此时的决策为选择出租（A2）
以上根据地震实验结果所做决策的总期望收益为：
EMV(S)=30*+* - 5= 16(万元)
选择做地震实验的期望值增量为：
?EMV=EMV(S)-EMV* = 16-13 = 3 (万元)
综上所述，最优决策为：先进行地震实验，如果结果为封闭结构则自行钻探开采，如为开放结构则出租该地的开采权，这样可获期望收益16万元。
26、画出网络图（不考虑工序时间）
网络图1 网络图2 网络图3 工序紧后工序工序紧前工序工序紧前工序
A C,D A -- A --
B C,D,E B -- B --
C G C -- C A
D H,F D A D A
E H,
F E B E B
F G F C F B
G I G B,D G D,E
H I H E H D,E
I G,H I D,E,F
J E,F J C
K E,F K C
L I,J L J
M D,E,F,G,H,K 解：网络图1：
网络图2:
网络图3：
27、已知某项工程的作业程序、作业时间、直接成本、最大可缩短时间、各工序缩短一天工期所增加的直接费用等信息如下表所示，正常时间完成各工序的直接费用总和为1300元，每天的间接费用为25元：
要求：1）画出网络图，计算每一节点的最早、最迟时间，确定关键线路；
2）建立使该项工程达到最低成本时间的线性规划模型；
3）计算使总成本最低的最优完工时间。 解：1）网络图及节点时间计算如下图：
关键线路为：A-B-J-E-H 最短完工时间为27天
2)根据以上网络图，设X i 为
i 节点（i=1,2,3,…8）发生的时间，Y ij 为工序
i-j 实际缩短
的时间；T ij 为工序i-j 的正常完工时间（已知），
T ij ’为工序i-j 最大可缩短时间（已
知）。线性规划模型为： 目标函数：Min F =
8X D Y g
ij ij
?+?∑
约束条件：X j -X i ≥T ij -Y ij 对一切可压缩的工序 Y ij ≤T ij ’对一切可压缩的工序
X i ,Y ij ≥0 i,j=1,2,3,…8且i-j 为一切可能的工序 （具体可根据网络图详细写出目标函数和约束条件）
3）关键线路上A-B-J-E-H 直接费率g 最小的工序为E ，E 虽然最多可缩短5天，但只能先
缩短1天（如大于1天，A-B-D-G 将会成为新的关键线路），E 缩短1天后增加直接费用10元，同时减少间接费用25元，因此，还可继续缩短。此时A-B-D-G 也成为关键线路，最小g 为D 工序，最多可缩短2天，但需与E 工序一起缩短。D 、E 各缩短两天以后增加直接费用为15*2+10*2=50元，同时减少的间接费用为2*25=50元。增加的费用和减少的费用正好相等，因此，不需要再继续缩短。此时的最优完工时间为24天。 28、某企业对一种原材料的年需求量为5000立方米，该种原材料的市场价1000元/立方米，每
次购买时的订货费8000元，年库存费500元/立方米，试确定最佳订货周期和经济批量。 解：此题假设为不允许缺货，且能瞬时到货。根据题意有：
D=5000 立方米/年，RC=8000元/次， HC=500元/立方米.年 因此，
订货周期T 0=Q 0/D= 400/5000 = 年，约29天。
该企业最佳订货策略为：订货周期为29天，每次订货400立方米
29、一食品店要决定每月牛奶的进货量，进货每箱80元，售价100元。如果该店根据过去的
若当天不能售出因牛奶变质而全部损失，试确定每天最佳进货量和最大期望收益值。 解： k=100－80=20，h=80
k h k
+=100
20=
因为，P （25）=＜ ≤P
（25）+P （26）= 所以，可以确定进货26箱。 每天订26箱时的获利情况如下：
市场需求25箱时，获利：-80+25*20=420元 26箱时，获利：26*20=520元 27箱时，获利：26*20=520元 28箱时，获利：26*20=520元
最大期望收益值=420*+520*+520*+520*=510元 因此，每天订26箱时的最大期望收益为510元。
30、某时装专卖店计划在冬季到来前订购一批新颖皮装，已知皮装的进价每件1000元，估计
利润率为40%，多进的货如果卖不出去只能以进价的一半返还给厂家，试确定销售服从以下均匀分布时的最佳订货批量。分布函数为：
立方米
单位产品年存储成本年需求量单位订货成本经济订货量40020=??=
HC
D
RC Q r
f(r)
Q*
解：此题属于需求是连续随机变量的单期库存问题，有 P(r ≤Q *
)h
k k
+=
由题意可知，售出一件利润为1000*40%=400元 ，退回厂家亏损500元，最低需求为50
件，最高需求为100件。故有，k=400, h=500, 9
4
500400400=+=+h k k 9
4
50505010050Q*)≤P(r =-=--=
Q Q
可解得Q *
≈72(件)
因此，最佳订购量为72件。
参考文献 [1] 胡运权．运筹学教程．北京：高等教育出版社，2005 [2] 胡运权．运筹学基础及应用．哈尔滨：哈尔滨工业大学出版社，1998 [3] 《运筹学》编写组．运筹学．北京：清华大学出版社， 1990 [4] 张莹．运筹学基础．北京：清华大学出版社，2002 [5] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1999 [6] 何坚勇．运筹学基础．北京：清华大学出版社， 2000 [7] 马振华等．现代应用数学手册—运筹学与最优化理论卷．北京：清华大学出版社，2000 [8] 牛映武．运筹学．西安：西安交通大学出版社，1993 [9] 梁工谦．运筹学- 典型题解析集自测试题。西安：西北工业大学出版社，2002 [10] 徐永仁．运筹学试题精选与答题技巧．哈尔滨：哈尔滨工业大学出版社，2000 [11] 徐玖平，胡知能，王緌．运筹学(第二版)．北京：科学出版社，2004 [12] 刘满风，傅波，聂高辉．运筹学模型与方法教程- 例题分析与题解．北京：清华大学出版社，2001 [13] 胡运权．运筹学习题集．北京：清华大学出版社，2002 [14] 盛昭瀚，朱乔，吴广谋．DEA理论、方法与应用．北京：科学出版社，1996 [15] Frederick ~S．Hillier，Gerald~J．Lieberman．Introduction to Operations Research (6th Ed．)．Beijing：China Machine Press/ McGraw - Hill，1999 [16] J．D．Wiest，F．K．Levy．统筹方法管理指南．北京：机械工业出版社，1983 [17] 王元等．华罗庚科普著作选集．上海：上海教育出版社，1984 [18] 江景波等．网络计划技术．北京：冶金工业出版社，1983 [19] David R．Anderson，Dennis J．Sweeney，Thomas A．Williams．数据、模型与决策．北京：机械工业出版社，2003 [20] Frederick S．Hillier，Mark S．Hillier，Jerald J．Lieberman．Introduction to Management Science．Beijing：McGraw - Hill Comanies，Inc．，2001
运筹学课程设计 实践报告 学号： 01 班级： 管理科学与工程类4班
第一部分小型案例分析建模与求解 ................................................................... 错误!未定义书签。 案例1. 杂粮销售问题 ........................................................................................................ 错误!未定义书签。 案例2. 生产计划问题 ........................................................................................................ 错误!未定义书签。 案例3. 报刊征订、推广费用的节省问题 ...................................................................... 错误!未定义书签。 案例4. 供电部门职工交通安排问题 ................................................................................ 错误!未定义书签。 案例5. 篮球队员选拔问题 ................................................................................................ 错误!未定义书签。 案例6. 工程项目选择问题 .............................................................................................. 错误!未定义书签。 案例7. 高校教职工聘任问题（建摸） .......................................................................... 错误!未定义书签。 案例8. 电缆工程投资资金优化问题 ................................................................................ 错误!未定义书签。 案例9. 零件加工安排问题 ................................................................................................ 错误!未定义书签。 案例10. 房屋施工网络计划问题 ...................................................................................... 错误!未定义书签。第二部分：案例设计 ...................................................................................................... 错误!未定义书签。 问题背景： .......................................................................................................................... 错误!未定义书签。 关键词： .............................................................................................................................. 错误!未定义书签。 一、问题的提出 .................................................................................................................. 错误!未定义书签。 二、具体问题分析和建模求解 .......................................................................................... 错误!未定义书签。 三、模型的建立对于N个应聘人员M个用人单位的指派是可行的。......................... 错误!未定义书签。
第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1+ x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为: 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围: 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限.25 .333 常数项数范围: 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为: 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格
运筹学的应用 运筹学在早期的应用主要在军事领域。当时英、美军队开展了使护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400%；研究了船只在受敌攻击时，提出了大船应急转向和小船应还慢转向的逃避方法。研究结果使船只在受敌攻击时，中弹数由47%降到29%。 第二次世界大战过后，运筹学除军事方面的应用研究以外，相继在工业、农业、经济和社会问题等领域都有应用，这里只对某些重要领域给予简述。 （1）市场销售。主要应用在广告预算和媒介的选择、竞争性定价、新产品开发、销售计划的制定等方面。如美国杜邦公司在20世纪50年代起就非常重视将运筹学用于研究如何做好广告工作，产品定价和新产品的引入。通用电力公司对某些市场惊醒模拟研究。 （2）生产计划。在总体计划主要用于总体确定生产、存储和劳动力的配合等计划，以适应波动的需求计划，节省10%的生产费用。还可以用于生产作业计划、日程表的编辑等。此外，还有在合力下料、配料问题、物料管理等方面的应用。 （3）库存管理。主要应用于多种物资库存量，群定某些设备的能力或容量，如停车场的大小、新增发电设备的容量大小、电子计算机的内存量、合理的水库容量等。美国某机器制造公司应用存储论后，节省18%的费用。目前国外新动向是将库存理论与计算机的物资管理系统相结合。如美国西电公司，从1971年起用5年时间建立了“西电物资管理系统”，使公司节省了大量物资存储费用和运费，而且减少了管理人员。 （4）运输问题。这涉及空运、水运、公路运输、铁路运输、管道运输、场内运输。空运问题设计飞行航班和飞行机组人员服务时间安排等。为此在国际运筹学协会中设有航空组，专门研究空运中的运筹学问题。水运有船舶航运计划、光口装卸设备的配置和船到港口后的运行安排。公路运输除了汽车调度计划外，还有公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租汽车的调度和停车场的设立。铁路运输方面的应用就更多了。 （5）财政和会计。这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用的较多的方法是统计分析、数学规划、决策分析。此外还有盈亏分析法、价值分析法等。
第二章作业的参考答案 73P 4、将下面的线性规划问题化成标准形式 ???? ? ????≤≤-≤≤≤-+≥+-+-6130326 32..2max 213213213 21x x x x x x x x t s x x x 解：将max 化为 min ，3x 用54 x x -代替，则 ????? ??????≥≤≤-≤≤≤--+≥-+---+-0 ,61303)(26)(32..)(2min 5421542154215421x x x x x x x x x x x x t s x x x x 令122 +='x x ，则 ????? ??????≥≤'≤≤≤≤---'+≥-+-'----'+-0 ,70303)()1(26)(3)1(2..)(21min 54215421542 1542 1x x x x x x x x x x x x t s x x x x 将线性不等式化成线性等式，则可得原问题的标准形式
????? ??????≥'=+'=+=++-'+=--+'--+-'+-0,,,,,,,73424332..122min 9876542 192 81754216542 1542 1x 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 73P 5、用图解法求解下列线性规划问题： （1）?? ? ????≥≤≤≥++2 12620..3min 212121x x x x t s x x 解：图2.1的阴影部分为此问题的可行区域。将目标函数的等值线c x x =+21 3（c 为常 数）沿它的负法线方向 T ），（31--移动到可行区域的边界上。于是交点T ），（812就是该问题的最优解，其最优值为36。
第一章线性规划1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x1+x2 ? ? ? ? ? ? ? ≥ ≤ ≤ ≥ + ≤ + - 10 5 8 24 4 2 1 2 1 2 1 x x x x x x 解： 由图可得：最优解x=1.6,y=6.4
Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= +∞
Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8.
12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中 x 3’≥0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x
运筹学在实际生活中的应用 摘要：随着经济的快速发展和社会的进步，社会各行各业之间的竞争日益激烈，尤其表现为对资源的争夺。因此，在有限的资源下获得最大的利益是每个竞争者所考虑的问题，这也是经济学和运筹学所着重解决的问题。运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。作为一门实用性很强的学科，运筹学可以用来很好的解决生活中的许多问题。运筹学有着广泛的应用，对现代化建设有重要作用。正因为如此，运筹学在企业决策领域中有着广泛的应用。众所周知，运筹学研究的根本目的在于对资源进行最优化配置，用数学的理论与方法指导社会管理，提高生产效率，创造经济效益。而企业投资的根本目的也是在资源的优化配置和有限资源的有效使用的基础上，达到既定目标，实现企业利润最大化。然而，随着市场竞争的日趋激烈，决策是否有效对于企业生存发展的影响愈来愈大。正确的决策可以使企业获利并促进企业的发展，而错误的或者无效的决策只能使企业无利可获甚至亏损，阻碍企业的发展。而运筹学、经济学、博弈论等决策性的科学可以引导投资者选择最佳投资组合策略，为决策者在投资决策过程中提供一些有价值的思路。用来解决人们用纯数学方法或者现实实验无法解决的问题，对企业正确决策的形成有着积极地促进作用。 关键词：运筹学；决策；应用；理论体系；效益 一、引言 人们无论从事任何工作，不管采取什么行动，都希望所制订的工作或行动方案，是一切可行方案中的最优方案，以期获得满意的结果，诸如此类的问题，通常称为最优化问题。运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。求解最优化问题的关键，一是建立粗细适宜的数学模型，把实际问题化
为数学问题；二是选择正确而简便的解法，以通过计算确定最优解和最优值。最优解与最优值相结合，便是最优方案。人们按照最优方案行事，即可达到预期的目标。运筹学的应用可大可小，可以处理各种策略性的问题。 通过对运筹学的学习，无论是从简单的故事，还是真实的案例中，我们可以发现，所谓的运筹，是用最小的功效获得最大的利益。这在我们的生产生活中有极大的意义。运筹学有广阔的应用领域，它已渗透到诸如矿山、服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。 二、运筹学概述 运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。虽然不大可能存在能处理及其广泛对象的运筹学，但是在运筹学的发展过程中还是形成了某些抽象模型，并能应用解决较广泛的实际问题。 运筹学的思想在古代就已经产生了。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法，这就是“运筹帷幄之中，决胜千里之外”的说法。但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却相对较晚。也可以说，运筹学是在二十世纪四十年代才开始兴起的一门分支。运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、图论、决策论、对策论、可靠性理论等。 三、运筹学的发展 Operation Research原意是操作研究、作业研究、运用研究、作战研究，译作运筹学，是借用了《史记》“运筹于帷幄之中，决胜于千里之外”一语中“运筹”二字，既显示其军事的起源，也表明它在我国已早有萌芽。 运筹学是一门应用科学，是应用分析、试验、量化的方法，它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题。它对管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以期发挥最大效益。作
2011年5月
目录 摘要 (3) 一、引言 (3) 二、运筹学概述 (4) 三、运筹学的发展 (4) 四、运筹学的理论体系 (5) （1）规划论 (5) （2）决策论 (6) （3）运输问题 (6) （4）存储论 (6) （5）图论 (7) (6) 排队论 (7) （7）博弈论 (7) 五、运筹学的应用所涉及的领域 (8) （1）市场销售 (8) （2）生产计划 (8) （3）库存管理 (8) （4）运输问题 (9) （5）财政和会计 (9) （6）人事管理 (9) （7）城市管理 (9) 六、运筹学国内外应用现状 (9) 七、结论 (11) 八、结语 (11) 参考文献 (11)
浅析管理运筹学在实际生活中的应用 摘要：随着经济的快速发展和社会的进步，社会各行各业之间的竞争日益激烈，尤其表现为对资源的争夺。因此，在有限的资源下获得最大的利益是每个竞争者所考虑的问题，这也是经济学和运筹学所着重解决的问题。运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。作为一门实用性很强的学科，运筹学可以用来很好的解决生活中的许多问题。运筹学有着广泛的应用，对现代化建设有重要作用。正因为如此，运筹学在企业决策领域中有着广泛的应用。众所周知，运筹学研究的根本目的在于对资源进行最优化配置，用数学的理论与方法指导社会管理，提高生产效率，创造经济效益。而企业投资的根本目的也是在资源的优化配置和有限资源的有效使用的基础上，达到既定目标，实现企业利润最大化。然而，随着市场竞争的日趋激烈，决策是否有效对于企业生存发展的影响愈来愈大。正确的决策可以使企业获利并促进企业的发展，而错误的或者无效的决策只能使企业无利可获甚至亏损，阻碍企业的发展。而运筹学、经济学、博弈论等决策性的科学可以引导投资者选择最佳投资组合策略，为决策者在投资决策过程中提供一些有价值的思路。用来解决人们用纯数学方法或者现实实验无法解决的问题，对企业正确决策的形成有着积极地促进作用。 关键词：管理运筹学；决策；应用；博弈论；理论体系；效益 一、引言 人们无论从事任何工作，不管采取什么行动，都希望所制订的工作或行动方案，是一切可行方案中的最优方案，以期获得满意的结果，诸如此类的问题，通常称为最优化问题。运筹学就是以数学为主要手段、着重研究最优化问题解法的学科。求解最优化问题的关键，一是建立粗细适宜的数学模型，把实际问题化
运筹学的实际应用 学生会晨读考勤巡视人员分配建模 晨读考勤制度是我校对大学一年级及二年级学生的特殊制度，针对上午第一节有课的班级——周一至周五上午第一节课有课（包括任何课程）的班级需7:30到教室组织英语晨读，未按时到达学生录入考勤系统，按迟到处理。 晨读考勤状况的盘点与巡视工作由校学生会负责。因为每天上晨读的班级数目都不一样，所以每天需要的巡查人员数目也并不同，根据每天晨读班级数目制定的每日所需巡查人数如下表所示。巡视工作枯燥繁重，所以成员在连续参与巡视工作3天后，可以连休两天。（周二至周四巡视过得人员可以在周五和下周一休息）。 学生会人数有限，所以请设计一套方案，需满足每天所需的巡查人数，又使 项目解决： 一，项目内容要求提取 （1）忽略星期六和星期日 （2）巡视人员连续工作3天后连续休息2天，忽略请假情况 （3）分配休息两天后周一至周五每天开始工作的人员，使总工作人数最少。 二，分析建模 此问题是一个典型并且简单的线性规划问题，所以接下来是建立目标函数以及对应的约束条件，并设法求解。 建立模型： Z为所需巡视人员总的人数。 设：x i（i=1,2,3,4,5）为休息两天后，周一至周五每天开始工作的学生会成员。 minZ=x1+x2+x3+x4+x5 x1+x4+x5≥40 x1+x2+x5≥55
x1+x2+x3≥30 x2+x3+x4≥48 x3+x4+x5≥30 x i≥0，i=1,2,3,4,5 三，求解 运用Matlab的linprog函数求解 编写命令： c=[1,1,1,1,1] A=[-1 0 0 -1 -1; -1 -1 0 0 -1; -1 -1 -1 0 0; 0 -1 -1 -1 0; 0 0 -1 -1 -1;] b=[-40;-55;-30;-49;-30]; Aeq=[];beq=[]; vlb=[0;0;0;0;0];vub=[] [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) 求解得出： x = 4.3625 32.0000 0.0000 17.0000 18.6375 fval = 72.0000
运筹学基础及应用 习题解答 习题一 P46 (a) 该问题有无穷多最优解，即满足2 1 0664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。 (b) 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 (a) (1) 图解法
最优解即为?? ?=+=+82594321 21x x x x 的解??? ??=23,1x ，最大值235=z (2)单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式 ???=++=+++++=8 25943 ..00510 max 421321 4321x x x x x x t s x x x x z 则43,P P 组成一个基。令021==x x 得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。5 839,58min =?? ? ??=θ
02>σ，23 28,1421min =??? ? ?=θ 0,21<σσ，表明已找到问题最优解0 , 0 , 2 3 1,4321====x x x x 。最大值 2 35 *=z (b) (1) 图解法 \\ 最优解即为?? ?=+=+5 24262121x x x x 的解??? ??=23,27x ，最大值217=z (2) 单纯形法 首先在各约束条件上添加松弛变量，将问题转化为标准形式
1234523124125 max 2000515.. 6224 5z x x x x x x x s t x x x x x x =+++++=?? ++=??++=? 则3P ，4P ，5P 组成一个基。令021==x x 得基可行解()0,0,15,24,5x =，由此列出初始单纯形表 21σσ>。245min ,,461θ? ?=-= ?? ? 02>σ，15 33min ,24,5 22θ??== ??? 新的单纯形表为
运筹学在实际生活中的应用 一、运筹学概述 运筹学是近代应用数学的一个分支，主要是研究如何将生产、管理等事件中出现的运筹问题加以提炼，然后利用数学方法进行解决的学科。运筹学是应用数学和形式科学的跨领域研究，利用像是统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学不仅在科技、管理、农业、军事、国防、建筑方面有重要的运用，而且经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率, 在我们的实际生活中应用也很广泛。 二、运筹学的发展 运筹学的思想方法在我国古代就有过不少的记载。如田忌赛马、沈括运军粮的故事就充分说明了我国很早不仅有过朴素的运筹思想，而且在生产实践中实际运用了运筹方法，但运筹学作为一门新兴的学科是在第二次世界大战期间出现的，当时主要是用来解决复杂的战略和战术问题。二战之后，从事这项工作的许多专家转到了经济部门、民用企业、大学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学科逐步形成并得以迅速发展。 战后的运筹学主要在一下两方面得到了发展，其一为运筹学的方法论，形成了运筹的许多分支，如数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论、存储论、维修更新理论、搜索论、可靠性和质量管理等。1947年的求解线性规划问题的单纯形法是运筹学发展史上最重大的进展之一。其二是由于电子计算机尤其是微机迅猛地发展和广泛地应用，使得运筹学的方法论能成功地即时地解决大量经济管理中的决策问题。世界上不少国家已成立了致力于该领域及相关活动的专门学会，美国于1952年成立了运筹学会，并出版期刊《运筹学》，世界其他国家也先后创办了运筹学会与期刊，1957 年成立了国际运筹学协会。 三、运筹学的理论体系 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重
运筹学基础课后习题答案 [2002年版新教材] 第一章导论 P5 1.、区别决策中的定性分析和定量分析，试举例。 定性——经验或单凭个人的判断就可解决时，定性方法 定量——对需要解决的问题没有经验时；或者是如此重要而复杂，以致需要全面分析（如果涉及到大量的金钱或复杂的变量组）时，或者发生的问题可能是重复的和简单的，用计量过程可以节约企业的领导时间时，对这类情况就要使用这种方法。 举例：免了吧。。。 2、. 构成运筹学的科学方法论的六个步骤是哪些？ .观察待决策问题所处的环境； .分析和定义待决策的问题； .拟定模型； .选择输入资料； .提出解并验证它的合理性（注意敏感度试验）； .实施最优解； 3、．运筹学定义： 利用计划方法和有关许多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据 第二章作业预测P25 1、. 为了对商品的价格作出较正确的预测，为什么必须做到定量与定性预测的结合？即使在定量预测法诸如加权移动平均数法、指数平滑预测法中，关于权数以及平滑系数的确定，是否也带有定性的成分？ 答：（1）定量预测常常为决策提供了坚实的基础，使决策者能够做到心中有数。但单靠定量预测有时会导致偏差，因为市场千变万化，影响价格的因素很多，有些因素难以预料。调查研究也会有相对局限性，原始数据不一定充分，所用的模型也往往过于简化，所以还需要定性预测，在缺少数据或社会经济环境发生剧烈变化时，就只能用定性预测了。（2）加权移动平均数法中权数的确定有定性的成分；指数平滑预测中的平滑系数的确定有定性的成分。 2.、某地区积累了5 个年度的大米销售量的实际值（见下表），试用指数平滑法，取平滑系数α= 0.9，预测第6年度的大米销售量（第一个年度的预测值，根据专家估计为4181.9千公斤） 年度 1 2 3 4 5 大米销售量实际值 （千公斤）5202 5079 3937 4453 3979 。 答： F6=a*x5+a(1-a)*x4+a(1-a)~2*x3+a(1-a)~3*x2+a(1-a)~4*F1 F6=0.9*3979+0.9*0.1*4453+0.9*0.01*3937+0.9*0.001*5079+0.9*0.0001*4181.9
四、把下列线性规划问题化成标准形式： 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小时昼夜加班工作，需要的人员数量如下表所示：起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?
五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10 b -1 f g X3 2 C O 1 1／5 X l a d e 0 1 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3
管理运筹学第二版课后 习题参考答案 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 列出单纯形表
运筹学经典案例 案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的P.M.S.Blachett为首，组织了一个小组，代号为“Blachett 马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团”是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。
运筹学(胡运权)第五版课后答案-运筹作业
47页1.1b 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47页1.1d 无界解 1 2 3 4 5 4 3 2 1 - 1 -6 -5 -4 -3 -2 X2 X1 2x1- -2x1+3x 1 2 3 4 4 3 2 1 X1 2x1+x2=2 3x1+4x2= X
1.2（b） 约束方程的系数矩阵A= 1 2 3 4 2 1 1 2 P1 P2 P3 P4 基 基解 是否可行解目标函数值X1 X2 X3 X4 P1 P2 -4 11/2 0 0 否 P1 P3 2/5 0 11/5 0 是43/5 P1 P4 -1/3 0 0 11/6 否 P2 P3 0 1/2 2 0 是 5 P2 P4 0 -1/2 0 2 否 P3 P4 0 0 1 1 是 5 最优解A=(0 1/2 2 0)T和(0 0 1 1)T 49页13题 设Xij为第i月租j个月的面积 minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x1 3 +6000x23+7300x14 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 Xij≥0 用excel求解为： ( )
用LINDO求解： LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION V ALUE
中国古代优秀的运筹案例 1. 孙武与《孙子兵法》 孙武，字长卿，后人尊称其为孙武子、孙子，中国历史上著名军事家.公元前535年左右出生于齐国乐安（今山东惠民）. 后来到了吴国，因为献上兵法十三篇，被吴王阖闾重用，拜为大将，和伍子胥共事，辅佐吴王，领兵攻破楚国都城郢（今湖北江陵县纪南城）. 孙武在春秋末期（公元前476年前后）所著《孙子兵法》，是世界上现存最古老的兵书.其中的《始计第一》论述怎样在开战之前和战争中实行谋划的问题，以及谋划在战争中的重要意义；《作战第二》论述速战速胜的重要性；《谋攻第三》论述用计谋征服敌人的问题；《军形第四》论述用兵作战要先为自己创造不被敌人战胜的条件，以等待敌人可以被我战胜的时机，使自己“立于不败之地”；《兵势第五》论述用兵作战要造成一种可以压倒敌人的迅猛之势，并要善于利用这种迅猛之势；《虚实第六》论述用兵作战须采用“避实而击虚”的方针；《军争第七》论述如何争夺制胜的有利条件，使自己掌握作战主动权的问题；《九变第八》论述将帅指挥作战应根据各种具体情况灵活机动地处置问题，不要机械死板而招致失败，并对将帅提出了要求；《行军第九》论述行军作战中怎
样安置军队和判断敌情问题；《地形第十》论述用兵作战怎样利用地形的问题，并着重论述深入敌国作战的好处；《九地第十一》进一步论述用兵作战怎样利用地形及统兵之道的问题；《火攻第十二》论述在战争中使用火攻的办法、条件和原则等问题；《用间第十三》论述使用间谍侦察敌情在作战中的重要意义，以及间谍的种类和使用间谍的方法. 《孙子兵法》是体现我国古代军事运筹思想的最早的典籍.它考察了战争中各种依存、制约关系，总结了战争的规律，并依此来研究如何筹划兵力以争取全局的胜利. 书中的语言叙述简洁，内容也很有哲理性，后来的很多将领用兵都受到了该书的影响.《孙子兵法》对中国的文化发展有深远的影响. 2. 孙膑与齐王赛马 孙膑（约公元前380－公元前432），孙武的后世子孙，战国中期的著名军事家. 少时孤苦，年长后从师鬼谷子（著名隐士，精通兵学和纵横学）学习《孙子兵法》十三篇等兵书战策. 庞涓妒孙膑之才而将其骗至魏,施以膑刑(割去膝盖骨).后来乘齐国使团来魏之机，孙膑被齐使秘密接到齐国,并被大将田忌所赏识，留在府中做幕僚，奉为上宾. 孙膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例（记载于《史记·孙子吴起列传》），成为军事上一条重要的用兵规律，即要善于用局部的牺牲去换取全局的
《运筹学》课程复习资料 一、判断题： 1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 [ ] 2.线性规划问题的每一个基本解对应可行解域的一个顶点。 [ ] 3.任何线性规划问题存在并具有惟一的对偶问题。 [ ] 4.已知y i *为线性规划的对偶问题的最优解，若y i *＞0，说明在最优生产计划中第i 种资源已完 全耗尽。 [ ] 5.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。 [ ] 6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。 [ ] 7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。 [ ] 8.用单纯形法求解Max 型的线性规划问题时，检验数Rj ＞0对应的变量都可以被选作入基变量。 [ ] 9.对于原问题是求Min ，若第i 个约束是“＝”，则第i 个对偶变量yi ≤0。 [ ] 10.用大M 法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。[ ] 11.如图中某点vi 有若干个相邻点，与其距离最远的相邻点为vj ，则边[vi,vj]必不包含在最小 支撑树内。 [ ] 12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵 消缺货时造成的损失。 [ ] 13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可 行解时，其原问题具有无界解。 [ ] 14.在线性规划的最优解中，若某一变量xj 为非基变量，则在原来问题中，改变其价值系数cj ， 反映到最终单纯形表中，除xj 的检验数有变化外，对其它各数字无影响。 [ ] 15.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟 一最优解，有无穷多最优解，无界解，无可行解。 [ ] 16.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。 [ ] 17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的 选择。 [ ] 18.在物资价格有折扣的存贮模型中，计算费用时必须考虑物资本身的费用。 [ ] 19.若线性规划问题具有可行解,且可行解域有界,则该线性规划问题最多具有有限个数的最优解。[ ] 20.对一个有n 个变量，m 个约束的标准型线性规划问题，其可行域的顶点数恰好为m n C 个。 [ ] 21.Dijkstra 算法（T 、P 标号算法）要求边的长度非负。 [ ] 22.在求网络最大流问题中，最大流的流量是惟一的，但最大流不一定惟一。 [ ] 23.在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。 [ ] 24.状态转移方程为状态变量和决策变量的函数关系。 [ ] 25.任何线性规划问题一定有最优解。 [ ] 26.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字若从单纯形表中删除， 将会影响后面的计算结果。 [ ] 24.影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格 是不同的两个概念。 [ ] 28.指派问题效率矩阵的每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。 [ ] 29.任意可行流的流量不超过任意割集的割量。 [ ] 30.当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时 的订货批量。 [ ] 31.检验数Rj 表示非基变量xj 增加一个单位时目标函数的改变量。 [ ] 32目标函数极大化（MAX 型）的指派问题，是将目标函数乘以“－1”化为求最小值，再用匈牙 利法求解。 [ ] 33.动态规划的基本方程是将一个多阶段决策问题转化为一系列具有递推关系的单阶段的决策问 题。 [ ] 34.运输问题用闭回路法和用位势法求得的检验数不相同。 [ ] 35.容量网络中可行流是最大流的充要条件是不存在发点到收点的增广链。 [ ]