线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人 所重视线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的 约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或 线性方程来表示而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求 解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作 管理的重要性1■线性规划问题的最优解探讨1.1线性规划问题的提出考虑下面的线性规划问题的标准型:目标函数：约束条件:(1)⑵min Z = CXJ AX = b |X >0其中，C = (c ,c，…,c ), X 二(x ,x，…,x )T , b = (b ,b，…,b )T , A 二(a ) 阶矩阵1 2 n 1 2 n 1 2 m j mxn设B是A中m个线性无关的列向量构成的一个基，B二(a ) 阶矩阵，这样将矩 ij mxm阵A分成两个部分，即A= (B, N) ,X= (X ,X ) ,C=(C ,C ), X , c为基B对应的非基 BN B N B B变量和系数，X , X为N对应的非基变量和系数，这样将线性规划问题改写为：N NminZ =(C , C )B N约束条件:—X _(B, N)BXL N」X X'bn> 0=b经过矩阵变换，得出关于基B的标准型如下: 证明：◎ >0，由(7')式可知，对任意一组可行解X = (x ,x，…,x )T ,Z = Y c x , j j j=1约束条件:将(5) (6)展开为:约束条件:Z =区 c b0 i ii=1min Z = C」BB-1 + (C—C B-1N) X(5)N BNf X + B-1 NX =B-1b⑹[BN1 X , X> 01 B NB-1b = (b:,b '，…1 2,b ')Tm(、aa ….a1m+11m+21naa ….aB -1N =2 m+12 m+22 nt amm+1a •…mm+2a /mnmin Z = £ cb' + £i ii=1 j=m+1x + £ a' x = b'i ij j °j=m+1x > 0ja = c 一区 c aj j i ij i=11.2最优解判别准则迟 c a ') xi ij ji=1⑻⑼,称a为检验数。
准则一：若X⑴=(bb'2,…,b' ,0,…,0)T，为对应于基B的基本可行解，且对于1 2 m切的j = m +1,m + 2,…,n ，a >0，则X为线性规划问题的最优解均有Z > Z，0但X⑴能使等式成立，即Z = Z0解当 g > 0 , j = m +1, m + 2,…,nj有某一个g= 0 ，设 j>0，则该线性规划问题有第二个最优的基本可行解证明：构造一个行解m+1i = 1,2,…,m根据9原则x =9m+1x = 0 j9 = min<1
准则三：当c > 0 , j = m +1, m + 2,…,n，有某一个g = 0，对一切i = 1,2,…,m ， j j则该线性规划有无穷多个最优解证明：构造一个新解X⑶，由（8'）-a' xL im+1 m+1i = 1,2,…,mxm+1xj由于 a' < 0 ， 6 > 0，故 x > 0 , i = 1,2,…,mim+1 i将X⑴代入原目标函数（4）得：由于：b = cm+1 ,Z = £ c b' + (c -区i ii=1,i 丰 Lm+1i=1im+1-£c a'. . = 0 m+1 ii=1im+1故:cb'i ii =1Z = £ c b' +0i ii=1,i 丰 LX⑶仍为可行解，得到无穷多可行解，而目标函数仍为，即X⑶也是最优解Z = £ c b ' = Zi i 0i=1以下举出一些实例，进一步说明线性规划最优解的具体求解方法:2.线性规划最优解的问题举例2.1图解法求解线性规划问题例][5]:求解下面的线性规划问题：max Z = 5 一 8 x ,6x + 2x 一 3x 一 2x = 0,14 5 6< x 一 4x + 7 x + 5x = 0, ( 1)2 4 5 6x + 2x + 4x 一 3x = 20,3 4 5 6x > 0, j = 1,2,…,6.i j显然X* = (x ,x，…,x )t = (0,0,20,0,0,0” 是该线性规划问题(1)的一个最优解。
1 2 6{ b'因 c' = c' = 0 ，及 0 = min 匚:a'4 5 4 a'b'> 0, i = 1,2,3 J = —— = 0 ，a '140 5 = min{ b-L : a'a '5> 0, i = 1,2,3}=鼻=0 , a '25i 4可考虑如下线性规划问题:max W = x + x4 5(2)x + 2x - 3x = 0< 1 4 5x - 4 x + 7 x = 02 4 5x > 0, j = 1,2,4,5.v j易解得线性规划问题(2)的最优解为X'' = (x ,x ,x ,x )t = (0,0,0,0)t , W(X'') = 0 ,于 12 4 5是可得X* = (x ,x，…,x)T = (0,0,20,0,0,0)t是该线性规划问题(1)的唯一最优解1 2 6例2 [7]：求解下面的线性规划问题:max Z = 5 - x6x + x - 2 x - x = 01 4 5 6< x + 4x + 42x - 2x = 25 ( 1)2 4 5 6x - 2x + x + 3x = 03 4 5 6x > 0, j = 1,2, ,6.i j显然X* = (x ,x，…,x )t = (0,20,0,0,0,0)t是该线性规划问题(1)的一个最优解。
1 2 6因 c' = c' = 0，及 0 = mm{ i4 5 4 a'i 4b':a' 4 > 0, i = 1,2,3 J=—— = 0 ，i4 a'a 14{ b'0 5 = min L : a'a '5> 0, i = 1,2,3 }=吐=0 ,a '25可考虑如下线性规划问题:max W = x + x4 5(2)x + x - 2 x = 0< 1 4 5x - 2 x + x = 03 4 5x > 0, j = 1,3,4,5.i j易解得线性规划问题(2)有无界解，X'' = (x ,x ,x ,x )T = (0,3,2,1)T是该问题的一个可 13 4 5行解，W(X'') = 3 > 0 ,于是线性规划问题的最优解不唯一只要取X* = (x ,x , ,x)T1 2 6如下：x = 0, x = 3s;1 3x = 25 - s(4 x 2 + 42 x1) > 0;2x = 2s, x = s;4 5x = 0.6那么X '也是线性规划问题的最优解例如，分别取s=0.5、0.25时，则(0,0,1.5,1,0.5,0)T 和(0,12.5,0.75,0.5,0.25,0)t以及X * = (0,25,0,0,0,0)t都是该线性规划问题(1)的最优解， 其中，(0,25,0,0,0,0)t是一退化的基可行解，(0,0,1.5,1,0.5,0)t是一非退化的基可行解，而 (0,12.5,0.75,0.5,0.25,0)t = 1 [(0,0,1.5,1,0.5,0 > +(0,25,0,0,0,0 >]是一可行解而不是基 解。
例3⑷：要将两种大小不同的钢板结成A,B,C三种规格，每张钢板可同时截得三种规格 的小钢板的块数乳下表所示：钢板类型规格类型A规格B规格C规格第一种钢板211第二种钢板123今需A , B , C三种规格的成品分别为15，18，27块，问：各截取这两种钢板多少张可得所需三种规格成品，且使得所用钢板张数最少?2 x + y > 15x + 2 y > 18解：需要截得第一种钢板X张，第二种钢板Y张，则卜+ 3y > 27 （*）x > 0y > 0作出可行区域图如下：目标函数为z = x + y，经 过可行区域内的整点且与 原点最近的直线是 x + y二12它上面的整点有（0, 12）、（1,11）、（2,10）、 （3,9）、（ 4，8 ）、（ 5，7 ）、（6,6 ）、（ 7,5 ）、（ 8,4 ）、X（9,3）、（10,2）、（11,1）、 （12,0），若逐一讨论其是 否在可行域内比较麻烦时， 只需先判断点A（导害）附近的整数点是否满足条件，若满足条件，则再试附近的整 数点；若不满足条件，则不需要再判断下去故此题，我们只需先判断A点附近的整数点（3,9）、（4,8），分别代入（*）式，易得它们都满足条件。
故我们还需判断（2,10）、（5, 7）两点，代入（*）式发现它们都不满足条件，则其余点不需要再判断所以该题的最优解为（3,9）、（4,8）例4(3]: max S = 5x + 2x，约束条件为:1 2x < 41x — x > 3< 1 25x + 2x > 101 2x , x > 0J 1 2利用图解法求解如下:此例中约束条件中存在和目标函数的系数成比例的约束条件，但是由于此约束条件在可 行域的形成中没有发挥作用，所以此问题没有多个最优解图解法是求解含有两个变量的线性规划问题的一种很直观和有效的方法，所以在作 出问题的可行域时，则可根据这个必要条件，若可行域中没有与目标函数平行的边界线 时，则可直接判断出此问题一定没有多个最优解2.2单纯型法求解线性规划问题例5 M。