第六章-最优化决策模型

1、最优化问题的定义、分类和数学模型，规划求解最优化问题的定义、分类和数学模型，规划求解工工具；具；目标函数和约束条件与决策变量之间都是线性关系目标函数和约束条件与决策变量之间都是线性关系的规划问题，产品混合线性规划问题的求解；的规划问题，产品混合线性规划问题的求解；目标函数或者约束条件与决策变量之间不是线性关目标函数或者约束条件与决策变量之间不是线性关系的规划问题，产品混合非线性规划问题的求解；系的规划问题，产品混合非线性规划问题的求解；运输、运输、选址等选址等常见规划问题的求解。常见规划问题的求解。多目标规划问题的概念和求解；多目标规划问题的概念和求解；规划求解报告的生成与规划求解报告的生成与

2、分析分析。2最优化问题的最优化问题的概念概念最优化问题最优化问题分类分类最优化问题的最优化问题的数学模型数学模型最优化问题的求解方法最优化问题的求解方法3最优化问题就是在给定条件下寻找最佳方案的最优化问题就是在给定条件下寻找最佳方案的问题问题；最佳的含义有各种各样：成本最小、收益最大、最佳的含义有各种各样：成本最小、收益最大、利润最多、距离最短、时间最少、空间最小等，利润最多、距离最短、时间最少、空间最小等，即在资源给定时寻找最好的目标，或在目标确即在资源给定时寻找最好的目标，或在目标确定下使用最少的资源。定下使用最少的资源。4根据根据有无约束条件有无约束条件 无约束条件的最优化无约束条件的最

3、优化问题，问题，在在资源无限的情况下求解最佳目标资源无限的情况下求解最佳目标；有约束条件的最优化有约束条件的最优化问题，问题，在资源限定的情况下求解最佳目标在资源限定的情况下求解最佳目标；实际问题一般都是有资源限制的，所以大部分最优化问题都是实际问题一般都是有资源限制的，所以大部分最优化问题都是有约束条件的最优化问题有约束条件的最优化问题。 根据决策变量在目标函数与约束条件中出现的形式根据决策变量在目标函数与约束条件中出现的形式 线性规划问题线性规划问题 非线性规划问题非线性规划问题 l二次规划问题二次规划问题 根据决策变量是否要求取整数根据决策变量是否要求取整数 整数规划问题整数规划问题 l

4、0-10-1规划问题规划问题 任意规划任意规划问题问题5最优化最优化问题可表示为如下的数学形式问题可表示为如下的数学形式：6nxxxfyMinMax,:/210,:211nxxxsSt0,212nxxxs0,21nmxxxs方法方法一：公式法一：公式法分析问题，推导出计算最优解的公式。分析问题，推导出计算最优解的公式。方法二：用规划求解工具求解方法二：用规划求解工具求解启动规划求解工具，在规划求解参数对话框中设启动规划求解工具，在规划求解参数对话框中设置目标单元格（目标变量）和可变单元格（决策置目标单元格（目标变量）和可变单元格（决策变量），设置目标单元格的目标值（最大、最小变量），设置目标单

5、元格的目标值（最大、最小或者某一特定值），添加约束条件，另外也可以或者某一特定值），添加约束条件，另外也可以设置一些附加参数。按设置一些附加参数。按“求解求解”按钮，规划求解按钮，规划求解工具就根据参数设置寻求最优解工具就根据参数设置寻求最优解。78910线性规划问题线性规划问题与非线性规划问题与非线性规划问题Excel Excel 中中求解规划求解规划问题的方法和问题的方法和步骤步骤产品产品混合线性规划问题混合线性规划问题产品产品混合非线性规划混合非线性规划问题问题11线性规划就是研究在一组线性约束条件下，线性规划就是研究在一组线性约束条件下，求解一个线性函数的极大化或极小化的求解一个线性函

