运筹学习题

1． 单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，将使目标函数值得到最快的增长。（ ）

2． 单纯形计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量

的值为负。（ ）

3． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中

删除，而不影响计算结果。（ ）

4． 任何线性规划问题存在并具有唯一的对偶问题。（ ）

5． 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题

无可行解时，其原问题具有无界解。（ ） 6． 对偶问题的对偶问题一定是原问题。（ ）

7． 运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一；有

惟一最优解，有无穷多最优解，无界解，无可行解。（ ）

8． 整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。（ ） 9． 指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（ ） 10．指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。（ ） 11．按最小元素法给出的初始基可行解，从每一空格出发可以找到而且仅能找出惟一的闭回路。（ ）

12．表上作业法实质就是求解运输问题的单纯形法。（ ）

13．图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点边线的长短曲直等都要严格注意。（ ）

14．在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（ ）

15．大M法处理人工变量时，若最终表上基变量中仍含有人工变量，则原问题无可行解。（ ）

16．若可行域是空集，则表明存在矛盾的约束条件。（ ）

17．用单纯形法求线性规划问题，若最终表上非基变量的检验数均非正，则该模型一定有唯一最优解。（ ）

18．指派问题的每个元素都加上同一个常数k，并不会影响最优分配方案。（ ） 19．指派问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。（ ） 20．指派问题与运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。（ ） 21．最优化原理是“无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，余下的决策序列必构成最优策略。（ ）

22．当线性规划问题的原问题存在可行解时，则其对偶问题也一定存在可行解。（ ） 23．线性规划的原问题与其对偶问题之间存在如下关系

1） 对偶问题的对偶问题是原问题；

2） 原问题存在可行解，其对偶问题必存在可行解； 3） 原问题无可行解，其对偶问题必无可行解；

4） 原问题有无穷多最优解，其对偶问题也有无穷多最优解。

24、任何线性规划问题存在并具有唯一的对偶问题。（ ） 25、对偶问题的对偶问题一定是原问题。（ ）

二、选择题

1．求解线性规划模型时，引入人工变量是为了（ ）。

A． 使该模型存在可行解；B．确定一个初始基本可行解；C．使该模型标准化。 2．线性规划的数学模型由（ ）三个部分组成。

A．目标要求；B．基本方程；C．非负条件；D.顶点集合; E.约束条件。

3．对于线性规划问题标准型：maxZCX,AXb,X0，利用单纯形法求解时，每作一次换基迭代，都能保证它相应的目标函数值Z必不（ ）。 A． 增大；B．不减少；C．减少；D．不增大。

4．极小化（minZ）线性规划标准化为极大化问题后，原规划与标准型的最优解（ ），目标函数值（ ）。

A． 相关一个负号；B．相同；C．没有确定的关系。

5．用大M法求解线性规划模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（ ）。

A． 有可行解，但无最优解；B．有最优解；C．无可行解。 6．线性规划问题的标准型最本质的特点是（ ）。

A． 目标要求极小化；B．变量和右端常数要求非负；C．变量可以取任意值；D．约束条

件一定是等式形式。

7．目标函数取极小化（minZ）的线性规划可以转化为目标函数取极大化即（ ）的线性规划问题求解；两者的最优解（ ），最优值（ ）。 A．maxZ；B．max(Z)；C．max(Z)；D．相关一个负号； E．相同；F. 无确定关系；G．maxZ 8．线性规划问题 minZ3x15x2

s.t.

y12x212y 2对偶变量

3x12x218

y3x1,x20

x12,x26,z*36，则其对偶问题的最优解为 。

x14

已知其最优解为：

A．y13,y22,y30;B．y10,y23,y31;C．y10,y21,y34;

23D．y13,y21,y32;

3

9．某经济类问题求极大化的过程中，用单纯形法迭代简化的表格表示如表所示，假设没有人工变量。 XB x1 x2 x3 x4 x5 x6 b x3 4 a1 1 0 a2 0  -1 -5 0 1 -1 0 2 x4 x5 检验数j a3 -3 0 0 -4 1 3 1 2 0 0 -3 0 对6个未知数（a1，a2，a3，，1，2）的约束条件选择填空，使以下关于上表的说法为真。

