管理定量分析-规划分析

1、规划分析第8章第8章 规 划 分 析通过本章的学习，读者应理解线性规划在实际生活中的应用，掌握线性规划的求解方法图解法及单纯形法；通过实例分析掌握目标规划的数学模型特点及其简单求解方法图解法，理解目标规划与线性规划问题的关系。(1) 理解线性规划的数学模型及基本概念：基、基变量、非基变量、可行解、可行域、最优解、三大基本定理及其含义。(2) 掌握线性规划的标准形式三大部分：目标函数、约束条件和决策变量。(3) 理解线性规划的解法图解法。(4) 掌握线性规划的解法单纯形法。(5) 掌握目标规划的数学模型。(6) 理解目标规划的解法图解法。本章导读线性规划(Line Programming)是运筹

2、学的一个重要分支。线性规划问题是理论较为完整、应用极其广泛的一门数学规划学科。1939年，前苏联科学家兼经济学家康托洛维奇发表了生产组织与计划中的数学方法一书，第一次详细地介绍了线性规划问题。1947年，美国贝尔电话公司工程师G.B.Dantzig提出了单纯形法，线性规划在理论上趋于成熟，在实际应用中日益广泛与深入。G.B.Dantzig对线性规划理论的提炼和算法改进做出了卓越的贡献。 线性规划继单纯形法提出经历了几十年的发展，其应用日趋增多，已渗透到经济活动的各个领域，特别是电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛，从解决技术问题的最优设计到

3、工业、农业、商业、交通运输、军事、经济计划和管理决策等领域也发挥着各自的作用。线性规划成为重要的现代管理方法之一。1961年，查恩斯(A.Charnes)与库伯(W.W.Cooper)继丹捷格之后提出了目标规划。艾吉利(Y.Ijiri)提出了用优先因子来处理多目标问题，使目标规划得到发展。近10多年来，斯姆李(S.M.Lee)与杰斯开莱尼(V.Jaaskelainen)应用计算机处理目标规划问题，使目标规划在实际应用方面比线性规划更广泛，更为管理者所重视。目标规划在这里指的是线性目标规划，其一个很大的优点就是非常灵活，适用于许多方面，既适用于一个大目标附带有许多从属目标的问题，也适用于许多目标

4、并附有许多从属目标的问题，而且目标的计量单位不像线性规划那样只是单一的，而是可以多种多样的。8.1 线 性 规 划8.1.1 线性规划问题及其数学模型线性规划所解决的问题主要分为两类：一类是在人力、物力资源一定的情况下，如何规划利用这些现有的资源来完成最多的任务；另一类是在任务确定的情况下，如何统筹规划，如何利用最小的人力、物力资源来完成这个确定的任务。一般来说，用线性规划解决一个实际问题时，首先根据待要解决的线性规划问题，分析问题所要实现的目标及所存在的约束条件，建立线性规划的数学模型；其次对该模型利用计算机求解；再次检验解的合理性；最后付诸于实践。下面将通过几个实例来说明线性规划问题建模的

5、思路及其在实际问题中的应用，最后引出线性规划的标准模型。【例8-1】 某工厂计划生产和两种产品，已知生产单位产品所需的两种原材料见表8-1。表8-1 生产单位产品所需的两种原材料产 品现有原材料数量(kg)原材料原材料A原材料B423112050又已知每生产单位产品和分别可获利50元和30元，问应如何安排生产该工厂才能获得最大利润？分析：(1) 确定未知变量，设分别表示产品和的产量。(2) 该工厂的目标是使总利润最大，若用z表示利润，则，总利润最大记成。(3) 各种原材料数量是有限的，由原材料的限量可得到以下不等式：综上所述，可得该问题的数学模型：【例8-2】 某企业生产两种混合配料A和B，每

