《线性规划》课件.ppt

1、OPERATIONS RESEARCH 运筹学怎样把事情做到最好 绪论 Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本运用学 港台作业研究中国大陆运筹学Operational Research原来名称，意为军事行动研究历史渊源n运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题 学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学

2、方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学的工作步骤n确定问题n搜集数据建立模型n检验模型n求解模型n结果分析n结果实施运筹学与计算机n计算机为运筹学提供解题工具。n要学会解题的思路与方法，建立模型很重要。线性规划线性规划（Linear ProgrammingLinear Programming，简称，简称LPLP）n线性规划的发展线性规划的发展n1939年，前

3、苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年，Dantzig提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法n1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。n1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。线性规划研究的主要问题线性规划研究的主要问题 一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最

4、优解（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.2 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要

5、求：生产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 药物原料ABC单位成本（元吨）甲1235乙2016丙1417丁1228例3、合理下料问题 某车间接到制作 100 付钢架的定单，每付钢架要用长为 2.9m,2.7m,1.5m的圆钢 各一根，已

6、知原料长 7.4m。问如何下料，可使所用原料最省。例3、合理下料问题 设 xj 分别代表采用切割方案18的套数，方方案案2.9m2.1m1.5m合合计计余余料料12017.30.121207.10.331116.50.941037.4050306.31.160227.20.210,50,100:0,100231002321002.2.01.109.03.01.0)(min,64654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf最优解为则有零料最少若目标函数为使裁剪后16,30,50,10:0,100231002321002.)(m

7、in,421654321643165324321654321OBJxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxf则有最优解为则有钢筋最少若目标函数为使购买的二、数学模型二、数学模型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,xn)T表示某一方案，且决策变量取

8、值非负；满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。其它形式其它形式其中：),2,1(0),2,1(max(min)11njxmibxaxczjnjijijnjjj求和形式求和形式矩阵形式矩阵形式0 max(min)XbAXCXznxxxX21决策变量决策变量常数项常数项nbbbb21系数矩阵系数矩阵nmijmnmmnnaaaaaaaaaaA212222111211价值系数价值系数ncccC21其中：线性规划数学模型

9、的建立线性规划数学模型的建立一、建模条件一、建模条件1 优化条件：问题所要达到的目标能用线型函数描述，且能够用极值 （max 或 min）来表示；2 限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示；3 选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。线性规划图解法线性规划图解法一、解题步骤一、解题步骤4 将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部 分，称为可行域，可行域中的点称为可行解。2 标出目标函数值增加的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向

10、 平行移动，找与可行域最后相交的点，该点就是最优解。二、建模步骤二、建模步骤1 确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目 问什么就设什么为决策变量。2 找出所有限定条件：即决策变量受到的所有的约束；3 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。线性规划的图解max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小

11、的方案。(一)、运输问题 例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+

12、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 件工作的时间（或费用）为件工作的时间（或费用）为ci

13、j,，问如何分派这些人员使总时间（或费用）最少。问如何分派这些人员使总时间（或费用）最少。n 解解 1，第第i人做第人做第j件工作，件工作，n 设设 xij=n 0 ,否则否则n n 则得则得0-1规划：规划：n ).2.1,1(0).2.1(1).2.1(1min1111njixnjxnixxcZijniijnjijninjijij或(三)、网络问题n 一个网络包括一些结点（用圆圈表示），每个结点由几条弧（用箭头表示）与其它结点相连，如图：n 2 15 4n 20 12 8 9n 1 5 10 7n 14 10 8 12n 3 13 6 最短路问题解：设 1,有从 i 到期 j 的弧n xi

14、j=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=0n-x25-x45+x56+x57=0n-x36-x56+x67=0n-x47-x57-x67=-1（到达 7 的汽车为一辆）nXij=0,或1,i,j=1,2,7.(四)、选址问题n 例、某公司拟定在东、西、南三区建立门市部，拟议中有7个地址A1，A2

15、，,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规划模型：7,2,1,10,1,1,2,.max76543217171ixxxxxxxxbxbtsxcziiiiiii或(五五)、曲线拟合问题、曲线拟合问题n例例 已知变量已知变量y随变量随变量x变化，变化，并且已知一组观测值并且已知一组观测值n （xi,yi),I=1,2,n.n(1)拟合一

