第一章 线性规划及单纯形法习题
1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。
minz?2x1?3x2（1）?max?3x1?2x2 (2) ??4x1?6x2?6?2x1?2x2?4?x,x?0?12?2x1?x2?2
3x?4x?12?12?x,x?0?12maxz?5x1?6x2maxz?x1?x2 (3) ??6x1?10x2?120?2x1?x2?2 (4) ?
??2x1?3x2?2?5?x1?10?x,x?0?3?x?82?21?2.将下列线性规划问题化成标准形式。
minz??3x1?4x2?2x3?5x4?4x1?x2?2x3?x4??2?(1)?x1?x2?x3?2x4?14???2x1?3x2?x3?x4?2??x1,x2,x3?0,x4无约束minz?2x1?2x2?3x3??x1?x2?x3?4? (2) ??2x1?x2?x3?6
???2x1?3x2?x3?x4?2??x1?0,x2?0,x3无约束3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优
解。
minz?3x1?x2?2x3?12x1?3x2?6x3?3x4?9?x1?2x2?3x3?4x4?7?8x?x?4x?2x?10 (1) ?1 (2) ?234?2x1?2x2?x3?2x4?10??x?0(j?1,?,4)?3x1?x6?2?j?xj?0(j?1,?,6)?minz?5x1?2x2?3x3?2x4
4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可
行解对应图解法中可行域的哪一顶点。
1
maxz?10x1?5x2?3x1?4x2?9 (1) ??5x1?2x2?8?x,x?0?21maxz?2x1?x2?3x1?5x2?15 (2) ?
6x?2x?24?12?x,x?0?215.上题（1）中，若目标函数变为maxz?cx1?dx2，讨论c,d的值如何变化，使该问题可行域的每一顶点依次使目标函数达到最优。
6.考虑下述线性规划问题：
maxz?cx1?dx2?a11x1?a12x2?b ?
?a21x1?a22x2?b??x2,x1?0式中1?c1?3,4?c2?6 , ?1?a11?3,2?a12?5,8?b1?12,
2?a21?5,4?a22?6,10?b2?14，试确定目标函数最优值的下界和上
界。
7.分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。
maxz?2x1?x2?2x3?x1?x2?x3?6? (1) ??2x1?x3?2??2x2?x3?0?xj?0(j?1,2,3)?minz?4x1?x2minz?2x1?3x2?x3 (2) ??x1?4x2?2x3?8?3x1?2x2?6?x,x,x?0?123
maxz?10x1?15x2?12x3
?5x1?3x2?x3?9?3x1?x2?3?? (3) ?4x1?3x2?x3?6 (4) ??5x1?6x2?15x3?15??x?2x?x?424?1?2x1?x2?x3?5?xj?0(j?1,?,4)?xj?0(j?1,?,3)??8.已知某线性规划问题的初始单纯形表和单纯形法迭代后得到的表
1-1，试求括号中未知数a～l的值。
2
表1-1 x4 x5 6 1 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) cj?zj x1 x5 (f) 4 cj?zj 9.若X(1),X(2) 均为某线性规划问题的最优解，证明在两点连线上的所有点也是该问题的最优解。
10. 线性规划问题max z=CX，AX=b，X≥0，设X为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X，求证:
**0
(C-C)( X- X)≥0
11. 考虑线性规划问题
*0maxz??x1?2x2?x3?x4?x1?x2?x4?4?2???2x1?x2?x3?2x4?5?7??x?0(j?1,?,4)?j模型中?,?,为参数，要求：
(1)组成两个新的约束(i)'?(i)?(ii),根据(i)',(ii)',以x1，x2为基变量，列出初始单纯形表；
(2)在表中，假定??0,则?为何值时，x1，x2为问题的最优基；
(i)(ii)
(3)在表中，假定??3,则?为何值时，x1，x2为问题的最优基。
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所示：
表1-2 饲料
蛋白质(g) 矿物质(g) 3
维生素(mg) 价格(元／kg) 1 2 3 4 5 3 2 1 6 18 1 0.5 0.2 2 0.5 0.5 1.0 0.2 2 0.8 0.2 0.7 0.4 0.3 0.8 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。(建立这个问题的线性规划模型，不求解) 14. 某医院护士值班班次、每班工作时间及各班所需护士数如表1-3所示。每班护士值班开始时向病房报到，试决定：
（1）若护士上班后连续工作8小时。该医院最少需多少名护士，以满足轮班需要？
（2）若除22点上班的护士连续工作8小时外，其他护士由医院排定上1～4班中的两个，则该医院又需多少名护士，以满足轮班需要？ 表1-3 班 次 1 2 3 4 5 6 工作时间 6:00-10:00 10:00-14:00 14:00-18:00 18:00-22:00 22:00-2:00 2:00-6:00 所需护士人数 60 70 60 50 20 30 15. 一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-4所示。现有三种货物待运，已知有关数据列于表1-5。
表1-4
最大允许载重量（t） 3容 积（m） 表1-5
前 舱 2000 4000 3中 舱 3000 5400 每件重量(t/件) 8 6 5 后 舱 1500 1500 运价(元/件) 1000 700 600 商品 A B C 数量(件) 600 1000 800 每件体积(m/件) 10 5 7 又为了航运安全，前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例上偏差不超过15％，前、后舱之间不超过10％。问该货轮应装载A、B、C各多少件运费收入才最大?试建立这个问题的线性规划模型。 16. 时代服装公司生产一款新的时装，据测今后6个月的需求量如表1－6所示。每件时装用工2小时和10元的原材料非，售价40元。该公司1月初又4个工人，
4
每人每月可工作200小时，月薪2000元。该公司可于任何一个月初新雇工人，但每雇一人需要一次额外支出1500元，也可辞退工人，但每辞退1人需要补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存每件每月5元。当供不应求时，短缺数不需要补上。试帮助该公司决策，如何使6个月的总利润最大。
表1－6 月份 1 2 3 4 5 6 需求 500 600 300 400 500 800
17． 童心玩具厂下一年度的现金流（万元）如表1－7所示，表中负号所示该月现金流出大于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月份起每月还息1％，于12月归还本金及最后一次利息；二是得到短期贷款。每月初获得，于月底还，月息1.5％，当该厂有多余现金时，可短期存款，月初存入，月末取出，月息0.4％。问该厂应如何进行贷款操作，即能弥补可能出现得负现金流，又可使年末现金总量最大？
表1－7 月份 现金流 1 2 3 4 5 6 7 8 9 10 11 12 －12－10－8 －10 －4 5 －7 －2 15 12 －7 45 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年底需要筹集到的资金数额为最少。
5