一、（15分）某造船厂根据合同从当年起连续三年各提供四条规格相同的大型客货轮。已知该厂这

三年内生产大型客货轮的能力及每艘客货轮成本如下表1所示。

每艘每积压一年造成的损失为30万元。在签定合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年末完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产量，能够在满足上述各项要求的情况下总的生产费用最少？试建立线性规划模型，不求解。 二、（20分）某工厂生产过程中需要长度为3.1m ，2.5m 和1.7m 的同种棒料毛坯分别为200根，100

根和300根。现有的原料为9m 长棒材，问如何下料可使废料最少？试建立线性规划模型，不 求解。

三、（25分）某厂有100台机床，能够加工两种零件，要安排下面4个月的任务，根据以往经验，

知道这些机床用来加工第一种零件，一个月以后损坏率为1/3。而在加工第二种零件时，一个

月后损坏率为1/10。又知道，机床加工第一种零件时一个月的收益为10万美元，加工第二种零件时每个月的收益为7万美元。现在要安排4个月的任务，试问：怎样分配机器的任务，能使总收益为最大？

四、（20分）设有三种资源，每单位的成本分别为a ，b ，c 。给定的利润函数为

),,2,1(),,,,(n i z y x r i i i i ，现有资金为W ，应购买各种资源多少单位分配给n 个行业，才能

使总利润最大。试给出动态规划的公式，并列出它的一维递推关系式。

五、（20分）已知下列资料，如下表1所示。

要求：（1）绘制网络图；

（2）计算各项时间参数；

（3）确定关键路线。

六、（10分）用外点法求解非线性规划

1

)1(),(min 22

2

2121≥+-=x x x x x f

七、（10分）设线性规划问题1为

⎪⎩⎪⎨⎧=≥=≤=∑∑==),,2,1(,0),,2,1(,max 1

1

1n j x m i b x a x c z j

n

j i j ij n

j j

j ),,(**1m y y 是其对偶问题的最优解。

又线性规划问题2为

⎪⎩⎪⎨

⎧=≥=+≤=∑∑==),,2,1(,0),,2,1(,max 11

2n j x m i k b x a x c z j

n

j i i j ij n

j j

j 其中i k 是给定的常数。 求证：∑=+

≤m

i i

y

k z z 1

*112max max

八、（10分）在如下图所示的网络中，每弧旁的数字是),(ij ij f c 。

（1）确定所有的截集；

（2）求最小截集的容量； （3）试求该网络的最大流。

九、（20分）已知某配送车为了配送某种货物，由某城市①出发，经过②、③、④城市一次，且仅

一次，最后仍回到原出发的城市，各城市间的距离如下表2所示，问该配送车应如何选择行车路线，能使总的行程最短？

表2