12-13运筹学32答案

1、上海海洋大学试卷学年学期2012_ 20 13学年第1学期考核方式闭卷课程名称运筹学A/B卷(B)卷课程号1107401学分2学时32题号-一一二三四五六七八九十总分分数阅卷人诚信考试承诺书本人郑重承诺：我已阅读且透彻理解了“上海海洋大学学生考场规则”和“上海海洋大学学生违反校纪校规处理规定”，承诺在考试中自觉遵守，如有违反，按有关条款接受处理。承诺人签I期一、（10分）写岀下列线性规划问题的对偶问题：IMin Z = -5%! - 6X2 -7X3考生姓名：学号：专业班名：Xy + 5 尤 2 3 退一15-5Xj -6X2+10X3 < 20s.*1 *2 *3t.<= 5X1

2、 <0,X2>0,X3不受限制Maxw = 15y x +20y2 -5y3-y-5y 2 + y3 <-5解 5ji 6y2-y3 <-6-3）1 + 10,2-,3 = -7M >0,y2<0,y3不受限制、（15分）、已知线性规划问题：Max Z =耳 + 2X2 + 3X3 + 4x4尤+ 2X2 + 2X3 + 3X4 < 202x +X2 + 3x3 + 2x4 < 20x. > 0 , i 其对偶问题的最优解为 YM. 2, 丫 2*二0.2，试用对偶的互补松弛性求解原问题的最优 解。Max w = 20A + 20y2Ai+

3、2y 2 >1解：2 + % Z 2 2*+3s?t? <为 2 3 3A+2A >47i 2 0,光 2 0%+2 力- *舄 =1 2 乂 + y2 -y& = 2 2 乂+3 兜一 乂，=3变为标准型为3 乂+2%一打=4 丁 1，力，七，乂 2，劣，尺，NO因为最优解为 丫1*=1.2,=。丫 2*=0. 2,所以 ysi = 0.4, 乂，= 0.6,舄=°，儿根据对偶的互补松弛性，.%七+工 2义，+ 土以3 +4儿=0 ,所以X=£ =02x,+3x4=20 %C 所以 3X3+ 2X4 = 2CC，解得土 = 了 4=4三、(15分

4、)给定线性规划问题min z = _ 邑 + 2X2 +X3+ X2 + X3 < 6s.t.< 2x1 -X2 <4xy>0( j = 1,2,3)它的最优表如下：XIX2X3X4X5bX2111106X53011110考虑下面两个问题：（1）把q=-1改为4,求原问题的最优解C2）讨论c?在什么范围内变化时原来的最优解也是原问题的最优解。解：（1）在最优单纯形表中，由于也是非基变量，因此，改变叫对应的判别数G,在现行基下，也的判别数为九-zc = 3 - （-1-4） = -2 < 0 ,在此基础上继续迭代XIX2X3X4X5bX21111 06X53011

5、110-2012 021XX4X5bXl2X3X2012/32/31-1/38/3X5101/31/31/30/'13A005/38/32/36513最优解为（!,x2,x3）= （ a， §o）,目标函数的最优值为C2）由于想是基变量，因此，改变W对应的判别数 C2,因此改变C2将影响各个判别数，设 C2改变为C;于是有:'3 + （ c； -2）= I + c ；I + （ c； -2）*l = -1 + c ；'2 + （ c； -2）*l = c ；0 + （ c； -2）*0 = 0令所有判别数大于等于0解得c；>1,因此当c; 21时原来的最

6、优解也是新问题的最优解。四、(20分)已知运输表如下:销地产地BiB3B4供应量4 1241132A22103920A38511644需求量1628282496(1) 用最小元素法确定初始调运方案；(2) 基于(1)的初始解用位势法确定最优运输方案及最低运费用最小元素法求一个运输方案销地产地BiB2B3B4供应量Ai24832A16420A3281644需求量16286282496(2)运用位势法求的 = 0 , % = -1 , "3 = 5,3 = 3 , V2 = 10 , v3所以 4=1,7A2=2 ,久 2 = 1 ,冬 4 = 1 , 41=13, %2 = 运用闭回路

7、法进行调整得新的分配为销地产地BiB2B3B4供应量Ai28432A16420A3281644需求量16286282496运用位势法求的"=0 , W2 = 2 , U3 = 5 , % = 4 , V2 = 10 , V3 = 4 , V4 = 11 所以九产。，&2=2, a22 = 2 , a23 = 1,=9,在=12因此达到最优解，其总运费最少为28x4 + 11x4 +4x9 + 16x2 +28x5+ 16x6 = 460五、（15分）已知某实际问题的线性规划模型为max z = lOChq + 50x 2'2%! + 2X2 < 36（资源 1）

8、< 2%! + X2 < 38 （资源 2） x,X9 > 0假定重新确定这个问题的目标为：R: Z的值应不低于1800Pr-资源1必须全部利用1）将此问题转换为目标规划问题，列岀数学模型；2）图解法找岀此目标规划问题的满意解。【解】1）数学模型为min z = Pd" + p2 （d2+ d ；）100%, + 50X2 + d;-=18002%| + 2X9 + d d := 36< -1 -2% + X2 < 38x, X2, d； , d； > 0,i = 1,2,2）满意解 X= （18, 0）（15分）需要指派5人去做5项工作，每人做各

9、项工作所消耗的时间如下表工、员/Z .1ABCDE、作人4871512乙79171410丙691287T6714610戊6912106问指派哪个人去完成哪项工作，可使总的消耗时间最小？试用匈牙利方法解决之。 87151 4318一 30187 917 14 2(AII0 21730 1 7 6) 3006 9128703621023116 71461>01804006056 9121000364001330T解：对其效率矩阵进行化简得TD,戊 TE。因此达到最优解，所有最有方案为甲TC,乙tB,（10分）求解下列 0-1规划问题丙TA,max z = 3 工 1 + 2x2 一 5x3一 2x4 + 3x 5 尤+ X