《运筹学》模拟试题及参考答案

《运筹学》模拟试题及参考答案一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。)1.图解法提供了求解线性规划问题的通用方法。 ()2.用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj≥0，则问题达到最优。 ()3.在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。 ()4.满足线性规划问题所有约束条件的解称为基本可行解。 ()5.在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。 ()6.对偶问题的目标函数总是与原问题目标函数相等。 ()7.原问题与对偶问题是一一对应的。 ()8.运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。 ()9.指派问题的解中基变量的个数为m＋n。 ()10.网络最短路径是指从网络起点至终点的一条权和最小的路线。 ()11.网络最大流量是网络起点至终点的一条增流链上的最大流量。 ()12.工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。 ()13.在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。 ()14.单目标决策时，用不同方法确定的最佳方案往往是一致的。 ()15.动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ()二、简述题1.用图解法说明线性规划问题单纯形法的解题思想。2.运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。3.建立动态规划模型时，应定义状态变量，请说明状态变量的特点。三、填空题1.图的组成要素；。2.求最小树的方法有、。3.线性规划解的情形有、、、。4.求解指派问题的方法是。5.按决策环境分类，将决策问题分为、、。6.树连通，但不存在。四、下列表是线性规划单纯形表（求Zmax），请根据单纯形法原理和算法。1.计算该规划的检验数 C Cj → 3 2 0 0 0Ci xB x1 x2 x3 x4 x53 x1 3 1 0 -1 02 x3 4 0 1 1 1/2 0 zj 3 3.5 2 -2 0 cj－zj 2.计算对偶问题的目标函数值3.确定上表中输入，输出变量五、已知一个线性规划原问题如下，请写出对应的对偶模型六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。BB110710710610C110610C181258125514FS514FS6613766137C210A2C210A29B9B3七、自己选用适当的方法，对下图求最小(生成)树。VV1233523356V3V2V4V5V6八、用标号法求下列网络V1→V7的最短路径及路长。VV1V7V5V6V4V3V2543531761731九、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。223145651249105094十、某企业生产三种产品A1、A2、A3。每种产品在销售时可能出现销路好(S1)，销路一般(S2)和销路差(S3)三种状态，每种产品在不同销售状态的获利情况(效益值)如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。状态效益值状态效益值产品

S1

S2

S3A13010-6A220129A3151312(表1)十一、已知运输问题的运价表和发量和收量如表2所示，请用最小元素法求出运输问题的一组可解释。BB1B2B3B4A1291279A213524A31042653546(表2)十二、下列表3是一个指派问题的效率表(工作时间表)，其中Ai为工作人员(i=1,2,3,4)、Bj为工作项目(j=1,2,3,4)，请作工作安排，使总的工作时间最小。BB1B2B3B4A14174A22235A35643A46324 参考答案一、判断题(1)×(2)√(3)√(4)×(5)√(6)×(7)√(8)√(9)×(10)√(11)×(12)×(13)√(14)×(15)×二、简述题1、在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大（求Zmax），求出新解，计算出方案机会成本后，得出相应检验数，当所有的Cj–Zj≤0时即得最优解。2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用单纯形法求解，而用简单的表上作业法求解。3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性的特征要求。三、填空题1.树2.破圈法和避圈法3.可行解、退化解、无界解、多重解4.匈牙利法5.确定性决策，不确定性决策，风险性决策。6.圈。四. c cj → 3 2 0 0 0 0Ci X0 b X1 X2 X3 X4 X5 X6 (3) X1 3 1 0 1/2 -1 0 1/2(2) X2 4 0 1 1 1/2 -1 0 Zj 3 2 7/2 -2 -2 3/2 Cj–Zj 0 0 (-7/2) (2) 2 -3/22.Smin=153.X4输入，Xi输出。五、Zmax=-7y1+16y2B1B1SA2710B39C213FC110710512149610568(32)(27)(17)(10)(0)(13)(16)(26)(18)S—A1—B1—C1—F32七、5252V1V2V44353V3V5V6424最小树为图中双线所示，最小树长14VV2V5V7V6V2V4V1(v1,0)(v1,4)(v1,6)(v1,13)(v6,10)(v3,9)(v5,7)(v1,3)(v1,5)431573175631八、最短路径：v1→v3→v5→v6→v7L①②①②④⑥③⑤4012510994550102031200102731620十、