A． 现行解有无穷多最优解。 。 ①0,10,或20,a10 ②0,10,或20,a10 ③0,10,或20,a10

B． 现行解不可行。 。 ①0，②0，③为任意数

C．现行解是惟一最优解 。

①0,10,20 ②0,10,20 ③0,10,20 D．现行解是退化的基本可行解 。 ①0，②0，③0

10．满足下面条件的简单图G（V，E）是树图（ ）

１）无圈且连通；

２）有n个点和恰好（n-1）条边； ３）图中任意两点间存在惟一的链；

４）G无图，但只要加一条边即得惟一的圈。

11、对偶单纯形法的最小比值规划是为了保证（ ） A 使原问题保持可行 B 使对偶问题保持可行

C 逐步消除原问题不可行性 D逐步消除对偶问题不可行性 12、下列结论正确的有（ ）

A 任意一个运输问题不一定存在最优解 B 任何运输问题都存在可行解

C 产量和销量均为整数的运输问题必存在整数最优解

D mn个变量组构成基变量的充要条件是它不包括任何闭回路 E 运输单纯法（表上作业法）的条件是产量等于销量的平衡问题 13、用动态规划法求解生产与存储问题时，（ ） A 状态变量为存储量，决策变量是生产量 B 状态变量为生产量，决策变量是存储量

C 阶段指标函数是从第K阶段到第n阶段的总成本 D 过程指标函数是从第K阶段到下一阶段的总成本

14、互为对偶的两个线性规划问题的解存在关系（ ）。

A、原问题无可行解，对偶问题也无可行解 B、对偶问题有可行解，原问题可能无可行解 C、若最优解存在，则最优解相同

D、一个问题无可行解，则另一个问题具有无界解

15、有m个产地n 个销地的平衡运输问题模型具有特征（ ）。 A、有mn 个变量m+n 个约束 B、有m+n 个变量mn 个约束 C、有mn 个变量m+n－1约束

D、有m+n－1个基变量，mn－m－n－1个非基变量 16、非基变量的系数A、C、

cj变化后，最优表中( )发生变化。

jpj B、 D、

bj

Zj17、线性规划最优解不唯一是指( )。 A、可行解集合无界 B、存在某个检验数〉0

C、可行解集合是空集 D、最优表中存在非基变量的检验数非零 18、maxZ4x1x2,4x1x224,x210,x1,x20则( )。 A、无可行解 B、有唯一最优解 C、有无界解 D、有多重最优解 19、原问题有5个变量3个约束，其对偶问题( )。 A、有3个变量5个约束 B、有5个变量3个约束 C、有5个变量5个约束 D、有3个变量3个约束

2x1x2x352x12x2x46x,x,x,x020、线性规划的约束条件为1234则基本解为( )。

A、(0, 2, 3, 2) B、(3, 0, －1, 0) C、(0, 0, 6, 5) D、(2, 0, 1, 2)

21、用大M法求解线性规划数学模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（ ）。

A、有可行解但无最优解 B、有最优解 C、无可行解

12B37，CB=（3，6)，则对偶问题的最优解是（ ） 22、已知最优基

A、（3，0） B、（0，3） C、（3，1） D、（1，3）

23、X是线性规划的基本可行解则有( )

A、X中的基变量非零，非基变量为零 B、X不一定满足约束条件 C、X中的基变量非负，非基变量为零 D、X是最优解 1、线性规划具有唯一最优解是指（ ） A、最优表中存在常数项为零

B、最优表中非基变量检验数全部非零

C、最优表中存在非基变量的检验数为零 D、可行解集合有界

24、设线性规划的约束条件为（ ）

x1x2x332x1x2x44 x1,x2,x3,x40则基本可行解为

A、(0, 0, 4, 3) B、(3, 4, 0, 0) C、(2, 0, 1, 0) D、(3, 0, 4, 0) 25、minZ3x14x2

x1x24 s.t.2x1x22则（ ）

