线性规划与数学建模简介教学教材

1、学习 好资料更多精品文档第十三章线性规划与数学建模简介【授课对象】理工类专业学生【授课时数】6 学时【授课方法】课堂讲授与提问相结合【基本要求】1 、了解数学模型的基本概念、方法、步骤；2、了解线性规划问题及其数学模型；3 、了解线性规划问题解的性质及图解法.【本章重点】 线性规划问题 .【本章难点】 线性规划问题、线性规划问题解的性质、图解法 .【授课内容】本章简要介绍数学建模的基本概念、方法、步骤，并以几个典型线性规划问题为例，介绍构建数学模型的方法及其解的性质。1数学建模概述一、数学建模数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法

2、，必须从实际问题出发，遵循从实践到认识再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过程。二、数学模型的概念模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、量和加速度之间关系的牛顿第二定律F= ma就是一个典型的（数学）模型。一般地,可以给数学模型下这样的定义：数学模型是磁于以部分现实世界为一定目的而做的抽象、简化的数学结构。通俗而言，数学模型是为了一定目的对原型所作的一种抽象模拟，它用数学式子，数学符号以及程序

3、、图表等描述客观事物的本质特征与内在联系。三建立数学模型的方法和步骤建立数学模型没有固定模式。下面介绍一下建立模型的大体过程：1 . 建模准备建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使认识和实践过一步发展必须解决的问题。因此，我们首先要发现这类需要解决的实际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划，组织必要的人力、物力等，确立建模课题。2 模型假设作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进行抽象简化，人们就无法准确把握它的本质属性，而模型假设就是根据建模的目的对原型进行抽象、简化，抓住反映问题本质属性的主要因素，简化掉那些

4、非本质的次要因素。有了这些假设，就可以在相对简单的条件下，弄清各因素之间的关系，建立相应的模型。合理的假设是建立理想模型的必要条件和基本保证。如果假设是合理的，则模型切合实际，能解决实际问题；如果假设不合理中或过于简化，则模型与实际情况不符或部分相符，就解决不了问题，就要修改假设，修改模型。3 构造模型在模型假设的基础上，开始构建数学模型。首先分析变量类型，恰当使用数学工具。一般而言，如果实际问题中的变量是确定型变量，数学工具可采用微积分、微分方程、线性或非线性规划、投入产出、确定性库存论等。如果变量是随机变量，数学工具可采用概率与统计、排队论、对策论、决策论、随机微分方程、随机性库存论等。其

5、次，抓住问题本质，简化变量之间的关系。可以说，数学的任一分支在构造模型时都可能有用，而同一实际问题也可以构造不同的数学模型。一般而言，在能够达到建模目的前提下，所用的数学工具应力求简单、易解，但要保证模型的解的精确在允许的范围内。4 模型求解不同的模型要选择或设计不同的数学方法和算法求解，许多模型还可以通过编写计算机程序软件包，借助计算机快速完成对模型的求解。5 模型分析对模型的求解结果进行分析，主要包括稳定性分析，参数的灵敏度分析，误差分析等。通过分析，若发现不符合建模要求，就要修改或增减建模假设条款，重新构造模型，直到符合要求。若模型符合要求，则可以对模型进行评价是、预测民、优化等方面的探

6、析，力争得到最优模型。6 模型检验对于经过分析后符合要求的模型，还要把它放回到实际对象中去进行检验，看它是否符合实际，能否解决相应的实际问题。若不符合实际，就要修改前提假设，重新建模，重新分析，直到获得符合实际的模型。7 模型应用建模最终目的，是用模型来分析、研究和解决实际问题。因此，一个成功和数学模型必须能够在实践中得到成功的应用，甚至形成一套科学和理论。图 13 1学习-好资料是上述各步骤的直观图:图13 1数学建模步骤示意图一、数学模型的分类数学模型按照不同的分类标准有许多种类：1 .按照模型的数学方法分，有几何模型、代数模型、图论模型、微分方程模型概率模型、最优控制模型、随机模型等等。

7、2 .按模型的特征分，有静态模型和动态模型，确定性模型和随机模型，离散模型和 连续性模型，线性模型和非线性模型等。3 .按模型的应用领域分，有人口模型、交通模型、经济模型、生态模型、资源模型、 环境模型等。4。按建模的目的分，有预测模型、优化模型、决策模型、控制模型等。5.按夺模型结构的了解程度分，有白箱模型、灰箱模型、黑箱模型等。2线性规划问题及其数学模型线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛 的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以 最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现 有条件下进行组织和安排

8、，以完成更多的工作。因此，线性规划就是求一组变量的 值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。一、运输问题例1设有Ai, A2两个香蕉基地，产量分别为 60吨和80吨，联合供应Bi, B2, B3三个销地的销售量经预测分别为 50吨、50吨和40吨。两个产地到三个销地 的单位运价如下表所示：表131运价表（单位：元/吨）地BiB2B3Ai600300400A2400700300问每个产地向每个销地各发货多少，才能使总的运费最少?解 (1)在该问题中，所要确定的量是各产地运往各销地的香蕉数量，即决策变量是运输量。设Xj(i=1,2; j =1,2,3)分别表示由产地

