数学规划模型的建立.pptx

《数学规划模型的建立.pptx》由会员分享，可在线阅读，更多相关《数学规划模型的建立.pptx（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例2施工点 j 的坐标为对某材料的需求量为第 i个料场的容量为求料场的位置及各料场向各施工点的供应量，使材料运输的总吨公里最小。解 设各料场到各施工点的距离为直线距离，且各施工点可在不同料场取料。则总吨公里数需求限制容量限制非负限制mins.t.第1页/共79页学习这一部分需注意的地方：1.对给定的实际问题，如何作合理的假设，并建立 模型。如何处理分段函数、矛盾约束等问题。2.怎样将一类模型化为另一类模型，易于求解。3.同一问题可建立不同模型第二个问题不便用微分法求解，可用数学规划方法求解。第2页/共79页II II 数学规划模型的建立数学规划模型的建立数学规划模型的一般形式：例如：maxs.

2、t.若能写出描述S的数学式子，则可直接写出。这里第3页/共79页目标函数可行域可行解决策变量描述S 的数学式子约束条件S问题可行问题不可行最优解最优目标值几个概念：第4页/共79页特别：(或 max)或线性规划模型或等约束第5页/共79页注：M是常数与有相同的最优解1.2.与有相同的最优解第6页/共79页另外：1.取整数，称模型为整数规划模型2.中部分取整数，称模型为混合整数规划模型3.只取0或1两个值，称为 0 1 规划模型4.目标函数或约束条件是非线性的，称为非线性规划模型5.若目标函数只有一个，称为单目标规划模型；若目标函数不只一个，称为多目标规划模型。第7页/共79页产地销地运价例1求

3、使总运费最少的调运方案。试建模。产量需求量42一、运输问题第8页/共79页解则产销平衡注：若产大于销，则若产小于销，则线性规划模型第9页/共79页 重要结论：当供应量 与需求量 均为整数时，模型的最优解 是整数解。第10页/共79页例2 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C由三个水库供应。四个区每天必须的基本生活用水分别为30、70、10、10千吨，但三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中C水库与丁区间无输水管道），其它管理费均为450元/千吨。各区用户每千吨收费90

4、0元。此外，各区用户都向公司申请了额外用水量，分别为每天50、70、20、40千吨。问公司应如何分配供水量，才能获利最多？第11页/共79页引水管理费(元/千吨)第12页/共79页将有关数据整理列表：水库居民区供应量生活用水额外用水成水输本问题分析：可看成是“产小于销”的运输问题。解第13页/共79页设 xij 分别表示水库A,B,C(i=1,2,3)向居民区甲,乙,丙,丁(j=1,2,3,4)的供水量。其中X34=0.模型建立由题意目标函数为：可转化为：供给限制需求限制一般问题中：供给限制用“”需求限制用“”“”引水管理费因160千吨水须全部输出第14页/共79页注：为了增加供水，公司考虑改

5、造水库，使三个水库的供水能力提高一倍，问模型将作何改动？分析：由于总供水能力为320千吨，总需求量为300千吨，水不能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。每千吨净利润用户交的900元其它管理费450元引水管理费净利润(元/千吨)第15页/共79页模型改为：其它同前第16页/共79页例3 最大流问题 图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求到每小时的最大车流量。二、网络（规划）问题第17页/共79页设 v 为从 出发的车流量，为 到 的车流量，则流量守恒条件弧容量限制去掉去掉若不设v,则模型有四处需修改第18页/共79页如果源、汇不止一个时，建模

6、方法类似。可增加一个虚拟源、虚拟汇化成单源单汇的问题。图中的结点 称为源（发点），结点 称为汇（收点）。图是单源单汇的情形。第19页/共79页例42求从 流出，到 的最大流量。解 设 为 到 的流量，、为流入 、的量，、为流入 、的量。第20页/共79页例5 设有工作 件，人员 个，且一人做一件工作，第 人作第 件工作的时间（或费用）为 ，问：如何分派可使总时间（或总费用）最少。解 本题需确定：第 人做或不做第 件工作，这是定性变量，首先将其定量化。设01规划模型则注：若 表示效益，则目标函数应极大化问：各人员类不止1人，各工作类不止1件工作，决策变量为何？若人数“”工作件数 三、分派问题第2

