运筹学复习题及 答案
- 格式：doc
- 大小：138.00 KB
- 文档页数：9
运筹学复习题及答案
一、一个毛纺厂用羊毛和涤纶生产A、B、C混纺毛料，生产1单位A、B、C分别需要羊毛和涤纶3、 2； 1、 1； 4、4单位，三种产品的单位利润分别为4、1、5。每月购进的原料限额羊毛为8000单位，涤纶为3000单位，问此毛纺厂如何安排生产能获得最大利润？（要求：建立该问题的数学模型）
解：设 生产混纺毛料ABC各x1、x2、x3单位
max z＝x1+x2+5x3
3x1+x2+4x3≤8000
2x1+x2+4x3≤3000
x1,x2,x3≥0
二、写出下述线性规划问题的对偶问题
max s=2x1+3x2-5x3+x4
x1+x2-3x3+x4≥5
2x1 +2x3-x4≤4
x2 +x3+x4=6
x1,x2,x3≥0；x4无约束
解：先将原问题标准化为：
max s=2x1+3x2-5x3+x4
-x1-x2+3x3-x4≤-5
2x1 +2x3-x4≤4
x2 +x3+x4=6
x1,x2,x3≥0；x4无约束
则对偶问题为：
min z=-5y1+4y2+6y3
-y1+2y2≥2
-y1+ y2≥3
3y1+ 2y2+y3≥-5
-y1-y2+y3=1
y1,y2≥0,y3无约束
三、求下述线性规划问题
min S =2x1＋3x2－5x3 x1＋x2－3x3 ≥5
2x1 ＋2x3 ≤4
x1，x2，x3≥0
解：引入松弛变量x4，x5，原问题化为标准型：
max Z=-S =-2x1-3x2+5x3
x1＋x2－3x3 －x4=5
2x1 ＋2x3 +x5=4
x1，x2，x3, x4,x5≥0
对应基B0＝（P2,P5）的单纯形表为
T(B0)= 5 1 1 -3 -1 0
4 2 0 2 0 1
15 1 0 -4 -3 0
x1的检验数为正，x1进基，由min｛5/1,4/2｝=4/2知，x5出基，迭代得新基B1=(P2,P1),对应的单纯形表为
T(B1)= 3 0 1 -4 -1 -1/2
2 1 0 1 0 1/2
13 0 0 -5 -3 -1/2
至此，检验数全为非正，已为最优单纯形表。对应的最优解为：
x1=2,x2=3,x3=x4=x5=0,max z=-13,故原问题的最优解为：
x1=2,x2=3,x3 =0,min s=13。
四、利用大M法求解下面线性规划问题:
0,,6242..2max32121321321xxxxxxxxtsxxxs
解：引入松弛变量x4和人工变量x5，构造如下规划：
0,,,,6242..2max5432152143215321xxxxxxxxxxxxtsMxxxxs
对应基B0＝（P4,P5）的单纯形表为
T(B0)= 4 －2 1 1 1 0
6 1 2 0 0
1 6M -1+M 2+2M 1 0
0
x1的检验数为-1+ M>0，x1进基，由min｛6/1｝=6/1知，x5出基，迭代得新基B1=(P4,P1),对应的单纯形表为
T(B1)= 16 0 5 1 1 2
6 1 2 0 0 1
6 0 4 1 0 1-M
x3的检验数为1>0，x3进基，由min｛16/1｝=16/1知，x4出基，迭代得新基B2=(P3,P1),对应的单纯形表为
T(B2)= 16 0 5 1 1 2
6 1 2 0 0 1
-10 0 -1 0 -1
-1-M
至此，检验数全为非正，已为最优单纯形表。对应的最优解为：
x1=6,x2=0,x3=16,x4=x5=0,最优值max z=10。
五、已知线性规划问题(L):
0,,823622..32min321321321321xxxxxxxxxtsxxxs
(1)写出该问题的对偶表,从而给出其对偶问题(D).
(2)用对偶单纯形法求解问题.
解：(1)该问题的对偶表,
x1 x2 x3 Min
Max 其对偶问题(D)为
max Z=6y1+8y2
2y1+ y2≤1
y1+3y2≤2
2y1+2y2≤3
y1,y2≥0 1 2 3 c
b
2 1 2 6 y1
1 3 2 8 y2
(2)用对偶单纯形法求解问题. 引入松弛变量x4、x5，构造如下规划：
0x,x,x,x,x8x2x3xx6x2xx2xs.t.3x2xxSmaxZ5432153214321321
对应基B0＝（P4,P5）的单纯形表为
T(B0)= －6 -2 -1 -2 1 0
－8 -1 -3 -2 0 1
0 -1 -2 -3 0 0
检验数全为非正，基变量x4＝－6，x4出基,利用偶单纯形法，由min｛－1/－2，－2/-1,-3/-2｝=－1/－2知，x1进基，迭代得新基B1=(P1,P5),对应的单纯形表为
T(B1)= 3 1 1/2 1 -1/2 0
－5 0 -5/2 -1 -1/2 1
3 0 -3/2 -2 -1/2 0
基变量x5＝－5，x5出基,利用偶单纯形法知，x2进基，迭代得新基B2=(P1,P2),对应的单纯形表为
T(B2)= 2 1 0 4/5 -3/5 1/5
2 0 1 2/5 1/5 -2/5
6 0 0 -7/5 -1/5 -3/5
至此,得到最优解:x1=x2=2,x3=x4=x5=0,最优值maxZ=-6,故原问题的最优解为:
x1=x2=2,x3=0, 最优值minS=6.
六、某运输问题的产销平衡表和运价表如下，试用表上作业法求最优调运方案。
销地
产地 B1 B2 B3 产量
A1
A2
A3 1
0
3 2
4
1 6
2
5 7
12
11
销量 10 10 10
30
解：由最小元素法得初始运输方案
B1 B2 B3 产量
A1
A2
A3 10
10 7
2
1 7
12
11
销量 10 10 10 30
总运费S=0×10＋1×10＋6×7＋2×2＋5×1=61
经计算λ11＝（6＋0）－（2＋1）＝3>0,调整量Δ=min（7,10）＝7，
经调整，得新运输方案：
B1 B2 B3 产量
A1
A2
A3 7
3
10
9
1 7
12
11
销量 10 10 10 30
总运费S=61－3×7＝40
至此，所有检验数均以非正，该运输方案已为最优。即：
A1运到B1 7个单位；A2运到B1 3个单位；A2运到B3 9个单位 A3运到B2 10个单位；A3运到B3 1个单位；总运费S＝40个单位
七、某极大化整数规划对应的线性规划的最优单纯形表如下：
5/2 0 1 1/2 -1/2
13/4 1 0 -1/4 3/4
-69/4 0 0 -3/4 -3/4
试建立割平面方程并求原整数规划的最优解。
解：由x2=5/2为非整数，对应方程为：5/2=x2+1/2x3-1/2x4
即：x2－x4-2=1/2-(1/2x3+1/2x4),得Gomery割平面：1/2-(1/2x3+1/2x4)<0
引入松弛变量x5,添加约束： -1/2x3-1/2x4 ＋x5=－1/2,由表
5/2 0 1 1/2 -1/2 0
13/4 1 0 -1/4 3/4 0
-1/2 0 0 -1/2 -1/2 1
-69/4 0 0 -3/4
-3/4 0
利用对偶单纯形法迭代得到新单纯形表：
2 0 1 0 -1 1
7/2 1 0 0 1 -1/2
1 0 0 1 1 -2
-33/2 0 0 0 0 -3/2
由7/2=x1+x4-1/2x5,得Gomery割平面：1/2-1/2x5+<0
引入松弛变量x6,添加约束： -1/2x5 ＋x6=－1/2,由表
2 0 1 0 -1 1 0
7/2 1 0 0 1 -1/2 0
1 0 0 1 1 -2 0
-1/2 0 0 0 0 -1/2 1
-33/2 0 0 0 0 -3/2
0
利用对偶单纯形法迭代得到新单纯形表：
1 0 1 0 -1 0 -2
4 1 0 0 1 0 -1
3 0 0 1 1 0 -4
1 0 0 0 0 1 -2
-15 0 0 0 0 0 -3 至此，已得到整数解：x1=4,x2=1,x3=3,x4=0,最优值为15。
八、线性规划问题如下：
max s= -x1+2x2
-x1+x2≤2………………资源1
x1+2x2≤6………………资源2
x1，x2≥0
（1） 用单纯形法求最优解；
（2） 资源1的影子价格；
（3） 资源2由目前的6变为8，最优值会发生怎样的变化，最优解是多少?
（4） 对c2进行灵敏度分析。
解：(1)引入松弛变量x3,x4,原问题化为标准型：
max s=-x1+2x2
-x1+x2＋x3 ＝2
x1+2x2 ＋x4＝6
x1，x2 ，x3 ，x4≥0
对应基B0＝（P3P4）的单纯形表
T(B0)= 2 -1 1 1 0
6 1 2 0 1
0 -1 2 0 0
迭代得到新基B1＝（P2P4）,对应的单纯形表为：
T(B1)= 2 -1 1 1 0
2 3 0 -2 1
－4 1 0 -2
0
迭代得到新基B2＝（P2P1）,对应的单纯形表为：
T(B2)= 8/3 0 1 1/3 1/3
2/3 1 0 -2/3 1/3
-14/3 0 0 -4/3 -1/3
至此，检验数已经请为非正，得原问题得最优解：
x1=2/3,x2=8/3,最优值maxS＝14/3.
（2）由最优单纯形表T(B2)得知资源1的影子价格为松弛变量x3的检验数的负数，即为4/3。
（3）因为最优基B= B2的逆矩阵为
