北京交通大学交通运输学院《942管理运筹学》历年考研真题汇编（含部分答案）合集

目录2015年北京交通大学交通运输学院942管理运筹学考研真题2014年北京交通大学交通运输学院942管理运筹学考研真题2013年北京交通大学交通运输学院942管理运筹学考研真题2012年北京交通大学交通运输学院942管理运筹学考研真题2011年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题2010年北京交通大学交通运输学院942管理运筹学考研真题及详解2009年北京交通大学交通运输学院942管理运筹学考研真题2009年北京交通大学交通运输学院942管理运筹学考研真题及详解2008年北京交通大学交通运输学院942管理运筹学考研真题2008年北京交通大学交通运输学院942管理运筹学考研真题（含部分答案）

2007年北京交通大学交通运输学院417管理运筹学考研真题2007年北京交通大学交通运输学院417管理运筹学考研真题及详解2006年北京交通大学交通运输学院417管理运筹学考研真题2006年北京交通大学交通运输学院417管理运筹学考研真题及详解2005年北京交通大学交通运输学院417管理运筹学考研真题2005年北京交通大学交通运输学院417管理运筹学考研真题及详解

2004年北京交通大学交通运输学院管理运筹学考研真题2004年北京交通大学交通运输学院管理运筹学考研真题及详解2003年北方交通大学交通运输学院管理运筹学考研真题2003年北方交通大学交通运输学院管理运筹学考研真题及详解2002年北方交通大学交通运输学院管理运筹学考研真题2002年北方交通大学交通运输学院管理运筹学考研真题及详解

2001年北方交通大学交通运输学院管理运筹学考研真题2001年北方交通大学交通运输学院管理运筹学考研真题及详解2000年北方交通大学交通运输学院管理运筹学考研真题

2015年北京交通大学交通运输学院942管理运筹学考研真题

2014年北京交通大学交通运输学院942管理运筹学考研真题

2013年北京交通大学交通运输学院942管理运筹学考研真题

2012年北京交通大学交通运输学院942管理运筹学考研真题

2011年北京交通大学交通运输学院942管理运筹学考研真题

2010年北京交通大学交通运输学院942管理运筹学考研真题

2010年北京交通大学交通运输学院942管理运筹学考研真题及详解北京交通大学2010年硕士研究生入学考试科目代码：942科目名称：管理运筹学一、判断（正确的打“∨”，错误的打“×”）1．线性规划问题的每一个基解对应可行域的一个顶点；（北京交通大学2010年研）【答案】×【解析】基解不一定是可行解，基可行解对应着可行域的顶点。2．若、分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中、为正的实数；（北京交通大学2010年研）【答案】×【解析】必须规定，当一线性规划问题存在两个最优解时，则它一定存在无数个最优解，3．已知为线性规划问题的对偶问题的最优解，若，则说明在最优生产计划中第种资源已经完全耗尽；（北京交通大学2010年研）【答案】∨【解析】对偶问题互补松弛性质中；当表明在最优生产计划中第种资源已经完全耗尽。时，有，4．整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值；（北京交通大学2010年研）【答案】×【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目标函数值一定不优于其相应线性规划问题最优解的目标函数值。5．指派问题效率矩阵的每个元素乘以同一大于0的常数，将不影响最优指派方案；（北京交通大学2010年研）【答案】∨【解析】效率矩阵每个元素乘以同一大于0的常数，即目标函数的系数同时增大k倍，不会影响最优基的变化，故不影响最优指派方案。6．如果图T是树，则T中一定存在两个顶点，它们之间存在两条不同的链；（北京交通大学2010年研）【答案】×【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。7．任一图研）都存在支撑子图和支撑树；（北京交通大学2010年【答案】×【解析】当图中存在一个顶点，其次为0时，则该图不存在支撑树。8．网络图中任何一个结点都表示前一工序的结束和后一工序的开始；（北京交通大学2010年研）【答案】×【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。9．结点最早时间同最迟时间相等的点连接的线路就是关键路线；（北京交通大学2010年研）【答案】∨【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。10．假如到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布；（北京交通大学2010年研）【答案】∨【解析】设N（t）为时间[0，t]内到达系统的顾客数，则为参数为的普阿松流的充要条件是：相继到达时间间隔服从相互独立的参数为的负指数分布。11．运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解；（北京交通大学2010年研）【答案】×【解析】运输问题是一种特殊的线性规划模型，它总存在可行解，或是存在唯一最优解，或是有无穷最优解。12．单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。【答案】∨【解析】选择任何一个大于零的都可以，由上式可以看出，将最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。二、简答1．试简述求解整数规划模型的分枝定界法剪枝的几种情况；（北京交通大学2010年研）答：（1）某枝已经达到其范围内的最优解；（2）某枝域内没有可行解时，即是不可行域；（3）某枝所得数据不优于当前最优解时。2．试写出标准指派问题的线性规划问题；（北京交通大学2010年研）答：设，则得线性规划模型3．试写出求解最短径路的Dijkstra算法的步骤；（北京交通大学2010年研）答：步骤：（1）给（2）若vi点为刚得到P标号的点，考虑这样的点vj，（vi，vj）属于E，且vj为T标号。对vj的T标号进行如下修改：（3）比较所有具有T标号的点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号时停止。否则用代转回（2）。4．试写出M/M/1排队系统的Little公式；（北京交通大学2010年研）答：三、（40分）某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，其所需劳动力、原材料等有关数据如下：每件产品Ⅰ分别需要劳动力和原材料6个小时和3公斤，每件产品Ⅱ分别需要劳动力和原材料为3小时和4公斤，每件产品Ⅲ分别需要劳动力和原材料为5小时和5公斤；拥有的劳动力和原材料总数分别为45小时和30公斤；又知Ⅰ、Ⅱ、Ⅲ三种产品的单件利润分别为3、1、4元。（北京交通大学2010年研）要求：1．写出该厂获得最大的生产计划问题的线性规划模型并求出最优解；答：设三种产品的产量分别为x1、x2、x3，则得模型：将上述问题改写为标准形式为：用单纯形法计算如下：cj31400CBXBbx1x20x445630x53034x3x4x551[5]040011001310x415[3]－14x363/54/50－11/5－4/53/5－11/5003x151－1/301/3－1/34x33010－21－1/52/50－1/5－3/5得到最优解，即生产Ⅰ、Ⅲ各5和3件。2．写出该线性规划问题的对偶问题，并求对偶问题的最优解；答：对偶问题：由及上述最终单纯形表可知，。3．产品Ⅰ的利润在什么范围内变化时，上述最优计划不变？答：保持最优计划不变，即保持各非基变量检验数非正，则解得。4．如果设计一种新产品Ⅳ，单件产品消耗劳动力8小时，原材料2公斤，每件可获利3元，问该产品是否值得生产？答：新产品的产量为x6，则相对约束矩阵多一列向量单纯形表中为，在最终，其检验数为，故值得生产。5．如果劳动力数量不变，原材料可以从市场购买，每公斤0.4元，问该厂是否购买原材料来扩大生产，以购买多少为宜？答：设购买，则①②，故可以购买原材料来扩大生产。由①②两式得，即购买15公斤时可获得最大效益。四、（16分）某公司有甲，乙，丙三个工厂和A，B，C三个客户，这三个工厂在下一时期将分别生产某种产品300，500和400件，公司计划卖给客户A，B，C的产品数量分别为400，300，100件，客户D想尽可能多地购买剩下的商品。工厂卖给各客户单位产品的利润如下表。问如何安排供应使该公司总利润最大。答：该问题属于平衡运输问题，客户D将购买300＋500＋400－（400＋300＋100）＝400（件）商品。则由沃格尔法得初始方案，并用位势法得各空格检验数[]所示：ABCD供给量行差甲乙丙[－2]15[－3]13[－1]12300143002001830017[1]15[－3]1250020013[－2]1010091001040011112322需求量400300410033400223列差3234空格[乙C]检验数为正，故调整其所在回路，调整值为min[200，100]＝100并检验得：ABCD供给量甲乙丙[－2]15[－3]13[－2]1230014300100183001710015[－3]1250030013[－2]10[－1]910010400需求量400300100400所有检验数均小于零，即得最优方案如下：ABCD供给量甲乙丙300300500100400100300100300需求量4003001004001200五、（20分）用动态规划方法求解下列整数规划问题：（北京交通大学2010年研）答：将该过程分为3个阶段，决策变量为，状态变量为，表示第k阶段开始时候的状态（k＝1，2，3），其中，最优指标函数，表示第k阶段状态为时，第k阶段至第3阶段的最优值，且逆推法。，表示每个阶段的指标函数。采用k＝3时，k＝2时，k＝1时，。所以得x1*＝1，x2*＝2，x3*＝0，maxZ＝18。六、（14分）某理发店只有一个理发员，来理发的顾客到达过程为posson流，平均5人/小时；理发时间服从负指数分布，平均需要10分钟；店内备有5把椅子供顾客等候，多余顾客将到其他理发店理发。（北京交通大学2010年研）求：（1）该理发店忙的概率；（2）该店内恰有2个顾客的概率；（3）在该店内的平均顾客数；（4）每位顾客在该店内的平均逗留时间；（5）等待服务的平均顾客数；（6）每位顾客平均等待时间；（7）顾客损失的概率。答：该问题属于M/M/1/N模型，，，N＝5。（1）（2），∴1－P0＝0.7494，即为理发店忙的概率。∴。（3）。（4）（5）。。（6）顾客的平均等待时间是（7）。，即顾客损失的概率。2009年北京交通大学交通运输学院942管理运筹学考研真题

