运筹学期末考试试题及参

学号： 姓名：

《中山大学授予学士学位工作细则》第六条：“考试作弊不授予学士学位” 警示

说明：（1）共六题，满分100分；（2）考试时间120分钟；（3）对部分正确的答案，将会酌情给分。

一、考虑下面的线性规划问题：

Maximize Zc1x1x2subject to2x1x212x12x218x1,x20使用图解法，分析当c1(0c1)变化时最优解的变化。（15分） 参

可行域是OABC 所构成之多边形区域，如下图所示。

其中，O=(0,0)，A=(0,9)，B=(2,8)，C=(6,0)。 对不同的c1，最优解如下 c1的取值 c1 > 2 c1 = 2 0.5Page 1 of 6

最优解 C=(6,0) 线段BC上任意一点，即 (2,8)+ (1-)(6,0), 01 B=(2,8) 线段AB上任意一点，即 (0,9)+ (1-)(2,8), 01 A=(0,9) 最优目标函数值 6c1 12 2c1+8 9 9 二、帆船生产公司需要确定在今后4个季度每个季度中应该生产多少艘帆船，今后的4个季度每个季度的需求量是：第1季度为40艘帆船，第2季度为60艘，第3季度为75艘，第4季度为25艘。当前公司有10艘帆船的库存。每季度的需求必须满足（不能缺货）。在正常的工作时间内，公司每季度最多生产40艘帆船，每艘帆船总成本为400美元。如果加班的话，可以多生产，每艘成本为450美元。每季度末多余的帆船的仓储成本为20美元。使用线性规划描述该公司的生产计划问题，使该公司今后4个季度的生产和仓储成本最小。（15分）

参

xt: 每个季度正常生产的数量, t = 1,2,3,4, yt: 每个季度加班生产的数量, t = 1,2,3,4, it: 每个季度加班生产的数量, t = 1,2,3,4,

最小化总成本：总成本 = 正常生产的成本 + 加班生产的成本 + 库存成本

Min Z = 400x1 + 400 x2 + 400 x3 + 400 x4 + 450 y1 + 450 y2 + 450 y3 + 450 y4 + 20 i1 + 20 i2 + 20 i3

+20 i4 subject to x1 ≤ 40, x2 ≤ 40, x3 ≤ 40, x4 ≤ 40, i1 = 10 + x1 + y1 – 40, i2 = i1 + x2 + y2 – 60, i3 = i2 + x3 + y3 – 75, i4 = i2 + x4 + y4 – 25, xt, yt, it ≥ 0, t=1,2,3,4

三、考虑如下线性规划问题

Max Z2x15x23x3subject tox12x2x320x1x2x350x1,x2,x301、 写出两阶段法第一阶段的线性规划问题。（7分）

2、 构造问题1所得到的问题的初始单纯形表（如有需要转为合适的形式），并确定入基变量和出

基变量。（7分）

3、 写出该问题的对偶问题（6分）。

参

1、引入剩余变量x4, 人工变量x5,x6, 第一阶段问题:

Minimize Zsubject tox1x2x3x5x6x12x2x3x4x520x650

x1,x2,x3,x4,x5,x60Page 2 of 6

Maximize -Z

x5x6x12x2x3x4x5x1x2x320x650

subject tox1,x2,x3,x4,x5,x602、 迭代 基变量 Z x5 x6 方程 Z x1 x2 x3 x4 x5 x6 右端项 0 20 50 -20 20 50 -70 20 50 比值 初始表格（未转化为合适形式） 高斯消去: (0) (0)+(1)×(-1) 转化为合适的形式后 (0) -1 0 (1) 0 (2) 0 1 1 1 1 1 1 0 -2 1 2 -2 1 1 -2 1 0 1 1 -1 1 1 -2 1 1 0 -1 0 1 -1 0 1 -1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 20/1=20 50/1=50 Z x5 x6 (0) -1 -1 (1) 0 (2) 0 Z x5 x6 (0) -1 -2 (1) 0 (2) 0 初始BF解：x1=x2=x3=x4=0,x5=20,x6=50，入基变量：x3, 出基变量：x6. 3. Minimize W = 20y1 + 50y2 subject to

y1 + y2  2 -2y1 + y2  5 y1 + y2  3 y1 0, y2 free

四、已知线性规划问题:

