运筹学期末考试试题及参考答案

Page1of62014-2015学年度第2学期12级物流管理专业“运筹学”课程试题（样本）学号：姓名：《中山大学授予学士学位工作细则》第六条：“考试作弊不授予学士学位”说明：（1）共六题，满分100分；（2）考试时间120分钟；（3）对部分正确的答案，将会酌情给分。一、考虑下面的线性规划问题：112121212Maximizesubjectto212218,0Zcxxxxxxxx使用图解法，分析当11(0)cc变化时最优解的变化。（15分）参考答案可行域是OABC所构成之多边形区域，如下图所示。其中，O=(0,0)，A=(0,9)，B=(2,8)，C=(6,0)。对不同的c1，最优解如下c1的取值最优解最优目标函数值c12C=(6,0)6c1c1=2线段BC上任意一点，即(2,8)+(1-)(6,0),01120.5c12B=(2,8)2c1+8c1=0.5线段AB上任意一点，即(0,9)+(1-)(2,8),0190c10.5A=(0,9)9警示Page2of6二、帆船生产公司需要确定在今后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,最小化总成本：总成本=正常生产的成本+加班生产的成本+库存成本MinZ=400x1+400x2+400x3+400x4+450y1+450y2+450y3+450y4+20i1+20i2+20i3+20i4subjecttox1≤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三、考虑如下线性规划问题123123123123Max253subjectto22050,,0Zxxxxxxxxxxxx1、写出两阶段法第一阶段的线性规划问题。（7分）2、构造问题1所得到的问题的初始单纯形表（如有需要转为合适的形式），并确定入基变量和出基变量。（7分）3、写出该问题的对偶问题（6分）。参考答案1、引入剩余变量x4,人工变量5x,6x,第一阶段问题:56123451236123456Minimizesubjectto22050,,,,,0ZxxxxxxxxxxxxxxxxxPage3of656123451236123456Maximize-subjectto22050,,,,,0Zxxxxxxxxxxxxxxxxx2、迭代基变量方程Zx1x2x3x45x6x右端项比值初始表格（未转化为合适形式）Z(0)-100001105x(1)01-21-110206x(2)011100150高斯消去:(0)(0)+(1)×(-1)Z(0)-1-12-1101-205x(1)01-21-110206x(2)011100150转化为合适的形式后Z(0)-1-21-2100-705x(1)01-21-1102020/1=206x(2)01110015050/1=50初始BF解：x1=x2=x3=x4=0,5x=20,6x=50，入基变量：x3,出基变量：6x.3.MinimizeW=20y1+50y2subjecttoy1+y22-2y1+y25y1+y23y10,y2free四、已知线性规划问题:123123123max34..63525(1)34520(0,1,2,3jZxxxstxxxxxxxj资源资源2)用单纯形法求解时,其最优解的表见下表。基变量Zx1x2x3x4x5右端项最终单纯形表Z-10201/53/517x101-1/301/3-1/35/3x30011-1/52/53Page4of61、两种资源的影子价格分别是多少？（5分）2、写出最优解对应的对偶问题的互补基本解，并说明哪几个变量是对偶问题的决策变量，哪几个变量是对偶问题的剩余变量。（5分）3、若增加一个新的变量x4,其相应列系数为232，增加新变量后最优解是否发生变化？（5分）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/52，故原问题最优解将发生变化。4、*11331255S，假设基变量不变，则**2222221111112502533333320+12122012555555151533303223355bSbbbbbbb因此27.55b，因此212.525b。五、某玩具公司分别生产A、B、C三种新型玩具,每月可供量分别为1000件，2000件，2000件,它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期总销售量均为1500件,由于经营方面原因,各商店销售不同玩具的盈利额不同(见下表)。又知丙百货商店要求至少供应C玩具1000件,而拒绝进A玩具。玩具公司希望制定满足上述条件下使总盈利额为最大的供销分配方案。甲乙丙可供量A54--1000B16892000C12101120001、试用参数表，把该问题表述为一个产销平衡的运输问题。（10分）2、写出该运输问题的线性规划模型。（5分）参考答案Page5of61、把丙分为a、b两个部分，增加一个假想需求部门丁,产销平衡运输问题完整的参数表如下。每单位分销成本销地甲乙丙a丙b丁产量产地A54-M-M01000B168-M902000C1210111102000销量1500150010005005003、设产地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，目标最大化利润，线性规划问题如下1112131421222324313233341112131415212223242531323334351121311222321323331424max54168912101111..100020002000150015001000ZxxMxMxxxMxxxxxxstxxxxxxxxxxxxxxxxxxxxxxxxxx341525355005000,1,2,3,1,2,3,4ijxxxxxij六、运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他多个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij，总共有n个城市。问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。把该问题描述为一个整数规划模型或混合整数规划模型。（15分）参考答案设xij=1,旅行商贩从城市i出发的下一城市是j0,否则由此可写出其整数规划模型为Page6of61221122331122321111112121231231min..1,1,...,1,1,...,1,,,1,...,2,,,,,1,...,.........2,,所有不同的组合，所有不同的组合，所有不同的nnnijijijnijinijjiiiiiiiiiiiiiiiiZdxstxjnxinxxiiiinxxxiiiiiinxxxnii2n-212n-2,...,,,...,1,...,01,,1,...,组合，或ijiiiinxijn其中第一个约束保证每个城市的下一个访问城市只有一个；第二个约束保证每个城市的上一个访问城市只有一个；其余所有等式约束排除子回路，比如ABCDEF六个城市的问题，ABCA和DEFD是一个不满足题目要求但满足第一个和第二个约束的子回路，上述约束排除了所有这些可能的子回路。