2009年北京交通大学交通运输学院942管理运筹学考研真题及详解北京交通大学2009年硕士研究生入学考试科目代码：942科目名称：管理运筹学一、（50分）已知线性规划问题如下：1．求该问题的最优解；答：用对偶单纯形法计算如下：ciCBXBb251/200x3x4x5x1x20x4－3－1－20x5－90－125－1/210[－3]011/2000x4－2/3－1－11/601[－1/6]0－1/30－1/6－611/2x3301/31－2－29/600x691/2x366112413010－2010得最优解，X*＝（0，0，6）T，minz＝1/2×6＝3。2．写出该线性规划问题的对偶问题，并求对偶问题的最优解；答：由上最终单纯形表可得，，maxw＝33．分别确定x2、x3的目标函数系数c2、c3在什么范围内变化，最优解不变？答：（1）c2变化，最优解不变，要保证，解得，即。（2）c3变化，最优解不变，要保证，，解得，即。4．求约束条件右端值由变为时的最优解；答：代入最终单纯形表中，，因此不是最优解。ci0x6－3611251/2000[－6]11/2x3424131－200100x41/2－1－11/6011/2x3401/310029/600－1/6－1/31/6得新的最优解是X*＝[0，0，4]T，minz＝1/2×4＝2。5．求增加新的约束条件x1＋2x2＋x3≤5时的最优解。答：加入松弛变量x6得下表cjCBXBb0x4－3－1－20x5－90－10x6－5－1－2251/200x3x4x5－1/210[－3]01－1001/2000x1x2x60012500x4－2/3－1－11/601/2x330x6－2－1－5/3029/601－1/6001/310－1/300[－1/3]1201/61000010000x41/3－1/2－10100－1/2－1－31/21/2x350x5613253/24得最优解X*＝[0，0，5]T，minz＝1/2×5＝5/2。二、（25分）某铁路企业承担A、B、C三个城市之间的城际旅客列车运输任务，列车的出发和到达时间如下表所示：设旅客列车从到达某站到出发至少需要2个小时的准备时间，试制定一个最佳的旅客列车车底接续方案，使该铁路企业所使用的车底数量最少。答：题中，将达到某城市的列车当成是要完成工作的工作人员，而在该城市出发当成是要完成的工作，则3座城市的列车工作效率如下所示，数据是执行任务需等待时间。A城市：到达出发T101T103T105T107T109T102T104T106T108T1102381362925158411319152214201623152521420B城市到达出发T102T104T106T101T103T1051615102322173221C城市到达出发T108T110T107T109751513则对于A城市，利用匈牙利算法指派任务如下：初次指派为：盖所有的零元素，◎的个数少于54，故进行划线覆；继续求解，零元素，并最终求得最优解，依然不符合，故继续划线覆盖所有，即A城市中到达出发T101T103T105T107T109T102T104T106T108T110319243所需车底数是3；同理得B城市的指派为，所需车底数为2；C城市指派为，需要车底数为2。综上，该企业总的车底数最少需要是7个。三、（20分）已知运输问题的运价及产销平衡表如下：要求：1．用最小元素法求该运输问题的初始解，并进一步求出最优解；2.A3→B3的单位运价C33变为什么值时，有无穷多最优解？并进一步给出两个新的最优方案。答：（1）该运输问题的初始解是：B1B2B3B4产量A1A2310A310210122553销量6101212利用位势法计算个空格的检验数为：产量B1B2B3B4A1[1][0]10[1]10A2310[－2]1225A33[13]2销量61012[7]512空格A2B2检验数小于0，故调整其所在回路，调整量为min（2，3）＝2，得新方案，并检验之，如表中所示：B1B2B3B4产量A1[－1][－2]10[－1]10A2A3151021225[13][2][7]51212销量610仍不是最优方案，故继续调整，最后得最终方案如下：B1B2B3B4产量A110A210121225A3销量61012121055（2）A3B3的检验数为C33－12＋10－6＝0时，即C33＝8时，有无穷多最优解。新方案一：B1B2B3B4产量A1A210101.54.511.512250.55

