四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A )
《管理运筹学》
一、 单选题(每题2分,共20分。)
1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规
划问题求解,原问题的目标函数值等于( C )。
A. maxZ
B. max(-Z)
C. –max(-Z)
D.-maxZ 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 =-
1231231
21236
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
8910111213140,0
x 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 )
《管理运筹学》参考答案
一、单选题
满足
满足
1.C
2.B
3.D
4. A
5. D
6. B
7. C
8.B
9. B 10.D 二、多选题
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 即为所求的总收益。递推方程为:
{}
1
0()()()(
1,2,3)
ma x k k k k k k k k x s f s g x f s k ++≤≤=+=
44()0f s = 当k=3时有
{}
332
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
2222330()9()max x s f s x f s ≤≤=+
{}
22223092max x s x
s ≤≤+=
{}
22
222092()max x s x s x ≤≤+-=
令 2
222
222(,)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 ≤≤=+-
{}11111
0959max x s s x s ≤≤=-=
但此时 211100109/2s s x =-=-=,与2
9/2s 矛盾,所以舍去。 当2
222()2f s s =时,
{}
121111010
(10)42()max x f x s x ≤≤=+-
令 2
111111(,)42()h s x x s x =+- 由 1
22144()(1)0dh 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,min w v P v T v T += =[]min ,055∞+=
()()()[]13133,min 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,min 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)
D.-maxZ 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. 如图所示的单行线交通网,每个弧旁边的数字表示这条单行线的长度。现在有一个人要从
1
v 出发,经过这个交通网到达
8
v ,要寻求使总路程最短的线路。(15分)
5. 某项工程有三个设计方案。据现有条件,这些方案不能按期完成的概率分别为0.5,0.7,0.9,即三个方案均完不成的概率为0.5×0.7×0.9=0.315。为使这三个方案中至少完成一个的概率尽可能大,决定追加2万元资金。当使用追加投资后,上述方案完不成的概率见下表,问应如何分配追加投资,才能使其中至少一个方案完成的概率为最大。(15分)
《管理运筹学》模拟试题2参考答案
一、单选题
1.C
2.B
3.D
4. A .
5. D
6. B
7. C
8.B
9. B 10.D 二、多选题
1.×
2. √
3.×
4. √
5. √ 三、计算题
1. 解:(1)12max 15002500z x x =+
123265x x +≤ 满足 12240x x +≤ 2375
x ≤ 12,0
x x ≥
(2)
最优解 *(5,25,0,5,0)T x = 最优目标值 = 70000元
2. 解:此规划存在可行解(0,1)T
x =,其对偶规划
123m i n 4143
w y y y =++ 满足: 12333y y y -++≥
123222
y y y +-≥ 123,,0
y 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,m in 3
3u x C x f D u ∈= 得表:
最优策略:*1u =1,*2u =1, *3
u =0或
*1u =0,*
2u =2, *3u =0,
至少有一个方案完成的最大概率为1-0.135=0.865
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( C )
《管理运筹学》
二、 多选题(每题2分,共20分)
1.求运输问题表上作业法中求初始基本可行解的方法一般有 ( ) A .西北角法 B .最小元素法 C .单纯型法 D .伏格尔法 E .位势法 2.建立线性规划问题数学模型的主要过程有 ( ) A . 确定决策变量 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分)
12
3a x 437m z x x x =++ 12322100x x x ++≤ 12333100
x 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 )
《管理运筹学》参考答案
三、多选题
1.ABD
2.ABC
3.ABC
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
方案
3
方案
4
方案
5
方案
6
方案
7
方案
8
2.9 2 1 1 1 0 0 0 0
2.1 0 2 1 0 3 2 1 0
1.5 1 0 1 3 0 2 3 4
合计7.3 7.1 6.5 7.4 6.3 7.2 6.6 6.0
剩余料
头
0.1 0.3 0.9 0 1.1 0.2 0.8 1.4
设1x,2x,3x,4x,5x,6x,7x,8x分别为上面8中方案下料的原材料根数。
12345678
min z x x x x x x x x
=+++++++
2. 解 :引入松弛变量45,x x 将模型化为标准型,经求解后得到其最优单纯型表:
由此表可知,原问题的最优解*(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,min w v P v T v T += =[]220,min =+∞ ()()()[]13133,min w v P v T v T += =[]550,min =+∞
()()()[]14144,min w v P v T v T += =[]330,min =+∞
所有T 标号中,T (2v )最小,令P (2v )=2 第二步:2v 是刚得到的P 标号,考察2v
()32,v v ,()A v v ∈62,,且3v ,6v 是T 标号
()()()[]23233,min w v P v T v T += =[]422,5min =+ ()[]972,min 6=+∞=v T
所有T 标号中,T (4v )最小,令P (4v )=3 第三步:4v 是刚得到的P 标号,考察4v
()()()[]45455,min w v P v T v T += =[]853,min =+∞
所有T 标号中,T (3v )最小,令P (3v )=4 第四步:3v 是刚得到的P 标号,考察3v
()()()[]35355,min w v P v T v T += =[]734,8min =+
()()()[]36366,min w v P v T v T +=
=[]954,9min =+
所有T 标号中,T (5v )最小,令P (5v )=7 第五步:5v 是刚得到的P 标号,考察5v
()()()[]56566,min w v P v T v T += =[]817,9min =+
()()()[]57577,min w v P v T v T +=
=[]1477,min =+∞
所有T 标号中,T (6v )最小,令P (6v )=8 第6步:6v 是刚得到的P 标号,考察6v ()()()[]67677,min w v P v T v T +=
=[]1358,14min =+ 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) 状态转移方程:1k k k x x d +=-。 (6) 阶段指标:(,)k k k v x d 见表中所示。 (7) 动态规划基本方程:
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 =-
第三步:回溯求得最优策略最有解即最优策略巍:
16
x=,*
14
d=;
2112
x x d
=-=,*
21
d=;
* 3221
x x d
=-=,*
31
d=;*
4330
x x d
=-=
返回原问题的解,即企业A投资4千万元,企业B投资1千万元,企业C 投资1千万元,最大效益为22千万元。
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题(每题2分,共20分。) 1.目标函数取极小(minZ )的线性规划问题可以转化为目标函数取极大的线性规划问题求解,原问题的目标 函数值等于( )。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是( )。 A.基本解一定是可行解 B.基本可行解的每个分量一定非负 C.若B 是基,则B 一定是可逆 D.非基变量的系数列向量一定是线性相关的 3.在线性规划模型中,没有非负约束的变量称为 ( ) 多余变量 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.非负约束 二、多项选择题(每小题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.线性规划问题的主要特征有 ( )
《管理运筹学》(第二版)课后习题参考答案 第1章 线性规划(复习思考题) 1.什么是线性规划线性规划的三要素是什么 答:线性规划(Linear Programming ,LP )是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,是一种重要的优化工具,能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.求解线性规划问题时可能出现几种结果,哪种结果说明建模时有错误 答:(1)唯一最优解:只有一个最优点; (2)多重最优解:无穷多个最优解; (3)无界解:可行域无界,目标值无限增大; (4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时,可能是建模时有错。 3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答:线性规划的标准型是:目标函数极大化,约束条件为等式,右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答:可行解:满足约束条件0≥=X b AX ,的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 它们的相互关系如右图所示:
模拟试题一 一、单项选择题:(共7题,35分) 1、在线性规划模型中,没有非负约束的变量称为(C) A. 多余变量 B. 松弛变量 C. 自由变量 D. 人工变量 2、约束条件为AX=b,X≥0的线性规划问题的可行解集是(B ) A. 补集 B. 凸集 C. 交集 D. 凹集 3、线性规划的图解法适用于( B ) A. 只含有一个变量的线性规划问题 B. 只含有2~3个变量的线性规划问题 C. 含有多个变量的线性规划问题 D. 任何情况 4、单纯形法作为一种常用解法,适合于求解线性规划(A ) A. 多变量模型 B. 两变量模型 C. 最大化模型 D. 最小化模型 5、在单纯性法计算中,如果检验数都小于等于零,而且非基变量的检验数全为负数,则表明此问题有(D )。 A. 无穷多组最优解 B. 无最优解?? C. 无可行解 D. 唯一最优解 6、在线性规划中,设约束方程的个数为m,变量个数为n,m<n时,可以把变量分为基变量和非基变量两部分,基变量的个数为m个,非基变量的个数为(C ) A. m个 B. n个 C. n-m个 D. 0个 7、使用人工变量法求解极大化线性规划问题时,当所有的检验数在基变量中仍含有非零的人工变量,表明该线性规划问题(D ) A. 有唯一的最优解 B. 有无穷多最优解 C. 为无界解 D. 无可行解 二、填空题:(共5题,25分) 1、运筹学是一门研究如何有效地组织和管理决策的科学. 2、线性规划是一种合理利用资源、合理调配资源的应用数学方法,其基本特点是模型中的目标函数和约束方程都是线性表达式. 3、线性规划模型由三个要素构成:决策变量、目标函数、约束条件。 4、可行域中任意两点间联结线段上的点均在可行域内,这样的点集叫凸集。 5、线形规划的标准形式有如下四个特点:目标函数的最大化、约束条件为等式、决策变量费非负、右端常数项非负。 三、简答题:(共3题,40分) 1、简述线性规划模型的三个基本特征。 (1)每一个问题都有一个极大或极小的目标且能用有一组线性函数表示出来。 (2)问题中有若干约束条件且可用线性等式或不等式表示。 (3)问题中用一组决策变量来表示一科方案。 2、简述单纯型法的基本思想。 (1)确定初始基可行解(2)检验是否最优,由一个基可行解变换到另一个基可行基,直至找到最优解。 3、简述如何在单纯型表上判别问题有无界解。 答:如果存在一个非基变量的检验数为正数,但此变量当前系数中无正系数存在即可证明。 模拟试题二 一、单项选择题:(共5题,30分) 1、对偶问题的对偶是(D )
运 筹 学 考 卷 1 / 51 / 5
考试时间: 第十六周 题号一二三四五六七八九十总分 评卷得分 : 名 一、单项选择题。下列每题给出的四个答案中只有一个是正确的,将表示正确 姓 答案的字母写这答题纸上。(10 分, 每小题2 分) 1、使用人工变量法求解极大化线性规划问题时,当所有的检验数j 0 ,在 线 基变量中仍含有非零的人工变量,表明该线性规划问题() A. 有唯一的最优解; B. 有无穷多个最优解; C. 无可行解; D. 为无界解 2、对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中(): 号 A.b 列元素不小于零B.检验数都大于零 学 C.检验数都不小于零D.检验数都不大于零 3、在产销平衡运输问题中,设产地为m 个,销地为n 个,那么基可行解中非 零变量的个数() 订 A. 不能大于(m+n-1); B. 不能小于(m+n-1); C. 等于(m+n-1); D. 不确定。 4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足() A. d 0 B. d 0 C. d 0 D. d 0,d 0 5、下列说法正确的为() : 业 A.如果线性规划的原问题存在可行解,则其对偶问题也一定存在可行解 专 B.如果线性规划的对偶问题无可行解,则原问题也一定无可行解 装 C.在互为对偶的一对原问题与对偶问题中,不管原问题是求极大或极小,原 问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D.如果线性规划问题原问题有无界解,那么其对偶问题必定无可行解 : 院
学 2 / 52 / 5
二、判断下列说法是否正确。正确的在括号内打“√”,错误的打“×”。(18 分,每 小题2 分) 1、如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点。() 2、单纯形法计算中,如不按最小比列原则选取换出变量,则在下一个解中至少有一 个基变量的值为负。() 3、任何线性规划问题存在并具有惟一的对偶问题。() 4、若线性规划的原问题有无穷多最优解,则其最偶问题也一定具有无穷多最优解。 ()5、运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列四种情况之 一:有惟一最优解,有无穷多最优解,无界解,无可行解。() 6、如果运输问题的单位运价表的某一行(或某一列)元素再乘上那个一个常数k , 最有调运方案将不会发生变化。() 7、目标规划模型中,应同时包含绝对约束与目标约束。() 8、线性规划问题是目标规划问题的一种特殊形式。() 9、指派问题效率矩阵的每个元素都乘上同一常数k,将不影响最优指派方案。() 三、解答题。(72 分) max z 3x 3x 1 2 1、(20分)用单纯形法求解 x x 1 2 x x 1 2 4 2 ;并对以下情况作灵敏度分析:(1)求 6x 2 x 18 1 2 x 0, x 0 1 2 5 c 的变化范围;(2)若右边常数向量变为2 b ,分析最优解的变化。 2 20 2、(15 分)已知线性规划问题: max z x 2x 3x 4x 1 2 3 4 s. t. x 2x 2x 3x 20 1 2 3 4 2x x 3x 2x 20 1 2 3 4 x x x x , , , 0 1 2 3 4 其对偶问题最优解为y1 1.2, y2 0.2 ,试根据对偶理论来求出原问题的最优解。
1 课程:管理运筹学 管理运筹学作业 第二章线性规划的图解法 P23:Q2:(1)-(6);Q3:(2) Q2:用图解法求解下列线性规划问题,并指出哪个问题具有唯一最优解,无穷多最优解,无界解或无可行解。 (1)Min f=6X1+4X2 约束条件:2X1+X2>=1, 3X1+4X2>=3 X1, X2>=0 解题如下:如图1 Min f=3.6 X1=0.2, X2=0.6 本题具有唯一最优解。 图1 (2)Max z=4X1+8X2 约束条件:2X1+2X2<=10 -X1+X2>=8 X1,X2>=0 解题如下:如图2: Max Z 无可行解。 图2 1
2 2 (3) Max z =X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下:如图3: Max Z=有无界解。 图3 (4) Max Z =3X1-2X2 约束条件:X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下:如图4: Max Z 无可行解。 图 4
3 (5)Max Z=3X1+9X2 约束条件:X1+3X2<=22 -X1+X2<=4 X2<=6 2X1-5X2<=0 X1,X2>=0 解题如下:如图5: Max Z =66;X1=4 X2=6 本题有唯一最优解。 图5 (6)Max Z=3X1+4X2 约束条件:-X1+2X2<=8 X1+2X2<=12 2X1+X2<=16 2X1-5X2<=0 X1,X2>=0 解题如下:如图6 Max Z =30.669 X1=6.667 X2=2.667 本题有唯一最优解。 3
运筹学试题 Company Document number:WTUT-WT88Y-W8BBGB-BWYTT-19998
运筹学试题 一、填空题(本大题共8小题,每空2分,共20分) 1.线性规划闯题中,如果在约束条件中出现等式约束,我们通常用增加___的方法来产生初始可行基。 2.线性规划模型有三种参数,其名称分别为价值系数、___和___。 3.原问题的第1个约束方程是“=”型,则对偶问题相应的变量是___变量。 4.求最小生成树问题,常用的方法有:避圈法和 ___。 5.排队模型M/M/2中的M,M,2分别表示到达时间为___分布,服务时间服从负指数分布和服务台数为2。 6.如果有两个以上的决策自然条件,但决策人无法估计各自然状态出现的概率,那么这种决策类型称为____型决策。 7.在风险型决策问题中,我们一般采用___来反映每个人对待风险的态度。 8.目标规划总是求目标函数的___信,且目标函数中没有线性规划中的价值系数,而是在各偏差变量前加上级别不同的____。 二、单项选择题(本大题共l0小题,每小题3分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。多选无分。 9.使用人工变量法求解极大化线性规划问题时,当所有的检验数在基变量中仍含有非零的人工变量,表明该线性规划问题【】 A.有唯一的最优解 B.有无穷多最优解 C.为无界解 D.无可行解 10.对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中【】 A.b列元素不小于零 B.检验数都大于零 C.检验数都不小于零 D.检验数都不大于零
11.已知某个含10个结点的树图,其中9个结点的次为1,1,3,1,1,1,3,1,3,则另一个结点的次为【】 A.3 B.2 C.1 D.以上三种情况均有可能 12.如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【】 13.在运输方案中出现退化现象,是指数字格的数目【】 A.等于 m+n B.等于m+n-1 C.小于m+n-1 D.大于m+n-1 14.关于矩阵对策,下列说法错误的是【】 A.矩阵对策的解可以不是唯一的 C.矩阵对策中,当局势达到均衡时,任何一方单方面改变自己的策略,都将意味着自己更少的赢得和更大的损失 D.矩阵对策的对策值,相当于进行若干次对策后,局中人I的平均赢得或局中人Ⅱ的平均损失值 【】 A.2 8.—l C.—3 D.1 16.关于线性规划的原问题和对偶问题,下列说法正确的是【】 A.若原问题为元界解,则对偶问题也为无界解
四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题(每题2分,共20分。) 1.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性规 划问题求解,原问题的目标函数值等于(C)。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 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.非负约束 y是( B )。 6. 原问题的第i个约束方程是“=”型,则对偶问题的变量i 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分) 1 / 17
习题参考答案 习题一 1.设选用第1种、第2种、第3种、第4种、第5种饲料的量分别为12345,,,,x x x x x 。 Min 543218.03.07.04.02.0x x x x x Z ++++= 1234512345 1234512345326187000.50.220.530..0.50.220.8100,,,,0 x x x x x x x x x x s t x x x x x x x x x x ++++≥??++++≥?? ++++≥??≥? 2.设x ij 为生产第i 种食品所使用的第j 种原料数,i =1,2,3分别代表甲、乙、丙,j =1,2,3分别代表A 、B 、C 。其数学模型为: Max Z =) (0.1)(5.1)(2)(95.1)(45.2)(9.2332313322212312111333231232221131211x x x x x x x x x x x x x x x x x x ++?-++?-++?-++?+++?+++? s.t . ) 3,2,1,3,2,1(,05 .06 .015 .02 .06 .012002500200033 323133 23 222123 23 222121 13 121113 13 121111 332313322212312111==≥≤++≤++≥++≤++≥++≤++≤++≤++j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ij 3.将下列线性规划问题化为标准形式 (1)引入剩余变量1s ,松弛变量2 s
四、把下列线性规划问题化成标准形式: 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小时昼夜加班工作,需要的人员数量如下表所示: 每个工作人员连续工作八小时,且在时段开始时上班,问如何安排,使得既满足以上要求,又使上班人数 最少? 五、分别用图解法和单纯形法求解下列线性规划问题.并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题: 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2,约束形式为“≤”,X 3,X 4为松驰变量.表中解代入目标函数后得Z=10 (1)求表中a ~g 的值 (2)表中给出的解是否为最优解? (1)a=2 b=0 c=0 d=1 e=4/5 f=0 g=-5 (2) 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1.minZ=2x 1+2x 2+4x 3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25
管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待 定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制, 保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式, 有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数
运筹学期末试卷(B卷) 系别:工商管理学院专业:考试日期:年月日姓名:学号:成绩: 1.[10分] 匹克公司要安排4个工人去做4项不同的工作,每个工人完成各项工作所消耗的时间(单位:分钟)如下表所示: 要求:(1)建立线性规划模型(只建模型,不求解) (2)写出基于Lindo软件的源程序。 2.[15分]某公司下属甲、乙两个厂,有A原料360斤,B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品,乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下
(1) 建立规划模型获取各厂最优生产计划。 (2) 试用图解法 求解最优结果。 3.[10分] 考虑下面的线性规划问题: 目标函数:Min Z=16x 1+16x 2 +17x 3 约束条件: 利用教材附带软件求解如下: **********************最优解如下************************* 目标函数最优值为 : 148.916 变量 最优解 相差值 ------- -------- -------- x1 7.297 0 x2 0 .703 x3 1.892 0 约束 松弛/剩余变量 对偶价格 ------- ------------- -------- 13123123123300.56153420,,0 x x x x x x x x x x x +≤-+≥+-≥≥
1 20.811 0 2 0 -3.622 3 0 -4.73 目标函数系数范围: 变量下限当前值上限 ------- -------- -------- -------- x1 1.417 16 16.565 x2 15.297 16 无上限 x3 14.4 17 192 常数项数范围: 约束下限当前值上限 ------- -------- -------- -------- 1 9.189 30 无上限 2 3.33 3 15 111.25 3 -2.5 20 90 试回答下列问题: (1)第二个约束方程的对偶价格是一个负数(为-3.622),它的含义是什么? (2)x2有相差值为0.703,它的含义是什么? (3)请对右端常数项范围的上、下限给予具体解释,应如何应用这些数
07级工管运筹学期末习题课 一、考虑线性规划问题(P )max 0 z CX AX b X ==?? ≥? (1) 若12,X X 均为(P )的可行解,[0,1]λ∈,证明12(1)X X λλ+-也是(P ) 的可行解; (2) 写出(P )的对偶模型(仍用矩阵式表示)。 二、有三个线性规划: (Ⅰ) [Min] z =CX (Ⅱ) [Min] z =CX (Ⅲ) [Min] z =CX 约束条件AX =b 约束条件AX =b 约束条件AX =b X 0 X 0 X 0 已知 X 是(Ⅰ)的最优解,X 是(Ⅱ)的最优解,X *是(Ⅲ)的最优解,Y 是(Ⅰ)的对偶问题的最优解, 试证:(1)()()'-'-≤**C C X X 0; (2) C X X Y b b ()()***-≤-。 三、已知线性规划问题 ?? ? ??=≥+=++++=++++++++=)5,,1(03.00)(max 2 253232221212 143132121115 43322111Λj x t b x x a x a x a t b x x a x a x a st x x x c x c x t c z j 当1t =2t =0时,用单纯形法求得最终表如下: 要求:1. 确定23222113121121321,,,,,,,,,,a a a a a a b b c c c 的值; 2. 当2t =0时,1t 在什么范围内变化上述最优解不变; 3. 当1t =0时,2t 在什么范围内变化上述最优基不变。 1x 2x 3x 4x 5x 3x 5/2 0 1/2 1 1/2 0 1x 5/2 1 -1/2 0 -1/6 1/3 j j z c - -4 -4 -2
《管理运筹学》期中复习题 答案 标准化文件发布号:(9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-
《管理运筹学》期中测试题 第一部分 线性规划 一、填空题 1.线性规划问题是求一个 目标函数 在一组 约束条件 下的最值问题。 2.图解法适用于含有 两个 _ 变量的线性规划问题。 3.线性规划问题的可行解是指满足 所有约束条件_ 的解。 4.在线性规划问题的基本解中,所有的非基变量等于 零 。 5.在线性规划问题中,基本可行解的非零分量所对应的列向量线性 无 关 6.若线性规划问题有最优解,则最优解一定可以在可行域的 顶点_ 达到。 7.若线性规划问题有可行解,则 一定 _ 有基本可行解。 8.如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其 可行解 的集合中进行搜索即可得到最优解。 9.满足 非负 _ 条件的基本解称为基本可行解。 10.在将线性规划问题的一般形式转化为标准形式时,引入的松驰变量在目标函数中的系数为 正 。 11.将线性规划模型化成标准形式时,“≤”的约束条件要在不等式左_端加入 松弛 _ 变量。 12.线性规划模型包括 决策变量 、目标函数 、约束条件 三个要素。 13.线性规划问题可分为目标函数求 最大 _ 值和 最小 _值两类。 14.线性规划问题的标准形式中,约束条件取 等 _ 式,目标函数求 最大 _值,而所有决策变量必须 非负 。 15.线性规划问题的基本可行解与基本解的关系是 基本可行解一定是基本解,反之不然 16.在用图解法求解线性规划问题时,如果取得最值的等值线与可行域的一段边界重合,则 _ 最优解不唯一 。 17.求解线性规划问题可能的结果有 唯一最优解,无穷多最优解,无界解,无可行解 。 18.如果某个约束条件是“ ”情形,若化为标准形式,需要引入一个 剩余 _ 变量。 19.如果某个变量X j 为自由变量,则应引进两个非负变量X j ′ , X j 〞, 同时令X j = X j ′ - X j 〞 j 。 20.表达线性规划的简式中目标函数为 线性函数 _ 。 21.线性规划一般表达式中,a ij 表示该元素位置在约束条件的 第i 个不等式的第j 个决策变量的系数 。 22.线性规划的代数解法主要利用了代数消去法的原理,实现_ 基变量 的转换,寻找最优解。 23.对于目标函数最大值型的线性规划问题,用单纯型法代数形式求解时,当非基变量检验数_ 非正 时,当前解为最优解。 24.在单纯形迭代中,选出基变量时应遵循_ 最小比值 法则。 二、单选题 1. 如果一个线性规划问题有n 个变量,m 个约束方程(m 第一章 第一章 1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。 2.(1)设立决策变量; (2)确定极值化的单一线性目标函数; (3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量; (4)非负约束。 3.(1)唯一最优解:只有一个最优点 (2)多重最优解:无穷多个最优解 (3)无界解:可行域无界,目标值无限增大 (4)没有可行解:线性规划问题的可行域是空集 无界解和没有可行解时,可能是建模时有错。 4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 5. 可行解:满足约束条件AX =b,X≥0的解,称为可行解。 基可行解:满足非负性约束的基解,称为基可行解。 可行基:对应于基可行解的基,称为可行基。 最优解:使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵,称为最优基。 6. 计算步骤: 第一步,确定初始基可行解。 第二步,最优性检验与解的判别。 第三步,进行基变换。 第四步,进行函数迭代。 判断方式: 唯一最优解:所有非基变量的检验数为负数,即σj< 0 无穷多最优解:若所有非基变量的检验数σj≤ 0 ,且存在某个非基变量xNk 的检验数σk= 0 ,让其进基,目标函数的值仍然保持原值。如果同时存在最小θ值,说明有离基变量,则该问题在两个顶点上同时达到最优,为无穷多最优解。无界解:若某个非基变量xNk 的检验数σk> 0 ,但其对应的系数列向量P k' 中,每一个元素a ik' (i=1,2,3,…,m)均非正数,即有进基变量但找不到离基变量。 管理运筹学模拟试题及 答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】 四川大学网络教育学院模拟试题( 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.图解法求解线性规划问题的主要过程有() 习题参考答案 习题一 1.设选用第1种、第2种、第3种、第4种、第5种饲料的量分别为12345,,,,x x x x x 。 Min 543218.03.07.04.02.0x x x x x Z ++++= 1234512345 1234512345326187000.50.220.530..0.50.220.8100,,,,0 x x x x x x x x x x s t x x x x x x x x x x ++++≥??++++≥?? ++++≥??≥? 2.设x ij 为生产第i 种食品所使用的第j 种原料数,i =1,2,3分别代表甲、乙、丙,j =1,2,3分别代表A 、B 、C 。其数学模型为: Max Z =) (0.1)(5.1)(2)(95.1)(45.2)(9.2332313322212312111333231232221131211x x x x x x x x x x x x x x x x x x ++?-++?-++?-++?+++?+++? s.t . ) 3,2,1,3,2,1(,05 .06 .015 .02 .06 .012002500200033 323133 23 222123 23 222121 13 121113 13 121111 332313322212312111==≥≤++≤++≥++≤++≥++≤++≤++≤++j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ij 3.将下列线性规划问题化为标准形式 (1)引入剩余变量1s ,松弛变量2s 《管理运筹学》考试试卷(A) 一、(20 分)下述线性规划问题 Max z=-5x1+5x2+13x3 ST -x1+x2+3x3 ≤ 20 ——① 12x1+4x2+10x3 ≤ 90 ——② x1,x2,x3 ≥ 0 先用单纯形法求出最优解,然后分析在下列条件下,最优解分别有什么变化? ( 1 )约束条件①的右端常数由20 变为30 ; ( 2 )约束条件②的右端常数由90 变为70 ; ( 3 )目标函数中的x3 的系数由13 变为8 ; ( 4 )增加一个约束条件③2x1+3x2+5x3 ≤ 50 ( 5 )将原有约束条件②变为10x1+5x2+10x3 ≤ 100 二、(10 分)已知线性规划问题 Max z= 2x1+x2+5x3+6x4 对偶变量 2x1 +x3+x4 ≤ 8 y1 2x1+2x2+x3+2x4 ≤ 12 y2 x1,x2,x3,x4 ≥ 0 其对偶问题的最优解为y1*=4 ,y2*=1 ,试用对偶问题的性质,求原问题的最优解。 三、(10 分)某地区有三个化肥厂,除供应外地区需要外,估计每年可供应本地区的数字为:化肥厂 A —— 7 万吨,B —— 8 万吨,C —— 3 万吨。有四个产粮区需要该种化肥,需要量为:甲地区—— 6 万吨,乙地区—— 6 万吨,丙地区—— 3 万吨,丁地区—— 3 万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示(单位:元/ 吨): 根据上述资料指定一个使总的运费最小的化肥调拨方案。 四、(10 分)需要分配5 人去做5 项工作,每人做各项工作的能力评分见下表。应如何分派,才能使总的得分最大? 五、(10 分)用动态规划方法求解: Max F=4x 1 2 -x 2 2 +2x 3 2 +12 3x 1 +2x 2 +x 3 =9 x1,x2,x3 ≥ 0 六、(10 分)公司决定使用1000 万元开发A 、B 、C 三种产品,。经预测估计开发 第2章 线性规划的图解法 1.解: x ` A 1 (1) 可行域为OABC (2) 等值线为图中虚线部分 (3) 由图可知,最优解为B 点, 最优解:1x = 712,7152=x 。最优目标函数值:769 2.解: x 2 1 0 1 (1) 由图解法可得有唯一解 6.02.021==x x ,函数值为3.6。 (2) 无可行解 (3) 无界解 (4) 无可行解 (5) 无穷多解 (6) 有唯一解 38320 21== x x ,函数值为392。 3.解: (1). 标准形式: 3212100023m ax s s s x x f ++++= 0,,,,9 2213 2330 2932121321221121≥=++=++=++s s s x x s x x s x x s x x (2). 标准形式: 21210064m in s s x x f +++= ,,,4 6710 26 3212121221121≥=-=++=--s s x x x x s x x s x x (3). 标准形式: 21''2'2'10022m in s s x x x f +++-= 0,,,,30 22350 55270 55321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x 4.解: 标准形式: 212100510m ax s s x x z +++= ,,,8259 432121221121≥=++=++s s x x s x x s x x 松弛变量(0,0) 最优解为 1x =1,x 2=3/2. 运筹学试题四 一、对约束条件(20分) ??? ?? ---++=---++=----+=-≥=x x x x x x x x x x x x x x j j 123 56346712474817223241029017,, 说明解X=(1,2,1,0,0,0,0)T 是不是基可行解,假定不是,试找出一个基可行解。 二、已知线性规划问题(20分) ??422m 321321=++-+-=x x x x x x inz 12 五、用动态规划方法求解下列问题(25分) ???? ? max ,,z x x x x x x x j j =++≥≥=349 0123122232 123 六、求解下图的中国邮路问题(20分) 一、解: (1) ??----=1001A 解出 0,01,09431=>=>=x x x 由互补松弛定理:011=?s y x 得2,0211-=+∴=y y y s ① 033=?s y x 得2,0213-=-∴=ky y y s ② ①②联立得k y k k y +-=+-= 14 *,126*21 而**,'*,12*21y y Z Z 将=-=代入③ 12*6*421-=+∴y y ③ 则2*,6*,321=-=-=y y k 综上,3-=k ,对偶问题最优解为T T y y Y )2,6(),(*21-== 三、解:(1)表上作业法求解得: 四、解:用匈牙利法求解 ??????? ? ?46255132433656395132454740274135~ ??601003111571174150203??????? ??80 1200612271090001 ∴最优方案为:肖恩 安 材料准备, 琼 记录 管理运筹学第二版课后 习题参考答案 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 列出单纯形表2019管理运筹学课后答案
管理运筹学模拟试题及答案
卫生管理运筹学第二版答案(薛迪,复旦大学出版社)
《管理运筹学》考试试卷A,B卷
《管理运筹学》课后习题答案
管理运筹学试题四(含答案)
管理运筹学第二版课后习题参考答案