第10章 经管专业应用数学

第10章经管专业应用数学10.1行列式矩阵及其应用(见第3章)10.2概率统计及应用(见第4章)10.3线性规划的数学模型及其标准形式10.4线性规划问题的图解法10.5线性规划问题的单纯形解法返回10.3线性规划的数学模型及其标准形式线性规划是最重要的优化方法.1947年线性规划被成功地运用于工业、交通、农业和军事等各个领域，随着计算机的普及，它的适应领域越来越广泛.线性规划研究的问题主要有两类:一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务，数学上即是求“最小值”.二是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多，数学上即是求“最大值”.其实这两类问题是一个问题的两个方面，就是所谓寻求整个问题的某个整体指标最优的问题.如:生产的组织与计划问题;运输问题;合理下料问题;配料问题;布局问题;分配问题;投资问题，等等.10.3.1线性规划问题的数学模型下一页返回10.3线性规划的数学模型及其标准形式在生产实践和日常生活中，经常会遇到规划问题.所谓规划问题，简单地说，是指如何最合理地利用有限的资源(如资金、劳力、材料、时间等)，以便使生产的消耗最小，利润最大.如果利用数学方法来进行这种分析，这就是数学规划.当所建立的模型，都是线形代数方程时，这就是一个线性规划问题.这样的例子在管理和生产的实践中是很多的，我们现举一些例子来加以说明.例10-1生产问题:某工厂生产A,B两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表10-1所示.问如何制订生产计划使两种产品总利润最大?上一页下一页返回10.3线性规划的数学模型及其标准形式解这是一个企业在组织生产以前需要从宏观上进行规划的问题.假设生产A产品x公斤，B产品y公斤.得到利润x=7x+12y万元，我们的目标是使利润最大，我们称这个函数为目标函数.上一页下一页返回10.3线性规划的数学模型及其标准形式上一页下一页返回10.3线性规划的数学模型及其标准形式例10-2运输问题:设有两个砖厂A1,A2.其产量分别为23万块与27万块.它们生产的供应B1、B2、B3三个工地.其需要量分别为17万块、18万块和15万块.自各产地到各工地的运价如下表10-2所示.问应如何调运，才使总运费最省.上一页下一页返回10.3线性规划的数学模型及其标准形式我们的目标是使总运费最小，我们称这个函数为目标函数.上一页下一页返回10.3线性规划的数学模型及其标准形式上一页下一页返回10.3线性规划的数学模型及其标准形式上述例子虽然有不同的实际内容，但是都可归结为一类优化问题.从数学上说它们具有以下共同特征:(1)每一个问题都是求一组变量(称为决策变量)的值.这组变量的一组定值就代表一个具体方案.通常要求这组变量的取值是非负的.(2)存在一定的限制条件，称为约束条件.这些约束条件都可以用一组线性等式或不等式来表示.(3)都有一个期望达到的目标，并且这个目标可以表示为决策变量的线性函数(称为目标函数).按所研究问题的不同，要求目标函数值最大值或最小值.我们将具有上述三个特点的最优化问题归结为线性规划问题，其数学模型称为线性规划问题的数学模型，简称线性规划数学模型.上一页下一页返回10.3线性规划的数学模型及其标准形式例10-3广告方法的选择问题:某公司要求销售部经理制订一个广告计划，计划用经费10000元，要求尽量多的人能看到广告.该经理选择了三种广告方法:电视、广播电台和报纸.根据调查各种广告的费用如下:在地方电视台下午播放1.5分钟要1000元，晚上要2000元.该经理决定在电视上作广告至少两次，但不多于四次.在地方报纸作半页广告费是300元，一页要1000元.在)’一播电台上作广告的价格是，自天每半分钟600元，晚上每半分钟400元.公司限制用电台作广告的次数，自天最多不超过5次，晚上不超过3次.根据该经理所获得的资料估计，在下午观看电视)’一告节日的大约有40000人晚上有90000人.看日报的大约有60000人，并估计其中1/2的人看整页的)’一告1/3的人看半页的广告.广播电台的听众自天有40000人，晚上有30000人.上一页下一页返回10.3线性规划的数学模型及其标准形式解设在下午用电视作广告的次数为x11，在晚上用电视作广告的次数为x12;在白天用电台作广告的次数为x21，在晚上用电台作广告的次数为x22;在报纸上登半页广告的数目为x31，在报纸上登整页广告的数目为x32.其目标要求是尽量多的人能看到)’一告的宣传，所以目标函数是：受到的约束条件是:上一页下一页返回10.3线性规划的数学模型及其标准形式例10-4连续投资问题:某部门在今后5年内考虑给下列项目投资10万元，已知:项目A:从第1年到第4年每年初需要投资，并于次年末回收本金的1.15倍;上一页下一页返回10.3线性规划的数学模型及其标准形式项目B:第3年初需要投资，到第5年末回收本金的1.25倍，但规定最大投资额为4万元;项目C:第2年初需要投资，到第5年末回收本金的1.40倍，但规定最大投资额为3万元;项目D:每年初投资，每年末回收本金的1.06倍.求怎样投资使5年末总资本最大?解：设

