《{城乡园林规划}工程优化第5章》由会员分享，可在线阅读，更多相关《{城乡园林规划}工程优化第5章（169页珍藏版）》请在金锄头文库上搜索。
1、线性规划的简介和应用举例 线性规划的数学模型和图解法 线性规划的基本概念和基本性质 单纯形法 关于单纯形法的说明和补充 线性规划的对偶理论与对偶单纯形法,第5章 线性规划,线性规划就是一个线性函数在线性等式或不等式约束条件下的极值问题，是最简单的约束优化问题 理论最为成熟、应用最为广泛的一种数学规划方法 运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支 广泛应用于军事作战、经济分析、经营管理和工程技术等方面 为合理地利用有限的人力、物力、财力等资源作出最优决策，提供科学的依据。,线性规划的概述,法国数学家傅里叶和瓦莱-普森分别于1832和1911年独立地提出线性规划的想法，但未引
2、起注意。 1939年苏联数学家康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。 1947年美国数学家G.B.丹齐格提出线性规划的一般数学模型和求解线性规划问题的通用方法-单纯形法，为这门学科奠定了基础。 1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。,线性规划的发展,50年代后对线性规划进行大量的理论研究，并涌现出一大 批新的算法。例如 1954年，C.莱姆基提出对偶单纯形法 1954年
3、，S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题 1956年，A.塔克提出互补松弛定理 1960年G.B.丹齐格和P.沃尔夫提出分解算法等 1979年苏联数学家哈奇扬提出解线性规划问题的椭球算 法，并证明它是多项式时间算法。,线性规划的发展,1984年美国贝尔电话实验室的印度数学家卡马卡提出解线 性规划问题的新的多项式时间算法。用这种方法求解线性规 划问题在变量个数为5000时只要单纯形法所用时间的1/50。 现已形成线性规划多项式算法理论。 线性规划的研究成果还直接推动了其他数学规划问题包括 整数规划、随机规划和非线性规划的算法研究。由于数字电 子计算机的发展，出现了许多线性
4、规划软件，如MPSX， OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线 性规划问题。,线性规划的发展,线性规划通常解决下列两类问题：,当任务或目标确定后，如何统筹兼顾，合理安排，用最 少的资源 (如资金、设备、原标材料、人工、时间等)去 完成确定的任务或目标,(2) 在一定的资源条件限制下，如何组织安排生产获得最好 的经济效益(如产品量最多 、利润最大),线性规划问题的数学模型,例 某企业计划生产甲、乙两种产品。这些产品分别要在A、 B、C、D四种不同的设备上加工。按工艺资料规定，单件 产品在不同设备上加工所需要的台时如下表所示，企业决 策者应如何安排生产计划，使企业总的利润最大
5、？,线性规划问题的应用,解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：,线性规划问题的应用,目标函数：,约束条件：,线性规划数学模型的一般形式,线性规划问题的数学模型,目标函数：,约束条件：,线性规划问题的数学模型,线性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints,目标函数：,约束条件：,线性规划问题的数学模型,其特征是： (1) 问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值； (2) 问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个
6、模型是线性规划模型？,从线性规划数学模型的一般形式看,线性规划问题可能有各种不同的形式。 目标函数有实现最大化也有实现最小化的; 约束条件可以是“ ” 、“”、“=”。 决策变量有时有非负限制有时没有。 为便于今后讨论，我们规定线性规划问题的标准形为：,线性规划问题的标准形,bi 0 ( i = 1,2,m),线性规划标准形的矩阵形式,记 c = (c1, c2, , cn )T x = ( x1, x2, , xn )T b = (b1, b2, , bm )T A = (aij) m*n,线性规划的标准形的其它形式,也可写作,称A = (aij) m*n 是约束方程组的系数矩阵,线性规划标
7、准形的向量形式,记 c = (c1, c2, , cn )T, x = ( x1, x2, , xn )T b = (b1, b2, , bm )T Pj = ( a1j, a2j, , amj )T j = 1, 2, , n,线性规划的标准形的其它形式,线性规划标准形的向量形式,记 c = (c1, c2, , cn )T x = ( x1, x2, , xn )T b = (b1, b2, , bm )T Ai= (ai1, ai2, , ain ) i = 1, 2, , m,线性规划的标准形的其它形式,一般情况下 , 为正整数,分别表示约束条件的个数和决策变量的个数,具体问题的线性规
8、划数学模型是各式各样的,需要把它们化 成标准型,并借助于标准型的求解方法进行求解。,称m为线性规划的阶数, 称n为线性规划的维数。,线性规划的标准形,为价值向量, 为决策向量, b为右端向量，,为已知常数。,（1）目标函数求最小值； （2）决策变量非负； （3）约束条件都是等式； （4）常数项（右端向量）非负,线性规划标准形的特点,如何化成标准形,若目标函数是: max z= cTx , 只需将目标函数的最大值变换为求目标函数的最小值, 即 max z = min (- z) 。令z= -z, 于是得到： min z= - cTx.,目标函数的转换,若约束方程组为不等式,约束方程的转换：由不等
9、式转换为等式,称为松弛变量,相应的松弛变量在目标函数中的价值系数取值为0。,如何化成标准形,则在“ ” 号的左边加入非负变量;,把原“ ” 形的不等式变为等式;,约束条件为“ ”形式的不等式,约束条件为“ ”形式的不等式,则可在“ ”号的左端减去一个非负变量。,约束方程的转换：由不等式转换为等式,称为剩余变量,相应的剩余变量在目标函数中的价值系数取值为0。,如何化成标准形,若存在取值无约束的变量 ，,变量的转换,若 ，,如何化成标准形,可令,其中：,可令 ，显然,例1: 试将如下线性规划问题化成标准形,任何形式的线性规划问题都可以化成标准形。现举例如下：,如何化成标准形,解：令 x3= x4-
10、x5 , x4,x50 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准形:,如何化成标准形,例2: 化为标准形。 max z = 2x1+3x2 s.t. 2x1+2x2 12 x1+2x28 4x212 4x1 16 x1, x20,解：引进4个新的非负变x3,x4,x5,x6使不等式变为等式,标准形为： min z =-2x1- 3x2+ 0 x3+0 x4+0 x5+0 x6 s.t. 2x1+ 2x2+x3 =12 x1+ 2x2+ x4 =18 4x2+ x5 =12 4x1+ x6 =16 x1, x2, x
11、3, x4, x5, x60,如何化成标准型,线性规划问题,求解线性规划问题，就是从满足约束条件(2)的方程组中找出 一个解，使目标函数(1)达到最大值（或者最小值）。,线性规划的图解法,线性规划的基本概念,线性规划的图解法,线性规划的基本概念,可行解(Feasible Solution)-任一满足约束条件的一组决策变量的数值；,目标函数等值线(Objective functon line)-位于同一直线上的点，具有相同的目标函数值。,可行域(Feasible Region)-所有可行解组成的集合，也称为可行解集；,例3 用图解法求解线性规划问题,线性规划的图解法,对于简单的线性规划问题-只有
12、两个决策变量的线性规划问题,我们通过图解法可以对它进行求解。,求图解法的步骤： 建立坐标系， 将约束条件在图上表示 确立可行域 绘制目标函数的等值线族，确定目标函数增大和减小的方向 确定最优解：当求目标函数的最大值时，沿着目标函数值增大 的方向平移等值线，当平移直线刚要离开可行域时的“最后交 点”，即为最优解(既满足约束，又使目标函数值最大的点)。 当求目标函数的最小值时，沿着目标函数值减小的方向平移 等值线，当平移直线刚要离开可行域时的“最后交点”，即为最 优解(既满足约束，又使目标函数值最大的点)。,线性规划的图解法,x1,x2,o,x1 - 1.9x2 = 3.8(),x1 + 1.9x
13、2 = 3.8(),x1 - 1.9x2 = -3.8 (),x1 + 1.9x2 = 11.4(),4 = 2X1 + X2,20 = 2X1 + X2,17.2 = 2X1 + X2,11 = 2X1 + X2,Lo： 0 = 2x1 + x2,（7.6，2）,D,max Z,min Z,此点是唯一最优解， 且最优目标函数值 max Z=17.2,可行域,线性规划的图解法,建立坐标系， 将约束条件在图上表示,确立可行域,确定最优解：沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”时，“最后交点”即为最优解。,绘制目标函数的等值线族，确定目标函数增大和减小的方向,
14、x1,x2,o,x1 - 1.9x2 = 3.8 (),x1 + 1.9x2 = 3.8(),x1 - 1.9x2 = -3.8(),x1 + 1.9x2 = 11.4 (),（7.6，2）,D,L0： 0=3x1+5.7x2,max Z,（3.8，4）,34.2 = 3x1+5.7x2,蓝色线段上的所有点都是最 优解这种情形为有无穷多最 优解，但是最优目标函数值 max Z=34.2是唯一的。,可行域,线性规划的图解法,绘制目标函数的等值线族，确定目标函数增大和减小的方向,确定最优解：沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”时，“最后交点”即为最优解。,2
15、,4,6,x1,x2,2,4,6,无界解(无最优解),例4,x1+x2=4(),x1+3x2=6(),3x1+x2=6 (),max Z,min Z,线性规划的图解法,确定最优解：沿着函数值增大的方向平移等值线，与可行域时的“最后交点” 为最优解。,绘制目标函数的等值线族，确定目标函数增大和减小的方向,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),例5,线性规划的图解法,图解法简单、直观，便于初学者窥探线性规划基本原理和几何意义。 通过图解法了解线性规划有几种解的形式 (唯一最优解；无穷多最优解；无界解；无可行解) 作图的关键有三点： (1
16、) 可行域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动,线性规划的图解法,x1,x2,o,（7.6，2）,D,可行域,可行域是多边形,可行域是多边形，有界集,2,4,6,x1,x2,2,4,6,x1+x2=4(),x1+3x2=6(),3x1+x2=6 (),可行域是多边形，但无界,可行域是多边形,x1,x2,O,10,20,30,40,10,20,30,40,50,50,可行域是空集,可行域是空集,x1,x2,o,17.2 = 2x1 + x2,Lo： 0 = 2x1 + x2,（7.6，2）,D,max Z,min Z,此点是唯一最优解,可行域,线性规划的最优解若存在，定在可行域的某顶点,最优解唯一，最优解在可行域的一个顶点,x1,x2,o,（7.6，2）,D
