第二章 线性规划习题(附答案)
- 格式:doc
- 大小:938.50 KB
- 文档页数:23
习题
2-1 判断下列说法是否正确:
(1) 任何线性规划问题存在并具有惟一的对偶问题; (2) 对偶问题的对偶问题一定是原问题;
(3) 根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,
当对偶问题无可行解时,其原问题具有无界解;
(4) 若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多最优
解;
(5) 若线性规划问题中的b i ,c j 值同时发生变化,反映到最终单纯形表中,不会出
现原问题与对偶问题均为非可行解的情况; (6) 应用对偶单纯形法计算时,若单纯形表中某一基变量x i <0,又x i 所在行的元素全
部大于或等于零,则可以判断其对偶问题具有无界解。 (7) 若某种资源的影子价格等于k ,在其他条件不变的情况下,当该种资源增加
5个单位时,相应的目标函数值将增大5k ;
(8) 已知y i 为线性规划的对偶问题的最优解,若y i >0,说明在最优生产计划中第
i 种资源已经完全耗尽;若y i =0,说明在最优生产计划中的第i 种资源一定有剩余。
2-2将下述线性规划问题化成标准形式。
⎪⎪⎩
⎪⎪
⎨
⎧≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()⎪⎩⎪
⎨⎧≥≤≤-+-=++-+-=无约束
321
3213213
21,0,06
24
.322min 2x x x x x x x x x st x x x z 解:(1)令'''
444x x x =-,增加松弛变量5x ,剩余变量6x ,则该问题的标准形式如下
所示:
'''
12344'''
12344'''
123445'''
123446'''1234456max 342554222214..232
,,,,,,0
z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-⎧-+-+-=⎪+-+-+=⎪⎨-++-+-=⎪⎪≥⎩ (2)令'
z z =-,'11x x =-,'''333x x x =-,增加松弛变量4x ,则该问题的标准
形式如下所示:
'''''
1233''''
1233''''
12334''''12334
max 22334
..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+⎧++-=⎪+-++=⎨⎪≥⎩ 2-3分别用图解法和单纯形法求解下述线性规划问题,并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
()⎪⎩⎪
⎨⎧≥≤+≤++=0,825943.510max 12
1212121x x x x x x st x x z ()⎪⎩⎪
⎨⎧≥≤+≤++=0,242615
53.2max 22
121212
1x x x x x x st x x z 解:(1)图解法
最优点为B 点,最优解为x1=1,x2=3/2,最优值为35/2。 单纯形表计算过程:
初始单纯形表(对应O 点)
z ’ x 1 x 2 x 3 x 4 RHS z ’
x 3 9/3 x 4 8/5 第一次迭代(对应A 点)
z ’ x
x x x RHS z ’
x 3 /14/5
x 1
8/5/4/5
●第二次迭代(对应B点,即最优解)
z’x1x2x3x4RHS
z’
x2
x1
(2)图解法
初始单纯形表(对应O点)
z’x1x2x3x4RHS
z’
x315/3
x424/6
第一次迭代(对应A点)
z’x1x2x3x4RHS
z’
x33/4
x14/1/3 ●第二次迭代(对应B点,即最优解)
z’x1x2x3x4RHS
x2
x1
⎪⎩
⎪
⎨⎧≥≤++++≤++++057234219
532..5432154321j x x x x x x x x x x x t s ⎪⎪⎪⎩⎪⎪⎪
⎨⎧≥≥+≥+≥+++≥++022633
2..31434321421j x x x x x x x x x x x x t s 2-4已知线性规划问题,写出其对偶问题:
(1)
(2)
解:(1)原问题的对偶问题为:
12121
21
2121212min 1957210424
2320..3220525,0
y y y y y y y y s t y y y y y y ω=++≥⎧⎪+≥⎪⎪+≥⎪⎨+≥⎪⎪+≥⎪≥⎪⎩
(2)原问题的对偶问题为:
123412412234123
1234max 36223826
..36
,,,0
y y y y y y y y y s t y y y y y y y y y y ω=+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩
2-5运用对偶理论求解以下各问题: (1)已知线性规划问题: 543212*********max x x x x x z ++++=)5,4,3,2,1(=j 43216368min x x x x z +++=)4,3,2,1(=j 3
2
1
22min x
x x z +-=