16、条回归直线拟合一条回归直线,使回归值使回归值与观察值的绝对偏差之和最小与观察值的绝对偏差之和最小;n(2)拟合一条回归直线拟合一条回归直线,使回归值使回归值与观察值的最大偏差最小与观察值的最大偏差最小.n解解 设设所求回所求回归归直直线线方程方程为为n y=a+bxy=a+bxn(1)(1)据题意，应求使据题意，应求使n最小的最小的 a,ba,b。由于函数中带有绝对值，不便用。由于函数中带有绝对值，不便用数学分析方法来处理，但用线性规划方法来处数学分析方法来处理，但用线性规划方法来处理就变得较容易。令理就变得较容易。令n则得线性规划模型则得线性规划模型 niiibxayz1iiiiiiiivu

17、bxayvubxay,n模型中，xi,yi已知，ui,vi,a,b为决策变量。原问题化为含（2n+2)个决策变量，n个约束方程的一极小化问题。为自由变量bavuniyvubxatsvuziiiiiiniii,0,0.,2,1,.min1(六)、人员安排问题n例 某公司的营业时间是上午8点到22点，以两小时为一时段，各时段内所需的服务人员数如下表，每个服务人员可在任一时段开始上班，但要工作 8 小时，而工资都相同。问应如何安排服务人员使公司所付工资总数最少。序 号 时 间 区 间需求人数 1 8：0010：00 20 2 10：0012：00 25 3 12：0014：00 10 4 14：00

18、16：00 30 5 16：0018：00 20 6 18：0020：00 10 7 20：0022：00 5n解解 设设xi为时段为时段 i 开始工作的人数开始工作的人数（i=1,2,3,4).由于各班工资相同，要求公由于各班工资相同，要求公司所付的工资最少也就是要求服务人员最司所付的工资最少也就是要求服务人员最少。于是可得整数规划模型：少。于是可得整数规划模型：.4,3,2,10,5,10,20,30,10,25,20.min443432432132121141，ixxxxxxxxxxxxxxxxxtsxziii且为整数n例例 某公司的营业时间是上午某公司的营业时间是上午8点到点到21点。

19、点。服务人员中途需要服务人员中途需要1小时吃饭和休息时间，小时吃饭和休息时间，每人的工作时间为每人的工作时间为8小时。小时。上午上午8点到点到17点工作的人员月工资为点工作的人员月工资为800元，中午元，中午12点到点到21点工作的人员月工资为点工作的人员月工资为900元。元。为保证营业时间内都有人上班，公司安为保证营业时间内都有人上班，公司安排了四个班次，其班次和休息时间安排排了四个班次，其班次和休息时间安排如下表一。各时段需求的人数如上例之如下表一。各时段需求的人数如上例之表，只是第表，只是第6、7段合并为段合并为18点到点到21点，点，需求人数为需求人数为10人。问应如何安排服务人人。问

20、应如何安排服务人员既满足需求又使公司所付工资总数最员既满足需求又使公司所付工资总数最少。少。n 表表一一班次班次 工作时间工作时间 休息时间休息时间 月工资月工资 18:00-17:0012:00-13:00 800 28:00-17:0013:00-14:00 800 312:00-21:0016:00-17:00 900 412:00-21:0017:00-18:00 900n解 为了便于建立模型，可用各班中途休息的起止时刻和上例之表中时间区间的起止时间分细，并求出各班工作的关联表，见表二。表中nj 列的“1”表示该班次在相应的时段内工作，“0”表示不工作。表 二 时段 班次 1 2 3

