《经济管理决策分析方法最优化决策模型.pptx》由会员分享，可在线阅读，更多相关《经济管理决策分析方法最优化决策模型.pptx（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内容简介内容简介最优化问题的定义、分类和数学模型，规划求解工具；目标函数和约束条件与决策变量之间都是线性关系的规划问题；目标函数或者约束条件与决策变量之间不是线性关系的规划问题；规划求解报告的生成与分析。1第1页/共57页第一节第一节 最优化最优化问题概述问题概述最优化问题的概念最优化问题分类最优化问题的数学模型最优化问题的求解方法2第2页/共57页一一.最优化最优化问题的问题的概念概念最优化问题就是在给定条件下寻找最佳方案的问题；最佳的含义有各种各样：成本最小、收益最大、利润最多、距离最短、时间最少、空间最小等，即在资源给定时寻找最好的目标，或在目标确定下使用最少的资源。3第3页/共57页二
2、二.最优化最优化问题问题分类分类根据有无约束条件 无约束条件的最优化问题，在资源无限的情况下求解最佳目标；有约束条件的最优化问题，在资源限定的情况下求解最佳目标；实际问题一般都是有资源限制的，所以大部分最优化问题都是有约束条件的最优化问题。根据决策变量在目标函数与约束条件中出现的形式 线性规划问题 非线性规划问题 二次规划问题 根据决策变量是否要求取整数 整数规划问题 0-1规划问题 任意规划问题4第4页/共57页三三.最优化最优化问题的问题的数学模型数学模型最优化问题可表示为如下的数学形式：5第5页/共57页四四.最优化最优化问题的求解问题的求解方法方法方法一：公式法分析问题，推导出计算最优
3、解的公式。方法二：用规划求解工具求解启动规划求解工具，在规划求解参数对话框中设置目标单元格（目标变量）和可变单元格（决策变量），设置目标单元格的目标值（最大、最小或者某一特定值），添加约束条件，另外也可以设置一些附加参数。按“求解”按钮，规划求解工具就根据参数设置寻求最优解。6第6页/共57页7第7页/共57页8第8页/共57页9第9页/共57页第二节第二节 线性规划线性规划与非线性规划与非线性规划线性规划问题与非线性规划问题Excel中求解规划问题的方法和步骤10第10页/共57页一一.线性规划线性规划问题和非线性规划问题问题和非线性规划问题线性规划就是研究在一组线性约束条件下，求解一个线性
4、函数的极大化或极小化的问题线性规划的形式为：11第11页/共57页12线性规划问题的三要素线性规划问题的三要素 决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。有的目标要实现极大，有的则要求极小。目标函数是决策变量的线性函数。第12页/共57页13线性规划的定义线性规划的定义对于求取一组对于求取一组对于求取一组对于求取一组变量变量变量变量x xj j
5、 (j=1,2,.,nj=1,2,.,n)，使之既满足，使之既满足，使之既满足，使之既满足线线线线性约束性约束性约束性约束条件，又使具有条件，又使具有条件，又使具有条件，又使具有线性表达式线性表达式线性表达式线性表达式的的的的目标函数目标函数目标函数目标函数取得取得取得取得极值极值极值极值（极大值或极小值）的一类最优化问（极大值或极小值）的一类最优化问（极大值或极小值）的一类最优化问（极大值或极小值）的一类最优化问题称为题称为题称为题称为线性规划问题线性规划问题线性规划问题线性规划问题，简称，简称，简称，简称线性规划线性规划线性规划线性规划。第13页/共57页14某厂生产两种产品，需要三种资源
6、，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120例例例例.生产计划问题生产计划问题生产计划问题生产计划问题第14页/共57页15问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1 kg；B产品x2 kg2、确定目标函数：max Z=70X1+120X23、确定约束条件：劳动力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20第15页/共57页16用图示的方法来求解线性规划问题。一个二维的线性
7、规划问题(指只有两个决策变量)，可以在平面图上求解，三维的线性规划则要在立体图上求解，而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤LP问题的图解法问题的图解法(1)可行域的确定可行解(2)最优解第16页/共57页171.可行域的确定可行域的确定例如数学模型为例如数学模型为 max Z=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有
8、都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。LP问题的图解法问题的图解法第17页/共57页182.最优解的确定最优解的确定Z=30Z=42Z=15目标函数 Z=3x1+5 x2 代表以Z为参数的一族平行线。x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数
9、最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解LP问题的图解法问题的图解法?第18页/共57页19由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。目标函数最优值（如果存在）一定在可行域的边界达到，而不可能在其内部。二、说明二、说明LP问题的图解法问题的图解法第19页/共57页20例:求解下列线性规划问题 Max Z=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20LP问题的图解法问题的图解法第20页/共57页21X1X1=1
10、X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAX Z=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20X2 0X1 0第21页/共57页22LP问题的图解法问题的图解法唯一最优解唯一最优解：只有一个最优点。多多重重最最优优解解：无穷多个最优解。若在两个相相邻邻顶顶点点同时得到最优解，则它们连线上的每一点都是最优解。无无界界解解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）。无可行解无可行解：若约束条件相互矛盾，则可行域为空集。二、解的可能性二、解的可能性第22页/共57页23X1X1=1X1=6X2=4X2X
11、1+2X2=10ABCDE4X1-3X2=0 MAXZ=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20唯唯一一的的最最优优解解X1 0X2 0第23页/共57页24X1X1=1X1=6X2=4X2X1+2X2=10ABCDE MAXZ=2X1+4X2 S.T.X1+2X210 X16 X24 X11 X1,X202X1+4X2=存在无穷多解存在无穷多解 MAXZ=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20X1 0X2 0第24页/共57页25X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0 MAXZ=4
12、X1-3X2 S.T.X1+2X20 X16 X24 X11 X1,X20可行域无界可行域无界 MAXZ=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20X1 0X2 0第25页/共57页26X1X1=1X2X1+2X2=104X1-3X2=0 MAXZ=4X1-3X2 S.T.X1+2X2 10 X11 X1,X20 MAXZ=4X1-3X2 S.T.X1+2X210 X16 X24 X11 X1,X20可行域无界可行域无界X1 0X2 0第26页/共57页如果决策变量在目标函数或者约束条件中出现了非线性的形式，最优化问题就是非线性规划问题。线性规划问题是最简单
13、的规划问题，也是最常用的求解最优化问题的方法，对其进行的理论研究较早，也较成熟，可以找到全局最优解。非线性规划问题形式多样，求解复杂，不能保证找到全局最优解，大部分情况下只能找到局部最优解线性规划问题是非线性规划问题的一种特例。27第27页/共57页二二.Excel.Excel中求解规划中求解规划问题的方法和问题的方法和步骤步骤第一步，选择“规划求解”工具；第二步，根据对规划问题的分析，在“设置目标”中定义目标值所在的单元格及它的取值，在“通过更改可变单元格”中设置决策变量所在的单元格；第三步，在“遵守约束”中添加约束条件；第四步，选择求解方法，“单纯线性”或“非线性GRG”；第五步，在正确地
14、完成了对需要求解问题的相关参数的设置后，单击“求解”按钮，规划求解工具就开始求解。28第28页/共57页注意事项绝对引用与相对引用的切换：F4或者Fn+F4以矩阵和向量的形式表示；向量或者矩阵的运算(一般是求和用sum函数)最后要使用ctl+alt+shift，在公式外面加大括号；29第29页/共57页三三.线性规划线性规划问题问题【例8.1】某化工厂用A、B、C三种原料生产P1、P2两种化工产品。每生产1升P1产品需要A、B、C的数量为3，4，2公斤，而生产1升P2的数量为4，2，1公斤。P1、P2的单位利润分别为5元和4元，工厂现有A、B、C三种原料的数量分别为14，8，6公斤。试用规划求
15、解工具帮助该工厂安排生产P1、P2的产量，使其能获利最大。30第30页/共57页求解结果：31三三.线性规划线性规划问题问题第31页/共57页【例8.2】某公司生产两种产品，两种产品各生产一个单位需要工时3和7，用电量4千瓦和5千瓦，需要原材料9公斤和4公斤。公司可提供的工时为300，可提供的用电量为250千瓦，可提供的原材料为420公斤。两种产品的单价p与销量q之间存在负的线性关系，分别为p1=3000-50q1,p2=3250-80q2。工时、用电量和原材料的单位成本分别为10、12和50，总固定成本是10000。该公司怎样安排两种产品的产量，能获得最大利润？32四四.非非线性规划线性规划
16、问题问题第32页/共57页求解结果：需 要 指 出：对 于 非 线 性 规 划 问 题，其 解 可 能 不 唯 一，即 可 能 存 在 多 解，也 可 能 无 解。33四四.非非线性规划线性规划问题问题第33页/共57页课堂练习34用图解法求线性规划问题第34页/共57页35运输问题是线性规划问题的特例。产地产地：货物发出的地点。销地销地：货物接收的地点。产量产量：各产地的可供货量。销量销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。第三节第三节 运输运输问题问题第35页/共57页36 某饮料公司在国内有三个生产厂，分布在城市A1、A2、A3,其一级承
17、销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地销地产地产地B1 B2 B3 B4产量产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量销量 2 3 1 4例例例例1.1.运输问题运输问题运输问题运输问题运输问题运输问题第36页/共57页37(1)(1)决策变量决策变量。决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij，(2)(2)目标函数目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21
18、+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件。产量之和等于销量之和,故要满足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4供应平衡条件供应平衡条件非负性约束非负性约束 xij0(i=1,2,3；j=1,2,3,4)第37页/共57页38min Z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7
19、x34 综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij0(i=1,2,3；j=1,2,3,4)s.t.subject to第38页/共57页在实际问题建模时，还会出现如下一些变化：有时目标函数求最大，如求利润最大或营业额 最大等；当某些运输线路上的能力有限制时，模型中可 直接加入（等式或不等式）约束；产销不平衡的情况。39第39页/共57页40产销平衡运输问题的三种
20、类型 第40页/共57页41产大于销第41页/共57页42产小于销第42页/共57页【例8.3】某公司生产一种高档品牌葡萄酒，在全国有3个工厂（工厂1、工厂2和工厂3），各工厂的日最大生产量分别为120箱、200箱和100箱。该公司每天要向4个城市（城市A、城市B、城市C和城市D）供货，这四个城市的日需要量分别为80箱、150箱、100箱和70箱。每箱货物从工厂运到各城市的运费如下表所示：该公司怎样安排生产和运输量，能使总运费最小？要求各工厂的实际供给量不能超过其最大产量，同时又要满足各城市的需要量。43第43页/共57页求解结果：在线性规划中，当决策变量的取值 只能为整数时，把这类问题称之为
21、 整数规划。本题由于运输时不能拆 箱，因而是一个整数规划问题。44第44页/共57页45运输模型的解法运输模型的解法产销不平衡的运输问题需化成产销平衡问题再求解。产大于销：虚设一个销地 Bk(多于物资在产地存储)，其运价为0，销量(存储量)为产销量之差 bk=ai-bj。产小于销：虚设一个产地 Al(不足物资的脱销量)，其运价为0，产量(脱销量)为销产量之差 ak=bj-ai。第45页/共57页46增加一个销地产大于销产大于销(供大于求供大于求)销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销
22、量18121650-46B4000450465050产销不平衡问题产销不平衡问题第46页/共57页47产销不平衡问题增加一个产地产小于销产小于销(供不应求供不应求)销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523-22000122232323第47页/共57页48自来水分配问题：水价90元/kt，管理费45元/kt，引水费如下表：一、短缺资源的分配问题一、短缺资源的分配问题供区供区水库水库甲甲乙乙丙丙丁丁供水量供水量kt/dA1613221750B1413191560C192023-50最低需求最低需求kt
23、/d3070010最高需求最高需求kt/d507030不限不限如何分配供水量，保障各区最低需求，获利最大？运输问题的应用第48页/共57页49 利润=收入-成本，收入最大，成本最小，则利润最大。收入：每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。每天总收入是常数，与水量分配无关，可以不与考虑。成本：各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到最小，总成本则最低。如何分配水量，既满足最低需求，又使总的引水费最低？最大需求量：供水总量=50
24、+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个产小于销的不平衡问题。分析分析运输问题的应用运输问题的应用第49页/共57页50产小于销的运输问题化为平衡问题，虚设水库D，供水量50。各区的最低需求为基本需求，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。各区的最大需求与最低需求的差为额外需求，可以由虚设水库D供水，故单位引水费（运费）为0。丁地不能由C水库供水，乙优先由B供应。供区供区水库水库供水量供水量A50B60C50甲甲1甲甲2乙乙丙丙
25、丁丁1丁丁21616132217171414019151519192023MM销量销量302070301050DM0M0M050运输问题的应用第50页/共57页51用表上作业法求得最优方案供区供区水库水库甲甲1甲甲2乙乙丙丙丁丁1丁丁2供水量供水量A5050B20103060C3020050D302050销量销量302070301050最优分配方案：水库最优分配方案：水库A向乙区供水向乙区供水50，水库，水库B分别向乙区、丁区供水分别向乙区、丁区供水20和和40，水库，水库C向甲区供水向甲区供水50，不给丙区供水。，不给丙区供水。最小引水费：最小引水费：13 50+13 20+15(10+30
26、)+19(30+20)=2460 引水引水管理费：管理费：45(50+60+50)=7200 总成本：总成本：2460+7200=9600 总收入：总收入：90(50+60+50)=14400 最大获利：最大获利：14400-9600=4740运输问题的应用第51页/共57页52例1 某企业和用户签订了设备交货合同，相关数据如下表。若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消耗费用最低？二、生产和储存问题二、生产和储存问题季度季度工厂生产能力工厂生产能力（台）（台）季度末交货量季度末交货量（台）（台）每台设备生
27、产成本每台设备生产成本（万元）（万元）1251512.02352011.03302511.54202012.5运输问题的应用第52页/共57页53解：设 xij为第 i 季度生产的第 j 季度交货的设备数目，那么应满足：交货：x11 =15 生产：x11+x12+x13+x14 25 x12+x22 =20 x22+x23+x24 35 x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44 =20 x44 20 把第 i 季度生产的设备数目看作第 i 个生产厂的产量；把第 j 季度交货的设备数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Min f=12 x11+12.1 x12+12.2 x13+12.3 x14+11.1 x22+11.1 x23+11.2 x24 +11.5 x33+11.6 x34 +12.5 x44 第一季度第二季度第三季度第四季度D产量第一季度12.012.112.212.3025第二季度M11.011.111.2035第三季度MM11.511.6030第四季度MMM12.5010销量1520252030110运输问题的应用第53页/共57页例254运筹学教材课后题第54页/共57页55第55页/共57页练习题56第56页/共57页57感谢您的观看！第57页/共57页