工程优化第五章线性规划

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

2、0x1 + 2500x2目标函数约束条件3x1 + 2x2 £ 65s.t.2 x1 + x2 £ 403 x2 £ 75x1 ³ 0, x2 ³ 0564例 2 （）从 A1 , A2一个库厂要把若干的两个仓到零售点 B1 , B2 , B3 , B4 。仓库 Ai 能供应的数量为ai (i = 1, 2) ，零售点 Bj 所需的数量为bj ( j = 1, 2, 3, 4) 。假设能供应的总量等于需要的总24量，即åai=åbj j =1。且已知从仓库 Ai一i=1到 Bj 的运价为cij 。问应如何安排的，664才能既

3、满足各地的需要，又使所花费的用最小？总费解：假定运费与运量成正比。设由仓库 Ai 运往零售点Bj 的货物数量为 xij ，S 为min S = ååcij xij总费用，则24i=1 j =14å xijj =1= aii = 1,2 s.t.2å xij= bjj = 1,2,3,4i=1xij³ 0,i = 1,2,j = 1,2,3,4764以上两个例子,从数学上来讲,它们的共同特征是:(1)每个一组决策变量(n )表示某一方案 ,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。(2)一定的限制条件(称为约束条件),这

4、些条件可以用关于决策变量的一组线性等式或不等式来表示。(3) 都有一个目标要求,并且这个目标可表示为这组决策 变量的线性函数(称为目标函数),按研究要求目标函数实现最大化或最小化。的不同满足以上三个条件的数学模型称为线性模型。864在一组线性等式或不等式的约束条件之下，求一个线性函数的最大值或最小值的。其一般形式如下：(Min)Max z = c1 x1 + c2 x2 +L+ cn xn，称为线性+ a12 x2 +L+ a1n xn £ (=, ³)b1s.t.a11 x1a21 x1+ a22 x2+L+ a2n xn£ =, ³ b2LL+ am

5、2 x2 +L+ amn xn £ (=, ³)bmam1 x1³ 0n964§2一、线性线性的标准形式和图解法的标准形式一般的线性总可以写成下列标准形式：nmin åcj x j(2.1)j =1nå aij x j= bii = 1,2,L ,m (2.2)(LP)s.t.j =1x j ³ 0j = 1, 2,L, n2.3)令c = (c , c ,L, c)Tn-价格系数或成本系数，12b = (b , b ,L, b )T , b ³ 0, i = 1, 2,L, m ，右端12mi1064æ

6、 a11LLLa1ninöæ A1öA = ç a÷ = çM ÷ = ( PLP )Tax2 ,L, xn )ç÷ç÷i11nç a÷ç A ÷aèm1mn øèm ømin cT xAx = bs.t.于是，线性（LP）也可写成：x ³ 0min cT xs.t. Ai x = bix ³ 0i = 1, 2,L, m或min cT xnå Pj xj= bs.t.j =1

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

8、1n3.若约束条件中含有不等式å aij x j ³ bi ，增加松弛j =1变量 xn+i ³ 0 ，把上述约束化为等式约束1364nå aij x j - xn+ij =1= bi ；4.若第i 个等式约束中bi < 0 ，则用（-1）乘该等式两端；= uj - v,u j ³ 0, v j ³ 0 ，5.若 xj变量，可令 xjj把它代入目标函数和约束函数。1464min z =3x3£ 7s.t. 3x3 ³ 23例 1：将线性= 5化为。- 3x1 , x2x³ 0³ 0, 再令

9、x ², x ¢ ³ 0, x ² ³ 0 ，则解：引入松弛变量 x4 , x5333上述线性化为：3x ¢ + 3x ²min zs.t. 33¢ - x ² + x = 7334x ¢ - x ² - x = 2335x ¢ - 2x ² = 5-333¢,³ 0351564二、线性线性的图解法的图解法就是用几何作图的分析并求出其最优解的过程。求解思路：先将约束条件加以图示，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行

10、域中找出最优解。例 1 用图解法求解线性。1664max z = 2x1 + 3x22x1 + 2x2 £ 12s.t.x1 + 2x2 £ 8 4x1 £ 164x2 £ 12x1 , x2 ³ 0解：对于上述具有两个变量的线性，下图的阴影部分描述了满足约束条件的区域，为Z= z = 2x1 + 3x2OABCD;红虚线为目标函数的等值线。沿箭头方向移动目标函数的等值线，1764平移等值线直至与可行域 OABCD 相切或融合为一条直线，此时就得到最优解为 C 点，其坐标可x2通过解方程组得到：ìx1 + 2x2 = 862x1+2x

