运筹学计算题复习

运筹学计算题复习 一、第一章线性规划及单纯形法 1、 下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，为参数， （1） 试完成该表；

（2） 若该表中所示的21,xx为问题的最优基，试求的取值范围

jC  2 1 -4

Bc Bx b 1x 2x 3x 4x

1x 3 1 0 1 -1

2 2x 1 0 1 -1 0 jjzc 0 0

解： jC  2 1 -4

Bc Bx b 1x 2x 3x 4x  1x 3 1 0 1 -1

2 2x 1 0 1 -1 0 jjzc 0 0 3- -4

43 2、 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。

Max 43217432xxxxz







0,,,37628432..432143214321xxxxxxxxxxxxts

解：在第二个约束条件两边乘以-1，变为标准形式 Max 43217432xxxxz 





0,,,37628432..432143214321xxxxxxxxxxxxts

1x的系数列向量121p，2x的系数列向量232p，3x的系数列向量

613p；4x的系数列向量

74

4p

（1） 因为21,PP线性独立，令非基变量0,43xx得2121xx 基本可行解8,0,0,2,11)1(ZXT

（2） 因为31,PP线性独立，令非基变量0,42xx得131413451xx 基本解TX0,1314,0,1345)2( （3） 因为41,PP线性独立，令非基变量0,32xx得5753441xx 基本可行解5117,57,0,0,534)3(ZXT （4） 因为32,PP线性独立，令非基变量0,41xx得167164532xx 基本可行解16163,0,167,1645,0)4(ZXT （5） 因为42,PP线性独立，令非基变量0,31xx得297296842xx 基本解TX297,0,2968,0)5( （6） 因为43,PP线性独立，令非基变量0,21xx得3145316843xx 基本解TX3145,3168,0,0)5( 比较最大值431,,ZZZ可知51173Z为最大值，故最优解为

5117,57,0,0,534)3(ZX

T

3、 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相应于图形上哪一个顶点？

Max212xxz

S.T.0,24261553212121xxxxxx 解：（1）图解法，作图如下图所示，由图得唯一最优解TX)43,415(*，对应于图上的点为2A，其最优值为433*z。

155321xx X1

X2

A3 A2 A1 242621xx （2） 单纯形法，引入松驰变量0,43xx，标准型为 Max212xxz

S.T.0,,,242615534321421321xxxxxxxxxx 用单纯形法列表，求解过程见下表 jC 2 1 0 0

i

BC BX b 1x 2x 3x 4x

0 3x 15 3 5 1 0 5 0 4x 24 6 2 0 1 4 j 2 1 0 0

0 3x 3 0 4 1 -1/2 3/4 2 1x 4 1 1/3 0 1/6 12 j 0 1/3 0 -1/3

1 2x 3/4 0 1 1/4 -1/8 2 1x 15/4 1 0 -1/12 5/24 j 0 0 -1/12 -7/24

因为4,3,2,10jj，故问题的最优解TX)0,0,43,415(*，其最优目标函数值为

433*z

4、 建模题：某公司有资金3000万元，六年内有A、B、C、D、E五种投资项目可供选择。其中：项目A从第一年到第六年初均可投资，当年末可获利10%；项目B可在第一年到四年初投资，周期为3年，到期可25%；项目C只能在第二年初投资，周期为3年，到期可获利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，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？ 解：建模题 用ijx表示第i年投入到 j个项目的资金，则有

61555144424132312322211211

654321xxxxxxxxxxx

xx

EDCBA

目标函数：5544426135.14.125.11.1maxxxxxz s.t 055442323325161224155511231444241213231112322211211600800,100045.125.11.125.11.125.11.11.11.13000ijxxxxxxxxxxxxxxxxxxxxxxxxxx 二、第二章线性规划的对偶理论与灵敏度分析 5、写出线性规划问题的对偶问题 Max321326xxxz

S.T.0,,4422232131321xxxxxxxx 解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变量与对偶问题的约束条件之间的对应关系，具体见P53 原问题中：3,2,6C,401212A,42b 原问题的对偶问题为min21214242,yyyyYb 211212142,,2401212,yyyyyyyYA，由3,2,6C可知对偶问题为

min2142yy



S.T.0,3422622121121yyyyyyy 三、第三章运输问题 6、求解下列产销平衡的运输问题 单位价格表 销地B1 销地B2 销地B3 销地B4 产量 产地A1 产地A2 产地A3 10 5 6 7 8 2 7 6 9 3 4 8 25 25 50 销量 15 20 30 35 100 （1）用西北角法、最小元素法求初始基本可行解； （2）由上面所得的初始方案出发，应用表上作业法求最优方案。 解： （1）西北角法z=665 销地B1 销地B2 销地B3 销地B4 产量 产地A1 产地A2 产地A3 15 10 10 15 15 35 25 25 50 销量 15 20 30 35 100 （2）最小元素法 z=540 销地B1 销地B2 销地B3 销地B4 产量 产地A1 产地A2 产地A3 25 20 5 15 30 5 25 25 50 销量 15 20 30 35 100 （3）最优方案：z=535 销地B1 销地B2 销地B3 销地B4 产量 产地A1 25 25 产地A2 产地A3 15 10 15 5 30 25 50 销量 15 20 30 35 100

四、第四章目标规划 7、用图解法解下面的目标规划 五、第五章整数规划

8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。 任务 人员 A B C D

甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9

解： 1）变换系数矩阵，增加0元素。

2）试指派（找独立0元素）

独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D工作，乙负责B工作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28

六、第八章图与网络分析 9、书上P239例7（破圈法和避圈法） 10、最大流（标号法）书上250页例13

七、网络计划 11、某工地现场施工准备工作关系及持续时间如表1所示，该工程要在26天内完成，其全部直接费用为30000元，间接费用为5000元，每超过1天，间接费用增加600元。 表1工作清单 序号 工作名称 工作代号 持续时间/天 紧后工作

79429118713161491514410413152





2424104750111006211130











00102350960607130





00102350960607130