S1

S2

S3

maxA13010-630A22012920A315131215选方案A1十一、BB1B2B3B4aiA12⑨12⑦9A2①35②6A310④②65bj3746………||||||||||||||||33436十二、BB1B2B3B4A14①74A2②235A3564③A463②4 B1 B B1 B2 B3 B4 3 … 0 … 6 … 3 | | | | | | | 0 … 0 … 1 … 3 | | | | | | | 2 … 3 … 1 … 0 | | | | | | | 4 … 1 … 0 … 2S=8(表3)《运筹学》试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，若存在两个最优解时，必有相邻的顶点是最优解。2、树图中，任意两个顶点间有且仅有一条链。3、线性规划的图解法适用于决策变量为两个线性规划模型。4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变量。5、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。6、运输问题中求初始基本可行解的方法通常有最小费用法与西北角法两种方法。7、称无圈的连通图为树，若图的顶点数为p，则其边数为p－1。二、（每小题5分，共10分）用图解法求解下列线性规划问题：⑴⑵⑶⑷⑸⑴⑵⑶⑷⑸、⑹

⑵⑶⑷、⑸⑵⑶⑷、⑸⑹⑴解：从上图分析，可行解域为abcde，最优解为e点。由方程组解出x1=5，x2=3∴X*==（5，3）T∴minz=Z*=2×5+3=13三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x3≥0，设z是产品售后的总利润，则maxz=10x1+6x2+4x3s.t.2）用单纯形法求最优解：加入松弛变量x4，x5，x6，得到等效的标准模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表计算如下：

CBXBb1064000θLx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010↑640000x4400（3/5）1/21－1/100200/310x16012/51/201/1001500x618006/550－1/51150104501002↑－10－106x2200/3015/65/3－1/6010x1100/3101/6－2/31/600x6100004－20110620/310/32/3000－8/3－10/3－2/30∴X*=（，，0，0，0，100）T∴maxz=10×+6×=四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：minz=540x1＋450x2＋720x3解：用大M法，先化为等效的标准模型：maxz/=－540x1－450x2－720x3s.t.增加人工变量x6、x7，得到：maxz/=－540x1－450x2－720x3－Mx6－Mx7大M法单纯形表求解过程如下：

CBXBb－540－450－72000－M－MθLx1x2x3x4x5x6x7－Mx670359－101070/3－Mx730（9）530－10130/9=10/3－12－10－12MM－M－M12M－54010M－4512M－72－M－M00－Mx660010/3（8）－11/31－1/3－540x110/315/91/30－1/901/910/3/1/3=10-300+10/3-8M－－M－M/3+60－MM/3－600-150+10/38M-540MM/3－600－M/3+60－720x315/205/121－1/81/241/8－1/2415/2/5/12=18－540x15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450x320/3－1011/61/61/6－1/6x2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴该对偶问题的最优解是x*=（0，2，，0，0）T最优目标函数值minz=－（－5700）=5700

五、（12分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1B2B3B4siA1A2A32011

86

59

10

2

187

4

15

1015dj

33

