《线性规划》课件

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