《2019运筹学模型线性规划课件》由会员分享，可在线阅读，更多相关《2019运筹学模型线性规划课件（24页珍藏版）》请在金锄头文库上搜索。
1、运筹学模型,九江职业技术学院 林娜,运筹学作为科学名字是出现在20世纪30年代末。当时英、美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理运用雷达开始进行一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”（Operational Research）（我国在1957年正式定名为运筹学）。为了进行运筹学研究，在英、美的军队中成立了一些专门小组，开展了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400%，研究还使船只在受
2、敌机攻击时，中弹数由47%降到29%。二战结束后，在英、美军队中相继成立了更为正式的运筹研究组织。并以兰德公司（RAND）为首的一些部门开始着重研究战略性问题、未来的武器系统的设计和未来战争的战略。到60年代，参与了战略力量的构成和数量问题研究，除军事方面的应用研究以外，相继在工业、农业、经济和社会问题等各领域都有应用。与此同时，运筹学有了飞快的发展，并形成了运筹学的许多分支。如数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论等。,0 绪 论 0-1 运筹学简史,在中国，最早的运筹学思想有战国时期的田忌赛
3、马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。 50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。 1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改
4、名为“中国运筹学会”。,究竟什么是运筹学?,?,运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。,0-2 运筹学的概念,0-3 运筹学的基本内容,1、线性规划（Linear Program）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。 2、整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束。 3、非线性规划(Nonlinear P
5、rogram)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。 4、动态规划(Dynamic Program):多阶段决策问题。是美国贝尔曼于1951年提出的。,5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。 6、存储模型（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。 7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。 8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。 9、
6、决策分析(Decision Analysis) ：主要研究定量化决策。,今天我们给大家介绍的是应用最为广泛的线性规划,1 线性规划问题及其数学模型 1-1 问题的提出,例1某工厂在计划期内要安排生产、的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？,解：设x1, x2分别表示在计划期内生产产品、的产量。 由于资源的限制，所以有： 机器设备的限制条件: x1+2x28 原材料A的限制条件： 4x116 （称为资源约束条件） 原材料B的限制条件： 4x212 同时，产品、的产量不能是负数，所以有 x10，x
7、20 （称为变量的非负约束） 显然，在满足上述约束条件下的变量取值，均能构成可行方案，例如x1 =1，x2=0; x1 =3.5，x2=2等等，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使函数 Z=2x1+3x2的值达到最大。,综上所述，该生产计划安排问题可用以下数学模型表示：,例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。 第一化工厂每天排放污水2万m3，第二化工厂每天排放污水 1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水
8、中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？,解：设工厂1和工厂2每天分别处理污水x1 和x2万m3，总费用为z，则有：,1-2 线性规划的基本概念,以上两例都有一些共同的特征： 用一组变量表示某个方案，通常是该问题要求解的那些未知量，用 x=(x1,x2,xn)T表示，一般这些变量取值是非负的，这里的变量称之为决策变量。 存在对决策变量的约束条件，即x允许取值的范围，通常用一组关于x的等式hi(x)=0或不等式gj(x)0(0)来界定，分别称为等式约束和不等式约束。 与中的几个不等
9、式是问题的约束条件，记为s.t.(即subject to)。 都有一个要达到的目标，一般是达到最大或者最小，它是决策变量x的函数，可以表示成max f(x)或min f(x) 。 与式被称为问题的目标函数。,上述“决策变量、约束条件、目标函数”即为一规划问题数学模型的三个要素。由于上面例子中的目标函数及约束条件均为线性函数，故被称为线性规划问题。 线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题，简称线性规划(Linear Programming)或简称LP。,1、线性规划的数学模型,一般式,标准式,2、线性规划的解法：常用的解法有图解法和单纯型法，但在建模中更普 遍
10、的是使用数学软件求解。如LINGO ， MATHEMATICA。,对线性规划的解法有兴趣的读者可以参阅 其它相关书籍介绍,3、线性规划的建模步骤： 设置要求解的决策变量x1,x2,xn 。 明确目标函数，并用决策变量的线性函数来表示，确定对函数是取最大还是取最小的要求。 找出所有的限制，即约束条件。并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。,1-3 线性规划的实例,例3 配方问题 养海狸鼠饲料中营养要求：Va每天至少700克，Vb每天至少30克，Vc每天刚好200克。现有五种饲料
11、，搭配使用，饲料成分如下表所示，问如何搭配饲料，最省钱？建立该问题的线性规划模型。,解： 抓取饲料I、II、 III、IV、V分别为 x1、 x2、 x3、 x4、 x5kg,决策变量,目标函数,最省钱,约束条件,三种营养素的营养要求限制；非负限制,例4 合理利用线材问题 现要做一百套钢管，每套要长为2.9m、2.1m和1.5m的钢管各一根。已知原料长7.4m，问应如何下料，使用的原料最省。,解： 先看有多少种裁料方案，再进行组合和选择。方案如下表所示：,决策变量,目标函数,原料最省,约束条件,三种长度的钢管在8种切割方案下的总和各不少于100根 ； 非负限制,方案 , ,分别裁原料钢管x1,
12、 x2, x8根,例5 连续投资问题 某公司经调研分析知，在今后三年内有四种投资机会。方案A是在三年内每年年初投资，年底可获利15%，并可将本金收回；方案B是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；方案C是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；方案D是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？,解： 第i 年初(即第i -1年末)投资各项目的资金为xiA , xiB , xiC , xiD 该问
13、题的实际投资背景如下表所示:,决策变量,目标函数,3年末拥有的资金最多,约束条件,每年的投资额等于手中的资金； 非负限制,例6 仓库租用问题 A公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资。已知各月份所需仓库面积数列于表1。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表2。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该公司可根据需要，在任何一个月初办理租借合同。.每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,表1,表2,解： 设xij表示A公司在第i(i=1,2,3,4
14、)个月初签订的租借期为j(j=1,2,3,4)个月的仓库面积的合同(单位为100m2)。因5月份起该公司不需要租借仓库，该问题的实际投资背景如下表所示:,决策变量,目标函数,约束条件,每个月份所需仓库面积的限制； 非负限制,例7 混合配料问题 某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C含量，原料成本，各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少时，使该厂获利最大。试建立这个问题的线性规划模型。,解： 设xij表示用第 i种原料(i =1,2,3表示A,B,C三种原料)生产第j种糖果(j=1,2
15、,3,表示甲,乙丙三种糖果)的kg数。,决策变量,目标函数,约束条件,原料月供应量限制,含量成份的限制,例8 一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为2000万米3 ，储存费用为（70+100u）千元/万米3 ，u为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。,例9 有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货
16、物待运，已知有关数据列于表2。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线性规划模型。,在我国古代的北宋（公元9601127 年）年间，有一天皇帝居住的皇城（今河南开封）因不慎失火，酿成一场大灾，熊熊大火使鳞次栉比、覆压数里的皇宫，在一夜之间变成断壁残垣。为了修复烧毁的宫殿，皇帝诏令大臣丁渭组织民工限期完工。当时，既无汽车、吊车，又无升降机、搅拌机，一切工作都只能人挑肩扛。加之皇宫的建设不同于寻常民房建筑，它高大宽敞、富丽堂皇、雕梁画栋、十分考究，免不了费时费工，耗费大量的砖、砂、石、瓦和木材等。当时，使丁渭头痛的三个主要问题是：1.京城内烧砖无土，2.大量建筑材料很难运进城内，3.清墟时无处堆放大量的建筑垃圾
