第3章 线性规划
线性规划问题是最优化理论的重要分支，也是最基本的内容，许多实际问题抽象成数学模型后，都可以归结为线性规划问题。自从1947年G.B.Dantzig 提出求解线性规划的单纯形法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是随着计算机技术及数值计算方法的发展，线性规划的应用领域更为广泛。
3.1 线性规划的标准形式
例1-1和例1-2所述问题的数学模型的共同特点是目标函数和约束条件均为线性，设计变量非负。例1-1中的约束条件既含有不等式约束也含有等式约束，而例1-2中的约束条件仅含“≤”的约束。归纳起来，线性规划问题的一般形式为
目标函数：max (min)f(x)=c1x1+c2x2+…+cnxn  约束条件：
a11x1+a12x2+…+a1nxn≤(=,≥)b1
a21x1+a22x2+…+a2nxn≤(=,≥)b2

am1x1+am2x2+…+amnxn≤(=,≥)bm
xj≥0,  j=1,2,…,n,  m<n
线性规划问题的常规求解方法是利用矩阵的初等变换，求解时引进非负的松弛变量(对“≥”的约束称为剩余变量)将不等式约束转化为等式约束，也就是将线性规划问题的一般形式变为标准形式。因此，线性规划问题数学模型的标准形式为线性目标函数加上等式及变量非负的约束条件。用数学表达式表述为min(max) c1x1+c2x2+…+cnxn
s.t. a11x1+a12x2+…+a1nxn=b1
  a21x1+a22x2+…+a2nxn=b2
      
  am1x1+am2x2+…+amnxn=bm
  xj≥0, j=1,2,…,n,  m<n用矩阵表示为min (max) cTx
s.t. Ax=b
  xj≥0,  j=1,2,…,n (3-1) 因此，例1-1的模型化成标准形式为min f(x)=x1+x2+x3+x4+x5+0x6+0x7+0x8+0x9
      +0x10+0x11+0x12+0x13+0x14
s.t. x1+x2+x3+x4+x5+x6=18
  -3x1-4x2+5x3-4x4-6x5+x7=-80
  -3x1+x8=-5
  -4x2+x9=-15
  4x1+x10=35
  4x2+x11=40
  5x2+x12=30
  4x4+x13=40
  6x5+x14=35
  xj≥0, j=1,2,…, 14  例1-2的模型化成标准形式为max f(x)=220x1+250x2+0x3+0x4+0x5+0x6
s.t. x1+x2+x3=1200
  2x1+x2+x4=1800
  x1+x5=800
  x2+x6=1000
  xj≥0, j=1,2,…, 63.2 单 纯 形 法
在学习单纯形法之前需要了解以下两个基本概念。
极点： 若凸集S中的点x，不能成为S中任何线段的内点，则称x为S的极点。
单纯形： 若一个凸集仅包含有限个极点，则称此凸集为单纯形。
单纯形法是求解线性规划问题的有效方法。线性规划问题的可行域是n维向量空间Rn 中的多面凸集，如果存在最优解，则最优解必在该凸集的某极点处达到。极点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否为最优解。若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别。若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解，也可用此法判别。
3.2.1 基本解与基本可行解
在绪论中提到过，如果目标函数是一元线性函数f(x),x∈［a,b］，则f(x)的最大值（或最小值）必在x的端点上取得。而对多元线性规划问题来说，这一结论也是成立的，即f(x)的最大值或最小值在由约束条件构成的求解域的顶点上取得。线性规划问题属于有约束优化（规划）问题，约束条件由等式线性约束和变量非负条件构成。基本解是只满足线性约束条件的解，而基本可行解是既满足等式线性约束又满足变量非负要求的解。因此线性规划问题的解可通过求解线性等式约束方程来获得。
下面先通过一个例子来说明单纯形法的基本原理及求解过程。
【例3-1】 用单纯形法求解下面的线性规划问题：max f(x)=2x1+x2-2x3
s.t. x1+x2+2x3≤5
  x1+3x2-x3≤3
  x1,x2,x3≥0  解：  (1)  先用MATLAB线性规划函数求解，其计算程序如下：  %ch31_li1