6、数的极大化或极小化的问题问题线性规划的标准形式线性规划的标准形式为：为：120),.,(:211nxxxsSt),.,(:/21nxxxfyMinMax0),.,(212nxxxs0),.,(21nmxxxs13线性规划问题的三要素线性规划问题的三要素 决策变量决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负非负。 约束条件约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数线性函数。 目标函数目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、

7、成本最低。 有的目标要实现极大极大，有的则要求极小极小。 目标函数是决策变量的线性函数线性函数。14线性规划的定义线性规划的定义15 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg7012016 问题：如何安排生产计划，使得获利最多？ 步骤：1、确定决策变量：设生产A产品x1 kg；B产品x2 kg2、确定目标函数：max Z=70X1+120X23、确定约束条件：劳动力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300

8、非负性约束X10 X2017 用图示的方法来求解线性规划问题。 一个二维的线性规划问题(指只有两个决策变量)，可以在平面图上求解，三维的线性规划则要在立体图上求解，而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤LP问题的图解法问题的图解法(1) 可行域的确定可行解(2) 最优解181. 可行域的确定可行域的确定 例如数学模型为例如数学模型为 max Z= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.x1 =82x2 =123x1 +4 x2 =36x1x24812369 五边形五边形OABCD内内(含边界含边界)的任意

9、一点的任意一点 (x1，x2) 都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解 。 满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。LP问题的图解法问题的图解法192. 最优解的确定最优解的确定Z=30Z=42Z=15 目标函数目标函数 Z= 3x1 +5 x2 代表以代表以Z为参数的一族为参数的一族平行线平行线。x1 =82x2 =123x1 +4 x2 =36x1x24812369 等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数

10、值相同。 最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解LP问题的图解法问题的图解法?20 由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。 目标函数最优值（如果存在）一定在可行域的边界达到，而不可能在其内部。二、说明二、说明LP问题的图解法问题的图解法21 例: 求解下列线性规划问题 Max Z=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20LP问题的图解法问题的图解法22X1X1=1X1=

11、6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAX Z=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X2 0X1 023LP问题的图解法问题的图解法 唯一最优解唯一最优解：只有一个最优点。 多重最优解多重最优解：无穷多个最优解。若在两个相邻顶点相邻顶点同时得到最优解，则它们连线上的每一点都是最优解。 无界解无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）。 无可行解无可行解：若约束条件相互矛盾，则可行域为空集。二、解的可能性二、解的可能性24X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1

12、-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20唯一的最优解唯一的最优解X1 0X2 025X1X1=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 026X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X20 X16 X24 X11

13、 X1,X20可行域无界可行域无界 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X1 0X2 027X1X1=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如果决策变量在目标函数或者约束条件中出现如果决策变量在目标函数或者约束条件中出现了了非线性非线性的的形式形式，最优化问题就是非线性规划问题。最优化问题就是非线性规划问题。线性规划线性规划问题是最简

14、单的规划问题，也是最常用问题是最简单的规划问题，也是最常用的求解最优化问题的方法，对其进行的理论研究的求解最优化问题的方法，对其进行的理论研究较早，也较成熟，可以找到全局最优解较早，也较成熟，可以找到全局最优解。非线性规划非线性规划问题形式多样，求解复杂，不能保证问题形式多样，求解复杂，不能保证找到全局最优解，大部分情况下只能找到局部最找到全局最优解，大部分情况下只能找到局部最优优解解线性规划线性规划问题是非线性规划问题的一种特例。问题是非线性规划问题的一种特例。28第一第一步，步，选择选择“规划求解规划求解”工具工具；第二步，根据第二步，根据对规划对规划问题的分析，在问题的分析，在“设置目标

15、设置目标” ” 中中定义目标值所在的单元格及它的取值，在定义目标值所在的单元格及它的取值，在“通过通过更改可变单元格更改可变单元格”中设置决策变量所在的单元格；中设置决策变量所在的单元格；第三步，在第三步，在“遵守约束遵守约束”中中添加添加约束条件约束条件；第四第四步，选择求解方法，步，选择求解方法，“单纯线性单纯线性”或或“非线性非线性GRGGRG”；第第五五步步，在正确地完成了对需要求解问题的相关参，在正确地完成了对需要求解问题的相关参数的设置后，单击数的设置后，单击“求解求解”按钮，规划求解工具就按钮，规划求解工具就开始求解开始求解。29绝对引用与相对引用的切换：绝对引用与相对引用的切换

16、：F4F4或者或者Fn+F4Fn+F4以矩阵和向量的形式表示；以矩阵和向量的形式表示；向量或者矩阵的运算向量或者矩阵的运算( (一般是求和用一般是求和用sumsum函数函数) )最后要使用最后要使用ctl+alt+shiftctl+alt+shift，在公式外面加，在公式外面加大括号；大括号；30【例例8.18.1】某化工厂用某化工厂用A A、B B、C C三种原料生产三种原料生产P1P1、P2P2两种化工产品。每生产两种化工产品。每生产1 1升升P1P1产品需要产品需要A A、B B、C C的数量为的数量为3 3，4 4，2 2公斤，而生产公斤，而生产1 1升升P2P2的数量为的数量为4 4

17、，2 2，1 1公斤。公斤。P1P1、P2P2的单位利润分别为的单位利润分别为5 5元和元和4 4元，元，工厂现有工厂现有A A、B B、C C三种原料的数量分别为三种原料的数量分别为1414，8 8，6 6公斤。试用规划求解工具帮助该工厂安排生产公斤。试用规划求解工具帮助该工厂安排生产P1P1、P2P2的产量，使其能获利最大。的产量，使其能获利最大。31求解结果求解结果：32【例例8.28.2】某公司生产两种产品，两种产品各生产某公司生产两种产品，两种产品各生产一个单位需要工时一个单位需要工时3 3和和7 7，用电量，用电量4 4千瓦和千瓦和5 5千瓦，千瓦，需要原材料需要原材料9 9公斤和

18、公斤和4 4公斤。公司可提供的工时为公斤。公司可提供的工时为300300，可提供的用电量为，可提供的用电量为250250千瓦，可提供的原材千瓦，可提供的原材料为料为420420公斤。两种产品的单价公斤。两种产品的单价p p与销量与销量q q之间存在之间存在负的线性关系，分别为负的线性关系，分别为p1=3000 - 50q1, p2 = p1=3000 - 50q1, p2 = 3250- 80q23250- 80q2。工时、用电量和原材料的单位成本。工时、用电量和原材料的单位成本分别为分别为1010、1212和和5050，总固定成本是，总固定成本是1000010000。该公司。该公司怎样安排两

19、种产品的产量，能获得最大利润？怎样安排两种产品的产量，能获得最大利润？33求解结果求解结果：需需要要指出指出：对于非线性规划问题，对于非线性规划问题， 其其解可能不唯一，即可能存在多解可能不唯一，即可能存在多解解， 也可能无解。也可能无解。34运输问题运输问题选址选址问题问题3536运输问题是线性规划问题的特例。：货物发出的地点。：货物接收的地点。：各产地的可供货量。：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。一.运输问题37 某饮料公司在国内有三个生产厂，分布在城市某饮料公司在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有其一级承销商

20、有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一.运输问题38。 决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij，。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7

21、x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 。产量之和等于销量之和,故要满足：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) 39min Z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 综上所述，该问题的

