第一章 线性规划及单纯形法习题
1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。
(1)???
??≥≥+≥++=0,42266432min 2121212
1x x x x x x x x z (2) ???
??≥≥+≥++=0,12432
223max 2
121212
1x x x x x x x x
(3) ??
?
??≤≤≤≤≤++=8
3105120
106max 21212
1x x x x x x z (4)
???
??≥≤+-≥-+=0,2322
265max 1
2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。
(1)?????
?
?≥≥-++-≤+-+-=-+-+-+-=无约束
43214321432143214321,0,,2321422
245243min x x x x x x x x x x x x x x x x x x x x z (2) ?????
?
?≥≤≥-++-≤-+-=++-+-=无约束
32143213213213
21,0,023*******min x x x x x x x x x x x x x x x x z
3.对下列线性规划问题找出所有基本解,指出哪些是基可行解,并确定最优解。
(1) ???
??
?
?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213
21Λj x x x x x x x x x x x x x x z j (2)
???
??=≥=+++=+++++-=)4,,1(0102227
4322325min 432143214321Λj x x x x x x x x x x x x x z j
4.分别用图解发法和单纯形法求解下述问题,并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
(1) ???
??≥≤+≤++=0,825943510max 1
221212
1x x x x x x x x z (2) ?????≥≤+≤++=0,242615
532max 1
221212
1x x x x x x x x z
5.上题(1)中,若目标函数变为21m ax dx cx z +=,讨论c,d 的值如何变化,使该问题可行域的每一顶点依次使目标函数达到最优。
6.考虑下述线性规划问题:
?
????≥≤+≤++=0
,max 122221212121112
1x x b x a x a b
x a x a dx cx z
式中311≤≤c ,642≤≤c , 3111≤≤-a ,5212≤≤a ,1281≤≤b ,
5221≤≤a ,6422≤≤a ,14102≤≤b ,试确定目标函数最优值的下界和上
界。
7.分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题,并指出属哪一类解。
(1) ???
??
?
?=≥≥-≥+-≥+++-=)3,2,1(0022
2622max 32313213
21j x x x x x x x x x x x z j (2) ???
??≥≥+≥++++=0,,62382432min 3
21213213
21x x x x x x x x x x x z
(3) ???
??
?
?=≥=++=-+=++=)4,,1(042634334min 421321212
1Λj x x x x x x x x x x x z j (4)
???
???
?=≥≥++≤++-≤++++=)3,,1(0521515659
35121510max 321321321321Λj x x x x x x x x x x x x x z j
8.已知某线性规划问题的初始单纯形表和单纯形法迭代后得到的表1-1,试求括号中未知数a ~l 的值。
9.若)2()
1(,X X
均为某线性规划问题的最优解,证明在两点连线上的所
有点也是该问题的最优解。
10. 线性规划问题max z=CX ,AX=b ,X ≥0,设0X 为问题的最优解。若目标函数中用C *代替C 后,问题的最优解变为*
X ,求证:
(C *-C)( X *- X 0)≥0
11. 考虑线性规划问题
???
??=≥+=-+-+=-+-++=)4,,1(0)
(7522)(242max 43214214321Λj x ii
x x x x i x x x x x x x z j
ββα
模型中βα,,为参数,要求:
(1)组成两个新的约束),()()('
ii i i +=根据,)(,)('
'
ii i 以x 1,x 2为基变量,列出初始单纯形表;
(2)在表中,假定0=β,则α为何值时,x 1,x 2为问题的最优基;
(3)在表中,假定3=α,则β为何值时,x 1,x 2为问题的最优基。
12. 线性规划问题max z=CX ,AX=b ,X ≥0,如X ·是该问题的最优解,又且>0为某一常数,分别讨论下列情况时最优解的变化。
(1)目标函数变为maxz =λCX ; (2)目标函数变为max2=(C+λ)X ;
(3)目标函数变为maxz λ
C
=
x ,约束条件变为AX=b λ
13. 某饲养场饲养动物出售,设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单价如表1—2所示:
个问题的线性规划模型,不求解)
14. 某医院护士值班班次、每班工作时间及各班所需护士数如表1-3所示。每班护士值班开始时向病房报到,试决定:
(1)若护士上班后连续工作8小时。该医院最少需多少名护士,以满足轮班需要
(2)若除22点上班的护士连续工作8小时外,其他护士由医院排定上1~4班中的两个,则该医院又需多少名护士,以满足轮班需要
15. 一艘货轮分前、中、后三个舱位,它们的容积与最大允许载重量如表1-4所示。现有三种货物待运,已知有关数据列于表1-5。
表1-4
表1-5
又为了航运安全,前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求:前、后舱分别与中舱之间载重量比例上偏差不超过15%,前、后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大试建立这个问题的线性规划模型。
16.时代服装公司生产一款新的时装,据测今后6个月的需求量如表1-6所示。每件时装用工2小时和10元的原材料非,售价40元。该公司1月初又4个工人,
每人每月可工作200小时,月薪2000元。该公司可于任何一个月初新雇工人,但每雇一人需要一次额外支出1500元,也可辞退工人,但每辞退1人需要补偿1000元。如当月生产数超过需求,可留到后面月份销售,但需付库存每件每月5元。当供不应求时,短缺数不需要补上。试帮助该公司决策,如何使6个月的总利润最大。
17.童心玩具厂下一年度的现金流(万元)如表1-7所示,表中负号所示该月现金流出大于流入,为此该厂需借款。借款有两种方式:一是于上一年末借一年期贷款,一次得全部贷款额,从1月份起每月还息1%,于12月归还本金及最后一次利息;二是得到短期贷款。每月初获得,于月底还,月息%,当该厂有多余现金时,可短期存款,月初存入,月末取出,月息%。问该厂应如何进行贷款操作,即能弥补可能出现得负现金流,又可使年末现金总量最大
18. 宏银公司承诺为某建设项目从2003年起得4年中每年初分别提供以下数额贷款:2003年——100万元,2004年——150万元,2005年——120万元,2006年——110万元。以上贷款均于2002年底筹集齐。但为了充分发挥这笔资金得作用,在满足每年贷款额得前提下,可将多于资金分别用于下列投资项目:
(1)于2003年初购买A种债券,期限3年,到期后本息合计为投资额得140%,但限购60万元;
(2)于2003年初购买B种债券,期限2,到期后本息合计为投资额得125%限购90万元;
(3)于2004初购买C种债券,期限2,到期后本息合计为投资额得130%,但限购50万元;
(4)于每年年初将任意数额的资金存放于银行,年息4%,于每年底取出。求宏银公司应如何用这笔筹集到的资金存放于银行,使得2002年底需要筹集到的资金数额为最少。