21、4 需求人数 8:00-10:00 1 1 0 0 2010:00-12:00 1 1 0 0 2512:00-13:00 0 1 1 1 1013:00-14:00 1 0 1 1 1014:00-16:00 1 1 1 1 3016:00-17:00 1 1 0 1 2017:00-18:00 0 0 1 0 2018:00-21:00 0 0 1 1 10n设xi表示第i班安排的人数（i=1,2,3,4)，则可得整数规划模型：.4,3,2,10,10,20,20,30,10,10,25.900900800800min4334214321431432214321i，xxxxxxxxxxxx

22、xxxxxxxtsxxxxzi且为整数(七七)、有配套约束的资源优化问题、有配套约束的资源优化问题n例例 某公司计划用资金某公司计划用资金60万来购买万来购买A，B，C三种运输汽车。已知三种运输汽车。已知A种汽车每辆为种汽车每辆为1万万元，每班需一名司机，可完成每公里元，每班需一名司机，可完成每公里2100 吨。吨。B种汽车每辆为种汽车每辆为2万元，每班需万元，每班需两名司机，可完成每公里两名司机，可完成每公里3600吨。吨。C种汽种汽车每辆为车每辆为2.3万元，每班需两名司机，可万元，每班需两名司机，可完成每公里完成每公里3780吨。每辆汽车每天最多吨。每辆汽车每天最多安排三班，每个司机每天

23、最多安排一班。安排三班，每个司机每天最多安排一班。购买汽车数量不超过购买汽车数量不超过30辆、司机不超过辆、司机不超过145人。问：每种汽车应购买多少辆，可人。问：每种汽车应购买多少辆，可使公司今后每天可完成的公里吨数最大？使公司今后每天可完成的公里吨数最大？n解解 设购买设购买A种汽车中，每天只安排一班的有种汽车中，每天只安排一班的有x11辆，每天安排二班的有辆，每天安排二班的有x12辆，每天安排三辆，每天安排三班的有班的有x13辆；同样设购买辆；同样设购买B种汽车依次有种汽车依次有x21,x22,x23辆辆;购买购买C种汽车依次有种汽车依次有x31,x32,x33辆辆.因此有因此有.3,2

24、,1,0,14564264232,30,60313.20.20.1.11340756037801080072003600630042002100max3332312322211312113332312322211312333223222113121133323123222113121111且为整数jixxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxzij(八八)、多周期动态生产计划问题、多周期动态生产计划问题n例例 某柴油机厂接到今年某柴油机厂接到今年1至至4季度柴季度柴油机生产订单分别为：油机生产订单分别为：3000台，台，4500台，台，3500台，台，500

25、0台。该厂每台。该厂每季度正常生产量为季度正常生产量为3000台，若加班台，若加班可多生产可多生产1500台，正常生产成本为台，正常生产成本为每台每台5000元，加班生产还要追加成元，加班生产还要追加成本每台本每台1500元。库存成本为每台每元。库存成本为每台每季度季度200元，问该柴油机厂该如何组元，问该柴油机厂该如何组织生产才能使生产成本最低？织生产才能使生产成本最低？n解解 设设xi1为第为第i个季度正常生产的柴油机台数，个季度正常生产的柴油机台数，xi2为第为第i个季度加班生产的柴油机台数，个季度加班生产的柴油机台数，xi3为第为第i个个季度初库存数。季度初库存数。i=1,2,3,4.

26、第一季度初及年底的第一季度初及年底的库存数均产零，若记库存数均产零，若记di为第为第i季度的需求量；季度的需求量；c1,c2,c3分别为正常生产、加班生产、库存（每分别为正常生产、加班生产、库存（每季度）每台柴油机的成本。则其数学模型为：代季度）每台柴油机的成本。则其数学模型为：代入具体数据，得数学模型如下：入具体数据，得数学模型如下：.,4,3,2,10,0,4,3,2,1.;min53321,3,132141332211且为整数ixxxxidxxxxtsxcxcxcziiiiiiiiiiii.4,3,2,1.15000,300010,5000,3500,4500,3000;20065005

