运筹学卷子·1

决策变量：以给某项目投资的金额作为决策变量 ，则
状态转移方程：
0 1 2 3 4
*
0
1
2
3
4
38
41
48
60
66
38
41
48
60
66
0
1
2
3
4
0 1 2 3 4
*
0
1
2
3
4
40+38
40+41 42+38
40+48 42+41 50+38
40+60 42+48 50+41 60+38
40+66 42+60 50+48 60+41 66+38
项目
投资额
0
1
2
3
4
A
38
41
48
60
66
B
40
42
50
60
66
C
38
64
68
78
76
七、用单纯形法解线性规划问题，如何判断下列问题：（15分）
1.无可行解；2有多重解；3.有无界解。
试题一答案
一、解：设代表第i种原料混入第j种产品中的数量，其中i=1，2，3；j=1，2，3；则
二、解：原问题可化为：
60
30
70
四、从甲,乙,丙,丁,戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。（20分）
人工作
一
二
三
四
甲
10
5
15
20
乙
2
10
5
15
丙
3
15
14
13
丁
15
2
7
6
戊
9
4
15
8
五、求V1到各点的最短路及最短路径。（20分）
六、某公司有资金4百万元向A，B，C三个项目追加投资，各个项目可以有不同的投资额（以百万元为单位），相应的效益值如下表。问怎样分派资金，使总效益值最大，试用动态规划方法求解。（25分）
4 1 -4 0 1 0 4 -
0 0 2 0 -1 1 4 2
0 17 0 -4 0
0 0 0 1 -1/2 3/2 12
4 1 0 0 -1 2 12
1 0 1 0 -1/2 1/2 2
0 0 0 9/2 -17/2
由于 而对应的
此线性规划问题无界
二、解
（1）X2的价值系数由-7变为3。
最优解发生变化，继续迭代。
40
35
50
-25
20
25
40
0
15
60
30
15
30
0
100
0
30
15
35
65
40
30
55
30
25
65
130
-5
0
10
M
M-10
0
15
0
15
0
5
20
-30
销
25
115
60
30
70
300
20
40
15
30
30
此时检验数均大于或等于0，为最优解
四、 解：
10 5 1520M8 3 1012M5 0 79M-3
013 8 4 0
12 01 M-90
7 3 1001
此时，费用最小，
其中，丙一，甲二，乙三，戌四
五、解：
0*
11 9* 10
11 10* 20
11* 21 20
21 21*
21* 28
25*
11：
9：
10：
21：
20：
25：
六、解：
阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。
状态变量：以可以提供的投资额作为状态变量 ，其范围为0，1，2，3，4百万
2 1 0 0 0
2
0
0
1 1 1 0 0
0 2 1 1 0
0 -4 -6 0 1
5
5
-9
0 -1 -2 0 0
- 1/4 1/3 - -
2
0
0
1 0 1/2 0 1/4
0 0 -2 1 1/2
0 1 3/2 0 -1/4
0 0 -1/2 0 -1/4
-31/4
三、解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得：
试题一
试题代码：453 题名称：运筹学
１．本试题共七题，共3页，请考生认真检查；
一、某炼油厂生产三种牌号的汽油，70#，80#和85#汽油。每种汽油有不同的辛烷值和含硫量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用数量、质量指标和生产成本见表1，每种汽油的质量要求和销售价格见表2。问该炼油厂如何安排生产才能使其利润最大？假定在调和中辛烷值和含硫量指标都符合线性相加关系。试建立数学模型。（25分)
二、用对偶单纯形法求解下列线性规划问题：（25分）
三、已知某运输问题的产销平衡表与单位运价表如下表所示，B2地区需要的115单位必须满足，试确定最优调拨方案。（20分）
AiBj
B1
B2
B3
B4
B5
产量
A1
10
15
20
20
40
50
A2
20
40
15
30
30
100
A3
30
35
40
55
25
130
销量
25
115
正副
B1
B2
B3
B4
B5
A1
*
*
A2
*
*
A3
*
*
A4
*
*
A5
*
七、填空：（20分）
1．某工程公司拟从四个项目中选择若干项目，若令
用 的线性表达式表示下列要求：
（1）从1，2，3项目中至少选2个：；
（2）只有项目2被选中，项目4才能被选中：；
2．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经
4.对于极大化问题max Z = …令 转化为极小化问题 ，则利用匈牙利法求解时，极大化问题的最优解就是极小化问题的最优解，但目标函数相差：n+c；
5.如果图中从 至各点均有惟一的最短路，则连接至其他各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。
试题二答案
一、解：设 代表第i月正常生产的柴油机数量，
第三阶段：
第二阶段：
其中
第一阶段：
其中
六、解：依题意，首先给出一个可行流
在初始流上增流到不能再增，得到如下结果：
此时已不能再增流，流量 ，不能满足市场的需求量。应修改仓库3到市场3和4的容量，分别增流10和5即能满足需求。
七、解：3、5正确。
试题三
试题代码：453试题名称：运筹学
考生注意∶
１．本试题共七题，共3页，请考生认真检查；
三、解：此题可看作指派问题求解：
5 6 10 1 2 5 0 1 4 003
8 10 12 ~ 4 6 7 ~ 0 2 3 ~01 2
4 4 5 0 0 0 0 0 0 1 00
四、解：将最大化问题化为极小化问题，并将系数转为正，即令 ，整理得
综上，该0-1规划无可行解
五、解：按三个变量划分为三个阶段，状态转移方程
２．请务必将答案写在答卷纸上，写在试卷上的答案无效。
题号
一
二
三
四
五
六
七
总分
得分
签字
一、用单纯形法求解下述线性规划问题（20分）
二、设一线性规划问题为（25分）
其最优单纯形表为
2
-7
1
0
0
B-1b
2
1
1
1
1
0
6
0
0
3
1
1
1
10
0
-9
-1
-2
0
在下述每一种情况下，进行灵敏度分析并求出最优解。
2目标函数变为 ；
四、某校蓝球队准备从以下6名预备队员中选拔3名为正式队员，并使平均身高尽可能高，这6名预备队员情况如下表所示，试建立数学模型。（20分）
队员的挑选要满足下列条件：
2少补充一名后卫队员；
3大李或小田中间只能入选一名；
4最多补充一名中锋；
5如果大李或小赵入选，小周就不能入选。
预备队员
号码
身高（厘米）
位置
3约束条件右端项由(6,4)T变为(3,5)T；
4增加一个约束条件
三、某种产品今后四周的需求量分别为300，700，900，600件，必须得到满足。已知每件产品的成本在起初两周是10元，以后两周是15元。工厂每周能生产这种产品700件，且在第二、三周能加班生产。加班后，每周可增产200件产品，但成本每件增加5元。产品如不能在本周交货，则每件每周存贮费是3元。问如何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。（25分）
30
20
音乐
40
30
30
20
10
美术
20
30
20
30
30
问：应如何安排一周的讲座日程，使不能出席讲座的学生总数最少，并计算不能出席讲座的学生总数。
六、某飞行队有5名正驾驶员和5名副驾驶员。由于种种原因，某些正、副驾驶员不能同机飞行，某些则可以，如下表所示。每架飞机出航时需正，副驾驶员各一人。问最多能有几架飞机同时出航？应如何安排正，副驾驶员?用图论方法求解。（20分）
二、考虑线性规划问题：（25分）
用单纯形法求解，得其终表如下：
5
12
4
0
-M
B-1b
12
0
1
-1/5
2/5
-1/5
8/5
5
1
0
7/5
1/5
Βιβλιοθήκη Baidu2/5
9/5
0
0
-3/5
-29/5
-M+2/5
X4为松弛变量，X5为人工变量，
1．上述模型的对偶模型为：；
2．对偶模型的最优解为：；
3．当两种资源分别单独增加一个单位时，目标函数值分别增加和；
2 3 1 0 0
2
0
1 1 1 1 0
0 3 1 1 1
6
10
6
10/3
0 1 -1 -2 0
2
3
1 0 2/3 2/3 -1/3
0 1 1/3 1/3 1/3
8/3
10/3
0 0 -4/3 -2 -1/3
-46/3
代表第i月加班生产的柴油机数量，
代表第i月末的库存量，则 =4
二、解：
1、 对偶模型
2、由单纯形表可看出， 由于
则对偶问题的第一、二个约束是紧的，可解出
将 代入第三个约束，满足约束条件，则
3、5和2
4、
5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少，要么不变，绝对不会变大。
销
产
产
10
5
15
50
20
20
20
5
40
35
50
-15
20
10
40
10
15
60
30
30
30
10
100
0
30
5
35
65
40
20
55
20
25
65
130
5
0
15
M
M-10
0
5
0
-10
0
5
20
-20
销
25
115
60
30
70
300
20
30
15
30
20
此方案还不是最优，需要调整
销
产
产
10
15
15
50
20
30
20
15
市场
仓库
1
2
3
4
供应量
1
30
10
0
40
20
2
0
0
10
50
20
3
20
10
40
5
100
需求量
20
20
60
20
七．下列叙述中正确的是（）（20分）
1.图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的；
2.若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解；
3.如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；
济意义是，若从
该空格出发进行调整，设调整量为2，则调后可使总运费下降；
3.动态规划中的Bellman最优性原理是
。
试题三答案
一、解：将原问题化为标准形得
4 1 0 0 0
0 -1 1 1 0 0 2 -
0 1 -4 0 1 0 4 4
0 1 -2 0 0 1 8 8
4 1 0 0 0
0 0 -3 1 1 0 6 -
表1
序号i
原料
辛烷值
含硫量（％）
成本（元/吨）
可用量（吨/日）
1
直馏汽油
62
1.5
600
2000
2
催化汽油
78
0.8
900
1000
3
重整汽油
90
0.2
1400
500
表2
序号j
产品
辛烷值
含硫量（％）
销售价（元/吨）
1
70＃汽油
≥70
≤1
900
2
80＃汽油
≥80
≤1
1200
3
85＃汽油
≥85
≤0.6
1500
大张
大李
小王
小赵
小田
小周
4
5
6
7
8
9
193
191
187
186
180
185
中锋
中锋
前锋
前锋
后卫
后卫
五、某高校拟开设文学、艺术、音乐、美术四个学术讲座。每个讲座每周下午举行一次。经调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20分）
星期
讲座
一
二
三
四
五
文学
50
40
60
30
10
艺术
40
30
20
78
81
88
100
106
0
0
0，2
0
0
0 1 2 3 4
*
4
38+106 64+100 68+88 78+81 76+78
164
1
总效益最大值为164，其中 。
七、解：
1、无可行解：最终表人工变量不为零；或右侧常数 ，对应的 ；
2、有多重解： （非基变量）且至少有一个为零。
3、有无界解：非基变量的检验数 ，且对应的系数列向量 。
试题 二
试题代码：453试题名称：运筹学
考生注意∶
１．本试题共七题，共3页，请考生认真检查；
一、华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的订单数量分别为3000，4500，3500，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低，建立其线性规划模型。（20分）
2 10 5 15 0 0 8 0 7 0 0 8 0 7 0
3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~
15 27 M0 13 02 M-8 0 13 02 M-8 0
9 4 15 8 0 7 2 10 0 0 7 2 10 0 0
4068 M-3
0 907 1
4．最优基的逆矩阵B-1=
5．如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？
.
三、求解下列各题（解题方法自选）（20分）
四、用隐枚举法求解下列0-1规划问题（20分）
五、用动态规划方法求解下列问题（25分）
六、今有三个仓库运送某种产品到四个市场上去，仓库的供应量是20，20和100，市场需求量是20，20，60和20，仓库与市场之间的路线上的容量如下表（容量零表示两点间无直接的路线可通）。用图论方法确定现有路线容量能否满足市场的需求，若不能，应修改哪条线路的容量。（20分）