多2图解法+15坐标系，将约束条件在图上表示：确立满足约束条件的解的范围：绘制出目标函数的图形；确定最优解．用本章例2来具体说明图解法的原理步骤、例2的数学模型如下：(1.7a)max±=2x1+3x2(1.7b)12s.t.(2a+2r2431≤16(1.7c)≤15(1.7d)52(1.7e)[31,2≥01.先分析约束条件是如何图示的，本例只有两个变量1和2：以x1和x2为坐标轴作直角坐标系，因1≥0，2≥0，所以只有在第一象限内的点才满足约束（1.7e）.约束条件2x1+22≤12是一个不等式，先取2，+22=12，这是一条直线，在坐标系中画出这条直线，这条直线把第一象限的平面分为两部分，凡落在该直线右上方平面内的点均有2，+2z2>12，落在该直线左下方乎面内的点均有21+22<12.所以21+22≤12表示落在直线21+22=12上的和这条直线左下方半平面内的所有点，于是可用三角形OAB及其边界上的所有点表示对1≥0，2≥0及21+222≤12这三个约束条件的满足（见图1 -2).2.同理，满足约束条件4x1≤16的所有点是位于4.1=16这条直线上及这条直线左半边平面内；满足5元2≤15的所有点位于52=15这条直线上及这条直线下方的半平面内*21*2↓B(0,6)2x,+2x-124x,-162x,+2x,=125x,=152420,A(6,0)4Sx9.图1-3图1-2同时满足这些约束条件的点必然落在由元1、2两个坐标轴与上述四条直线所围成的多边形OQ：Q：Q3Q4内及该多边形的边界上（兜图1-3）从图1-3可以看到多边形OQ，Q2Q：Q4是凸的，后面我们要证明，如果
.16第1章线性规划及单纯形法线性规划问题存在可行域，则可行域一定是个凸集.3.目标函数的几何意义．目标函数22=2z1+3r2中，之是待定的值，将其改2一号+号，由解析几何知，写为32=的一族平行的这是参量为2、斜率为一3直线，如图1－4所示.从图1－4看出，这族平行线中，离0点越远的直线，的值越大，若对71、02的取值无限制，的值可以无限增大，图1-4但在线性规划问题中，对1、2的取值范围是有限制的，这就是图1一2中约束条件所包含的范围4.最优解的确定.最优解必须是满足约束条件要求，并使目标函数达到最优值，因此z1x2的取值范围只能从凸多边形OQ，Q2QQ4中去寻找.将图1-3和图1-4予以合并得到图1-5.可以看出，当代表目标函数的那条直线由O点开始向右上方移动时，之的值逐渐增大，一直移动到目标函数的直线与约束条件包围成的凸多边形相切时为止，切点就是代表最优解的点．因为再继续向右上方移动，z值仍然可以增大，但在目标函数的直线上找不出一个点位于约束条件包围成的凸多边形内部或边界上，本例中自标函数直线与凸多边形的切点为Q3，该点的坐标可由求解直线方程52=15和21+22=12得到，为（1，2）=（3，3）.将其代人目标函数得2=15.即常山机器厂生产的最佳方案为I、Ⅱ产品各生产3件，可获利15元本例中我们用图解法得到的问题的最优解是惟一的。但在线性规划问题的计算中，解的情况还可能出现下列几种：1，无穷多最优解.如将本例中的目标函数改变为maxz3r，+312，则目标函数的图形恰好与约束条件（1.7b）平行：当目标函数直线向右上方移动时，他与凸多边形相切时不是一个点，而是在整个线段Q2Q3上相切（见图1~6）.这时在Q2点、Q3点及Q2Q线段上的任意点都使目标函数值×达到最大，即该线性规划问题有无穷多最优解，也称具有多重最优解，2.无界解（或无最优解），如果例2中的约束条件只剩下（1.7c）和（1.7e），其他条件（1.7b）、（1.7d）不再考虑．用图解法求解时，可以看到变量2的取值可以无限增大，因而目标函数的值之也可以一直增大到无穷（见图1-7），这种情况下称问题具有无界解或无最优解．其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束
82图解法1712X2230x,012.图1-6图1 - 53.无可行解，如下述线性规划模型max=2x+3r2s.t.[221+2r2≤121+2x21431,x2≥0用图解法求解时找不到满足所有约束条件的公共范围（见图1一8），这时问题无可行解，其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正x2lX2l-L图 1 - 8图1-7图解法虽只能用来求解只其有两个变量的线性规划问题，但它的解题思路和几何上直观得到的一些概念判断，对下面要讲的求解一般线性规划问题的单纯形法有很大启示：（1）求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解；（2）若线性规划问题的可行域存在，测可行域是一个凸集；（3）若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷
.18第1章线性规划及单纯形法多的话）一定能够在可行域（凸集）的某个顶点找到；（4）解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值，比较周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该项点就是最优解的点或最优解的点之一，否则转到比这个点的日标函数值更优的另一顶点，重复上述过程，一直到找出使目标函数值达到最优的顶点为止，83单纯形法原理单纯形法是求解一般线性规划问题的基本方法，系1947年由丹齐格（G.B.Dantzig）提出．下面介绍这种方法的理论依据3一1预务知识：凸集和项点凸集对一个给定的几何图形，通常可从直观上判断其凹凸性，但这样做一方面不严格，容易产生错误；另一方面，如果一个几何形体给出的只是解析表达式，则无法从直观上进行判断．凸集的严格定义是：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集，由于X1、X2的连线可表示为aX,+ (1-a) X2 (0<a<1)因此凸集定义用数学语言可表为：对任何X,EC，X,EC，有aXi+（1-a）X2EC（0<a<1），则称C为凸集，在图1一9中（a）、（b）是凸集，（c)、（d）不是凸集，(d)(c)(a)(b)图1-9顶点凸集C中满足下述条件的点X称为顶点：如果C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点，或者这样叙述：对任何X,EC，X2EC，不存在X=aX,+（1-a）X2（0<a<1)，则称X是凸集C的顶点3一2几个基本定理的证明定理1若线性规划问题存在可行解，则问题的可行域是凸集
.19:83单纯形法原理【证】思路：若满足线性规划约束条件P,z，=b的所有点组成的几何图形C是凸集，根据凸集定义，C内任意两点X1X2连线上的点也必然在C内.下面给予证明，设X=（11，12，…，1)，X2=（21，22，…，2)为C内任意两点，即X,EC，X2EC，将X、X2代人约束条件（1.3b）有2p,2, = bZp,=b;(1.8)1=1X1、X2连线上任意一点可以表示为：(0<u<1)X=aXr+ (l-a) X2(1.9)(0<a<1,j=l,",n)或X,=ar1,+(1-a) 2)将式（1.9）代入约束条件并由式（1.8）得：p,[ar, + (1 - a)2,] =EPar+PEPaPar2.1=11=1J=11-1-1ab+b-ab=b所以X=aX,+（1-a）X2EC由于集合中任意两点连线上的点均在集合内，所以C为凸集引理线性规划问题的可行解X=（1，"，工）T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的.【证】（1）必要性，由基可行解的定义显然，（2）充分性.若向量P1，P2，"，P线性独立，则必有k≤m；当k=m时，它们恰好构成个基，从而X=（x1，2，，xm，0，…，0)为相应的基可行解，当<m时，则一定可以从其余列向量中找出（m一）个与P1,P2，，P构成一个基，其对应的解恰为X，所以据定义它是基可行解。定理2线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点.【证】本定理需要证明：X是可行域顶点一X是基可行解，下面采用的是反证法，即证明：X不是可行域的顶点一X不是基可行解，下面分两步来证明.（1）X不是基可行解=→X不是可行域的顶点，不失一般性，假设X的前m个分量为正，故有2pa.=b(1.10)7由引理知Pi，，P线性相关，即存在一组不全为零的数，（i=1，…，m），使得有