毕业设计方案(论文)文献综述.docVIP

生产决策中的目标规划模型 伏建建 第一部分 绪论 线性规划是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。是辅助人们进行科学管理的一种数学方法，为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写为LP。 线性规划的概述，在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是生产组织与计划的改进，即合理安排人力物力资源.二是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.线性规划所研究：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素. 法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出想法，苏联数学家Л.В.康托罗维奇在1939年《生产组织与计划中的数学方法》书中提出线性规划问题，也未引起重视。美国数学家G.B.丹齐克1947年提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。如，1954年C.莱姆基提出对偶单纯形法1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题1956年A.塔克提出互补松弛定理1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以方便地求解几千个变量的线性规划问题。1979年苏联数学家Л.Г.哈奇扬提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50现已形成线性规划多项式算法理论50年代后线性规划的应用范围不断扩大。 ①有唯一最优解； ②有无穷多组最优解； ③无可行解； ④无有限最优解（即为无界解）。 （3）图解法的步骤： ①建立平面直角坐标系； ② 根据图示要求条件，找出可行域；③图示目标函数，即为一条直线； ④将目标函数直线沿其法线方向在可行域内向可行域边界平移直至目标函数。 2、单纯形法 （1）基本思想：：① 找出初始可行基，确定初始基本可行解，建立初始单纯形表。 ② 检验此基本可行解是否为最优解，即检验各非基变量的检验,若所有的≤0（j=m+1，…n）则已经得到最优解，计算停止；③在0（j=m+1，…n）中，若有某个检验数对应的非基变量的系数列向量,则此问题为无界解，停止计算；④根据max（0）-，确定非基变量为换入变量；θ法则 确定基变量为换出变量。 ⑤实施枢轴运算，即以为主元素进行枢轴运算（亦即进行矩阵）,使Pk变换为第一行的元素为1，其余的元素为0；并将XB列中的换为，从而得到新的单纯形表；重复②-⑤，。直到终止。 3、两阶段法、大M法以及应用人工变量法求解非规范型的线性规划问题 （1） 两阶段法 ①原理：此方法是将加入人工变量后的线性规划问题分成两个阶段来求解。 第一阶段：目的是为原问题求初始基本可行解。为此，对于求极大化（或者极小化）的线性规划问题，建立一个新的人工变量的目标函数—人工变量的系数均为-1或(+1),对新的问题： 或者 使得 用单纯形法求解，若-0，即所有的人工变量都变换为非基变量，说明原问题已得到了初始基本可行解；反之，若目标函数的值为负（或正），则人工变量中至少有一个为正，表示原问题无可行解，应停止计算。 第二阶段：将第一阶段求得的基本可行解对原问题的目标函数进行优化，即将目标函数换成原目标函数，以第一阶段得到的最终单纯形表除去人工变量的列后作为第二阶段