9、Ai运往销地Bi的数量。(2)在解决问题的过程中，要受到如下条件限制，即约束条件:各产地运出的数量应等于其产量，即6080+ + X11 X12 X13 一+ + -匚 X 21 X 22 X 23各销地运进的数量应等于其当地预测的销售量，即Xl+X21=50 X12+X22=50-X13*X23=40从各产地运往各销地的数量不能为负值，即Xij -0(i =1,2; j =1,2,3)该问题的目的是运价最低，所以运价是目标函数，即S = 600 X11 +300X12 + 400 X12 + 400 X21 + 700 X22 + 300 X23 因止匕，该问题的数学模型为：求 min S

10、-600X11 300X12 400X13 400*1 700X22 300X23厂 Xii*Xi2*Xi3=60X21 + X22 + X23 = 80结束条件XiX21=50X12 + X22 = 50 X/X23 =40例1的一般形式是：设某种物资有m个产地A，A2,Am产量分别为 a1,a2,am5有n个销地BB,B,销量分别为b,b“.b(吨)。如果由 产地A运往销地Bj的单位运价为Cj (元/吨)，在产销平衡的情况下，应如何调运才能使运费最省？解 设Xj表示由产地Ai运往销地Bj的数是(i=l, m； j=1,2,n)则该问题数学模型为：求变量Xj的一组值，使它们满足X xii +

11、xi2+xin=ai+ + + Xm1 Xm2 . Xmn 一 HmIXli+X2lt.*Xm1=blX24X22 +4 Xm2=b2Xin+X2n * +Xmn=bnXj 0(i=i,2,.m;j=i2.n),并使目标函数S=CiiXii+Ci2Xi2+CmnXmn的值最小。二、生产组织与计划问题例2设某用a，a，,Am种原料，生产B1，B2,Bm种产品，其中Bj种产品 每单位需要 A，A2,Am原粉分别为；而该厂现有原料 ai，a2，,amj；的数量分别为 bi，b2,bm，Bi，B2,Bn各种产品每单位可是利润分别为Ci，C2,Cn。在该厂产 品全部能销售情况下，应如何组织生产，才能使该

12、企业获得最大？解 设生产产Bj中数量为Xj(j =i,2,n)，则此问题的数学模型为：求一组变量的值，使满足厂aiiXi+ai2X2+十 anH2iXi+a22X2+. .ta2nXn-b2结束条件-amiXi am2 X2 . amn Xn - bm lXj 之O(j=i, 一口)，并使目标函数S=CiXi+C2X2+CnXn的值最大。三、配料问题例 设有A1,Am种原料，配制含有几种成分 B1，B2,Bn的产品，要求产品中各 种成分的含量不低于a1，a2，an ；不高于b1，b2，,bn ； Bj种成分在A种原料中的 单位含量为，各种原料的单位价格依次为d1，d2，dm.问如何调配原料，才

13、能使产品 符合要求，又使成本最低？解 设xi表示每单位产品中原料 Ai的使用量（即决策变量），i =1,2,m,则数学模型 为：求一组变量的值，使其满足a al -Cl1 Xi +C21 X2 +. + CmlXm - bla2 -C12X1 +C22 X2. +Cm2Xm-b2约束条件1 ）an -C1nX1+C2n X2 + .+CmnXn - bnX1 + X2+Xm=1I Xi ,（i =1,m）并使目标函数S=d1X+dmXm最小。二、线性规划问题数学模型的一般形式和标准形式上面我们建立了经济领域中常见的实际问题的数学模型，尽管这些实际问题本身是多种多样的，但是它们的数学模型却具有相

14、同的特征：要确定某些变量（决策变量）的一组值，使得在确定的确定的约束条件下，目标函数是取得最大值或最小值。其 中，约束条件是决策变量的线性方程或线性不等式。目标函数是决策变量的线性函 数。因此，我们把这种规划问题称为线性规划问题。同时，我们可以得到对于一个 线性规划问题，其数学模型应具有如下形式：求 max（或 min）S=C1X1 C2X2 CnXna aux+2x2+ainXnb（或至b，或=9a2lXl +a22X2+ + a2nXn b2（或至 b2,或加0(j =i,2,n)线性规划问题的标准（i3.i ）也可写成矩阵形式minS =CXAX =bs.tLx -0其中 C =（C，C

15、2,，Cn），XX=广2.JX3-b，B= b2- ai2 a侵amA= a21a22a2 n.ami am2 amn -更多精品文档学习-好资料对于线性规划问题的一般形式，可以按如下方法化成标准形：(1)如果线性规划问题是求目标函数的最大值，即求maxS = ClX1+cnxn,只要令S = -S ,即可化为求目标函数的最小值，即求 m iSnC1X1 C2X2CnXn(2)如果某个约束条件为线性不等式，则可将其化为线性议程式的形式。设第k个约束条件为akiXl +ak2X2 +akmXn芸bk :则加入一个新变量，将其约束条件改为：akiXl ak2X2aknXn Xn k =bk这个所加

