南开大学2004年运筹学考研试卷

2004年硕士研究生入学考试试题

考试科目：运筹学

适用专业：运筹学与控制 一、（20分）线性规划的目标函数是maxZ，在用单纯形法求解的过程中得到表1（其中d、e为常数）： Cj—> 2 5 8 0 0 0 CB XB x6 x2 x4 Cj—>zj b 20 e 8 x1 0 d -2 x2 x3 3 -1 -2 x4 x5 0 0.5 1 x6 1、请在表1空白处填上适当的内容；

2、判断以下四种情况在什么时候成立，并简要说明理由。 a）此解为最优解，并写出相应的基解和目标函数值 b）此解为最优解，且词问题有无穷多个最优解； c）此问题有无界解；

d）此解不是最优解，且能用单纯形法得到下一个基可行解。

二、（10分）已知线性规划问题maxzx12x23x34x4

x12x2233x420 2x1x2332x420 x10,x20,x30,x40

其对偶问题最优解为y1=1.2，y2=0.2，试根据对偶理论求出原问题的最优解。 三、（20分）证明：若线性规划问题有可行解，则必有可行解。 四、（20分）试用割平面法求解下面整数规划问题

maxz7x19x2

x13x26 7x1x235

x10,x20,且均为整数。

五（20分）A、B、C三个工厂需要向甲、乙、丙三个地区供应某种物资，三个工厂与三个地区间的单位运价如表2所示。三个工厂的供应能力分别为200公斤、400公斤、500公斤。甲地区的需求量为300公斤，乙地区的需求量最低为200公斤，最高为500公斤，丙地区

更多南开大学考研试卷 尽在www.juanjuantx.com 的需求量最低为200公斤，最高不限。试用表上作业法确定一个调运方案，在保障供应的基础上，使总运费支出最少。 表2 单位运价表 单位：元/公斤 甲 乙 丙 A B C

六、（20分）求网络中从vs到vt的最大流量及最小割集。右图中各弧旁数字为容量，括弧

中为流量。 15（8） D A

25（14） 12（12） 8（1） 12（6） 6（3）

5（5） vs C vt E 9（6）

7（0） 10（10） 5（2） 6（1） B F 15（13） G 20（7） 2 7 3 5 2 6 4 3 8 16（12） 七、（20分）某厂拟将5台数控机床分配给A、B、C三个车间，各车间可用。这些机床创造的利润如表3所示。

问该厂如何分配这些数控机床，才能使总利润最大。要求使用动态规划方法求解。

表3 A B C 设备台数 0 1 2 3 4 5 0 3 6 9 11 14 0 5 9 12 12 12 0 4 7 10 11 11 八、已知A、B各自的纯策略及A的赢得矩阵如表5所示，求双方的最优策略及对策值。

表4 b1 b2 b3 b4 b5 a1 a2 a3 a4 2 -3 0 -2 -2 0 3 1

-1 1 -2 4 -3 -1 2 0 3 -2 1 0