7、1页/共79页四、生产活动问题(分段函数、矛盾约束等的处理方法)资源产品单耗资源量单位利润例6问如何安排生产使总利润最大。解 设 表示第 种产品的产量，则资源分配问题第22页/共79页分段函数问题例中 单位收益单位成本（可变成本）若还要考虑固定成本则第j 种产品的利润为：于是引入 01变量：设 Lj 是xj的上界，则模型改写为：第23页/共79页混合整数规划模型等价性：（1）由Z的极大化（2）由注：将目标函数变成则为非线性的。若不考虑固定成本，则不引入0-1变量。第24页/共79页 更复杂的分段函数的处理方法*设B1是某种原料（单位：吨），还可以从市场上购买到不超过1500吨的原料。若购买量不

8、超过500吨，其价格为10千元/吨；购买量多于500吨但不超过1000吨时，超过500吨的部分8千元/吨；购买量超过1000吨时，超过1000吨的部分6千元/吨。问怎样安排生产和采购？增设x为采购量，则可得采购支出（千元）：第25页/共79页这时，目标函数为:处理法1：设三种价格的采购量分别为：则目标函数为：约束条件增加：只有当 x1=500时，才能以每吨8千元的价格购买x2(0)非线性规划模型！第26页/共79页处理法1：可用端点的凸组合来表示线段上的值，如：为了统一表示，引入01变量第27页/共79页则且至多两个相邻的 i取非零值可得混合整数规划模型第28页/共79页产品种类限制问题（不考

9、虑固定成本）n种产品中只生产其中k种设则要求产量不小于80单位80第29页/共79页矛盾约束问题设 、为机器1、2的可用工时（资源），种产品只在一台机器上加工，则以下两个约束条件是矛盾的，不能同时出现在一个模型中。若引入 01变量：设 M 是充分大的常数，则两个矛盾约束可统一在一个模型中：第30页/共79页一般，若m 种资源中只用其中k 种资源，则令约束条件改为：第31页/共79页例7 生产存储问题（多阶段问题）某公司生产一种产品，最大生产能力为100单位，第 月的单位存储费为 元，预定的销售量和单位成本如表。求使生产成本与存储费之和最低的生产计划。解先作合理假设 1月初无库存；4月底卖完；当

10、月生产的不入库；库存量无限制。假设：月份单位成本(元)销售量(件)第32页/共79页模型一且为整数，第 j+1月初的库存量整数规划模型设 为第 月的产量，为单位存储费，则第33页/共79页模型二若设 为第 月初的库存量，则且为整数，增加了决策变量 ，但模型简洁了。本问题还可建立动态规划模型第34页/共79页几点说明：1.增加投资扩大生产能力若每投资k 元可增加一个单位的生产能力。设 表示第 月的投资，则第 月的产量限制条件变为：第 月前的投资在第 月仍起作用，生产投资问题。第35页/共79页2.均衡生产问题前例中的最优月产量为：月初库存量为：为使生产尽量均衡，可增加相继两个月产量差的限制：同时

11、希望非负变量 、越小越好。则目标函数可提为：其中a 为第 月比第 月增加一个产品要支付的费用，b 为减少一个产品支付的费用，c 为库存费。第36页/共79页根据要求还可提为：或不希望减少不希望增加第37页/共79页例8 （P.7例1.8）求生产、存储、维修计划将有关数据整理列表(同例1.6)：机床单耗产品台数月台时单位利润月台时台数 小时 天数。13444 16 21如一台机床维修一次需160(台时)10(天)16(小时)19第38页/共79页假定：没有轮到维修的和维修后的机床在使用期间能正常工作；维修一台机床是在某月内完成，不会跨入下一月。设 第 月初、第 种产品的库存量，第 月、第 种产品

12、的产量，第 月、第 种机床的维修量。需求限制资源限制维修限制 第 月维修哪几台机床可由人安排，只安排未维修的；第39页/共79页例9 （下料问题）某厂要做100套钢架，每套由长为2.9米，2.1米和1.5米的圆钢各一根组成。已知原料长7.4米。问如何下料使原料最省。试建模。问题分析：“最节省”可以是“所用原料根数最少”，也可以是“余料最少”。基于前者建模。一根原料钢管有不同的切割组合.。找出每一种组合用去多少根原料钢管。所以首先列出所有可能组合即“模式”。第40页/共79页解 将8种下料方案列表:方案根数长度合计 6.0 6.6 7.2 6.3 7.4 6.5 7.1 7.3余料 1.4 0.

13、8 0.2 1.1 0 0.9 0.3 0.1需求量第41页/共79页若希望余料最少，则 余料超过1.5米 约束条件取“100”设需 根原料，第 根下第 种圆钢 根，n是决策变量，而线性规划模型中是定数！该模型不易计算！以下几种作法欠妥：第42页/共79页客户拟定的设施地址（1）离散型选址问题（2）连续型选址问题设施的地址未拟定，可选在所论区域（很大）的任何地方。问题：第 个设施是否需修建？若要修建，应为周围哪些客户服务？选址 分配问题五、选址问题第43页/共79页例10（离散型）施工点 j 对某材料的需求量为第 i个料场的容量为的单位运费(元/吨).求使总费用最少的场址。可基于两种考虑建模：