12121）用最小费用法求初始运输方案，并写出相应的总运费；（4分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销地产用费地销B1B2B3B4SiA1201186532××A25910210×××10A31874115×1122dj331212303032B32B1B2A11212B1212B2B4A3B310A2B4Z=20×3+11×2+2×10+7×1+4×12+1×2=1592）①用闭回路法，求检验数：地产用费地销地产用费地销B1B2B3B4SiA12011806－1532××A25129－110－5210×××10A318－274115×1122dj3312123030∵=12＞0，其余≤0∴选作为入基变量迭代调整。②用表上闭回路法进行迭代调整：地产用费地销地产用费地销B1B2B3B4SiA12011812611523××A259－1310－152101××9A318－147－124115××123dj3312123030再选作为入基变量迭代调整。地产用费地销地产用费地销B1B2B3B4SiA120－121186－15×32×A259－110－52103××7A318－14704115××105dj3312123030调整后，从上表可看出，所有检验数≤0，已得最优解。∴最优方案为：332B2B3A13737B1B4A2105B3B4A3最小运费Z=11×3+8×2+5×3+2×7+4×10+1×5=123六、（8分）一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：D1D2D3D4甲35272837乙28342940丙35243233丁24322528问：公司经理应怎样分派4个推销员才使总利润最大？解：用求极大值的“匈牙利法”求解。效率矩阵表示为：行约简M－CijM=40行约简M－CijM=40标号列约简所画（）0元素少于n（n＝4），未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：标号列约简√√√√√√标号未被直线覆盖的最小元素为cij=2,在未被直线覆盖处减去2，在直线交叉处加上2。标号∴得最优解：∴使总利润为最大的分配任务方案为：甲→D1，乙→D4，丙→D3，丁→D2此时总利润W=35+40+32+32=139七、（6分）计算下图所示的网络从A点到M点的最短路线及其长度。11B11B117457117457885MG1317DA5MG1317DA9999956895684HIEFC4HIEFC6868解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：21121121121111B11B754811775481172616502616505MG1317DA5MG1317DA9999895689564HIEFC4HIEFC68681810918109最佳策略为：A→C→F→G→M此时的最短距离为8+8+5+5=26八、（8分）用P→T标号法求下图从至的最短路。（需写出最短路线）v8vv8v5v231313971v115v6623971v115v66226v91v48v126v91v48v1744132174413211v109v7v31v109v7v3解：此为网络分析之“最短路问题”，可用顺向追踪“TP标号法”解决如下：v5v2v8v5v2v81132v1031v103120410v68v423971v115620410v68v423971v1156826v91826v91714413271441321v109v7v31v109v7v387158715v1到v7的最短路线是：v1→v2→v5→v9→v8→v11，最短距离2+1+1+7+9=20。

九、（10分）用找增广链的方法求如下网络的最大流。（需写出相应的增广链）（弧旁的数字为该弧容量）v4v4v1117344734423vtv3vs23vtv3vs85310853104v5v24v5v2解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特—富克尔逊算法）”解决如下：㈠标号过程：1、给vs标上（0，∞）；2、检查vs，在弧（vs，v1）上，fs1=0，Cs1=4，fs1<Cs1，给v1标号(s，β(v1))，其中，（s，4）（s，4）v4v11173447344（0，∞）23vtv3vs（0，∞）23vtv3vs85310853104v5v24v5v2（（s，10）同理，给v2标号(s，β(v2))，其中，3、检查v1，在弧（v1，v3）上，f13=0，C13=3，f13<C13，给v3标号(1，β(v3))，其中，（3，3）（s，4）（3，3）（s，4）v4v11173447344（0，∞）23vtv3vs（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）检查v3，同理，给v4标号(3，β(v4))，其中，检查v2，同理，给v5标号(2，β(v5))，其中，4、检查v4，在弧（v4，vt）上，f4t=0，C4t=7，f4t<C4t，给vt标号(4，β(vt))，其中，vt得到标号，标号过程结束。（3，3）（s，4）（3，3）（s，4）v4v11173447344（4，3）（0，∞）23vtv3vs（4，3）（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）㈡调整过程：从vt开始逆向追踪，找到增广链。（3，3）（s，4）（3，3）（s，4）v4v11173447344（4，3）（0，∞）23vtv3vs（4，3）（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）µ（vs，v1，v3，v4，vt），=3，在µ上进行流量=3的调整，得可行流f'如图所示：v4v4v1（1，0）（1，0）（7，3）（4，3（7，3）（4，3）（4，3）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，0）（8，0）（5，0）（3，0）（10，0）（8，0）（5，0）（3，0）（4，0）v5v2（4，0）v5v2去掉各点标号，从vs开始，重新标号。

