线性规划在企业决策中的应用外文翻译资料

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

Seyed Saeed Hosseinian,Hamidreza Navidi,Abas Hajfathaliha

Journal Group Decision and Negotiation

摘要：本文先从线性规划背景和发展出发，提出它的定义，几种形式，数学模型，实际应用，介绍了线性规划的解法——单纯形法，进而综合性地提出企业决策论，企业团队在面对企业重要决策时对数据的分析、整理、联系，构建出线性规划模型，最后比较得出团队决策，使企业收益实现最大化。

关键词：线性规划；团队决策 ； 构建模型；分析数据

第一章 线性规划理论

1. 线性规划简介

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

2.线性规划的发展历程

法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法但未引起注意。 1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题也未引起重视。 1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究并涌现出一大批新的算法。例如1954年C.莱姆基提出对偶单纯形法1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题1956年A.塔克提出互补松弛定理1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展出现了许多线性规划软件如MPSXOPHEIEUMPIRE等可以很方便地求解几千个变量的线性规划问题[3]。1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。建立线性规划模型的方法。

3. 线性规划的数学模型及其标准形式。

3.1 线性规划问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源以便得到最好的经济效果。

线性规划主要解决两类问题

1、资源有限，要求生产的产品或利润最多。

2、任务或产品一定，要求消耗的资源或成本最少。

3.2线性规划问题的特征

1、每一个问题都用一组决策变量12n (x,x...x)表示某一方案，这组决策变量的值就有代表一过具体方案。

2、一般这些变量取值是非负的。

3、存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。

4、都有一个要求达到的目标，它可用决策变量的线性函数称为目标函数来表示。按问题的不同，要求目标函数实现最大化或最小化。

满足以上四个条件的数学模型称为线性规划的数学模型。

3.3 从实际问题中建立数学模型的步骤

1、根据影响所要达到目的的因素找到决策变量

2、由决策变量和所在达到目的之间的函数关系确定目标函数

3、由决策变量所受的限制条件确定决策变量所要满足的约束条件

3.4 所建立的线性规划模型的特点

1、每个模型都有若干个决策变量12n (x,x...x)其中n为决策变量个数。决策变量的一组值表示一种方案同时决策变量一般是非负的。

2、目标函数是决策变量的线性函数根据具体问题可以是最大化max或最小化min二者统称为最优化opt[3]。

3、约束条件也是决策变量的线性函数。

3.5 线性规划模型的一般形式

3.6 线性规划模型的标准形式

4.线性规划的解法

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

4.1 一般线性规划问题的单纯形解法

4.1.1 建立初始基本可行解

在线性规划问题中，约束条件多为不等式，所以首先要将其化为标准型，同

时建 立一个初始基本可行基。

4.1.2 最优解检验

找到一个可行判断它是不是最优解。判断方法是检验目标函数中是否还有正的系数，若有正的系数，则说明还有更好的解。只有当目标函数中的全部系数为负值或0时，说明改解才是最优解。

4.1.3 基变换

从一个基可行解到另一个基可行解的变换就是进行一次基变换。

4.1.4 迭代旋转运算

将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或Gauss变换变为单位矩阵[6]。

4.2 非标准型线性规划问题的解法

4.2.1 大M法

在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值无影响，为此可取人工变量在目标函数中的系数为M(M为非常大的正数)[7]这样目标函数要实现最大化，人工变量只能取零，因此必须把人工变量从基变量中换出，否则目标函数就不可能实现最大化。

4.2.2 两阶段法

第一阶段不考虑原问题是否存在基可行解，给原线性规划问题加上人工变量，构造仅含人工变量的目标函数和要求实现最小化。

第二阶段将第一阶段得到的最优单纯形表，除去人工变量，将原目标函数的系数换掉该表的目标函数的系数行，作为第二阶段计算的初始表。

4.3 对偶分析

4.3.1 对偶问题的基本概念，在线性规划问题中，如果把一个求最大值的线性规划定义为“原”问题，那么与其同时存在一个求最小值的所谓对偶问题，并且原线性规划的最优解对应着对偶线性规划问题的最优解。

4.3.2 对偶问题的性质 

1、对称性 对偶问题的对偶是原问题。

2、弱对偶性 若X*是原问题的可行解Y是对偶问题的可行解。则存在CX*Y*b。

3、无界性 若原问题对偶问题为无界解，则其对偶问题原问题无可行解。

4、可行解是最优解时的性质，设X是原问题的可行解Y是对偶问题的可行解 

5、对偶定理 若原问题有最优解，那么对偶问题也有最优解且最优值相同。

6、互补松驰性 分别是对偶问题和原问题的可行解最优解。

4.4灵敏度分析 灵敏度分析主要有以下几种情况[4]

1. 资源数量变化的分析
2. 目标函数中价值系数jc的变化分析
3. 技术系数ija的变化
4. 约束条件增减的变化分析

第二章 企业决策理论

1. 企业决策概述

