运筹学数学模型

1、 第二章第二章 线性规划线性规划 运筹学中应用最广泛的方法之一运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划规划，目标规划和多目标规划都是以线性规划为基础的为基础的 解决稀缺资源最优分配的有效方法，使付出的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大费用最小或获得的收益最大1947 库伯曼斯库伯曼斯 提出运输问题提出运输问题 DANTZIG 提出提出 “单纯形法单纯形法”1939 康脱洛维奇康脱洛维奇 “生产组织与计划中的生产组织与计划中的 数数学方法学方法” 研究对象研

2、究对象 有一定的人力、财力、资源条件下，如何合理有一定的人力、财力、资源条件下，如何合理安排使用，效益最高安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之某项任务确定后，如何安排人、财、物，使之最省最省 寻求某个整体目标最优寻求某个整体目标最优2.1 线性规划的数学模型线性规划的数学模型 甲甲 乙乙 备用资源备用资源 A 1 1 45 B 2 1 80 C 1 3 90 收益收益 4 5例例1、生产计划问题、生产计划问题甲、乙各生产多少甲、乙各生产多少, 可获最大利润可获最大利润? max Z= 4x1 +5x2解解:设产品甲、乙产量分别为变量设产品甲、乙产量分别为变量x1 ， x

3、2x1 + x2 452x1 + x2 80 x1 +3x2 90 x1，x2 0例例3、运输问题、运输问题例例2、运输问题、运输问题仓库仓库/工地工地 1 2 3 库存库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求需求 40 15 35设设xij为为i 仓库运到仓库运到 j工地的材料数量工地的材料数量(i 1，2，3， j 1，2，3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11 +x21+x31

4、= 40 x12 +x22+x32 = 15x13 +x23+x33 = 35 xij 0例例3 3、配料问题、配料问题 某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同混合调配出三种不同规格的产品甲、乙、丙，数据如表。规格的产品甲、乙、丙，数据如表。 问：该厂应如何安排生产，使利润收入为最大？问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料 1 不少于 50%，原材料 2 不超过 25%50乙原材料 1 不少于 25%，原材料 2 不超过 50%35丙不限25原材料名称每天最多供应量单价（元/kg）1100652100253603

5、5 解：设解：设 xij 表示表示第第 i 种（甲、乙、丙）产品中原料种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：的含量。这样我们建立数学模型时，要考虑： 对于甲：对于甲： x11，x12，x13； 对于乙：对于乙： x21，x22，x23； 对于丙：对于丙： x31，x32，x33； 对于原料对于原料1 1： x11，x21，x31； 对于原料对于原料2 2： x12，x22，x32； 对于原料对于原料3 3： x13，x23，x33； 目标函数：目标函数： 利润最大，利润利润最大，利润 = = 收入收入 - - 原料支出原料支出 约束条件：约束条件： 规格要求规

6、格要求 4 4 个；个； 供应量限制供应量限制 3 3 个。个。目标函数目标函数：Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 约束条件：约束条件： s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料（原材料1不少于不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料（原材料2不超过不超过25%） 0.75x21-0.25x22 -0.25x23 0 （原材料（原材料1不少于不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （原材料（原材料2不超过不超过50%

7、） x11+ x21 + x31 100 (供应量限制）供应量限制） x12+ x22 + x32 100 (供应量限制）供应量限制） x13+ x23 + x33 60 (供应量限制）供应量限制） xij 0 , i = 1,2,3; j = 1,2,3 2.9m钢筋架子钢筋架子 2.1m 各各100根，原料长根，原料长7.4m 1.5m 2.9m 1 2 0 1 0 2.9m 1 2 0 1 0 2.1m 0 0 2 2 1 2.1m 0 0 2 2 1 1.5m 3 1 2 0 3 1.5m 3 1 2 0 3 合计合计 7.4 7.3 7.2 7.1 6.67.4 7.3 7.2 7.

8、1 6.6 料头料头 0 0.1 0.2 0.3 0.80 0.1 0.2 0.3 0.8例例4、合理下料问题、合理下料问题解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根minZ= 0.1x2 + 0.2x3+0.3x4+0.8x5 x1 + 2x2 + x4 = =100 2x3 +2x4+ x5= =100 3x1+ x2+2x3 +3x5= =100 xi 0 (i =1,5)，且为整数且为整数以上例题共同特点以上例题共同特点目标明确：要解决的问题的目标可以用数值目标明确：要解决的问题的目标可以用数值 指标反映。指标反映。Z=(x1 xn) 线性式，求线性式，求Z

9、极大或极大或极小极小多种方案：对于要实现的目标有多种方案可多种方案：对于要实现的目标有多种方案可 选择选择资源有限：有影响决策的若干约束条件资源有限：有影响决策的若干约束条件线性关系：约束条件及目标函数均保持线性线性关系：约束条件及目标函数均保持线性关系关系 决策变量：向量决策变量：向量(x1 xn)T 决策人要考决策人要考虑和控制的因素非负虑和控制的因素非负 约束条件：线性等式或不等式约束条件：线性等式或不等式 目标函数：目标函数：Z=(x1 xn) 线性式，求线性式，求Z极极大或极小大或极小线性规划模型特征线性规划模型特征一般式一般式0,),(),(),()(212211222221211

10、12121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZMaxMinaij 结构系数或消耗系数结构系数或消耗系数bi 限定系数或常数项限定系数或常数项cj 利润系数或成本系数利润系数或成本系数 比例性：决策变量变化引起目标的改变量与决比例性：决策变量变化引起目标的改变量与决策变量改变量成正比策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独可加性：每个决策变量对目标和约束的影响独立于其它变量立于其它变量 连续性：每个决策变量取连续值连续性：每个决策变量取连续值 确定性：线性规划中的参数确定性：线性规划中的参数aij , bi ,

11、cj为确定值为确定值 隐含的假设隐含的假设应应 用用 市场营销市场营销(广告预算和媒介选择，竞争性定价，新产广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划品开发，制定销售计划) 生产计划制定生产计划制定(合理下料，配料，合理下料，配料，“生产计划、库存、生产计划、库存、劳力综合劳力综合”) 库存管理库存管理(合理物资库存量，停车场大小，设备容量合理物资库存量，停车场大小，设备容量) 运输问题运输问题 财政、会计财政、会计(预算，贷款，成本分析，投资，证券管预算，贷款，成本分析，投资，证券管理理) 人事人事(人员分配，人才评价，工资和奖金的确定人员分配，人才评价，工资和奖金的确定) 设

12、备管理设备管理(维修计划，设备更新维修计划，设备更新) 城市管理城市管理(供水，污水管理，服务系统设计、运用供水，污水管理，服务系统设计、运用)例题：例题：某装修公司在下一年度的某装修公司在下一年度的1 14 4月份的月份的4 4个月内拟租用仓库堆放个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表物资。已知各月份所需仓库面积列于下表2-12-1。仓库租借费。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表用随合同期而定，期限越长，折扣越大，具体数字见表2-22-2。租借仓库的合同每月初都可办理，每份合同具体规定租用面租借仓库的合同每月初都可办理，每份合同具体规定租用面 积和期

13、限。因此该公司可根据需要，在任何一个月初办理租借积和期限。因此该公司可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决租用期限不同的合同。试确定该公司签订租借合同的最优决 策，目的是使所租借费用最少。策，目的是使所租借费用最少。月份月份 1 2 3 4所需仓库面积所需仓库面积15 10 20 12表表2-1表表2-2合同租借期限合同租借期限 1 1个月个月 2 2个月个月 3 3个月个月 4 4个月个月合同期内的租费合同期内的租费2800 4500 600

14、0 7300单位：单位：100m2单位；元单位；元/100m2解：设解：设 表示公司在第表示公司在第i (i=1,2,3,4)月初签订的租期为月初签订的租期为j (j=1,2,3,4)个月的个月的仓库面积仓库面积的合同（单位为的合同（单位为100m2) )。 ijx11x12x13x14x21x22x23x31x32x41x15151010202012121514131211xxxx10232221141312xxxxxx1241322314xxxx20323123221413xxxxxx2800Z)(41312111xxxx4500)(322212xxx6000)(2313xx 147300

15、 x)4 , 1; 4 , 1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij)(4500)(2800min32221241312111xxxxxxxZ1423137300)(6000 xxx目标函数目标函数约束条件约束条件习题：习题：1 1、某商场是个中型百货商场，它对售货员的需求情况经、某商场是个中型百货商场，它对售货员的需求情况经过统计分析如下表所示。为了保证售货人员充分休息，过统计分析如下表所示。为了保证售货人员充分休息，售货员每周工作售货员每周工作5 5天，休息两天，并要求休息的两天是连天，休息两天，并要求休息的两天是连续的。问应如何安排售货人员的作息，即能满足工作的续的。问应如何安排售货人员的作息，即能满足工作的需要，又使配备的售货人员的人数最少？需要，又使配备的售货人员的人数最少？时间时间所需售货员人数所需售货员人数时间时间所需售货员人数所需售货员人数星期一星期一1515星期五星期五3131星期二星期二2424星期六星期六2828星期三星期三2525星期日星期日2828星期四星期四1919习题：习题：2 2、某班有男生