A3销量6101212新方案二：B1B2B3B4产量A1A2A310102411122515销量6101212四、（21分）某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如下表所示。已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。（北京交通大学2009年研）答：采用动态规划方法求解。设每个月生产xk件产品，xk小于等于6；sk为每个月开始的存货量，则s1＝0，s5＝0，，表示在k月初存货量是sk是从第表示第k个月生产xk个产品k个月开始至第4个月的最优指标函数。时所需要的生产费用，，表示第k个月生产xk个产品时，剩余产品所需要的存储费用，（1）k＝4时，（2）k＝3时，（3）k＝2时，（4）k＝1时，∴为最优生产计划。五、（20分）在下图中，分别求v1至v6，v1至v4，v6至v2和v2至v5的最短路和最短距离。（北京交通大学2009年研）答：用Floyd方法求解：令网络的权矩阵为k＝0，，由表示从vi到vj点或直接有边或借v1点为中间点是的最短路长，括弧中元素为更新元素，得D（1）k＝1，；表示从vi到vj点最多经v1，v2的最短路长，得D（2）k＝2，k＝3，，依次类推，；k＝4，；k＝5，。；k＝6，∴v1至v6的最短路是v1－v3－v5－v6，最短距离是－1。v1至v4的最短路是v1－v3－v5－v4，最短距离是0。v6至v2的最短路是v6－v4－v2，最短距离是3。v2至v5的最短路是v2－v3－v5，最短距离1。六、（14分）某汽车加油站只有一个加油设备，汽车到达加油站的过程服从泊松分布，汽车平均到达时间间隔为5分钟，加油站平均1个小时能加24辆车。试求：（1）加油站的空闲的概率；（2）加油站有三辆车的概率；（3）加油站有两辆车以上的概率；（4）加油站内的平均车辆数；（5）车辆在加油站内的平均逗留时间；（6）加油站内的平均等待车数；（7）车辆的平均等待时间。答：属于M/M/1/∞模型，。（1）加油站的空闲的概率。（2）加油站有三辆车的概率（3）加油站有两辆车以上的概率（4）加油站内的平均车辆数即。。。（辆）。（5）车辆在加油站内的平均逗留时间（6）加油站内的平均等待车数即（7）车辆的平均等待时间（辆）。。2008年北京交通大学交通运输学院942管理运筹学考研真题

2008年北京交通大学交通运输学院942管理运筹学考研真题（含部分答案）北京交通大学2008年硕士研究生入学考试试卷考试科目：942管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（35分）已知线性规划问题：maxZ＝3x1＋4x2＋x3（1）求线性规划问题的最优解：（2）求对偶问题的最优解：（3）求b1的灵敏度范围；（4）求c2的灵敏度范围；如果右端值[10，16]变为[12，10]求新问题的最优解。答：（1）由题意，用单纯形法计算。Cj34100θiCBXBb00101[2]11016221013410058Cj－Zj40Cj－Zj51/211/21/206[1]00－1110－1－2010643Cj－Zj2011/21－1/26100－1100－1－1－1此时，所有检验数为负，已得最优解XT＝（6，2，0），目标函数值为Z＝26。（2）对偶问题Minw＝10y1＋16y2s．ty1＋2y2≥3①2y1＋2y2≥4②y1＋y2≥1③y1，y2≥0由互补松弛条件YXs＝0，XYs＝0；由X＝（6，2，0），得Y1s＝0Y2s＝0，即①②③为严格等式，即y1＋2y2＝3，2y1＋2y2＝4；所以y1＝1，y2＝1。即最优解y1＝1，y2＝1，minw＝26。（3）灵敏度分析当b1变化△b时，可计算B－1b＋B－1由，所以。因此8≤b1≤16。（4）记即，得，所以。（5）当右端值由[10，16]变为[12，10]时，。将其反映到最终单纯性表中，再用对偶单纯性法进行迭代，如下。Cj34100CBXBb43Cj－Zj7011/21－1/2－2100[－1]100－1－1－145111/201/20Cj－Zj2－1001－10－10－1－2故新问题的最优解为X＊＝（0，5，0，2，0），最优值为z＊＝20。二、（20）已知LP问题为要求：（1）设其偶变量为y1，y2，y3，y4，写出其对偶问题；（2）已知原问题最优解（x1，x2，x3，x4，）＝（2，2，4，0），试根据对偶性质直接求出对偶问题的最优解。（北京交通大学2008年研）答：（1）对偶问题minW＝8y1＋6y2＋6y3＋9y4s．t（2）由互补松弛条件YXs＝0，XYs＝0；（x1，x2，x3，x4，）＝（2，2，4，0），则X1s＝X2s＝X3s＝0，X4s≠0，且＝0，Y1s＝Y2s＝Y3s＝0所以，因此（y1，y2，y3，y4）＝（，1，0）。三、（20）某公司有3个工厂和3个客户，这3个工厂在下一时期将分别制造产品300，500和200件，公司答应卖给客户1，2，3的产品分别是300，200，100件，客户4想尽可能多的购买剩下产品。工厂i卖给客户j的单位产品利润如下表所示。问如何安排生产和供应才能使总利润最大？答：用18减去图中各个利润，将问题转化为运输问题，建立产销平衡表。产量356430001365005898200销量300200100400用伏格尔法求解，（）内数据为解产地销地销量产量行差30（300）1（200）3（0）65300564（300）300112500139（100）8（100）2003318200100400列差334323324用位势法计算所有空格的检验数，计算结果如下图所示。12104－24－112354表中有负检验数，选择（1，3）为调入格，调入量为100，得新的解300200200100100100再用位势法检验，得检验数2322103－141244此时，所有检验数都非负，故上表中的解为最优解。即安排A1生产300提供给B4，A2生产200提供给B1，A2生产200提供给B2，A3生产100提供给B3，A3生产100提供给B1，A3生产100提供给B4，故总利润为15000。四、（25）某工厂有1000台机器，拟分四个阶段使用。已知在每个阶段有两种生产任务，进行第一种生产时每台机器可收益9千元，其机器报废率0.3，而进行第二种生产时每台机器可收益6千元，其机器报废率为0.1．文怎样分配机器，使收益最大？（要求写出动态规划模型的基本要素并求解）（北京交通大学2008年研）答：将此题看成一个4个阶段决策问题。令为状态变量，它表示第k阶段初拥有的完好机器数量，决策变量为第k阶段分配给第一种生产的机器数量，于是为该阶段分配给第二种生产的机器数量。状态转移方程为收益，则，设为第k阶段的令最优值函数表示由机器数量出发，从第k阶段开始到第4阶段结束时所获得的收益最大值，故有递推关系式：（1）k＝4时，因f4是u4的线性单调增函数，故得最大解（2）k＝3时，，相应的。故得最大解，相应的有。（3）k＝2时，当，相应的有。（4）k＝1时，当，相应的有。因s1＝1000，所以＝23793千元。计算结果表明，第1阶段将1000台机器投入第二种生产，第2阶段将900台机器投入到第二种生产，第3阶段将810台机器投入到第一种生产，第4阶段将567台机器投入到第一种生产。可得最大收益为23793千元。五、（10）为解决污水河流的污染问题，某城市拟修建污水处理站。备选的站址有A、B、C三个，其投资等技术经济参数见下表：按环保部门要求，每年至少要从污水中清除8万吨污染物1和6万吨污染物2。请构造一个整数规划模型，在满足环保要求的前提下使投资和运行费用最小。（北京交通大学2008年研）答：设表示处理的万吨数，，被采用时为1，未采用时为0。建立整数规划模型minz＝500＋500x1＋400＋800x2＋300＋1000x3六、（20）某修理店只有一个修理工，来修理的顾客到达过程为poisson流，平均5人／小时。分别计算在下列修理时间分布的情况下系统的Ls，Lq，Ws与Wq的值。（1）修理时间为常数，每次修理需10分钟；（2）修理时间为负指数分布，平均修理需10分钟；（3）修理时间为正态分布，μ＝9分钟，δ＝4。答：（1）当修理时间为常数（2）当修理时间为负指数分布（3）当修理时间为正态分布2007年北京交通大学交通运输学院417管理运筹学考研真题

