运筹学习题解答（chap1 线性规划及单纯形法）

1、第一章 线性规划及单纯形法一、写出下列线性规划的标准形式，用单纯形法求解，并指出其解属于哪种情况。1、P55,1.3(a) 解：将模型化为标准型 单纯形表如下用单纯形法求解得最终单纯形表如下。1050009341008【5】20110500021/50【14/5】1-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14因所有检验数，已达最优解，最优解是，最优目标值为。由检验数的情况可知，该问题有唯一最优解。2、 P55,1.3(b)s.t解：将模型化为标准型 单纯形表如下210000150510002462010051100

2、121000015051002411/301/600102/30-1/6101/30-1/30015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2因所有检验数，已达最优解，最优解是，最有目标值为。由检验数的情况可知，该问题有唯一最优解。3、 ， 解：将模型化为标准型： 用单纯形法迭代12-10000422-1100081-220100511100112-1000085/21011/20-141/2-1101/20011/2200-1/213/21001/20 最优解为（0，0，4），最优值为-4。4、 解：311114-22101631

3、012-20012-111/201440-1/210010因为所有检验数均已非负，故已是最优解，最优解为（0，2，0，4），-10分最优目标值：。由于最终表中非基变量的检验数为0， 故该问题有无穷多最优解。二、用大M法求解下面的线性规划问题1、P54,1.1(a) 解：将模型化为标准型 单纯形表如下用单纯形法求解得最终单纯形表如下。2300MMM64【6】-1010M8420-1012-8M3-8MMM00312/31-1/601/60M2【8/3】01/3-1-1/31-8M/301/2-M/3M4M/3-1/2031/201-1/41/41/4-1/423/4101/8-3/8-1/83/

4、8001/20M-1/2M所有检验数，已是最优解，最优目标值3。因为有非基变量的检验数为0，此问题属于无穷多最优解的情况。2、P54,1.1(b) 解：将模型化为标准型 单纯形表如下用单纯形法求解得最终单纯形表如下。3200M022【1】100-M12340-113+3M2+4M0M0222【1】100-M4-50-4-11-1-5M0-2-4M-M0所有检验数，满足最优性条件，但人工变量未出基。故该问题无可行解。3、P55,1.7(b)解：将模型化为标准形式 列单纯形表格求解如下：23100MMM81【4】2-1010M63200-1012-4M3-6M1-2MMM00321/411/2-1

5、/401/40M2【5/2】0-11/2-1-1/215/4-5M/20-1/2+M3/4-M/2M-3/4+3M/2039/5013/5-3/101/103/10-1/1024/510-2/51/5-2/5-1/52/50001/21/2M-1/2M-1/2所有检验数均为非负，故已达最优解，最优解为最优目标值为。 有无穷多最优解。 4、P55,1.7(a)解：将模型化为标准形式 列单纯形表格求解如下：2-12000-M-M-M-M6111-100100-M2-2010-10010-M00【2】-100-10012-M-1+3M2+M-M-M-M000-M6103/2-101/210-1/2-

6、M2-20【1】0-10010-1001-1/200-1/2001/22-M0-M-M00-M3【4】00-13/21/21-3/2-1/222-2010-10010-11-1100-1/2-1/201/21/24M+500-M02100-1/43/81/81/4-3/8-1/82001-1/2-1/41/41/21/4-1/4-1010-1/4-1/8-3/81/41/83/80005/4-1/8-7/8-M-M-M-检验数为正，但其对应系数列全部为负，故该问题为无界解的情况。 5、 解：化标准型 用单纯形法迭代12-100-M-M041111000-M1-2【1】-10-110-M9031

7、0001-2M-34M10-M000330211-1001-21-10-110-M6【6】0403-316M-304M+103M-4M0000001-1/21/2-1/203011/30001/3-3110【2/3】01/2-1/21/600303/2-M-3/2-M+1/2000001-1/21/2-1/205/2-1/2100-1/41/41/413/23/20103/4-3/41/4-9/2000-3/4-M+3/4-M-1/4所以最优解为最优值为。 6、 解：将模型化为标准型： 用单纯形法迭代5130-M0-M101【4】2-1100161-210015+M1+4M3+2M-M0015

