线性规划

线性规划简述

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

线性规划的成长

法国数学家 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等，可以很方便地求解几千个变量的线性规划困难。

1979年苏联数学家L. G. Khachian提出解线性规划困难的椭球算法，并证明它是多项式时间算法。

1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划困难的新的多项式时间算法。用该种方法求解线性规划困难在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用规模持续扩大。 建立线性规划模型的方法

线性规划的模型建立

从事实困难中建立数学模型一般有下方三个步骤：

1.依据影响所要高达目的的原因寻到决策变量；

2.由决策变量和所在高达目的之间的函数关系确定目标函数；

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

当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时说此数学模型为线性规划模型。

例：

生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材恐供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其得到最多？

解：

1、确定决策变量：设x1、x2为产品Ⅰ、Ⅱ的生产数量；

2、清晰目标函数：获利最大，即求2x1+3x2最大值；

3、所满足的约束条件：

设备制约：x1+2x2≤8

原材料A制约：4x1≤16

原材料B制约：4x2≤12

基本要求：x1,x2≥0

用max代替最大值，s.t.（subject to 的简写）代替约束条件，则该模型可记为：

max z=2x1+3x2

s.t. x1+2x2≤8

4x1≤16

4x2≤12

x1,x2≥0

线性规划的解法

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

单纯形法

可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。前者供应基本算法所根据的逻辑规则，适用于在电子计算机上执行求解运算；后者将变量和报告列成表格，适用于笔算。两者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～）于1947年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～）于1938年提出的解乘数法相相似。 依据单纯形法的原理，在线性规划困难中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数高达最大值（或最小值）的可行解称为最优解。如此，一个最优解能在整个由约束条件所确定的可行区域内使目标函数高达最大值（或最小值）。求解线性规划困难的目的就是要找出最优解。

或许显现下列情形之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情形下发生，即没有可行解或各类约束条件不阻止目标函数的值无限放大（或向负的方向无限放大）。

要缩减对最优解的搜索规模，就务必认识最优解的一般性质，最优解假使存在的话，则它必然处在可行区域的边界上。

任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或“≥”号而得到的。每一个边界方程确定一个超平面。所以，可行区域的边界是由那些满足一个或同期满足几个边界方程（即处在作为边界的一个或几个超平面上）的可行解所构成，而且最优解必在其中。最优解不仅是在可行区域的边界上，而且亦在这个区域的一个隅角上。一个可行解，假使不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。假使连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解具有下列三个重要性质：①假使存在着一个最优解，那么它必定是角点可行解。假使存在有多个最优解，那么起码有两个最优解必定是相邻的角点可行解。②只存在有限个数的角点可行解。③假使一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一部分，那它就比所有其余角点可行解都更好，也就是最优解。

上述这些性质组成单纯形法的原理基础。最后一个性质的重要性在于它为一个角点可行解能否是最优解给予了一种简便的检验标准，因此毋需列举所有的可行解。单纯形法正是利用了这个性质，只要检查少数的角点可行解，而且一旦这个最优性检验得到通过就可立刻停止运算。

单纯形法的运算步骤可归结为：①起始步骤──在一个角点可行解上开始。②迭代步骤──移动至一个更好一部分的相邻角点可行解（依据需要反复执行这一步骤）。③停止法则──在目前角点可行解比所有相邻角点可行解都更好些时停止。目前角点可行解就是一个最优解。

单纯形法的优点及其成功之处在于它只需要较少的有限次数的迭代，即可寻到最优解。

线性规划的应用

在企业的各类管理活动中,比如计划、生产、运输、技术等困难,线性规划是指从各种制约条件的组合中,选择出最为合理的计算方法,建立线性规划模型进而求得最佳结果.