资源描述
目 录目 录第一章 线性规划基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 第二章 深入线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8第三章 线性规划的对偶理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 第四章 整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23第五章 运输问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 第七章 图论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56第八章 动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 习 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63I第一章 线性规划基础第一章 线性规划基础习题一、应用问题的建模1、某养鸡场饲养肉鸡出售，设每只鸡每天至少需100克蛋白质、12克矿物质、60毫克维生素。现有五种饲料可供选用，各种饲料每千克营养成分含量及单价如表1-10所示：表 1-10 饲料成分和成本表饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/千克）13160.5220.3100.8320.480.6452715160.831.5问：如何在满足肉鸡营养需求的前提下，最经济地搭配饲料？建立本问题的建立线性规划模型。答案：解：定义第种饲料的购买量为( = 1, , 5)，则本问题的线性规划模型为：min= 0.5 1 + 0.8 2 + 0.6 3 + 4 + 1.5 5s.t.3 1 + 2 2 + 2 3 + 5 4 + 16 5100必须为，下同。1 + 0.3 2 + 0.4 3 + 2 4 + 0.8 5126 1 + 10 2 + 8 3 + 7 4 + 3 560 0( = 1, , 5)必须有变量的非负约束2、某工厂利用两条生产线 1和 2生产两种产品 1和 2。这两种产品分别由其核心部件和普通易耗品部件组装而成，其销售价格为部件价格之和的110%（单位：元）。表1-11给出了各生产线生产各部件所需单位工时，以及各生产线的每月可使用的总工时（单位：小时）。表 1-11 单位产品生产的工时和售价表单位产品工时产品 1产品 2可用工时核心部件A普通部件B核心部件C普通部件D生产线10.030.020.050.0140生产线20.040.020.050.0245单位售价250150400100配合产品的售后服务政策，每生产1件产品 1和 2需额外生产2件普通部件作为备件单独销售。问：该工厂应如何安排生产可实现月销售额最大？建立本问题的线性规划模型。答案：1第一章 线性规划基础解：根据下表定义由各生产线所生产各种部件的数量：答案表 1-1 变量定义产量产品 1产品 2核心部件A普通部件B核心部件C普通部件D生产线11111生产线22222本问题完整模型为：max= 740( 1 + 2 ) + 750( 1 + 2 )s.t.3( 1 + 2 ) ( 1 + 2 ) = 03( 1 + 2 ) ( 1 + 2 ) = 00.03 1 + 0.02 1 + 0.05 1 + 0.01 1 6 400.04 2 + 0.02 2 + 0.05 2 + 0.02 2 6 45 0, = 1, 2; = , , ,必须有变量的非负约束3、某公司在两个工厂生产产品满足顾客需求。现已知下个月三个地区的需求情况，问如何安排供货，从而使得公司的总运输成本最低？表1-12给出了这两个工厂的生产能力，以及工厂到三个地区送货的单位物流成本（单位：元/件）。表 1-12 运费表单位运费销地地区1地区2地区3生产能力产地工厂1700750650400工厂2850550450600需求量350250400试建立本问题的线性规划模型。答案：解：定义 为工厂向地区送货的数量。则本问题的模型为：min= 700 11 + 750 12 + 650 13+ 850 21 + 550 22 + 450 23s.t.11 + 12 + 13 6 40021 + 22 + 23 6 60011 + 21 = 35011 + 22 = 25013 + 23 = 400 0,= 1, 2;= 1, 2, 34、某公司提供4种不同型号的彩色涂料产品 1、 2、 3和 4，各型号产品的市场售价如表1-13所示。这些彩色涂料由3种原料（原色涂料 1、 2和 3）根据不同的配方物理混合而成以上两式符号可以为等号，对于供需不平衡的问题，则必须为6也可以为，以下两式同必须有变量的非负约束2第一章 线性规划基础（成品重量为原料重量之和），各原料在成品中的配方比例如表1-13所示，采购售价如表1-14所示。表 1-13 不同型号成品的配方和销售价格成品型号 配方比例要求 销售价格（元/公斤）1不少于40%12不多于20%1203不多于5%1不多于10%22不多于30%903不少于50%31不多于10%702不少于60%1不多于30%42不多于40%503不多于40%答案：表 1-14 3种原料的市场售价原料 1 2 3价格503040假设4种产品均供不应求，且本月的采购预算为10 000元，问：该公司本月应如何采购并如何生产，可获得最多利润？试建立本问题的线性规划模型。解：定义 ( = 1, 2, 3, 4; = 1, 2, 3)为成品 中原料 的数量。则本问题的线性规划模型为：max= 120( 11 + 12 + 13) + 90( 21 + 22 + 23)+ 70( 31 + 32 + 33) + 50( 41 + 42 + 43) 50( 11 + 21 + 31 + 41) 30( 12 + 22 + 32+ 42) 40( 13 + 23 + 33 + 43)s.t.11 0.4( 11 + 12 + 13)12 6 0.2( 11 + 12 + 13)13 6 0.05( 11 + 12 + 13)21 6 0.1( 21 + 22 + 23)22 6 0.3( 21 + 22 + 23)23 0.5( 21 + 22 + 23)31 6 0.1( 31 + 32 + 33)32 0.6( 31 + 32 + 33)41 6 0.3( 41 + 42 + 43)42 6 0.4( 41 + 42 + 43)43 6 0.4( 41 + 42 + 43)4 3 6 10000=1 =1 0,= 1, 2, 3, 4;= 1, 2, 35、某公司将产品从三个工厂( 1、 2和 3 )运往四个城市 ( 6、 7、 8 和 9 ) ，图1-1给出了各可行路线的单位运输成本（单位：千元/公斤），其中 4和 5为分销中心，图两侧的数字表示第种原料的市场价格必须有变量的非负约束3第一章 线性规划基础分别表示各工厂的供应量和各个城市的需求量（单位：公斤）。3.5A6200250A1223A45A7150366300A2444A53A83506450A335A9300图 1-1 物流网络数据图问：如何安排运输可使总运费最少？试建立本问题的线性规划模型。答案：解： 定义从 到 的运输量为 ，其中 到 有运输路线， = 1, 2, , 5, = 4, 5, , 9。则本问题的本问题的线性规划模型为：min= 3.5 16 + 2 14 + 3 15 + 6 24 + 4 25 + 4 34 + 3 35+ 2 46 + 5 47 + 3 48 + 6 49 + 4 56 + 3 57 + 6 58 + 5 59s.t.16 + 14+ 15 = 25024+ 25 = 30034+ 35 = 45014 + 24 + 34 = 46 + 47 + 48 + 4915 + 25 + 35 = 56 + 57 + 58 + 59以上两个约束条件容46+ 56= 200易漏掉47+ 57= 15048+ 58= 35049+ 59= 300 0, = 1, , 5, = 1, , 96、SH地产集团有闲置资金20亿元，拟在未来5年进行对外投资。为了保证资金安全，财务部门提出了以下4个可选的投资方向：投资方向1：企业借贷投资每年年初可投资，当年年末收回本利107%；投资方向2：国内基金投资每年年初可投资，次年年末收回本利118%；投资方向3：土地买卖每年年初可投资，回收周期为3年，回收本利130%；投资方向4：股权投资只能在第3年年初投资，最大投资不能超过10亿元，第5年年末收回本利155%。假定不存在投资风险且忽略利率波动因素，问：该集团应如何安排投资计划，使得第5年年末时拥有的本利总额最大？建立本问题的线性规划模型。答案：定义 ( = 1, , 5; = 1, , 4)为第年年初用于第个投资方向的投资额。根据问题描述，可以得到每年年初的投资额，以及年底的收益如下表所示：4第一章 线性规划基础答案表 1-2年份年初投资总额年末收回本利总额111 + 12+ 131.07 11221+ 22+ 231.07 21 + 1.18 12331+ 32+ 33 + 341.07 31+ 1.18 22+ 1.30 13441+ 42+ 431.07 41+ 1.18 32+ 1.30 23551+ 52+ 531.07 51+ 1.18 42+ 1.30 33 + 1.55 34本问题的线性规划模型为：max= 1.07 51 + 1.18 42 + 1.30 33 + 1.55 34s.t.11 + 12+ 13 620符号可以为等号，下21 + 22+ 23 6 1.07 11同31 + 32+ 33+ 34 6 1.07 21+ 1.18 1241+ 42+ 43 6 1.07 31+ 1.18 22 + 1.30 1351+ 52+ 53 6 1.07 41+ 1.18 32 + 1.30 2334 6 10 0( = 1, , 5; = 1, , 4)必须有变量的非负约束7、某手工作坊生产的竹制座椅中需要用到3种规格楠竹片，每张椅子需要长度为60cm、40cm和 30cm 的楠竹片 2、 6和2 片。可以在市场上采购这些规格的现货，也可以将作坊仓库中长度为110cm的楠竹片切割成所需的规格，但每切割1次会发生1cm的长度损耗。问：如果要制作100张竹制座椅，该作坊的仓库中至少要有多少条长度为110cm的楠竹片，才不用去市场上采购？试建立本问题的线性规划模型。答案：解：将110cm长的竹片切割为60cm、40cm和30cm共有5种方式，见下表：答案表 1-3 5种切割方式得到片数 规格60cm40cm30cm切割方式11102101301240205003定义为采取第种方式切割的110cm楠竹片的数量，则本问题的线性规划模型为：min=1 + 2 + 3 + 4 + 5s.t. 1+ 2200符号必须为1+ 3 + 2 4 6002+ 2 3+ 3 5 200 0,= 1, , 5必须有变量的非负约束5第一章 线性规划基础8、JM公司是一家基于互联网的化妆品销售公司，该公司每个月需租用仓库存放货物。已知其未来4个月的仓储面积需求如表1-15所示，租金按单位面积的租用时间计算，租金价格见表1-16。表 1-15 仓储面积需求月份 面积（单位：平方米）1 40,0002 30,0003 20,000450,000表 1-16 不同租期的仓库租金租用时长（月） 每平方米月租金（元）160210031354170现JM公司需要与出租方签订未来4个月的租用合同，该合同可细化到各月不同租期租用不同仓储面积，例如：在2月份，租10,000平方米租期1个月，20,000平方米的3个月。问：JM公司应如何制订租用计划，可使租金支出最少？建立本问题的线性规划模型 (提示：设 为第个月初租用租期为个月的仓储面积( = 1, , 4; = 1, , 4)。)答案：定义为第个月初租用租期为个月的仓储面积( = 1, , 4; = 1, , 4).每个月实际可用仓储面积如下表所示：答案表 1-4月份111213142122232431323334414243441234表示仓储面积当月可用本问题的模型为：min= 60 11 + 100 12 + 135 13 + 170 14 + 60 21 + 100 22 + 135 23 + 170 24+ 60 31 + 100 32 + 135 33 + 170 34 + 60 41 + 100 42 + 135 43 + 170 44s.t.11 + 12 + 13+ 14 40000符号必须为 ，下同12+ 13 + 14 + 21 + 22 + 23+ 24 3000013 + 14 + 22+ 23 + 24 + 31 + 32 + 33+ 34 2000014 + 23 + 24 + 32+ 33 + 34 + 41 + 42 + 43+ 44 50000 0( = 1, , 4; = 1, , 4)二、线性规划问题的图解法计算9、应用图解法求解下列线性规划问题：6第一章 线性规划基础(1)max= 2 1 + 2(2)max= 1 3 2s.t.1 + 2 6 4s.t.1 2 1 1 + 2 51 + 2 2 6 41, 2 01, 2 0答案：答案：最优解为(4, 0)，最优值为4。图略。无可行域，所以问题无可行解。图略。(3)max= 2 1 + 2(4)min= 2 1 4 2s.t.2 6 10s.t. 1 + 2 2 6 152 1 + 5 2 6 301 + 2 6 121 + 2 6 205 1 + 3 2 6 453 1 + 2 6 361, 2 01, 2 0答案：答案：最优解为(3, 9)，最优值为42。图略。最优解为( 15013 , 1813 )，最优值为31813 。图略。7第二章 深入线性规划第二章 深入线性规划习题一、标准单纯形法的计算1、将下列线性规划问题变换为标准形式。答案：(1) min= 3 1 + 4 2 2 3 + 5 4s.t. 4 12+2 34= 2max= 3 1 4 2 2 3 5 4 + 5 4+3614s.t.4 1+2+ 2 3+ 4 4= 212341 + 2 3 3 4 + 4 + 5= 142 1 + 3 2 3 + 2 4 22 1 + 3 2 + 3+ 2 4 2 4 6 = 21, 2 0, 3 6 0, 4无限制1, 2, 3, 4, 4, 5, 6 0答案：(2) max= 2 1 + 3 2s.t.1+ 26 3max= 2 1+ 3 2 3 22 1 2 2s.t.1+ 2 2 + 3= 31 0, 2无限制2 1 2+ 2 4 = 21, 2, 2, 3, 4 02、请穷举出下列线性规划问题的所有基本解，指出其中的基本可行解和最优解。(1) max= 1 + 2s.t. 2 1 + 3 2 6 6 2 1 + 2 6 41, 2 0答案：引入松弛变量 3, 4将模型变换为标准形式：max= 1 + 2s.t.2 1 + 3 2 + 3= 62 1 + 2+ 4 = 41, 2, 3, 4 0约束条件数量为2，所以基本解中基变量个数为2。答案表 2-1序基变量组合基本解可行解目标函数值( 1, 2)最优解13是53是( 1, 2)(, 1, 0, 0)(, 1)2222( 1, 3)(2, 0, 2, 0)是2(2, 0)3( 1, 4)(3, 0, 0, 2)否4( 2, 3)(0, 4, 6, 0)否5( 2, 4)(0, 2, 0, 2)是2(0, 2)6( 3, 4)(0, 0, 6, 4)是0(0, 0)8第二章 深入线性规划(2) min= 3 1 2 + 2 3 4 4 s.t. 2 1 + 3 2 + 3 + 2 4 = 121 + 2 3 + 2 4 = 81, 2, 3, 4 0答案：将模型标准化为：max= 3 1 + 2 2 3 + 4 4s.t.2 1 + 3 2 + 3 + 2 4 = 121 +2 3 + 2 4 = 81, 2, 3, 4 0约束条件数量为2，所以基本解中基变量个数为2。答案表 2-2序基变量组合基本解可行解目标函数值( 1, 2, 3, 4)最优解这里要么写成 ，1( 1, 2)(12, 4, 0, 0)否要么写成 ，不能写2204否成( 1, 3)(, 0, , 0)333( 1, 4)(4, 0, 0, 2)是4(4, 0, 0, 2)4( 2, 3)(0, 5, 3, 0)否5( 2, 4)(0, 2, 0, 3)是14(0, 2, 0, 3)6( 3, 4)(0, 0, 2, 5)是16(0, 0, 2, 5)是注：由于还不涉及单纯形法求解，本题的目标函数也可以不用化为max ，而是直接计算。3、应用单纯形表法求解下列线性规划问题。(1) max= 1 + 5 2 + 2 3 s.t. 1 + 2 3 6 16 1 + 2 2 + 3 6 32 2 1 + 3 2 + 2 3 6 601, 2, 3 0答案：答案表 2-3152000bCBXB12345652010110163371123001312124111001513121240005231=83121249第二章 深入线性规划本例在一开始求解即出现退化（答案中不需明确），本问题有唯一最优解：X * = ( *1, *2, *3, *4, *5, *6) = (3, 16, 3, 0, 0, 0) ,* = 83.(2) min= 3 1 3 2 3s.t.1 + 26 12 1 + 2 + 3 3 6 143 1 + 2 +3 6 161, 2, 3 0答案：标准化后用单纯形表求解结果如下：答案表 2-4331000bCBXB1234565134332010488413001111324421135311004884000511=3712442本问题有唯一最优解：X * = ( 1*, 2*, 3*, 4*, 5*, 6*)5433, 0, 0, 0) , *= 371= (,.4422(3) max= 4 1 + 5 2 + 4 3s.t.1 + 2 + 3 6 81 + 3 2 + 3 6 213 1 + 2 2 + 3 6 151, 2, 3 0答案：下表为目标函数转化为max=3 1 + 3 2 +3的单纯形表，如直接以min求解，检验数为相反数。注意：如果转换了目 标函数，在最后应转换为 。标准化后用单纯形表求解结果如下：答案表 2-5454000bCBXB123456711543001442452010110132221111411004424000710=381有0检验数22210第二章 深入线性规划本问题有无穷多最优解，其中一个最优解为：必须明确X* = ( *, *, *, *, *, *)= (1,13,5, 0, 0, 0) , *= 381.1234564242(4) min= 1 + 2 2 + 3s.t. 1 + 2121 3 641, 2, 3 0答案：在第1、2个约束条件中分别引入剩余变量 4和松弛变量 5：min= 1 + 2 2 + 3s.t.1 + 2 4= 121 3+ 5 = 41, 2, 3, 4, 5 0可直接以 2, 5为基变量建立初始单纯形表直接求解。答案表 2-612100bCBXB123452211010120510101410120=24220111 181110101400021=20本问题有无穷多最优解，其中一个最优解为：X * = ( *1, *2, *3, *4, *5) = (4, 8, 0, 0, 0) ,* = 20.4、分别应用大M法和两阶段法求解下列线性规划问题。(1) max= 1 + 2 2 + 3 3s.t. 2 1 + 3 2 + 5 3 10 2 1 + 5 2 + 7 3 = 151, 2, 3 0注：下表为最小值直接求解的单纯形表，如以最大值为目标函数，检验数取相反数 有0检验数 必须明确答案：大M法： 标准化后在第1、2个约束条件中分别引入人工变量 5和 6，将问题的目标函数改写为max = 1 + 2 2 + 3 3 5 6注意人工问题是否写单纯形表求解结果如下：对，特别是 的符号11第二章 深入线性规划答案表 2-71230bCBXB123456111570011522220402211150 110 1=152222本问题有唯一最优解：X* = ( *, *, *, *, *, *)= (15, 0, 0, 5, 0, 0) , * =15.12345622两阶段法： 第一阶段：构造辅助问题min = 5 + 6，单纯形表求解结果如下：注意辅助问题是否写答案表 2-8对，特别是目标函数应求min而不是max000011bCBXB123456032510011577770444011557777000011=0最优表中= 0，亦即人工变量全部为0（非基变量），可进入第二阶段。第二阶段：去掉第一阶段最优表中的人工变量，将原始问题的目标函数系数代回，单纯形表求解结果如下：注意2：求解过程中答案表 2-9右端常数不得出现负数1230bCBXB1234
展开阅读全文