运筹学期中考试答案

南京信息工程大学滨江学院期中考试试卷 2009 2010 学年 第 一 学期 运筹学原理 课程期中试卷本试卷共 页；考试时间 分钟；任课教师 刘晓波 ；出卷时间 2009 年 11 月 学院 专业 年级 班 学号 姓名 得分 一、计算题（70分）1.已知线性规划问题：（20分） 求：（1）、用图解法求解；（10分） （2）、写出其对偶问题；（10分）解：（1）、 x2 2 Z Z x1x1-x2=-10 2 40.5x1+x2=2 由图可知： 解之得： 则最优解为X=（4，0）T Max Z=-4-0=-4 为唯一最优解 （2）、该问题的对偶问题为： 2、已知下列线性规划问题：（30分）求：（1）、用单纯形法求解，并指出问题属于哪一类解；（20分） （2）、若增加一约束条件，则最优解如何变化？（10分）解：（1）、将原问题划为标准形得： =60 6-33000b0603111000202-2401006033-30016-330006-33000b03004-51-3/206101-1201/2003006-90-3/2103-90-306-33000b0100011-1/2-2/3615101/201/41/6-3501-3/20-1/41/600-9/20-9/4-1/2所以X=（15，5，0，10，0，0）T 为唯一最优解 Max Z=6*15-3*5=75 （2）、将X=（15，5，0，10，0，0）T代入给出的约束条件中可知，最优解满足此约束条件。所以，最优解不变。 3、（20分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1 B2 B3 B4siA1A2A31 2 3 48 7 6 59 10 11 9108015dj8 22 12 181）用最小费用法求初始运输方案，并写出相应的总运费；（10分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 地产用费地销B1B2B3B4SiA112341082A2876520218A3910119302010dj8221218 606082B1B2A1初始方案：218B3B4A22010B2B3A3Z=18+22+62+518+1020+1110=4242）用闭回路法，求检验数：地产用费地销B1B2B3B4SiA11230421082A284726520218A390101191302010dj8221218 6060=10，其余0选作为入基变量迭代调整。用表上闭回路法进行迭代调整：地产用费地销B1B2B3B4SiA11231431082A283716520128A390101119302010dj8221218 6060调整后，从上表可看出，所有检验数0，已得最优解。最优方案为：82B1B2A1128B3B4A22010B2B4A3最小运费Z=18+22+612+58+1020+910=414二、简述题(2*15分=30分) 1. 用图解法说明线性规划问题单纯形法的解题思想。 2. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。1、在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大（求Zmax），求出新解，计算出方案机会成本后，得出相应检验数，当所有的CjZj0时即得最