工程优化课件第5章线性规划

1、第五章线性规划 线性规划问题举例 线性规划的标准形式及图解法 线性规划的基本概念及基本性质 单纯形法 两阶段法及大 M 法 线性规划的对偶理论修正单纯形法对偶单纯形法XiDian University1线性规划问题举例例 1:某工厂拥有 A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示，问题：工厂应如何安排生产可获得最大的总利润？解：设变量 xi 为第i 种（甲、乙）产品的生产件数（ i 1，2）。XiDian University根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。该问题建立

2、的数学规划模型如下：XiDian University产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500maxz = 1500x1 + 2500x2目标函数约束条件3x1 + 2x2 65s.t.2x1 + x2 403x2 75x1 0, x2 0XiDian University例 2（运输问题）一个制造厂要把若干单位的产品从 A1 , A2 两个仓库发送到零售点B1 , B2 , B3 , B4 。仓库 Ai 能供应产品的数量为ai (i = 1, 2) ，零售点Bj 所需产品的数量为bj ( j = 1, 2, 3, 4) 。假设能供应的

3、总量等于需要的总24量，即 ai=bj。且已知从仓库 Ai 运一个单位i=1j =1的产品到Bj的运价为cij 。问应如何安排运输，XiDian University才能既满足各地的需要，又使所花费的运输总费用最小？解：假定运费与运量成正比。设由仓库 Ai 运往零售点Bj的货物数量为 xij24，S 为运输总费用，则min S = i=1cij xij= ais.t.xijij = bjxijji=xij 0,i = 1,2,j = 1,2,3,4XiDian University以上两个例子,从数学上来讲,它们的共同特征是:(1) 每个问题都用一组决策变量( x1 , x2 ,L, xn )

4、表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)条件(称为约束条件),这些条存在一定的件都可以用关于决策变量的一组线性等式或不XiDian University或不等式来表示。(3)都有一个目标要求,并且这个目标可表示为这组决策 变量的线性函数(称为目标函数),按研究问题的不同,要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划数学模型。XiDian University在一组线性等式或不等式的约束条件之下，求一个线性函数的最大值或最小值的问题，称为线性规划问题。其一般形式为(1.1)和(1.2)形式。(Min)Max z = c1

5、x1 + c2 x2 +L+ cn xn(1.1)+ a12 x2 +L+ a1n xn (=, )b1s.t.a11 x1a21 x1+ a22 x2 +L+ a2n xn (=, )b2LL(1.2)+ am2 x2 +L+ amn xn (=, )bmam1 x1x1 , x2 ,L, xn 0XiDian University2线性规划的标准形式和图解法一、线性规划问题的标准形式一般的线性规划问题总可以写成下列标准形式：nmin cj x j j =1(2.1)n aij x j j =1x j 0= bii = 1,2,L,m (2.2)(LP)s.t.j = 1, 2,L, n(2

6、.3)令c = (c , c ,L, c)Tn-价格系数或成本系数，12右端向量b = (b , b ,L, b )T , b 0, i = 1, 2,L, m ，12miXiDian Universityx = (x , x ,L, x)T12n a11 A1a1ninLL LA = a = M = ( PLP )ai11n约束矩阵aamn m Am1划问题（LP）也可写成：min cT xs.t. Ax = bx 0于是，线或XiDian Universitymin cT xs.t. Ai x = bix 0i = 1, 2,L, m或min cT xn Pj x j= bs.t.j =1