clc;
close all;
f=-\2\];
A=\1\];
b=\;
xl=\;
\=linprog(f,A,b,\,\,xl)计算结果为  x=
  3.4696
    0.0000
    0.4696
fval=
  -6.0000 (2)  手算求解
引入松弛变量，将所给问题化成线性规划标准形式:max f(x)=2x1+x2-2x3+0x4+0x5
s.t. x1+x2+2x3+x4+0x5=5
  x1+3x2-x3+0x4+x5=3
  x1,x2,x3,x4,x5≥0将上式约束方程用矩阵表示：11 210
13-101x1
x2
x3
x4
x5=5
3 (3-2)   由于方程个数少于变量个数，因此有无穷多个解。但若取其中3个变量的解为零，则可得到确定的解，并且按这种取法得到的解是有限的，对本问题来说可有10个不同的解。应用MATLAB编程检索这10个解的部分结果如下：  ----------l=1-----j=1, k=2------------
 x(1,2)=6.000000,-1.000000
A=1  1
   1  3
y=11
----------l=2-----j=1, k=3------------
x(1,3)=3.666667,0.666667
AA=1  2
     1  -1
y=6.0000
----------l=3-----j=1, k=4------------
 x(1,4)=3.000000,2.000000
AA=1  1
     1  0
y=6
----------l=4-----j=1, k=5------------
 x(1,5)=5.000000,-2.000000
AA=1  0
     1  1
y=10从中可以看出，虽然这些解都是基本解，但并不都是基本可行解。并且x1=3.6667,x3=0.6667 和x1=3.0,x4=2.0都是最优基本可行解。挑选基本解的程序如下：  %ch1_li1_1
clc;
clear all;
b=\';
A1=\1 1  2 1 0
    1 3 -1 0 1\];
f=\2 0 0\];
l=0;
for j=1:5 
for k=1:5
if(j~=k&&j<k)
AA=\A1(1,j), A1(1,k)
    A1(2,j), A1(2,k)\];
if det(AA)~=0
  l=l+1;
  x=inv(AA)b;
fprintf('---------l= %d-----j= %d, k= %d-----------＼n x(%d,%d)= %f,%f',l,j,k,j,k,x(1),x(2))    
  AA
  y=f(j)x(1)+f(k)x(2)
