信息与计算科学外文翻译.doc

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）资源有限，要求生产的产品（或利润）最多。（2

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

6、由决策变量所受的限制条件确定决策变量所要满足的约束条件。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)向量和矩阵表示： (1-

7、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 业务决策第三类叫业务决策，完成集团企业具体任务的执行工作，包括物流在各企业间的合理流动以及从原材料到成品的物理加工过程，如原材料的运输、零件加工、部件装配、检测、仓储等过程。在本层中，完成制造、销售、供应、运输等任务的同时，还要对

15、第一线的信息进行采集、整理、反馈以供上层决策时使用。是在资源合理分配后，进行日常业务和计划的决策，线性规划模型最适合进行战术决策，解决诸如劳动力和生产能力等资源的合理分配，运输和指派方案的最优选择、广告和推销费用的预算等问题，同时它也在投资方案选择、配料、选址、生产计划、环境（如空气、水）污染控制、下料等优化方面有广泛的应用。2.2 按企业决策的环境分类在企业的决策中，我们按企业决策的环境可分为确定性决策、风险决策和不确定性决策。2.2.1 确定性决策确定性决策是指未来环境完全可预测，而且在此确定的未来环境下待选择的决策方案的后果也是可以确定的。简单讲，就是一种方案只有一种确定的结果。2.2.

16、2 风险决策风险决策是指未来环境有几种可能的状态和相应的后果，人们无法得到关于未来环境的充分可靠的信息，但可以预测每一种状态和后果出现的概率。对利润、效益等问题的决策一般都是风险型决策2.2.3 不确定性决策不确定性决策是指未来环境出现某种状态的概率难以估计，甚至连可能出现的状态和相应的后果都是未知的。这类决策，主要依靠决策者的经验和主观判断。2.3 按企业决策的主体分类在企业的决策中，我们按企业决策的主体可分为个人决策和群体决策。2.3.1 个人决策个人决策是指决策的主体是一个人，即最终方案的选择仅仅由一个人拍板决定。 2.3.2 群体决策群体决策是指决策的主体是两人或两人以上。企业中许多重

17、要的决策都是由决策群体制定的，属于群体决策。2.4 按企业决策的目标分类在企业的决策中，我们按决策目标可分为单目标决策和多目标决策。2.4.1 单目标决策单目标决策是指决策行动只要求实现一种目标，此种决策相对比较简单。2.4.2 多目标决策多目标决策是指一项同时需要实现多个目标的决策。在做出一项复杂决策时，需 要妥善处理好多个目标的冲突问题。应用线性规划方法解决企业决策问题时，求解方法已经不存在问题，各种大型求解线性规划问题的计算机程序到处可以找到，使用也比较方便，应用中的主要问题是根据实际情况建立合理的线性规划模型，这是从事系统分析工作者的主要工作11。下面将介绍线性规划模型的特点和建模的基

18、本步骤，并列举若干实例来说明线性规划在企业决策中的应用。 Linear programming in the corporate decision-makingChapter I The theory of linear programming1. Linear programming Introduction Linear programming operations research study earlier, an important branch of the rapid development of a wide range of applications, the method

19、is more mature, it is a mathematical method of scientific management to help people in economic management, transportation, industrial and agricultural production and other economic activities, improve the economic effect is the one indispensable requirements, and improve the economic effect is gene

20、rally in two ways: First, technical improvements, such as improving the production process, the use of new equipment and new raw materials. production organization and planned improvement shuman and material resources, reasonable arrangements for linear programming study: under certain conditions, r

21、easonable arrangements for the human and material resources and other resources, the economy achieve the best results in general, seeking the maximum linear objective function can constraints orminimum, collectively referred to as linear programming problem 1. Solutions satisfy the linear constraint

22、s is called a feasible solution, the set of all feasible solutions is called the feasible region 2. Decision variables, constraints, the objective function is the three elements of linear programming.2. The course of development of linear programming French mathematician J. - B. - J. Fourier and C.

23、Valle - Epson independently proposed the idea of linear programming in 1832 and 1911, but did not attract attention.1939 the Soviet mathematician . Cantor Petrovich mathematical methods in the production organization and planning a book made linear programming problem, did not pay attention. 1947 Am

24、erican mathematician GB Danzig general mathematical model of linear programming and general method for solving linear programming problems-simplex method, laid the foundation for this discipline.1947 the American mathematician J.von Neumann linear programming duality theory, creating a new field of

25、study, has expanded its scope of application and problem-solving ability.1951 U.S. economist TC Koopmans linear programming applied to the field of economy, this Cantor Petrovich won the 1975 Nobel Prize in Economics.A large number of theoretical studies on linear programming in the 1950s, and the e

26、mergence of a large number of new algorithms. For example, in 1954, C. Lai Muji proposed dual simplex method, 1954 S. Vegas and T. Sadi solve linear programming sensitivity analysis and parametric programming, 1956 A. Tucker complementary slackness theorem 1960 GB Danzig and P. Wolfe decomposition a

27、lgorithm.Linear programming research has directly contributed to other mathematical programming problems including integer programming, stochastic programming and nonlinear programming algorithm. Due to the development of the digital computer, there are a number of linear programming software, such

28、as MPSX, OPHEIE, UMPIRE, you can easily solve the thousands of variable linear programming problems 3.In 1979 Soviet mathematician LG Khachian, ellipsoid method proposed for solving linear programming problems, and prove that it is a polynomial time algorithm.1984 Bell Telephone Laboratories Indian

29、mathematician N. Ka Maka new polynomial time algorithm proposed for solving linear programming problems. Solving linear programming problems with this approach in the number of variables to 1/50 of the time as long as the simplex method used in 5000. Has now formed the theory of polynomial algorithm

30、 for linear programming. Expanding range of applications of linear programming in the 1950s. To establish the method of linear programming model.3. Linear programming mathematical model and its standard form 3.1 Linear programming problems raised Frequently asked a class of problems in production ma

31、nagement and business activities, the rational use of the limited human, material, financial and other resources in order to get the best economic effect.Linear programming to solve two problems:(1) Limited resources, request product (or profit) the most.(2) Task (or product) must require the resour

32、ces consumed (or cost) at least.3.2 Characteristics of the linear programming problem (1)Every problem with a set of decision variables of a program; this set of values of the decision variables there on behalf of an over-specific programs. (2)Usually these variables the value is non-negative. (3)Th

33、ere are some constraints, these constraints can use a set of linear equations or linear inequalities. (4)Has a requirement to achieve, it can be used a linear function of the decision variables (called the objective function). Different problem, the objective function is maximized or minimized. Meet

34、 the above four conditions mathematical model called the mathematical model of linear programming.3.3 From the actual problem, create a mathematical model of the steps;(1) Based on impact to achieve the objective factors to find the decision variables;(2) Where the decision variables and achieve the

35、 purpose of the functional relationship between objective function;(3) Restrictions suffered by the decision variables to determine the constraints to be met by the decision variables.3.4 Created by the characteristics of the linear programming model;(1) Each model has a number of decision variables

36、, which is number. Which means that a program of a set of values of the decision variables, the decision variables are generally non-negative.(2) The objective function is a linear function of the decision variables, according to the specific issues can be maximized or minimized, both collectively r

37、eferred to as optimization 3.(3) Constraints is a linear function of the decision variables.3.5 The general form of the linear programming modelObjective function: (1-1)Constraints： (1-2)Linear programming mathematical model, the equation (3-1) is referred to as the objective function; (3-2) referre

38、d to as the constraint condition.3.6 The standard form of the linear programming model (1-3) (1-4)Among.The abbreviated form: (1-5) (1-6)Vectors and matrices: (1-7) (1-8)Among ，4. The solution of the linear programming Graphical method and simplex method for solving linear programming problems, but

39、the practical application of the simplex method, now has the simplex method standard software in the computer to solve the constraints and the number of decision variables of 10000a linear programming problem. In order to improve the speed of problem-solving, but also to improve the simplex method,

40、dual simplex method, the original dual decomposition algorithm and polynomial time algorithm. Graphical method to solve simple linear programming problem with only two variables, can also be used. This method only applies to only two variable linear programming problem 5. It is characterized by an i

41、ntuitive and easy to understand, but little practical value. However, by the graphical method for solving can understand some basic concepts of linear programming. The following highlights the simplex method.4.1 General linear programming problem Simplex Method4.1.1 To establish an initial basic fea

42、sible solutionLinear programming problem, many constraints as inequality, so first you want to translate it into a standard, built at the same timeEstablished an initial basic feasible basis.4.1.2 Optimal solution testFind a feasible to determine if it is not the optimal solution. Method to judge wh

43、ether the test objective function is the Department of, If the number of positive coefficients, then there is a better solution. Only when all the coefficients in the objective function is negative or 0, change the solution is the optimal solution.4.1.3 Base changeTransform from a basic feasible sol

44、ution to another basic feasible solution is a base change.4.1.4 Iteration (rotation operation)Constraints augmented matrix in the new base variable coefficients through the rows of the matrix transform or Gauss transform into a single-Bit matrix 6.4.2 Non-standard linear programming problem solution

45、4.2.The way of MArtificial variable in the constraints of a linear programming problem, requiring artificial variables on the objective function value, this desirable artificial variables in the objective function coefficients (very large positive number) 7,so that the objective function to be maxim

46、ized, artificial variables can only take zero, so the artificial variables must be swapped out from the base variable, otherwise the objective function can not be achieved to maximize.4.2.2 Two-stage methodPhase I: without regard to the original problem exists basic feasible solution to the original linear programming problem with artificial variables, the construct containing only the objective function of the artificial variables and requirements are minimized.Second stage: the first stage to obtain the optimal simplex tableau removed