7、x 0XiDian University满足约束条件(2.2），(2.3)的向量 x 是可行解.全体可行解构成LP 的可行域.当可行域为空集时，称此线性规划无可行解或无解。当可行域非空，但目标函数值在可行域上无界， 则称此线性规划无界或无最优解.结论：线性规划问题（LP）的可行域是凸集.各种形式的线性规划都可化为标准形线性规划：XiDian Universitymin(-c)T x ；1.若给出的是max cT x ，则可转化为n2.若约束条件中含有不等式 aij x j bi ，增加松弛j =1 0xn+i变 量， 把 上 述 约 束 化 为 等 式 约 束n aij x j + xn+i=

8、 bi ，而目标函数保持不变；j =1n3.若约束条件中含有不等式 aij x j bi ，增加松弛j =1变量 xn+i 0 ，把上述约束化为等式约束XiDian Universityn aij x j - xn+i= bi ；j =14.若第i 个等式约束中bi 0j x jjR从而得到使得目标函数值减少的新的基本可行解。为此，在原来的n - m 个非基变量中，使得XiDian Universityn - m - 1 个变量仍取零值，而另一个非基变量，比如 xk 增大，即取正值，以便实现我们的目的。x j ( j R)那么如何确定下标k 呢？由（*）式，当取值相同时， s （正数）越大，目

9、标函数至下j降得越多，因此选择 xk ，使得s k = maxs j jR这里假定s k 0 ， xk 由零变为正数后，得到方程= B-1b - B-1 p x= b - yk x组 Ax = b 的解 xBkkXiDian Universityk是m 维列向量， b = B-1b, yk= B-1 pk其中b 和 yk，将 xB 按分量写出来，即xykbB111xykBbxB = = - 22 xk2MMMxykbm m m BxN = (0, 0,LTxk , 0,L, 0)在新得到的点处，目标函数值是XiDian Universityf = CBBb - s xT-1kk再来分析怎样确定

10、 xk 的取值。一方面，由上式，xk 取值越大函数值下降越多；另一方面，根据 xB的表达式，xk 的取值受到可行性的限制，它不能= B-1 pk 0 时），对某个i ，当无限的增大（当 ykx 0 0 0ykx时， k 取任何值时，总成立，而当Biix= b - yk x 0yk时，为保证，就必须取值Biiikibix x 0。因此，为了使，应令kkyiBX D an Universityix= min bi| yk 0 =brkikykyirbr后，原来的基变量 xB= 0 ，得到新的可xk 取值行解kyrrx = (xT, x,L, x, 0, x, 0,L, x , 0,L, 0)B1B

11、2Br-1Br+1k这个解一定是基本可行解。这是因为原来的基B = ( pB , pB ,L, pB ,L, pB)12rm中的m 个列是线性无关的，其中不包含 pk ，由于XiDian University= B-1 pk ，故ykmp= Byk =ky pkiBii=1是向量组 pB , pB12,L, pBr ,L, pBm即 pk的线性组合， 0ykpp且系数 r。因此，用取代后，得到的Brk向量组 pB , pB ,L, pk ,L, pB12m也是线性无关的。因此，新的可行解 x 的正分量对应的列向量是线性无关的，故 x 为基本可行解。XiDian University经上述转换，

12、 xk 由原来的非基变量变成基变量，而原来的基变量 xB变成非基变量。在新的可r行解处，目标函数值比原来减少了s k xk 。重复以上过程，可以进一步改进基本可行解，直至（*） 中所有s j 均非正数，以致任何一个非基变量取正值都不能使目标函数值减少为止。选取哪个基变量离基及哪个非基变量进基的具体方法如下：XiDian University（1）确定进入基的变量s k = maxs| s j 0 ，则取 xk 为进入一般的，令j基的变量， Pk 为进入基的向量。（2）确定离开基的变量（a） 设已确定xk 为进基变量，令bl 0= minbi 0 | b 0,1 i m，ikbblkik由此确定

13、变量 xl 由基变量化为非基变量。XiDian University（b）对原来的 T(B)进行适当变换，使第k 列变为单位向量，其中第l 个分量为 1，构造新基 B 的T (B) = (b/ )单纯形为ij= blj, j = 0,1,L, n/bljblk- bljb= b, j = 0,1,L, n, i = 0,1,L, m, i l/bljijikblkXiDian University定理 4.1（最优性判别定理）若在极小化问题中,对于某个基本可行解,所有s 0 ,则这个基本可行解是最优解；若在极大j化问题中, 对于某个基本可行解, 所有s 0 ,则中j这 个基本可行解是最优解。其

14、s= CB Bp - c j = 1, 2,L, n-1jj称为检验数。jXiDian University例1考虑标准线性规划min f = 2x1 + x2x1 + x2 + x3-x1 + x26x1 + 2x2= 5= 0= 21s.t.+ x4+ x5x1 ,L, x5 0x3 , x4 , x5考 虑 基 变 量x = (0, 0, 5, 0, 21)T对 应 的 基 本 可 行 解x , x， 非 基 变 量的 判 别 数12s1 = -2 0,s 2= -1 cT x 。新的基本可行解 x ，则3单纯形方法的基本步骤（以极小化问题为例）假设已有一个可行基 B = (Pj , P

15、j ,L, Pj12m) ，作对应于基B 的单纯形表T (B) ，如果所有的检验数都小于或等于 0，则XiDian UniversityStep1:Step2:关于基B 的基本可行解便是（LP）的最优解，算法结束；否则转 step3；若检验数中有s r 0 ，使T (B) 中 xr 所在Step3:-BP = (bmr ) 0 ，则（LP）无最优1, b,L, b的列r1r2r解，算法终止，否则转 step4；Step4:令r 为最大正检验数中指标最小者，即r = minl | s l = max s j s j 0取 xr为进基变量；令 js 为比值最小的行中指标最XiDian Univer

16、sity小者，即| bk 0= min bi 0 ,1 i mj = min jskbbbir 0krir取 x j 为离基变量。sStep5: 换基迭代：以bsr 为主元进行s,r旋转变换，得到新的单纯形表T (B% ) ，以 B% 取代 B，返回 step2。注：对极大化问题，可给出类似的步骤，只是确定进基变量的准则不同，应令s l= min s j 。s j 0 ，-k 0 ，则此线性规划没有最1BP且相应的列向量优解.定理 4.3对于非退化的线性规划问题，从任何基本可行解开始，经有限次迭代，或达到一个最优基本可行解，或得出线性规划问题无界的结论.注：对于退化情形，可以证明，如果最优解存

17、在， 只要采取一定的措施，也能做到有限步收敛。XiDian University例 1 求解线性规划问题min f = -2x1 - x2x1 + x2 + x3-x1 + x26x1 + 2x2= 5= 0= 21s.t.+ x4+ x5x j 0, j = 1, 2,L, 5解：取可行基为B = (P3 , P4 , P5 ) ，对应的基本可行解为x = (0, 0, 5, 0, 21)T，1建立初始单纯形表T (B) 如下：XiDian University2. maxs1, s2=2= s1, r =1,所以x1 为进基变量.3. x1 对应的的列向量中有正分量存在，bk 0= min

18、bi 0521= 21,1 i m = min,bkrbir166bir 0iXiDian UniversityxBx1x2x3x4x5x3 x4 x511100-11010620015021f210000取s=3,故x5 为离基变量；故x1对应列与x5对应行的相交处的b31=6为主元素,4.以b31=6为主元进行旋转变换得新的单纯形表；xBx1x2x3x4x5x3 x4 x102/30-1/604/311/611/301/63/27/27/2f01/300-1/3XiDian University-75.maxs2=1/3= s2, 所以r=2，故x2 为进基变量；6. x2对应的列向量中有

19、正分量存在，bk 0, i mminbir 0min,bkr4 / 3 1 / 36ir取s=1,故x3 为离基变量；故x2对应列与x5对应行的相交处的b21=2/3为主元素；7.以b21=2/3为主元进行旋转变换得新的单纯形表；XiDian University8. 这时，检验数全部小于等于0，即目标函数已不可能再减小，于是得到最优解：x = (11/4,9/4,0,1/2,0)T目标函数的最小值为： f = -31/4XiDian UniversityxBx1x2x3x4x5x2 x4 x1013/20-1/400-211/210-1/201/49/41/211/400-1/20-1/4-

20、31/45初始基本可行解的求法用单纯形法解线性规划时，需要先有一个初始基本可行在前边例子中，约束矩阵中含有，且b 0 ，则可取初始基本可一个单位矩阵行基 B = I，即可得到一个基本可行解，但在一般情况下，难以凭观察得出初始可行基，甚至有无可行基都难以判定基本可行解的一般方此有必要给出寻找初始XiDian University考虑标准形式的线性规划问题：cT x Ax = bx 0mins.t.(LP)不妨设b 0 ，但并不要求 A 为行满秩矩阵。对于一般标准型的线性规划问题，约束方程组的系数矩阵中不包含单位矩阵。本节给出引进人工变量，构造一个单位矩阵，从而得到初始基XiDian Univer

21、sity本可行解的方法。寻找初始基本可行解的方法主要有两阶段法和大M 法。一两阶段法算法的第一阶段：用单纯形法消去人工变量（如可能的话），即把人工变量换成非基变量，求出（LP）的一个基本可行解。m对 上 述 （ LP ）， 引 入 0(i = 1,L, m) 后，XiDian University个 人 工 变 量xn+i用单纯形方法求解如下的辅助问题（ALP）min g = eT xa s.t.Ax + xa = bx 0, xa 0me为 分 量 全 为 1其 中的维 列 向 量 ，xa= (x)T,L, x是n+1n+m x = 0 人工变量构成的m 维列向量。显然， x b 为 a （

22、ALP）的一个基本可行解。XiDian University设（ALP）是非退化的，求解（ALP）得到的最 x优基本可行解是 x ，此时必有下列情形之一：a情形 1： xa 0 ，这时（LP）无可行解。因为 x = x 则 0 是（ALP）如果（LP）有可行解的可行解，在此点，（ALP）目标函数值g = 0 x + eT 0 = 0 eT xa ，而eT xa 是（ALP）的最优值。XiDian University情形 2： xa = 0 ，且 xa 的分量都是非基变量，此 x = x 时m 个基变量都是原来的变量，又知 x 0 a是（ALP）的基本可行解，因此 x = x 是（LP） 的一

23、个基本可行解。情形 3： xa = 0 ，且 xa 的某些分量是基变量，这时可用主元消去法把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始XiDian University两阶段法的第二阶段。应指出，为替换出人工变量而采用的主元消去法，在主元选择上，并不要求遵守单纯形法确定离进基变量的规则。设 xn+s 为基变量，则（ALP）关于B 的单纯形表中xn+s 所在的第s 行对应的方程为xn+ s + bsj x j + bs,n+i xn+i= 0（*）jJiI这里J 为 x1,L, xn中非基变量的指标集，I 为人工变量中非基变量的指标集。XiDian University=

24、0( j J ) ，表明第s 个方若（*）式中所有的bsj程是多余的，应删去，这相当于从B 的单纯形表中删去第s 行。若（*）中存在r J , 使bsr 0 ，则以bsr为主元进行转轴运算，得到（ALP）的新的单纯形表，它对应的基本可行解仍为（ALP）的最优解，但新的基变量中减少了一个人工变量xn+s ，若新的基变量中还有人工变量，重复此法，经有限次，必能化为情形 2。XiDian University综上所述，对不具有明显可行基的（LP），可先用单纯形法求解辅助性性规划问题（ALP），解的结果或者说明（LP）无可行解，或者找到（LP）的一个基本 可行解，然后再从这个基本可行解开始应用单纯形法求解（LP），此即两阶段法的第二阶段。将目标函数 g 用非基变量表示如下：mmnmnmg = xn+i= (b - ai