2007年北京交通大学交通运输学院417管理运筹学考研真题及详解北京交通大学2007年硕士研究生入学考试试卷考试科目：417管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（20分）某工厂准备生产甲、乙、丙三种产品，它们都消耗A、B两种原材料，有关数据如下表所示：要求：构造使该厂利润最大的线性规划模型，并用单纯型法求解。答：设三种产品的产量分别为x1、x2、x3，则得以下线性规划模型：用单纯形法计算如下：cj3140x3x451[5]040CBXBbx1x20x445630x5303431x5010x415[3]－101－14x363/54/5101/53/5－11/500－4/53x151－1/301/3－1/34x33010－21－1/52/50－1/5－3/5得到最优解，即生产甲和丙各5和3单位。二、（40分）已知线性规划模型Maxz＝2x1＋x2求：（1）写出原问题的对偶线性规划模型；（2）用对偶单纯型法求解原问题的最优解；（3）增加约束条件3x1＋2x2≤12，最优解会有什么变化？（4）若C1由2降至1.5，C2由1升至2，最优解会有什么变化？（5）资源b3由现在的5变成4，最优解是否发生变化。答：（1）（2）对原问题的对偶问题利用对偶单纯形法cjCBYBb0y4－2015y124y2500y3y41y50[－6]－10y5－1－5－2－1011524150024y21/301/6－1/600y5－1/3－50[－2/3]－1/3115010104024y21/4－5/415y31/215/2015/20－1/41/41/2－3/27/23/2得最优解，X*＝[7/2，3/2]，maxz＝8.5。（3）即对偶问题增加了一变量y6，其约束变量为a＝[3，2]T，目标函数变量为12，在最终单纯形表中的，，因此不是最优解，继续计算如下：cjCBYBby1152450012y6y2y3y4y524y21/4－5/4105y31/215/20115/200－1/41/41/41/2－3/2[3/2]7/23/2－3/224y21/6－5/21－1/6－1/31/2012y61/351502/31/3－1101040得原问题最优解X*＝[4，0]，maxz＝8。（4）在其对偶问题中，即资源变量变化，最终单纯形表中，继继续利用对偶单纯形法计算如下：cjCBYBb15y124y2500y3y4y524y2－1/8[－5/4]10－1/41/411/2－3/207/23/25y39/415/215/20015y11/1015y33/200－4/501/5－1/5661－10023得原问题最优解X*＝（2，3）T，maxz＝7。（5）即对偶问题c3＝4，y3是基变量，因此检查各非基变量的检验数，因此最优解不发生变化。三、（15分）求出下面运输问题的所有最优解。答：本题为运输平衡问题，用沃格尔法计算如下：（）内数据为解。产地销地B1B2B3B4产量行差A1A2A3A49（6）8（2）13（5）14（5）181141110810912（24）1411（6）13240022611122107（12）111212360销量列差611114135051111111112用位势法检验，各空格检验数[]内数据，存在检验数小于零的空格。产地销地B1B2B3B4产量A19（6）8（2）13（5）14（5）18A2A310[2]10[3]12（24）14[1]11（6）13[1]2468[1]9[3]A4销量10[2]7（12）11[－1]12[－1]1261435560在相应回路调整，如空格A1B3所在回路，调整量为5，最后得新方案，并检验如下：不存在检验数小于0的空格，得最优解，∵A3B1检验数为0，∴最优解不唯一。产地销地B1B2B3B414[1]产量18A19（6）8（12）13[1]A2A310[1]10[2]12（24）14[1]11（6）13[1]248[0]9[2]6A4销量10[2]7（2）11（5）12（5）1261435560由A3B1所在回路，任意变化可得所有最优解如下：产地销地B1B2B3B4产量A16－c12＋c18A2A324246c6－cA4销量2－c5＋c51214355606C的取值范围是[0，2]。四、（15分）用分支定界法求整数规划问题的最优解

