《线性规划企业利润最大化.doc》由会员分享，可在线阅读，更多相关《线性规划企业利润最大化.doc（36页珍藏版）》请在金锄头文库上搜索。
1、引 言线性规划主要用于解决生活、生产中的资源利用、人力调配、生产安排等问题，它是一种重要的数学模型简单的线性规划指的是目标函数含两个自变量的线性规划，其最优解可以用数形结合方法求出。涉及更多个变量的线性规划问题不能用初等方法解决。线性规划问题的难点表现在三个方面：一是将实际问题抽象为线性规划模型；二是线性约束条件和线性目标函数的几何表征；三是线性规划最优解的探求。线性规划的发展史法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。 1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视
2、。 1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。 1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。 50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和
3、P.沃尔夫提出分解算法等。 线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。 1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。 1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大
4、。随着经济的发展，关于线性规划在企业中的应用越来越广泛。林海明早在1996年就立足于较强的普及性，从经济常识的角度来认知线性规划问题的解法，初步论述这一问题；熊福力、张晓东等在2004年作了基于利润最大化的油田开发非线性规划一文，他们根据油田开发的实际情况，将油田和利润细分为几个部分，以获得最大利润为目标，建立了油田开发的数学模型；吴海华和王志江在关于影子价格作为企业资源配置依据的探讨根据线性规划模型资源影子价格的经济意义，讨论了在企业以收入最大化和利润最大化两种情况下，影子价格作为企业资源配置依据时存在的问题。胡徐胜、刘娟和汪发亮在最优控制在汽车企业利润最大化中的应用一文中从汽车企业职工结构
5、角度出发，研究在企业提供职工工资总量不超过某一限定值的情况下,如何分配汽车企业中普通职工与高级职工的比例来达到实现汽车企业利润最大化的目标。随着经济社会的发展，线性规划在资源配置和企业管理方面发挥着独特的作用。在企业的各项管理活动中，例如计划、生产、运输、技术等问题，从各种限制条件的组合中，通过对实际数据的分析处理和数学模型的建立，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果，给出了更多的决策参考信息。这也将成为未来企业生产与管理的普遍方法。 不单如此，企业现如今更着重于对各种条件组合中限制条件作局部调整以达到对获得利润的一种控制，而这恰恰也是线性规划问题中灵敏度分析所研究的对象
6、。本文共分为四章。在第一章，介绍本文的背景和线性规划的发展状况；在第二章，介绍线性规划本身和一系列相关性质问题及企业利润最大化数学模型的基础知识；在第三章，介绍利用线性规划建立企业利润最大化数学模型；最后，求解模型最优解。第2章线性规划问题本章主要介绍线性规划本身和一系列相关性质问题，并相应举出一些简单的例子更好的阐述了线性规划问题。本章主要借鉴于胡运权、郭耀煌等编著，清华大学出版社出版的运筹学教程（第二版）的内容。2.1线性规划模型及标准型211线性问题的数学模型例1：美佳公司计划制造，两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序及每天可用于这两种家电的能力、各售出一件
7、时的获利情况，如表1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1项目每天可用能力设备A（h）0515设备B（h）6224调试工序（h）113利润（元）21 对上例用和分别表示美佳公司制造家电和的数量。这时此例数学模型可表示为 由此例可以看出，规划问题的数学模式型由三个要素组成：变量，或称决策变量，是问题中要确定的未知量，它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制；目标函，它是决策变量的函数，按优化目标分别在这个函数前加上或；约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。假定线性规划问题中含个变量，分别用（）表示，在
8、目标函数中的系数为（通常称为价值系数），的取值受项资源的限制，用（）表标第种资源的拥有量，用表示变量取值为1个单位时所消耗或含有的第种资源的数理量，通常称为技术系数或工艺系数。刚上述线性规划问题的数学模型可表示为：上述模型的简写形式为用向量形式表达时，上述模型可写为：式中；用矩阵和向量形式来表示可写为：称为约束方程组（约束条件）的系数矩阵。 变量的取值一般配为非负，即；从数学意义上可以有。又如果变量表示第种产品期内产量相对于前期产量的增加值，则的取值范围为，称取值不受约束，或无约束。2112线性规划问题的标准形式线性规是问题的标准形式如下：标准形式的线性规划模型中，目标函数为求极大值，约束条件
9、全为等式，约束条件右端常数项全为非负值，变量的取值全为非负值。对不符合标准形式的线笥规划问题，可分别通过下列方法化为标准形式。1）目标函数为求极小值，即为：因为求等价于求，令，即化为：2）约束条件的右端项时，只需将等式或不等式两端同乘（-1），则等式右端项必大于零。3）约束条件为不等式。当约束条件为“”时，如，可令，得，显然。当约束条件为“”时，如有，可令，得，。和是新加上去的变量，取值均为非负，加到原约束条中去的变量其目的是使不等式转化为等式，其中称为松弛变量，一般配称为剩余变量，但也有称松弛变量的。松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润
10、，所以引进模型后它们在目标函数中的系数均为零。4）取值无约束的变量是。如果变量代表某产品当年计划数与上一年计划数之差，显然的以值可能是正也可能是负，这时可令，其中，将其代入线性规划模型即可。5）对的情况，令，显然。22线性规划模型的求解221线性规划问题的基与解 线性无关：对于n维空间的一组向量，若数域F中有一组不全为0的数（），使 成立，则称这组向量在F上线性相关。否则称这组向量在F上线性无关。秩：设A是mn矩阵。若A的n个列向量中有r个线性无关（），而所有个数大于r的列向量组都线性相关，则称数r为矩阵A的列秩。类似可定久矩阵A的行秩。矩阵A的列秩与行秩一定相等，它也称为矩阵A的秩。基：已知
11、A是约束条件的mn系数矩阵，其秩为m。若B是A中mm非奇异子矩阵（即可逆矩阵，有），则称B是线性规划问题的一个基，B是由A中m个线性无关的系数列向量组成的。基向量：B中一列（共m个）基变量非基向量：B外（A中）一列（共nm个）非基变量可行解：满足、的解最优解：满足的可行解基本解：令所有非基变量=0，求出的满足的解基本可行解：满足的基本解最优基本可行解：满足的基本可行解基本解退化的基本解：有基变量=0的基本解退化的基本可行解退化的最优化基本可行解222线性规划的图解法l 适于求解二维问题l 不必化为标准型2211图解法步骤例2： 1）由全部约束条件作图求出可行域2）作出一条目标函数的等值线3）平
12、移目标函数等值线，作图得最优点，再算出最优值 图1最优点Q： ；最优值Z： .2212从图解法看线性规划问题解的几种情况1）有唯一最优解（一般情况）2）有无穷多组最优解（平行；最优值相同）对例2，修改为：3） 无可行解（可行域空集）对例2，增加一个约束条件：4） 无有限最优解（无界域；取决于求还是？）对例2，去掉第一个约束条件l 线性规划的可行域为凸集，特殊情况下为无界域（有有限个顶点）或空集。l 线性规划若有最优解，一定可在可行域顶点上得到。223单纯形法2231单纯形法迭代原理1）确定初始基可行解 当线性规划问题的所有约束条件均为号是，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量
13、可确定基可行解。 对约束条件含或号时，可构造人工基，人为产生一个单位矩阵，用大法或两阶段法获得初始基可行解。2）最优性检验与解的判别（目标函数极大型） 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。 若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解（无最优解）。 当存在某些非变量的检验数大于零，需要找个一个新的基可行解，即要进行基变换。2232单纯形法迭代步骤1）求出初始可行解，列出初始单纯形表。 设为基变量，为非
14、基变量基100001002）计算检验数进行最优性检验。 若已获得最优解（或确定无最优解），则停止；否则进行下一步。3）换基。根据的原则，确定为换入变量，计算（），按规则，确定为换出变量。4）通过初等行变换将系数矩阵中变量对应列变换为第个元素为1的单位列向量，用代为新的基变量，列出新的单纯形表，回到第二步骤。例3：用单纯形法求解线性规划问题 解 先将上述问题化成标准形式有 其约束条件系数矩阵的增广矩阵为 是单位矩阵，构成一个基，对应变量是基变量。令非基变量等于零，即找到一个初始基可行解以此列出初始单纯形表记作表2如下：表221000基0150510002462010051100121000因表中有大于零的检验数，故表中基可行解不是最优解。因，故确定为换入变量。将列除以的同行数字得，由此6为主元素，作为标志对主元素6加上方括号 ，主元素所在行
