管院运筹学考试内容.doc

《管院运筹学考试内容.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、建模问题例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50

2、，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。例4.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表： B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150 工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还

3、是A4，才能使今后每年的总费用最少。解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：一、简答题1.单纯形的基本思想与主要步骤单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题

4、的最优解。如果问题无最优解也可用此法判别。主要步骤：1.对偶单纯形法的主要迭代步骤迭代步骤：一、计算题1.对偶单纯形法求解例3.6用对偶单纯形法求解（P）例3.6线性规划如下：maxZ=2x1+x2问题：1.若c1降为1.5，而c2增至2时，最优解有何变化；2.若c1不变，c2在什么范围内变化时，该规划的最优解不发生变化。解(1)将c1和c2的变化直接反映到最终单纯形表中得：cj1.52000CB基bx1x2x3x4x501.52x3x1x215/27/23/2010001100[5/4]1/4－1/4－15/2－1/23/

5、2cj－zj0001/8－9/4从上面的单纯形最终表格知道：原来问题的最优解为：x1=7/2,x2=3/2。重新算检验数。发现变量x4的检验数大于零，故需继续用单纯形法迭代计算CB基bx1x2x3x4x501.52x4x1x26230100014/5－1/51/5100－610cj－zj00－1/100－3/2最优解变为：x1=2,x2=3(2)设c2=(1+λ)元，反映到最终单纯形表中得:cj21+λ000CB基bx1x2x3x4x5021+λx3x1x215/27/23/20100011005/41/4-1/4-15/2

6、-1/23/2cj－zj000-1/4+λ/4-1/2-3λ/2为使上表中的解仍为最优解，应有解得：即c2的变化范围应满足：一、最短路问题看一下课本P195页的例题，记住步骤就可以，考试题目比这简单。二、运输问题（产销平衡）这道题看一下老师的课件运输问题那一章，看课件P10页---P30页的解题步骤。考题和这个很相似。欢迎大家补充。祝大家学习愉快，快乐加油！