运筹学计算题复习
一、第一章线性规划及单纯形法
1、下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，α为参数，
（1） 试完成该表；
（2） 若该表中所示的x 1, x 2为问题的最优基，试求α的取值范围
3≤α≤4
2、在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
Max z =2x 1+3x 2+4x 3+7x 4
⎧2x 1+3x 2-x 3-4x 4=8⎪
s . t . ⎨x 1-2x 2+6x 3-7x 4=-3 ⎪x , x , x , x ≥0⎩1234
解：在第二个约束条件两边乘以-1，变为标准形式
Max z =2x 1+3x 2+4x 3+7x 4
⎧2x 1+3x 2-x 3-4x 4=8⎪
s . t . ⎨-x 1+2x 2-6x 3+7x 4=3 ⎪x , x , x , x ≥0⎩1234
⎡2⎤⎡3⎤
x 1的系数列向量p 1=⎢⎥，x 2的系数列向量p 2=⎢⎥，x 3的系数列
⎣-1⎦⎣2⎦
⎡-1⎤⎡-4⎤
向量p 3=⎢⎥；x 4的系数列向量p 4=⎢⎥
⎣-6⎦⎣7⎦
⎧x 1=1（1） 因为P 1, P 2线性独立，令非基变量x 3, x 4=0得⎨
x =2⎩2
基本可行解X (1) =(1, 2, 0, 0), Z 1=8
T
45⎧
x =⎪⎪113⎨（2） 因为P 1, P 3线性独立，令非基变量x 2, x 4=0得
14⎪x =-
⎪13⎩
基本解X (2)
14⎫⎛45
= , 0, -, 0⎪
13⎭⎝13
T
34⎧
x =⎪⎪15
（3） 因为P 1, P 4线性独立，令非基变量x 2, x 3=0得⎨
7⎪x =4⎪5⎩
基本可行解X (3)
7⎫117⎛34
= , 0, 0, ⎪, Z =
555⎝⎭
T
45⎧
x =⎪⎪216
（4） 因为P 2, P 3线性独立，令非基变量x 1, x 4=0得⎨
7⎪x =3⎪16⎩
基本可行解X (4)
163⎛457⎫
= 0, , , 0⎪, Z =
161616⎝⎭
T
68⎧
x =⎪⎪229
（5） 因为P 2, P 4线性独立，令非基变量x 1, x 3=0得⎨
⎪x =-74⎪29⎩
基本解X (5)
7⎫⎛68
= 0, , 0, -⎪
29⎭⎝29
T
68⎧
x =-⎪⎪331
（6） 因为P 3, P 4线性独立，令非基变量x 1, x 2=0得⎨
45⎪x =-4⎪31⎩
基本解X (5)
6845⎫⎛
= 0, 0, -, -⎪
3131⎭⎝
117
为最大值，故最优解为5
T
比较最大值Z 1, Z 3, Z 4可知Z 3=
X
(3)
7⎫117⎛34
= , 0, 0, ⎪, Z =
5⎭5⎝5
T
3、分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每
一步相应于图形上哪一个顶点？
Max z =2x 1+x 2
⎧3x 1+5x 2≤15⎪
S.T.⎨6x 1+2x 2≤24
⎪x , x ≥0⎩12
解：（1）图解法，作图如下图所示，由图得唯一最优解X *=(上的点为A 2，其最优值为z *=
153T
, ) ，对应于图44
33。 4
（2） 单纯形法，引入松驰变量x 3, x 4≥0，标准型为
Max z =2x 1+x 2
⎧3x 1+5x 2+x 3=15⎪
S.T.⎨6x 1+2x 2+x 4=24
⎪x , x , x , x ≥0⎩1234
因为σj ≤0(j =1, 2, 3, 4)，故问题的最优解X *=(, , 0, 0) T ，其最优目标函数值
44
33
为z *=
4
4、建模题：某公司有资金3000万元，六年内有A 、B 、C 、D 、E 五种投资项目可供选择。其中：项目A 从第一年到第六年初均可投资，当年末可获利10%；项目B 可在第一年到四年初投资，周期为3年，到期可25%；项目C 只能在第二年初投资，周期为3年，到期可获利45%，但规定最大投资额不超过1000万元；项目D 只能在第四年初投资，周期为3年，到期可获利40%，但规定最大投资额不超800万元；项目E 只能在第五年投资，周期为2年，到期可
获利35%，但规定最大投资额不超过500万元。又项目A 、B 、C 、D 、E 的风险指数分别为0.1，0.2，0.4，0.3，0.1，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？ 解：建模题
用x ij 表示第i 年投入到 j个项目的资金，则有
1234
A x 11x 21x 31x 41B x 12x 22x 32x 42
C x 23
D E
x 44
x 55
5x 516x 61
目标函数：max
z =1. 1x 61+1. 25x 42+1. 4x 44+1. 35x 55
x 11+x 12=3000x 21+x 22+x 23=1. 1x 11x 31+x 32=1. 1x 21
x 41+x 42+x 44=1. 1x 31+1. 25x 12
s.t
x 51+x 55=1. 1x 41+1. 25x 22x 61=1. 1x 51+1. 25x 32+1. 45x 23x 23≤1000, x 44≤800x ij ≥0
x 55≤600
二、第二章线性规划的对偶理论与灵敏度分析 5、写出线性规划问题的对偶问题
Max z =6x 1-2x 2+3x 3
⎧2x 1-x 2+2x 3≤2⎪
S.T.⎨x 1+4x 3≤4
⎪x , x , x ≥0⎩123
解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变
量与对偶问题的约束条件之间的对应关系，具体见P53
⎡2-12⎤⎡2⎤
原问题中：C =(6, -2, 3), A =⎢, b =⎥⎢⎥
⎣104⎦⎣4⎦⎡2⎤
原问题的对偶问题为min ω=Yb =[y 1, y 2]⎢⎥=2y 1+4y 2
⎣4⎦
⎡2-12⎤
由C =(6, -2, 3)可知对偶问题为 YA =[y 1, y 2]⎢=[2y 1+y 2, -y 1, 2y 1+4y 2]，⎥
⎣104⎦
min ω=2y 1+4y 2
⎧2y 1+y 2≥6⎪-y ≥-2⎪1
S.T.⎨
⎪2y 1+4y 2≥3⎪⎩y 1, y 2≥0
三、第三章运输问题
6、求解下列产销平衡的运输问题
（2）由上面所得的初始方案出发，应用表上作业法求最优方案。 解：
四、第四章目标规划
7、用图解法解下面的目标规划 五、第五章整数规划
8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。
解： 1）变换系数矩阵，增加0元素。
⎡01370⎤ ⎡215134⎤-2
⎡013112⎤⎢6069⎥
⎢⎥⎢601011⎥⎢⎥1041415⎥-4⎢⎢⎥⎢0532⎥⎢9141613⎥-9⎢0574⎥⎢⎥ ⎢0100⎥⎣⎦⎢⎥⎣78119⎦-2）试指派（找独立07元素） ⎣0142⎦ -4-2 ⎡01370⎤⎢⎥ ⎢6069⎥ ⎢0532⎥ ⎢0100⎥⎣⎦
独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D 工作，乙负责B 工作，丙负责A 工作，丁负责C 工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28
六、第八章图与网络分析 9、图与网络的基本概念 10、树的基本概念
七、网络计划
11、某工地现场施工准备工作关系及持续时间如表1所示，该工程要在26天内完成，其全部直接费用为30000元，间接费用为5000元，每超过1天，间接费用增加600元。
要求：（1）先画出双代号网络图，确定关键线路
（2）将表2中的各项工作的3列空格内容计算出来，并填入表中。 （3）进行工期费用优化，求出计算工期为26天的总费用和与原计划相比节约的费用
12、根据表3给出的资料，绘制双代号网络图，找出关键路线，并简要说明如要缩短工期，应首先考虑哪些工作
3、某分部工程双代号时标网络计划如图1所示，根据该图确定各项工作的时间参数，请将结果直接填写在表4中相应位置。
图1 双代号时标网络计划
运筹学计算题复习
一、第一章线性规划及单纯形法
1、下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，α为参数，
（1） 试完成该表；
（2） 若该表中所示的x 1, x 2为问题的最优基，试求α的取值范围
3≤α≤4
2、在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
Max z =2x 1+3x 2+4x 3+7x 4
⎧2x 1+3x 2-x 3-4x 4=8⎪
s . t . ⎨x 1-2x 2+6x 3-7x 4=-3 ⎪x , x , x , x ≥0⎩1234
解：在第二个约束条件两边乘以-1，变为标准形式
Max z =2x 1+3x 2+4x 3+7x 4
⎧2x 1+3x 2-x 3-4x 4=8⎪
s . t . ⎨-x 1+2x 2-6x 3+7x 4=3 ⎪x , x , x , x ≥0⎩1234
⎡2⎤⎡3⎤
x 1的系数列向量p 1=⎢⎥，x 2的系数列向量p 2=⎢⎥，x 3的系数列
⎣-1⎦⎣2⎦
⎡-1⎤⎡-4⎤
向量p 3=⎢⎥；x 4的系数列向量p 4=⎢⎥
⎣-6⎦⎣7⎦
⎧x 1=1（1） 因为P 1, P 2线性独立，令非基变量x 3, x 4=0得⎨
x =2⎩2
基本可行解X (1) =(1, 2, 0, 0), Z 1=8
T
45⎧
x =⎪⎪113⎨（2） 因为P 1, P 3线性独立，令非基变量x 2, x 4=0得
14⎪x =-
⎪13⎩
基本解X (2)
14⎫⎛45
= , 0, -, 0⎪
13⎭⎝13
T
34⎧
x =⎪⎪15
（3） 因为P 1, P 4线性独立，令非基变量x 2, x 3=0得⎨
7⎪x =4⎪5⎩
基本可行解X (3)
7⎫117⎛34
= , 0, 0, ⎪, Z =
555⎝⎭
T
45⎧
x =⎪⎪216
（4） 因为P 2, P 3线性独立，令非基变量x 1, x 4=0得⎨
7⎪x =3⎪16⎩
基本可行解X (4)
163⎛457⎫
= 0, , , 0⎪, Z =
161616⎝⎭
T
68⎧
x =⎪⎪229
（5） 因为P 2, P 4线性独立，令非基变量x 1, x 3=0得⎨
⎪x =-74⎪29⎩
基本解X (5)
7⎫⎛68
= 0, , 0, -⎪
29⎭⎝29
T
68⎧
x =-⎪⎪331
（6） 因为P 3, P 4线性独立，令非基变量x 1, x 2=0得⎨
45⎪x =-4⎪31⎩
基本解X (5)
6845⎫⎛
= 0, 0, -, -⎪
3131⎭⎝
117
为最大值，故最优解为5
T
比较最大值Z 1, Z 3, Z 4可知Z 3=
X
(3)
7⎫117⎛34
= , 0, 0, ⎪, Z =
5⎭5⎝5
T
3、分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每
一步相应于图形上哪一个顶点？
Max z =2x 1+x 2
⎧3x 1+5x 2≤15⎪
S.T.⎨6x 1+2x 2≤24
⎪x , x ≥0⎩12
解：（1）图解法，作图如下图所示，由图得唯一最优解X *=(上的点为A 2，其最优值为z *=
153T
, ) ，对应于图44
33。 4
（2） 单纯形法，引入松驰变量x 3, x 4≥0，标准型为
Max z =2x 1+x 2
⎧3x 1+5x 2+x 3=15⎪
S.T.⎨6x 1+2x 2+x 4=24
⎪x , x , x , x ≥0⎩1234
因为σj ≤0(j =1, 2, 3, 4)，故问题的最优解X *=(, , 0, 0) T ，其最优目标函数值
44
33
为z *=
4
4、建模题：某公司有资金3000万元，六年内有A 、B 、C 、D 、E 五种投资项目可供选择。其中：项目A 从第一年到第六年初均可投资，当年末可获利10%；项目B 可在第一年到四年初投资，周期为3年，到期可25%；项目C 只能在第二年初投资，周期为3年，到期可获利45%，但规定最大投资额不超过1000万元；项目D 只能在第四年初投资，周期为3年，到期可获利40%，但规定最大投资额不超800万元；项目E 只能在第五年投资，周期为2年，到期可
获利35%，但规定最大投资额不超过500万元。又项目A 、B 、C 、D 、E 的风险指数分别为0.1，0.2，0.4，0.3，0.1，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？ 解：建模题
用x ij 表示第i 年投入到 j个项目的资金，则有
1234
A x 11x 21x 31x 41B x 12x 22x 32x 42
C x 23
D E
x 44
x 55
5x 516x 61
目标函数：max
z =1. 1x 61+1. 25x 42+1. 4x 44+1. 35x 55
x 11+x 12=3000x 21+x 22+x 23=1. 1x 11x 31+x 32=1. 1x 21
x 41+x 42+x 44=1. 1x 31+1. 25x 12
s.t
x 51+x 55=1. 1x 41+1. 25x 22x 61=1. 1x 51+1. 25x 32+1. 45x 23x 23≤1000, x 44≤800x ij ≥0
x 55≤600
二、第二章线性规划的对偶理论与灵敏度分析 5、写出线性规划问题的对偶问题
Max z =6x 1-2x 2+3x 3
⎧2x 1-x 2+2x 3≤2⎪
S.T.⎨x 1+4x 3≤4
⎪x , x , x ≥0⎩123
解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变
量与对偶问题的约束条件之间的对应关系，具体见P53
⎡2-12⎤⎡2⎤
原问题中：C =(6, -2, 3), A =⎢, b =⎥⎢⎥
⎣104⎦⎣4⎦⎡2⎤
原问题的对偶问题为min ω=Yb =[y 1, y 2]⎢⎥=2y 1+4y 2
⎣4⎦
⎡2-12⎤
由C =(6, -2, 3)可知对偶问题为 YA =[y 1, y 2]⎢=[2y 1+y 2, -y 1, 2y 1+4y 2]，⎥
⎣104⎦
min ω=2y 1+4y 2
⎧2y 1+y 2≥6⎪-y ≥-2⎪1
S.T.⎨
⎪2y 1+4y 2≥3⎪⎩y 1, y 2≥0
三、第三章运输问题
6、求解下列产销平衡的运输问题
（2）由上面所得的初始方案出发，应用表上作业法求最优方案。 解：
四、第四章目标规划
7、用图解法解下面的目标规划 五、第五章整数规划
8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。
解： 1）变换系数矩阵，增加0元素。
⎡01370⎤ ⎡215134⎤-2
⎡013112⎤⎢6069⎥
⎢⎥⎢601011⎥⎢⎥1041415⎥-4⎢⎢⎥⎢0532⎥⎢9141613⎥-9⎢0574⎥⎢⎥ ⎢0100⎥⎣⎦⎢⎥⎣78119⎦-2）试指派（找独立07元素） ⎣0142⎦ -4-2 ⎡01370⎤⎢⎥ ⎢6069⎥ ⎢0532⎥ ⎢0100⎥⎣⎦
独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D 工作，乙负责B 工作，丙负责A 工作，丁负责C 工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28
六、第八章图与网络分析 9、图与网络的基本概念 10、树的基本概念
七、网络计划
11、某工地现场施工准备工作关系及持续时间如表1所示，该工程要在26天内完成，其全部直接费用为30000元，间接费用为5000元，每超过1天，间接费用增加600元。
要求：（1）先画出双代号网络图，确定关键线路
（2）将表2中的各项工作的3列空格内容计算出来，并填入表中。 （3）进行工期费用优化，求出计算工期为26天的总费用和与原计划相比节约的费用
12、根据表3给出的资料，绘制双代号网络图，找出关键路线，并简要说明如要缩短工期，应首先考虑哪些工作
3、某分部工程双代号时标网络计划如图1所示，根据该图确定各项工作的时间参数，请将结果直接填写在表4中相应位置。
图1 双代号时标网络计划