线性规划与数学建模简介.pdf

精品课程高等数学 （线性代数部分）电子教案 第 1 页 共 10 页 第十三章线性规划与数学建模简介 【授课对象】 理工类专业学生 【授课时数】 6 学时 【授课方法】 课堂讲授与提问相结合 【基本要求】 1、了解数学模型的基本概念、方法、步骤； 2、了解线性规划问题及其数学模型； 3、了解线性规划问题解的性质及图解法. 【本章重点】 线性规划问题 . 【本章难点】 线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤，并以几个典型线性规划问题 为例，介绍构建数学模型的方法及其解的性质。 §1 数学建模概述 一、数学建模 数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问 题的一种科学方法。运用这种科学方法，必须从实际问题出发，遵循从实践到认识 再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实 际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研 究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过 程。 二、数学模型的概念 模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律Fma就是一个典型的（数学）模型。一般地， 可以给数学模型下这样的定义：数学模型是磁于以部分现实世界为一定目的而做的 抽象、简化的数学结构。 通俗而言，数学模型是为了一定目的对原型所作的一种抽象模拟，它用数学 式子，数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程： 1. 建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此，我们首先要发现这类需要解决的实 际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划，组织 必要的人力、物力等，确立建模课题。 2模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进 行抽象简化，人们就无法准确把握它的本质属性，而模型假设就是根据建模的目的 对原型进行抽象、简化，抓住反映问题本质属性的主要因素，简化掉那些非本质的 精品课程高等数学 （线性代数部分）电子教案 第 2 页 共 10 页 次要因素。有了这些假设，就可以在相对简单的条件下，弄清各因素之间的关系， 建立相应的模型。 合理的假设是建立理想模型的必要条件和基本保证。如果假设是合理的，则模 型切合实际，能解决实际问题；如果假设不合理中或过于简化，则模型与实际情况 不符或部分相符，就解决不了问题，就要修改假设，修改模型。 3构造模型 在模型假设的基础上，开始构建数学模型。首先分析变量类型，恰当使用数学 工具。一般而言，如果实际问题中的变量是确定型变量，数学工具可采用微积分、 微分方程、线性或非线性规划、投入产出、确定性库存论等。如果变量是随机变量， 数学工具可采用概率与统计、排队论、对策论、决策论、随机微分方程、随机性库 存论等。其次，抓住问题本质，简化变量之间的关系。可以说，数学的任一分支在 构造模型时都可能有用，而同一实际问题也可以构造不同的数学模型。一般而言， 在能够达到建模目的前提下，所用的数学工具应力求简单、易解，但要保证模型的 解的精确在允许的范围内。 4模型求解 不同的模型要选择或设计不同的数学方法和算法求解，许多模型还可以通过编 写计算机程序软件包，借助计算机快速完成对模型的求解。 5模型分析 对模型的求解结果进行分析，主要包括稳定性分析，参数的灵敏度分析，误差 分析等。通过分析，若发现不符合建模要求，就要修改或增减建模假设条款，重新 构造模型，直到符合要求。若模型符合要求，则可以对模型进行评价是、预测民、 优化等方面的探析，力争得到最优模型。 6模型检验 对于经过分析后符合要求的模型，还要把它放回到实际对象中去进行检验，看 它是否符合实际，能否解决相应的实际问题。若不符合实际，就要修改前提假设， 重新建模，重新分析，直到获得符合实际的模型。 7模型应用 建模最终目的，是用模型来分析、研究和解决实际问题。因此，一个成功和数 学模型必须能够在实践中得到成功的应用，甚至形成一套科学和理论。图13 1 是上述各步骤的直观图： 一、数学模型的分类 数学模型按照不同的分类标准有许多种类： 1按照模型的数学方法分，有几何模型、代数模型、图论模型、微分方程模型 建模准备 （分析实际问题 确立课题） 建模假设 （抽象、 简化） 构建模型 模型求解模型分析 （是否相符） 模型分析 （是否相符 模型应用 图 13 1 数学建模步骤示意图 精品课程高等数学 （线性代数部分）电子教案 第 3 页 共 10 页 概率模型、最优控制模型、随机模型等等。 2按模型的特征分，有静态模型和动态模型，确定性模型和随机模型，离散模型和 连续性模型，线性模型和非线性模型等。 3按模型的应用领域分，有人口模型、交通模型、经济模型、生态模型、资源模型、 环境模型等。 4。按建模的目的分，有预测模型、优化模型、决策模型、控制模型等。 5按夺模型结构的了解程度分，有白箱模型、灰箱模型、黑箱模型等。 §2 线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛 的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以 最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现 有条件下进行组织和安排，以完成更多的工作。因此，线性规划就是求一组变量的 值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。 一、运输问题 例 1 设有 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 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 300700400400300600min 结束条件 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) 则该问题数学模型为： 求变量 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 nm ,.,., 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 的值最大。 三、配料问题 例设有 AA 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 bxCxCxCa bxCxCxCa bxCxCxCa i m nnmnnnn mm mm 并使目标函数 xdxd mm S. 11 最小。 二、线性规划问题数学模型的一般形式和标准形式 上面我们建立了经济领域中常见的实际问题的数学模型，尽管这些实际问题本身是 多种多样的，但是它们的数学模型却具有相同的特征：要确定某些变量( 决策变量 ) 的一组值，使得在确定的确定的约束条件下，目标函数是取得最大值或最小值。其 中，约束条件是决策变量的线性方程或线性不等式。目标函数是决策变量的线性函 数。因此，我们把这种规划问题称为线性规划问题。同时，我们可以得到对于一个 线性规划问题，其数学模型应具有如下形式： 求 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). 由此可见，一个线性规划问题问题的数学模型，必须含有三个要素：决策变量、 约束条件和目标函数。 由上面的例子可知，线性规划问题的数学模型的一般形式很多。目标函数有求 最大值和最小值；约束条件有“”， “” ， “”三种情况。这种多样性给问题的 讨论带来很大的不便。为此，我们介绍线性规划问题的一种统一形式标准形式。 规定线性规划问题的数学模型的标准形式为： 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 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 ： 则加入一个新变量，将其约束条件改为： 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 ,且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）基础可行解 ：若可行解 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的极点。例如，圆周上的点都是极点。 （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至少有一极点，且极点的个数有限。 性质 4 最优值可以在极点上达到。 这几条性质实际上给我们指出了线性规划问题求解的思路和方向：由于线性规 划问题的最优解一定能在可行解集的极点达到，而极点的数目中有限的。所以，总 可以想办法在有限的极点中经过有限次寻找，得到最优解。因而，就有了求解线性 规划问题的图解法和单纯形法。由于篇幅所限，下面仅介绍图解法的应用。有兴趣 精品课程高等数学 （线性代数部分）电子教案 第 9 页 共 10 页 的读者可以学习一下单纯形法。 二、图解法（又称几何法） 图解法是对于只是两个决策变量的线性规划问题，在平面内建立直角坐标系， 使每个决策变量的取值在一个数轴上表示出来，可行解就成为平面上的点，可 行域就是平面上的一个共域，从而最优解必定是在这个平面区域内（包括边界 上）的点。根据目标函数在这个平面区域内的取值找出使目标函数取得最优值 的点（即最优解）。 图解法便于我们理解和了解线性规划问题的一些概念、理论及解的一些特性， 也为我们进一步学习单纯方法提供一个直观图形。 例 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，所以，原点所在半平面及直线本身就是 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值越大，我们寻找的是在可行域内使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上每一点的坐标均为最优解， 最优解有无穷多个， 而它们对应的目标函数数值是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 题。