《运筹学》试题参考答案

工商管理03级（本）已考《运筹学》试题参考答案资料加工、整理人 杨玲（函授总站高级讲师）※考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式4、在图论中，称无圈的连通图为树。5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。二、（每小题5分，共10分）用图解法求解下列线性规划问题：1）maxZ=6xl+4x2 ⑴\o"CurrentDocument"'2x+X≤10 ⑵1 2\o"CurrentDocument"X+X≤8 ⑶<1 2X≤7 ⑷2[x1，X2≥0 ⑸、⑹解：此题在《运筹学》复习参考资料OC”中已有，不再重复。2）minZ=—3X1+2X2 ⑴⑵⑶⑷⑸⑹、⑺2X+4X≤2212-x+4x≤101212X-X≤72x-3x≤12X,X≥012解：可行解域为abcda,最优解为b点。12X+4X=22由方程组11 「IX=0I 2解出x1=11,x2=0r

.∙.X*=IX1X2=(11,0)τJ・•・minZ=—3×11+2×0=—33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2,则x1、x2≥0,设Z是产品售后的总利润，则maxZ=70x1+120x2s.t.。X+4X≤3601 24X+6X≤200V1 23X+10X≤30012X,X≥0122）用单纯形法求最优解：加入松弛变量X3,x4,x5,得到等效的标准模型：maxZ=70x1+120x2+0x3+0x4+0x5s.t.9x+4x+x=3601 2 34x+6x +x=2001 2 43x+10x +x=3001 2 5ɪ2°,j=1,2,…5Lj列表计算如下:CBXBb70120000θL0X336094100900X420046010100/30X53003(10)001300000070120↑0000X324039/5010-2/5400/130X420(11/5)001-3/5100/11120X2303/101001/1010036120001234↑000—120X31860/11001—39/1119/1170X1100/111005/11-3/11120X2300/11010-3/222/114300070^^1200^^^^170/1130/1111000-170/11—30/11.・.X*=(100,300,I860,0,0)T11 11 11・・.maxZ=70×≡+120×吧=4300011 11 11四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:minz=5x1＋2x2＋4x33X+X+2X≥4123<6X+3X+5X≥1023X,X,X≥0123解：用大M法，先化为等效的标准模型:maxz/=－5x－2x－4x123s.t.3X+X+2X—X=41 2 3 4<6X+3X+5X -X=10235y≥0,j=1,2,…5j增加人工变量x6、x7,得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t3X+X+2X-X1 2 3 4<6X+3X+5X23X≥0,j=1,2,…,7j+X=46+X=107-X5大M法单纯形表求解过程如下:CBXBb—5X1—2X2—4X30X40X5—MX6—MX7θL-MX64(3)12—10104/3-MX7106350—1015/3—9M—4M—7MMM—m—m9M—5↑4M—27M—4—M—M00—5X14/311/32/3—1/301/30——MX72011(2)—1—211—5-M—5/3-M—10/3-2M+5/3M2M—5/3-M0M—1/3M—2/32M—5/3↑—M—3M+5/30—5X15/311/25/60—1/601/610/30X410(1/2)1/21—1/2—11/22—5—5/2—25/605/60—5/601/2↑1/60—5/6—M—M+5/6—5X12/3101/3—11/31—1/3—2X220112—1—2122—5—2—11/311/3—1—1/3T00—1/3—1—1/3—M+1—M+1/3.∙.x*=(23，2，0，0，0)T最优目标函数值minz=—maxz/=一（—五）=22

3 3五、（15分）给定下列运输问题：（表中数据为产地Ai到销地BJ的单位运费）B1B2B3B4S.iAI123410A2876580A391011915d.J82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：B3220B2B4B3Z=IX8+2X2+6X2+5X18+10X20+11X10=42434 j・・・选X作为入基变量迭代调整。34②用表上闭回路法进行迭代调整：费\销产‹\地产B1B2B3B4SiA1123一14-31082XXA28-37一16520XX128A39O1011一1930X20X10dj822121860~60调整后，从上表可看出，所有检验数σ≤0,已得最优解。j・,・最优方案为:最小运费Z=1X8+2X2+6X12+5×8+10×20+9X10=414六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲21097乙154148丙13141611丁415139问应该如何指派，才能使总的消耗时间为最少？解用“匈牙利法”求解。效率矩阵表示为：[21510 94147：8行约简[011807105、4列约简I 131416112350标号15139><01195，，(0)112、O*8

(O)31225(O)45、4O*I>,(O) 8 2 5、 ζQ) 5 —2 3——(O)——O*-J)* 12 4