《线性规划》PPT课件PPT课件.ppt

1、OPERATIONS RESEARCH 运筹学,怎样把事情做到最好 张朝伦,1,绪论,Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学 Operational Research原来名称，意为军事行动研究历史渊源,2,运筹学的历史 军事运筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队,3,运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题,4,学科性质,应用学科 Morse (2)拟合一条回归直线,使回归值与观察值的最大偏差最

2、小.,34,解 设所求回归直线方程为 y=a+bx (1)据题意，应求使 最小的 a,b。由于函数中带有绝对值，不便用数学分析方法来处理，但用线性规划方法来处理就变得较容易。令 则得线性规划模型,35,模型中，xi,yi已知，ui,vi, a, b为决策变量。原问题化为含（2n+2)个决策变量，n个约束方程的一极小化问题。,36,(六)、人员安排问题,例 某公司的营业时间是上午8点到22点，以两小时为一时段，各时段内所需的服务人员数如下表，每个服务人员可在任一时段开始上班，但要工作 8 小时，而工资都相同。问应如何安排服务人员使公司所付工资总数最少。,37,38,解 设xi为时段 i 开始工作

3、的人数（i=1,2,3,4).由于各班工资相同，要求公司所付的工资最少也就是要求服务人员最少。于是可得整数规划模型：,39,例 某公司的营业时间是上午8点到21点。服务人员中途需要1小时吃饭和休息时间，每人的工作时间为8小时。 上午8点到17点工作的人员月工资为800元，中午12点到21点工作的人员月工资为900元。为保证营业时间内都有人上班，公司安排了四个班次，其班次和休息时间安排如下表一。各时段需求的人数如上例之表，只是第6、7段合并为18点到21点，需求人数为10人。问应如何安排服务人员既满足需求又使公司所付工资总数最少。,40,表一,41,解 为了便于建立模型，可用各班中途休息的起止时

4、刻和上例之表中时间区间的起止时间分细，并求出各班工作的关联表，见表二。表中 j 列的“1”表示该班次在相应的时段内工作，“0”表示不工作。,42,表 二,43,设xi表示第i班安排的人数（i=1,2,3,4)，则可得整数规划模型：,44,(七)、有配套约束的资源优化问题,例 某公司计划用资金60万来购买A，B，C三种运输汽车。已知A种汽车每辆为1万元，每班需一名司机，可完成每公里2100 吨。B种汽车每辆为2万元，每班需两名司机，可完成每公里3600吨。C种汽车每辆为2.3万元，每班需两名司机，可完成每公里3780吨。每辆汽车每天最多安排三班，每个司机每天最多安排一班。购买汽车数量不超过30辆

5、、司机不超过145人。问：每种汽车应购买多少辆，可使公司今后每天可完成的公里吨数最大？,45,解 设购买A种汽车中，每天只安排一班的有x11辆，每天安排二班的有x12辆，每天安排三班的有x13辆；同样设购买B种汽车依次有x21,x22,x23辆; 购买C种汽车依次有x31,x32,x33辆.因此有,46,(八)、多周期动态生产计划问题,例 某柴油机厂接到今年1至4季度柴油机生产订单分别为：3000台，4500台，3500台，5000台。该厂每季度正常生产量为3000台，若加班可多生产1500台，正常生产成本为每台5000元，加班生产还要追加成本每台1500元。库存成本为每台每季度200元，问该

6、柴油机厂该如何组织生产才能使生产成本最低？,47,解 设xi1为第i个季度正常生产的柴油机台数，xi2为第i个季度加班生产的柴油机台数，xi3为第i个季度初库存数。i=1,2,3,4. 第一季度初及年底的库存数均产零，若记di为第i季度的需求量；c1,c2,c3分别为正常生产、加班生产、库存（每季度）每台柴油机的成本。则其数学模型为：代入具体数据，得数学模型如下：,48,49,(十二)、投资问题,投资者经常会遇到投资项目的组合选择问题，要考虑的因素有收益率、风险、增长潜力等条件，并进行综合权衡，以求得一个最佳投资方案。 例 某投资公司有50万元可用于长期投资，可供选择的投资项目包括购买国库券、

7、购买公司债券、投资房地产、购买股票、银行短期或长期储蓄。各种投资方式的投资期限，年收益率，风险系数，增长潜力的具体参数见下表。若投资者希望投资组合的平均年限不超过5年，平均的期望收益率不低于13%，风险系数不超过4，收益的增长潜力不低于10%。问在满足上述要求前提下，投机者该如何选择投资组合使平均年平均收益率最高？,50,51,解 设xi为第i种投资方式在总投资中所占的比利,则该数学模型为:,52,例 某投资者有资金10万元,考虑在今后5年内给下列4个项目进行投资,已知: 项目A：从第1年到第4年每年年初需要投资，并于次年末回收本利115%. 项目B:第3年初需要投资,到第5年末能回收本利12

8、5%,但规定投资额不超过4万元 项目C:第2年初需要投资,到第5年末能回收本利140%,但规定最大投资额不超过3万元. 项目D:5年内每年初可购买公债,于当年亩归还,并加利息6%. 问该投资者应如何安排他的资金,确定给这些项目每年的投资额,使到第5年末能拥有的资金本利总额为最大?,53,解 记xiA,xiB,xiC,xiD(i=1,2,5)分别表示第i年初给项目A,B,C,D的投资额,它们都是决策变量,为了便于书写数学模型,列表如下:,54,根据项目A，B，C，D的不同情况，在第5年末能收回的本利分别为：1.15x4A,1.25x3B,1.40 x2C,及1.06x5D。因此目标函数为： ma

9、xz= 1.15x4A+ 1.25x3B+ 1.40 x2C+ 1.06x5D. 约束条件是每年年初的投资额等于该投资者年初所拥有的资金。 第1年年初该投资者拥有10万元资金，故有 x1A+x1D=10000. 第2年年初该投资者手中拥有资金只有（1+6%）x1D,故有 x2A+x2C+x2D=1.06x1D. 第3年年初该投资者拥有资金从D项目收回的本金：1.06x2D,及从项目A中第1年投资收回的本金：1.15x1A,55,故有 x3A+x3B+x3D=1.15x1A+1.06x2D. 同理第4年、第5年有约束为： X4A+X4D=1.15X2A+1.06X3D, X5D =1.15X3A+1.06X4D. 故本例数学模型经化间后为 maxz= 1.15x4A+ 1.25x3B+ 1.40 x2C+ 1.06x