22、数学模型表示为综上所述，该问题的数学模型表示为 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 在实际问题建模时，还会出现如下一些变化： 有时目标函数求最大，如求利润最大或营业额 最大等； 当某些运输线路上的能力有限制时，模型中可 直接加入（等式或不等式）约束； 产销不平衡的情况。4041 产销平衡运输问题的三种类型 minjjiba110,.,2 , 1,

23、.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ42 产大于销minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ43 产小于销minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ44 产销不平衡的运输问题需化成产销平衡问题再求解。产销不平衡的运输问题需化成产销平衡问题再求解。 产大于销：产大于销： 虚设一个销地虚设一个销地 Bk (多于物资在产地存储多于物资在产地存储)，其运价为，其运

24、价为0， 销量销量(存储量存储量)为产销量之差为产销量之差 bk = ai- bj。 产小于销：产小于销： 虚设一个产地虚设一个产地 Al (不足物资的脱销量不足物资的脱销量)，其运价为，其运价为0，产量，产量(脱销量脱销量)为销产量之差为销产量之差 ak = bj - ai 。45增加一个销地增加一个销地产大于销产大于销( (供大于求供大于求) )销地产地B1B2B3产量A159215A231718A362817销量181216销地产地B1B2B3产量A159215A231718A362817销量18121650-46B400045046505046 增加一个产地增加一个产地产小于销产小于销

25、( (供不应求供不应求) )销地产地B1B2B3产量A141210A234312销量8105销地产地B1B2B3产量A141210A234312A3销量810523-22000122232323【例例8.38.3】某公司生产一种高档品牌葡萄酒，在全国有】某公司生产一种高档品牌葡萄酒，在全国有3 3个个工厂（工厂工厂（工厂1 1、工厂、工厂2 2和工厂和工厂3 3），各工厂的日最大生产量分），各工厂的日最大生产量分别为别为120120箱、箱、200200箱和箱和100100箱。该公司每天要向箱。该公司每天要向4 4个城市（城个城市（城市市A A、城市、城市B B、城市、城市C C和城市和城市D

26、D）供货，这四个城市的日需要）供货，这四个城市的日需要量分别为量分别为8080箱、箱、150150箱、箱、100100箱和箱和7070箱。每箱货物从工厂运箱。每箱货物从工厂运到各城市的运费如下表所示到各城市的运费如下表所示：该公司怎样安排生产和运输该公司怎样安排生产和运输量，能使总运费最小？要求各工厂的实际供给量不能超过量，能使总运费最小？要求各工厂的实际供给量不能超过其最大产量，同时又要满足各城市的其最大产量，同时又要满足各城市的需要量需要量。47求解结果求解结果：在在线性规划中，当决策变量的取值线性规划中，当决策变量的取值 只能为只能为整数时，把这类问题整数时，把这类问题称之为称之为 整数