27、000min243424143333231332322212312114333234232221241312111且为整数ixxxxxxxxxxxxxxxxxxxxxxxxxxxzii(十二十二)、投资问题、投资问题n 投资者经常会遇到投资项目的组合选择问投资者经常会遇到投资项目的组合选择问题，要考虑的因素有收益率、风险、增长潜力题，要考虑的因素有收益率、风险、增长潜力等条件，并进行综合权衡，以求得一个最佳投等条件，并进行综合权衡，以求得一个最佳投资方案。资方案。n例例 某投资公司有某投资公司有50万元可用于长期投资，可万元可用于长期投资，可供选择的投资项目包括购买国库券、购买公司供选择的投资

28、项目包括购买国库券、购买公司债券、投资房地产、购买股票、银行短期或长债券、投资房地产、购买股票、银行短期或长期储蓄。各种投资方式的投资期限，年收益率，期储蓄。各种投资方式的投资期限，年收益率，风险系数，增长潜力的具体参数见下表。若投风险系数，增长潜力的具体参数见下表。若投资者希望投资组合的平均年限不超过资者希望投资组合的平均年限不超过5年，平年，平均的期望收益率不低于均的期望收益率不低于13%，风险系数不超过，风险系数不超过4，收益的增长潜力不低于，收益的增长潜力不低于10%。问在满足上。问在满足上述要求前提下，投机者该如何选择投资组合使述要求前提下，投机者该如何选择投资组合使平均年平均收益率

29、最高？平均年平均收益率最高？序序号号投资方式投资方式投资期限投资期限（年）（年）年收益年收益率率(%）风险风险系数系数增长潜增长潜力力(%）1国库券国库券311102公司债券公司债券10153153房地产房地产6258304股票股票2206205短期储蓄短期储蓄110156长期储蓄长期储蓄512210n解解 设设xi为第为第i种投资方式在总投资中所占种投资方式在总投资中所占的比利的比利,则该数学模型为则该数学模型为:.6,2,10,11,106105542033015,42683,13121020251511,5526103.;121020251511max654322654321654321

30、654321654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxzjn例例 某投资者有资金某投资者有资金10万元万元,考虑在今后考虑在今后5年内年内给下列给下列4个项目进行投资个项目进行投资,已知已知:n 项目项目A：从第：从第1年到第年到第4年每年年初需要投年每年年初需要投资，并于次年末回收本利资，并于次年末回收本利115%.n 项目项目B:第第3年初需要投资年初需要投资,到第到第5年末能回年末能回收本利收本利125%,但规定投资额不超过但规定投资额不超过4万元万元n 项目项目C:第第2年初需要投资年初需要投资,到第到第5年末能回年末能回收本利收本利14

31、0%,但规定最大投资额不超过但规定最大投资额不超过3万元万元.n 项目项目D:5年内每年初可购买公债年内每年初可购买公债,于当年亩于当年亩归还归还,并加利息并加利息6%.n 问该投资者应如何安排他的资金问该投资者应如何安排他的资金,确定给确定给这些项目每年的投资额这些项目每年的投资额,使到第使到第5年末能拥有的年末能拥有的资金本利总额为最大资金本利总额为最大?n解解 记记xiA,xiB,xiC,xiD(i=1,2,5)分别表示第分别表示第i年初给项年初给项目目A,B,C,D的投资额的投资额,它们都是决策变量它们都是决策变量,为了便于书为了便于书写数学模型写数学模型,列表如下列表如下:年份项目

32、1 2 3 4 5 AX1AX2AX3AX4A BX3B CX2C DX1DX2DX3DX4DX5Dn根据项目根据项目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

33、+x1D=10000.n 第第2年年初该投资者手中拥有资金只有（年年初该投资者手中拥有资金只有（1+6%）x1D,故有故有n x2A+x2C+x2D=1.06x1D.n 第第3年年初该投资者拥有资金从年年初该投资者拥有资金从D项目收回的项目收回的本金：本金：1.06x2D,及从项目及从项目A中第中第1年投资收回的本年投资收回的本金：金：1.15x1A,故有故有 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