第一章习题
1.思考题
(1)微分学求极值的方法为什么不适用于线性规划的求解?
(2)线性规划的标准形有哪些限制?如何把一般的线性规划化为标准形式?
(3)图解法主要步骤是什么?从中可以看出线性规划最优解有那些特点?
(4)什么是线性规划的可行解,基本解,基可行解?引入基本解和基可行解有什么作用?
(5)对于任意基可行解,为什么必须把目标函数用非基变量表示出来?什么是检验数?它有什么作用?如何计算检验数?
(6)确定换出变量的法则是什么?违背这一法则,会发生什么问题?
(7)如何进行换基迭代运算?
(8)大M法与两阶段法的要点是什么?两者有什么共同点?有什么区别?
(9)松弛变量与人工变量有什么区别?试从定义和处理方式两方面分析。
(10)如何判定线性规划有唯一最优解,无穷多最优解和无最优解?为什么?
2.建立下列问题的线性规划模型:
(1)某厂生产A,B,C三种产品,每件产品消耗的原料和设备台时如表1-18所示:
润最大的模型。
(2)某公司打算利用具有下列成分(见表1-19)的合金配制一种新型合金100公斤,新合金含铅,锌,锡的比例为3:2:5。
如何安排配方,使成本最低?
(3)某医院每天各时间段至少需要配备护理人员数量见表1-20。
表1-20
假定每人上班后连续工作8小时,试建立使总人数最少的计划安排模型。能否利用初等数学的视察法,求出它的最优解?
(4)某工地需要30套三角架,其结构尺寸如图1-6所示。仓库现有长6.5米的钢材。如何下料,使消耗的钢材最少?
图1-6
3. 用图解法求下列线性规划的最优解:
??????
?≥≤+-≥+≥++=0
,425.134 1
2 64 min )1(21212
12121x x x x x x x x x x z
??????
?≥≤+≥+-≤++=0
,82 5 1032 44 max )2(21212
12121x x x x x x x x x x z
?????
????≥≤≤-≤+-≤++=0
,6
054 4 22232 96 max )3(2122
1212121x x x x x x
x x x x x z
???
??≥≤+-≥+
+=0,1 12
34 3 max )4(2
12
12121x x x x x x x x z
4. 把下列线性规划化为标准形式:
??????
?≥≤=-++-≥-+≤-+-+-=无约束
432143213
214313
210,,01 32 21
2 min )1(x x x x x x x x x x x x x x x x x z
??????
?≤≤≥+-≤++=无约束
2112
12121,02
1
82 32 max )2(x x x x x x x x x z
5. 判定下列集合是否凸集:
(1)R 1={(x 1,x 2)|x 12+2x 22≤2}
(2)R 2={(x 1,x 2)|x 12-2x 2+3≥0,x 2≥0,|x 1|≤1} (3)R 3={(x 1,x 2)|x 1x 2≥1,x 1≥1,x 2≥0}
6. 求出下列线性规划的所有基本解,并指出其中的基可行解和最优解。
???
???
?=≥=++=+=++=5,,1 ,018
2 312 2 48
53 max 52142312
1 j x x x x x x x x x x z j
7. 求下列线性规划的解: (1)
(2)
??????
?≥≤+≤≤+=0
,182 36 8
2 5
3 max 2121212
1x x x x x x x x z
???
??≥≤+-≤++=0,1 4
2 42 max 2
121212
1x x x x x x x x z
(3)
(4)
???
??≥≤+--≥+-+=0,12
2 2 max 2
121212
1x x x x x x x x z
??????
?≥≤≥≤--≤++≤+-++=0
,0,020102603 2 max 3213213213213
21x x x x x x x x x x x x x x x z
8. 利用大M 法或两阶段法求解下列线性规划: (1)
(2)
???????≥≥+≥-≤++=0
,217
2 2
3 max 212121
212
1x x x x x x x x x x z
??????
?≥=-+≤+≥++--=0
,,54 218
23 2 max 321321213213
21x x x x x x x x x x x x x x z (3)
(4)
???????≥≥≤-≥++-=0
,2 6 312
34 max 21221
212
1x x x x x x x x x z
???
??≥≥+++≥++++++=0,,,1223615
263 343 min 4
321432143214
321x x x x x x x x x x x x x x x x z 9. 对于问题
??
?≥==0
b max X AX CX z (1)设最优解为X *,当C 改为C 时,最优解为X ,则0))((*
≥--X X C C 。
(2)如果X 1,X 2均为最优解,则对于α∈[0,1],αX 1+(1-α)X 2均为最优解。 10. 用单纯形法求解问题2(4)(合理下料问题)。
11. 表1-21是一个求极大值线性规划的单纯形表,其中x 4,x 5,x 6是松弛变量。
(2)要使上表成为最优表,a 应满足什么条件? (3)何时有无穷多最优解? (4)何时无最优解?
(5)何时应以x 3替换x 1?
第二章习题
1.思考题
(1)如何在以B为基的单纯形表中,找出B-1?该表是怎样由初始表得到的?
(2)对偶问题的构成要素之间,有哪些对应规律?
(3)如何从原问题最优表中,直接找到对偶最优解?
(4)叙述互补松弛定理及其经济意义。
(5)什么是资源的影子价格?它在经济管理中有什么作用?
(6)对偶单纯形法有哪些操作要点?它与单纯形法有哪些相同,哪些地方有区别?
(7)灵敏度分析主要讨论什么问题?分析的基本思路是什么?四种基本情况的分析要点是什么?
2.已知某线性规划的初始单纯形表和最终单纯形表如表2-21,请把表中空白处的数字填上,并指出最优基B及B-1。
3.某个线性规划的最终表是表2-22:
表2-22
初始基变量是1,4,5。
(1)求最优基B=(P1,P2,P3);
(2)求初始表。
4.写出下列线性规划的对偶问题:
??????
?≤≥=+-≥-+-≤+++-=无约束3213213
21321321,0,0131
4242 3 max )1(x x x x x x x x x x x x x x x z ??????
?≤≥≥++=++-≤--+++-=无约束
43214313
2143214321,,0,012
22 242 32 min (2)x x x x x x x x x x x x x x x x x x z ???
??
??????????+=≤+==≥+=≥+===≤=∑∑∑∑====n
n j x n n j x n j x m
m i b x a m m i b x a m i b x a x c z j
j j i n
j j ij i n
j j ij i n
j j ij n
j j
j ,,1,0,,1,,,1,0,,1,,,1,,,2,1, max (3)22112
12
11
111
无约束 ??????
?????==≥=====∑∑∑∑====n
j m i x n
j b x m i a x x c z ij j m i ij i n
j ij m i n
j ij
ij ,,1 ,,10,,1 ,,1
min (4)1
111
5. 已知线性规划
???
??≥≥++≥++++=0,, min 3
212
3232221211
313212111332211x x x b x a x a x a b x a x a x a x c x c x c z (1)写出它的对偶问题;
(2)引入松弛变量,化为标准形式,再写出对偶问题; (3)引入人工变量,把问题化为等价模型:
???
??≥=+-++=+-+++-++=0
,,
)( max 71
2
7532322212116431321211176332211x x b x x x a x a x a b x x x a x a x a x x M x c x c x c z 再写出它的对偶问题。
试说明上面三个对偶问题是完全一致的。由此,可以得出什么样的一般结论? 6. 利用对偶理论说明下列线性规划无最优解:
???
??≥≤≥≥+--≥++-+-=0
,0,03224
2 max 321
3213213
21x x x x x x x x x x x x z 7. 已知表2-23是某线性规划的最优表,其中x 4,x 5为松弛变量,两个约束条件为≤
型。
j (2)写出原问题的对偶问题; (3)由表2-23求对偶最优解。 8. 已知线性规划问题
?????
??
??=≥≥+≥+≥+++≥+++++=4
,3,2,1,02 2 633 2 6368 min 314343214214321j x x x x x x x x x x x x x x x x z j
(1)写出对偶问题;
(2)已知原问题的最优解为X *=(1,1,2,0)T ,求对偶问题的最优解。 9*. 已知线性规划
??????
?≥=+-≥++≤--+-=无约束
3213213
21321321,0,41
632532 34 max x x x x x x x x x x x x x x x z 的最优解为X *=(0,0,4)T 。
(1)写出对偶问题; (2)求对偶问题最优解。
10. 用对偶单纯形法解下列各线性规划:
?????≥≥+-≥++++=0,,4
3232 432 min (1)3
21321321321x x x x x x x x x x x x z
?????≥≥++≥++++=0,,10
536423 425 min (2)3
213213213
21x x x x x x x x x x x x z
11. 设线性规划问题
????
?=≥=≤=∑∑==n j x m i b x a x c z j
i n
j j ij n
j j
j ,,2,1 ,0,,2,1 max 11
(2.41)
的m 种资源的影子价格为y 1*,y 2*,…,y m *。 线性规划