《运筹学》期末考试试题及参考答案

本文格式为Word版，下载可任意编辑——《运筹学》期末考试试题及参考答案《运筹学》试题参考答案

一、填空题（每空2分，共10分）

1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。

4、在图论中，称无圈的连通图为树。

5、运输问题中求初始基本可行解的方法寻常有最小费用法、西北角法两种方法。

二、（每题5分，共10分）用图解法求解以下线性规划问题：1）maxz=6x1+4x2

⑴

?2x1?x2?10?x?x?8?12?x2?7???x1，x2?0⑵⑶⑷⑸、⑹

解：此题在“《运筹学》复习参考资料.doc〞中已有，不再重复。2）minz=－3x1+2x2

⑴⑵⑶⑷⑸⑹、⑺

?2x1?4x2?22??x?4x?1012???2x1?x2?7?x?3x?12?1??x1,x2?0解：

第1页共11页

可行解域为abcda，最优解为b点。

?2x1?4x2?22由方程组?解出x1=11，x2=0

x?02??x?*?1?∴X=??=（11，0）T?x2?∴minz=－3×11+2×0=－33

三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储存如下表所示：

甲乙A94360B46200C31030070120

1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）

第2页共11页

2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：

设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则

maxz=70x1+120x2

s.t.

?9x1?4x2?360??4x1?6x2?200??3x1?10x2?300??x1，x2?02）用单纯形法求最优解：

参与松弛变量x3，x4，x5，得到等效的标准模型：

maxz=70x1+120x2+0x3+0x4+0x5

s.t.

?360?9x1?4x2?x3??x4?200?4x1?6x2?3x?10x?x?300125??xj?0,j?1,2,...,5?列表计算如下：

第3页共11页

70120000CB00000120070120XBx3x4x5b36020030024020301860/11100/11300/11x194307039/5（11/5）3/103634↑010x246（10）0120↑0011200001x3100001000010000x40100001000－39/115/11-3/22x500100-2/5-3/51/1012－1219/11-3/112/11θL90100/330400/13100/11100x3x4x2x3x1x243000701200011∴X*=（100，300，1860，0，0）T

111111∴maxz=70×100+120×300=43000

111111170/1130/11-170/11－30/11

四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：

minz=5x1＋2x2＋4x3

?3x1?x2?2x3?4??6x1?3x2?5x3?10?x,x,x?0?123第4页共11页

解：用大M法，先化为等效的标准模型：

maxz/=－5x1－2x2－4x3s.t.

?3x1?x2?2x3?x4?4??x5?10?6x1?3x2?5x3?y?0,j?1,2,...,5?j增加人工变量x6、x7，得到：

maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t