6、100kg的成本分别为110元和80元。每种产品含三种营养成分，但它们的含量各不相同。在每100kg混合配料中各种营养成分的含量见表8-2。表8-2 每100kg混合配料中各种营养成分的含量混 合 配 料混合配料A混合配料B营养成分营养成分甲(kg)营养成分乙(kg)营养成分丙(kg)1034239现要获得各种营养成分的总量为：营养成分甲至少20kg；营养成分乙至少18kg；营养成分丙至少36kg，问满足这些要求的最低成本为多少？分析：(1) 确定未知变量，设(100kg)分别表示混合配料A和B的需要量。(2) 该企业的目标是使总成本最小，若用z表示成本，则，总成本最小记成。(3) 各种营养成

7、分数量有最低标准，由各营养成分的限量可得到以下不等式：综上所述，可得该问题的数学模型：一般来说，线性规划的数学模型的一般形式为：凡能表示为以上形式的问题统称为线性规划问题。线性规划问题具有以下特征。(1) 线性规划问题的目标能表示为最大化或最小化的问题。例如，求最小成本或人力、投资等，最大化利用材料储备，实现企业的最大利润等问题。(2) 问题的解可以用一组变量来表示，而且解的个数不只一个，即必须要有选择的可能性。(3) 要达到的目标是有限制条件的。(4) 问题的目标和限制条件都能表示为线性表达式。8.1.2 线性规划的标准形式为了讨论问题方便，规定线性规划问题的标准形式为：实际中碰到各种线性规

8、划问题的数学模型都应变化为标准形式后求解。将非标准形式线性规划化为标准形式线性规划时可能出现以下几种可能情况，处理的方法有以下几种。1. 决策变量(1) 决策变量有非正约束，即，令，于是新变量。(2) 决策变量有上下界，即，可将上下界分别处理。令，则新变量且。这时满足了非负要求，上限约束作为新的约束条件按照相应方法转化为等式。(3) 决策变量符号不受限制，即可以为一切实数。令，其中，。2. 目标函数目标函数为最小化，即。令，则得到。3. 约束条件(1) 约束条件为小于或等于形式，即存在约束，这时在不等式左端加上一个非负的新变量即可化为等式，即，新增变量为松弛变量。(2) 约束条件为大于或等于形

9、式，即存在约束，这时在不等式左端减去一个非负的新变量即可化为等式，即，新增变量为松弛变量。(3) 某一等式约束中存在，即存在，令，即在该不等式两边同乘以-1变为：。【例8-3】 将下述线性规划问题化为标准形式。解：(1) 首先分析决策变量，令，其中，。(2) 在第一不等式两边乘以-1得：。在第二不等式左边加上松驰变量，化为等式：，其中。在第三个不等式左边减去松驰变量，化为等式：，其中。(3) 在目标函数两端同乘以-1，同时令，得该线性规划的标准形式为：8.1.3 线性规划的图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。现用图解法求解例8-1，即求解线性规划：如图8.1所示：在以为

10、坐标轴的直角坐标系中，非负条件指第一象限；约束条件代表以直线为边界的左下方的半平面；约束条件代表以直线为边界的左下方的半平面。同时满足例8-1中三个约束条件的点必然位于图8.1中多边形OABC内(包括边界点)，因而此区域为例8-1的可行解的集合，称为可行域。再分析目标函数，它可表示斜率为-5/3的一簇平行线，如图8.2中就是其中一条线，当Z值逐渐增大时，直线向右上方移动，使Z值在可行域OABC的顶点B达到最大值。B点坐标(15，20)即为该线性规划的最优解，即，可计算出最优值：。图8.1 例8-1的可行域 图8.2 例8-1的最优解8.1.4 单纯形法在介绍单纯形法之前，先引入以下几个基本概念

11、。(1) 基：设是约束方程组的系数矩阵，其秩为m。B是矩阵A中的阶非奇异子矩阵()，则称B是线性规划问题的一个基。设：(2) 基向量：基B的列向量称为线性规划问题的基向量。基B中共有m个基向量。(3) 基变量：与基向量相对应的变量被称为基变量，否则称为非基变量。在单纯形法求解线性规划基可行解过程中令所有非基变量为零。现以例8-1为例介绍单纯形法，即求解线性规划问题：(8-1)该线性规划问题的标准形式为： (8-2)容易看出的系数构成一个基：，因此为基变量，为非基变量。基变量可用非基变量表示为： (8-3)将式(8-3)代入目标函数式(8-1)得： (8-4)令非基变量，由式(8-3)可得一个基