end
end
end
end下面通过初等变换或消元法求解例3-1。如果约束条件中变量的系数组成的矩阵是满秩的，则对应的变量为基本变量，其系数矩阵称为基矩阵。求解时应选择基本变量和基矩阵进行初等变换。由式（3-2）可知，选择松弛变量x4,x5为基本变量，对应的系数组成的矩阵为基矩阵将会带来很大方便。
令非基本变量x1,x2,x3均为零，则得到x4=5, x5=3。将该结果代入目标函数中，得f(x)=2×0+1×0-2×0+0×5+0×3=0这一结果似乎没有带来什么益处，因为对目标函数没有丝毫影响。但是通过观察可以发现，如果将变量x1由0变成正值，用其替换其中一个基本变量，则目标函数增加最多，因为变量x1的系数最大。这是将非基本变量选进基本变量的一个原则。接下来的问题是将原来的基本变量x4,x5中的哪一个移出，使其成为非基本变量。解决这一问题要借助约束条件，如果仍旧保持x2,x3为零，并去掉方程中非基本变量x2,x3及其系数，则约束方程为110
101x1
x4
x5=5
3 (3-3) 分别选x1, x4和x1, x5为基本变量考察解的情况。以x1, x4为基本变量，同时令x5=0，结果为x1=3, x4=2, f=6; 再以x1, x5为基本变量，同时令x4=0，结果为x1=5, x5=-2, f=10. 第二种方案是不可取的，因为解x1=5, x5=-2不是基本可行解，只是基本解。也就是说应该选择变量x5移出基本变量表。为了说明进基变量的系数列向量元素与右端项元素的关系，将x1分别替换x4和x5的情况用下面的模型进行分析。用x1替换x4的约束方程为a110
a211x1
x5=b1
b2选a11为消元主元，结果为10
01x1
x5=b1/a11
b2-a21b1a11从而得x1=b1/a11,  x5=b2-a21b1a11 (3-4) 用x1替换x5的约束方程为1a11
0a21x4
x1=b1
b2 (3-5) 选a21为消元主元，结果为10
01x4
x1=b1-a11b2a21
b2a21 (3-6) 从而得x4=b1-a11b2a21,  x1=b2/a21 (3-7) 观察式（3-4）和式（3-7) ，注意到当x1=minbiai1=min51,31=b2a21=31=3 (3-8) 时，可得到基本可行解，否则x1的取值不能使所有基本变量的取值成为基本可行解，如式（3-4) . 出基变量与式（3-8）有着必然的联系。式（3-8）中最小比值对应的右端项元素或系数行下标对应的基本变量就是出基变量，且比值分母系数下标就是进基变量对应的主消元元素。验证式（3-3）可知，变量x5为被替换出的变量，与计算结果一致。由此可见，目标函数与约束条件配合，约束方程求解完成后，将基本变量结果代入目标函数中，通过比较非基本变量系数大小决定进基变量（此时认为非基本变量取值不为零）。对求最大值问题，系数较大的非基本变量为进基变量；对于最小值问题，系数较小的非基本变量为进基变量。确定了进基变量后，则计算右端项与进基变量在约束方程中列系数向量对应元素的比值，比值小者的行下标对应的基本变量为出基变量。
下面对单纯形法进行更一般的说明。将式(3-1)中的约束矩阵A按列表示:A=［p1 p2 … pn］pi(i=1,2,…,n)是m×1的向量，pi的分量是各约束方程中与设计变量xi对应的系数。设矩阵A的秩为m，将设计变量x分解为基本变量和非基本变量，即x=［xE xN］T,相应地，系数矩阵A也分解为两部分，一部分为基矩阵，用E表示；另一部分为非基矩阵，用N表示。于是A=［E N］,E=［p1 p2 … pm］, N=［pm+1 pm+2 … pn］。式(3-1)中的约束条件重新表示为［E N］xE
xN=b(3-9)即ExE+NxN=b上式两端左乘E-1并移项，得xE=E-1b-E-1NxN (3-10) xN的分量为自由变量，它们取不同的值，就会得到方程组的不同解。特别地，如果令xN=0，则得到x=xE
xN=E-1b
0 (3-11) 称解x为方程组Ax=b的一个基本解。如果E-1b≥0，则称x=xE
xN=E-1b
0为满足约束条件的基本可行解（非负的基本解）. 
3.2.2 基本可行解的转换
基本可行解的转换就是在得到了某组基本可行解后，如何进一步改进获得更好的解，最终达到最优基本可行解。从3.2.1节的分析可知，获得改进的解是在满足约束条件的前提下使目标函数值增加（对于最大值问题）或使目标函数值减小（对于最小值问题）的解。设已经获得一组基本可行解：x (0) =E-1b
0其对应的目标函数值记为f0。设x=xE
xN是另一组基本可行解，将其代入目标函数中，得f=cTx=cTE cTNxE
xN
=cTExE+cTNxN=cTE(E-1b-E-1NxN)+cTNxN
=cTEE-1b+(cTN-cTEE-1N)xN
=f0+∑nj=m+1(cj-cTEE-1pj )xj
=f0+∑nj=m+1(cj-zj)xj (3-12)   如果每次将一个非基本变量转换为基本变量，并假定求目标函数的最大值，那么由式（3-12) 可知，选择求和项中系数cj-zj>0最大者对应的非基本变量进入基本变量，当该变量取正值时，可使目标函数增加最多。如果所有非基本变量的系数cj-zj不再有正值，则说明非基本变量的进基运算不会再使目标函数值增加，此时就终止计算，输出最优结果。非基本变量转换为基本变量后，则要将上一轮迭代中的一个基本变量转换为非基本变量，判断出基本变量表的条件由约束方程的消元计算格式给出。
设xk为进基变量，不失一般性，认为xk替换xr，在约束方程中相应地用pk替换pr, pk=［a′1k a′2k … a′mk］T, pr=［a′1r a′2r … a′mr］T，新的基矩阵为E(1)。为表示清楚起见，将pk标记为p(k)r，其元素相应地表示为p(k)r=［a′(k)1r a′(k)2r … a′(k)mr］T。因此基矩阵E(1)表示为E(1)=［p1 p2 … p(k)r … pm］
=10…a′(k)1r…0
01…a′(k)2r…0

