运筹学试题及答案11.doc

1/8运筹学试题及答案一、填空题:(每空格2分,共16分)1、线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。2、在求运费最少的调度运输问题中,如果某一非基变量的检验数为4,则说明如果在该空格中增加一个运量运费将增加4。3、“如果线性规划的原问题存在可行解,则其对偶问题一定存在可行解”,这句话对还是错?错4、如果某一整数规划:MaxZ=X1+X2X1+9/14X2≤51/14-2X1+X2≤1/3X1,X2≥0且均为整数所对应的线性规划(松弛问题)的最优解为X1=3/2,X2=10/3,MaxZ=6/29,我们现在要对X1进行分枝,应该分为X1≤1和X1≥2。5、在用逆向解法求动态规划时,fk(sk)的含义是:从第k个阶段到第n个阶段的最优解。,而其所对应的整数规划的可行解集合为B,(极大化问题,约束条件均为“≤”型不等式)其中X3,X4,X5为松驰变量。XBbX1X2X3X4X5X4300-213X14/310-1/302/3X210100-1Cj-Zj00-50-23问:(1)写出B-1=?????????????1003/(2)对偶问题的最优解:Y=(5,0,23,0,0),则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______;,则对偶问题_无解_____;,假设Xi=bi不符合整数要求,INT(bi)是不超过bi的最大整数,则构造两个约束条件:Xi≥INT(bi)+1和Xi≤INT(bi),分别将其并入上述松驰问题中,形成两个分支,即两个后继问题。(极大化问题,约束条件均为“≤”型不等式)其中X4,X5,X6为松驰变量。XBbX1X2X3X4X5X6X12110201X32/30011042/8X510-20116Cj-Zj000-40-9问:(1)对偶问题的最优解:Y=(4,0,9,0,0,0)T(2)写出B-1=??????????611401102二、计算题(60分)1、已知线性规划(20分)MaxZ=3X1+4X2X1+X2≤52X1+4X2≤123X1+2X2≤8X1,X2≥0其最优解为:基变量X1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2σj000-3/4-1/21)写出该线性规划的对偶问题。2)若C2从4变成5,最优解是否会发生改变,为什么?3)若b2的量从12上升到15,最优解是否会发生变化,为什么?4)如果增加一种产品X6,其P6=(2,3,1)T,C6=4该产品是否应该投产?为什么?解:1)对偶问题为Minw=5y1+12y2+8y3y1+2y2+3y3≥3y1+4y2+2y3≥4y1,y2≥02)当C2从4变成5时,σ4=-9/8σ5=-1/4由于非基变量的检验数仍然都是小于0的,所以最优解不变。3)当若b2的量从12上升到15X=9/829/81/4由于基变量的值仍然都是大于0的,所以最优解的基变量不会发生变化。4)如果增加一种