运筹学习题.doc

****题一
用图解法求解下列线性规划问题,并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
(1) min z =6x1+4x2 (2) max z =4x1+8x2
st. 2x1+ x2≥1 st. 2x1+2x2≤10
3x1+ 4x2≥ -x1+ x2≥8
x1, x2≥0 x1, x2≥0
(3) max z = x1+ x2 (4) max z =3x1-2x2
st. 8x1+6x2≥24 st. x1+x2≤1
4x1+6x2≥-12 2x1+2x2≥4
2x2≥4 x1, x2≥0
x1, x2≥0
(5) max z =3x1+9x2 (6) max z =3x1+4x2
st. x1+3x2≤22 st. -x1+2x2≤8
-x1+ x2≤4 x1+2x2≤12
x2≤6 2x1+ x2≤16
2x1-5x2≤0 x1, x2≥0
x1, x2≥0
. 在下列线性规划问题中,找出所有基本解,指出哪些是基本可行解并分别代入目标函数,比较找出最优解。
(1) max z =3x1+5x2 (2) min z =4x1+12x2+18x3
st. x1 + x3 =4 st. x1 +3x3- x4 =3
2x2 + x4 =12 2x2+2x3 - x5=5
3x1+ 2x2 + x5 =18 xj ≥0 (j=1,…,5)
xj ≥0 (j=1,…,5)
. 分别用图解法和单纯形法求解下列线性规划问题,并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。
(1) max z =10x1+5x2
st. 3x1+4x2≤9
5x1+2x2≤8
x1, x2≥0
(2) max z =100x1+200x2
st. x1+ x2≤500
x1 ≤200
2x1+6x2≤1200
x1, x2≥0
. 分别用大M法和两阶段法求解下列线性规划问题,并指出问题的解属于哪一类:
(1) max z =4x1+5x2+ x3 (2) max z =2x1+ x2+ x3
st. 3x1+2x2+ x3≥18 st. 4x1+2x2+2x3≥4
2x1+ x2 ≤4 2x1+4x2 ≤20
x1+ x2- x3=5 4x1+8x2+2x3≤16
xj ≥0 (j=1,2,3) xj ≥0 (j=1,2,3)
(3) max z = x1+ x2 (4) max z =x1+2x2+3x3-x4
st. 8x1+6x2≥24 st. x1+2x2+3x3=15
4x1+6x2≥-12 2x1+ x2+5x3=20
2x2≥4 x1+2x2+ x3+ x4=10
x1, x2≥0 xj ≥0 (j=1,…,4)
(5) max z =4x1+6x2 (6) max z =5x1+3x2+6x3
st. 2x1+4x2 ≤180 st. x1+2x2+ x3≤18
3x1+2x2 ≤150 2x1+ x2+3x3≤16
x1+ x2=57 x1+ x2+ x3=10
x2≥22 x1, x2≥0,x3无约束
x1, x2≥0
线性规划问题max z=CX,AX=b,X≥0,如X*是该问题的最优解,又λ>0为某一常数,分别讨论下列情况时最优解的变化:
目标函数变为max z=λCX;
目标函数变为max z=(C+λ)X;
目标函数变为max z=X,约束条件变为AX=λb。
下表中给出某求极大化问题的单纯形表,问表中a1, a2, c1, c2, d为何值时以及表中变量属于哪一种类型时有:
表中解为唯一最优解;
表中解为无穷多最优解之一;
表中解为退化的可行解;
下一步迭代将以x1替换基变量x5 ;
该线性规划问题具有无界解;
该线性规划问题无可行解。
x1 x2 x3 x4 x5
x3 d 4 a1 1 0 0
x4 2 -1 -5 0 1 0
x5 3 a2 -3 0 0 1
cj -zj c1 c2 0 0 0
战斗机是一种重要的作战工具,但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外,需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj(j=1,…,n),又每架战斗机每年能培训出k名驾驶员,问应如何分配每年生产出来的战斗机,使在n年内生产出来的战斗机为空防作出最大贡献?
. 某石油管道公司希望知道,在下图所示的管道网络中可以流过的最大流量是多少及怎样输送,弧上数字是容量限制。请建立此问题的线性规划模型,不必求解。
2 5 4
10
3 1