8、/2【1/4】11/2-1/41/400213/202-1/21/2119/405/21/4-M-1/40510142-110060-6-1【1】-110-19-75-M-505161-21001060-6-11-11011-20-M-5因为的检验数为，但系数列，故该问题为无界解。三、建立下列问题的数学模型1、P57. 1.14 某厂在今后4个月内需租用仓库堆放物资。已知各月所需仓库面积列于表1-1，仓库租借费用随合同期定，期限越长折扣越大，具体数字见表1-2.租借仓库的合同每月初都可以办理，每份合同具体规定租用面积和期限。因此该厂可根据需要在任何一个月初办理租借合同，每次办理时可签一份，也可

9、签若干份租用面积和租借期限不同的合同，总目标是使得所附租借费用最小。试建立该问题的数学模型。 表1-1月份1234所需仓库面积（100m2）15102012 表1-2合同租借期限1个月2个月3个月4个月合同期内的租费（元/100m2）2800450060007300解：表示第i个月签订的期限为j个月合同中所规定的仓库面积（i=1,2,3,4;j=1,2,3,4）则模型为：s.t 2、P57. 1.16 某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在上完成，都可用于完成B工序。已知产品可在A、B任何一种设备上加工；产品的A工序可在相应任何设备上完成，但B工序只能在上完成；产品只

10、能在上加工。加工单位产品所需工序时间及其他各项数据见下表。请安排最优生产计划，使该厂获利最大。设备产品设备有效台时（h）设备加工费（元/h）51060000.05007912100000.03216840000.062541170000.1119740000.0500原料费（元/件）0.250.350.50售价（元/件）10252.002.80解：设在上加工的产品的数量是。在上加工的产品的数量是。则模型如下：s.t ； ； ； ；3、P59. 1.21北海银行某分理处每天各时段对职员的需求如下表所示：时段9101011111212131314141515161617所需人数45665688该分

11、理处分别聘用部分全日制和非全日制职员。全日制职员每天从9:00工作到17:00，中间安排一小时午休（分两批，一批12:0013:00，另一批13:0014:00）每天薪金240元。非全日制职员分六批次上班，时间分别是9:0012:00,10：0013:00,11:0014:00,12:0015:00,13:0016:00，14:0017:00，每人每天薪金80元。问：该分理处应聘用全日制和各批次的非全日制职员各多少人，能满足需求，又使得薪金支出为最少？解：设全日制职员在12:0013:00午休的为 人，13:0014:00午休的为 人。非全日制职员各批次分别为人。则建立模型如下：4、P59.

12、1.22 工业原材料的合理利用要制作100套钢筋架子，每套需要2.9米，2.1米和1.5米的钢筋各一根。已知原材料钢筋每根长7.4米。应如何下料切割，使原材料最省。试建立该问题的数学模型。解：采用套裁的方式，每根7.4米的原料可按如下几种方法切割，得到所需长度的钢筋。方案1方案2方案3方案4方案5方案62.9米1112002.1米1200121.5米103132剩余料头0.9m0.300.10.80.2只考虑这几种料头较少的方案。设按照各方案瞎聊的原材料根数分别为。建立模型如下：5、P60. 1.23某鞋厂推出一款新型运动鞋。根据经验和调查，预测下一年度上半年对该款运动鞋的需求如下：1月-3000双；2月-3600双；3月-4000双；5月-48000双；6月-5000双。生产每双鞋需耗用熟练工人4h和150原材料费，每双售价240元。该厂1月初有熟练工80人，每人每月工作160小时。为适应生产需要，该厂可招收新工人培训，但培训1名新工人需占用熟练工人40小时用于指导操作，新工人培训期为1个月，培训结束即可上岗。熟练工人每月工资2000元。新工人培训期间当月发生活费800元，上岗后工资