maxZ3x1x24x3s.t.6x13x25x325(资源1)xj0,j1,2,3用单纯形法求解时, 其最优解的表见下表。 最终单纯形表

Page 3 of 6

3x14x25x320(资源2)

基变量 Z x1 x3 Z -1 0 0 x1 0 1 0 x2 2 -1/3 1 x3 0 0 1 x4 1/5 1/3 -1/5 x5 3/5 2/5 右端项 17 3 -1/3 5/3 1、 两种资源的影子价格分别是多少？（5分）

2、 写出最优解对应的对偶问题的互补基本解，并说明哪几个变量是对偶问题的决策变量，哪几

个变量是对偶问题的剩余变量。（5分）

23、若增加一个新的变量x4 , 其相应列系数为3，增加新变量后最优解是否发生变化？（5分） 24、资源2数量(b2)允许的变化范围是多少？（5分）

参

1、 两种资源的影子价格为 y1* = 1/ 5 , y2* = 3/ 5。

2、 y=(1/5, 3/5, 0, 2, 0), 其中y1, y2是决策变量，y3, y4, y5是剩余变量。

3、相应于新变量x4 , 对偶问题对应的约束为3y1 + 2y2 ≥ 2，因有3(1/5) + 2(3/5) = 9/5 < 2，故原问题最优解将发生变化。

1133*4、S，假设基变量不变，则

125511111133253325330**bSb122012b20+b1222555555

1515b2b233330223b3b2255因此7.5b25，因此12.5b225。

五、某玩具公司分别生产A、B、C三种新型玩具, 每月可供量分别为1000件，2000件，2000件, 它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期总销售量均为1500件, 由于经营方面原因, 各商店销售不同玩具的盈利额不同(见下表)。又知丙百货商店要求至少供应C 玩具1000件, 而拒绝进A玩具。玩具公司希望制定满足上述条件下使总盈利额为最大的供销分配方案。 A B C 甲 5 16 12 乙 4 8 10 丙 -- 9 11 可供量 1000 2000 2000 1、 试用参数表，把该问题表述为一个产销平衡的运输问题。（10分） 2、 写出该运输问题的线性规划模型。（5分）

参

Page 4 of 6

1、把丙分为a、b两个部分，增加一个假想需求部门丁, 产销平衡运输问题完整的参数表如下。 产地 A B C 销量 甲 5 16 12 1500 乙 4 8 10 1500 每单位分销成本 销地 丙a -M -M 11 1000 丙b -M 9 11 500 丁 0 0 0 500 产量 1000 2000 2000

3、 设产地A、B、C序号分别是1，2，3；销地甲、乙、丙a、丙b、丁的序号分别是1，2，3，

4，5。令xij = 产地i到销地j的运输量i=1,2,3, j=1,2,3,4,5，目标最大化利润，线性规划问题如下

maxZ5x114x12Mx13Mx1416x218x22Mx239x2412x3110x3211x3311x34s.t.x11x12x13x14x151000x21x22x23x24x252000x31x32x33x34x352000x11x21x311500x12x22x321500x13x23x331000x14x24x34500x15x25x35500xij0,i1,2,3,j1,2,3,4

六、运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他多个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i 和城市j 之间的距离为dij，总共有n个城市。问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。把该问题描述为一个整数规划模型或混合整数规划模型。（15分）

参

设 xij = 1 , 旅行商贩从城市 i 出发的下一城市是 j

0 , 否则

由此可写出其整数规划模型为

Page 5 of 6

minZdijxiji1j1nns..txi1nj1nij1,j1,...,n1,i1,...,n

xijxi1i2xi2i11,所有不同的i1,i2组合，i1,i21,...,nxi1i2xi2i3xi3i12,所有不同的i1,i2,i3组合，i1,i2,i31,...,n......xi1i2xi2i3...xin2i1n2,所有不同的i1,i2,...,in-2组合，i1,i2,...,in-21,...,nxij0或1,i,j1,...,n其中第一个约束保证每个城市的下一个访问城市只有一个；第二个约束保证每个城市的上一个访问城市只有一个；其余所有等式约束排除子回路，比如ABCDEF六个城市的问题，ABCA和DEFD是一个不满足题目要求但满足第一个和第二个约束的子回路，上述约束排除了所有这些可能的子回路。

Page 6 of 6