11、2=124x1=16í4x = 16î1ì x1 = 44íx= 2î 2AB4x =1223也为该的最优解，最优值z = 2´ 4 + 3 ´ 2 = 14 。1D4068Cx1+2x2=81864例2 用图解法求解线性max Z=4x1+3x2s.t.2x1+2x2 16005 x1+2.5x2 2500x1 400x1,x20由约束条件得到可行域OABCD。由等值线Z=4x1+3x2 沿箭头方向向上平移与可行域交于B 点，则B点就是最优点。最优值等于26001964x2例3 maxZ=40x1+ 80x2x1+2x2

12、£ 303x1+2x2 £ 602x2 £ 24x1 , x2 ³0ABCDx10x + 2x =30求解最优解：BC线段12B点C点x1=(6,12)x2=(15,7.5)Z= 40 x1 + 80x2 =0x=a x1+(1-a) x2 (0£ a £ 1)2064maxZ=1200x1x2612157.5= a+(1-a )x=x1 =6a+ +(1- a )·15x2=12+ +(1-)·7.5x1 =15-9ax2 =7.5+4.5a（有无穷个最优解）(0£ a £ 1)2164例4m

13、axZ=2x1+ 4x2s.t. 2x1+x2-2x1+x2 £ 2 x1 , x2 ³0-2x1+ x2=2x2864无有限最优解若目标函数由 Max Z= 2x1 + 4x2 改为 Min Z =2 x1 +4 x2 ,则可行解所在的范围虽然无20x41Z=02x1+ x2=8界,但有最优解 x = 4，1x2 = 0 ,即(4,0)点.2264例5、 maxZ=3x1+2x2-x1 -x2 ³1x1 , x2 ³0x2无解无可行解-10x1-12364通过图解法可以看出：1.线性的可行解的可行域一般是的；2.若存凸多边形，有些可行域是在最优解，则一

14、定在可行域的某顶点得到；3.若在两个顶点上同时得到最优解， 则这两点的连线上的任一点都是最优解。4.若可行域，则可能发生最优解的情况；5.若可行域是空集，此时无最优解。2464§3 线性一、若干基本概念集合H =x Î Rn的基本概念和基本性质| aT x = b称为超平面，其中a 为， b Î R .容易非零列超平面为凸集。集合H +=x Î Rn | aT x ³ b 与| a T x £ b 称为半空间，显然有H -=x Î RnH = H + I H - 。定义 设C 为凸集，称 x ÎC 为C 的极点，如

15、果x1, x2 ÎC ， x1¹ x2 ，使不2564, l Î(0,1) .x2换言之， x 为凸集 C 的极点是指， 若, l Î(0,1) ，则必x1, x2 ÎC ，使x2= x2 .x1有例如，在平面上，闭三角形区域的极点是三角形的3 个顶点的圆周上任一点都是极点；开圆域没有极点；原点是每个象限区域的唯一极点；整个平面没有极点。2664线性的标准形式：nmin å c j x j3.1j =1nå aij x j j =1x j ³ 0= bii = 1,2 ,L ,m(LP)s.t.(3.2)j = 1

16、, 2,L, n(3.3)æ a11öæ A1öLLa1nA = ç a÷ = çM ÷ = ( P)， c =aLPTc1 , c2 ,L, cn其中ç÷ç÷，i1in1nç a÷ç A÷Laèm1mn øèm ø， b = (b , b ,L, b)T)Tx ,L, x，为了计算的需要min cT x2n12ms.t. Ax = bx ³ 0一般假设b ³ 0 ，则（LP）

17、也可写成2764的约束集合S = x | Ax = b, x ³ 0-可行域记标准线性最优解：使目标函数（3.1）达到最小值的可行解.阶的系数矩阵， m £ n ， Rank ( A) = m ，设 A 为m ´ n基B 是矩阵 A 中的m ´ m 阶的矩阵，称 B 是线性的一个基.æ a11öLa1mB = ç MM÷ = (P ,L, P )，则P1 , P2 ,L, Pm不失一般性，设ç÷1mç a÷Laèm1mm øPj ( j = 1,L, m)