27、规划整数规划。本题由于运输时不能。本题由于运输时不能拆拆 箱箱，因而是一个整数规划问题。，因而是一个整数规划问题。48【例例8.48.4】一家移动通信公司准备在四个候选的位置】一家移动通信公司准备在四个候选的位置中挑选几个来建造信号发射基站，以便覆盖一个城中挑选几个来建造信号发射基站，以便覆盖一个城市中的四个地区。这四个位置对于四个区的覆盖与市中的四个地区。这四个位置对于四个区的覆盖与修建费用如下表所示（在一个位置所在列与一个地修建费用如下表所示（在一个位置所在列与一个地区所在行的交叉点处有数字区所在行的交叉点处有数字“1 1”表明在该位置建造表明在该位置建造信号发射基站时信号可以覆盖对应的地

28、区）：信号发射基站时信号可以覆盖对应的地区）：要求：构造一个线性规划要求：构造一个线性规划模型，模型，用规划求解工具确用规划求解工具确定一种基站建设方案，使得既能定一种基站建设方案，使得既能将四将四个地区个地区都覆盖都覆盖，又又使建站总费用达到极小。使建站总费用达到极小。49求解结果求解结果：本本题目中决策变量的取值只有题目中决策变量的取值只有0 0 和和1 1，在线性规划中把这类，在线性规划中把这类取值取值 为为0 0或或1 1的问题的问题称之为称之为0-10-1规划。规划。50多目标规划问题多目标规划问题概述概述多目标规划问题的多目标规划问题的求解方法求解方法多目标规划问题的多目标规划问题

29、的求解求解举例举例51只有一个目标函数只有一个目标函数的最优化问题的最优化问题称为称为单单目标规划目标规划问题问题。在经济管理中有时会面临多目标决策问题，例如在经济管理中有时会面临多目标决策问题，例如在研究产品混合问题时在研究产品混合问题时，既要既要保证保证获利最大的前获利最大的前提下提下能否能否，又要，又要使使原料的消耗最小。原料的消耗最小。多目标规划问题要比单目标规划问题多目标规划问题要比单目标规划问题复杂复杂。52分层分层序列法：将各目标按其重要性排序，先求出序列法：将各目标按其重要性排序，先求出第一个最重要目标的最优解，然后在保证前一目第一个最重要目标的最优解，然后在保证前一目标最优解

30、不变的前提下，按序依次求下一目标的标最优解不变的前提下，按序依次求下一目标的最优解，直至求出最后一个目标的最优解。最优解，直至求出最后一个目标的最优解。化多为少化多为少法：将多目标问题转化为单目标问题来法：将多目标问题转化为单目标问题来求解，最常用的线性加权法。求解，最常用的线性加权法。多多属性效用法：各目标都用表示效用程度大小的属性效用法：各目标都用表示效用程度大小的效用函数表示，通过效用函数构成多目标的综合效用函数表示，通过效用函数构成多目标的综合效用函数，以此来评价各个可行方案的优劣效用函数，以此来评价各个可行方案的优劣。53【例例8.88.8】某公司生产和销售两种产品，两种产品某公司生

31、产和销售两种产品，两种产品各生产一个单位需要工时各生产一个单位需要工时3 3和和7 7，用电量，用电量4 4千瓦和千瓦和5 5千瓦，需要原材料千瓦，需要原材料9 9公斤和公斤和4 4公斤。公司可提供的公斤。公司可提供的工时为工时为300300，可提供的用电量为，可提供的用电量为250250千瓦，可提供千瓦，可提供的原材料为的原材料为420420公斤。两种产品的单位利润分别为公斤。两种产品的单位利润分别为2525元和元和3030元。假设两种产品各生产元。假设两种产品各生产1 1个单位，试在个单位，试在ExcelExcel中建立产品组合线性规划模型，用规划求解中建立产品组合线性规划模型，用规划求解

32、工具求解两种产品的最优生产量，使总利润最大，工具求解两种产品的最优生产量，使总利润最大，总工时最少。总工时最少。54使利润最大的第一次规划的结果使利润最大的第一次规划的结果：55在保证利润最大的前提下，使总工时最小的第二次规划的结果：在保证利润最大的前提下，使总工时最小的第二次规划的结果：56规划求解报告的规划求解报告的生成生成规划求解报告的分析规划求解报告的分析57ExcelExcel的规划求解工具在求解的过程中，还能生成的规划求解工具在求解的过程中，还能生成运算结果报告、敏感性报告和极限值报告，这三运算结果报告、敏感性报告和极限值报告，这三张报告反映了在求解过程中目标变量、决策变量张报告反映了在求解过程中目标变量、决策变量的变化情况，约束条件的满足条件情况等，还提的变化情况，约束条件的满足条件情况等，还提供了对决