线性规划和灰色模型介绍课件

1、1线性规划模型和灰色模型介绍1线性规划模型和灰色模型介绍1.线性规划问题及其数学模型问题的提出：在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等 最佳：有一个标准或目标，使利润达到最大或成本达到最小。 有限资源的合理配置有两类问题：如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。 2一、线性规划模型1.线性规划问题及其数学模型2一、线性规划模型线性规划模型的基本假设1.线性 目标函数和约束条件2.可分性 活动对资源的可分性3.可加性 活动所

2、耗资源的可加性，资源总需要量为多种活动所需资源数量的总和。4.明确性 目标的明确性5.单一性 期望值的单一性6.独立性 变量是独立的表示各种作业对资源都是互竟关系，没有互助关系7.非负性线性规划模型的基本假设1.线性 目标函数和约束条件例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗 每周资源总量 甲乙维生素（公斤） 3020160设备（台班） 5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排

3、两种药品的产量才能使每周获得的利润最大？4例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维 定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。 数学模型为 s.t. （subject to) (such that) 称之为上述问题的数学模型。每吨产品的消耗 每周资源总量 甲乙维生素（公斤） 3020160设备（台班） 5115单位利润（万元） 55 定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的2.线性规划的一般数学模型 线性规划模型的特征：（1）用一组决策变量x1，x2，xn表示某一方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标

4、函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题62.线性规划的一般数学模型6 线性规划的模型的一般形式: 目标函数 约束条件 通常称 为决策变量， 为价值系数， 为消耗系数, 为资源限制系数。 7 线性规划的模型的一般形式: 7 标准线性规划模型（标准形式）： s.t 其中（2） （3）3.线性规划的标准形式（1）8 标准线性规划模型（标准形式）：（2） （3）3.线性规划紧凑格式： s.t.向量格式： s.t. 其中 称为价值向量，

5、为决策变量向量， 为决策变量xj所对应的消耗系数向量， 为资源向量。9紧凑格式：9非标准形式线性规划问题的标准化（1）极大化与极小化 ： 若 ，令 ，则有 原目标函数 。(2)线性不等式与线性等式： 其中 为非负松弛变量， 其中 为非负剩余变量。 10非标准形式线性规划问题的标准化1011矩阵格式：其中 为mn阶矩阵 为价值向量， 为决策变量向量， 为资源向量。11矩阵格式： (4) 非负变量与符号不受限制的变量 若 xi的符号不受限制，则可引进非负变量xi1,xi2，令 xi = xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。 例7，将下述线性规划问题化为标准型

6、解：令,其中符号不受限制 (3) 右端项为负 约束两端乘以（1）12 (4) 非负变量与符号不受限制的变量例7，将下述线性规考虑一个标准的线性规划问题： s.t 其中为n维行向量， 是n维列向量， 是m维列向量， 是mn阶矩阵，假定满足mn，且()=m，标准型线性规划的解的概念13考虑一个标准的线性规划问题： 线性规划问题解的概念：(1) 可行解。满足约束条件的解可行解集称为线性规划问题的可行域。(2) 最优解。使目标函数达到最优值的的可行解称为最优解，最优解常用 表示。(3) 基。若是中mm阶非奇异矩阵，即|0，则称是线性规划问题的一个基。 14 线性规划问题解的概念：14基向量，基变量 若

7、是线性规划问题的一个基，那么一定是由m个线性无关的列向量组成，不失一般性，可设 称 为基向量，与基向量相对应的变量称为基变量。 基的个数 一个线性规划的基通常不是唯一的，但是基的个数也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。15基向量，基变量 若是线性规划问题的一个基，那么一(4) 基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。 有一个基就可以求得一个基本解。 由基的有限性可知，基本解的个数也不会超过 个。 由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5)