18、 称为基向线性无关. B 中的每一个列Pj 对应的变量 xj 称为基变量.线性量，与基中除变量.基变量以外的变量称为2864基本解在约束方程组（3.2）中，令所有变量取零，由m 个约束方程可解出m 个基变量的唯一解 xB ，将此解加上变量取零的值有öB0 ÷ ，称 x 为线性（LP）èø的基本解.mC的基本解个数至多为 n .注：线基本量不一定全部非负.的非2964基本可行解 满足变量非负约束条件（3.3）的基本解.本可行解的基.正分量的个数恰为m 个，则称可行基对应若基本可行此基本可行解为非的基本可行解。正分量的个数小于m 个，则称此的基本可行解。若基

19、本可行基本可行解为如果一个线性的本可行解都是非退的.化的，则称此线性为非3064例 1求下面线性min 4x1 - 4x2的本可行解+= 4s.t.3= 2-4xj ³ 0, j = 1, 2, 3, 4约束矩阵的 4 个列解依次为= æ1 ö= æ-1ö= æ1 ö= æ0 öPPPP1ç -1÷ ， 2çç1 ÷1 ÷ ， 3ç 0 ÷ ， 4èøèøèø

20、2;ø不难得到该的全部基3164B1 = (P1 , P3 ) ， B2 = (P1 , P4 ) ， B3 = (P2 , P3 ) ，= (P3 , P4 )B4 = (P2 , P4 ) ， B5B1 ， x1 , x3量， x2 , x4 为对于基变量，令ìx1 + x3= 4= 2 ，得到关x2 = x4 = 0 ，有í-xB1î1= (-2, 0, 6,0)T的基本解 x1，它不是可行解.B2 ， x1 , x4 为基变量， x2 , x3 为对于变量，令= 4ì x1x2 = x3 = 0 ，有 í-xB2 的= 2 ，

21、得到关+ xî143264= (4, 0, 0,6)T基本解 x2，它是一个非的基本可行解.同理可求B3 , B4 , B5 的基本解分别为= (0,= (0,0)T2)T= (0,6)T- 4, 0,x3x5x42,0,6,4,，。显然，x3 , x5 均为非的基本可行解，而 x4 不是可行解.故所给线性的本可行解为x5 ，且均是非的，故所给线性问题是非的.3364二、线性的基本定理定理 3.1 设 x 是标准线性（LP）的可行解.x 是（LP）的基本可行解的充分必要条件是 x 的正分量对应的系数列定理 3.2 设 x 为标准线性是线性无关的.（LP）的可行解.x 为（LP）的基本

22、可行解的充分必要条件是 x 为可行域S 的极点.推论：（LP）的可行域S 最多有有限个极点.3464mC由基本解的定义，线性的基本解的个数最多为 n个，而基本可行解集合只是基本解集合的一个子集。即极点集合只是基本解集合的一个子集，所以极点个数小于等于Cmn 。定理 3.3若（LP）可行解，则它一定基本可行解.定理 3.4若（LP）最优解，则必基本可行解是最优解.注：由上述定理知，若（LP）有最优解，只需从基本可mC超过 n 个.行找最优解，而基本可行解的个数3564§4单纯形法单纯形法（1947，Dantzig）的思想：一可行解出发，求出使目标函数值下降的另一个基本可行解；通过不断改

23、本可行解，力图找出使目标函数值达到最优的基本可行解。需要解决的三个：1).2).3).求（LP）的初始基本可行解的；判别一个基本可行解是否为最优解的准则；一个基本可行解转换到使目标函数值下降的.另一个基本可行解的36641 基本可行解是最优解的考虑如下形式的线性min f = cT xs.t. Ax = bx ³ 0其中 A Î Rm´n ， Rank ( A) = m .准则（LP）(4.1)(4.2)(4.3)设 x 是（LP）的一个基本可行解，不妨设 x对应的基为B = (P1 , P2 ,L, Pm ) ，从而m 为基变量，n 为变量。记3764N = (

24、P)T, P,L, P ) ，x ,L, xm+1m+2n2mTxm+ 2 ,L, xn )，于是A = (B, N ), x = æ xB, c =öæöcBç x÷ç c÷èN øè N øBxB + NxN = b约束方程组 Ax = b 可表示为-1-1xB = Bb - BNxN（4.4）由此-1在上式中，令 xN = 0 ，即知 xB = Bb ，从而得基本解æçèö-1Bb0x =÷，将（ . ）代入目标函数（

