运筹学复习资料.doc

∆1、分别用图解法和单纯形法求解下面的线性规划问题
Max z=2x1+x2
s.t 3x1+5x2≤15
6x1+2x2≤24
X1,x2≥0
解：
1）图解法：

由上图可知，B点为最优点，最优解为（15/4,3/4），最优值为　z=33/4
2）单纯形法：
将上述线性规划问题化为标准形：
Max z=2x1+x2
s.t 3x1+5x2+x3=5
6x1+2x2+x4=24
X1,x2,x3,x4≥0
利用单纯形法运算得到表一至表三：

由表三可知，线性规划问题的最优解为X*=(15/4,3/4,0,0)T
目标函数的最优值为max z=33/4
∆2已知线性规划问题
Max z=x1+2x2+3x3+4x4
s.T x1+2x2+2x3+3x4 ≤ 20
2x1+x2+3x3+2x4≤20
x1 ,x2 ,x3 , x4 , ≥0
其对偶问题的最优解为W=(1.2,0.2)T，试根据对偶理论求出原问题的最优解
解，该原问题的对偶问题为：
min Y=20w1+20w2
s.T w1+2w2 ≥1　　 (1) w1+2w2>1 x1=0
2w1+w2 ≥ 2 (2) 2w1+w2>2 x2=0
2w1+3w2 ≥ 3 (3) 2w1+3w2=3
3w1+2w2 ≥ 4 (4) 3w1+2w2=4
w1,w2 ≥ 0
将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到
X1=x2=0
又w1,w2>0，由松驰性质得到原问题约束条件应取等号即
w1>0 2x3+3x4=20
w2 >0 3x3+2x4=20， 解方程组，得x3=x4=4
所以原问题的最优解为：X=(0,0,4,4)T
3已知线性规划问题
Max z=2x1+x2+5x3+6x4
s.T 2x1 + x3+ x4 ≤ 8
2x1+2x2+x3+2x4≤12
x1 ,x2 ,x3 , x4 , ≥0
其对偶问题的最优解为w=(4,1)T，试根据对偶理论求出原问题的最优解
解，该原问题的对偶问题为：
min Y=8w1+12w2
s.T 2w1+2w2 ≥2　　 (1) 2w1+2w2>2 x1=0
2w2 ≥ 1 (2) 2w2>1 x2=0
w1+ w2 ≥ 5 (3) w1+w2=5
w1+2w2 ≥ 6 (4) w1+2w2=6
w1,w2 ≥ 0
将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到
X1=x2=0
又w1,w2>0，由松驰性质得到原问题约束条件应取等号即
W1>0 x3+x4=8
W2>0 x3+2x4=12，解方程组，得x3=x4=4
所以原问题的最优解为X=(0,0,4,4)T
∆4 A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大？

解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题：
max z=7x1 + 12x2 (总销售收入)
s.t. 9x1 + 4x2≤ 360 (煤资源限制)
4x1 + 5x2£≤ 200 (电资源限制)
3x1 + 10x2£ ≤300 (油资源限制)
x1 ³≥ 0，x2 ≥ 0 (非负条件)
用单纯形法求解得：x1=20，x2=24。

原问题的最优解为X＝(20,24)T,对应的对偶价格，
也就是影子价格为(0,1.36,0.52)
∆5 已知企业关于获利的线性规划问题如下所示：
Max z=-5x1+5x2+13x3
s.T -x1+x2+3x3 ≤ 20
12x1+4x2+10x3≤90
x1 ,x2 ,x3 ≥0
(1)试确定获得最大利润的产品计划。
(2)产品B的利润（即x2)在什么范围内变化时，上述的最优生产计划不变。
(3)如果设计一种新产品D，单位劳动力（即第一种资源）消耗为2单位，材料（第二种资源）消耗为3单位，每件可获利12元，问该产品是否值得生产？
(1)将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表：
即最优生产计划为：

即最优生产计划为：x1=0,x2=20,x3=0 ,最优值为max z=100
（2） 假设B产品的变化量为△C
表三
-5
5
13
0
0
Xb
b
b
X1
X2
X3
X4
X5
5
X2
20
-1
1
3
1
0
0
X5
10
16
0
-2
-4
1

0
∆c
-2
-5
0
解得：-2/3≤ △C ≤0
故产品B在13/3≤ △C ≤5时，最优生产计划为不变
（3）由最优表可知，第一种资源的影子价格为5，第二种资源的影子价格为0，因此D产品的生产成本为：
　　生产成本：5＊2＋0＊3＝10＜12
即生产成本小于12，企业有利图，值得生产。
∆6.P114 页。4.3题
解：设生产A、B、C三种产品的数量分别为x1,x2,x3，依题意得：
Max z=3x1+x2+4x3
s.t 6x1+3x2+5x3≤45
3x1+4x2+5x3≤30
x1,x2,x3≥0
利用单纯形法求解得表一至表三：

表二
3
1
4
0
0
xb
b
X1
X2
X3
X4
X5
X4
15
3
-1
0
1
-1
X5
6
3/5
4/5
1
0
1/5

3/5
-11/5
0
0
-4/5

表三
3
1
4
0
0
XB
b
x1
x2
x3
x4
x5
X1
5
1
-1/3
0
1/3
-1/3
X3
3
0
1
1
-1/5
2/5

0
-2
0
-1/5
-3/5