…a′(k)rr…0

00…a′(k)mr…1  变量xk由零变为正值后，新的方程组的解为x′E=E-1(1)b′ (3-13) 其中，基矩阵E(1)的逆阵为E-1(1)=10…-a′(k)1ra′(k)rr…0
01…-a′(k)2ra′(k)rr…0

…1a′(k)rr…0

00…-a′(k)mra′(k)rr…1 (3-14)   这里认为初始基矩阵为单位阵。在基矩阵中用pk替换pr，就是将pk放在第r列的位置上。对于式（3-14）所示的矩阵，其逆矩阵只有第r列的元素发生变化，对角线上的元素为相应元素的倒数，该列上其他元素等于原来的元素取反再除以对角线上的元素。式（3-13）的解为x(k)r=b′ra′(k)rr (3-15) 
x(k)i=b′i-a′(k)irb′ra′(k)rr=b′i-a′(k)irx(k)r, i=1,2,…, m,i≠r (3-16)   由于设计变量非负，并假设设计变量在约束方程中的系数和右端项元素均大于零，因此x (k)r≥0自然满足；而式（3-16）中的变量非负意味着b′i-a′(k)irb′ra′(k)rr≥0即b′ia′(k)ir-b′ra′(k)rr≥0 (3-17) 当θ=xk=b′ra′(k)rr=min b′ia′(k)ir,a′(k)ir>0 (3-18) 时，则能保证用xk替换xr使所有基本变量非负。在线性规划中，通常称σj=cj-zj (3-19) 为判别数或检验数。对极小化问题，进基变量xk的下标与σk=ck-zk=minj(cj-zj)项的下标“k”对应，非基本变量xk的引入使目标函数f=f0+∑nj=m+1σjxj增加最多（最大值问题），或减少最多（最小值问题）。出基变量xEr的下标与θ=b′ra′rk=minb′ia′ik,a′ik>0项的下标“r”对应。式（3-18）和式（3-19）是单纯形法求解线性规划问题的重要判别式和检验规则。
3.2.3 单纯形法的计算步骤
应用单纯形法求解时，首先要了解怎样求得初始基本可行解，又怎样从一个基本可行解转到邻近的另一个基本可行解，又怎样检验得到的基本可行解是不是最优解。下面通过例题3-2说明这些问题。
【例3-2】 用单纯形法求下述问题的最优解：min z=-6x1+3x2-2x3
s.t. 2x1+x2+x3≤6
  x1+x3≤2
  x1,x2,x3≥0  解： 首先引入松弛变量x4,x5，把数学模型化为标准形式：min z=-6x1+3x2-2x3+0x4+0x5
s.t. 2x1+x2+x3+x4+0x5=6
  x1+0x2+x3+0x4+x5=2
  x1,x2,x3,x4,x5≥0  引入松弛变量后，变量总数n=5，约束方程数m=2（不含变量大于等于零的约束），因此有n-m=3个非基本变量，并令其为零进行求解。一个简单的做法就是选松弛变量x4,x5为基本变量，因为其系数列向量为单位基向量E=p4 p5=10
