运筹学练习题
最优解:X*=(3.75,0.75,0,0)T,MaxZ=8.25
第二章
1. 如果线性规划的原问题存在可行解,则其对偶问题 也一定存在可行解;
2. 如果线性规划问题的对偶问题无可行解,则原问题 也一定无可行解; 3. 在互为对偶的一对原问题与对偶问题中,原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标 函数值;
用对偶单纯形法求解下列线性规划问题 minz=4x1+12x2+18x3 x1 +3x3 ≥3 st 2 x2+2x3 ≥5 xj≥0 (j=1,2,3) MAXZ=-4X1-12X2-18X3 -X1 -3X3+X4 =-3 ST -2 X2 -2X3 +X5=-5 XJ≥0
CB 0
c j XB x4
,,,,,
(7)、单纯形法计算中,如不按θi最小原则选取换出变量,则 在下一个解中至少有一个基变量的值为负
(8)、一旦人工变量在迭代中离基,该变量及相应列在单纯 形表中的数字可以不再计算,而不会影响计算结果 (9)、对一个有n个变量、m个约束的SLP问题,其可行域的 顶点恰好为Cnm个
10 b 3/2 1 x1 0 1
5 x2 1 0
0 x3 5/14
0 x4 -3/14 2/7
4 12 0 12
x2 3/2 x1 1 j x3 21/5 x1 8/5
0 1 0 0 1 0
1 0 0 14/5 2/5 -4/5
5/14
-1/7 2/7
-3/14 2/7 -18/7 -3/5 1/5 -12/5
CB 0 0
a 0
cj XB x4 x5
a
1
b 6 1
f 4
j
x1 x5
j
x1 b -1 a 1 0 0
x2 c 3 1 2 i -7
-2 x3 d e
0
0
-2 -1 1 j
x4 1 0 0 1/2 1/2 k
x5 0 1 0 0 1 l
i
① ②
③ ④ ⑤ ⑥
(3) x5为基变量, l=0; (4)p4由第一个表的[1,0]T变为第二个表中的[1/2,1/2]T, 即① /2= ④ ,因此, f=3; b=2; c=4; d=-2;
CB
cj XB xm xn j xs xt j
b 6 1 f 4
x1 b -1 a g h 0
x2 c 3 1 2 i -7
x3 d e -2 -1 1 j
x4 1 0 0 1/2 1/2 k
x5 0 1 0 0 1 l
i
[解](1)因为初始表中x4、x5为基变量,所以, m=4;n=5;
— 1 0 0 - -1/3 1/3 -2
1 0
— 0 -1/2 -6 - 0 -1/2 -6
j i
-18 -12 x3 x2 1 3/2
j
最优解X*=(0,3/2,1)T ,MINZ=36
灵敏度分析
已知线性规划问题 MaxZ =10x1+5x2 3x1+4x2 ≤9 s.t 5x1+2x2 ≤ 8 x1,x2≥0 最优表如右:
1.互为对偶的两个线性规划问题的解存在关系( B) A.原问题无可行解,对偶问题也无可行解; B.对偶问题有可行解,原问题可能无可行解; C.若最优解存在,则最优解相同; D.一个问题无可行解,则另一个问题具有无界解。 2. 当某一cj发生改变,则( A C) A. 原最优解可能发生改变; B. 原可行解可能改变; C. 原可行解不变; D. 不确定
CB 10 5 4 10
c j XB x2 x1
b 3/2
1
j
4 10 x1 0 1 0
10 5 x2 1 0 0
0 x3 5/14 -1/7 -5/14
0 x4 -3/14 2/7 -25/14
1、若c1=4, c2=10,则上述最优解是否改变? 解:将c1=4, c2=10 代入单纯形表:
CB 0 0
a 0
cj XB x4 x54
j
x1 x5
j
i=5; e=2;
x1 2 -1 a 1 0 0
x2 4 3 1 2 i -7
-2 x3 -2 e
0
0
-2 -1 1 j
x4 1 0 0 1/2 1/2 k
x5 0 1 0 0 1 0
i
① ②
③ ④ ⑤ ⑥
(5)同理,行②+行 ④ =行⑤ (6) σ2 =1-2a=-7,所以,a=4; (7)j=6;k=-2;
第一章
(1)、图解法与单纯形法虽然求解的形式不同,但从几何意 义上理解,两者结果是一致的 (2)、线性规划模型中增加一个约束条件,可行域的范围一 般将缩小;反之一般将扩大 (3)、线性规划问题的每一个基解对应可行域的一个顶点 (4)、如果线性规划问题存在最优解,则最优解一定对应可 行域的某一个顶点 (5)、如果线性规划问题存在最优解,则最优解一定对应可 行域边界上的一个点 (6)、用单纯形法求解SLP问题时,只要检验数j >0所对应 的变量都可以被选作入基变量
1、价值系数 c1和 c2分别在什么范围内变动,上述最优解 不变; CB 5+ 5 c2 10 c j XB x2 x1 b 3/2 1 10 x1 0 1 0
5+5 c2
x2 1 0 0
0 x3 5/14 -1/7 -5/14
0 x4 -3/14 2/7 -25/14
j
将c′2=5+ c2代入最优表中 [解] ′3 = 0-5/14(5+c2)+10/7≤0,c2≥ -1 ′4= 0+3/14(5+c2 )-20/7≤0,c2≤ 25/3 当-1≤ c1 ≤25/3 ,即4≤ c2 ≤40/3时,最优解不变
CB 0 0
cj XB x4 x5
a
1
b 6 1
f 4
j
xs xt
j
x1 b -1 a g h 0
x2 c 3 1 2 i -7
-2 x3 d e
0
0
-2 -1 1 j
x4 1 0 0 1/2 1/2 k
x5 0 1 0 0 1 l
i
(2)迭代后的表中,基变量为: x1、x5,因此: g=1 ; h=0; s=1;t=5;
0 x3 5/14
0
j i
0 10 x4 x1 2/3 11/3
x4 [ -3/14] 2/7 -1/7 -5/14 -25/14 - -5/3 1/3 -10/3 1 0 0
0 1 0
j
得新最优解X*=(11/3,0,0,2/3)T
练习
XB x3 x1 b 5/2 5/2 x1 0 1 0 x2 1/2 -1/2 -4 x3 1 0 0 x4 1/2 -1/6 -4 x5 0 1/3 -2
4、任何线性规划问题具有唯一的对偶问题;
5、对偶问题的对偶问题一定是原问题; 6、若LP问题有可行解且有界,则有最优解;
7、若LP及其对偶问题都具有可行解,则两者都具有 最优解 8、若线性规划的原问题有无穷多最优解,则其对偶问 题也一定具有无穷多最优解;
9、已知yi为线性规划的对偶问题的最优解,若yi >0, 则说明在最优生产计划中第i种资源已完全耗尽; 10. 已知yi为线性规划的对偶问题的最优解,若yi =0, 则说明在最优生产计划中第i种资源一定有剩余。
maxz=2x1+x2 3x1+5x2≤15 st 6x1+2x2≤24 x1,x2≥0
SLP:MaxZ=2X1+X2 3X1+5X2+X3 =15 6X1+2X2 +X4 =24 X1,X2,X3,X4≥0
c j CB 0 XB x3 b 15
0
0 2
x4
24
j
x3 x1
3 4
j
10+10 c1 x1 j
将c′1=10+ c1 代入最优表中 [解] ′3 = 0-25/14+1/7(10+c1 )≤0,c1 ≤5/2 ′4= 0+15/14-2/7(10+c1 )≤0,c1 ≥-25/4 当-25/4 ≤ c1 ≤5/2 ,即15/4 ≤ c1 ≤25/2时,最优解不变
1 2
x2
x1
0.75 3.75
j
2 1 0 x1 x2 x3 3 5 1 0 [6 ] 2 2 1 0 0 [4] 1 1 1/3 0 0 1/3 0 0 1 1/4 1 0 -1/12 0 0 -1/12
0 x4 0 1 0 -1/2 1/6 -1/3 -1/8 5/24 -7/24
i
15/3 24/6 3/4 12
j
已知某单纯形法求解的最优表,表中 x4 、 x5 为松驰 变量,原问题的约束为≤形式。 (1)直接写出该问题及其对偶问题的最优解;
x1 y1 x2 y2 x3 y3 x4 y4 x5 y5
原问题最优解X*=(5/2, 0, 5/2, 0, 0)T 对偶问题最优解Y*=(4,2,0,4,0)
XB x3 x1
1
0 0
j
得新最优解X*=(8/5,0,21/5,0)T
CB 5 10
c j XB x2 x1
b 3/2 1
10 x1 0 1
5 x2 1 0
0 x3 5/14 -1/7 -5/14
0 x4 -3/14 2/7
j
0
0
-25/14
11 9 4、约束条件右端项由 变为 时上述最优解的变化。 19 8 5/14 –3/14 11 -1/7 -1 [解] B b′= -1/7 2/7 19 = 27/7 最优基改变,用对偶单纯形法继续求解。 CB 5 10
c j XB b x2 -1/7 x1 27/7 10 5 0 0
j
x1 0 1 0
x2 1 0 0