12、本可行解：，目标函数值。分析目标函数表达式(8-4)，的系数都是正数，因此，非基变量中任意一个变量取值从零变为正值(变成基变量)，都可能使目标函数值增大，这就是所谓的基变换。为使目标函数值增加幅度最大，选取系数最大的非基变量作为入基变量。下面确定出基变量。由于作为入基变量，仍然是基变量，即，代入式(8-3)可得到：即，也就是说，当新基变量的值增大时，原基变量的值最先降为零，因此选为出基变量。上述基变换过程用单纯形表表示见表8-3。表8-3 例8-1初始单纯形表503000比值004231100112050120/4=3050/2=25503000表中第一行列出了线性规划标准形式中所有变量在目标

13、函数中对应的目标系数，第二列为所有基变量，第一列为基变量在目标函数中对应的目标系数，中间部分数据为各变量在约束条件中对应的约束系数。最下端一行数字对应式(8-4)中各变量系数，又称为检验数，也可通过公式，计算，可以证明基变量对应的检验数为零。线性规划问题取得最优解的判定条件为：若所有检验数，所对应的基本可行解为最优解。箭头表示了入基变量及出基变量的选取方法，其中入基变量的选择方法是：如果存在正的检验数，选取最大的正检验数对应的变量作为入基变量(选取正系数最大的非基变量作为入基变量，使目标函数值增加幅度最大)，即。出基变量的选择依据是选取最小的比值对应的基变量作为出基变量(新基变量的值增大时，原

14、基变量的值最先降为零)，其中比值。经过上述基变换，新的基变量为，非基变量为。根据式(8-3)得出新的基变量表达式： (8-5)将式(8-5)代入目标函数表达式(8-1)，得： (8-6)令非基变量为零，得到另一个基本可行解：，目标函数值。从目标函数表达式(8-6)可以看出，的系数仍为正值，说明目标函数值还可能继续增大，因此需再次进行基变换，方法如前所述。对应单纯形表见表8-4。表8-4 例8-1单纯形表基变换过程一503000比值0500111/210-21/2202520/1=2025/1/2=50050-25表中数字变化方法为，表8-3入基变量和出基变量所在行和列交叉处元素为主元(如表中方

15、框中数字)，对表格中约束系数进行基本行变换，即将主元变为1，主元所在列其他元素变为0，即得表8-4。根据线性规划问题取得最优解的判定条件：若所有检验数，所对应的基本可行解为最优解。因此表8-4中所得基本可行解不是最优解，再次进行基变换得单纯形表，见表8-5。表8-5 例8-1单纯形表基变换过程二503000305001101-1/2-23/2201500-5-151350这时满足线性规划最优解判定条件，即所有，因此，为原线性规划问题的最优解，最优值：。8.2 目 标 规 划目标规划(Goal programming)是运筹学中非常重要的一个分支，最早由美国管理学家彼特德鲁克(Peter F.

16、Drucker)于1954年正式提出，现已由对管理人员进行的目标管理发展成为对企业各项任务的目标管理，已成为一种广泛使用的目标管理方法。线性规划有一致命的弱点，就是目标单一，即寻求某一个目标之最大或最小，这和现代经济社会的要求很不一致。目标规划最重要的特点是强调系统性，采用多目标的统筹安排来替代单目标的制定，通过寻求各目标与成果之间最小差距来达到生产过程中的多目标成果；用“令人满意”的概念来替代“最优”的传统概念，这些都与线性规划有很大的不同。8.2.1 目标规划的数学模型【例8-4】 在例8-1中如果由于某种原因厂长要求：(1) 总利润不小于1200元；(2) 充分利用原材料B。试建立该问题