14、2 施工点 只能在某一料场获取全部所需材料。1 施工点 可在任何料场获取部分材料，以满足需求；建场费为di 元,解 1 假定：任何施工点到任何料场的道路是通的；施工点 可在任何料场获取部分材料，以满足需求；拟定m 个地方建料场，为地址 到施工点 一个大型工程有n个施工点，第44页/共79页则总费用需求限制容量限制非负限制mins.t.混合整数规划模型第45页/共79页2假定：任何施工点到任何料场的道路是通的；施工点 只能在某一料场获取全部所需材料。设则总费用需求限制容量限制mins.t.非负限制01规划模型第46页/共79页由于区域很大，所以施工点到料场间的距离视为直线距离例11（连续型）设工

15、程所涉及的区域很大，第 j 个施工点的坐标为：单位运费为c(元/吨/公里),欲建的m个料场地址未拟定，其余条件与例11相同。求使总费用最少的场址。解 基于第二种考虑建模设料场 的坐标为mins.t.同前例 对 可不作非负限制，称为自由变量非线性规划模型第47页/共79页注：(1)若m个料场都要修建，则不设01变量（3）若区域小，且道路呈网状，则使用矩形距离（2）指标不一定是“费用”，可以是“客户”到“设施”的最大距离最小等。相当于将 取成1。目标函数中的常数项 应去掉。第48页/共79页若希望用户到中心的最大距离越小越好，则也可以是用户到中心的距离之和最小建模。均在第一象限内，例12 设某城市

