工程优化方法 第五章.ppt

第五章 线性规划 ;线性规划就是一个线性函数在线性等式或不等式约束条件下的极值问题，是最简单的约束优化问题 理论最为成熟、应用最为广泛的一种数学规划方法 运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支 广泛应用于军事作战、经济分析、经营管理和工程技术等方面 为合理地利用有限的人力、物力、财力等资源作出最优决策，提供科学的依据。;法国数学家傅里叶和瓦莱-普森分别于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.沃尔夫提出分解算法等 1979年苏联数学家哈奇扬提出解线性规划问题的椭球算 法，并证明它是多项式时间算法。 ; 1984年美国贝尔电话实验室的印度数学家卡马卡提出解线 性规划问题的新的多项式时间算法。用这种方法求解线性规 划问题在变量个数为5000时只要单纯形法所用时间的1/50。 现已形成线性规划多项式算法理论。 线性规划的研究成果还直接推动了其他数学规划问题包括 整数规划、随机规划和非线性规划的算法研究。由于数字电 子计算机的发展，出现了许多线性规划软件，lingo等，可以 很方便地求解几千个变量的线性规划问题。;线性规划通常解决下列两类问题：;例 某企业计划生产甲、乙两种产品。这些产品分别要在A、 B、C、D四种不同的设备上加工。按工艺资料规??，单件 产品在不同设备上加工所需要的台时如下表所示，企业决 策者应如何安排生产计划，使企业总的利润最大？;解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：;第五章 线性规划 ;目标函数：;线性规划问题的数学模型;目标函数：; 线性规划问题可能有各种不同的形式。 目标函数有实现最大化也有实现最小化的; 约束条件可以是“? ” 、“?”、“=”。 决策变量有时有非负限制有时没有。 为便于今后讨论，我们规定线性规划问题的标准形为：;线性规划标准形的矩阵形式;线性规划标准形的向量形式;线性规划标准形的向量形式; 一般情况下 , 为正整数,分别表示约束条件的个数和决策变量的个数, 为价值向量, 为决策向量, 通常 为已知常数。; （1）目标函数求最小值； （2）决策变量非负； （3）约束条件都是等式； （4）常数项（右端向量）非负;如何化成标准形; 若约束方程组为不等式 约束条件为“ ? ”形式的不等式,则在“ ? ” 号的左边加入非负的松弛变量;把原“ ? ” 形的不等式变为等式;; 约束条件为“ ? ”形式的不等式,则可在“ ? ”号的左端减去一个非负的剩余变量。; 若存在取值无约束的变量 ，可令 其中： ;;解：令 x3= x4-x5 , x4,x5?0 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准形:;例2: 化为标准形。 max z = 2x1+3x2 s.t. 2x1+2x2 ≤12 x1+2x2≤8 4x2≤12 4x1 ≤16 x1, x2≥0 ;线性规划问题;线性规划的图解法;例3 用图解法求解线性规划问题; 求图解法的步骤： 建立坐标系， 将约束条件在图上表示 确立可行域 绘制目标函数的等值线族，确定目标函数增大和减小的方向 确定最优解：