运筹学计算题复习

1、运筹学计算题复习运筹学计算题复习一、第一章线性规划及单纯形法1 、下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，a为参数，1 试完成该表；2假设该表中所示的 x 1, x 2为问题的最优基，试求 a 的取值范围3a 0?1234解：在第二个约束条件两边乘以 -1 ，变为标准形式Max z =2x 1+3x 2+4x 3+7x 4?2x 1+3x 2 -x 3-4x 4=8 ?s . t .? -x 1+2x 2-6x 3+7x 4=3 ?x , x , x , x 0?1234?2?3?x 1 的系数列向量 p 1= ?， x 2 的系数列向量 p 2=?，x 3 的系数列

2、? -1?2? -1?-4?向量 p 3= ?； x 4 的系数列向量 p 4=? -6?7?x 1=1 1 因为 P 1, P 2 线性独立，令非基变量 x 3, x 4=0 得?x =2?2根本可行解 X (1) =(1, 2, 0, 0), Z 1=845 ?x = ?113?( 2 ) 因为 P 1, P 3 线性独立，令非基变量 x 2, x 4=0 14 ?x = -?13?根本解 X (2)14 ?45= , 0, -, 0?13 ?13T34 ?x = ?15(3) 因为 P 1, P 4 线性独立，令非基变量 x 2, x 3=0 得?7 ?x =4?5?根本可行解 X (3

3、)7 ?117?34= , 0, 0,?, Z =555 ?T45 ?x = ?216(4) 因为 P 2, P 3 线性独立，令非基变量 x 1, x 4=0 得?7 ?x =3?16?根本可行解 X (4)163 ?457?= 0, , , 0?, Z =161616 ?T68 ?x = ?229(5) 因为 P 2, P 4 线性独立，令非基变量 x 1, x 3=0?x = -74 ?29?根本解 X (5)7 ?68= 0, , 0, -?29 ?29T68 ?x =- ?331(6) 因为 P 3, P 4 线性独立，令非基变量 x 1, x 2=045 ?x = -4 ?31?根

4、本解 X (5)6845 ?= 0, 0, -, -?3131 ?117为最大值，故最优解为 5T得?得?比拟最大值 Z 1, Z 3, Z 4 可知 Z 3=(3)7 ?117?34= , 0, 0, ?, Z =5 ?5?5T3 、分别用图解法和单纯形法求解以下线性规划问题，并指出单纯形法迭代的每 一步相应于图形上哪一个顶点？Max z =2x 1+x 2?3x 1+5x 2 15?S.T. ?6x 1+2x 2 0?12解：( 1 )图解法，作图如以下图所示，由图得唯一最优解X *=( 上的点为 A 2，其最优值为 z *=153T, ) ，对应于图 4433 。 4(2)单纯形法，引入

5、松驰变量x 3, x 4 0,标准型为Max z =2x 1+x 2?3x 1+5x 2+x 3=15?S.T. ?6x 1+2x 2+x 4=24?x , x , x , x 0?1234因为cj 0(j =1,2, 3, 4) ，故问题的最优解 X *=(, 0, 0) T，其最优目标函数值4433为 z *=44 、建模题：某公司有资金 3000 万元，六年内有 A 、 B 、 C 、D 、E 五种投资工程可 供选择。其中：工程 A 从第一年到第六年初均可投资，当年末可获利10%；工程 B 可在第一年到四年初投资，周期为 3 年，到期可 25%；工程 C 只能在第二年初投资，周期为 3

6、年， 到期可获利 45%，但规定最大投资额不超过1000万元；工程 D 只能在第四年初投资，周期为 3 年，到期可获利 40%，但规定最大投资额不超 800 万元；工程 E 只能在第五年投资， 周期为 2 年，到期可获利 35%，但规定最大投资额不超过500 万元。又工程 A 、 B 、 C 、 D 、E 的风险指数分别为 0.1 ，0.2 ，0.4 ，0.3 ，0.1 ，问：如何确定这些工程的每年投资额，使得第六年 末公司获得最大利润？ 解：建模题用 x ij 表示第 i 年投入到 j 个工程的资金，那么有1234A x 11x 21x 31x 41B x 12x 22x 32x 42C x

7、 23D Ex 44x 555x 516x 61目标函数： maxz =1. 1x 61+1. 25x 42+1. 4x 44+1. 35x 55x 11+x 12=3000x 21+x 22+x 23=1. 1x 11x 31+x 32=1. 1x 21x 41+x 42+x 44=1. 1x 31+1. 25x 12s.tx 51+x 55=1. 1x 41+1.25x 22x 61=1. 1x 51+1.25x 32+1.45x 23x 230x 55 600、第二章线性规划的对偶理论与灵敏度分析 5 、写出线性规划问题的对偶问题Max z =6x 1-2x 2+3x 3?2x 1 -x

8、 2+2x 3 2?S.T. ?x 1+4x 3 0?123解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变 量与对偶问题的约束条件之间的对应关系，具体见 P53? 2-12?2?原问题中： C =(6, -2, 3), A =?, b =? 104?4?2?原问题的对偶问题为 min 3 =Yb =y 1, y 2?=2y 1+4y 2?4?2 -12?由 C =(6, -2, 3) 可知对偶问题为 YA =y 1, y 2?=2y 1+y 2, -y 1, 2y 1+4y 2?104?min 3 =2y 1+4y 2?2y 1+y 2 6? -y -2?1S.T. ?

9、2y 1+4y 2 3?y 1, y 20三、第三章运输问题6 、求解以下产销平衡的运输问题 (2)由上面所得的初始方案出发，应用表上作业法求最优方案。解：四、第四章目标规划7 、用图解法解下面的目标规划 五、第五章整数规划8 、甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。解： 1 变换系数矩阵，增加 0 元素。?01370? ?215134? -2?013112?6069?601011?1041415? -4 ?0532?9141613?-9 ?0574?0100?78119?-2 试指派找独立 07 元素 ?0142? -4-2?01370? ?6069? ?0532? ?0100?独立 0元素的个数为 4 , 指派问题的最优指派方案即为甲负责 D 工作，乙负责 B 工 作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4+ 4+ 9+ 11 =28六、第八章图与网络分析 9 、图与网络的根本概念 1 0 、树的根本概念七、网络方案11 、某工地现场施工准备工作关系及持续时间如表 1 所示，该工程要在 26 天内完成， 其全部直接费用为 30000 元，间接费用为 5000 元，每超过 1 天，间接费用增加 600元。要求： 1先画出双代号网络图，确定关键线路2将表 2中的各项工作的 3 列空格内容计算出来，并填入表中。3进行工期费用优化