运筹学计算题复习

运筹学计算题复习

一、第一章线性规划及单纯形法

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

（2）

45⎧

x =⎪⎪113⎨因为P 1, P 3线性独立，令非基变量x 2, x 4=0得

⎪x =-14⎪13⎩

(2)

基本解X

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⎭⎝

T

比较最大值Z 1, Z 3, Z 4可知Z 3=

117

为最大值，故最优解为5

X (3)

7⎫117⎛34

= , 0, 0, ⎪, Z =

555⎝⎭

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 =(

*

153T

, ) ，对应于图上的点为44

A 2，其最优值为z *=

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

z *=

33 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个项目的资金，则有

A 1

x 112x 213x 314x 415x 516x 61

B x 12x 22x 32x 42

C x 23

D E

x 44

x 55

目标函数：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

原问题中：C =(6, -2, 3), A =⎢

⎡2-12⎤

, b =⎥

⎣104⎦

⎡2⎤⎣4⎦

⎡2⎤⎢4⎥ ⎣⎦

原问题的对偶问题为min ω=Yb =[y 1, y 2]⎢⎥=2y 1+4y 2

⎡2-12⎤

YA =[y 1, y 2]⎢=[2y 1+y 2, -y 1, 2y 1+4y 2]，由C =(6, -2, 3)可知对偶问题为 ⎥

⎣104⎦

min ω=2y 1+4y 2

⎧2y 1+y 2≥6⎪-y ≥-2⎪1

S.T.⎨

2y +4y ≥32⎪1⎪⎩y 1, y 2≥0

三、第三章运输问题

6、求解下列产销平衡的运输问题 单位价格表

（1）用西北角法、最小元素法求初始基本可行解；

（2）由上面所得的初始方案出发，应用表上作业法求最优方案。 解：

四、第四章目标规划

7、用图解法解下面的目标规划 五、第五章整数规划

8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。

解： 1）变换系数矩阵，增加0元素。

⎡01370⎤

⎡215134⎤-2⎢6069⎥⎡013112⎤ ⎢⎥⎢⎥⎢601011⎥1041415⎥-4⎢ ⎢0532⎥⎢⎥⎢9141613⎥-9⎢⎥⎢0574⎥ ⎢0100⎥⎣⎦⎢⎥-7 ⎣781190⎦元素）2）试指派（找独立0142⎣⎦ -4-2 ⎡01370⎤⎢⎥ ⎢6069⎥ ⎢0532⎥ ⎢0100⎥⎣⎦

独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D 工作，乙负责B 工作，丙负责A 工作，丁负责C 工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28

六、第八章图与网络分析

9、书上P239例7（破圈法和避圈法） 10、最大流（标号法）书上250页例13

七、网络计划

11、某工地现场施工准备工作关系及持续时间如表1所示，该工程要在26天内完成，其全部直接费用为30000元，间接费用为5000元，每超过1天，间接费用增加600元。

表1工作清单

要求：（1）先画出双代号网络图，确定关键线路

（2）将表2中的各项工作的3列空格内容计算出来，并填入表中。

（3）进行工期费用优化，求出计算工期为26天的总费用和与原计划相比节约的费用

12、根据表3给出的资料，绘制双代号网络图，找出关键路线，并简要说明如要缩短工期，应首先考虑哪些工作

3、某分部工程双代号时标网络计划如图1所示，根据该图确定各项工作的时间参数，请将结果直接填写在表4中相应位置。

图1 双代号时标网络计划

表4工作时间参数