工程优化第5章

•线性规划的简介和应用举例•线性规划的数学模型和图解法•线性规划的基本概念和基本性质•单纯形法•关于单纯形法的说明和补充•线性规划的对偶理论与对偶单纯形法第5章线性规划•线性规划就是一个线性函数在线性等式或不等式约束条件下的极值问题，是最简单的约束优化问题•理论最为成熟、应用最为广泛的一种数学规划方法•运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支•广泛应用于军事作战、经济分析、经营管理和工程技术等方面•为合理地利用有限的人力、物力、财力等资源作出最优决策，提供科学的依据。线性规划的概述•法国数学家傅里叶和瓦莱-普森分别于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。现已形成线性规划多项式算法理论。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。线性规划的发展线性规划通常解决下列两类问题：(1)当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标(2)在一定的资源条件限制下，如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)线性规划问题的数学模型例某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润(元)甲21402乙22043有效台时1281612线性规划问题的应用•解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：线性规划问题的应用121212121223..221228416412,0maxzxxstxxxxxxxx目标函数：约束条件：线性规划数学模型的一般形式11221111221121122222112212()...(1)...(,)...(,)...(2)...(,),,...,0nnnnnnmmmnnmnminmaxzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划问题的数学模型目标函数：约束条件：11221111221121122222112212()...(1)...(,)...(,)...(2)...(,),,...,0nnnnnnmmmnnmnminmaxzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划问题的数学模型线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints目标函数：约束条件：11221111221121122222112212()......(,)...(,)......(,),,...,0nnnnnnmmmnnmnminmaxzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划问题的数学模型其特征是：(1)问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；(2)问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？从线性规划数学模型的一般形式看线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;约束条件可以是“”、“”、“=”。决策变量有时有非负限制有时没有。为便于今后讨论，我们规定线性规划问题的标准形为：11221111221121122222112212...............,,...,0nnnnnnmmmnnmnminzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划问题的标准形bi0(i=1,2,···,m)线性规划标准形的矩阵形式记c=(c1,c2,···,cn)Tx=(x1,x2,···,xn)Tb=(b1,b2,···,bm)TA=(aij)m*n线性规划的标准形的其它形式(0)..0TminzcxAxbbstx11221111221121122222112212...............,,...,0nnnnnnmmmnnmnminzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx:,0(0)TminzcxAxbxb也可写作称A=(aij)m*n是约束方程组的系数矩阵线性规划标准形的向量形式记c=(c1,c2,···,cn)T,x=(x1,x2,···,xn)Tb=(b1,b2,···,bm)TPj=(a1j,a2j,···,amj)Tj=1,2,···,n线性规划的标准形的其它形式1(0)..0TnjjjminzcxPxbbstx11221111221121122222112212...............,,...,0nnnnnnmmmnnmnminzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划标准形的向量形式记c=(c1,c2,···,cn)Tx=(x1,x2,···,xn)Tb=(b1,b2,···,bm)TAi=(ai1,ai2,···,ain)i=1,2,···,m线性规划的标准形的其它形式,1,2,...,(0)..0TiiiminzcxAxbimbstx11221111221121122222112212...............,,...,0nnnnnnmmmnnmnminzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx一般情况下,为正整数,分别表示约束条件的个数和决策变量的个数,具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解。mn,mncx,,(1,...,,1,...,)ijijabcimjn称m为线性规划的阶数,称n为线性规划的维数。线性规划的标准形(0)..0TminzcxAxbbstx为价值向量,为决策向量,b为右端向量，为已知常数。（1）目标函数求最小值；（2）决策变量非负；（3）约束条件都是等式；（4）常数项（右端向量）非负线性规划标准形的特点(0)..0TminzcxAxbbstx如何化成标准形若目标函数是:maxz=cTx,只需将目标函数的最大值变换为求目标函数的最小值,即maxz=min(-z)。令zˊ=-z,于是得到：minzˊ=-cTx.目标函数的转换若约束方程组为不等式约束方程的转换：由不等式转换为等式ijijbxa称为松弛变量相应的松弛变量在目标函数中的价值系数取值为0。如何化成标准形则在“”号的左边加入非负变量;把原“”形的不等式变为等式;约束条件为“”形式的不等式,0ijjniiniaxxbx约束条件为“”形式的不等式,则可在“”号的左端减去一个非负变量。约束方程的转换：由不等式转换为等式ijijbxa称为剩余变量相应的剩余变量在目标函数中的价值系数取值为0。如何化成标准形0ijjniiniaxxbx若存在取值无约束的变量，jxjjjxxx0,jjxx变量的转换若，jjxx0jx0jx如何化成标准形可令其中：可令，显然例1:试将如下线性规划问题化成标准形1231231231231232372..325,0,minzxxxxxxxxxstxxxxxx无限制任何形式的线性规划问题都可以化成标准形。现举例如下：如何化成标准形1245671245612457124512723300723225,,...,0minzxxxxxxxxxxxxxxxxxxxxxxx解：令x3=x4-x5,x4,x50,(1)式左端加上非负松弛变量x6,(2)式左端减去非负剩余变量x7,则可将上述线性规划问题化成如下的标准形:如何化成标准形例2:化为标准形。maxz=2x1+3x2s.t.2x1+2x2≤12x1+2x2≤84x2≤124x1≤16x1,x2≥0解：引进4个新的非负变x3,x4,x5,x6使不等式变为等式,标准形为：minzˊ=-2x1-3x2+0·x3+0·x4+0·x5+0·x6s.t.2x1+2x2+x3=12x1+2x2+x4=184x2+x5=124x1+x6=16x1,x2,x3,x4,x5,x6≥0如何化成标准型线性规划问题求解线性规划问题，就是从满足约束条件(2)的方程组中找出一个解，使目标函数(1)达到最大值（或者最小值）。线性规划的图解法线性规划的基本概念11221111221121122222112212()...(1)...(,)...(,)...(2)...(,),,...,0nnnnnnmmmnnmnminmaxzcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx线性规划的图解法线性规划的基本概念可行解(FeasibleSolution)----任一满足约束条件的一组决策变量的数值；目标函数等值线(Objectivefunctonline)----位于同一直线上的点，具有相同的目标函数值。可行域(FeasibleRegion)----所有可行解组成的集合，也称为可行解集；例3用图解法求解线性规划问题线性规划的图解法对于简单的线性规划问题---只有两个决策变量的线性规划问题,我们通过图解法可以对它进行求解。121212121212max2..1.93.81.93.81.911.41.93.80,0zxxstxxxxxxxxxx求图解法的步骤：•建立坐标系，将约束条件在图上表示•确立可行域•绘制目标函数的等值线族，确定目标函数增大和减小的方向•确定最优解：当求目标函数的最大值时，沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”，即为最优解(既满足约束，又使目标函数值最大的点)。当求目标函数的最小值时，沿着目标函数值减小的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”，即为最