x1,x20A、无可行解 B、有唯一最优解

C、有多重最优解 D、有无界解

26、互为对偶的两个线性规划, maxZCX,AXb,X0

minWYb,YAC,Y0，对任意可行解X 和Y，存在关系（ ）

A、Z > W B、Z = W C、Z≥W D、Z≤W

27、有6个产地4个销地的平衡运输问题模型具有以下特征（ ） A、有10个变量24个约束 B、有24个变量10个约束

C、有24个变量9个约束 D、有9个基变量10个非基变量 28、下例错误的说法是（ ） A、标准型的目标函数是求最大值 B、标准型的目标函数是求最小值 C、标准型的常数项非正 D、标准型的变量一定要非负

29、已知线性规划求极小值，用对偶单纯形法求解时，初始表应满足条件（ ） A、检验数均小于等于零，常数项均大于等于零 B、检验数均大于等于零，常数项均大于等于零 C、检验数均小于等于零，常数项有负分量 D、检验数均大于等于零，常数项有负分量

31、对偶单纯形法的最小比值规划是为了保证（ ） A、使原问题保持可行 B、使对偶问题保持可行

C、逐步消除原问题不可行性 D、逐步消除对偶问题不可行性 1、有5个产地和5个销地的平衡运输问题有 个基变量 个约束条件。

2、已知最优基B312,CB(3,6)，则对偶问题的最优解为 。 73、用大M法求解线性规划数学模型时，若在最终单纯形表上基变量中仍含有非零

的人工变量，则原模型 。

4、非基变量的系数

cj变化后，最优表中 发生变化。

5、原问题有6个变量4个约束条件，则其对偶问题有 个变量 个约束条件。

6、设运输问题求最大值，则当所有检验数 时取得最优方案。

7、线性规划maxZx1x2,2x1x26,4x1x28,x1,x20的最优解是（0，6），它的第1、2个约束中的松驰变量(s1,s2)=（ ）。

8、求解线性规划模型时，引入人工变量是为了 。

三、简答题

1、在单纯形表上如何判别线性规划问题解的几种情况。（6分） 2、试比较单纯形法与对偶单纯形法的区别。（8分） 3、大M法是用于处理何类问题的方法，并说明人工变量与剩余变量及松驰变量的区别。（6）

4、求解线性规划问题时可能出现哪几种结果，哪些结果反映建模时有错误？（6分）

5、试述动态规划的最优化原理。（4分） 6、松驰量及剩余量的实际意义。（4分） 7、对偶单纯形法的优点及其局限性。（4分）

四、计算题 （单纯形法）

（一） 某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），要求确定总利润最大的最优生产计划。该问题的数学模型如下：