8、 基本可行解。满足非负条件的基本解称为基本可行解 （简称基可行解）。与基本可行解对应的基称为可行基。 基本可行解的非零向量的个数小于等于m，并且都是非负的。 由于基本可行解的数目一般少于基本解的数目，因此可行基 的数目也要少于基的数目。 当基本可行解中有一个或多个基变量是取零值时，称此解为 退化的基本可行解。16(4) 基本解。设B是线性规划的一个基，若令n-m个非基变量4.线性规划模型的求解方法1）单纯形法 适合较为简单的问题 单纯形法是求解标准形式线性规划的常用方法，这种方法的基本思想是：迭代过程找出一个基可行解后，判断其是否为最优解；若它不是最优解，再用迭代的方法找出另一个使目标函数值更

9、优的基可行解。经过有限次迭代后，找出最优解或判定出问题有无最优解为目标。174.线性规划模型的求解方法1）单纯形法 适合较为简单的问2）借助软件Mathematica软件、MATLAB软件、Lingo软件、excelLINGO是Linear Interactive and General Optimizer的缩写，即“交互式的线性和通用优化求解器”，由美国LINDO系统公司（Lindo System Inc.）推出的，是用来求解线性和非线性优化问题的简易工具，功能十分强大， LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。18

10、2）借助软件18参照数学模型，在Lingo的模型窗口中输入模型代码例：Max =98*x1+277*x2-x12-0.3*x1*x2-2*x22;X1+x100;x1=0;X2=0; 然后点击工具条上的执行按钮 即可Lingo优化软件简介参照数学模型，在Lingo的模型窗口中输入模型代码Max =执行结果：使用的内存计算时间非零系数个数约束个数变量个数模型类型求解状态目标值迭代次数执行结果：使用的内存计算时间非零系数个数约束个数变量个数模型最优解约束中的松弛变量和剩余变量影子价格：当对应约束有微小变动时,目标函数的变化率最优解约束中的松弛变量和剩余变量影子价格：当对应约束有微小变 注意：（1）

