运筹与决策之2线性规划-课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹与决策之2线性规划-课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹 决策 线性规划 课件
- 资源描述:
-
1、运筹与决策之2线性规划1Question线性规划的概念和建模线性规划的概念和建模线性规划的图解法线性规划的图解法单纯形法基本步骤单纯形法基本步骤计算机软件求解计算机软件求解LP问题(下料优化)问题(下料优化)Case 2:灵敏度分析灵敏度分析(运筹与决策之2线性规划21绪论绪论 Introduction2线性规划线性规划 Linear Programming3运输问题运输问题 Transportation Models 4整数规划整数规划 Integer Programming5网络模型网络模型 Network Models6项目计划项目计划 PERT&CPM7排队论排队论 Queueing
2、Models8 模拟模拟 Simulation 9决策分析决策分析 Decision Theory10多目标决策多目标决策 Multi-objective Decision运筹与决策之2线性规划3l线性规划问题的导出线性规划问题的导出lOR在企业管理的具体应用在企业管理的具体应用例例1、家具厂生产计划问题、家具厂生产计划问题例例3、合理下料问题、合理下料问题l线性规划概念和模型线性规划概念和模型运筹与决策之2线性规划4 产品产品 A B可用资源可用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬运工搬运工 0 2 24 利润利润(¥)40 50例例1、家具厂生产计划问题、家具厂生产
3、计划问题A,B 各生产多少各生产多少,可获最大利润可获最大利润?如何建模?如何建模?运筹与决策之2线性规划5产品消耗系数、利润、可用资源产品消耗系数、利润、可用资源A,B 各生产多少各生产多少最大利润最大利润运筹与决策之2线性规划6x1+2x2 30 3x1+2x2 60 2x2 24 x1,x2 0max Z=40 x1+50 x2解解:设产品设产品A,B产量分别为变量产量分别为变量x1,x2运筹与决策之2线性规划7例例2 2 营养配餐营养配餐求:最低成本的原料混合方案求:最低成本的原料混合方案 原料原料i A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1
4、 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量如何建模?如何建模?运筹与决策之2线性规划8解:设每单位添加剂中原料解:设每单位添加剂中原料i的用量为的用量为xi(i=1,2,3,4)Min Z=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)运筹与决策之2线性规划9定义:定义:对于求取一组变量对于求取一组变量 xj(j=1,2,.,n),使之既,使之既满足线性约束条件,又使具有线性的目满足线性约束条件,又使具有线性的目标函数取得极值的一类
5、最优化问题称为标函数取得极值的一类最优化问题称为线性规划问题。线性规划问题。运筹与决策之2线性规划10l要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映l对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择l有影响决策的若干约束条件有影响决策的若干约束条件运筹与决策之2线性规划11l线性规划很容易而有效率地被求解线性规划很容易而有效率地被求解l如果存在最优解,则必能够找到如果存在最优解,则必能够找到l功能强大的敏感性分析(功能强大的敏感性分析(sensitivity analysis)l许多实际问题本质上是线性的许多实际问题本质上是线性的运筹与决策之2线性规
6、划12l决策变量决策变量:向量:向量(x1 xn)T 决策人要决策人要考虑和控制的因素非负考虑和控制的因素非负l约束条件约束条件:线性等式或不等式:线性等式或不等式l目标函数目标函数:Z=(x1 xn)线性式,求线性式,求Z极大或极小极大或极小运筹与决策之2线性规划13一般式一般式max(min)Z=C1X1+C2X2+CnXna11X1+a12X2+a1nXn (=,(=,)b)b1 1a21X1+a22X2+a2nXn (=,(=,)b)b2 2 am1X1+am2X2+amnXn (=,(=,)b)bm mXj j 0(0(j=1,n)运筹与决策之2线性规划14njjjXCZ1max(m
7、in),2,1(0),2,1(1njXmibXajinjjij运筹与决策之2线性规划15l比例性比例性:决策变量变化引起目标的改变:决策变量变化引起目标的改变量与决策变量改变量成正比量与决策变量改变量成正比l可加性可加性:每个决策变量对目标和约束的:每个决策变量对目标和约束的影响独立于其它变量影响独立于其它变量l连续性连续性:每个决策变量取连续值:每个决策变量取连续值l确定性确定性:线性规划中的参数:线性规划中的参数aij,bi,ci为为确定值确定值 运筹与决策之2线性规划16某钢筋架需要某钢筋架需要 长度长度1.5m、2.1m和和 2.9m各各100段段,每根标准钢筋长度为,每根标准钢筋长度
8、为7.4m,问如何,问如何合理下料所需标准钢筋数目最少?合理下料所需标准钢筋数目最少?2.9m 1 2 0 1 0 2.9m 1 2 0 1 0 2.1m 0 0 2 2 1 2.1m 0 0 2 2 1 1.5m 3 1 2 0 3 1.5m 3 1 2 0 3 合计合计 7.4 7.3 7.2 7.1 6.67.4 7.3 7.2 7.1 6.6 料头料头 0 0.1 0.2 0.3 0.80 0.1 0.2 0.3 0.8例例3 3、合理下料问题、合理下料问题运筹与决策之2线性规划17解:设按第解:设按第i种方案下料的原材料为种方案下料的原材料为xi根根min Z=0.1x2+0.2x3
9、+0.3x4+0.8x5 x1+2x2 +x4 =100 2x3+2x4+x5=100 3x1+x2+2x3 +3x5=100 xi 0(i=1,5)如何正确建模?如何正确建模?运筹与决策之2线性规划18l决策变量缺少整数变量约束决策变量缺少整数变量约束l约束条件为等式约束条件为等式l用余料作为目标函数用余料作为目标函数l下料方式不全(少下料方式不全(少3种下料方式)种下料方式)运筹与决策之2线性规划19解:设按第解:设按第i种方案下料的原材料为种方案下料的原材料为xi根根min Z=x1+x2+x3+x4+x5+x6+x7+x8 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x
10、6+x7 100 x1+x3+3x4 +2x6+3x7 +4x8 100 xi 0(i=1,8),且为整数且为整数如何建模?如何建模?运筹与决策之2线性规划20例例4 4、运输问题、运输问题某公司有三个分厂分别供应三个市场,某公司有三个分厂分别供应三个市场,具体生产能力和需求量如下表:具体生产能力和需求量如下表:如何建模?如何建模?市场市场1 市场市场2 市场市场3 产量产量工厂工厂1 2 1 3 50工厂工厂2 2 2 4 30工厂工厂3 3 4 2 10 需求需求 40 15 35运筹与决策之2线性规划21设设xij为为i 工厂运到工厂运到 j市场的产品数量市场的产品数量(i 1,2,3,
11、j 1,2,3)min Z=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0运筹与决策之2线性规划22例例5 5、连续投资、连续投资1010万元万元lA:从第:从第1年年 到第到第4年每年初要投资,次年末年每年初要投资,次年末回收本利回收本利1.15lB:第第3年初投资,到第年初投资,到第5年末回收年末回收1.25,最大,最大投资投资4万元万元lC:第第2年初投资,到第
12、年初投资,到第5年末回收年末回收1.40,最大,最大投资投资3万元万元lD:每年初投资,每年末回收每年初投资,每年末回收1.11。求:求:5 5年末总资本最大年末总资本最大如何建模?如何建模?运筹与决策之2线性规划23分析分析 1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D Xik(i=1,2,5;k=A,B,C,D)第第i年初投年初投k项目的资金数项目的资金数max Z=1.15x4A+1.40 x2C+1.25x3B+1.11x5Dx1A+x1D 10 x2A+x2C+x2D=1.11 x1Dx2C 3x3A+x3B+x
13、3D=1.15 x1A+1.11 x2Dx3B 4x4A+x4D=1.15 x2A+1.11 x3Dx5D=1.15 x3A+1.11 x4D xik 0运筹与决策之2线性规划25AX=b (1)X 0 (2)max Z=CX (3)定义定义1 1:满足约束满足约束(1)、(2)的的X=(X1 Xn)T称为称为LP问题的问题的可行解可行解,全部可行解集合称为,全部可行解集合称为可行域。可行域。定义定义2 2:满足满足(3)的可行解称为的可行解称为LP问题的问题的最优解。最优解。运筹与决策之2线性规划26 产品产品 A B 备用资源备用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬
14、运工搬运工 0 2 24 利润利润 40 50例例1、家具厂生产计划问题、家具厂生产计划问题A,B 各生产多少各生产多少,可获最大利润可获最大利润?运筹与决策之2线性规划27建立模型建立模型max Z=40X1+50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 ,X2 0 0建模后如何计算?建模后如何计算?运筹与决策之2线性规划28解:解:(1)、确定可行域、确定可行域 X1 0 0 X1=0=0(横轴横轴)X2 0 0 X2=0=0(纵轴纵轴)X1+2X2 30X1+2X2=30两点两点(0,15)、(30,0)2030100102030X2DABC3X1+2X2=60(
15、0,30)(20,0)2X2=24X1运筹与决策之2线性规划29(2)、求最优解、求最优解解:解:X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2 (0,0),(10,-8)0203010102030X1X2DABCDABCC点:点:X1+2X2=30 3X1+2X2=60运筹与决策之2线性规划30几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集:约束半平面的交集:凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束
16、直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线:目标函数等值线:一组平行线一组平行线 目标函数值等于一个常目标函数值等于一个常数的解数的解如何对应?如何对应?运筹与决策之2线性规划31(1)用字母表示可行域;)用字母表示可行域;(2)画出目标函数的平行线;)画出目标函数的平行线;(3)注意目标函数的斜率;注意目标函数的斜率;(4)适当的说明语句(包括可行域、最优)适当的说明语句(包括可行域、最优解、目标函数值等)解、目标函数值等)运筹与决策之2线性规划32例例2、图解法、图解法 max Z=40X1+80X2 X1+2X2 30 3X1+2X2 60 2X2
17、24 X1,X2 0 0运筹与决策之2线性规划330Z=40 X1+80X2=0 X1+2X2=30DABCX2X1X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)求解求解最优解:最优解:BCBC线段线段B B点点C C点点无穷多解无穷多解运筹与决策之2线性规划34X1=6+(1-)15X2=12+(1-)7.5X1=15-9 X2=7.5+4.5 (0 1)X=+(1-)max Z=1200 X1 6 15 X2 12 7.5运筹与决策之2线性规划35无界无界无有限最优解无有限最优解例例3、max Z=2X1+4X2 2X1+X2 8 8-2X1+X2
展开阅读全文