maxZ3x1x25x3

) s.t. 6x13x25x345(劳动力 3x14x25x330(原材料) x1,x2,x30

其中x1,x2,x3是产品A、B、C的产量。 此线性规划问题的最终表如下： 基 变 量 CB x1 x2 x3 x4 x5 3 1 5 0 0 b x1 x3 3 5 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5 3 4 5 0 1 0 -3 0 0 -1 5 3 30 zjj 1、写出其对偶问题的数学模型及最优解。（6分）

2、求出使得最优解不变的产品A的单位利润变动范围。（3分） 3、求出使劳动力对偶价格不变的b1的变化范围。（3分）

4、如果市场上原材料的单价为0.8元，是否值得购买，为什么？购买多少为宜？（4分）

5、假如这时又试制成新产品D，生产一个单位新产品D需要劳动力4单位，原材料3单位，而每单位的新产品D的利润为3元，请问这时生产计划是否要进行修改？为什么？（4分）

（二）某公司用原料甲、乙、丙制造三种产品A、B、C，有关资料见下表：

材料消耗量 产品 原材料 甲 乙 丙 每件产品利润(元)

A B C 2 1 1 1 2 3 2 2 1 4 1 3 每月可供原材料(kg) 2000 5000 6000 （1）如何安排生产，使利润最大。（8分）

（2）求出使最优解不变的产品A的单位利润变动范围。（4分）

（3）如果原材料乙的市场价格为1.2元/kg，若要转卖原材料乙，公司应至少叫价多少，为什么？（3分）

（4）假如这时又试制成新产品D，生产一件新产品D需要消耗原材料甲、乙、丙分别为2kg、2kg、1kg，每件新产品D应获利多少时才有利于投产？（3分） （5）写出其对偶问题的数学模型，并求出其最优解。（4） （6）求出使最优解不变的产品C的单位利润变动范围。（3分） （7）如果原材料甲的市场价格为0.8元/kg，是否应该购买？购买多少为宜？（5分） （三）某工厂在计划期内要安排甲、乙两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的如下表所示。 设备 A B 甲 1 2 0 乙 1 1 1 资源 300台时 400kg 250kg 已知工厂每生产一单位产品甲可获利50元，每生产一单位乙可获利100元。 1、建立线性规划模型，求使该厂获利最大的生产计划。（12分） 2、求出使最优解不变的产品甲的单位利润变动范围。（5分）

3、若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B如数量不足可去市场购买，单价为40元，问该厂是否应购买，购进多少为宜？（7分） （四）已知某线性规划问题，其初始表及最优表如表1及表2所示。 表1（初始表）

XB CB x1 x2 x3 x4 x5 1 2 0 0 0 b x3 0 2 2 1 0 0 3 0 0 1 0 0 2 0 0 1 1 2 0 0 0 12 9 8 x4 0 x5 0 j 表2（最终表）

x1 1 1 0 1/2 0 -1/2 0 0 -3/2 1 3/2 0 1 0 0 1/2 0 0 -1/2 0 -1/2 2 3 4 x4 0 x2 2 j

1、 写出此线性规划问题的数学模型。（4分）

2、写出此线性规划问题的对偶问题的数学模型，并指出对偶问题的最优解及最优值。（7分）

2、 求c1的变化范围，使最优解不变。（5分） 3、 如b1由12变为16，求最优解。（10分）

4、 已知一求最大目标函数值的线性规划问题的单纯形表如下图 b XB x1 x1 x2 x3 x4 x5 x6 1 -1 4 0 0 2 0 -2 3 1 0 -1 0 -3 -1 0 1 3 0 2 3 0 0 6 b1 4 5 x4 x5 j

问表中b1、2 、3、6为何值时有：

（1） （2） （3） （4）

表中的解为唯一最优解； 表中的解为无穷多最优解； 线性规划问题有无界解。 表中的解为退化的可行解。



（运输问题）

（一）用表上作业法求解。（15分）

1、有甲、乙、丙三个城市，每年分别需要煤碳320、250、350（万吨），由A、B两个煤矿负责供应。已知煤矿年产量A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价（元/吨）如下表所示，由于需求大于产量，经协调平衡，甲城市必要时可少供应0-30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将A、B两煤矿的煤碳全部分配出去，满足上述条件又使总运费最低的调运方案。 A B 甲 15 21 乙 18 25 丙 22 16 2、某地区有三个化肥厂,除供应外地区需要外,估计每年可供应本地区的数字为：化肥厂A---7万吨, B---8万吨, C--3万吨,有四个产粮区需要该种化肥,需要量为：甲地区---6万吨,乙地区---3万吨,丙地区---3万吨,丁地区---3万吨,已知从各化肥厂到各产粮区的每吨化肥的运价如表所示,试根据以下资料制订一个使总的运费最少的化肥调拨方案。

产粮区 化肥厂 A B C 5 4 8 甲 8 9 4 乙 7 10 2 丙 3 7 9 丁

3、汽车客运公司有豪华、中档和普通三种型号的客车5辆、10辆和15辆，每辆车上均可载客40人，汽运公司每天要送400人到B城市，送600人到B城市。每辆客车每天只能送一次，从客运公司到B和B城市的票价如下表所示。

到B城市（元/人） 到B城市（元/人） 甲（豪华） 80 65 乙（中档） 60 50 丙（普通） 50 40 （1）试建立总收入最大的车辆调度方案数学模型。（8分） （2）求最优调运方案（用表上作业法求解）。（14分）

1、（1）解：设xij 表示到Bi城市用j种车送的人数(i=1,2;j=1,2,3,分别代表豪华车、

中档车和普通车)，则数学模型为(1分)

maxZxxxxxx（1分） s.t. xxx（1分）

xxx（1分）

xx（1分）

xx（1分） xx（1分）

xij,i,;j,,（1分）

（2）解：作出产销平衡运价表及初始方案如下（6分）

甲（豪华） 乙（中档） 丙（普通） 50 40 400 0 200 600 200 0 产量 400 200 0 600 400 0 200 0 80 200 65 0 200 0 60 200 50 200 0 400 200 0 B B 假想地 销量 解的检验（用位势法）（5分） 甲（豪华） 乙（中档） 80 200 65 60 200 50 200 0 -10 丙（普通） 50 0 40 400 0 200 80 60 50 ui 0 B B-55 假想地 -10 0 -30 -50 vj 由于所有非基变量的检验数都小于等于零，因而此方案是最优方案（1分）

即用豪华车送200人到城市B，用中档车运200人到城市B和运200人到B，用普通车运400人到B，可实现最大利润为54000。（2分）

4、某试验设备厂按合同规定在当年前四个月末分别提供同一型号的干燥箱50、40、60、80台给用户。该厂每个月的生产能力是65台，如果生产的产品当月不能交货，每台每月必须支付维护及存储费0.15万元，已知四个月内每台生产费分别是1、1.25、0.87、0.98万元，试安排这四个月的生产计划，使既能按合同如期交货，又使总费用最小。 （1）试建立此问题的数学模型；（8分）

（2）将此问题转化成运输问题，建立平衡运价表，并求出最优解。（14分）

（指派问题）

1、某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家具及计算机5个类别，通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见下表。该商业集团如何做出投资决策使年利润最大。（用匈牙利法求解）。（20分） 地点 商品 电器 服装 食品 家具 计算机 1 120 80 150 90 220 2 300 350 160 200 260 3 360 420 380 - 270 4 400 260 300 180 - 2、分配甲乙丙丁四个人去完成五项任务，每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间最少的指派方案（用匈牙利法求解）。（20分） 人 任务 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 3、学校举行蛙泳、自由泳、仰泳、蝶泳四个项目的接力赛，已知五名运动员完成各项目的成绩（秒）如表所示。从中选拔一个接力队，使预期的比赛成绩最好（用匈牙利法求解）。（20分）

甲 乙 丙 丁 戊

蛙泳 20 15 18 19 17

自由泳

43 33 42 44 34

仰泳 33 28 38 32 30

蝶泳 29 26 29 27 28

4、某房地产公司计划在一住宅小区建设5栋不同类型的楼房B1，B2，B3，B4，B5。由三家建筑公司A1，A2，A3进行投标，允许每家建筑公司可承建1～2栋楼，经

过投标得出各建筑公司对各新楼的预算费用见下表，求使总费用最少的分派方案。(用匈牙利法求解)（20分） A1 A2 A3 B1 3 7 6 B2 8 9 9 B3 7 10 13 B4 15 14 12 B5 11 12 7

（动态规划）

1、用动态规划法求解。（25分）

某公司与用户签订了4个月的交货合同如下表所示：

月份 1 2 3 4 合同数量/百台 2 5 3 3 该公司的最大生产能力为每月4百台，该厂的存货能力为3百台。已知每百台的生产费用为20000元，在进行生产的月份，工厂要支出固定费用8000元，仓库的保管费用为每百台每月2000元，假定开始时及4月交货后都无存货，问各月应生产多少台产品，才能在满足交货的前提下，使得总费用最小？

2、某工厂需对一种产品制定今后四个月的生产计划，据估计在今后四个月内，市场对该产品的需求量见下表。该厂生产每批产品的固定成本为4千元，若不生产则为零；每生产1千件产品可变成本费用为1千元，而每1千件库存费用为0.5千元，该厂的最大库存量为3千件。该厂月生产能力为4千件，第一个月初库存量为0，第四个月末的库存量也为0，试问该厂应如何安排各月的生产与库存才能既满足市场需求，又使生产与库存的总费用最少？

市场 对某产品的需求 单位：千件

月份 1 2 3 4 需求量 2 3 2 4

3、某公司有资金4百万元，向A、B、C三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如下表所示，问如何分配资金，才使总效益值最大？（用动态规划法求解） 效益值 投资额 项目 A B C 0 1 2 3 4 47 51 59 71 76 49 52 61 71 78 46 70 76 88 88 4、某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如下表所示。问这5台设备应如何分配给这3个工厂，使得所

创造的利润为最大？（用动态规划法求解） 盈利 工厂 设备台数 0 1 2 3 4 5 月份 1 2 3 4 甲厂 乙厂 丙厂 0 0 0 3 5 4 7 10 6 9 11 11 12 11 12 13 11 12 合同数量（百台） 1 2 5 3 5、某公司与用户签订了4个月的交货合同如下表所示： 该公司的最大生产能力为每月4百台，该厂的存货能力为3百台。已知每百台的生产费用为20000元，在进行生产的月份，工厂要支出固定费用8000元，仓库的保管费每百台每月2000元，假定开始时及4月交货后都无存货，问各月应生产多少台产品，才能满足交货任务的前提下，使得总费用最小？(用动态规划法求解)（26分）

6、某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问如何设置销售点，才能使每月获得的总利润最大？（用动态规划求解） 销售店 利润 地区 1 2 3 0 0 0 0 1 16 12 10 2 25 17 14 3 30 21 16 4 32 22 17 7、某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户需要的工作日数以及获得的利润如下表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他公司去做，该咨询公司应如何选择客户使得在这10个工作日获利最大？（用动态规划求解）（26分） 咨询项目类型 1 2 3 4

待处理客户数 4 3 2 2 处理每个客户所需工作日数 1 3 4 7 处理每个客户所获利润 2 8 11 20

用Dijkstra法求解。（20分）

1、某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价如下表所示。新机器每一年运行及维修费为0.3万元，使用1~3年后机器每年的运行及维修费用分别为0.8、1.5、2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。

第j年 年初购置价 使用j年的机器处理价（即第j年末机器处理价） 第一年 第二年 第三年 第四年 2.5 2.6 2.8 3.1 2.0 1.6 1.3 1.1

2、某企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备使用了1-4年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在1-4年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。在第4年末设备一定被处理掉的情况下，试确定一个设备更新策略，使4 年的设备购置和维护费用最小。（用Dijkstra法求解）

5、某公司有一台已使用一年的生产设备，每年年底，公司就要考虑下一年度是购买新设备还是继续使用这台旧设备。若购买新设备，就要支出一笔购置费；若继续使用旧设备，则要支付维修费用，而且随着使用所限的延长而增长。已知这种设备每年年底的购置价格见表1，而第一年开始时使用的有一年役龄的老设备其净值为8，不同使用年限的维修费用见表2。制定一个4年内设备的使用或更新计划，使4年内设备的使用维修费和设备购置费的总支出最小。（用狄克斯托标号法求解）（24分）

表1

年份 年初价格 表2 使用年限 年维修费用

2、某工厂需要外购某一个部件，年需求为4800件，单价为40元，每次的订购费用为350元，每个部件存储一年的费用为每个部件的价格的25%；又假设每年有250个工作日，该部件需要提前5天订货（即订货后5天可送货到厂），不允许缺货，请求出： （1）经济订货批量。（4分） （2）两次订货所间隔的时间。（3分） （3）每年订货与存储的总费用。（3分）

五、建模题(本题共12分)

0~1 2 1~2 3 2~3 5 3~4 8 4~5 12 2 11 3 12 4 12 1、某公司要求销售部经理制定一个广告计划，计划用经费10000元，要求尽量多的人能看到广告。该经理选择了三种广告方法：电视、广播电台和报纸。据调查各种广告的费用如下：在地方电视台下午播放1.5分钟要1000元，晚上要2000元。该经理决定在电视上打广告至少两次，但不多于四次。在地方报纸上打半页广告费用是300元，一页要1000元。在广播电台上打广告的价格是：白天每半分钟600元，晚上每半分钟400元。公司在电台打广告的次数：白天最多不超过5次，晚上不超过3次。

根据该经理所获得的资料估计，在下午观看电视广告节目的大约有40000人，晚上有90000人。看日报的大约有60000人，并估计有1/2的人看整页的广告，1/3的人看半页的广告。广播电台的听众白天有40000人，晚上有30000人。根据以上信息建立其数学模型。（只建模型不求解）

2、某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际的有效工作时间分别为42小时和36小时。为完成这三项工作任务，该公司需要每周总有效工作时间为：第一项工作10000小时；第二项工作20000小时；第三项工作为30000小时。需招收的工人数为：技工不超过400人；力工不超过800人。根据以上信息试建立其数学模型，确定招收技工和力工各多少人，使总的工资支出为最少。（只建模型不求解）

3、某企业在考虑本单位职工的升级调资方案时，依次遵守以下规定：

1． 不超过年工资总额60000元。

2． 每级的人数不超过定编规定的人数。

3． B、C级的升级面尽可以达到现有人数的20%。

4． C级不足编制的人数可录用新职工，而A级的职工中有10%要退休。 有关资料汇总后如下表所示。问该企业应如何拟订一个满意的方案。 等级 工资额/元·年-1 现有人数 编制人数 A B C 2000 1500 1000 10 12 15 37 12 15 15 42 合计

,x2,x3分别表示提升到A、B级和录用C级的新职工人数。对目标确定的优先解：设x1 因子为：P1 ：不超过年工资总额60000元。

P2：每级的人数不超过定编规定的人数。

P3：B、C级的升级面尽可能达到现有人数的20%。

先分别建立各自的目标约束。 年工资总额不超过60000元：

10-100.1x1 150012x2-x1100015x3-x2d1d1600002000 每级的人数不超过定编规定的人数：

对A级有 10-100.1x1d2d212

对B级有 12x2-x1d3d315 对C级有 15x3-x2d4d415

对B、C级的升级面尽可能达到现有人数的20%：

对B级有 x1d5d5120.2 对C级有 x2d6d6150.2 目标函数为：minZP1d1P2d2d3d4P3d5d6

4、某彩色电视机组装工厂，生产A、B、C三种规格电视机。装配工作在同一生产

线上完成，三种产品装配时的工时消耗分别为6、8和10h。生产线每月正常工作时间为200h；三种规格电视机销售后，每台可获得分别为500、600和800元。每月销量预计为12、10、6台。该厂经营目标如下：

P1 ：利润指标定为每月16000元。 P2：充分利用生产能力。 P3：加班时间不超过24h。

P4：产量以预计销量为标准。

为确定生产计划，试建立该问题的目标规划模型。

,x2,x3分别表示A、B、C三种规格电视机的产量 解：设x1 目标规划模型为：

minZP1d1--P2d2P3d3P4d4d4d5d5d6d6

500x1650x2800x3d1d116000

6x18x210x3d2d2200 d2d3d324

x1d4d412

x2d5d510 x3d6d66

x1,x2,x30;di,di0(i1,,6)

综合题：

要铺设一条从A到E的管道，各箭线旁数字为相应的两点间距离，如下图。

甲、乙、丙、丁4人讨论用什么样的运筹学模型方法求解。甲提出用Dijkstra算法来求A到E的最短距离和最短路程；乙认为可用动态规划求解，但丙和丁认为从A-B1-D1-E为三个阶段，而从A-B2-C2-D2-E为四个阶段，因而认为乙的建议不可行；丙提出这个问题可通过建立整数规划的模型求解，但甲和乙对此持怀疑态度；丁设想先找出图中最小生成树，由树图中任意两点间存在唯一的链，故最小生成树中从A到E的链即为从A到E到铺设管道的最短路径，对此乙和丙不同意。因此除一致同意甲的方法外，对乙、丙、丁的方法设想均有争议。试发表你对乙、丙、丁所述方法的评论意见并说明同意或反对的理由。