工程技术大学运筹学 - 张伯生 - 2011～2012学年第一学期考试试卷

一、辨析题（本题共5小题，每小题3分，共15分）

1、线性规划模型中，设系数矩阵A＝(aij)3?6，则X＝（0，0，2，3，4，0）T有无可能是A的基可行解？ 有可能（1分）。基可行解中非零值的个数不超过m，（题中m＝3），给定解中X有3个非零值分量。（2分）

2、m个发点和n个收点的运输问题中，有m+n个相互独立的约束条件。 错（1分）。相互独立的约束条件有m+n-1（2分）。 3、一个赋权图的最小生成树是否唯一？为什么？

不是唯一的。（1分）因为可以该赋权图中边的所赋权可能是相同的，在这种情况下得到的最小生成树可能就不唯一的。（2分） 4、用单纯形法求解极大化问题的线性规划问题时，?J?0与对应的变量都可以被选为换入变量吗？为什么？ 答：可以。（1分）因为检验数大于零，把xj作为换入变量，仍然可以改进目标函数值。（2分）

5、已知网络上某条链如下图，问：x为何值时，该链是增流链，为什么？

答：x＝0（1分）。此时后向边不为零边，不符合增流链定义（2分）。

二、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15分） （1）写出问题的数学模型 （2）求获最大利润的方案。

甲 乙 设备能力 设备A 设备B 设备C 3 2 0 2 1 3 2500 65 40 75 vs(3,1)v1(1,x)v3(4,2)vt利润（元/件） 1500

解：设甲、乙产品分别生产x1,x2件，线性规划模型为

maxZ?1500x1?2500x2?3x1?2x2?65?2x1?x2?40?s.t.??3x2?75??x1,x2?0

利用单纯形法进行求解为 2500 x2 2 1 (3) 2500 0 0 1 0 0 0 1 1 0 0 0 1/3 -2/3 0 0 -500 0 1 0 0 0 x3 1 0 0 0 0 1 0 0 0 x4 0 1 0 0 0 x5 0 0 1 0 -2/3 -1/3 1/3 -833.3 -0.2222 5 0.1111 1/4 -500 5 25 b 65 40 75 0 15 15 25 8 CB 0 0 0 0 0 2500 1500 0 2500 Cj xB x3 x4 x5 r x3 X4 X2 r X1 X4 x2 r 1500 x1 3 2 0 1500 (3) 2 0 1500 1 0 0 0 ? 32.5 40 25 5 7.5

最优解为:X*=(5, 25, 0, 5, 0)T, 目标函数最优值70000.

三、用图解法找出以下目标规划问题的满意解。（10分）

????minz?Pd?d?P2d?d????111223x1?10x2?d?1?d?1?503x1?5x2?d?2?d?2?208x1?6x2?d?3?d?3?100

x1,x2,di?,di??0,i?1,2,3

满意解为（50，0） d1+=0,d1-=0,d2+=130,d2-=0，d3+=300,d3-=0 四、对于线性规划模型：（10分）

max f =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x4?20 2x1+x2+3x3+2x4?20 x1?0，x2?0，x3?0，x4?0

已知其对偶问题的最优解U*＝（6/5，1/5），利用互补松弛性求解原问题的解。

解：原问题的对偶问题为

min z =20u1+20u2 s.t. u1+2u2?1 （1） 2u1+u2?2 （2） 2u1+3u2?3 （3） 3u1+2u2?4 （4）

u1?0，u2?0 （5分）

??x?0x12将U＝（6/5，1/5）代入对偶问题，（1）、（2）式为严格不等式，则有，?0

??u?0u12因为，?0，所以有

*

2x3+3x4＝20

3x3+2x4＝20

**x?4x3解得，4?4。（5分）

五、现在有线性规划问题（15分）

max z=-5X1+5X2+13X3 ??X1?X2?3X3?20??12X1?4X2?10X3?90?X,X,X?0?123的最优单纯形表如下：

5 0 Cj X2 X5 r -5 -1 16 0 1 0 5 13 3 -2 1 0 0 1 0 b 20 10 -4 -5 0 -2 0 -100 （1）约束条件2的右端常数由90变为了70,对最优基、最优解有何影响？如果有影响请求出最优解。

?10??20??1'??B?1??b?Bb???41???10?????? 对最优基、最优解有影响.

5 0 5 13 Cj X2 X5 r X2 X3 r -5 -1 16 0 23 -8 -16 1 0 5 13 3 -2 1 0 0 1 0 b 20 -10 -4 -5 -5 2 -1 0 1 0 0 -2 0 1 0 0 3/2 -1/2 -1 -100 5 5 90 X=(0,5,5,0,0) z=90 （2）目标函数中X3的系数由13变为8,对最优基、最优解有何影响？如果有影响请求出最优解。

?3?r3?8??50????2????7?0?? 对最优基、最优解没有影响. 六、若发点A1，A2及收点B1，B2，B3的有关数据如下表所示。假定A1，A2处

允许物资存储，（本题共15分）

B1 B2 B3 A1 A2 需求量 4 6 8 6 2 4 50 100 100 供应量 200 200 存储费 5 4 （1） 写出运输问题的数学模型； （2） 用最小元素法找出初始基本可行解；

（3） 求出初始基本可行解的检验数，找出闭回路，确定调整量； （4） 求出最优运输方案和最小总运费。 解：

设Ai→Bj的运输量为xij，则由新的运输问题可以得到：

?5x1??12x?4x?2411?6x12?8x1346x222 min f?4x 3xx11?x12?x13?200x21?x22?x23?200x11?x21?50x12?x22?100x13?x23?100 xij?0,i?1,2,j?1,2,3

xij?0，i?1,2.j?1,2,3,4. （5分） (2)解：该运输问题为产>销的问题，虚拟销地B4，形成新的问题： B1 B2 B3 B4 供应量 A1 A2 需求量 4 6 8 5 6 2 4 4 50 100 100 150 200 200

（2分） 使用最小元素法得到初始解： B1 B2 B3 B4 A1 A2 需求量 50 100 50 100 100 50 100 100 150 供应量 200 200

（2分） （3）使用位势法，得到检验数为： B1 B2 B3 B4 A1 A2 0 3 0 0 3 0 -3 0 ui 0 -1

vj 4 3 8 5 增加A2→B3的运输量，得到新的解为： B1 B2 B3 B4 A1 A2 需求量 50 0 150 100 100 50 100 100 150 供应量 200 200 （2分）

使用位势法，得到检验数为： B1 B2 B3 B4 A1 A2 vj ui 0 -4 0 0 0 0 6 0 0 3 4 6 8 5 （4）因此可知： B1 B2 B3 B4 A1 A2 需求量 50 0 150 100 100 50 100 100 150 供应量 200 200 为该运输问题的最优解。 F=1050（4分）

七、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表1：（10分） 表1 工作 A B C D 工人 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？

解：用匈牙利法求解过程如下：得最优指派：

?0100??1000?????10000001????X1??X?2?0010?0010??????0001??0100?????

最少的耗时数z=15+18+16+21=70。 八、用标号法求出图中v1至各点的最短路（10分）

V21V49V1588274V633V7107V3V5

解：V1－V2 9 V1－V3 8（2分） V1－V2－V4 10（2分） V1－V2－V4－V5

或V1－V2－V6－V5 14（2分） V1－V2－V6 11（2分） V1－V2－V4－V7 13（2分）

本文来源：https://www.bwwdw.com/article/cr2p.html