《线性规划与数学建模简介.pdf》由会员分享,可在线阅读,更多相关《线性规划与数学建模简介.pdf(10页珍藏版)》请在三一文库上搜索。
1、精品课程高等数学 (线性代数部分)电子教案 第 1 页 共 10 页 第十三章线性规划与数学建模简介 【授课对象】 理工类专业学生 【授课时数】 6 学时 【授课方法】 课堂讲授与提问相结合 【基本要求】 1、了解数学模型的基本概念、方法、步骤; 2、了解线性规划问题及其数学模型; 3、了解线性规划问题解的性质及图解法. 【本章重点】 线性规划问题 . 【本章难点】 线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤,并以几个典型线性规划问题 为例,介绍构建数学模型的方法及其解的性质。 1 数学建模概述 一、数学建模 数学建模是构造刻划客观事
2、物原型的数学模型并用以分析、研究和解决实际问 题的一种科学方法。运用这种科学方法,必须从实际问题出发,遵循从实践到认识 再实践的认识规律,围绕建模的目的,运用观察力、想象力的抽象概括能力,对实 际问题进行抽象、简化,反复探索,逐步完善,直到构造出一个能够用于分析、研 究和解决实际问题的数学模型。因此,数学建模是一种定量解决实际问题的创新过 程。 二、数学模型的概念 模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律Fma就是一个典型的(数学)模型。一般地, 可以给数学模型下这样的定义:数学模型是磁于以部分现实世界为一定目的而做的 抽象、简化的数学
3、结构。 通俗而言,数学模型是为了一定目的对原型所作的一种抽象模拟,它用数学 式子,数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程: 1. 建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此,我们首先要发现这类需要解决的实 际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划,组织 必要的人力、物力等,确立建模课题。 2模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进 行抽象简化,人们就无法
4、准确把握它的本质属性,而模型假设就是根据建模的目的 对原型进行抽象、简化,抓住反映问题本质属性的主要因素,简化掉那些非本质的 精品课程高等数学 (线性代数部分)电子教案 第 2 页 共 10 页 次要因素。有了这些假设,就可以在相对简单的条件下,弄清各因素之间的关系, 建立相应的模型。 合理的假设是建立理想模型的必要条件和基本保证。如果假设是合理的,则模 型切合实际,能解决实际问题;如果假设不合理中或过于简化,则模型与实际情况 不符或部分相符,就解决不了问题,就要修改假设,修改模型。 3构造模型 在模型假设的基础上,开始构建数学模型。首先分析变量类型,恰当使用数学 工具。一般而言,如果实际问题
5、中的变量是确定型变量,数学工具可采用微积分、 微分方程、线性或非线性规划、投入产出、确定性库存论等。如果变量是随机变量, 数学工具可采用概率与统计、排队论、对策论、决策论、随机微分方程、随机性库 存论等。其次,抓住问题本质,简化变量之间的关系。可以说,数学的任一分支在 构造模型时都可能有用,而同一实际问题也可以构造不同的数学模型。一般而言, 在能够达到建模目的前提下,所用的数学工具应力求简单、易解,但要保证模型的 解的精确在允许的范围内。 4模型求解 不同的模型要选择或设计不同的数学方法和算法求解,许多模型还可以通过编 写计算机程序软件包,借助计算机快速完成对模型的求解。 5模型分析 对模型的
6、求解结果进行分析,主要包括稳定性分析,参数的灵敏度分析,误差 分析等。通过分析,若发现不符合建模要求,就要修改或增减建模假设条款,重新 构造模型,直到符合要求。若模型符合要求,则可以对模型进行评价是、预测民、 优化等方面的探析,力争得到最优模型。 6模型检验 对于经过分析后符合要求的模型,还要把它放回到实际对象中去进行检验,看 它是否符合实际,能否解决相应的实际问题。若不符合实际,就要修改前提假设, 重新建模,重新分析,直到获得符合实际的模型。 7模型应用 建模最终目的,是用模型来分析、研究和解决实际问题。因此,一个成功和数 学模型必须能够在实践中得到成功的应用,甚至形成一套科学和理论。图13
7、 1 是上述各步骤的直观图: 一、数学模型的分类 数学模型按照不同的分类标准有许多种类: 1按照模型的数学方法分,有几何模型、代数模型、图论模型、微分方程模型 建模准备 (分析实际问题 确立课题) 建模假设 (抽象、 简化) 构建模型 模型求解模型分析 (是否相符) 模型分析 (是否相符 模型应用 图 13 1 数学建模步骤示意图 精品课程高等数学 (线性代数部分)电子教案 第 3 页 共 10 页 概率模型、最优控制模型、随机模型等等。 2按模型的特征分,有静态模型和动态模型,确定性模型和随机模型,离散模型和 连续性模型,线性模型和非线性模型等。 3按模型的应用领域分,有人口模型、交通模型、
8、经济模型、生态模型、资源模型、 环境模型等。 4。按建模的目的分,有预测模型、优化模型、决策模型、控制模型等。 5按夺模型结构的了解程度分,有白箱模型、灰箱模型、黑箱模型等。 2 线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支,是研究较早,理论较完善,应用最广泛 的一门科学。它所研究的问题主要包括两个方面:一是在一项任务确定后,如何以 最低限度和成本(如人力、物力、资金和时间等)去完成这一任务;二是如何在现 有条件下进行组织和安排,以完成更多的工作。因此,线性规划就是求一组变量的 值,使它满足一组线性式子,并使一个线性函数的值最大(或最小)的数学方法。 一、运输问题 例 1 设有
9、A1,A2两个香蕉基地,产量分别为 60吨和 80 吨,联合供应 B1,B2, B3三个销地的销售量经预测分别为50 吨、50 吨和 40 吨。两个产地到三个销地的单 位运价如下表所示: 表 131 运价表(单位:元 / 吨) 问每个产地向每个销地各发货多少,才能使总的运费最少? 解(1)在该问题中,所要确定的量是各产地运往各销地的香蕉数量,即决策变量 是运输量。设 Xij(i =1,2; j=1,2,3) 分别表示由产地 Ai 运往销地 Bi 的数量。 (2)在解决问题的过程中,要受到如下条件限制,即约束条件: 各产地运出的数量应等于其产量,即 80 60 232221 131211 xxx
10、 xxx 各销地运进的数量应等于其当地预测的销售量,即 40 50 50 2313 2212 2111 xx xx xx 从各产地运往各销地的数量不能为负值,即 销地 单位动价 产地 B1B2B3 A1600 300 400 A2400 700 300 精品课程高等数学 (线性代数部分)电子教案 第 4 页 共 10 页 )3,2,1;2, 1(0ji xij (3) 该问题的目的是运价最低,所以运价是目标函数,即 xxxxxx S 232221121211 300700400400300600因此,该问题的数学模型为: 求 xxxxxx S 232221131211 300700400400
11、300600min 结束条件 40 50 50 80 60 2313 2212 2111 232221 131211 xx xx xx xxx xxx 例 1 的 一 般 形 式 是 : 设 某 种 物 资 有m 个 产 地 AAA m , 21 产 量 分 别 为 aaa m , 21 , 有 n 个销地BBB n , 21 , 销量分别为 。吨,)(, 321 bbb 如果由 产地Ai运往销地B j 的单位运价为Cij(元/ 吨) ,在产销平衡的情况下, 应如何调运 才能使运费最省? 解设xij表示由产地Ai运往销地B j 的数是 (i=1, , m ;j=1,2, , n) 则该问题数学
12、模型为: 求变量 xij 的一组值,使它们满足 ),.,2, 1;,.,2, 1(0 . . . . . 21 222212 112111 21 11211 njmi x bxxx bxxx bxxx axxx axxx ij nmnnn m m mmnmm n 并使目标函数 xCxCxC mnmn S. 12121111 的值最小。 二、生产组织与计划问题 例 2 设某用 AAA m ,., 21 种原料,生产 BBB m ,., 21 种产品,其中 B j 种产品 每单位需要 AAA m ,., 21 原粉分别为;而该厂现有原料 aaa mj ,., 21 ;的数量分别为 BBBbbb n
13、m ,.,., 2121 各种产品每单位可是利润分别为 CCC n ,., 2, 1 。 在该厂产 精品课程高等数学 (线性代数部分)电子教案 第 5 页 共 10 页 品全部能销售情况下,应如何组织生产,才能使该企业获得最大? 解 设生产产 Bj 中数量为),.,2, 1(nj xj ,则此问题的数学模型为: 求一组变量的值,使满足 结束条件 ),.,1(0 . . . . 2211 22222121 11212111 nj x bxaxaxa bxaxaxa bxaxaxa j mnmnmm nn nn 并使目标函数 xCxCxC nn S. 2211 的值最大。 三、配料问题 例设有 A
14、A m ,., 1 种原料,配制含有几种成分 BBB n ,., 21 的产品,要求产品中各 种成分的含量不低于 aaa n ,., 21 ;不高于 bbb n ,., 21 ; Bj 种成分在 Ai 种原料中的 单位含量为, 各种原料的单位价格依次为.,., 21 ddd m 问如何调配原料, 才能使产品 符合要求,又使成本最低? 解设 xi 表示每单位产品中原料 Ai 的使用量 ( 即决策变量 ) ,,.,2, 1mi则数学模型 为: 求一组变量的值,使其满足 约束条件 ),.,1( , 0 1. . . . 21 2211 222221122 112211111 mi x xxx bxC
15、xCxCa bxCxCxCa bxCxCxCa i m nnmnnnn mm mm 并使目标函数 xdxd mm S. 11 最小。 二、线性规划问题数学模型的一般形式和标准形式 上面我们建立了经济领域中常见的实际问题的数学模型,尽管这些实际问题本身是 多种多样的,但是它们的数学模型却具有相同的特征:要确定某些变量( 决策变量 ) 的一组值,使得在确定的确定的约束条件下,目标函数是取得最大值或最小值。其 中,约束条件是决策变量的线性方程或线性不等式。目标函数是决策变量的线性函 数。因此,我们把这种规划问题称为线性规划问题。同时,我们可以得到对于一个 线性规划问题,其数学模型应具有如下形式: 求
16、 xCxCxC nn S 2211 min)max(或 精品课程高等数学 (线性代数部分)电子教案 第 6 页 共 10 页 ),.,2, 1(0 ),(. )(. )(. xi 222211 2222222121 1111212111 ni bbbxaxaxa bbbxaxaxa bbbxaxaxa mnmnmm nn nn 或或 ,或或 ,或或 我们称这种形式的线性规划模型为一般形式。其中, C j 为目标函数系数约束方 程系数; bi 为约束方程常数项; (i=1, ,m;j=1, ,n). 由此可见,一个线性规划问题问题的数学模型,必须含有三个要素:决策变量、 约束条件和目标函数。 由
17、上面的例子可知,线性规划问题的数学模型的一般形式很多。目标函数有求 最大值和最小值;约束条件有“”, “” , “”三种情况。这种多样性给问题的 讨论带来很大的不便。为此,我们介绍线性规划问题的一种统一形式标准形式。 规定线性规划问题的数学模型的标准形式为: xCxCxC nn S.min 2211 S.t ),.,2, 1(0 . . . . 2211 22222221 11212111 nj x bxaxaxa bxaxaxa bxaxaxa i mnmnmm nn nn 线性规划问题的标准( 13.1 )也可写成矩阵形式 CXSmin s.t 0X bAX 其中),( ,21 ccc n
18、 C, X x x x 3 2 1 . ,A aaa aaa aaa mnmm n n . 21 22221 11212 ,B b b b m 2 1 对于线性规划问题的一般形式,可以按如下方法化成标准形: (1)如果线性规划问题是求目标函数的最大值,即求 xcxc nn S 11 max ,只 要令SS,即可化为求目标函数的最小值,即求 xcxcxc nn S 2211 min (2)如果某个约束条件为线性不等式,则可将其化为线性议程式的形式。 精品课程高等数学 (线性代数部分)电子教案 第 7 页 共 10 页 设第 k 个约束条件为 bxaxaxa knkmkk2211 : 则加入一个新
19、变量,将其约束条件改为: bxxaxaxa kknnknkk2211 这个所加的变量称为松弛变量。 若第l个约束条件为: bxaxaxa lnllln2211 则加入一个新变量,将上述约束条件变为: bxxaxaxa llnnllln2211 (3)若对某变量没有非负限制,则引进两个非负变量0,0 xx jj 令 xxx jjj 代入约束条件和目标函数,可化为全部变量都有非负限制。 例4将下列线性规划模型化为标准形 xx S 21 32m a x 为 非 负 限 制 xx xx xx tS 21 21 22 ,0 23 5 . 解引入松驰变量0, 0 43 xx ,令 xxx SS 222 ,
20、且0,0 22 xx 即可得标准形式如下 xxx S 221 332m i n S.t )4,3, 1(,0,0 23 522 22 4221 3221 j xxx xxxx xxxx j 3 线性规划问题解的性质及图解法 一、线性规划问题的解的性质 对于线性规划问题( 13.2 ) : CXSmin 0 . X bAX tS 1几个概念 精品课程高等数学 (线性代数部分)电子教案 第 8 页 共 10 页 (1)可行解 :满足线性规划问题所有约束条件的向量 T n xx X),( )0()0( 1 称为可行 解,所有可行解构成的集合称为可行域,记为R ,则 R0,|xbAxx (2)基础可行
21、解 :若可行解 X0,或 X的非零分量所对应的系数列向量线性无关, 则称 X为基础可行解。 (3)最优解 :使目标函数取最小值的可行解称为最优解。 (4)基础最优解 :使目标函数取最小值的基础可行解称为基础最优解。 (5)凸集 :若连接 n 维点集 S中任意两点 xx 21, 的线段仍要 S内,则称 S为凸集。 换言之,若 n ESSSxx xxxx , 10,1| 2121 则称 S为凸集。 (6)极点 :若凸集 S中的点 x , 不能成为 S中任何线段的内点,则称x 为 S的极点。 换言之,若对任意不同两点S xx 21, , 不存在)10(,使 Sx xx 21 )1( 则称 x 为 S
22、的极点。例如,圆周上的点都是极点。 (7)凸集合 :设 n i E x ,实数, 2, 1, 0si i 且 s i i 1 1, 则称 ss xx x 211 为点 xxx s , 21 的一个凸组合。 2线性规划问题的解 由线性代数求解议程组的方法及上述概念可知,线性规划问题(LP)的解有如下几 种情况: 有唯一最优解 有可行解有无穷多最优解 无最优解 无可行解 3线性规划问题解的性质 性质 1 线性规划问题( LP)的可行域0,|XbAXXR是凸集。 性质 2 可行域 R中的点 x是极点的充要条件是x是基础可行解。 性质 3 若(LP)问题的可行域R ,则 R至少有一极点,且极点的个数有
23、限。 性质 4 最优值可以在极点上达到。 这几条性质实际上给我们指出了线性规划问题求解的思路和方向:由于线性规 划问题的最优解一定能在可行解集的极点达到,而极点的数目中有限的。所以,总 可以想办法在有限的极点中经过有限次寻找,得到最优解。因而,就有了求解线性 规划问题的图解法和单纯形法。由于篇幅所限,下面仅介绍图解法的应用。有兴趣 精品课程高等数学 (线性代数部分)电子教案 第 9 页 共 10 页 的读者可以学习一下单纯形法。 二、图解法(又称几何法) 图解法是对于只是两个决策变量的线性规划问题,在平面内建立直角坐标系, 使每个决策变量的取值在一个数轴上表示出来,可行解就成为平面上的点,可
24、行域就是平面上的一个共域,从而最优解必定是在这个平面区域内(包括边界 上)的点。根据目标函数在这个平面区域内的取值找出使目标函数取得最优值 的点(即最优解)。 图解法便于我们理解和了解线性规划问题的一些概念、理论及解的一些特性, 也为我们进一步学习单纯方法提供一个直观图形。 例 5 求解线性问题 xx S 21 57m i n 0, 42 28 . 21 21 21 4 2 xx xx xx tS 解第一步,在平面直角坐标系 xx O 21 上绘出约束条件图(图132) 画出这条直线282 21 xx ,再定出282 21 xx 区域。 把(0,0)代入不等式得 02028,所以,原点所在半平
25、面及直线本身就是 282 21 xx 代表的区域。 画出424 21 xx 这条直线,定出424 21 xx 代表的区域,有( 0,0)代入 不等式得 04042 所以,424 21 xx 代表的区域是包括原点的下半平面与直 线本身。 定出0, 0 21 xx 的区域,它就是第一象限。从图 132 看出,满足全部约束条件的点所构成的区域(即 可行域) ,就是凸多边形 OABC 。 第二步,绘制目标函数图形。对于目标函数 xx S 21 57 将 S看作参数,即得到一簇平行直线(图132 中虚线所 示) ,直线上每一点的目标函数值为S。由图可见,直线离 原点越远, S值越大,我们寻找的是在可行域
26、内使S值最大 点。可见, B点即为可行域内使目标函数最大的点,即为最 优解。 第三步,确定最优解。 B点是直线424282 2121 x 与 xxx 交点,所以 解方程组 424 282 21 2 1 xx xx 得到10,8 21 xx 057 21 xx 5057 21 xx 10657 21 xx 424 21 xx 282 11 xx 精品课程高等数学 (线性代数部分)电子教案 第 10 页 共 10 页 这就是最优解。将其代入目标函数,得最优解10610587max S 例 5 有可行解且有唯一最优解将目标函数改为 xxxx SS 2121 42或仍求其最大值,则BC或 AB上每一点
27、的坐标均为最优解, 最优解有无穷多个, 而它们对应的目标函数数值是28 或 42。读者可以证明习题中第 4 题的(1)小题有可行解但无最优解( 2)小题没有可行解。这就说明了线性规划问 题解的情况。 习题十三 1写出下列问题的数学模型: (1) 某工厂生产甲、乙两种产品,每件纯利为5 元和 4 元,生产这两种产品每件 需机器工作时间2 小时和 3 小时,需人力工时4 小时和 2 小时。已知该工厂 每天能提供 300 小时的机器工作和320 小时的人力工时, 问应如何安排生产, 才能使工厂获利最多? (2) 某产品需经两道工序加工才能完成,共有工人30名,按照过去的经验,第一 道工序每个工人每天能加工产品100 件,第二道工序每个工人每天能加工产 品 200 件,问应如何安排生产才能使连续生产过程中出成品最多? 2将下列线性规划问题的数学模型化为标准形式 (1) xx S 21 32max(2) xx S 21 2min 0,0 22 1 . 21 21 21 xx xx xx tS 0,0 5 4 . 21 21 21 xx xx xx tS 3用图解法解第 1 题。 4用图解法解第 2 题。
链接地址:https://www.31doc.com/p-5522208.html