1、运筹学基础 2005 学号 姓名 成绩 一 (10 分 )已知线性规划问题 1 2 31 2 312m a x 4 5 212 3 10,jz x x xx x xxxx 问 (1) 变量 12,xx 能否成基变量 ?如是 ,得到的基解为何 ?是否是基可行解 ? (2) 变量 13,xx 能否成基变量 ?如是 ,得到的基解为何 ?是否是基可行解 ? 二 .(12 分 )从下面的线性规划及对应的单纯形表可得出 ( ) 有唯一最优解 ( ) 有无界解 ( ) 无可行解 ( ) 最优解不唯一 (A ) 121212212max 35 10 5014,0z x xxxxxxxx 化标准型为 :121
2、2 41225m a x 35 10 503140iz x xx x xx x xxxx 得单纯形表 x1 x2 x3 x4 x5 - x 1| 1.0000 0.0000 0.0000 0.2000 -2.0000| 2.0000 x 3| 0.0000 0.0000 1.0000 0.2000 -1.0000| 5.0000 x 2| 0.0000 1.0000 0.0000 0.0000 1.0000| 4.0000 - z-c| 0.0000 0.0000 0.0000 0.2000 1.0000| (B )1 2 31 2 31 2 31 2 31 2 3m a x 10 15 12
3、5 3 95 6 15 1525, , 0z x x xx x xx x xx x xx x x 得第一阶段规划为 : 71 2 3 51 2 3 61 2 3 4 7m in5 3 95 6 15 15250izxx x x xx x x xx x x x xx 得单纯形表 : x1 x2 x3 x4 x5 x6 x7 - x 1| 1.0000 0.4875 0.0000 0.0000 0.1875 -0.0125 0.0000| 1.5000 x 3| 0.0000 0.5625 1.0000 0.0000 0.0625 0.0625 0.0000| 1.5000 x 7| 0.0000
4、 -0.5375 0.0000 -1.0000 -0.4375 -0.0375 1.0000| 0.5000 z-c | 0.0000 0.5375 0.0000 1.0000 0.4375 0.0375 0.0000| (C )1 2 31 2 3121 2 3m a x 2 34 2 83 2 6, , 0z x x xx x xxxx x x 化标准型为 : 1 2 31 2 3 41 2 51 2 3 4 5m a x 2 34 2 83 2 6, , , , 0z x x xx x x xx x xx x x x x 得单纯形表 x1 x2 x3 x4 x5 - x 2| 1.500
5、0 1.0000 0.0000 0.0000 -0.5000| 3.0000 x 4| 5.0000 0.0000 -2.0000 1.0000 -2.0000| 4.0000 - z-c | 2.5000 0.0000 -1.0000 0.0000 -1.5000| (D ) 1212121212max 6 4243 2 1424,0z x xxxxxxxxx 化标准型为 : 121 2 31 2 41 2 51 2 3 4 5m a x 6 4243 2 1424, , , , 0z x xx x xx x xx x xx x x x x 得单纯形表 x1 x2 x3 x4 x5 - x
6、3| 0.0000 0.0000 1.0000 -0.4286 1.1429| 2.5714 x 2| 0.0000 1.0000 0.0000 0.2857 -0.4286| 2.2857 x 1| 1.0000 0.0000 0.0000 0.1429 0.2857| 3.1429 - z-c | 0.0000 0.0000 0.0000 2.0000 0.0000| 三 (12 分 )已知某线性规划问题为 1 1 2 2 3 31 1 1 1 2 2 1 3 3 11 2 1 2 2 2 2 3 3 2m a x.0 , 1 , , 3jz c x c x c xa x a x a x
7、bs t a x a x a x bxj 将它化成标准型后得单纯形表如下： x1 x2 x3 x4 x5 x3 0 -1/2 1 1/2 0 5/2 x1 1 -1/2 0 -1/6 1/3 5/2 z-c 0 4 0 4 2 1） .求 , , , 1, 2 , 1, 2 , 3ij i ja b c i j的值。 2）写出原问题的对偶问题 3）求出对偶问题的最优解 四 . (16 分 ) 某厂生产 I,II,III三种产品 ,其所需劳动力 ,材料等有关数据见下表 ,要求 : (1) 确定获利最大的产品生产计划 ; (2) 产品 I的利润在什么范围内变动时 ,上述最优计划不变 ; (3) 如
8、果设计一种新产品 IV,单件劳动力消耗为 8 个单位 ,材料消耗为 2 个单位 ,每件获利 3 元 ,问该种产品是否值得生产 ? (4) 如果劳动力数量不增 ,材料不足时可以从市场购买 ,每单位 0.4 元 ,问该厂要不要购进原材料扩大生产 ,以购多少为宜 ? I II III 可用量 (单位 ) 劳动力 6 3 5 45 材 料 3 4 5 30 利润 (元 /件 ) 3 1 4 (已知 ： - x 4| 6.0000 3.0000 5.0000 1.0000 0.0000| 45.0000 x 5| 3.0000 4.0000 5.0000 0.0000 1.0000| 30.0000 -
9、 z-c | -3.0000 -1.0000 -4.0000 0.0000 0.0000| - x 1| 1.0000 0.5000 5/6 1/6 0.0000| 7.5000 x 5| 0.0000 2.5000 2.5000 -0.5000 1.0000| 7.5000 - z-c | 0.0000 0.5000 -1.5000 0.5000 0.0000| ) 五 .求解整数规划 (12 分 ): Max z=x1+x2 S.t 2x1+x2 6 4x1+5x2 20 x1,x2 0,且是整数 已知在无整数要求下的线性规划最后单纯形表如下 x1 x2 x3 x4 x1 1 0 5/6
10、-1/6 5/3 x2 0 1 -2/3 1/3 8/3 z-c 0 0 1/6 1/6 在用分枝定界法求解时 (1) 在 增加约束 1 2x 时 ,求解 (要求写出单纯形表 ) (2) 在增加约束 1 1x 时 ,得单纯形表如下 x1 x2 x3 x4 x5 - x 3| 0.0000 0.0000 1.0000 -0.2000 -1.2000| 0.8000 x 2| 0.0000 1.0000 0.0000 0.2000 -0.8000| 3.2000 x 1| 1.0000 0.0000 0.0000 0.0000 1.0000| 1.0000 - z-c| 0.0000 0.0000
11、 0.0000 0.2000 0.2000| 就 在用分枝法求解时 ,增加约束 2 3x 求解 (要求写出单纯形表 ) 六 .求如下的运输问题最优调运方案 (10 分 ). 销地 产地 B1 B2 B3 产量 A1 A2 A3 4 3 1 2 5 3 5 3 2 8 7 4 销量 4 8 5 七 .（ 12 分） 某公司有三个工厂，它们都可已考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如表所示（单位：千万元）。现公司有资金 5 千万元，问应如何分配投资使公司的总收益最大？ （注：表中“ ”表示无此方案） 八 .(10 分 ) 设 mnRA ，而 X 是一个 n
12、维的未知列向量 , 1nRb ,Y 是一个 m 维的未知行 ijm 工厂 i=1 i=2 I=3 C(投资 ) R(收益 ) C R C R 1 2 3 4 0 0 1 5 2 6 0 0 2 8 3 9 4 12 0 0 1 3 (方案 ) 向量。试用对偶理论证明：线性不等式组 AX b 有解的充要条件是：对任意满足 YA=0,Y 0 的 Y 都有 Yb 0。 九 .(6 分 ) 设 mnRA ,rank mA , X 是一个 n 维的未知列向量 , 1,nR b b 0 , 证明 :线性规划 maxzCX .st AX b , X0 的可行解是基可行解的充要条件是 :可行解非零分量对应的系数列向量线性无关 .
