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

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

2、生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万元。但根据万元。但根据市场需求调查的结果，甲药品每周的产量不应超过市场需求调查的结果，甲药品每周的产量不应超过4 4吨。问该厂应如何安吨。问该厂应如

3、何安排两种药品的产量才能使每周获得的利润最大？排两种药品的产量才能使每周获得的利润最大？4 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。数学模型为数学模型为 s.t.s.t.（subject to)subject to)(such that)(such that)称之为上述问题的数学模型。121212112maxZ=5x+2x30 x20 x1605xx15x4x0,x0每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（

4、台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 552.2.线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示某一方案，且在一般情况下，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式或线）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式

5、来表达。性不等式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（）或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题6 线性规划的模型的一般形式线性规划的模型的一般形式:目标函数目标函数 约束条件约束条件 通常称通常称 为决策变量，为决策变量，为价值系数，为价值系数，为消耗系数为消耗系数,为资源限制系数为资源限制系数。1122nnmax(min)Z=c x+c x+c x1111221nn12112222nn2m11m22mnnm12n a xa xa x(,)b a xa xa x(

6、,)b axaxax(,)b x,x,x0 12nx,x,x12nc,c,c1112mna,a,a12mb,b,b711max(min)(,)s.t.0,1,2,niiiniiiizc xa xbxin n 标准线性规划模型（标准形式）：标准线性规划模型（标准形式）：s.t s.t 其中其中（2 2）（3 3）3.3.线性规划的标准形式线性规划的标准形式（1 1）1122nn1111221nn12112222nn2 m11m22mnnm 12nminZ=c x+c x+c xa x+a x+a x=ba x+a x+a x=bax+ax+ax=b x,x,x012mb=(b,b,b)0T8l紧

7、凑格式：紧凑格式：s.t.s.t.l向量格式：向量格式：s.t.s.t.其中其中 称为价值向量，称为价值向量，为决为决策变量向量，策变量向量，为决策变量为决策变量x xj j所对应的消耗系数所对应的消耗系数向量，向量，为资源向量。为资源向量。njjj=1minZ=C xnjjj=1jP x=bx0,j=1,2,nminZ=CXnijjij=1ja x=b,i=1,2,mx0,j=1,2,n12nC=(c,c,c)12nX=(x,x,x)Tj1j2jmjP=(a,a,a)T12mb=(b,b,b)T9n非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化（1 1）极大化与极小化）极大化与

8、极小化 ：若若 ，令，令 ，则有，则有 原目标函数原目标函数 。(2)(2)线性不等式与线性等式：线性不等式与线性等式：其中其中 为非负松弛变量，为非负松弛变量，其中其中 为非负剩余变量。为非负剩余变量。njjj=1maxZ=C xn+ixn+kxZ=-Znjjj=1minZ=min(-Z)=-minZ=-C xnjjj=1maxZminZ=-C xnnijjiijjn+iij=1j=1a xb a x+x=bnnkjjkkjjn+kkj=1j=1a xb a x-x=b1011minZ=CXAX=bX011121n21222nm1m2mnaa.aaa.aA=.aa.al矩阵格式：矩阵格式：其

9、中其中为为mn阶矩阵阶矩阵 为价值向量，为价值向量，为决策变量向量，为决策变量向量，为资源向量。为资源向量。12nC=(c,c,c)12nX=(x,x,x)T12mb=(b,b,b)T (4)(4)非负变量与符号不受限制的变量非负变量与符号不受限制的变量 若若 x xi i的符号不受限制，则可引进非负变量的符号不受限制，则可引进非负变量x xi1i1,x,xi2i2，令，令 x xi i=x=xi1i1-x-xi2i2，这样就可以使线性规划里所有的变量都转化为有非负限，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。制的变量。例例7 7，将下述线性规划问题化为标准型，将下述线性规划问

10、题化为标准型 123123123123123minZ=-x+2x-3x xxx7 x -xx2 3x -x -2x5x0,x0,x解：解：令令,其中其中1245124 56124571245124567minZ=x-2x+3x-3x xxx -xx =7 x -xx -x -x=23x -x -2x+2x 5x,x,x,x,x,x0345x=x-x45x0,x0.(3)(3)右端项为负右端项为负 约束两端乘以（约束两端乘以（1 1）12考虑一个标准的线性规划问题：考虑一个标准的线性规划问题：s.t s.t 其中为其中为n n维行向量，维行向量，是是n n维列向量，维列向量，是是m m维列向量，

11、维列向量，是是m mn n阶矩阵，假定满足阶矩阵，假定满足mnmn，且，且()=m)=m，minZCX AXb X0 p标准型线性规划的解的概念标准型线性规划的解的概念13 线性规划问题解的概念：(1)可行解。满足约束条件的解可行解集称为线性规划问题的可行域。(2)最优解。使目标函数达到最优值的的可行解称为最优解，最优解常用 表示。(3)基。若是中mm阶非奇异矩阵，即|0，则称是线性规划问题的一个基。minZCX(4)AXb (5)X0 (6)*X12nX=(x,x,x)TD=X/AX=b ,X0 14基向量，基变量 若是线性规划问题的一个基，那么一定是由m个线性无关的列向量组成，不失一般性，

12、可设 称 为基向量，与基向量相对应的变量称为基变量。基的个数 一个线性规划的基通常不是唯一的，但是基的个数也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。11121m21222m12mm1m2mmaa.aaa.aB=(P,P,P).aa.amnCj1j2jmjp=(a,a,a),(j=1,2,m)jPjx,(j=1,2,m)15(4)基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。有一个基就可以求得一个基本解。由基的有限性可知，基本解的个数也不会超过 个。由于基本解中的非零分量可能

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

14、后，找出最优解或判定出问题有无最优解为目标。17 2）借助软件Mathematica软件、MATLAB软件、Lingo软件软件、excelLINGO是Linear Interactive and General Optimizer的缩写，即“交互式的线性和通用优化求解器”，由美国LINDO系统公司（Lindo System Inc.）推出的，是用来求解线性和非线性优化问题的简易工具，功能十分强大，LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。1812221122982770.32Max zxxxx xx121 0 0 xx1

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