运筹学计算题复习
一、第一章线性规划及单纯形法
1、 下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，α为参数， （1） 试完成该表；
（2） 若该表中所示的21,x x 为问题的最优基，试求α的取值范围
43≤≤α
2、 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入
目标函数，确定哪一个是最优解。
Max 43217432x x x x z +++= ⎪⎩⎪
⎨⎧≥-=-+-=--+0,,,37628432..4
32143214321x x x x x x x x x x x x t s 解：在第二个约束条件两边乘以-1，变为标准形式
Max 43217432x x x x z +++=
⎪⎩⎪
⎨⎧≥=+-+-=--+0,,,37628432..4
32143214321x x x x x x x x x x x x t s 1x 的系数列向量⎥⎦⎤⎢⎣⎡-=121p ，2x 的系数列向量⎥⎦
⎤
⎢⎣⎡=232p ，3x 的系数列向量
⎥⎦⎤⎢⎣⎡--=613p ；4x 的系数列向量⎥⎦
⎤
⎢⎣⎡-=744p
（1） 因为21,P P 线性独立，令非基变量0,43=x x 得⎩⎨⎧==212
1x x 基本可行解()8,0,0,2,11)
1(==Z X
T
（2）
因为31,P P 线性独立，令非基变量0,42=x x 得
⎪⎪⎩
⎪⎪⎨⎧
-==131413451x x
基本解T
X
⎪⎭⎫ ⎝⎛-=0,1314,0,13
45
)
2(
（3） 因为41,P P 线性独立，令非基变量0,32=x x 得⎪⎪⎩
⎪⎪⎨
⎧
==575
3441x x 基本可行解5117,57,0,0,534
)
3(=⎪⎭
⎫ ⎝⎛=Z X
T
（4） 因为32,P P 线性独立，令非基变量0,41=x x 得⎪⎪⎩
⎪⎪⎨⎧
==16716
4532x x
基本可行解16163,0,167,1645,0)
4(=⎪⎭
⎫
⎝⎛=Z X
T
（5） 因为42,P P 线性独立，令非基变量0,31=x x 得⎪⎪⎩
⎪⎪⎨⎧
-==29729
6842x x
基本解T
X
⎪⎭⎫ ⎝⎛-=297,0,29
68
,0)
5(
（6） 因为43,P P 线性独立，令非基变量0,21=x x 得⎪⎪⎩
⎪⎪⎨⎧
-=-=314531
6843x x
基本解T
X
⎪⎭⎫ ⎝
⎛
--=3145,3168,0,0)
5(
比较最大值431,,Z Z Z 可知5
117
3=
Z 为最大值，故最优解为5117,57,0,0,534
)
3(=⎪⎭
⎫ ⎝⎛=Z X T
3、 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相应于
图形上哪一个顶点？
Max 212x x z +=
S.T.⎪⎩⎪
⎨⎧≥≤+≤+0,242615532
12121x x x x x x
解：（1）图解法，作图如下图所示，由图得唯一最优解T
X )4
3,415(
*
=，对应于图上的点为2A ，其最优值为4
33*=
z 。
（2） 单纯形法，引入松驰变量0,43≥x x ，标准型为
Max 212x x z +=
S.T.⎪⎩⎪
⎨⎧≥=++=++0,,,242615534
321421321x x x x x x x x x x
用单纯形法列表，求解过程见下表
因为()4,3,2,10=≤j j σ，故问题的最优解T X )0,0,4
,4(
*
=，其最优目标函数值为4
33*=
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，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？ 解：建模题
用ij x 表示第i 年投入到 j 个项目的资金，则有
61
55
5144
42
41323123
22211211654321
x x x x x x x x x x x x x E
D C B A
目标函数：5544426135.14.125.11.1max
x x x x z +++=
s.t
554423233251612241555112
3144424121
3231112322211211600
800,100045.125.11.125.11.125.11.11.11.13000≥≤≤≤++=+=++=++=+=++=+ij x x x x x x x x x x x x x x x x x x x x x x x x x x
二、第二章线性规划的对偶理论与灵敏度分析 5、写出线性规划问题的对偶问题
Max 321326x x x z +-=
S.T.⎪⎩⎪
⎨⎧≥≤+≤+-0,,442223
2131321x x x x x x x x
解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变量与对偶问题的约束条件之间的对应关系，具体见P53