01。将基本变量用右端列向量和非基本变量表示，得x4=6-2x1-x2-x3
x5=2-x1-x3令非基本变量x1=x2=x3=0，则基本解为x4=6, x5=2记初始基本解为x(0)=\T  此解又满足式xj≥0,j=1,2,…,5，因此，x(0)是基本可行解，它对应着凸可行域的一个顶点。一般来说，对于约束条件全为“≤bi”形式(i=1,2,…,m)的线性规划问题，通过引入松弛变量，可较容易地找到一个初始基本可行解。
下一步，将初始基本可行解x(0)=\T代入目标函数表达式中，得z=-6×0+3×0-2×0+0×6+0×2=0  非基本变量x1=x2=x3=0对应的目标函数值z=0，为找出进基变量，将x4,x5代入原式得z=-6x1+3x2-2x3+c4(6-2x1-x2-x3)+c5(2-x1-x3)
=6c4+2c5+(-6-2×c4-c5)x1+(3-c4)x2+(-2-c4-c5)x3
=\10
01]6
2]+\-\10
01]211
101]x1
x2
x3]
=cTEE-1b+(cTN-cTEE-1N)xN
=-6x1+3x2-2x3  由上式看出，x1增加1个单位，目标函数值z下降6个单位；x2增加1个单位，z增加3个单位；x3增加1个单位，z值下降2个单位。如果使x1和x3成为正值，都能使目标函数向极小方向改善，那么当前解不是最优解。
选择的进基变量应是使目标函数改善最大的非基本变量进基。由前面的分析看到，在目标函数中，应选择有负系数，且负系数绝对值最大的非基本变量进基。例3-2中，目标函数中x1的系数为-6，所以x1应选为进基变量。这是因为当x1由当前的零变为正值时，使目标函数下降最大。
出基变量的选择也不是任意的，原则是要保证变量满足非负条件。为此，要考察约束条件。这两个方程均有变量x1要从0上升为正值，要从x4和x5这两个变量中选择一个出基（即从当前值下降到0) ，而另两个非基本变量x2和x3还要保持为零。
由式x4=6-2x1-x2-x3
x5=2-x1-x3得x4=6-2x1
x5=2-x1  x1从0变为正值时，x4和x5可从当前值下降为0，但不能成为负值（因为变量要满足非负条件）。由上式可以看出，x1取x1=θmin =min biai1=21=2时，x4和x5均为非负 (x4=2>0, x5=0) ，且θmin 使x5=0，因此选x5为出基变量。
已经确定了进基变量x1和出基变量x5，就可进行新的消元求解。继续求解下面的方程：0x5+x2+x3+x4+2x1=6
x5+0x2+x3+ 0x4+x1=2  此时，令非基本变量x2=x3=x5=0，求x1和x4的解。为了下面便于说明建立单纯形表的过程，用初等变换（消元）求解上面的方程，结果为-2x5+x2-x3+x4+0x1=2
x5+0x2+x3+0x4+x1=2解得x1=2, x4=2  再将x1和x4用约束方程的非基本变量表示，得x4=2-x2+x3+2x5
x1=2-x3-x5将其代入目标函数，得z=-6(2-x3-x5)+3x2-2x3+c4(2-x2+x3+2x5)+c5x5整理得z=-6×2+c4×2+(3-c4)x2+(-2+6+c4)x3+(c5+6+2c4)x5由于所有非基本变量的系数均为非负，没有进一步可使目标函数减少的非基本变量，因此迭代结束，最优解为x1=2,x2=0,x3=0,f=-12. 
根据3.2.2节的介绍及上面的计算，单纯形法的一般步骤可归纳如下。
 (1)  把线性规划问题的约束方程组表达成标准形方程组，然后找出一个基本可行解作为初始基本可行解。对等式约束或“≥bi”形式的约束，如果不易得出初始基本可行解，则需