17、的数学模型。分析：(1) 确定未知变量，设仍分别表示产品和的产量。(2) 该工厂的目标是使总利润不小于1200元，从例8-1的最优解可知该工厂可实现的最大总利润为1350元。为此引入正负偏离变量，其中：高于所定目标的数量低于所定目标的数量则该约束可表示为(3) 充分利用原材料B可表示为。原材料A隐含约束不变，仍为。(4) 确定新的目标函数若决策者想准确实现目标，目标函数形式为：。、为该目标中相应的偏离变量。若决策者想不超过某一目标，目标函数形式为：。若决策者想不低于某一目标，目标函数形式为：。例8-4中第一目标目标函数形式为：。第二目标目标函数形式为：。按照决策者要求，分别赋于这两个目标优先系

18、数p1和p2，并规定p1p2，表示p1比p2有更大的优先权。该问题的目标函数为：。综上所述，可得该问题的数学模型：8.2.2 目标规划的图解法【例8-5】 图解法求解例8-4，即求解目标规划：对只具有两个决策变量的目标规划的数学模型，可以用图解法来求解。由于式(4)变量为非负约束，在平面直角坐标系第一象限内做各约束条件。约束条件(3)的作图与线性规划问题相同，代表图8.3中以直线为边界的左下方半平面；做约束(1)时，先令，做相应的直线，然后在直线旁标上，如图8.3所示，表明该约束条件可以沿所示的方向平移。考虑具有优先因子的目标，在目标函数中要求实现，从图中可以看出，满足的区域位于直线的右上方半

19、平面。同理可以分析约束条件(2)所代表区域为直线2x1+x2=50上位于第一象限内所有的点。约束条件(3)代表区域为直线4x1+3x2=120的左下方平面。综合分析上述约束条件，得出该目标规划问题的解为虚线段AB上所有的点。图8.3 例8-6 可行域及最优解8.3 案例应用分析应用线性规划方法辅助高校经济决策1【案例说明】在社会主义市场经济条件下，高等学校在办好本科和研究生教育的同时如何发挥学科优势，利用学校现有房屋、设备、场地、科技和人才开展对外服务，提高经济效益已成为高校管理决策中的重要问题。一切生产过程都要发生活劳动和物化劳动的消费，精神产品和物质产品一样都有一个成本问题，对外服务发生的

20、支出应从对外服务收入中获得补偿，如果不注重这部分成本的计算，就可能会发生挤占预算拨款或发生纯收入不“纯”的问题。段海艳. 提升高校财务管理水平的途径D. 西安：西北工业大学，2003.因此高校开展对外服务之前都要对其成本进行测算，定出其服务价格，比如一个班国家批准计划招收学生30名，而教室可坐40名学生的情况下，不增加师资、教室再招10名插班生，仅有增量活动的追加成本，便可降低收费标准，招收10名插班生的收费价格在市场同行业学校中是有竞争力的。但是在对外服务项目中有很多复杂的因素要考虑，而利用线性规划可以解决这种成本最小、价格最优、利润最大的问题测算。【案例分析】1. 分析资料用线性规划解决对

21、外服务成本测算问题可按以下三步进行。(1) 提出问题。从高校管理与决策的立场出发，研究对外服务各项目方面的成本支出、资金分配及使用问题，当然也可依本单位的业务性质及管理的需要拟定对象。(2) 建立线性规划模型。线性规划模型是用数学符号和函数关系式来描述研究对象各因素之间数量上本质联系的数学表达式。线性规划模型一般由以下三要素构成: 决策变量：即决策者对问题需要考虑和控制的因素，如招收学生数量多少的确定，需要考虑教室、食堂、学生宿舍容纳数量，图书资料可供借阅人次，基础及专业教师等因素，即一组未知数。这些因素可记为或。 约束条件：即决策者为实现目标函数最优、最大或最小的一些限制条件，如学校的教职工

22、人力限制、校舍限制、教学仪器设备的限制等。可建立如下约束条件： 目标函数：即决策者欲达到的最优目标与决策变量之间相互关系的数学表达式。它是要求实现最大化或最小化的问题。如学校在现有条件下办学规模最优、效益最大；或学校在现有条件下对外服务支出成本最低利润最大；即目标函数达到最大值或最小值。目标函数如下：。(3) 求解线性规划模型。即根据建立的模型采用单纯形法求出使目标函数值最大或最小的各决策变量的数值作为安排工作的参考。2. 建立该问题的数学模型，测算学校招生结构下面将建立该问题的数学模型并用单纯型法求解，再根据求得的决策变量的值来说明线性规划的具体运用。设为国家任务学生数；为全脱产成人教育或定