分别表示第i年年初项目A,B,C,D的投资额.根据题意可以确定出各个项目的投资和收益表，如表10-3所示:上一页下一页返回10.3线性规划的数学模型及其标准形式上一页下一页返回10.3线性规划的数学模型及其标准形式由此我们建立目标: 受到的约束条件:由于项目D每年都可以投资，并且于当年末即能回收本息.所以该部门每年应把资金全部投出去.这样每年年初的投资额应等于上一年年末回收的资金总额，第一年年初的投资总额为该部门初期拥有的资金额10万元.因此根据以上表格可以得到如下约束，上一页下一页返回10.3线性规划的数学模型及其标准形式上一页下一页返回10.3线性规划的数学模型及其标准形式10.3.2线性规划问题的标准型从前面的例子我们知道线性规划问题有各种形式，如目标函数有的是求极大值，有的是求极小值;约束条件一也有“≤”，“=”，“≥”三种形式.现规定线性规划问题的标准形式为上一页下一页返回10.3线性规划的数学模型及其标准形式它具有下述特点:(1)求目标函数的最大值;(2)约束条件中均为等式，并且等式右端的常数为非负;(3)所有变量为非负.线性规划问题都可以化为标准形，其方法为:上一页下一页返回10.3线性规划的数学模型及其标准形式该条件转化为：上一页下一页返回10.3线性规划的数学模型及其标准形式上一页返回10.4线性规划问题的图解法在线性规划问题中，建立了数学模型后，还需要求解出满足约束条件且使目标函数达到最大值或最小值的决策变量值，即求解线性规划问题.对于两个变量的线性规划问题，我们可以用图解法求解.这一节的目的是通过两个变量的线性规划问题的图解法，了解线性规划问题解法的特点及相关的一些概念，从而为学习线性规划问题的一般解法一单纯形法打下基础.10.4.1两个变量的线性规划问题的图解法下一页返回10.4线性规划问题的图解法解将约束条件中的不等式改为等式，分别为:2x+3y=12与2x+y=8，x=0，y=0它们分别表示平面直角坐标系内的一条直线作出各直线，如图10.1所示:上一页下一页返回10.4线性规划问题的图解法图中的封闭图形(ABC为一个凸多边形，这个凸多边形内及其边界上的点都满足约束条件(即不等式的解).特别地，凸多边形的四个顶点O(0,0)、A(0,4)、B(3,2)、C(4,0)均为约束条件(不等式)的解.下面我们来讨论目标函数z=6x+7y.让z取一些确定的值，如令z=0,1,2,3…就得到一束直线，这些直线的斜率都等于-6/7，因止匕它们是才目互平行的，而在每一条直线上，目标函数z值都目等，因此称这种直线为等值线.我们将其中的一条等值线0=6x+7y在凸多边形内平行移动，最后与凸多边形的顶点召相交.故B点为该规划的最优点.结合图像，点B是直线2x+3y=12与直线2x+y=8的交点，因此解联立方程组上一页下一页返回10.4线性规划问题的图解法得点B的坐标为(3,2)，代人目标函数得z=6X3+7X2=32.解将约束条件中的不等式改为等式，得x=4、y=3、x+2y=8.在平面直角坐标系内作出各直线.如图10.2所示.上一页下一页返回10.4线性规划问题的图解法从图中可以知道满足约束条件的最优点有无数多个.

在线段BC上的每一个点都是最优解.故目标函数的最大值为z=8.由以上的例子可以得出用图解法求解二元线性规划问题的一般步骤:(1)直角坐标系中作出满足约束条件的范围一凸多边形(区域);(2)在同一直角坐标系中作出目标函数的等值线;(3)观察凸多边形与等值线簇，找出既在凸多边形的边界上又使目标函数达到最大或最小的点(或边);(4)联立求解边界直线所构成的方程组，得到解并带人目标函数得到最优值.一般地，我们把满足约束条件的解称为可行解;所有可行解构成的集合称为可行解集(或可行域);使目标函数达到最大或最小的可行解称为最优解.上一页下一页返回10.4线性规划问题的图解法10.4.2线性规划问题解的特点由上面的图解法可以直观地看出线性规划的解具有如下几个特点:(1)如果一个线性规划问题确实存在唯一的最优解，那么它必定是凸多边形的一个顶点.(2)如果一个线性规划问题存在多个最优解，那么至少有两个相邻顶点是此线性规划问题的最优解.(3)一个线性规划问题的解只存在有限个顶点可行解.(4)如果一个顶点可行解的目标函数值比相邻的顶点可行解的目标函数值要好的话，那么它就比其他所有顶点可行解的目标函数值要好，或者说它就是一个最优解.从上面的这些特点我们可以得到求解线性规划问题的一种简单方法，上一页下一页返回10.4线性规划问题的图解法这就是把所有的顶点可行解都求出来，然后带人目标函数求出每个顶点可行解的目标函数值，并对它们进行比较，显然其中最大(或最小)的解就是最优解.当顶点可行解的个数比较多时，我们可以用第四个特点来进行讨论.这时我们只需讨论相邻的顶点可行解就可以了，当出现一个顶点可行解的目标函数值比相邻的顶点可行解的目标函数值要好的时候，线性规划问题的求解就结束了.上一页下一页返回10.4线性规划问题的图解法10.4.3线性规划问题解法的特点——单纯形法的思想由上面的图解法所得到的线性规划解的特点，我们可以得出求解线性规划问题的一般方法一单纯形法的思路，这就是:(1)从一个顶点可行解(如(0,0>开始一起步;(2)向邻近的一个使目标函数值更好(较大或较小)的顶点可行解移动一重复步骤;(3)检查此顶点可行解是否比所有邻近的顶点可行解都好.如果是，那么它就是最优解一最优性检查规则.如例10-6的图中，我们可以从点O出发经过两条线路到达最优点B，即(1)O→A→B，

(2)O→C→B.上一页返回10.5线性规划问题的单纯形解法10.5.1线性规划问题的解上面我们通过两个二维问题的例子从几何上说明了线性规划问题解的特点.这一节我们将从代数上介绍线性规划问题解的基本概念，以及它与几何解的对应关系.定义10.1可行解:满足约束条件的解称为线性规划问题的可行解，下一页返回10.5线性规划问题的单纯形解法所有可行解的集合称为可行域.如上一节例10-1图中的凸多边形及其内部.定义10.2最优解:满足目标函数的可行解称为线性规划问题的最优解.如上一节例10-1图中的凸多边形的顶点B的坐标.定义10.3基本可行解:满足非负条件的基本解称为线性规划问题的基本可行解.如上一节例10-1图中的凸多边形的所有顶点(O,A,B,C)的坐标.上一页下一页返回10.5线性规划问题的单纯形解法10.5.2单纯形解法建立初始基本可行解:在线性规划问题中，约束条件多为不等式，所以我们首先要将其化为标准型，同时建立一个初始基本可行解.上一页下一页返回10.5线性规划问题的单纯形解法其中初始基本可行解为(0,0,12,8).列表如表10-6所示.上一页下一页返回10.5线性规划问题的单纯形解法最优解检验规则:当我们找到一个基本可行解之后，要判断它是不是最优解.判断的方法是检查目标函数中的系数是否还有正的系数，若有正系数存在，则说明还有更好的解.如本例上表中目标函数的(6,7,0,0)，这说明当减少x3，x4，时不会使Z的值减少，而增加x1，x2的值却可以使Z的值增加.这说明目前的解不是最优解，只有当目标函数的全部系数为负值或0时，该解才是最优解.进行迭代:确定换人变量，由目标函数可知x2的系数比x1的系数大，即同样增加一个单位的值，7x2增加7,6x1增加6，所以我们选择x2为换入变量.从约束条件中，我们选择同时满足所有约束条件的x2的最大解min{b/xi}.如下表10一7.上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法上一页下一页返回10.5线性规划问题的单纯形解法10.5.3表解形式的单纯形法上面介绍的单纯形法求解计算比较麻烦，所以我们一般采用表解的方法使其规格化.只是需要指明换人变量就可以了.如上例10-8的求解，用表解形式如表10一10.上一页下一页返回10.5线性规划问题的单纯形解法所以线性规划问题的最优解为(3,2)，目标函数的最大值为32.例