运筹学试题（含参考答案）VIP

1、运筹学试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，若存在两个最优解时，必有 相邻的顶点是 最优解。2、树图中，任意两个顶点间有且仅有 一条链 。3、线性规划的图解法适用于决策变量为 两个 线性规划模型。4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为 松弛变量 。5、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。6、运输问题中求初始基本可行解的方法通常有 最小费用法 与 西北角法 两种方法。7、称无圈的连通图为树，若图的顶点数为p，则其边数为 p1 。二、（每小题5分，共10分）用图解法求解下列线性规划问题： 、1）ma

2、x z = 6x1+4x2 、 2）min z =2x1+x2解：从上图分析，可行解域为abcde，最优解为e点。由方程组 解出x1=5，x2=3x*=（5，3）tmin z =z*= 25+3=13三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：

3、设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x30，设z是产品售后的总利润，则max z =10x1+6x2+4x3s.t.2）用单纯形法求最优解：加入松弛变量x4，x5，x6，得到等效的标准模型：max z =10x1+6x2+4x3+0 x4+0 x5+0 x6s.t.列表计算如下：cbxbb1064000lx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010640000x4400（3/5）1/211/100200/310x16012/51/201/1001500x618006/5501

4、/5115010450100210106x2200/3015/65/31/6010x1100/3101/62/31/600x610000420110620/310/32/30008/310/32/30x*=（，0，0，0，100）tmax z =10+6=四、（10分）用大m法或对偶单纯形法求解如下线性规划模型：min z =540x1450x2720x3解：用大m法，先化为等效的标准模型：max z/ =540x1450x2720x3s.t.增加人工变量x6、x7，得到：max z/ =540x1450x2720x3mx6mx7s.t大m法单纯形表求解过程如下：cbxbb5404507200

5、0mmlx1x2x3x4x5x6x7mx670359101070/3mx730（9）53010130/9=10/312m10m12mmmmm12m54010m45012m720mm00mx660010/3（8）11/311/360/8=2.5540x110/315/91/301/901/910/3/1/3=10-300+10/3m-8m180mm/3+60mm/3600-150+10/3m8m-540mm/3600m/3+60720x315/205/1211/81/241/81/2415/2/5/12=18540x15/61（5/12）01/241/81/241/85/6/5/12=25405

6、72720135/2475/12135/275/201250135/2475/12135/2m75/2m720450x320/31011/61/61/61/6x2212/5101/103/101/103/1057003604507207515751518000751575m15m该对偶问题的最优解是x*=（0，2，0，0）t最优目标函数值min z =（5700）=5700 五、（12分）给定下列运输问题：（表中数据为产地ai到销地bj的单位运费）b1 b2 b3 b4sia1a2a320 11 8 65 9 10 218 7 4 151015dj3 3 12 121）用最小费用法求初始运输方

7、案，并写出相应的总运费；（4分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 地产用费地销b1b2b3b4sia1201186532a2591021010a318741151122dj331212 303032b1b2a1初始方案：1212b2b4a3b310a2b4z=203+112+210+71+412+12=1592）用闭回路法，求检验数：地产用费地销b1b2b3b4sia120118061532a25129110521010a3182741151122dj331212 3030=12

8、0，其余0选作为入基变量迭代调整。用表上闭回路法进行迭代调整：地产用费地销b1b2b3b4sia12011812611523a25913101521019a318147124115123dj331212 3030再选作为入基变量迭代调整。地产用费地销b1b2b3b4sia1201211861532a259110521037a31814704115105dj331212 3030调整后，从上表可看出，所有检验数0，已得最优解。最优方案为：32b2b3a137b1b4a2105b3b4a3最小运费z=113+82+53+27+410+15=123六、（8分）一个公司经理要分派4个推销员去4个地区推

9、销某种商品。4个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：d1d2d3d4甲35272837乙28342940丙35243233丁24322528问：公司经理应怎样分派4个推销员才使总利润最大？解：用求极大值的“匈牙利法”求解。效率矩阵表示为：行约简mcijm=40 标号列约简 所画（）0元素少于n（n4），未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：标号未被直线覆盖的最小元素为cij=2,在未被直线覆盖处减去2，在直线交叉处加上2。 得最优解：使总利润为最大的分配任务方案为：甲d1，乙d4，丙d3，丁d2此时总利润w=35+