Maxz＝X1＋x2答：利用单纯形法先解相应的线性规划，得最优解如下：cj1100CBXBbx1x2x3x41x13/2107/161x210/3017/8－9/327/1600－21/16－5/32不是整数，故用分支定界法继续求解，z0＝29/6是问题最优解z*的上界，z＝0是一个下界，则。将问题分成问题B1和B2问题B1问题B2z1＝10/3z1＝41/9x1＝1x1＝2x2＝7/3x2＝23/9∵z1<z2，∴先将问题B2分解成B3和B4问题B3问题B4z1＝17/6z1＝14/3x1＝5/6x1＝5/3x2＝2x2＝3接着讲B4分解成问题B5和B6，问题B5问题B6z1＝17/6z1＝4x1＝2x1＝3x2＝23/9x2＝1得到一整数解z＝4，X＝[3，1]T，比较个z值，发现B6的解即为最优解。五、（20分）某部门拟将某种新设备5台分配给甲、乙、丙3个工厂，各工厂获得这些设备后可盈利如下表所示，这5台设备应如何分配，使其利润最大？用动态规划方法求解（要求写出状态转移方程和递推方程）。答：将该问题分成3个阶段，xk（k＝1，2，3，4）为决策变量即在第K阶段分给k工厂xk台设备，sk（k＝1，2，3，4）为第k阶段开始时候的状态变量，为最优策略的指标函数，表示第k阶段状态为sk时第k阶段至第三阶段的最优值，且，用加法方式。s1＝5，s2＝s1－x1，s3＝s2－x2＝x3。模型为：∴0≤x1≤5，0≤x2≤s2，0≤x3＝s3其中，a（x1），b（x2），c（x3）分别表示三家工厂获得这种设备后将能为集团提供的盈利，如上表所示，采用逆推法，计算如下：k＝3时，，即S3x3x3*000114226331144125512012345k＝2时，，即x2S2012345x2*01234504565＋410115＋610＋411125＋1110＋611＋4110510141601221、22125＋1210＋1111＋611＋41121k＝1时，，即x1s1012345x1*5213＋167＋149＋1012＋513210、2∴分配给各厂的设备分别为2、2、1或者0、2、3．获得最大利益21。六、（20分）在下图中，分别求v1至v6，v4至v5，v6至V2的最短路和最短距离。答：用Floyd方法求解：令网络的权矩阵为，Dk表示至少经过vk时的距离，括号内数字即变动的距离。，，∴可得v1至v6的没有通路，最短距离是∞。v4至v5的最短路是v4—v2—v3—v5，最短距离是－3。v6至V2的最短路是v6—v4—v2，最短距离－1。七、排队论（20分）假设到达一个公用电话间的顾客数服从普阿松分布，有两个公用电话间同时使用。两个顾客相继到达的平均间隔时间为3分钟，通话时间服从平均数为3分钟的普阿松分布。公用电话间内最多只能容纳5人。假设到达的顾客见到电话间里已有5个人时就离开这个公用电话间去别处打电话。求：（1）一位到达的顾客只得离开这个电话间去别处打电话的概率；（2）平均队长；（3）电话局打算只要顾客在队伍中的平均等待时间不超过1分钟，就搬走一台电话。但如果因为减少一台电话会使顾客排队等待时间超过5分钟，那么电话局就会放弃原来的打算。问这个公用电话间的服务设施是否需要改变？答：（1）即去别处打电话的概率是0.3276。（2）。（3）当撤走一台电话时，此问题变成M/M/1/5排队模型。∴电话设施不会改变。2006年北京交通大学交通运输学院417管理运筹学考研真题

2006年北京交通大学交通运输学院417管理运筹学考研真题及详解北京交通大学2006年硕士研究生入学考试试卷考试科目：417管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（25分）设有如下的线性规划问题：（1）写出该线性规划的标准型；（10分）答：（2）求原规划的最优解和最优目标函数值。（15分）答：加入一个人工变量x7，利用单纯形法计算如下：cj－123－30000CBXBbx1’x2’x3’x3’’x4x5x7x60x4720x56－30x7440x640－111－11000－1－2[2]01002123－300100000013－300000x410[1/2]1/20011/200－3x3’’3－3/2－1/2－1101/2000x7131/20x6401/20003/2101000001－11/21/20003/200－1x1’201－3x3’’13011016002100－11320000－111000000100117000x7300x6400∴x1＝－x1’＝－20，x2＝x2’＋2＝2，x3＝x3’－x3’’＝－13；得到最优解X*＝[－20，2，－13]T，minz＝－55。二、（25分）标准型线性规划问题（minZ＝CX，AX＝b，X≥0）的最优单纯型表为：其中：x4，x5是对应于初始单位矩阵的松弛变量。试求：（1）求该标准型线性规划目标函数的系数c1－c5；答：松弛变量x4，x5的目标函数为0，，且由最终单纯形表可知：解得。（2）设该标准型线性规划的右端常数项为b，△b1，△b2分别为b的两个分量的增量，试分别对两个增量进行灵敏度分析，即求出△b1，△b2分别变化时的取值范围；答：当当，解得，解得；。（3）假定用b＋λ△b代替b，其中△b＝的最优基B*不变，求λ的变化范围，并求当，－∞＜λ＜＋∞，要使现行时的最优解；答：保持最优基B*不变，则要求解得，当时，最优解不发生变化，。所以X*＝[3，1]T，minz＝－9。（4）要使现行的最优基不变，求目标函数系数c1变化范围；答：保持最优基不变，各非基变量检验数认识非负，则：解得，。∴c1变化范围是[－3，－1]。（5）求两个约束的影子价格。答：由最终单纯形表可知，两个影子价格即两个松弛变量的检验数，即分别为3和1。三、（25分）某工厂安排某种生活必需品在以后四个月的生产计划。该产品可以在以后四个月的任一个月生产，不过受用工和原料价格的影响，不同的月份其生产成本不同，该产品在以后四个月的生产成本分别是12，10，15，18元，件。该产品以后四个月需要量分别是400，700，900和800件，考虑到生活必需品的要求，产品需要量必须加以满足。该工厂平常每月最多能生产700件，但在第二个月农闲时期工厂可以聘用临时工加班，加班后可增产300件，但生产成本每件增加3元。过剩产品每件存储费用是每月3元。试完成：（1）仿照运输问题建立使总成本最小的生产计划线性规划数学模型；（10分）答：设xij是第i个月生产供第j个月消费的产品数量，i＝1，2，2‘，3，4，j＝1，2，3，4，其中x2’表示第2个月加班完成的产品数量。z表示总成本。则由题意得线性规划数学模型：（2）用运输问题表上作业法求解。（10分）答：总供给量为700×4＋300＝3100；总需求量是400＋700＋900＋800＝2800，故设一虚拟消费月份5，需求量是300，成本是0，其他如xij（i<j），成本是∞。则化成产销平衡问题，利用沃格尔法得初始解如下：（括号内为分配量，[]内为检验数）消费月份1生产月份2345产量1（400）12[5]15[2]18[2]21（300）070022‘[∞][∞][∞][∞]400∞（700）10[0]0700∞（0）13（200）16（100）19（0）030013[0]16[3]34需求量∞[∞]∞[∞]700∞（700）15[0]18[1]070007003100∞[∞]900∞（700）18[1]800300所有空格检验数均为非负，故得最优解。即4个月份分别生产400件、1000件、700件和700件。（3）理论上讲该问题有几个最优基本可行解？（5分）答：因为存在检验数为0，故有无数个最优基本可行解。四、（25分）某城市公共交通公司共有公交客车1000辆，可投入超负荷和正常负荷两种状态运营，如果当年投入高负荷状态运营，年运量为20万人／台，且第一年投入高负荷运营时汽车年完好率为0.8，以后各年投入高负荷运营时每年完好率随车龄每年以0.1递减，如果投入正常负荷状态运营，年运量为15万人／台，第一年汽车年完好率为0.95，以后各年投入正常负荷运营时每年完好率随车龄以O．O5递减，试安排5年运量最大的运营方案。答：设第k年有xk（k＝1，2，3，4，5）辆车超负荷状运营，年初有sk辆完好车，则，s1＝1000辆，s2＝0.8x1＋0.9（s1－x1），sk＋1＝sk－xk*0.01－（sk－xk）*0.05（k＝2，3，4）。最优指标函数表示k年初状态为sk时，从第k年至第5年末的最大运量，K＝5时，。采用逆推方法计算如下：K＝4时，k＝3时，K＝2时，K＝1时，∴可知，第1年全部车辆正常运行，从第2年开始至第5年，所有车辆超负荷运营，可获得最大运营量为80341万人次。五、（15分）用割平面法求解下列IP问题：MaxZ＝8x1十5x2st．2x1＋3x2≤12x1－x2≤6x1，x2≥0且为整数答：首先用单纯形法计算其相应的线性规划问题cj8500CBXBbx1x20x312[2]30x461－1085x31x40616008x1613/21/200x400－5/2－1/210－7－40从上表中可以看出，已求得整数解XT＝[6，0]T，，maxz＝48。无需在用割平面法进行求解。六、（15分）试证明定理：可行流f*是最大流的充分必要条件是不存在关于f*的增广链。答：（1）充分性不存在关于f*的增广链，则对f*的任意一条弧都不能再进行调整，故现在的可行流流量已达到最大值，故可行流f*是最大流。（2）必要性（用反证法）可行流f*是最大流，假设存在关于f*的增广链，则总可以对f进行调整，调整量。则增广链上，正向弧，则整个可行流流量都增加，得到的新的可行流大于原可行流，则可知原可行流f*不是最大流，与题意相悖。七、（20分）某理发店只有一个理发师，来理发的顾客到达过程为Poisson流，平均到达间隔为20分钟。理发时间服从负指数分布，平均需要15分钟。试求：（1）理发店空闲的概率答：该问题属于M/M/1模型，理发店空闲的概率。（2）店内恰有3个顾客的概率答：店内恰有3个顾客的概率。（3）店内至少有1个顾客的概率答：店内至少有1个顾客的概率（4）在店内的平均顾客数。答：在店内的平均顾客数。（5）每位顾客在店内的平均逗留时间答：每位顾客在店内的平均逗留时间。（6）等待服务的平均顾客数答：等待服务的平均顾客数。（7）每位顾客平均等待时间答：每位顾客平均等待时间。（8）顾客在店内逗留超过10分钟的概率答：顾客在店内逗留超过10分钟的概率。2005年北京交通大学交通运输学院417管理运筹学考研真题

