经济师线性规划法

线性规划法是解决多变量最优决策的方法,是在各种相互关联的多变量约束条件下,解决或规划一个对象的线性目标函数最优的问题,即给与一定数量的人力、物力和资源,如何应用而能得到最大经济效益。

其中目标函数是决策者要求达到目标的数学表达式,用一个极大或极小值表示约束条件是指实现目标的能力资源和内部条件的限制因素,用一组等式或不等式来表示。

线性规划是决策的静态最优化数学规划方法之一它作为经营决策中的数学手段,在现代决策中的应用是非常广泛的,它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划。

缺点：对于数据的准确性要求高，只能对线性的问题进行规划约束，而且计算量大。有由线性规划演变的非线性规划法等等后续的方法弥补，但是计算量增加许多。

线性规划法是解决多变量最优决策的方法,是在各种相互关联的多变量约束条件下,解决或规划一个对象的线性目标函数最优的问题,即给与一定数量的人力、物力和资源,如何应用而能得到最大经济效益其中目标函数是决策者要求达到目标的数学表达式,用一个极大或极小值表示约束条件是指实现目标的能力资源和内部条件的限制因素,用一组等式或不等式来表示
线性规划是决策的静态最优化数学规划方法之一它作为经营决策中的数学手段,在现代决策中的应用是非常广泛的,它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划

缺点：对于数据的准确性要求高，只能对线性的问题进行规划约束，而且计算量大。
，有由线性规划演变的非线性规划法等等后续的方法弥补，但是计算量增加许多。

[编辑本段]线性规划概述
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学的一种数学方法在经济、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料二是生产组织与计划的改进，即合理安排人力物力资源线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素
[编辑本段]线性规划问题的数学模型的一般形式
（1）列出约束条件及目标函数 （2）画出约束条件所表示的可行域 （3）在可行域内求目标函数的最优解及最优值
[编辑本段]线性规划的发展
法国数学家 J- B- J傅里叶和 C瓦莱－普森分别于1832和2022年地提出线性规划的想法，但未引起注意。 2022年苏联数学家ЛВ康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。 2022年数学家GB丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法——单纯形法，为这门学科奠定了基础。 2022年数学家Jvon诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 2022年经济学家TC库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获2022年诺贝尔经济学奖。 2022年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，2022年C莱姆基提出对偶单纯形法，2022年S加斯和T萨迪等人解决了线性规划的灵敏度分析和参数规划问题，2022年A塔克提出互补松弛定理，2022年GB丹齐克和P沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。 2022年苏联数学家L G Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 2022年贝尔电话实验室的印度数学家N卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。2022年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法
[编辑本段]线性规划的模型建立
从实际问题中建立数学模型一般有以下三个步骤； 根据影响所要达到目的的因素找到决策变量； 由决策变量和所在达到目的之间的函数关系确定目标函数； 由决策变量所受的限制条件确定决策变量所要满足的约束条件。 所建立的数学模型具有以下特点： 1、每个模型都有若干个决策变量（x1,x2,x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。 2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。 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代替最大值，（subject to 的简写）代替约束条件，则该模型可记为： max z=2x1+3x2 x1+2x2≤8 4x1≤16 4x2≤12 x1,x2≥0
[编辑本段]线性规划的解法
求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。 对于一般线性规划问题： Min z=CX ST AX =b X>=0 其中A为一个m*n矩阵。 若A行满秩 则可以找到基矩阵B，并寻找初始基解。 用N表示对应于B的非基矩阵。则规划问题1可化为： 规划问题2： Min z=CB XB+XN ST B XB+N XN = b (1) XB >= 0, XN >= 0 (2) (1)两边同乘于B-1，得 XB + B-1 N XN = B-1 b 同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为： 规划问题3： Min z=CB B-1 b + ( - CB B-1 N ) XN ST XB+B-1N XN = B-1 b (1) XB >= 0, XN >= 0 (2) 令N:=B-1N，b:= B-1 b，ζ= CB B-1b，σ= - CB B-1 N，则上述问题化为规划问题形式4： Min z= ζ + σ XN ST XB+ N XN = b (1) XB >= 0, XN >= 0 (2) 在上述变换中，若能找到规划问题形式4，使得b>=0，称该形式为初始基解形式。 上述的变换相当于对整个扩展矩阵（包含C及A） 乘以增广矩阵 。所以重在选择B，从而找出对应的CB。 若存在初始基解 若σ>= 0 则z >=ζ。同时，令XN = 0，XB = b，这是一个可行解，且此时z=ζ，即达到最优值。所以，此时可以得到最优解。 若σ >= 0不成立 可以采用单纯形表变换。 σ中存在分量<0。这些负分量对应的决策变量编号中，最小的为j。N中与j对应的列向量为Pj。 若Pj <=0不成立 则Pj至少存在一个分量ai，j为正。在规划问题4的约束条件（1）的两边乘以矩阵T。 T= 则变换后，决策变量xj成为基变量，替换掉原来的那个基变量。为使得T b >= 0，且T Pj=ei（其中，ei表示第i个单位向量），需要： l ai，j>0。 l βq+βi*(-aq,j/ai,j)>=0，其中q!=i。即βq>=βi/ ai,j * aq,j。 n 若aq,j<=0，上式一定成立。 n 若aq,j>0，则需要βq / aq,j >=βi/ ai,j。因此，要选择i使得βi/ ai,j最小。 如果这种方法确定了多个下标，选择下标最小的一个。 转换后得到规划问题4的形式，继续对σ进行判断。由于基解是有限个，因此，一定可以在有限步跳出该循环。 若对于每一个i，ai,j<=0 最优值。 若不能寻找到初始基解 无解。 若A不是行满秩 化简直到A行满秩，转到若A行满秩。
[编辑本段]线性规划的应用
在企业的各项活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果

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

线性规划
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学的一种数学方法在经济、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料二是生产组织与计划的改进，即合理安排人力物力资源线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好

单纯形法
求解线性规划问题的通用方法。单纯形是数学家GB丹齐克于2022年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值，则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。
改进单纯形法 原单纯形法不是很经济的算法。2022年数学家GB丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。
对偶单纯形法 2022年数学家C莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（2022年），这是用于优化无约束问题的一种数值方法，属于更一般的搜索算法的类别。
这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。