（3，1）（s，1）（3，1）（s，1）v4v1（1，0）（1，0）（7，3）（4，3）（4，3）（3，3）（7，3）（4，3）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，0）（8，0）（5，0）（3，0）（2，3）（10，0）（8，0）（5，0）（3，0）（2，3）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，10）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（3，1）（s，1）（3，1）（s，1）v4v1（1，0）（1，0）（7，3）（4，3）（4，3）（3，3）（7，3）（4，3）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，0）（8，0）（5，0）（3，0）（2，3）（10，0）（8，0）（5，0）（3，0）（2，3）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，10）µ（vs，v2，v3，v4，vt），=1，在µ上进行流量=1的调整，得可行流f'如图所示：

v4v4v1（1，0）（1，0）（7，4）（4，4（7，4）（4，4）（4，3）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，1）（8，0）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2去掉各点标号，从vs开始，重新标号。（1，1）（s，1）（1，1）（s，1）v4v1（1，0）（1，0）（7，4）（4，4）（4，3）（3，3）（7，4）（4，4）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。

（1，1）（s，1）（1，1）（s，1）v4v1（1，0）（1，0）（7，4）（4，4）（4，3）（3，3）（7，4）（4，4）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）µ（vs，v1，v4，vt），=1，在µ上进行流量=1的调整，得可行流f'如图所示：v4v4v1（1，1）（1，1）（7，5）（4，4）（4，（7，5）（4，4）（4，4）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，1）（8，0）（5，0）（3，1）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2去掉各点标号，从vs开始，重新标号。

（5，2）（-3，2）v4（5，2）（-3，2）v4v1（1，1）（1，1）（7，5）（4，4）（4，4）（3，3）（7，5）（4，4）（4，4）（3，3）（4，2）（2，0）（3，0）（0，∞）vtv3vs（4，2）（2，0）（3，0）（0，∞）vtv3vs（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（5，2）（-3，2）v4（5，2）（-3，2）v4v1（1，1）（1，1）（7，5）（4，4）（4，4）（3，3）（7，5）（4，4）（4，4）（3，3）（4，2）（2，0）（3，0）（0，∞）vtv3vs（4，2）（2，0）（3，0）（0，∞）vtv3vs（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）µ（vs，v2，v5，v4，vt），=2，在µ上进行流量=2的调整，得可行流f'如图所示：

v4v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（7，7）（4，4）（4，4）（3，3）（2，2）（3，0）vtv3vs（2，2）（3，0）vtv3vs（10，3）（8，0）（10，3）（8，0）（5，0）（3，1）（4，2）v5（4，2）v5v2去掉各点标号，从vs开始，重新标号。（-t，3）（-3，3）v4（-t，3）（-3，3）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，3）（2，2）（3，0）（0，∞）vtv3vs（5，3）（2，2）（3，0）（0，∞）vtv3vs（s，3）（10，3）（8，0）（5，0）（3，1）（s，3）（10，3）（8，0）（5，0）（3，1）（4，2）v5v2（4，2）v5v2（3，3）（（3，3）（s，7）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。

（-t，3）（-3，3）v4（-t，3）（-3，3）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，3）（2，2）（3，0）（0，∞）vtv3vs（5，3）（2，2）（3，0）（0，∞）vtv3vs（s，3）（10，3）（8，0）（5，0）（3，1）（s，3）（10，3）（8，0）（5，0）（3，1）（4，2）v5v2（4，2）v5v2（3，3）（（3，3）（s，7）µ（vs，v3，v5，vt），=3，在µ上进行流量=3的调整，得可行流f'如图所示v4v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）vtv3vs（2，2）（3，3）vtv3vs（10，3）（8，3）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2去掉各点标号，从vs开始，重新标号。

（-t，1）（-3，1）v4（-t，1）（-3，1）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，∞）vtv3vs（5，1）（2，2）（3，3）（0，∞）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2（3，1）（（3，1）（s，7）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（-t，1）（-3，1）v4（-t，1）（-3，1）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，∞）vtv3vs（5，1）（2，2）（3，3）（0，∞）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2（3，1）（（3，1）（s，7）µ（vs，v2，v3，v5，vt），=2，在µ上进行流量=2的调整，得可行流f'如图所示