2005年北京交通大学交通运输学院417管理运筹学考研真题及详解北京交通大学2005年硕士研究生入学考试试卷考试科目：417管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（40分）已知线性规划问题（1）求线性规划问题的最优解（20分）：答：Cj1534000θiCBb000Cj－Zj8002120051000313143[4]5532434100100000010800/3300250050－1/40－1/4－1/410－3/4020020－2[1]011/420052503/415/43/40001000/3Cj－Zj04－11/40－13/41/4001001/40－13/4020020－2－5/411/4－1－11015Cj－Zj100－3/4111/40－13/40－11/400－3/410－1/4－1所以最优解，最优值＝800＋500＝1300。（2）求对偶问题的最优解（5分）；答：由最终单纯性表可得y1＝0，y2＝1/4，y3＝1。（3）当△b3＝－150时最优基是否发生变化？为什么？（5分）；答：出现了负值，所以最优解会发生变化。（4）求c2的灵敏度范围（5分）；答：Cj134000CBb041001/42002100－3/40－13/40－2111/4011/410100－3/4－1－11Cj－Zj3/4－7011－11/4003/4－44－所以，得。（5）如果x3的系数由[1，3，5]变为[1，3，2]最优基是否改变？若改变求新的最优解（5分）。答：Cj1534000CBb041001/420020－1/400[1]111/4－101－15Cj－Zj100－3/41－1/40－13/401/400－3/410－1/4－1031503/4200200011/411/2－5/4101－15Cj－Zj150－1/410－15/4001/40－1/23/4－1/40－1/2－3/4所以最优解，最优值＝600＋750＝1350。二、（20分）已知某运输问题其供需关系及单位运价表如下表所示：要求：用表上作业法找出最优调运方案。答：由于产销不平衡，虚拟一个销地B4，运费为O。即B1B2B3B4产量A142508A235307A313204销量4852首先，用伏格尔法求初始解，如下所示：（）内数据为解产地销地B1B22（8）5B3B40产量行差A1A2A34382233021153（5）0（2）71（4）3（0）2（0）04销量列差4228113511220其次，用位势法进行检验，得空格的检验数。B1B2B3B4uiA14A211A3170231vj021－2所有检验数均为正数，说明此时已得最优解。即最优调运方案为A1提供B1数量为8，A2提供给B3的量为5，提供给B4的量为2，A3提供给B1的量为4。可得最小运费16＋15＋0＋4＝35。三、（20分）某市共有6个区，每个区都可以设消防站，市政府希望设置消防站最少以便节省费用，但必须保证在城区任何地方发生火警时，消防车能在15分钟内赶到现场。据实地测定，各区之间消防车行驶时间如下表所示。建立该问题的规划模型。各区之间的行驶时间答：根据题中给定的约束条件，可建立如下的规划模型四、（30分）某公司有资金10万元，若投资于各项目（i＝1，2，3）的投资额为Xi时，效益分别为g1（x1）＝4x1，g2（x2）＝9x2，g3（x3）＝2x23问：如何分配投资数额才能使总效益最大？答：设为第k阶段初剩余的投资额。令最优指数函数表示第k阶段初状态为时，第k阶段到第3阶段的后部最优收益，则该问题的基本方程为（1）k＝3时，，这是一个简单的函数求极值问题，易知：当时，取得极大值，即。（2）k＝2时，这是一个非线性规划问题。令极小点，根据微积分知识可得。，极大值只可能在[0，s2]端点取得，当当时，时，，此时，此时；。（3）当k＝1时，当时，但此时当小点。比较[0，10]两个端点，＝0，时，，由微积分知识，可得200；＝10，是极40。所以。再由转移方程顺推，，所以。由于，因此，，最优目标函数值五、（20分）求下图所示的网络的最小费用最大流（每条弧旁边的数字是（bij，Cij））答：取为初始可行流。构造赋权有向图，并求出从到的最短路，如图（a）所示。在原网络图中，与这条最短路相应的增广链为。在上进行调整，，得。按照上述算法依次得到，流量依次为5，7，10，11，13。注意到中已无从到的最短路，所以为最小费用最大流。六、（20分）某厂拟用1名修理工人，已知平均送修的设备数λ＝0.2台／h，现有2种级别的工人可聘：A级工，其工作能力为μ1＝0.25台／h，工资每小时10元；B级工，其工作能力为μ2＝0.28台/h，工资每小时20元。因设备送修，平均每台每小时造成停工损失为40元。问应聘那一种工人，可使工厂的经济效益较高。答：用A级工，平均损失为0.2×20×40＋10＝170（元）。用B级工，平均损失为0.2×12.5×40＋20＝120（元）。所以应聘B级工，可使工厂的经济效益较高。