由表三可知，所有的检验数均小于等于0，所以表三为最优表，
最优解为X=(5,0,3)T
(2)设A产品的变化范围为△C，利用灵敏度分析得表四：
表四
3
1
4
0
0
XB
b
x1
X2
x3
x4
x5
X1
5
1
-1/3
0
1/3
-1/3
X3
3
0
1
1
-1/5
2/5

0
△c/3-2
0
-△c/3-1/5
△c/3-3/5

要使表四为最优表须：△c/3-2≤0 -△c/3-1/5≤0 △c/3-3/5≤0
解不等式得：-3/5≤△c≤9/5
所以产品A的最优变化范围为[12/5,24/5]
(3)由表三可知两种资源的影子价格分别为：1/5,3/5
增加新产品的成本为：1/5*8+2*3/5=14/5 <3
企业有利可赚，值得生产D产品
7 填空题 （要求用位势法调整）

由于上表的所有检验数均大于等于零，所以此表为最优表
最优方案为：
x11=15,x12=35,x21=10,x23=60,x24=30,x32=80,x35=70 ，其余为0
最优值为：
minz=10*15+15*35+10*20+15*60+30*30+35*80+25*70
=7225
∆8求根据下面的效能矩阵求最优指派

每列减
最小元
每行减
最小元
解(1)根据效能矩阵，使每行每列都出现0元

（2） 试求最优解 (3)调整并试求最优解 (4)调整并试求最优解 (5)原问题的最优解为

即最优解：
X11=x24=x32=x43=1 其余为0
最优值为：z=15+18+21+16=70
地7 9 由4个人完成4项任务，由于能力不同，完成所需要的时间不同，具体如下表：问应如何指派才使总效率最高即总用时最少？

使每列
出现0元
使每行
出现0元
解:(1)使效能矩阵每行每列出现0元

(2) 试求最优解解: (3)调整并试求最优解 (4)故原问题的最优解为

即x11=x24=x32=x43=1
最优值为：z=2+7+5+6=20
10现要从A地出发，铺设一条天然气管道到F地，中间要经过4站，
每站都有几条路可供选择，并且已知各地间的距离(单位：百米)，
如下图所示，问应选择哪条路径使总的铺设路径最短？

由上图可以得出最优的决策路径为：A-B4-C2-D5-E1-F
最短的铺设路径为900米
11现要从A地出发，铺设一条天然气管道到G地，中间要经过5站，
每站都有几条路可供选择，并且已知各地间的距离(单位：百米)，
如下图所示，问应选择哪条路径使总的铺设路径最短？

由上图可以得出最优的决策路径为：A-B1-C2-D1-E2-F2-G
最短的铺设路径为1800米
12求下列线性参数规划问题

V2
V5

5

解：当 t=0时，经过三次迭代得到最终单纯形表一所示：
将要求解的参数线性规划看成
x1的目标函数系数从3→3+2t
变化，取△ t1=2t,同理x2系
数的△x2=-t,利用灵敏度分析得：

故当0≤t≤9/7时，最优解为：
X=(2,6,2,0,0)T 最优值z=36-2t
t≥0
t≤9/7
t≥-2/3
解不等式：
t≥0
-3/2+7t/6≤0
-1-2/3t≤0

下面向t>9/7方向开拓，当t>9/7时，首先遇到σ4>0,故此时，x4应进基，
利用最小比原则可得x3应为出基

-
下面再向t>5方向开拓，当t>5时，首先遇到σ4>0,故此时，x4应进基，
利用最小比原则可得x3应为出基
故当9/7≤t≤5时，最优解为：
X=(4,3,0,6,0)T 最优值z=27+5t
t≥9/7
t ≤5
要使表二为最优表，须有：
9/2-7t/2 ≤0
-5/2+t/2 ≤0

下面再向t>5方向开拓，当t>5时，首先遇到σ4>0,故此时，x4应进基，
利用最小比原则可得x3应为出基

综上所述：
故当t≥5时，最优解为：
X=(4,0,0,12,6)T 最优值z=12+8t
t≥5
t ≥-3/2
要使表三为最优表，须有：
5-t ≤0
-3-2t ≤0

∆13某地有10个村庄，它们之间的交通道路如下图所示，
图中边旁权为道路长度(单位：百米)，现在要沿道架设电线，
实现村村通电话工程，问应如何架设电线才能使总长度最短？

解：本题实质是最小树问题，利用避圈法可求得最短路线，
如下图粗线所示：

最优架设路线如上图粗线所示，
架设电线最短长度为18(百米)。

附判断
定理3.1 （对称性定理）对偶问题的对偶问题是原问题
根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为
原问题，而把另一个称为其对偶问题
定义4.1：如果线性规划问题存在一组基本可行解，其中至少有一分量为零时，则称该问题为退化的。
Max(≤)松驰变量的检验数的相反数为对偶问题的最优解
Min(≥) 松驰变量的检验数就为对偶问题的最优解
Max(≤)松驰变量的检验数的相反数就为相应资源的影子价格
Min(≥) 松驰变量的检验数相应资源的影子价格
树的性质：
任意两顶点之间必有一条且仅有一条链。
去掉任一条边，则树成为不连通图。
不相邻的两个顶点间添上一条边，恰好得到一个环。
如果树有n个结点，则边的数目刚好为n-1
8