第三章线性规划的解法§3.1重点、难点提要一、线性规划问题的图解法及几何意义1．图解法。
线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。
图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。
（1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为：1）在平面上建立直角坐标系；2）图示约束条件，找出可行域。
具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。
求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点；3）图示目标函数直线。
给定目标函数Z一个特定的值k，画出相应的目标函数等值线；4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。
具体地，当k值发生变化时，等值线将平行移动。
对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。
（2）线性规划问题的几种可能结果：1）有唯一最优解；2）有无穷多个最优解；3）无最优解(无解或只有无界解)。
2．重要结论。
（1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点；（2）每一个基可行解对应可行域的一个顶点。
若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。
（3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对于n 个变量m 个约束方程的线性规划问题，基可行解的个数不会超过!!()!m n n m n m C =-。
单纯形法单纯形法的基本思想（Simplex method ）简要地讲就是，每次从单纯形上的⼀个顶点⾛到⼀个更好的顶点直到找到最⼩（⼤）值。
线性规划是由两部分组成的：线性的⽬标函数和线性的限制条件。
限制条件由等式和不等式组成。
每⼀个线性的等式在⼏何上就限制了可⾏解必须在⼀个超平⾯上。
每⼀个线性的不等式在⼏何上就限制了可⾏解必须在⼀个超平⾯的⼀边。
于是这些限制条件就限制了可⾏解必须在某个单纯形上，所谓单纯形就是很多超平⾯围成的区域。
由于⽬标函数也是线性的，所以如果最优解存在，⼀定有⼀个最优解是单纯形上的⼀个顶点。
所以⽬标变成了找单纯形上最好的顶点。
最好的顶点怎么找？最直接的办法就是逐个找。
聪明⼀点的办法是，每次找到的新的顶点都⽐原来的好。
单纯形法就是这类⽅法。
问题描述min z =CXs.t.AX =b X ≥0单纯形法基本思路：从⼀个初始的基本可⾏解出发，选中⼀条达到最优基本可⾏解的最佳途径。
确定初始的基本可⾏解约束⽅程AX =b 表⽰为：AX =(B N )X B X N=BX B +NX N =b得：X B =B −1b −B −1NX N 若令所有⾮基变量X N =0，则基变量X B =B −1b由此可得初始的基本可⾏解X =B −1b 0判断现⾏的基本可⾏解是否最优假如已经求得⼀个基本可⾏解X =B −1b 0将其代⼊⽬标函数，可求得相应的⽬标函数值z =CX =C B C NB −1b 0=C B B −1b其中，C B 和C N 分别表⽰基变量和⾮基变量所对应的⽬标函数系数⼦向量.怎么判断C B B −1b 是否已经达到最⼩值？min z =C BB −1b+(C N −C BB −1N )XN s.t.X B =B −1b −B −1NX N X B ,X N ≥0定理1 （最优化准则）如果σN ≥0，则基可⾏解x =B −1b 0为原问题的最优解.其中，σN =C N −C B B −1N =(σm +1,σm +2,⋯,σn )称为⾮基变量X N 的检验向量，它的各个分量称为检验数.若σN 的每⼀个检验数均⼤于等于0，即σN ≥0，则⽬前的基本可⾏解就是最优解.()()()()()()基本可⾏解的改建— 基变换先从检验数为负的⾮基变量中确定⼀个换⼊变量，使它从⾮基变量变成基变量，再从原来的基变量中确定⼀个换出变量，试它从基变量变成⾮基变量，由此可得到⼀个新的基本可⾏解.换⼊变量的确定—最⼤减⼩原则选取最⼩负检验数所对应的⾮基变量为换⼊变量，即若min {σj |σj <0,m +1≤j ≤n }=σm +k则选取对应的x m +k 为换⼊变量.由于σm +k <0且为最⼩，因此当x m +k 由零增⾄正值时，可使⽬标函数值最⼤限度的减⼩.换出变量的确定—最⼩⽐值原则如果确定确定x m +k 为换⼊变量，设p m +k 为A 中与x m +k 对应的系数列向量.现在需要在X B 中确定⼀个基变量为换出变量. 当x m +k 由零慢慢增加到某个值时，为保持解的⾮负性，可以按最⼩⽐值原则确定换出变量：θ=min {(B −1b )i(B −1p m +k )i|(B−1p m +k )i >0,1≤i ≤m }=(B −1b )l(B −1p m +k )l则选取对应的基变量x l 为换出变量.例⼦min z =−5x 1−2x 2−3x 3+x 4−x 5s.t.x 1+2x 2+2x 3+x 4=83x 1+4x 2+x 3+x 5=7x 1,x 2,x 3,x 4,x 5≥0解：已知A =1221034101，b =87，C =(−5,−2,−3,1,−1)1. 确定初始基本可⾏解基变量x 4，x 5，B =P 4P 5=1001，X B =x 4x 5T ，X N =x 1x 2x 3T ，B =1001，N =122341，C B =1−1，X N =−5−2−3b =87T令X N =0，则X B =B −1b =87T ，X =00087Tz =C B B −1b =11. 检验X 是否最优检验向量σN =C N −C B B −1N =(−3,0,−4)因为σ1和σ3均⼩于0，所以X =00087T 不是最优解.1. 基本可⾏解的改进（1）选取换⼊变量{[][]()[]()()[][]()()()()()()因为min {−3,−4}=−4，选取x 3为换⼊变量（2）选取换出变量B −1b =87T ，B −1P 3=21T >0，因为min {82,71}=82，选取x 4为换出变量.1. 求解改进了的基本可⾏解— 旋转运算对约束⽅程组的增⼴矩阵A b 施以初等⾏变换，使换⼊变量x 3所对应的系数向量P 2变换成换出向量x 4所对应的单位向量P 4，保持x 5的系数向量P 5为单位向量不变.122108341017⇒121112045230−1213基变量x 3，x 5，B =P 3P 5=1001，X B =x 3x 5T ，X N =x 1x 2x 4T ，B =1001，N =12112523−12，C B =−3−1，X N =−5−2−1b =43T令X N =0，则X B =B −1b =43T ，X =00403Tz =C B B −1b =−151. 转2，检验X 是否最优检验向量σN =C N −C B B −1N =(−1,4,2)因为σ1⼩于0，所以X =00403T 不是最优解.1. 转3，基本可⾏解的改进（1）选取换⼊变量因为σ1=−1，选取x 1为换⼊变量（2）选取换出变量B −1b =43T ，B −1P 3=1252T>0，因为min {41/2,35/2}=35/2，选取x5为换出变量.1. 转4，求解改进了的基本可⾏解对约束⽅程组的增⼴矩阵施以初等⾏变换，使换⼊变量x 1所对应的系数向量P 1变换成换出向量x 5所对应的单位向量P 5，保持x 3的系数向量P 3为单位向量不变.()()[]()()()[]()()[][]()()()()()()()()121112045230−1213⇒25135−151751650−152565基变量x3，x1，B=P3P1=10 01，X B=x3x1T，X N=x2x4x5T，B=1001，N=2535−1565−1525，C B=−3−5，X N=−21−1b=17565T令X N=0，则X B=B−1b=17565T，X=65017500Tz=C B B−1b=−8151. 转2，检验X是否最优检验向量σN=C N−C B B−1N=(265,95,25)因为所有检验系数均⼩于0，所以X=65017500T是最优解.参考资料()() ()[]()()[][]()()()()()()Processing math: 100%。