2004年北京交通大学交通运输学院管理运筹学考研真题

2004年北京交通大学交通运输学院管理运筹学考研真题及详解北京交通大学2004年硕士研究生入学考试试卷考试科目：管理运筹学注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评分！一、（30分）回答下列问题：1．什么是线性规划问题的基可行解？答：满足线性规划数学模型中的非负条件的基解为基可行解。2．什么是可行流？答：满足下列条件的网络流f称为可行流。（1）容量限制条件对每一弧（vi，vj）∈A，（2）平衡条件对于中间点，流出量＝流入量，即对每个i（i≠s，t），有。对于起点，记对于终点，记。式中，入量）。称为这个可行流f的流量，即发点的净输出量（或收点的净输3．什么是关于可行流f的增广链？答：设f是一个可行流，是网络的起点，是网络的终点，是从到的一条链，若满足下列条件：（1）在弧（2）在弧上，上，，即中每一前向弧是非饱和弧。，即中每一后向弧是非零流弧。称是关于可行流f的一条增广链。4．线性规划问题最优解共有几种可能？并写出各自相应的判别准则。答：（1）唯一最优解：当x≥0，且非基变量的检验数＜0；（2）无穷最优解：当x≥0，且非基变量的检验数≤0，且有为0。5．非标准指派问题：某大型工程有五个工程项目，决定向社会公开招标，建设公司A1，A2，A3参加招标承建，根据实际情况，可允许每家建设公司承建一项或二项工程。报价表如右，单位万元。如何将其化成标准的指派问题（只转化成标准指派问题即可，不要求求解）答：为将非标准指派问题转化为标准指派问题，需要使公司数目和工程数目一致，所以此题可虚拟一个工程项目B6，这个虚拟的项目由各公司承建的费用为0。又每件公司可承建一项或二项工程，所以将同一个公司虚拟成2个。即建立如下的报价表。487151204871512079171410079171410069128706912870二、（30分）某厂生产甲、乙两种产品，需要A、B两种资源，有关资料如下：（1）求使工厂获利润最大的生产计划（列出模型并求解）；答：设生产甲，乙则用单纯形法进行求解。Cj3400CBXBb00Cj－Zj61813110[2]014006402[1/2]01－1/24441/2101/28Cj－Zj100－234412002－11－11Cj－Zj00－2－1所以最优解，最优值＝12＋8＝20。（2）确定原最优基不变条件下，产品甲的单位利润的允许可变范围；答：若变为，则，所以。（3）若该厂准各出让资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学模型。答：（4）资源A、B的影子价格是多少？答：将对偶问题化为标准形式，用对偶单纯形法求解。Cj－6－800CBXBb00Cj－Zj－3－1－4－1－6－110[－2]01－8000－8－1[－1/2]01－1/20－1/221/21Cj－Zj－200－4－6－8Cj－Zj21100010－211－1－4－2所以最优解，最优值＝12＋8＝20。所以A的影子价格为2，B的影子价格为1。（5）试用此例的计算结果，验证和解释对偶理论中的互补松弛定理的正确性。答：由互补松弛条件YXs＝0，XYs＝0。由于，所以y1s＝y2s＝0，即对偶问题中的约束条件为严格的等。与上题中用对偶单纯形法所求的解相同，证明式，所以可得互补松弛定理的正确。对松弛定理的解释见教材。三、（20分）设有产量分别30，50，60的三个原料产地A1，A2，A3，欲将原料运往需求量分别为15，10，40，45的四个销地，运价表如下，试求运费最省的调运方案。答：由于产销不平衡，虚拟一个销地B5，构成产销平衡表，用伏格尔法求初始解。（）内数据为解产地销地B1B2B3B4B5产量行差A1A23（15）584（15）0303111174（10）86（10）0（30）5042222A31035（40）2（20）0602111销量列差15410140345230041321321212用位势法进行检验。B1B2B3B4B5uiA131202A22－1A3934－2vj3274－2由于存在负检验数，用闭回路法进行调整。（2，3）为调入格，调整量为min（10，40）＝10。得到如下新的分配。（）内数据为解产地销地B1B2B38B44（15）00（30）5（30）2（30）0B5A1A2A33（15）574（10）8（10）6103继续用位势法进行检验。B1B2B3B4B5uiA121A231011