25、. ），有ø3864f = cT x = cT x+ cT xBBNN= cT (B-1b - B-1 Nx) + cT xBNNN= cT B-1b - (cT B-1 N - cT )xBBNN即得用变量表示目标函数的公式.T-C BB - CB = 0 ，所以上式还可写为1T又 Bf = cT B-1b - (cT B-1N - cT )x- (CT B-1B - CT )xBBNNBBB= cT B-1b - (cT B-1 A - CT )xBB以上推导表明：对于给定的一个基，（LP）可化为如下的等价形式：3964min f = cT B-1b - (cT B-1N - c

26、T )xBBNNs.t. x+ B 1Nx= B-1bBx ³ 0N（4.5）称（4.5）为（LP）关的典式.B （或基本可行解 x）注：如果 x 对应的基B 为一般形式，即B = (Pj , Pj ,L, Pj )12m通过类似的推导，可得关于一般基B 的典式仍具有（4.5）的形式.4064s = c BA - C ,T-1T记B则基变量对应的部分s= CT B 1B - CT = 0BBB变量对应的部分s N= cT B-1 N - cTBN定义 4.1 在标准线性（LP）s= cT B-1P - c ( j = 1, 2,L, n)中，称jBjj为变量 x j 关B 的判别数.

27、sT-= c BA - C1T是所有变量 x 的判由此定义B别数.4164定义 4.2 在标准线性（LP）中，若关于.设 B 是一个基， x 是一个可行解，则 Ax = bB-1 Ax = B-1b 。因此f + (cT B-1 A - CT )x = cT B-1b又BB于是可得方程组：ìï B-1 Ax = B-1bíf + (cT B-1 A - CT ) x = cT B-1bïîBB写成矩阵形式得：4264æ B-1böé0B-1 ACT B-1 A - CTù æ f ö=

28、ê1ú ç÷ç÷xT-1C Bbû èøëèBøBæ 0B-1 AB-1bö÷ø系数增广矩阵ç 1简写为CT B-1 A - CTT-1C BbèBBæ B-1 AB-1böç÷-称为对应的单纯形表，T-T-C BA - C1T1C BbèBøBæöB-1 AB-1bT (B) = ç÷ç÷记为T-