随着企业计算机应用和信息化程度的不断深入，企业已经积累了大量的业务和财务数据并继续随着时间和业务的发展而呈几何级膨胀趋势。企业信息处部门的工作重点已逐渐超越了简单的数据收集，企业内的各级人员都希望能够快速、准确并方便有效地从这些大量杂乱无章的数据中获取有意义的信息决策者也希望能够充分利用现有的数据指导企业决策和发掘企业的竞争优势[9]。决策效率和决策质量的高低将直接影响企业的运营绩效和市场竞争力。由于集团企业具有分布、异构、自治等特点集团企业运营过程中的决策将是一个复杂的过程对于不同的决策问题需要采用不同的决策方法。同时在集团企业运营过程中决策的形式也是多种多样的，它在一定的阶段表现为个体的行为，在一定的阶段又表现为群体的活动从而给集团企业管理中的决策分析提出了高要求。

2.企业决策分类

2.1 按重要程度分类

在企业的决策中，我们按重要程度分类一般把决策分为三个层次，即战略决策、战术决策和业务决策[10]。

2.1.1 战略决策

第一类战略决策是与管理总的方针和开发企业所需要的资源有关的决策，它于长远规划对企业的发展具有深远影响，决策过程中要考虑很多不确定和冒风险的因素。是集团企业决策信息模型中的最高层负责管理、控制、协调整个集团企业网络的正常运行。其控制范围包括涉及集团企业全体成员整体利益的事务和对整个企业集团运营活动的调控与制约。在这一层次可以设定集团企业决策模型的范围和内容、集团企业的合作机制和行为准则的设定、运营过程的绩效评价、利益分配机制和风险控制机制等任务，为集团企业正常运营提供了战略决策框架和行动指南。根据集团企业实际情况进行群体决策，担负着全局优化以及在新机遇下的集团企业组建过程中的决策工作。

2.1.2 战术决策

第二类决策称为战术决策，是在物资资源、设备等决策之后，规划如何最有效的分配所获得的资源，如生产能力、资金、材料、劳力等以便获得最大效益。定义集团企业各成员企业的各种基本决策活动过程。虽然由于集团企业的动态特性，各企业的实际情况和操作流程会有所不同，但我们总能找到一些存在于企业业务活动中相对稳定且有相同或类似行为特征的实体。同时也能找出系统中不能再分的最小粒度的原子过程，利用技术，我们将企业中的各类实体和原子过程封装成对象，根据产品结构信息和集团企业实际运行状态信息，将客户的订单分解到集团企业的各成员企业，并派生出由不同的原子过程组成的工作流对资源进行分配并完成对工作流监督、控制的任务。

2.1.3 业务决策

第三类叫业务决策，完成集团企业具体任务的执行工作，包括物流在各企业间的合理流动以及从原材料到成品的物理加工过程，如原材料的运输、零件加工、部件装配、检测、仓储等过程。在本层中，完成制造、销售、供应、运输等任务的同时，还要对第一线的信息进行采集、整理、反馈以供上层决策时使用。是在资源合理分配后，进行日常业务和计划的决策线性规划模型最适合进行战术决策，解决诸如劳动力和生产能力等资源的合理分配，运输和指派方案的最优选择、广告和推销费用的预算等问题，同时它也在投资方案选择、配料、选址、生产计划、环境如空气、水污染控制、下料等优化方面有广泛的应用。

2.2 按企业决策的环境分类

在企业的决策中，我们按企业决策的环境可分为确定性决策、风险决策和不确定性决策。

2.2.1 确定性决策

确定性决策是指未来环境完全可预测，而且在此确定的未来环境下待选择的决策方案的后果也是可以确定的。简单讲就是一种方案只有一种确定的结果。

2.2.2 风险决策

风险决策是指未来环境有几种可能的状态和相应的后果，人们无法得到关于未来环境的充分可靠的信息，但可以预测每一种状态和后果出现的概率。对利润、效益等问题的决策一般都是风险型决策。

2.2.3 不确定性决策

不确定性决策是指未来环境出现某种状态的概率难以估计，甚至连可能出现的状态和相应的后果都是未知的。这类决策主要依靠决策者的经验和主观判断。

2.3 按企业决策的主体分类

在企业的决策中我们按企业决策的主体可分为个人决策和群体决策。

2.3.1 个人决策

个人决策是指决策的主体是一个人即最终方案的选择仅仅由一个人拍板决定。

2.3.2 群体决策

群体决策是指决策的主体是两人或两人以上。企业中许多重要的决策都是由决策群体制定的属于群体决策。

2.4 按企业决策的目标分类

在企业的决策中我们按决策目标可分为单目标决策和多目标决策。

剩余内容已隐藏，支付完成后下载完整资料

---

外文文献出处：Journal Group Decision and Negotiation.

附外文文献原文

Linear programming in the corporate decision-making

Chapter I The theory of linear programming

1. Linear programming Introduction

Linear programming operations research study earlier, an important branch of the

rapid development of a wide range of applications, the method 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 generally 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, reasonable 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 constraints 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. 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 American 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 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 emergence 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 algorithm.

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 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 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 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 management 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 resources 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)There 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 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 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, 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

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[286781]，资料为PDF文档或Word文档，PDF文档可免费转换为Word