A3923－2vj3374－1此时，所有检验数为非负，所以此为最优解，即A1运往销地B115，运往B415；A2运往销地B210，B310；A3运往销地B330，B430。最小费用为15×3＋15×4＋4×10＋8×10＋5×30＋2×30＝435。四、（25分）某工厂有100台机器，拟分四期使用，在每一期都有两种生产任务。根据经验，若把x1台机器投入第一种任务，则在本期结束时将有1／3x1台机器损坏报废。剩下的机器全都投入第二种生产任务，则有1／10的机器在期束损坏报废。如果干第一种任务时每台机器可获利润10，干第二种任务时每台机器可获利润7，问应如何分配使用机器以使四期的总利润最大（期末剩下的完好机器数量不限）？答：将此题看成一个4个阶段决策问题。令为状态变量，它表示第k阶段初拥有的完好机器数量；决策变量为第k阶段分配给第一种生产的机器数量，于是段分配给第二种生产的机器数量。为该阶状态转移方程为；设为第k阶段的收益，则令最优值函数表示由机器数量出发，从第k阶段开始到第4阶段结束时所获得的收益最大值，故有递推关系式：（1）k＝4时，因f4是x4的线性单调增函数，故得最大解（2）k＝3时，，相应的。故得最大解，相应的有。（3）k＝2时，当，相应的有。（4）k＝1时，当，相应的有。因s1＝100，所以＝2680（千元）。计算结果表明，第1阶段将100台机器投入第二种生产，第2阶段将90台机器投入到第二种生产，第3阶段将81台机器投入到第一种生产，第4阶段将54台机器投入到第一种生产。可得最大收益为2680千元。五、（25分）求如下图所示网络的最大流（弧旁的数字表示的是（容量，流量）），并指出截集。答：（1）标号过程①首先给标上②检查，在弧③检查，在弧④检查，在弧⑤检查，在弧；上，的标号为上，的标号为上，的标号为上，的标号为；；；。因有了标号，故转入调整过程。（2）调整过程按点的第一个标号找到一条增广链，按图的可行流：在上调整f．调整后得如下（3）对得到的可行流进行标号：①首先给标上②检查，在弧③检查，在弧④检查，在弧；上，的标号为上，的标号为上，的标号为；；。因有了标号，故转入调整过程。（4）调整过程按点的第一个标号找到一条增广链，按图的可行流：在上调整.调整后得如下（5）对得到的可行流进行标号：①首先给标上②检查，在弧③检查，在弧；上，的标号为上，的标号为；；④检查，找不到可以标号的点，故标号无法再继续，算法结束。最大流量为：7＋4＝11。割集为可行流图中的虚线所示。六、（20分）某修理店只有一个修理工人，来修理的顾客到达次数服从普阿松分布，平均每小时4人，修理时间服从负指数分布，平均需6分钟，求（1）修理店空闲的概率；答：（2）店内有3个顾客的概率；答：。（3）店内至少有一个顾客的概率；答：。（4）在店内顾客的平均数；答：。（5）在店内平均逗留时间；答：。（6）等待服务的顾客平均数；答：。（7）平均等待修理（服务）时间。答：。（8）如果店内已有3个顾客，那么后来的顾客即不在排队，其他条件相同，求店内空闲的概率和店内顾客平均数。答：即系统的容量限制为N＝32003年北方交通大学交通运输学院管理运筹学考研真题

2003年北方交通大学交通运输学院管理运筹学考研真题及详解北方交通大学2003年硕士研究生入学考试试卷考试科目：管理运筹学注意事项；答案一律写在答题纸上，写在试卷上的不予装订和评分。一、已知线性规划问题（35分）1．试用单纯形法求最优解；答：加入松弛变量之后利用单纯形法求解如下：cj23100CBXBbx1x2x3x41x500x4310x591211[4]73101000x43/4[3/4]0－3/413x29/41/417/45/40－17/40－1/41/4－3/402x1113x22000－14/3－1/3－1/31/313/20－3/2－5/3－1/3得到最优解，X*＝[1，2，0]T，maxz＝8。2．写出原问题的对偶问题，并根据对偶理论，直接求出对偶问题的最优解；答：，根据对偶理论，得其最优解Y*＝[5/3，1/3]。3．如果增加一个新的变量x6（x6≥0），P6＝C6＝7，原问题的最优解有何变化；答：在最终单纯形表中，，xk的约束变量为，检验数。所以最优解发生变化，继续计算如下：cj2310072x11103x220100－14/3－1/3[1]3/2－1/31/30－3/2－5/3－1/357xk1103x2201－50－14/3－1/31[3/2]－1/31/307/2－25/34/307xk7/312/3010/9－1/911x34/302/31－2/9[2/9]0－68/95/90－5－7/307xk3110x56031/219/2－1010100－5－4－5/2－7得最优解，X*＝[0，0，0，3]，maxz＝21。4．如果添加一个新的约束X1＋2X2＋X3≤4，原问题的最优解有何变化。答：加入一个松弛变量x6，重新计算如下：cjCBXBbx1x2x30x4310x5910x6412231000x4x5x61000100010001147[2]1310x41[1/2]01/210－1/20x51－10501－23x221/211/2001/21/20－1/200－3/22x1210x5303x210001061020－121－3－1010－1－10－1得到最优解X*＝[2，1，0]T，maxz＝7。二、有三家企业A1、A2和A3生产同一种产品供应三个用户Bl，B2和B3，Al企业至少要发出60个单位的产品，它最多能生产ll0个单位产品：A2企业必须发出70个单位产品：A3企业至少发出40个单位的产品。各用户的需求量分别为100、40和60个单位。生产企业到用户的单位运价见下表。用表上作业法求该运输问题的最优解。（20分）答：由题意设生产企业A1‘产量是30，其到个用户的运价与A1相同；A3’产量是30，其到各用户运价与A3相同。此时产量是230单位，故再增加一虚拟用户B4，需求量是30，A1、A2、A3到它的运价皆是∞，两虚拟企业到它的运价是0，则可得运输平衡问题。用位势法得初始方案（括号内数据）并检验（[]内数据）如下：用户生产企业B1B3B3B4产量A1A1’302[2]4303[∞]∞60[0]2[2]43030030A2A3A3’需求量701[4]5[4]6[∞]∞70[1]3402[1]4[∞]∞40[1]302[1]430030100406030可以得此即为最优解。最优方案即用户生产企业B1B3B3产量A1A23070609070A3需求量40401004060三、甲、乙、丙、丁和戊五条生产线去生产A、B、C、D和E五种产品。已知每条生产线生产各种产品所产生的效益如下表所示，试确定总效益为最大的指派方案。（20分）答：用表中最大元素10减去每一个元素，得到标准形式的最小化指派问题：指派任务得，显然◎的个数小于5个，划线覆盖0元素。未被覆盖区域数据减去1，同时划线列加上1，并重新指派任务得，继续划线，未被覆盖区域数据减去1，同时划线列加上1，并重新指派个，指派成功。则◎的个数等于5即：甲生产线生产产品D；乙生产线生产产品B；丙生产线生产产品C；丁生产线生产产品A，戊生产线生产产品E，总效益最大为37。四、求下图从Vs至Vt的最小费用最大流。图中弧旁数字为（费用，容量）。（20分）答：（1）取f（0）＝0为初始可行流。（2）构造赋权图W（f（0）），用Dijkstr