第六章-最优化决策模型.

最优化问题的定义、分类和数学模型，规划求解工具；目标函数和约束条件与决策变量之间都是线性关系的规划问题，产品混合线性规划问题的求解；目标函数或者约束条件与决策变量之间不是线性关系的规划问题，产品混合非线性规划问题的求解；运输、选址等常见规划问题的求解。多目标规划问题的概念和求解；规划求解报告的生成与分析。2最优化问题的概念最优化问题分类最优化问题的数学模型最优化问题的求解方法3最优化问题就是在给定条件下寻找最佳方案的问题；最佳的含义有各种各样：成本最小、收益最大、利润最多、距离最短、时间最少、空间最小等，即在资源给定时寻找最好的目标，或在目标确定下使用最少的资源。4根据有无约束条件无约束条件的最优化问题，在资源无限的情况下求解最佳目标；有约束条件的最优化问题，在资源限定的情况下求解最佳目标；实际问题一般都是有资源限制的，所以大部分最优化问题都是有约束条件的最优化问题。根据决策变量在目标函数与约束条件中出现的形式线性规划问题非线性规划问题二次规划问题根据决策变量是否要求取整数整数规划问题0-1规划问题任意规划问题5最优化问题可表示为如下的数学形式：6nxxxfyMinMax,,,:/210,,,:211nxxxsSt0,,,212nxxxs0,,,21nmxxxs……方法一：公式法分析问题，推导出计算最优解的公式。方法二：用规划求解工具求解启动规划求解工具，在规划求解参数对话框中设置目标单元格（目标变量）和可变单元格（决策变量），设置目标单元格的目标值（最大、最小或者某一特定值），添加约束条件，另外也可以设置一些附加参数。按“求解”按钮，规划求解工具就根据参数设置寻求最优解。78910线性规划问题与非线性规划问题Excel中求解规划问题的方法和步骤产品混合线性规划问题产品混合非线性规划问题11线性规划就是研究在一组线性约束条件下，求解一个线性函数的极大化或极小化的问题线性规划的标准形式为：120),...,,(:211nxxxsSt),...,,(:/21nxxxfyMinMax0),...,,(212nxxxs0),...,,(21nmxxxs……13线性规划问题的三要素•决策变量–决策问题待定的量值称为决策变量。–决策变量的取值要求非负。•约束条件–任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。–约束条件是决策方案可行的保障。–LP的约束条件，都是决策变量的线性函数。•目标函数–衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。–有的目标要实现极大，有的则要求极小。–目标函数是决策变量的线性函数。14线性规划的定义对于求取一组变量xj(j=1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极值（极大值或极小值）的一类最优化问题称为线性规划问题，简称线性规划。15•某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120例.生产计划问题16•问题：如何安排生产计划，使得获利最多？•步骤：1、确定决策变量：设生产A产品x1kg；B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：劳动力约束9X1+4X2≤360设备约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥017•用图示的方法来求解线性规划问题。•一个二维的线性规划问题(指只有两个决策变量)，可以在平面图上求解，三维的线性规划则要在立体图上求解，而维数再高以后就不能图示了。一、图解法的基本步骤LP问题的图解法(1)可行域的确定可行解(2)最优解181.可行域的确定•例如数学模型为maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.x1=82x2=123x1+4x2=36x1x248123690ABC(4,6)D•五边形OABCD内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。•满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。LP问题的图解法192.最优解的确定Z=30Z=42Z=15•目标函数Z=3x1+5x2代表以Z为参数的一族平行线。x1=82x2=123x1+4x2=36x1x248123690ABC(4,6)D•等值线：位于同一直线上的点的目标函数值相同。•最优解：可行解中使目标函数最优(极大或极小)的解LP问题的图解法?20•由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。•可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。•目标函数最优值（如果存在）一定在可行域的边界达到，而不可能在其内部。二、说明LP问题的图解法21•例:求解下列线性规划问题MaxZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20LP问题的图解法22X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20X20X1023LP问题的图解法•唯一最优解：只有一个最优点。•多重最优解：无穷多个最优解。若在两个相邻顶点同时得到最优解，则它们连线上的每一点都是最优解。•无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）。•无可行解：若约束条件相互矛盾，则可行域为空集。二、解的可能性24X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0MAXZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20唯一的最优解X10X2025X1X1=1X1=6X2=4X2X1+2X2=10ABCDEMAXZ=2X1+4X2S.T.X1+2X210X16X24X11X1,X202X1+4X2=Ω存在无穷多解MAXZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20X10X2026X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0MAXZ=4X1-3X2S.T.X1+2X20X16X24X11X1,X20可行域无界MAXZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20X10X2027X1X1=1X2X1+2X2=104X1-3X2=0MAXZ=4X1-3X2S.T.X1+2X210X11X1,X20MAXZ=4X1-3X2S.T.X1+2X210X16X24X11X1,X20可行域无界X10X20如果决策变量在目标函数或者约束条件中出现了非线性的形式，最优化问题就是非线性规划问题。线性规划问题是最简单的规划问题，也是最常用的求解最优化问题的方法，对其进行的理论研究较早，也较成熟，可以找到全局最优解。非线性规划问题形式多样，求解复杂，不能保证找到全局最优解，大部分情况下只能找到局部最优解线性规划问题是非线性规划问题的一种特例。28第一步，选择“规划求解”工具；第二步，根据对规划问题的分析，在“设置目标”中定义目标值所在的单元格及它的取值，在“通过更改可变单元格”中设置决策变量所在的单元格；第三步，在“遵守约束”中添加约束条件；第四步，选择求解方法，“单纯线性”或“非线性GRG”；第五步，在正确地完成了对需要求解问题的相关参数的设置后，单击“求解”按钮，规划求解工具就开始求解。29绝对引用与相对引用的切换：F4或者Fn+F4以矩阵和向量的形式表示；向量或者矩阵的运算(一般是求和用sum函数)最后要使用ctl+alt+shift，在公式外面加大括号；30【例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公斤。试用规划求解工具帮助该工厂安排生产P1、P2的产量，使其能获利最大。31求解结果：32产品P1P2实际量供给量原料A341414原料B4288原料C2146单位利润54产量0.43.2总利润14.814.82TRUETRUE100【例8.2】某公司生产两种产品，两种产品各生产一个单位需要工时3和7，用电量4千瓦和5千瓦，需要原材料9公斤和4公斤。公司可提供的工时为300，可提供的用电量为250千瓦，可提供的原材料为420公斤。两种产品的单价p与销量q之间存在负的线性关系，分别为p1=3000-50q1,p2=3250-80q2。工时、用电量和原材料的单位成本分别为10、12和50，总固定成本是10000。该公司怎样安排两种产品的产量，能获得最大利润？33求解结果：需要指出：对于非线性规划问题，其解可能不唯一，即可能存在多解，也可能无解。34产品1产品2需要量可提供量单位成本工时37201.9130010用电量45190.1325012原材料94295.4842050产量24.7218.25a30003250b-50-80单价17641790收益43606.0832667.5单位变动成本528330变动成本13052.166022.5总固定成本10000总利润47198.9247198.922TRUETRUE100运输问题选址问题3536运输问题是线性规划问题的特例。•产地：货物发出的地点。•销地：货物接收的地点。•产量：各产地的可供货量。•销量：各销地的需求数量。•运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。一.运输问题37某饮料公司在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地产地B1B2B3B4产量A1A2A3632575843297523销量2314例1.运输问题一.运输问题38(1)决策变量。决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(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供应平衡条件非负性约束xij≥0(i=1,2,3；j=1,2,3,4)39minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34•综上所述，该问题的数学模型表示为x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij≥0(i=1,2,3；j=1,2,3,4)s.t.subjectto•在实际问题建模时，还会出现如下一些变化：①有时目标函数求最大，如求利润最大或营业额最大等；②当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；③产销不平衡的情况。4041•产销平衡运输问题的三种类型minjjiba110,...,2,1,