10、40+32+32=139七、（6分）计算下图所示的网络从a点到m点的最短路线及其长度。11b11745785mg1317da9995684hiefc68解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：21121111b75481172616505mg1317da9989564hiefc6818109最佳策略为：acfgm此时的最短距离为8+8+5+5=26八、（8分）用pt标号法求下图从至的最短路。（需写出最短路线）v8v5v2313971v115v66226v91v48v174413211v 109v7v3解：此为网络分析之“最短路问题”，可用顺向追踪“tp标号法”解决

11、如下：v5v2v81132v103120410v68v423971v1156826v9171441321v 109v7v38715v1到v7的最短路线是：v1v2v5v9v8v11，最短距离2+1+1+7+9=20。九、（10分）用找增广链的方法求如下网络的最大流。（需写出相应的增广链）（弧旁的数字为该弧容量）v4v11734423vtv3vs853104v5v2解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给vs标上（0，）；2、检查vs，在弧（vs，v1）上，fs1=0，cs1=4，fs1cs1，给v1标号(s，(v1)

12、，其中，（s，4）v4v117344（0，）23vtv3vs853104v5v2（s，10）同理，给v2标号(s，(v2)，其中，3、检查v1，在弧（v1，v3）上，f13=0，c13=3，f13c13，给v3标号(1，(v3)，其中，（3，3）（s，4）v4v117344（0，）23vtv3vs（1，3）853104v5v2（2，4）（s，10）检查v3，同理，给v4标号(3，(v4)，其中，检查v2，同理，给v5标号(2，(v5)，其中，4、检查v4，在弧（v4，vt）上，f4t=0，c4t=7，f4tc4t，给vt标号(4，(vt)，其中，vt得到标号，标号过程结束。（3，3）（s，4）

13、v4v117344（4，3）（0，）23vtv3vs（1，3）853104v5v2（2，4）（s，10）调整过程：从vt开始逆向追踪，找到增广链。（3，3）（s，4）v4v117344（4，3）（0，）23vtv3vs（1，3）853104v5v2（2，4）（s，10）（vs，v1，v3，v4，vt），=3，在上进行流量=3的调整，得可行流f 如图所示：v4v1（1，0）（7，3）（4，3）（4，3）（3，3）（2，0）（3，0）vtv3vs（10，0）（8，0）（5，0）（3，0）（4，0）v5v2去掉各点标号，从vs开始，重新标号。（3，1）（s，1）v4v1（1，0）（7，3）（4，3）

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

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

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

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

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

19、v2去掉各点标号，从vs开始，重新标号。（-t，1）（-3，1）v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（3，1）（s，7）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（-t，1）（-3，1）v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（3，1）（s，7）（vs，v2，v3，v5，vt），=2，在上进行流

20、量=2的调整，得可行流f 如图所示：v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）vtv3vs（10，5）（8，5）（5，5）（3，3）（4，2）v5v2去掉各点标号，从vs开始，重新标号。（-t，2）（-3，2）v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（5，2）（2，2）（3，3）（0，）vtv3vs（-5，2）（10，5）（8，5）（5，5）（3，3）（4，2）v5v2（2，2）（s，5）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（-t，2）（-3，2）v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（5，

21、2）（2，2）（3，3）（0，）vtv3vs（-5，2）（10，5）（8，5）（5，5）（3，3）（4，2）v5v2（2，2）（s，5）（vs，v2，v5，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）vtv3vs（10，7）（8，7）（5，5）（3，3）（4，4）v5v2去掉各点标号，从vs开始，重新标号。v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）（0，）vtv3vs（10，7）（8，7）（5，5）（3，3）（4，4）v5v2（s，3）标号至点v2：标号过程无法进行，所以 f 即为最大流。v4v1（1，1）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）（0，）vtv3vs（10，7）（8，7）（5，5）（3，3）（4，4）v5v2（s，3）=vs，v2，=v1，v3，v4，v5，vt截集（，）=（vs，v1），（vs，v3），（v2，v3），（v2，v5）v（ f ）=c（，）=4+3+3+4=14苦蕾虚润侣皮婚于梦阂戒扣祸活裕踊雨内存橱她圆爷注臼垦曹厕魂剪藐稚煤敌夯蔫懒衙谐萎蘸挛擅父恬伎敛刘碧藤巴唯折翠香雪卑执纪汐蝉先