线性规划在企业决策中的应用

《线性规划在企业决策中的应用》由会员分享，可在线阅读，更多相关《线性规划在企业决策中的应用（28页珍藏版）》请在金锄头文库上搜索。

1、页眉线性规划在企业决策中的应用第一章 线性规划理论1. 线性规划简介 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题1。满足线性约束条件的解叫做可行解

2、，由所有可行解组成的集合叫做可行域2。决策变量、约束条件、目标函数是线性规划的三要素。2. 线性规划的发展历程 法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。 1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。 1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。 1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951年美国经济学家T.C

3、.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。 50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题3。 1979年苏

4、联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。建立线性规划模型的方法。3. 线性规划的数学模型及其标准形式3.1 线性规划问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。线性规划主要解决两类问题：（1）资源有限，要求生产的产品（或利润）最多。

5、（2）任务（或产品）一定，要求消耗的资源（或成本）最少。3.2 线性规划问题的特征（1）每一个问题都用一组决策变量表示某一方案；这组决策变量的值就有代表一过具体方案。 （2）一般这些变量取值是非负的。 （3）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 （4）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上四个条件的数学模型称为线性规划的数学模型。3.3 从实际问题中建立数学模型的步骤；（1）根据影响所要达到目的的因素找到决策变量；（2）由决策变量和所在达到目的之间的函数关系确定目标函数；（

6、3）由决策变量所受的限制条件确定决策变量所要满足的约束条件。3.4 所建立的线性规划模型的特点；（1）每个模型都有若干个决策变量，其中为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。（2）目标函数是决策变量的线性函数，根据具体问题可以是最大化或最小化，二者统称为最优化3。（3）约束条件也是决策变量的线性函数。3.5 线性规划模型的一般形式目标函数： (1-1)约束条件： (1-2)在线性规划的数学模型中，方程（3-1）称为目标函数；（3-2）称为约束条件。3.6 线性规划模型的标准形式 (1-3) (1-4)其中.简写形式为： (1-5) (1-6)向量和矩阵表示： (

7、1-7) (1-8)其中 ，4. 线性规划的解法求解线性规划问题的基本方法有图解法和单纯形法，但实际运用的主要是是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题5。它的特点是直观而易于理解，但实用价值不大。不过通过图解法求解可以理解线性规划的一些基本概念。下面着重介绍单纯形法。4.1 一般线性规划问题的单纯形解法4.1.1 建立初始基本

8、可行解在线性规划问题中，约束条件多为不等式，所以首先要将其化为标准型，同时建立一个初始基本可行基。4.1.2 最优解检验找到一个可行判断它是不是最优解。判断方法是检验目标函数中是否还有正的系数，若有正的系数，则说明还有更好的解。只有当目标函数中的全部系数为负值或0时，说明改解才是最优解。4.1.3 基变换从一个基可行解到另一个基可行解的变换就是进行一次基变换。4.1.4 迭代（旋转运算）将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或Gauss变换变为单位矩阵6。4.2 非标准型线性规划问题的解法4.2.1 大法在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值无

9、影响，为此可取人工变量在目标函数中的系数为(为非常大的正数)7，这样目标函数要实现最大化，人工变量只能取零，因此必须把人工变量从基变量中换出，否则目标函数就不可能实现最大化。4.2.2 两阶段法第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加上人工变量，构造仅含人工变量的目标函数和要求实现最小化。第二阶段：将第一阶段得到的最优单纯形表，除去人工变量，将原目标函数的系数换掉该表的目标函数的系数行，作为第二阶段计算的初始表。4.3 对偶分析4.3.1 对偶问题的基本概念在线性规划问题中，如果把一个求最大值的线性规划定义为“原”问题，那么与其同时存在一个求最小值的所谓对偶问题，并且原线性规

10、划的最优解对应着对偶线性规划问题的最优解。4.3.2 对偶问题的性质（1）对称性 对偶问题的对偶是原问题。（2）弱对偶性 若是原问题的可行解，是对偶问题的可行解。则存在。（3）无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（4）可行解是最优解时的性质 设是原问题的可行解，是对偶问题的可行解，当时，,是最优解。 （5）对偶定理 若原问题有最优解，那么对偶问题也有最优解且最优值相同。 （6）互补松驰性 若,分别是对偶问题和原问题的可行解。那么和,当且仅当,为最优解。4.4灵敏度分析灵敏度分析主要有以下几种情况8： （1）资源数量变化的分析； （2）目标函数中价值系数的变化分

