四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A )
《管理运筹学》
一、 单选题（每题２分，共20分。）
1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规划问题求解，原问题的目标
函数值等于（ ）。
A. maxZ
B. max(-Z)
C. –max(-Z)
D.-maxZ 2. 下列说法中正确的是（ ）。
Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负
Ｃ．若B 是基，则B 一定是可逆 Ｄ．非基变量的系数列向量一定是线性相关的
3．在线性规划模型中，没有非负约束的变量称为 （ ）
多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ ）。
Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验
但不完全满足 （ ）。
A ．等式约束
B ．“≤”型约束
C ．“≥”约束
D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y
是（ ）。
Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量
7.在运输方案中出现退化现象，是指数字格的数目( )。
A.等于m+n
B.大于m+n-1
C.小于m+n-1
D.等于m+n-1
8. 树Ｔ的任意两个顶点间恰好有一条（ ）。
Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的 （ ）。
A ．最小流
B ．最大流
C ．最小费用流
D ．无法确定
10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ ）
Ａ．等式约束 Ｂ．“≤”型约束 Ｃ．“≥”型约束 Ｄ．非负约束
二、多项选择题（每小题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
2
222330()9()max x s f s x f s ≤≤=+
{}
2222
3092max 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 = 当29/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 =-=-= ，与29/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
一、单选题（每题２分，共20分。）
1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规划问题求解，原问题的目标
函数值等于（ ）。
A. maxZ
B. max(-Z)
C. –max(-Z)
D.-maxZ 2. 下列说法中正确的是（ ）。
Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负
Ｃ．若B 是基，则B 一定是可逆 Ｄ．非基变量的系数列向量一定是线性相关
的
3．在线性规划模型中，没有非负约束的变量称为（ ）
A ．多余变量
B ．松弛变量
C ．人工变量
D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ ）。 Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解
5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ ）。
A ．等式约束
B ．“≤”型约束
C ．“≥”约束
D ．非负约束
6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y
是（ ）。 Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量 7. 在运输方案中出现退化现象，是指数字格的数目( )。
A.等于m+n
B.大于m+n-1
C.小于m+n-1
D.等于m+n-1
8. 树Ｔ的任意两个顶点间恰好有一条（ ）。
Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的（ ）。
A ．最小流
B ．最大流
C ．最小费用流
D ．无法确定
10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ ）
Ａ．等式约束 Ｂ．“≤”型约束 Ｃ．“≥”型约束 Ｄ．非负约束
二、判断题题（每小题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千万元。
《管理运筹学》复习题2014.12 一、填空题(每题3分，共18分) 1．运筹学中所使用的模型是数学模型。用运筹学解决问题的核心是建立数学模型，并对模型求解。 2.数学模型中，“s ·t ”表示约束。 3．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。 4．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 5．图解法适用于含有两个变量的线性规划问题。 6．线性规划问题的可行解是指满足所有约束条件的解。 7．在线性规划问题的基本解中，所有的非基变量等于零。 8．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。 11．线性规划问题可分为目标函数求极大值和极小_值两类。 12．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。 13．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 14.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。 15.物资调运问题中，有m 个供应地，A l ，A 2…，A m ，A j 的供应量为a i (i=1，2…，m)，n 个需求地B 1，B 2，…B n ，B 的需求量为b j (j=1，2，…，n)，则供需平衡条件为 ∑=m i i a 1= ∑=n j i b 1 16．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。 17．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n －1个(设问题中含有m 个供应地和n 个需求地) 18、供大于求的、供不应求的不平衡运输问题，分别是指∑=m i i a 1_＞∑=n j i b 1的运输问题、∑=m i i a 1_＜∑=n j i b 1的运输问题。 19．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。 20.运输问题的模型中，含有的方程个数为n+m 个 21．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。 22．在分枝定界法中，若选X r =4／3进行分支，则构造的约束条件应为X 1≤1，X 1≥2。 23．在0 - 1整数规划中变量的取值可能是_0或1。 24．分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 25.分枝定界法一般每次分枝数量为2个. 26．图的最基本要素是点、点与点之间构成的边 27．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 28．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 29．在图论中，图是反映研究对象_之间_特定关系的一种工具。 30．任一树中的边数必定是它的点数减1。 二、选择题（每题3分，共18分） 1．我们可以通过（ C ）来验证模型最优解。 A ．观察 B ．应用 C ．实验 D ．调查 2．建立运筹学模型的过程不包括（ A ）阶段。 A ．观察环境 B ．数据分析 C ．模型设计 D ．模型实施 3.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。这个过程是一个（C ） A 解决问题过程 B 分析问题过程 C 科学决策过程 D 前期预策过程 4.从趋势上看，运筹学的进一步发展依赖于一些外部条件及手段，其中最主要的是（ C ） A 数理统计 B 概率论 C 计算机 D 管理科学
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：
《管理运筹学》第四版课后习题解析（上） 第2章 线性规划的图解法 1．解： （1）可行域为OABC 。 （2）等值线为图中虚线部分。 （3）由图2-1可知，最优解为B 点，最优解1x = 127，2157x =；最优目标函数值697 。 图2-1 2．解： （1）如图2-2所示，由图解法可知有唯一解12 0.2 0.6x x =??=?，函数值为3.6。 图2-2 （2）无可行解。 （3）无界解。 （4）无可行解。 （5）无穷多解。
（6）有唯一解 12203 8 3x x ?=????=?? ，函数值为923。 3．解： （1）标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ （2）标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ （3）标准形式 1 2212min 2200f x x x s s ''''=-+++ 12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4．解： 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量（0，0） 最优解为 1x =1，x 2=3/2。 5．解：
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题（每题２分，共20分。） 1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规 划问题求解，原问题的目标函数值等于（ C ）。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是（ B ）。 Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负 Ｃ．若B 是基，则B 一定是可逆Ｄ．非基变量的系数列向量一定是线性相关的 3．在线性规划模型中，没有非负约束的变量称为 （ D ） 多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ A ）。 Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ D ）。 A ．等式约束 B ．“≤”型约束 C ．“≥”约束 D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y 是（ B ）。 Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量 7.在运输方案中出现退化现象，是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树Ｔ的任意两个顶点间恰好有一条（ B ）。 Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的 （ B ）。 A ．最小流 B ．最大流 C ．最小费用流 D ．无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ 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分)
关键路线为：H-B-G-A- Du3-F-K，总工期为20
关键路线为：a-f-i-n-o-q，总工期为152
2 直接费用为20＋30＋15＋5＋18＋40＋10＋15＝153百元，间接费用为5×15＝75百元，总费用为153＋75＝228百元 方案II：G工时缩短1天，总工期14天 直接费用为153＋3×1＝156百元，间接费用为5×14＝70百元，总费用为156＋70＝226百元 关键路线为：B-Du2-G-H、A-F-Du1-H和B-C 最低成本日程为226百元，总工期14天。
直接费用为100＋200＋80＋0＋150＋250＋120＋100＋180＋130＝1310元，间接费用为15×27＝405元，总费用为1310＋405＝1715元 方案II：1－2工序工时缩短2天，总工期25天 直接费用为1310＋10×2＝1330元，间接费用为15×（27－2）＝375元， 总费用为1330＋375＝1705元 关键路线为：关键路线为：1－2－3－4－6－8 方案III：2－3工序工时缩短4天，总工期21天 直接费用为1330＋20×4＝1410元，间接费用为15×（25－4）＝315元， 总费用为1410＋315＝1725元 最低成本日程为1705元，总工期25天。
9.5解：网络图如下： 方案Ⅰ：按正常工时工作，总工期19天，关键路线为：B-E-F 方案Ⅱ：E工时缩短2天，总工期17天，变化费用＝30－50×2＝－70； 关键路线为：B-E-F和C-F 方案Ⅲ：C工时缩短1天，E工时缩短1天，总工期16天，变化费用＝－70＋30＋15－50×1＝－75； 关键路线为：A-D-F、B-E-F和C-F 方案Ⅳ：F工时缩短1天，总工期15天，变化费用＝－75＋40－50＝－85； 关键路线为：A-D-F、B-E-F和C-F 方案Ⅴ：B工时缩短3天，C工时缩短3天，D工时缩短2天，A工时缩短1天，总工期12天，变化费用＝－85＋25×3＋30×3＋10×2＋20×1－50×3＝－30； 关键路线为：A-D-F、B-E-F和C-F 所以正常计划工期是19天，最少工期是12天，最佳工期是15天，各项工作的相应工时如上表方案Ⅳ所示。
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
11.1解： 4=λ人/小时，10660==μ人/小时，4.010 4===μλρ，属于M/M/1排队模型。 （1）仓库管理员空闲的概率，即为6.04.0110=-=-=ρP （2）仓库内有4个工人的概率即为()()01536.04.04.011444=?-=-=ρρP （3）至少有2个工人的概率为16.024.06.01110=--=--P P （4）领工具的工人平均数人6667.06 44104==-=-=λμλ s L （5）排队等待领工具工人的平均数人2667.06 6.141044.0==-?=-=λμρλq L （6）平均排队时间分钟小时4066 7.06 4.04104.0===-=-= λμρq W （7）待定 11.2解： 32060==λ人/小时，41560==μ人/小时，75.04 3===μλρ，属于M/M/1排队模型。
（1）不必等待概率，即为25.075.0110=-=-=ρP （2）不少于3个顾客排队等待的概率，即系统中有大于等于4个（或大于3个）顾客的概率，为 3164.01055.01406.01875.025.0113210=----=----P P P P （3）顾客平均数人31 3343==-=-=λμλ s L （4）平均逗留时间小时13 411=-=-=λμs W （5）λ λμ-=-=<4115.1s W 小时，即小时人/333.3>λ。平均到达率超过3.333人时，店主才会考虑增加设备或理发员。 11.3解：
4=λ人/小时，10660==μ人/小时，4.010 4===μλρ，属于M/M/1/3排队模型。 （1）仓库内没有人领工具的概率，即为6158.04 .014.0111410=--=--=+N P ρρ （2）工人到达必须排队等待的概率，即为仓库内有1个、2个和3个工人的概率和 ()() 3842.04.014.014.04.04.011432132321=--?++=--++=+++N P P P ρρρρρ （3）新到工人离去的概率为0394.04 .014.014.01143133=--?=--=+N P ρρρ （4）领工具的工人平均数()=-?--=-+--=++44114 .014.044.014.0111N N s N L ρρρρ （5）排队等待领工具工人的平均数人2667.06 6.141044.0==-?=-=λμρλq L （6）平均排队时间分钟小时4066 7.064.04104.0===-=-= λμρq W
习题参考答案 习题一 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
《管理运筹学》第四版课后习题解析（下） 第9章 目 标 规 划 1、解： 设工厂生产A 产品1x 件，生产B 产品2x 件。按照生产要求，建立如下目标规划模型。 112212121211122212min ()() s.t 43452530 555086100 ,,,0,1,2 -- +-+-+-++++-+=+-+==i i P d P d x x x x x x d d x x d d x x d d i ≤≤≥ 由管理运筹学软件求解得 12121211.25,0,0,10, 6.25,0x x d d d d --++ ====== 由图解法或进一步计算可知，本题在求解结果未要求整数解的情况下，满意解有无穷多个，为线段(135/14,15/7)(1)(45/4,0),[0,1]ααα+-∈上的任一点。 2、解： 设该公司生产A 型混凝土x 1吨，生产B 型混凝土x 2吨，按照要求建立如下的目标规划模型。 ) 5,,2,1(0,,0,0145 50.060.015550.040.030000100150100 120275200.)()(min 2121215521442331222111215443 32 211 1 =≥≥≥≤+≤+=-++=-+=-+=-++=-++++++++-+-+-+-+-+-- - - + +- i d d x x x x x x d d x x d d x d d x d d x x d d x x t s d p d d p d p d d p i i 由 管 理 运 筹 学 软 件 求 解 得 . 0,0,20,0,0,0, 0,35,40,0,120,120554433221121============+-+-+-+-+-d d d d d d d d d d x x
管理运筹学 ——管理科学方法谢家平 第一章 第一章 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 ，让其进基，目标函数
第一章 思考题、主要概念及内容 1、了解运筹学的分支，运筹学产生的背景、研究的内容和意义。 2、了解运筹学在工商管理中的应用。 3、体会管理运筹学使用相应的计算机软件，注重学以致用的原则。 第二章 思考题、主要概念及内容 图解法、图解法的灵敏度分析 复习题 1. 考虑下面的线性规划问题： max z=2x1+3x2； 约束条件： x1+2x2≤6， 5x1+3x2≤15， x1，x2≥0． (1) 画出其可行域． (2) 当z=6时，画出等值线2x1+3x2=6． (3) 用图解法求出其最优解以及最优目标函数值． 2. 用图解法求解下列线性规划问题，并指出哪个问题具有惟一最优解、无穷多最优解、无界解或无可行解． (1) min f=6x1+4x2； 约束条件： 2x1+x2≥1， 3x1+4x2≥3， x1，x2≥0． (2) max z=4x1+8x2； 约束条件： 2x1+2x2≤10， -x1+x2≥8， x1,x2≥0． (3) max z=3x1-2x2； 约束条件： x1+x2≤1， 2x1+2x2≥4， x1，x2≥0． (4) max z=3x1+9x2； 约束条件：
-x1+x2≤4， x2≤6， 2x1-5x2≤0， x1，x2≥0 3. 将下述线性规划问题化成标准形式： (1) max f=3x1+2x2； 约束条件： 9x1+2x2≤30， 3x1+2x2≤13， 2x1+2x2≤9， x1，x2≥0． (2) min f=4x1+6x2； 约束条件： 3x1-x2≥6， x1+2x2≤10， 7x1-6x2=4， x1，x2≥0． (3) min f=-x1-2x2； 约束条件： 3x1+5x2≤70, -2x1-5x2=50， -3x1+2x2≥30， x1≤0，-∞≤x2≤∞． (提示：可以令x′1=-x1，这样可得x′1≥0．同样可以令x′2-x″2=x2，其中x′2，x″2≥0．可见当x′2≥x″2时，x2≥0；当x′2≤x″2时，x2≤0，即-∞≤x2≤∞．这样原线性规划问题可以化为含有决策变量x′1，x′2，x″2的线性规划问题，这里决策变量x′1，x′2，x″2≥0．) 4. 考虑下面的线性规划问题： min f=11x1+8x2； 约束条件： 10x1+2x2≥20， 3x1+3x2≥18， 4x1+9x2≥36， x1，x2≥0． (1) 用图解法求解． (2) 写出此线性规划问题的标准形式． (3) 求出此线性规划问题的三个剩余变量的值． 5. 考虑下面的线性规划问题： max f=2x1+3x2； 约束条件： x1+x2≤10， 2x1+x2≥4，
《运筹学》模拟试题及参考答案 一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。) 1. 图解法提供了求解线性规划问题的通用方法。( ) 2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j ≥0，则问题达到最优。( ) 3. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。( ) 4. 满足线性规划问题所有约束条件的解称为基本可行解。( ) 5. 在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。( ) 6. 对偶问题的目标函数总是与原问题目标函数相等。( ) 7. 原问题与对偶问题是一一对应的。( ) 8. 运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。( ) 9. 指派问题的解中基变量的个数为m＋n。( ) 10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。( ) 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。( ) 12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。( ) 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。( ) 14. 单目标决策时，用不同方法确定的最佳方案往往是一致的。( ) 15. 动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ( ) 三、填空题 1. 图的组成要素；。 2. 求最小树的方法有、。 3. 线性规划解的情形有、、、。 4. 求解指派问题的方法是。 5. 按决策环境分类，将决策问题分为、、。 6. 树连通，但不存在。 1
《管理运筹学》第四版课后习题解析（上） 第2章 线性规划的图解法 1．解： （1）可行域为OABC 。 （2）等值线为图中虚线部分。 （3）由图2-1可知，最优解为B 点，最优解1x = 127，2157x =；最优目标函数值69 7 。 图2-1 2．解： （1）如图2-2所示，由图解法可知有唯一解12 0.2 0.6x x =??=?，函数值为3.6。
图2-2 （2）无可行解。 （3）无界解。 （4）无可行解。 （5）无穷多解。 （6）有唯一解 12203 8 3x x ?=????=?? ，函数值为923。 3．解： （1）标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ （2）标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ （3）标准形式 1 2212min 2200f x x x s s ''''=-+++
12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4．解： 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量（0，0） 最优解为 1x =1，x 2=3/2。 5．解： 标准形式 12123min 118000f x x s s s =++++ 121122123121231022033184936,,,,0 x x s x x s x x s x x s s s +-=+-=+-=≥ 剩余变量（0, 0, 13） 最优解为 x 1=1，x 2=5。 6．解： （1）最优解为 x 1=3，x 2=7。
管理运筹学试题（A） 一．单项选择（将唯一正确答案前面的字母填入题后的括号里。正确得1分，选错、多选或不选得0分。共15分） 1．在线性规划模型中，没有非负约束的变量称为（） A．多余变量B．松弛变量C．自由变量D．人工变量 正确答案：A: B: C: D: 2．约束条件为AX=b，X≥0的线性规划问题的可行解集是（）A．补集B．凸集C．交集D．凹集 正确答案：A: B: C: D: 3．线性规划问题若有最优解，则一定可以在可行域的（）上达到。A．内点B．外点C．极点D．几何点 正确答案：A: B: C: D: 4．对偶问题的对偶是（） A．基本问题B．解的问题C．其它问题D．原问题 正确答案：A: B: C: D: 5．若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的（） A．值B．个数C．机会费用D．检验数 正确答案：A: B: C: D: 6．若运输问题已求得最优解，此时所求出的检验数一定是全部（）A．大于或等于零B．大于零C．小于零D．小于或等于零 正确答案：A: B: C: D: 7．设V是一个有n个顶点的非空集合，V={v1，v2，……，vn}，E是一个有m条边的集合，E={e1，e2，……em}，E中任意一条边e是V 的一个无序元素对[u，v]，（u≠v），则称V和E这两个集合组成了一个（） A．有向树B．有向图C．完备图D．无向图 正确答案：A: B: C: D: 8．若开链Q中顶点都不相同，则称Q为（）
A．基本链B．初等链C．简单链D．饱和链 正确答案：A: B: C: D: 9．若图G 中没有平行边，则称图G为（） A．简单图B．完备图C．基本图D．欧拉图 正确答案：A: B: C: D: 10．在统筹图中，关键工序的总时差一定（） A．大于零B．小于零C．等于零D．无法确定 正确答案：A: B: C: D: 11．若Q为f饱和链，则链中至少有一条后向边为f （） A．正边B．零边C．邻边D．对边 正确答案：A: B: C: D: 12．若f 是G的一个流，K为G的一个割，且Valf=CapK，则K一定是（） A．最小割B．最大割C．最小流D．最大流 正确答案：A: B: C: D: 13．对max型整数规划，若最优非整数解对应的目标函数值为Zc，最优整数解对应的目标值为Zd，那么一定有( ) A．Zc ∈Zd B．Zc =Zd C．Zc ≤Zd D．Zc ≥Zd 正确答案：A: B: C: D: 14．若原问题中xI为自由变量，那么对偶问题中的第i个约束一定为（）A．等式约束B．“≤”型约束C．“≥”约束D．无法确定 正确答案：A: B: C: D: 15．若f*为满足下列条件的流：Valf*=max{Valf |f为G的一个流}，则称f*为G的（） A．最小值B．最大值C．最大流D．最小流 正确答案：A: B: C: D:
《管理运筹学》第四版课后习题解析 第5章单纯形法 1．解： 表中a 、c 、e 、f 是可行解，f 是基本解，f 是基本可行解。 2．解： （1）该线性规划的标准型如下。 max 5x 1＋9x 2＋0s 1+0s 2+0s 3 s.t. 0.5x 1＋x 2＋s 1＝8 x 1＋x 2－s 2＝10 0.25x 1＋0.5x 2－s 3＝6 x 1，x 2，s 1，s 2，s 3≥0 （2）至少有两个变量的值取零，因为有三个基变量、两个非基变量，非基变量取零。 （3）（4，6，0，0，-2）T （4）（0，10，-2，0，-1）T （5）不是。因为基本可行解要求基变量的值全部非负。 （6）略 3.解： 令33 3x x x ''-'=，z f -=改为求f max ；将约束条件中的第一个方程左右两边同时乘以-1，并在第二和第三个方程中分别引入松弛变量5x 和剩余变量6x ，将原线性规划问题化为如下标准型： j x '、j x ''不可能在基变量中同时出现，因为单纯性表里面j x '、j x ''相应的列向 量是相同的，只有符号想法而已，这时候选取基向量的时候，同时包含两列会使 选取的基矩阵各列线性相关，不满足条件。 4．解： （1） 表5-1 0,,,,,, 24423 1863 1334 7234max 65433 21633 21543321433 214 321≥'''=-''+'--=++''+'-+-=+''+'---++-=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 f 约束条件：
第一章 第一章 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)均非正数，即有进基变量但找不到离基变量。
习题参考答案 习题一 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
第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.
管理运筹学模拟试题及 答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
四川大学网络教育学院模拟试题( A ) 《管理运筹学》 一、单选题（每题２分，共20分。） 1．目标函数取极小（minZ）的线性规划问题可以转化为目标函数取极大的线性 规划问题求解，原问题的目标函数值等于（C）。 A. maxZ B. max(-Z) C. –max(-Z) 2.下列说法中正确的是（B）。 Ａ．基本解一定是可行解Ｂ．基本可行解的每个分量 一定非负 Ｃ．若B是基，则B一定是可逆Ｄ．非基变量的系数列向量一定是 线性相关的 3．在线性规划模型中，没有非负约束的变量称为（ D ） 多余变量 B．松弛变量 C．人工变量 D．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时， 可求得（A）。 Ａ．多重解Ｂ．无解Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足（ D ）。 A．等式约束 B．“≤”型约束 C．“≥”约束 D．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y是 （B）。 Ａ．多余变量Ｂ．自由变量Ｃ．松弛变量Ｄ．非 负变量 7.在运输方案中出现退化现象，是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8.树Ｔ的任意两个顶点间恰好有一条（B）。 Ａ．边Ｂ．初等链Ｃ．欧拉圈 Ｄ．回路 9．若G中不存在流f增流链，则f为G的（ B ）。 A．最小流 B．最大流 C．最小费用流 D．无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满 足最优检验但不完全满足（D） Ａ．等式约束Ｂ．“≤”型约束Ｃ．“≥”型约束 Ｄ．非负约束 二、多项选择题（每小题4分，共20分） 1．化一般规划模型为标准型时，可能引入的变量有（） A．松弛变量 B．剩余变量 C．非负变量 D．非正变量E．自由变量 2．图解法求解线性规划问题的主要过程有（）
第二章补充作业习题： 用大M 法和两阶段法求解下面LP 问题： ?????? ?≥≥+-≥-+= 0, 3 232s.t.42min 212 12121x x x x x x x x z 解： 标准化为 ?????? ?≥=-+-=----=0,,, 3 232s.t.42max 43214 2 132121x x x x x x x x x x x x z （1）大M 法 引入人工变量65,x x ，得到下面的LP 问题 ?????? ?=≥=+-+-=+------=6,,1,0 3 2 32s.t.42max 6 4 2 15 3216521 j x x x x x x x x x Mx Mx x x z j 因为人工变量6x 为4>0，所以原问题没有可行解。
（2）两阶段法： 增加人工变量65,x x ，得到辅助LP 问题 ?????? ?=≥=+-+-=+----=6,,1,0 3 232s.t.max 6 4 2 15 32165 j x x x x x x x x x x x g j 初始表 因为辅助LP 问题的最优值为4>0，所以原问题没有可行解。 习2.1 解： 设1x 为每天生产甲产品的数量，2x 为每天生产乙产品的数量，则数学模型为
,518 320 2..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z 最优解为：()T X 4.8,2.3*=，最优值为：z = 2640。
（1） 最优解为：()T X 5.0,5.1*=，最优值为：z = 4.5。 （2） 无可行解