16、的变量称为松弛变量。若第l个约束条件为：aMXi +ai2X2+ ainXn -b则加入一个新变量，将上述约束条件变为：ailXl ai2X2ainXn Xnl =bl(3)若对某变量没有非负限制，则引进两个非负变量X，j之0，X”j20令Xj = Xj X：代入约束条件和目标函数，可化为全部变量都有非负限制。例4 将下列线性规划模型化为标准形m aSX-2Xi 3X2X2+X2-5S.tj3Xi X22Y?0，Y2为非负限制X1 X2X“2 且 xFQxy0解引入松驰变量X30，X40,令S=-S，X2 = X2更多精品文档学习-好资料即可得标准形式如下m iSn2Xi-3x2 3xXi+2

17、X22X %X3=5S.t 3Xix 2 x 2 X4 =2X2-0，X 2-0，Xj-（j =1,3,4）3线性规划问题解的性质及图解法一、线性规划问题的解的性质对于线性规划问题(13.2):minS =CX1.几个概念(D 口仃解：满足线性规划问题所有约束条件的向量 x =(x1(0)，Xn(0)T称为可行解，所有可行解构成的集合称为可行域，记为 R,则R= x| Ax = b,x2 0(2)基础可行解：若可行解X=0,或X的非零分量所对应的系数列向量线性无关， 则称X为基础可行解。(3)最优解：使目标函数取最小值的可行解称为最优解。 (4)基础最优解：使目标函数取最小值的基础可行解称为基

18、础最优解。 (5)门”：若连接n维点集S中任意两点Xl，X2的线段仍要S内，则称S为凸集。换言之，若x|x = ： X1 1-： X2，0- -1，Xi，X2 S : S，S En则称S为凸集。更多精品文档学习-好资料（6）强点：若凸集S中的点x,不能成为S中任何线段的内点，则称x为S的极点，换言之，若对任意不同两点 x1,x2e S,不存在a（0a1）,使x =二 x1 （1 ）X2 三 S则称x为S的极点。例如，圆周上的点都是极点。s（7）门”学:设xi = En,实数九0=1,2,s,且九i=1,则称.i 1x = 1x1 x2s s为点x1, x2, , xs的一个凸组合。2. 线性规

19、划问题的解由线性代数求解议程组的方法及上述概念可知，线性规划问题（ LP）的解有如下几种情况：ff.有唯一最优解有可行解有无穷多最优解无最优解无可行解3. 线性规划问题解的性质性质1线性规划问题（LP）的可行域R = x|AX=b,X20 是凸集。性质2可行域R中的点x是极点的充要条件是x是基础可行解。性质3若（LP）问题的可行域Rw，则R至少有一极点，且极点的个数有限。性质4最优值可以在极点上达到。这几条性质实际上给我们指出了线性规划问题求解的思路和方向：由于线性规划问题的最优解一定能在可行解集的极点达到，而极点的数目中有限的。所以，总更多精品文档学习-好资料可以想办法在有限的极点中经过有限

20、次寻找，得到最优解。因而，就有了求解线性 规划问题的图解法和单纯形法。由于篇幅所限，下面仅介绍图解法的应用。有兴趣 的读者可以学习一下单纯形法。二、图解法（又称几何法）图解法是对于只是两个决策变量的线性规划问题，在平面内建立直角坐标系， 使每个决策变量的取值在一个数轴上表示出来，可行解就成为平面上的点，可 行域就是平面上的一个共域，从而最优解必定是在这个平面区域内（包括边界 上）的点。根据目标函数在这个平面区域内的取值找出使目标函数取得最优值 的点（即最优解）。图解法便于我们理解和了解线性规划问题的一些概念、理论及解的一些特性， 也为我们进一步学习单纯方法提供一个直观图形。例5 求解线性问题m

21、 iS n 7 x1 + 5x2xi +2x2-28S.tJ4xi + X242Xi，X2 0解 第一步，在平面直角坐标系OX1X2上绘出约束条件图（图13 2）画出这条直线 X1+2X2=28,再定出X1+2X2W28区域。把（0, 0）代入不等式得0+2 028,所以，原点所在平平面及直线本身就是X1+2X2M28代表的区域。画出4Xl + X2=42这条直线，定出4Xl+X2E42代表的区域，有（0, 0）代入不等式得0 4 + 042所以，4X1 + X2W42代表的区域是包括原点的下半平面与直线本身。4Xi X2 = 42定出X1之0,X2之0的区域，它就是第一象限。从图X X7X1 5X2=106学习-好资料13 2看出，满足全部约束条件的点所构成的区域（即7 Xi 5x2 50可行域）,就是凸多边形OABC。X1 2X1 = 28第二步，绘制目标函数图形。对于目标函数 S = 7X1+5X2、将S看作参数，即得到一簇平行直线（图13-2中虚线所.示），直线上每一点的目标函数值为 So由图可见，直线离飞原点越远，S值越大，我们寻找的