16、的街道成纵横交叉的网状，今欲建一物资供应中心，供n个用户。问该中心建在什么位置合适。试建模。),(yx处，坐标为处，坐标为供应中心建在街道拐角供应中心建在街道拐角问题！第49页/共79页以下几种作法不妥：用直线距离 没设“中心”建在街道拐角处 将“中心”取在坐标原点，决策变量？设第 个用户的需求量为 ，单位运费为 ，得（总运费）第50页/共79页例13某公司有工厂A1,A2生产某种产品，生产能力分别为Q1,Q2,有四个容量为Mk的仓库Bk(k=1,2,3,4)存放该产品，工厂和仓库均可向n个客户Cj(j=6,7,n+5)供货，客户需求量为qj(j=6,7,n+5).现公司打算：扩建仓库B1,其

17、月费用为e1，库容量增加M；新建仓库B5,月费用为e5，库容量为M5;关闭仓库B2或B3,关闭后可节约费用e2或e3;并要求总的仓库数不得超过4个。已知工厂Ai向仓库或客户供货的运费每单位为cij(i=1,2;j=1,2,3,4,5为向仓库供货的运费，j=6,7,n+5为向客户供货的运费)。第k个仓库向第j个客户供货的单位运费dkj(k=1,2,3,4,5;j=6,7,n+5)。以上费用均由公司负担。问公司该作何选择可使总费用最少。第51页/共79页解为便于理解，先作网络图。工厂仓库客户第52页/共79页可仿运输问题，将有关数据列表。产地销地运价总量设9第53页/共79页 产量限制客户需求限制

18、仓库数量限制第54页/共79页六、曲线拟合问题（去绝对值符号、化极大极小化模型为线性规划模型）已知变量 y（随机变量）随 x（非随机变量）变化。并已知一组样本观测值：求近似表示 y 与 x 之关系的经验方程回归方程。对观测值作散点图，若点子沿一直线变化，则可用直线方程作为经验方程。（回归方程）所给的准则不同，求出的a,b 也不同。第55页/共79页常用方法 最小二乘法：求使最小的a,b.由可解得 a,b。求回归直线这一过程，称为拟合 一条回归直线。于是得到回归方程称函数值：为回归值。所求回归方程能否用于预测和控制，还需作假设检验。类似可拟合回归曲线和回归平面。第56页/共79页例14（1）拟合

19、一条回归直线，使回归值与观测值的绝对偏差之和最小；（2）拟合一条回归直线，使回归值与观测值的最大偏差最小。解 设回归方程为：（1）依题意，求解这是一个无约束的非线性规划模型，不便用微分法处理。已知变量y随变量x变化，并已知一组观察值去掉绝对值符号，化为线性规划模型第57页/共79页令则模型化为：是2n+2个决策变量，n个约束方程的线性规划模型。第58页/共79页（2）依题意，得一极大极小化模型：min a,b令因对任何i都有：于是得非线性规划模型：又因对任何i都有：化线性规划模型第59页/共79页则得线性规划模型：该模型中只有三个决策变量。第60页/共79页例15某公司上午8点到21点各时段需

20、要的服务人员数量如表1，四个班次的作息时间及月工资如表2。求既满足需求又使公司所付工资总额最少的人员安排。序号时间区间需求人数表1七、人员时间安排问题第61页/共79页班次工作时间休息时间月工资表2解利用表1、表2的各时间区间端点，将营业时间区间细分，并用“1”表示工作，“0”表示休息，得一关联表（表3）。第62页/共79页班 次时 段需求人数表3列给出了各班在哪几个时段工作，行给出了各时段有哪几个班在工作。第63页/共79页设 为第 班安排的人数则得整数规划模型：且为整数，建该模型的关键是：找出各班次工作的关联表，根据关联表写出约束条件。有多余的约束条件！第64页/共79页例16 （选课策略

21、）某校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属 类别和先修课要求如表。问：毕业时，学生最少可以学习哪些课程？第65页/共79页编号 名称 学分 所属类别 先修课要求1 微积分 5 数学2 线性代数 4 数学3 最优化 4 数学；运筹学 微积分；线代4 数据结构 3 数学；计算机 计算机编程5 应用统计 4 数学；运筹学 微积分；线代6 计算机模拟 3 计算机；运筹学 计算机编程7 计算机编程 2 计算机8 预测理论 2 运筹学 应用统计9 数学实验 3 运筹学；计算机 微积分；线代课程情况表第66页/共79页建立课程与课

22、程类别的关联表：类别数学计算机运筹学课程微积分 线代 优化 结构 统计 模拟 编程 预测 实验 需求量则得01规划模型：是前例中需求量为2，3，2的特别情形。解第67页/共79页编号 名称 先修课要求1 微积分 2 线性代数 3 最优化 微积分；线代4 数据结构 计算机编程5 应用统计 微积分；线代6 计算机模拟 计算机编程7 计算机编程 8 预测理论 应用统计9 数学实验 微积分；线代课程情况表第68页/共79页课程总数类别（需求）限制先修要求注意表述方法！第69页/共79页例17 一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。单位利润产品原料单

23、耗甲 乙总量解 设 为甲，乙的产量则双目标规划模型一般形式：矛盾的八、线性多目标规划模型第70页/共79页化成单目标规划模型化法一或化法二 为目标权重或偏好系数。均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出满意解。第71页/共79页例17中，要求利润最大，同时产量之和最小，这种目标称为理想目标。这些目标往往是相互矛盾的，不可能同时达到最优。更现实的做法是：给出目标值，将理想目标转化为现实目标，求出尽量达到目标值的生产方案。如要求：总利润产量之和把目标函数转化成了约束条件引入正负偏差变量 、，将多目标规划模型转化为目标规划模型。九、线性目标规划模型第72页/共79页Min 要“”成

24、立，只需 min 要“”成立，需min目标规划模型达成函数第73页/共79页一般方法：目标类型目标规划格式极小化第74页/共79页注：1.对于硬约束“”,可不设正偏差变量 ，即直接取 。对于“”，可直接取 。2.关于优先级问题例如：上例中，目标的重要性依次为：1 A,B两种原料一定不能超过限量；2 原料B尽量用完；3 利润超过1000；4 产量之和尽量少。于是，达成函数可写为：Min 其中为优先因子或Min 第75页/共79页实验作业 1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60

25、千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.第76页/共79页77 2.某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台每季度的生产费用为 （元），其中x是该季生产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低第77页/共79页3.某商店有五位工作人员:经理1人,主任1人,售货员3人.有关情况见下表.设广告费对销售额的贡献为其投入的15倍,各工作人员的收入相当于其完成销售额的5.5%.问如何安排才能达到以下的目标:P1保证全体人员正常工作时间;P2 至少完成销售额70000元;P3主任的月收入不少于1200元,售货员A和B的月收入不少于600元和400元;P4 全体人员加班时间不超过规定;P5广告费不超过3000元,力争销售额增加10000元,前者的重要性为后者的两倍.每小时对销售额的贡献(元)每 月 总 工时每月加班限量(工时)经理 144 200 24主任 96 200 24售货员A 54 172 52售货员B 30 160 32售货员C 9 100 32第78页/共79页感谢您的观看！第79页/共79页