《线性规划》PPT课件.ppt

OPERATIONS RESEARCH 运筹学,怎样把事情做到最好 张朝伦,绪论,Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学 Operational Research原来名称，意为军事行动研究历史渊源,运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队,运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题,学科性质,应用学科 Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。 Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。 中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,运筹学的工作步骤,确定问题 搜集数据建立模型 检验模型 求解模型 结果分析 结果实施,运筹学与计算机,计算机为运筹学提供解题工具。 要学会解题的思路与方法，建立模型很重要。,线性规划 （Linear Programming，简称LP）,线性规划的发展 1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年，Dantzig提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法 1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。 1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。,线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究如 何充分合理地使用它们，才能使完成的任务量为最大。, 实际上，上述两类问题是一个问题的两个不同的方面，都是求问 题的最优解（ max 或 min ）。,另一类是当一项任务确定以后，研究如何统筹安排，才能使完成 任务所耗费的资源量为最少。,线性规划,线性规划的基本概念 一、问题的提出,解：,1.决策变量：设产品I、II的产量分 别为 x1、x2,2.目标函数：设总运费为z，则有： max z = 2 x1 + 3 x2,3.约束条件：,例1.2 某厂生产三种药物，这些药 物可以从四种不同的原料中提取。 下表给出了单位原料可提取的药物 量,要求：生产A种药物至少160单位； B种药物恰好200单位，C种药物不 超过180单位，且使原料总成本最 小。,解：,1.决策变量：设四种原料的使用 量分别为： x1、x2 、x3 、x4,2.目标函数：设总成本为z，则有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x4,3.约束条件：,例3、合理下料问题,例3、合理下料问题 设 xj 分别代表采用切割方案18的套数，,二、数学模型,1.决策变量： X = (x1,x2,xn)T,2.目标函数：max(minz) = c1 x1 + c2 x2 + . + cnxn,三、模型特点,1 都用一组决策变量X = (x1,x2,xn)T表示某一方案，且决策变量取值非负；, 满足以上三个条件的数学模型称为线性规划,2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；,3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。,其它形式,其中：, 求和形式, 矩阵形式,决策变量,常数项,系数矩阵,价值系数,其中：,线性规划数学模型的建立,一、建模条件,1 优化条件：问题所要达到的目标能用线型函数描述，且能够用极值 （max 或 min）来表示；,2 限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示；,3 选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。,线性规划图解法,一、解题步骤,4 将最优解代入目标函数，求出最优值。,1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部 分，称为可行域，可行域中的点称为可行解。,2 标出目标函数值增加的方向。,3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向 平行移动，找与可行域最后相交的点，该点就是最优解。,二、建模步骤,1 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目 问什么就设什么为决策变量。,2 找出所有限定条件：即决策变量受到的所有的约束；,3 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,一般的运输问题就是要解决把某种产 品从若干个产地调运到若干个销地，在每 个产地的供应量与每个销地的需求量已知， 并知道各地之间的运输单价的前提下，如 何确定一个使得总的运输费用最小的方案。,(一)、运输问题,例1. 某公司从两个产地A1,A2将物品运往三个销地B1，B2，B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：,问应如何调运，使得总运输费最小？,解：我们知道A1、A2两个产地的总产量为： 200 + 300 = 500（件）；B1，B2，B3三个销地 的总销量为：150+150+200=500（件）,总产量 等于总销量这是一个产销平衡的运输问题。把 A1，A2 的产量全部分配给B1，B2，B3，正好 满足这三个销地的需要。,从上表可写出此问题的数学模型。 满足产地产量的约束条件为： x11 + x12 + x13 = 200， x21 + x22 + x23 = 300. 满足销地销量的约束条件为： x11 + x21 = 200， x12 + x22 = 300， x13 + x23 = 200.,所以此运输问题的线性规划的模型如下： 目标函数： minf=6x11+4x12+6x13+6x21+5x22+5x23 约束条件： x11 + x12 + x13 = 200， x21 + x22 + x23 = 300， x11 + x21 = 150， x12 + x22 = 150， x13 + x23 = 200. xij0. (i = 1，2；j = 1，2，3),(二)、分派问题,例 设有工作m件，人员个,且一人做一件工作,第 i 人做 j 件工作的时间（或费用）为cij,，问如何分派这些人员使总时间（或费用）最少。 解 1， 第i人做第j件工作， 设 xij= 0 , 否则 则得0-1规划：,(三)、网络问题,一个网络包括一些结点（用圆圈表示），每个结点由几条弧（用箭头表示）与其它结点相连，如图： 2 15 4 20 12 8 9 1 5 10 7 14 10 8 12 3 13 6,最短路问题,解：设 1, 有从 i 到期 j 的弧 xij= 0, 否则 则得0-1规划： Minz=20x12+14x13+15x24+12x25+10x34+13x36 +8x45+9x47+8x56+10x57+12x67(总路程） S.t. X12+x13=1 (从 1 出发的汽车为一辆） -x12+x24+x25=0 -x13+x34+x36=0 -x24-x34+x45+x47=0,-x25-x45+x56+x57=0 -x36-x56+x67=0 -x47-x57-x67=-1（到达 7 的汽车为一辆） Xij=0,或1, i,j=1,2,7.,(四)、选址问题,例、某公司拟定在东、西、南三区建立门市部，拟议中有7个地址A1，A2，,A7可供选择，并规定： 在东区，A1，A2，A3中至多选两个； 在西区，A4，A5中至少选一个； 在南区，A6，A7中至少选一个； 若选Ai,投资bi元，每年可获利估计为ci元,总投资不超过b元.问如何选择门市部的地址公司的年利润最大.,解 设 1，选择Ai, xi= 0，否则 则得0-1规划模型：,(五)、曲线拟合问题,例 已知变量y随变量x变化，并且已知一组观测值 （xi,yi), I=1,2,n. (1)拟合一条回归直线,使回归值与观察值的绝对偏差之和最小; (2)拟合一条回归直线,使回归值与观察值的最大偏差最小.,解 设所求回归直线方程为 y=a+bx (1)据题意，应求使 最小的 a,b。由于函数中带有绝对值，不便用数学分析方法来处理，但用线性规划方法来处理就变得较容易。令 则得线性规划模型,模型中，xi,yi已知，ui,vi, a, b为决策变量。原问题化为含（2n+2)个决策变量，n个约束方程的一极小化问题。,(六)、人员安排问题,例 某公司的营业时间是上午8点到22点，以两小时为一时段，各时段内所需的服务人员数如下表，每个服务人员可在任一时段开始上班，但要工作 8 小时，而工资都相同。问应如何安排服务人员使公司所付工资总数最少。,解 设xi为时段 i 开始工作的人数（i=1,2,3,4).由于各班工资相同，要求公司所付的工资最少也就是要求服务人员最少。于是可得整数规划模型：,例 某公司的营业时间是上午8点到21点。服务人员中途需要1小时吃饭和休息时间，每人的工作时间为8小时。 上午8点到17点工作的人员月工资为800元，中午12点到21点工作的人员月工资为900元。为保证营业时间内都有人上班，公司安排了四个班次，其班次和休息时间安排如下表一。各时段需求的人数如上例之表，只是第6、7段合并为18点到21点，需求人数为10人。问应如何安排服务人员既满足需求又使公司所付工资总数最少。,表一,解 为了便于建立模型，可用各班中途休息的起止时刻和上例之表中时间区间的起止时间分细，并求出各班工作的关联表，见表二。表中 j 列的“1”表示该班次在相应的时段内工作，“0”表示不工作。,表 二,设xi表示第i班安排的人数（i=1,2,3,4)，则可得整数规划模型：,(七)、有配套约束的资源优化问题,例 某公司计划用资金60万来购买A，B，C三种运输汽车。已知A种汽车每辆为1万元，每班需一名司机，可完成每公里2100 吨。B种汽车每辆为2万元，每班需两名司机，可完成每公里3600吨。C种汽车每辆为2.3万元，每班需两名司机，可完成每公里3780吨。每辆汽车每天最多安排三班，每个司机每天最多安排一班。购买汽车数量不超过30辆、司机不超过145人。问：每种汽车应购买多少辆，可使公司今后每天可完成的公里吨数最大？,解 设购买A种汽车中，每天只安排一班的有x11辆，每天安排二班的有x12辆，每天安排三班的有x13辆；同样设购买B种汽车依次有x21,x22,x23辆; 购买C种汽车依次有x31,x32,x33辆.因此有,(八)、多周期动态生产计划问题,例 某柴油机厂接到今年1至4季度柴油机生产订单分别为：3000台，4500台，3500台，5000台。该厂每季度正常生产量为3000台，若加班可多生产1500台，正常生产成本为每台5000元，加班生产还要追加成本每台1500元。库存成本为每台每季度200元，问该柴油机厂该如何组织生产才能使生产成本最低？,解 设xi1为第i个季度正常生产的柴油机台数，xi2为第i个季度加班生产的柴油机台数，xi3为第i个季度初库存数。i=1,2,3,4. 第一季度初及年底的库存数均产零，若记di为第i季度的需求量；c1,c2,c3分别为正常生产、加班生产、库存（每季度）每台柴油机的成本。则其数学模型为：代入具体数据，得数学模型如下：,(十二)、投资问题,投资者经常会遇到投资项目的组合选择问题，要考虑的因素有收益率、风险、增长潜力等条件，并进行综合权衡，以求得一个最佳投资方案。 例 某投资公司有50万元可用于长期投资，可供选择的投资项目包括购买国库券、购买公司债券、投资房地产、购买股票、银行短期或长期储蓄。各种投资方式的投资期限，年收益率，风险系数，增长潜力的具体参数见下表。若投资者希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%。问在满足上述要求前提下，投机者该如何选择投资组合使平均年平均收益率最高？,解 设xi为第i种投资方式在总投资中所占的比利,则该数学模型为:,例 某投资者有资金10万元,考虑在今后5年内给下列4个项目进行投资,已知: 项目A：从第1年到第4年每年年初需要投资，并于次年末回收本利115%. 项目B:第3年初需要投资,到第5年末能回收本利125%,但规定投资额不超过4万元 项目C:第2年初需要投资,到第5年末能回收本利140%,但规定最大投资额不超过3万元. 项目D:5年内每年初可购买公债,于当年亩归还,并加利息6%. 问该投资者应如何安排他的资金,确定给这些项目每年的投资额,使到第5年末能拥有的资金本利总额为最大?,解 记xiA,xiB,xiC,xiD(i=1,2,5)分别表示第i年初给项目A,B,C,