23、向生；为自考或者函授生。那么，依前面给定的目标函数，该校每年所得的收入应该是：。上式中是可以变化的，是根据该校在校学生历史、当前和将来的情况测算的各类学生数，称它为决策变量。一旦的数值决定下来，Z也就决定下来了。上式中变量前的系数为收费和拨款标准，假设类学生每年拨款约3000元加学杂费2000元，合计5000元，得到收款额；类学生交学杂费3000元，得到收款额3000；类学生交学费1000元，得到收款额1000。在这个问题中，决策变量的取值并不是完全自由的，而是受到一些变化中的条件的制约。这些限制条件为问题的约束条件。设有如下约束条件：(1) 校舍能力限制。由于学生食堂、宿舍、教室建筑平米数的

24、限制，能容纳学生数量也受限制，假定上例能容纳全日制学生3000名，约束条件：。(2) 师资力量的限制。由于学生在校学习的课程及门数与教师人数及专业有关，与基础课与专业课的搭配结构有关，故对上例做如下假设：在校教师约210人，学生人数为每班50人；任课方式有单班课和合班课，依工科本、专科的情况，学生平均每届应学课程为20门课，平均每年完成为5门课。另外，3、4个班的合班课为基础课，占整个上课比例的5%或10 %；2个班的合班课为专业基础课，占整个上课比例的20%、30%或40%；1个班的单班课为专业课，占整个上课比例的70%、50%或40%。于是，有如下约束条件：简化为：。(3) 后勤支出能力限

25、制。由于在校生需使用水、电、暖等，其各类学生消耗成本不一样，上例按类每生每年消耗700元，类每生每年消耗500元，类每生每年消耗300元，水电暖耗费取为250元，则约束条件为：(4) 受国家任务限制。由于目前我国培养本专科生是国家教委下达培养任务，而建校规模是按教育发展目标建立的，上例国家任务为1900，则约束条件：。至此可建立以下模型 (max表示最大，s.t.表示约束条件)：3. 求解及结果分析用单纯形法求解得：最优解，；最优值。以上求得最优解为：国有任务类学生1900名；全日制成教或定向生1100名；函授生600名；其收入值为1340万元。依此，学校在完成国家任务每年培养1900名本科生

26、的同时，又可培养定向生1100名，函授生600名，扣除本科生的收入值950万元(19005000)，可在不增添设施的前提下多收入390万元。例中设定的系数随着测算目的和时间的变化应做相应的调整。在不同的条件下变动其值又可得出变动后的最优值，这就为管理决策提供了较为坚实的依据。以上用单纯形法测算学校某个时点上办学招生方面的结构和收入情况，用此方法还可预测不同时期不同情况的办学、科研、后勤服务等结构及收入值，若使用图解法、特殊模型法亦可编成应用程序输入计算机，则对不同的约束条件，即可求得优化值，供决策参考，使用很方便，并能提高学校财务管理决策的质量和工作效率。本 章 小 结本章第一部分通过实例引出了线性规划的建模思路及数学模型；第二部分介绍了线性规划问题的标准形式及一般线性规划问题化为标准形式的方法；第三部分介绍了求解线性规划问题的图解法，图解法简单直观并反映了线性规划的求解原理，但其只适用于含有两个或三个变量的线性规划问题；第四部分介绍了线性规划问题的单纯形解法，通过案例简单介绍了该方法的求解过程及原理，给出了单纯形表的变化过程；最后介绍了目标规划的数学模型及图解法，线性规划的缺点就是目标单一，在一组约束条件下，求某一个目标之最大或最小，这和现代经济社会的要求很不一致，目标规划一个很大的优点就是非常灵活，适用于许多方面。习 题1. 试建立下列问题的数学模型：(1) 某厂生产甲