四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A )
《管理运筹学》
一、 单选题(每题2分,共20分。)
1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规
划问题求解,原问题的目标函数值等于( C )。
A. maxZ
B. max(-Z)
C. –max(-Z) 2. 下列说法中正确的是( B )。
A.基本解一定是可行解 B.基本可行解的每个分量一定非负 C.若B 是基,则B 一定是可逆D.非基变量的系数列向量一定是线性相关的
3.在线性规划模型中,没有非负约束的变量称为 ( D )
*
多余变量 B .松弛变量 C .人工变量 D .自由变量
4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得( A )。
A.多重解 B.无解 C.正则解 D.退化解 5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 ( D )。
A .等式约束
B .“≤”型约束
C .“≥”约束
D .非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y
是( B )。
A.多余变量 B.自由变量 C.松弛变量 D.非负变量 7.在运输方案中出现退化现象,是指数字格的数目( C )。
A.等于m+n
B.大于m+n-1
C.小于m+n-1
D.等于m+n-1
8. 树T的任意两个顶点间恰好有一条( B )。 {
A.边 B.初等链 C.欧拉圈 D.回路 9.若G 中不存在流f 增流链,则f 为G 的 ( B )。
A .最小流
B .最大流
C .最小费用流
D .无法确定
10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足( D )
A.等式约束 B.“≤”型约束 C.“≥”型约束 D.非负约束
二、多项选择题(每小题4分,共20分)
1.化一般规划模型为标准型时,可能引入的变量有 ( )
A .松弛变量
B .剩余变量
C .非负变量
D .非正变量
E .自由变量
2.图解法求解线性规划问题的主要过程有 ( )
A .画出可行域
B .求出顶点坐标
C .求最优目标值 ]
D .选基本解
E .选最优解
3.表上作业法中确定换出变量的过程有 ( )
A .判断检验数是否都非负
B .选最大检验数
C .确定换出变量
D .选最小检验数
E .确定换入变量
4.求解约束条件为“≥”型的线性规划、构造基本矩阵时,可用的变量有 ( )
A .人工变量
B .松弛变量 C. 负变量 D .剩余变量 E .稳
态变量
5.线性规划问题的主要特征有 ( )
A .目标是线性的
B .约束是线性的
C .求目标最大值
D .求目标最小值
E .非线性 三、
计算题(共60分)
、
1. 下列线性规划问题化为标准型。(10分)
123min +5-2Z x x x =-
123123121236
23510
0,0,x x x x x x x x x x x +-≤-+≥+=≥≤符号不限
2. 写出下列问题的对偶问题 (10分)
123min 42+3Z x x x =+
123123121234+56=7
891011121314
0,0x x x x x x x x x x x --+≥+≤≤≥无约束,
】
3. 用最小元素法求下列运输问题的一个初始基本可行解(10分)
4.某公司有资金10万元,若投资用于项目
(1,2,3)i i i x =的投资额为时,其收益分别为11122()4,()9,g x x g x x == 33()2,g x x =问应如何分配投资数额才能使总收益最大(15分)
5. 求图中所示网络中的最短路。(15分)
,
满足
满足
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A )
《管理运筹学》参考答案
一、单选题 ,
4. A
5. D
6. B
7. C 9. B
二、多选题
1. ABE
2. ABE
3. ACD
4. AD
5. AB 三、计算题
1、 max(-z)=
''''
123352()x x x x -+-
2、 写出对偶问题
maxW=12371114y y y ++
…
3、解:
4.解:状态变量k s 为第k 阶段初拥有的可以分配给第k 到底3个项目的资金额;
决策变量k x 为决定给第k 个项目的资金额;状态转移方程为1k k k s s x +=-;最优指标函数()k k f s
表示第k 阶段初始状态为k s 时,从第k 到第3个项目所获得的最大收益,()
k k f s 即为所求的总收益。递推方程为:
{}10()()()(1,2,3)
max k k
k k k k k k x s f s g x f s k ++≤≤=+= 44()0f s = 当k=3时有
{}
33
2
3330()2max x s f s x ≤≤=
当33x s =时,取得极大值22
3s ,即:
{}33
2
2
33330()22max x s f s x x ≤≤==
、
当k=2时有:
{}
22
2
222330()9()max x s f s x f s ≤≤=+
{}
2222
3
092max x s x
s
≤≤+=
{}
22
222092()max x s x s x ≤≤+-=
令 2
222222(,)92()h s x x s x =+-
用经典解析方法求其极值点。
由 2
22292()(1)0dh s x dx =+--= 解得:
229
4x s =-
而 22
2
240d h d x
=
所以
229
4x s =-
是极小值点。 。
极大值点可能在[0,2s ]端点取得:
2
22(0)2f s =, 222()9f s s =
当222(0)()f f s =时,解得 29/2s =
当29/2s 时,222(0)()f f s ,此时,*
20x =
当2
9/2s 时,222(0)()f f s ,此时,*
22x s =
当k=1时,
{}
11
111220()4()max x s f s x f s ≤≤=+
当 222()9f s s =时,
{}11
111110()499max x s f s x s x ≤≤=+-
{}11
111
0959max x s s x s ≤≤=-=
但此时 211100109/2s s x =-=-=,与29/2s 矛盾,所以舍去。 当2222
()2f s s =时,
{}
121111010(10)42()max x f x s x ≤≤=+-
~
令 2
111111(,)42()h s x x s x =+-
由 1
22144()(1)0
dh s x dx =+--= 解得: 211x s =-
而 22
2
210d h d x = 所以 111x s =-是极小值点。
比较[0,10]两个端点 10x =时,1(10)200f = 110x =时,1(10)40f =
*
10x = 所以
再由状态转移方程顺推:
*
21110010s s x =-=-= `
因为 29/2s
所以 *20x =,*
32210010s s x =-=-=
因此
*3310x s == 最优投资方案为全部资金用于第3个项目,可获得最大收益200万元。
5. 解:用Dijkstra 算法的步骤如下, P (1v )=0
T (j v
)=∞(j =2,3…7) 第一步:
因为()21,v v ,()31,v v A ∈ 、
且2v ,3v 是T 标号,则修改上个点的T 标号分别为:
()()()[]12122,m in w v P v T v T +=
=
[]min ,055∞+=
()()()[]13133,m in w v P v T v T +=
=
[]min ,022∞+=
所有T 标号中,T (3v )最小,令P (3v )=2 第二步:3v 是刚得到的P 标号,考察3v
()34,v v ,()36,v v A ∈,且5v ,6v 是T 标号 ()()()44334min ,T v T v P v w =+????
=
[]min ,279∞+=
《
()[]6min ,2T v =∞+4=6
所有T 标号中,T (2v )最小,令P (2v )=5 第三步:2v 是刚得到的P 标号,考察2v
()()()44224min ,T v T v P v w =+????
=
[]min 9,527+=
()()()55225min ,T v T v P v w =+????
=
[]min ,5712∞+=
所有T 标号中,T (6v )最小,令P (6v )=6 第四步:6v 是刚得到的P 标号,考察6v
()()()44664min ,T v T v P v w =+????
、
=
[]min 9,627+=
()()()55665min ,T v T v P v w =+????
=
[]min 12,617+= ()()()77667min ,T v T v P v w =+????
=
[]min ,6612∞+=
所有T 标号中,T (4v ),T (5v )同时标号,令P (4v )=P (5v )=7 第五步:同各标号点相邻的未标号只有7v
()()()[]57577,m in w v P v T v T +=
=
[]min 12,7310+=
至此:所有的T 标号全部变为P 标号,计算结束。故1v 至7v 的最短路为10。
(
《管理运筹学》模拟试题2
一、单选题(每题2分,共20分。)
1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规划问题求解,原问题的目标函数值等于( )。
A. maxZ
B. max(-Z)
C. –max(-Z) 2. 下列说法中正确的是( )。
A.基本解一定是可行解 B.基本可行解的每个分量一定非负
C.若B 是基,则B 一定是可逆 D.非基变量的系数列向量一定是线性相关
的
3.在线性规划模型中,没有非负约束的变量称为( ) /
A .多余变量
B .松弛变量
C .人工变量
D .自由变量
4. 当满足最优解,且检验数为零的变量的个数大于基变量的个数时,可求得( )。 A.多重解 B.无解 C.正则解 D.退化解
5.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足( )。
A .等式约束
B .“≤”型约束
C .“≥”约束
D .非负约束 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i y
是( )。 A.多余变量 B.自由变量 C.松弛变量 D.非负变量 7. 在运输方案中出现退化现象,是指数字格的数目( )。
A.等于m+n
B.大于m+n-1
C.小于m+n-1
D.等于m+n-1
8. 树T的任意两个顶点间恰好有一条( )。 ;
A.边 B.初等链 C.欧拉圈 D.回路
9.若G 中不存在流f 增流链,则f 为G 的( )。
A .最小流
B .最大流
C .最小费用流
D .无法确定
10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足( )
A.等式约束 B.“≤”型约束 C.“≥”型约束 D.非负约束
二、判断题题(每小题2分,共10分)
1.线性规划问题的一般模型中不能有等式约束。 ( ) 2.对偶问题的对偶一定是原问题。 ( ) 3.产地数与销地数相等的运输问题是产销平衡运输问题。 ( ) 4.对于一个动态规划问题,应用顺推或逆解法可能会得出不同的最优解。 ( ) <
5.在任一图G 中,当点集V 确定后,树图是G 中边数最少的连通图。 ( )
三、计算题(共70分)
1、某工厂拥有A,B,C 三种类型的设备,生产甲、乙两种产品,每件产品在生产中需要使用的机时数,每件产品可以获得的利润,以及三种设备可利用的机时数见下表:
求:(1)线性规划模型;(5分) (2)利用单纯形法求最优解;(15分)
4. 如图所示的单行线交通网,每个弧旁边的数字表示这条单行线的长度。现在有一个人要从
1v 出发,经过这个交通网到达8v ,要寻求使总路程最短的线路。
(15分)
/
5. 某项工程有三个设计方案。据现有条件,这些方案不能按期完成的概率分别为,,,即三个方案均完不成的概率为××=。为使这三个方案中至少完成一个的概率尽可能大,决定追加2万元资金。当使用追加投资后,上述方案完不成的概率见下表,问应如何分配追加投资,才能使其中至少一个方案完成的概率为最大。(15分)
。
《管理运筹
学》模拟试题2参考答案
一、单选题
4. A .
5. D
6. B
7. C 9. B 二、多选题
1.×
2. √
3.×
4. √
5. √ 三、计算题
1. 解:(1)12m ax 15002500z x x =+
123265x x +≤ 满足 12240x x +≤ 。
2375x ≤
12,0x x ≥
(2)
最优解 *(5,25,0,5,0)T x = 最优目标值 = 70000元
2. 解:此规划存在可行解(0,1)T
x =,其对偶规划
'
123m in 4143w y y y =++
满足: 12333y y y -++≥ 123222y y y +-≥
123,,0y y y ≥
对偶规划也存在可行解(0,1,0)T
y =,因此原规划存在最优解。
3、解:可以作为初始方案。理由如下: (1)满足产销平衡
(2)有m+n-1个数值格
(3)不存在以数值格为顶点的避回路
]
4.解:
5.解:
此题目等价于求使各方案均完不成的概率最小的策略。把对第k 个方案追加投资看着决策过程的第k 个阶段,k =1,2,3。
k x -----------第k 个阶段,可给第k, k+1,…,3个方案追加的投资额。 k u -----------对第k 个方案的投资额
{}
k
k k k k k k k u x x x u u u D -=≤==+12,1,0且
阶段指标函数
()()k k k k u x p u x C ,,=,这里的()k k u x p ,是表中已知的概率值。
*
过程指标函数
()()()()()1
,,,44113
,13
3,min =?=?=++∈+=x f x f u x C x f V u x C V k k k k D u k k k k
i k k k k
k
以上的k =1,2,3
用逆序算法求解 k =3时,()()
3333,min 3
3u x C x f D u ∈= 得表:
最优策略:*1u =1,*
2u =1, *3u =0或
*1u =0,*
2u =2, *3u =0,
至少有一个方案完成的最大概率为=
#
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( C )
《管理运筹学》
二、 多选题(每题2分,共20分)
1.求运输问题表上作业法中求初始基本可行解的方法一般有 ( )
A .西北角法
B .最小元素法
C .单纯型法
D .伏格尔法
E .位势法
2.建立线性规划问题数学模型的主要过程有 ( ) A . - B . 确定决策变量 B . 确定目标函数 C .确定约束方程 D .解法 E .结果
3.化一般规划模型为标准型时,可能引入的变量有 ( ) A .松弛变量 B .剩余变量 C .自由变量 D .非正变量 E .非负变量
8.就课本范围内,解有“≥”型约束方程线性规划问题的方法有 ( ) A .大M 法 B .两阶段法 C .标号法 D .统筹法 E .对偶单纯型法 10.线性规划问题的主要特征有 ( ) A .目标是线性的 B .约束是线性的 C .求目标最大值 D .求目标最小值 E .非线性
二、辨析正误(每题2分,共10分)
1.线性规划问题的一般模型中不能有等式约束。 ( ) 2.线性规划问题的每一个基本可行解对应可行域上的一个顶点。 ( ) —
3.线性规划问题的基本解就是基本可行解。 ( ) 4.同一问题的线性规划模型是唯一。 ( ) 5.对偶问题的对偶一定是原问题。 ( ) 6.产地数与销地数相等的运输问题是产销平衡运输问题。 ( ) 7.对于一个动态规划问题,应用顺推或逆解法可能会得出不同的最优解。 ( ) 8.在任一图G 中,当点集V 确定后,树图是G 中边数最少的连通图。 ( ) 9.若在网络图中不存在关于可行流f 的增流链时,f 即为最大流。 ( ) 10.无圈且连通简单图G 是树图。 ( )
三、计算题(共70分)
1、某工厂要制作100套专用钢架,每套钢架需要用长为2.9m , 2.1m , 1.5m 的圆钢各一根。已知原料每根长7.4m ,现考虑应如何下料,可使所用的材料最省
%
求:(1 (2)将上述模型化为标准型(5分)
2、求解下列线性规划问题,并根据最优单纯形法表中的检验数,给出其对偶问题的最优解。(15分)
123ax 437m z x x x =++
12322100x x x ++≤ 12333100x x x ++≤
123,,0x x x ≥
3. 10分)
>
4.用Dijkstra算法计算下列有向图的最短路。(15分)
v2
v6
v1
v4v5
v7
v3
2
3
5
2
1
7
3
5
1
7
5
5
5.某集团公司拟将6千万资金用于改造扩建所属的A、B、C三个企业。每个企业的利润增长额与所分配到的投资额有关,各企业在获得不同的投资额时所能增加的利润如下表所示。集团公司考虑要给各企业都投资。问应如何分配这些资金可使公司总的利润增长额最大(15分)
四川大学网络教育学院模拟试题( C )
《管理运筹学》参考答案
三、?
四、多选题
4. ABE .
5. AB
二、判断题
1. ×
2. √3×4.×5. √6.×7.×8. √9. √10. √
三、计算题
1. 解分析:利用7.4m 长的圆钢截成
2.9m , 2.1 m ,1.5m 的圆钢共有如下表所示的8
方案
毛胚/m
方案
1
方案
2
,
方案
方案
4
方案
5
方案
6
方案
7
方案
8
3 2 1 1 (
1 0 0 0 0 0
2 1 0
?
3 2 1 0 1 0 1 3 0
<
2 3
4 合计
"
剩余料头
# 设1x ,2x ,3x ,4x ,5x ,6x ,7x ,8x 分别为上面8中方案下料的原材料根数。
12345678min z x x x x x x x x =+++++++
2. 解 :引入松弛变量45,x x 将模型化为标准型,经求解后得到其最优单纯型表:
最优单纯型表
基变量
i b 1x 2x 3x 4x 5x
2x
)
3x
25 25
-3/4 1 0 3/4 -1/2 5/4 0 1 -1/4 1/2
i σ
-250 -10/4 0 0 -1/2 -2
由此表可知,原问题的最优解*(0,25,25)T x =,最优值为250.表中两个
松弛变量的检验数分别为-1/2 , -2 ,由上面的分析可知,对偶问题的
最优解为(1/2,2)T
-。
)
3.解:不能作为初始方案,因为应该有n+m-1=5+4-1=8有数值的格。
4.解:P (1v )=0
T (j v
)=∞(j =2,3…7) 第一步:
因为()21,v v ,()31,v v ,()A v v ∈41,
且2v ,3v ,4v 是T 标号,则修改上个点的T 标号分别为:
()()()[]12122,m in w v P v T v T += =[]220,m in =+∞
()()()[]13133,m in w v P v T v T +=
!
=[]550,m in =+∞
()()()[]14144,m in w v P v T v T += =[]330,m in =+∞
所有T 标号中,T (2v )最小,令P (2v )=2 第二步:2v 是刚得到的P 标号,考察2v
()32,v v ,()A v v ∈62,,且3v ,6v 是T 标号 ()()()[]23233,m in w v P v T v T +=
=[]422,5m in =+
()[]972,m in 6=+∞=v T
所有T 标号中,T (4v )最小,令P (4v )=3 ;
第三步:4v 是刚得到的P 标号,考察4v ()()()[]45455,m in w v P v T v T +=
=[]853,m in =+∞
所有T 标号中,T (3v )最小,令P (3v )=4 第四步:3v 是刚得到的P 标号,考察3v ()()()[]35355,m in w v P v T v T +=
=[]734,8m in =+
()()()[]36366,m in w v P v T v T +=
=[]954,9m in =+
所有T 标号中,T (5v )最小,令P (5v )=7 !
第五步:5v 是刚得到的P 标号,考察5v ()()()[]56566,m in w v P v T v T += =[]817,9m in =+
()()()[]57577,m in w v P v T v T +=
=[]1477,m in =+∞
所有T 标号中,T (6v )最小,令P (6v )=8 第6步:6v 是刚得到的P 标号,考察6v ()()()[]67677,m in w v P v T v T +=
=[]1358,14m in =+
T (7v )=P (7v )=13 )
至此:所有的T 标号全部变为P 标号,计算结束。故1v 至7v 的最短路为13。
5. 解:第一步:构造求对三个企业的最有投资分配,使总利润额最大的动态规
划模型。
(1) 阶段k :按A 、B 、C 的顺序,每投资一个企业作为一个阶
段,
k =1,2,3,4
(2) 状态变量k x :投资第k 个企业前的资金数。 (3) 决策变量k d :对第k 个企业的投资。 (4) 决策允许集合:0k k d x ≤≤。 (5) …
(6)
状态转移方程:1k k k x x d +=-。
(7) 阶段指标:(,)k k k v x d 见表中所示。
(8) 动态规划基本方程:
11()max{(,)()}k k k k k k k f x v x d f x ++=+ 44()0f x = (终端条件)
第二步:解动态规划基本方程,求最有值。
k=4, 44()0f x =
k=3, 334330,d x x x d ≤≤=-
k=2, 220d x ≤≤, 322x x d =-
k=1, 110d x ≤≤, 211x x d =- 第三步:回溯求得最优策略 最有解即最优策略巍:
16x =,*14d =;2112x x d =-=,*
21d =;
*3221x x d =-=,*
31d =;*433
0x x d =-= 返回原问题的解,即企业A 投资4千万元,企业B 投资1千万元,企业C 投
资1千万元,最大效益为22千万元。