11、每条语句后必须使用分号“；”结束。问题模型必须由Model命令开头，并以END结束。（2）用MODEL命令来作为输入问题模型的开始，格式为MODEL：starement(语句）。（3）目标函数必须由“min”或“max”开头（4）如果说明一个变量X是整型，可以用函数：GIN( X); 如果说明一个变量X是0-1型，可以用函数：BIN( X);22 注意：22用Lingo编程语言建立模型应用Lingo编程语言语句不多，语法简洁；适合大规模数学规划问题；模型易于扩展；初始化语句与其他部分分开；集合的概念很有特色，可表达模型的实际事物；23用Lingo编程语言建立模型应用Lingo编程语言语句不多，

12、例：模型如下Max z=5*x1+7*x2+3*x3s.t.y1+y2+y3=2;x1=7*y1; x2=5*y2; x3=9*y3;3*x1+4*x2+2*x3=30+M*y;4*x1+6*x2+2*x3=0;y1, y2, y3 =1 or 0;y=1 or 0;SETS:PRODUCTS/1.3/:price,x,y,Limit;FACTORIES/1.2/:r;LINKS(FACTORIES,PRODUCTS):CO;ENDSETSDATA:price=5 7 3;Limit=7 5 9;r=30 40;CO=3 4 2 4 6 2;M=255;ENDDATAmax=sum(PRODU

13、CTS(I):price(I)*x(I);sum(PRODUCTS(I):y(I)=2;for(PRODUCTS(I):x(I)=Limit(I)*y(I);sum(PRODUCTS(I):CO(1,I)*x(I)=r(1)+M*z;sum(PRODUCTS(I):CO(2,I)*x(I)=r(2)+M*(1-z);for(PRODUCTS(I):BIN(y(I);BIN(z);例：模型如下Max z=5*x1+7*x2+3*x3SETS25251、概念1）灰色系统 1982年，邓聚龙发表灰色控制系统一文，标志着灰色系统理论诞生。由于灰色系统模型对试验观测数据及其分布没有特殊要求和限制，因此适

14、用于各种领域研究，目前已广泛应用于工业、农业、社会、经济、能源、地质、石油等众多科学领域。根据系统信息的可得性，将系统分为三类：白色系统、黑色系统和灰色系统。 白色系统是指系统内部特征是完全已知的；黑色系统是指系统内部信息完全未知的；而灰色系统是介于白色系统和黑色系统之间的一种系统；灰色系统其内部一部分信息已知，另一部分信息未知或不确定。通过对部分已知信息的生成和开发区了解、认识现实世界，实现对系统运行行为和演化规律的正确描述和把握。26二、灰色系统预测GM（1,1）模型及其Matlab实现1、概念26二、灰色系统预测GM（1,1）模型及其Matla2）灰色预测 灰色预测，是指对系统行为特征值

15、的发展变化进行的预测，对既含有已知信息又含有不确定信息的系统进行的预测，也就是对在一定范围内变化的、与时间序列有关的灰过程进行预测。 目前使用最广泛的灰色预测模型就是关于数列预测的一个变量、一阶微分的GM(1,1)模型。它是基于随机的原始时间序列，经按时间累加后所形成的新的时间序列呈现的规律可用一阶线性微分方程的解来逼近。 G表示gray（灰色），M表示model（模型），（1,1）表示1阶1个变量的微分方程。GM（1，N）是灰色系统主要的模型形式。272）灰色预测27灰色系统的基本原理包括： 1）差异信息原理。“差异”是信息，凡信息必有差异； 2）解的非唯一性原理。信息不完全、不明确的解是非

16、唯一的； 3）最少信息原理。对已有的“最少信息”进行充分开发利用； 4）认知根据原理。信息是认知的根据； 5）新信息优先原理。新信息对认知的作用大于老信息； 6）灰性不灭原理。“信息不完全”是绝对的。282、原理灰色系统的基本原理包括：282、原理3、建模思路GM（1,1）模型常用于灰色系统预测。灰色系统预测模型建模思路为：1）将离散数据视为连续变量在其变化过程中所取的离散值，从而可以利用微分方程式处理数据；2）不直接使用原始数据而是由原始数据产生累加生成数列，对数列使用微分方程实现模型构建。通过以上建模思路，GM预测模型可以抵消大部分数据产生的随机误差，显示出规律性。293、建模思路GM（1

17、,1）模型常用于灰色系统预测。灰色系统4、GM（1,1）建模过程和运行机理1）将原始数据序列记录为非负序列：其中，x（0）（k）0，k=1,2，n。其相应的生成数据序列为X（1）：其中，4、GM（1,1）建模过程和运行机理1）将原始数据序列记录为2）生成X（1）的紧邻均值数列Z（1）其中，其中，a和b是需要通过建模求解的参数。3）由X（0）、 X（1） 和Z（1）可构建GM（1,1）模型如下：2）生成X（1）的紧邻均值数列Z（1）其中，其中，a和b是需4）若a=（a，b）T为参数列，且求微分方程 ： 的最小二乘估计系数列满足 ，则微分方程的白化方程为：4）若a=（a，b）T为参数列，且求微分方

18、程 ： 5）白化方程 的解可称为时间响应函数，公式为：GM（1,1）灰微分方程 的时间响应序列为：5）白化方程 6）取x（1）（0）= x（0）（1），则还原值为：6）取x（1）（0）= x（0）（1），则还原值为：5、实例以预测白云区2015-2019年人口为例 以广州市白云区2005年-2014年常住人口数据为例，预测白云区2015年-2019年常住人口数量。原始数据如下表所示： 年份常住人口2005155.452006175.462007184.242008190.272009201.162010207.482011216.672012223.22013230.572014228.892

19、01520162017201820195、实例以预测白云区2015-2019年人口为例 1）将原始数据序列记录为非负序列：其相应的生成数据序列为：6、求解x（0）=155.45 175.46 184.24 190.27 201.16 207.48 216.67 223.2 230.57 238.89x（1）=155.45 330.91 515.15 705.42 906.58 1114.06 1330.73 1553.93 1784.50 2023.391）将原始数据序列记录为非负序列：其相应的生成数据序列为：62）生成X（1）的紧邻均值数列Z（1）3）根据X（0）、 X（1） 和Z（1）构建GM（1,1）模型：Z（1）=243.18 423.03 610.285 806 1010.32 1222.395 1442.33 1669.215 1903.945如X（0）（1）为： 155.45+243.18a=b2）生成X（1）的紧