29、CT B-1bC BA - C1TèBø)TBCT B-1b = bB-1b = (b, b,L, b记B00,1020m0CT B-1 A - CT = (b, b,L, b0n ) 称为检验数B01024364B-1 A = B-1 (P , P ,L, P )12b1222MnLLæ b11ö÷÷b1n2nMç bbb= ç21ç÷Mç b÷bLbè m1mn øm2于是æ b11ö÷LLb1nMb10MçMT

30、 (B) = ç÷÷÷øç bm1LLbmnbm0çbbbè010n004464如何从一个基本可行解x0 出发，求一个改进的基本可行解？x = æ xBöç x÷ 是任一个可行解，由 Ax = b 得到设èN ø-1-1xB = Bb - BNxN在该点处的目标函数值f = cT x = cT x+ cT xBBNN= cT (B-1b - B-1Nx) + cT xBNNN= cT B-1b - (cT B-1 N - cT ) xBBNN4564

31、29;jÎRåT-(cT B-1 p= c Bb - c )x1BBjjjT-s x= c Bb -1（*）BjjjÎR其中 R 是变量下标集。由（*）可知，适未知量 xj ( j Î R) 的数值就有可能使得当选取ås> 0j x jjÎR从而得到使得目标函数值减少的新的基本可行解。为此，在原来的n - m 个变量中，使得4664n - m - 1 个变量仍取零值，而另一个变量，比如 xk 增大，即取正值，以便实现我们的目的。那么如何确定下标k 呢？由（*）式，当 x j ( j Î R)取值相同时，s j （正数）

32、越大，目标函数至下降得越多，因此选择 xk ，使得s k = maxs j jÎR这里假定s k > 0 ， xk 由零变为正数后，得到方程= B-1b - B-1 p x= b - yk xkkk组 Ax = b 的解 xB4764， b = B-1b, yk= B-1 pk其中b 和 yk 是m 维列将 xB 按分量写出来，即，æ xBö÷æçöæö÷ykb11ç÷ç1xykbç÷ç÷ç÷Bx=

33、ç÷ = ç÷ - ç22÷ x2BkMMMç÷ç ÷ç÷ç÷ç÷ç÷xykbèm øèm øèmøBxN = (0, 0,L, 0, xk , 0,L, 0)T在新得到的点处，目标函数值是4864f = CBBb - s xT-1kk再来分析怎样确定 xk 的取值。一方面，由上式，xk 取值越大函数值下降越多；另一方面，根据 xB， xk 的取值受到可行性

34、的限制，它不能的表k = B-1k£ 0 时），对某个i ，当无限的增大（当x³ 0£ 0> 0ykx时，取任何值时，总成立，而当Biikx= b - yk x ³ 0yk时，为保证，就必须取值Biiikibix £³ 0 ，。因此，为了使 xBkkyii4964x= min ìï bi| yk > 0üï =bríýkikykyïîïþirbr后，原来的基变量 xB= 0 ，得到新的可xk 取值kyrr行解L x , 0,

35、L, 0)Tx,B2k这个解一定是基本可行解。这因基B = ( pB , pB ,L, pB ,L, pB)12rm中的m 个列是线性无关的，其中不包含 pk ，由于5064= B-1 pk ，故ykmåp= Byk =ky pkiBii=1p, pB ,L, pB ,L, pB即 pk 是组的线性组合，后，得到的向B12rm¹ 0ykpp且系数 r。因此，用 k 取代Brp, pB ,L, pk ,L, pB量组也是线性无关的。因此，B12m新的可行解的正分量对应的列是线性无关的，故 x 为基本可行解。5164经上述转换， xk由原来的变量变成基变变量。在新的可x量，而原

36、来的基变量变成Br，目标函数值比原来减少了s k xk 。重复以行上过程，可以进一步改本可行解，直至（*）中所有s j 均非正数，以致任何一个值都不能使目标函数值减少为止。变量取正选取哪个基变量离基及哪个变量的具体如下：5264（1） 确定进入基的变量s k = maxs j | s j> 0 ，则取 xk 为进入。一般的，令基的变量， Pk 为进入基的（2）确定离开基的变量（a） 设已确定 xk 为变量，令bl 0= minbi 0 | b> 0,1 £ i £ m，ikbblkik由此确定变量 xl 由基变量化为变量。5364（b）对原来的 T(B)进行适当

37、变换，使第k 列变，其中第l 个分量为 1，构造新基B¢ 的为T (B¢) = (b/ )单纯形为ij= blj, j = 0,1,L, n/bljblk- bljb= bb , j = 0,1,L, n, i = 0,1,L, m, i ¹ l/ljijikblk5464定理 4.1（最优性判别定理）中,对于某个基本可行解,若在极小化所有s 化这 个£ 0 ,则这个基本可行解是最优解；若在极大j中, 对于某个基本可行解, 所有s³ 0 ,则中j基本可行解是最优解。其s= CB Bp - c j = 1, 2,L, n-1jj称为检验数。j55

38、64例1考虑标准线性min f = 2x1 + x2+= 5s.t.3= 0- 6x1 ,L, x5考 虑 基 变 量x = (0, 0, 5, 0, 21)T4x5 = 21³ 0x5对 应 的 基 本 可 行 解x , x，变 量的 判 别 数12s 1 = -2 < 0,s 2= -1 < 0 ，所以 x 是最优解.5664定理 4.2 （1）如上所得新基B¢是可行基；（2）换基之后，目标函数值不增，而当原基本可行解 x 是非新的基本可行解 x ，则时，按上述cT x > cT x 。得到3 单纯形的基本步骤（以极小化为例）B = (P , Pj ,L, Pj) ，假设已有一个可行基j12mB 的单纯形表T (B) ，Step1: 作对应Step2: 如果所有的检验数都小于或等于 0，则5764B 的基本可行解便是（LP）的最优解，算关法结束；否则转 step3；若检验数中有s r> 0 ，使T (B) 中 xrStep3:所在BP = (b-mr )