广东工业大学-运筹学-试卷+答案

广东工业大学试卷用纸，共广东工业大学试卷用纸，共8页，第1页：名姓线：号：名姓线：号学订：业专装：院学课程名称: 运筹学B 试卷满分100考试时间: 2008年7月11日(第20周星期五)题号 一 二 三 四 五 六 七 八 九 十 总分评卷得分评卷签名复核得分复核签名一、判断题（每小题2分，共20分，无须改错）标准形式的线性规划模型中决策变量的取值可以无任何限制（ ）线性规划问题的可行域一定非空（ ）若线性规划问题无可行解，则其对偶问题一定无可行解（ ）任何一个无向图中偶点的个数不能是奇数（ ）对产大于销的运输问题，可通过添加假想的销地化为产销平衡运输问题。（ ）目标规划中任意一个目标约束的正负偏差变量不可能同时为正数（ ）若指派问题的系数矩阵中某行元素都减去同一个常数，则得到的新矩为系数矩阵的指派问题与原问题有同样的最优解（ ）8．增广链上的每条后向边都为零流边（ ）动态规划的最优策略应该具有性质，无论先前的状态与决策如何，当的决策应该是最优（ ）矩阵对策就是二人有限零和对策（ ）广东工业大学试卷参考答案及评分标准( )课程名称: 运筹学 。考试时间:2008年7月11日(第20周星期五一、判断题（每小题2分，共20分，无须改错）1．标准形式的线性规划模型中决策变量的取值可以无任何限制（ 线性规划问题的可行域一定非空（ ）若线性规划问题无可行解，则其对偶问题一定无可行解（ ）任何一个无向图中偶点的个数不能是奇数（ ）对产大于销的运输问题，可通过添加假想的销地化为产销平衡运输问题。（ ）．目标规划中任意一个目标约束的正负偏差变量不可能同时为正数。（ ）7．若指派问题的系数矩阵中某行元素都减去同一个常数，则得到的新矩为系数矩阵的指派问题与原问题有同样的最优解（ ）8．增广链上的每条后向边都为零流边（ ）动态规划的最优策略应该具有性质，无论先前的状态与决策如何，当的决策应该是最优（ ）矩阵对策就是二人有限零和对策（ ）二、单项选择题（每小题2分，共20分）下列哪个模型是线性规划模型[ C ]A． B．minz2

y2 minw

4sinx1 2y2y 2

cosx

1 23x 01 2

1 2y3y 3

2x 41 2

1 2yy 0 xx无约束1 2 1 2C． D．max{5x1

4x2

x} minzx3

5x |2x 4x 0

3x

2x 42 3x4x 3

1 25x 31 2 1 2xx,x 0 x,x 01 2 3 1 2若用单纯形法求解线性规划问题得到的最终单纯形表中，基变量不含人工变量且非基变量的检验数均非零则线性规划问题为下面的情形[ A ]A．有唯一最优解，B．有无穷多个最优解，C．无界解，D．无可行解广东工业大学试卷用纸，共广东工业大学试卷用纸，共8页，第2页若线性规划的原问题不存在最优解，则对偶问题[ B ]A．可能存在最优解不存在最优解，C．一定是无可行解，D．一定无界解。4．若线性规划问题的某个资源常数发生变化，则在最终单纯形表中这一变化[ B ]A．对检验数存在影响，B．对b列数存在影响，C．对该资源常数所在行的数存在影响，D．对所有数都无影响。对于有m个产地n个销地的产销平衡运输问题的表上作业法求解，下面正确的说法是[ C ]A．每个空格有唯一的闭回路，B．数字格的个数为m+n-1，C．沃格尔法得到的调运方案是最优方案，D．若存在负检验数，则调运方案仍可改进。6．对于目标规划问题的求解，在满足一个目标时[ B ]A．必须同时考虑优先级别较低的目标，B．不得违背已经得到满足的优先级别更高的目标，C．不必顾虑优先级别较高的目标，D．无须考虑上述情况7．若一个无向图可以一笔画出，则该图中[ C ]A．最多有一个奇点恰好有两个奇点最多有两个奇点没有奇点。下图v2v1v5vv3v4的邻接矩阵是[ D ]0 1 1

0 0 1 1 0 010000010000000

0 0 1 0 1A．1

0 0 0 0

，B．

0 0 0 1 ，C．0

0 1 1 ，1 1

10 0

1 0 0

0 0 1 0 00 1 0 0 0 D．1 0 0 1 1 1 1 0 0 00 0 0

0 0 1 0 0

1 0 在一个容量网络中一个可行流满足的条件中不包括下面的哪一点[ A ]AB物质的和，C．每边上的流量不超过其容量，D．发点发出的物资的和等于收点接受的物资的和。在矩阵对策中，若局中人1的赢得矩阵不存在鞍点，则[ C ]A．矩阵对策问题虽然存在纯策略意义下的解，但不能通过求矩阵鞍点的方求解矩阵对策不存在解矩阵对策不存在纯策略意义下的解矩阵对策不存在混合策略意义下的解。三、 设有如下的线性规划问题minzx1

2x2

4x33xx 21 2x5x1

3x无约,x x 01 2 3（6分）（6分1）标准形式是maxwxx2x4x1 1 2 33x3xxx 21 1 2 4xx5x 3 1 1 3x,xx,x 01 1 2 3[目标函数2分，每个约束方程各1分，变量2分]（2）对偶问题为maxw2y1

3y23yy 11 2y215y42y0,y1

无约束2[目标函数1分，每个约束（包括变量约束）各1分]20203/2000CBXBbx1x2x3x4x5x6ax12d-1001-1bx33/20210-12cx40e001-10j0-100-1/2fa~f的值（6分）上表是否给出了最优解，若是则求出最优解及对偶问题最优解（6分）广东工业大学试卷用纸，共8页，第3页广东工业大学试卷用纸，共广东工业大学试卷用纸，共8页，第6页解（1）a=2,b=3/2,c=0,d=1,e=0,f=-1[每个参数值1分]（2）由于所有检验数都非正，因此该表给出最优解[2分]，最优解为x 2,x1

0,x3

3/2,x4

0,x5

0,x6

0;z*25/4[2分]利用对偶关系可得对偶问题最优解为y 0y 1/2y y 0y y 25/4[2分]1 2 3 4 5 63A、、C超市，每个月的营业利润估算如下表所示（单位：万元：地址超市123A162030B121520C101316问这三个超市应如何分布，可使公司总的营业利润最高？（12分）解：这是最大化指派问题，化为标准化指派问题，系数矩阵为10 0 0 0 0 0 0 0 15 10 20 17 41 0 0 0 0 0 0 7

7

0 1 8故最优解为超市1在位置B，超市2在位置C，超市3在位置A；总利润为55万元。[化为标准形式3分，求解过程正确5分，最优解2分，最优值2分]7设成本（单位：百元。7个单位连接起来，并使总成本最低？（8分）若图中A、B两个单位之间必须直接连通，则最低总成本是多少？（分）876512645A 7 B4 329解（1）由避圈法或破圈法得到如下的最小树，即最优架设线路[6分]876512645A 7 B4 329总费用为25（百元）[2分]（2）在上述求解中总是保留AB之间的线路，得相应的线路为[3分]876512645A 7 B4 329总费用28（百元）[1分]七、设矩阵对策问题3 3 11 2 31q1 2 p2 53 2 1