11、析； （3）技术系数的变化； （4）约束条件增减的变化分析。第二章 企业决策理论1. 企业决策概述 随着企业计算机应用和信息化程度的不断深入，企业已经积累了大量的业务和财务数据，并继续随着时间和业务的发展而呈几何级膨胀趋势。企业信息处理部门的工作重点已逐渐超越了简单的数据收集，企业内的各级人员都希望能够快速、准确并方便有效地从这些大量杂乱无章的数据中获取有意义的信息，决策者也希望能够充分利用现有的数据指导企业决策和发掘企业的竞争优势9。决策效率和决策质量的高低将直接影响企业的运营绩效和市场竞争力。由于集团企业具有分布、异构、自治等特点，集团企业运营过程中的决策将是一个复杂的过程，对于不同的决策

12、问题需要采用不同的决策方法。同时，在集团企业运营过程中，决策的形式也是多种多样的，它在一定的阶段表现为个体的行为，在一定的阶段又表现为群体的活动，从而给集团企业管理中的决策分析提出了高要求。2. 企业决策分类2.1 按重要程度分类在企业的决策中，我们按重要程度分类一般把决策分为三个层次，即战略决策、战术决策和业务决策10。2.1.1 战略决策第一类战略决策是与管理总的方针和开发企业所需要的资源有关的决策，它属于长远规划，对企业的发展具有深远影响，决策过程中要考虑很多不确定和冒风险的因素。是集团企业决策信息模型中的最高层，负责管理、控制、协调整个集团企业网络的正常运行。其控制范围包括涉及集团企业

13、全体成员整体利益的事务和对整个企业集团运营活动的调控与制约。在这一层次，可以设定集团企业决策模型的范围和内容、集团企业的合作机制和行为准则的设定、运营过程的绩效评价、利益分配机制和风险控制机制等任务，为集团企业正常运营提供了战略决策框架和行动指南。根据集团企业实际情况进行群体决策，担负着全局优化以及在新机遇下的集团企业组建过程中的决策工作。2.1.2 战术决策第二类决策称为战术决策，是在物资资源、设备等决策之后，规划如何最有效的分配所获得的资源（如生产能力、资金、材料、劳力等），以便获得最大效益。定义集团企业各成员企业的各种基本决策活动过程。虽然由于集团企业的动态特性，各企业的实际情况和操作流

14、程会有所不同，但我们总能找到一些存在于企业业务活动中相对稳定且有相同或类似行为特征的实体。同时也能找出系统中不能再分的最小粒度的原子过程，利用技术，我们将企业中的各类实体和原子过程封装成对象，根据产品结构信息和集团企业实际运行状态信息，将客户的订单分解到集团企业的各成员企业，并派生出由不同的原子过程组成的工作流，对资源进行分配，并完成对工作流监督、控制的任务。2.1.3 业务决策第三类叫业务决策，完成集团企业具体任务的执行工作，包括物流在各企业间的合理流动以及从原材料到成品的物理加工过程，如原材料的运输、零件加工、部件装配、检测、仓储等过程。在本层中，完成制造、销售、供应、运输等任务的同时，还要对第一线的信息进行采集、整理、反馈以供上层决策时使用。是在资源合理分配后，进行日常业务和计划的决策，线性规划模型最适合进行战术决策，解决诸如劳动力和生产能力等资源的合理分配，运输和指派方案的最优选择、广告和推销费用的预算等问题，同时它也在投资方案选择、配料、选址、生产计划、环境（如空气、水）污染控制、下料等优化方面有广泛的应用。2.2 按企业决策的环境分类在企业的决策中，我们按企业决策的环境可分为确定性决策、风险决策和不确定性决策。2.2.1 确定性决策确定性决策是指未来环境完全可预测，而且在此确定的未来环境下待选择的决策方案的后果也是可以确定的。简单讲，就是一种方案只有一种