简单的线性规划问题解法探索

李晓斌　雒莎莉

简单的线性规划问题的常见解法是直线平移法和交点代入法，两种方法首先都是在直角坐标系中画出约束条件对应的可行域，再进行问题解答.画出可行域，分析目标函数是解答这类问题的常规思路，但上面的思路能否进行优化，很是困惑，一直思考着.困惑的原因是，直线方程的一般式Ax+By+C=0与对应的不等式Ax+By+C>0（<0）的关系仅符号不同，表达式是相同的，能否仅从表达式的系数入手，通过系数间的关系确定由不等式（组）自身判断所表示的平面区域？解答线性目标函数的最值问题是否可以优化直线平移法和交点代入法，不用求解所有交点坐标，而能够快速判定最优解对应的交点，进而求解呢？经过笔者研究，运用直线的法向量可以使困惑释解，剖析如下：

1不等式Ax+By+C>0（<0）表示的平面区域的确定方法

命题1已知直线l：Ax+By+C=0的法向量为n=（A，B），则向量n的方向是不等式Ax+By+C>0表示的平面区域在直线l：Ax+By+C=0的一侧的方向；向量-n的方向是不等式Ax+By+C<0表示的平面区域在直线Ax+By+C=0的一侧的方向.

证明设点M（x0，y0）是直线l：Ax+By+C=0上任一点，N（x1，y1）是直线外一点，且MN⊥l，直线l的法向量n=（A，B），设n=kMN.

则（A，B）=k（x1-x0，y1-y0）

即x1=x0+Ak，

y1=y0+Bk，

又M在直线l上，所以Ax0+By0+C=0，即C=-（Ax0+By0），所以Ax1+By1+C=A（x0+Ak）+B（y0+Bk）y1+C=1k（A2+B2），所以Ax1+By1+C与k同号.

由于向量MN表示不等式表示的平面区域在对应直线一侧的方向，故k>0时向量n的方向是不等式Ax+By+C>0表示的平面区域在直线Ax+By+C=0的一侧的方向；k<0时向量n的相反方向是不等式Ax+By+C<0表示的平面区域在直线Ax+By+C=0的一侧的方向.

例1不等式3x-2y+6>0表示平面区域在直线3x-2y+6=0的（）.

A.左下方B.左上方C.右下方D.右上方

解析直线3x-2y+6=0的法向量n=（3，-2）在直角坐标系里指向右下方，又不等号是“>”，由命题1可知不等式3x-2y+6>0表示平面区域在直线3x-2y+6=0的右下方，选C.

2可行域开闭的判定方法和线性目标函数的最值问题求解方法

图1因为不等式Ax+By+C<0（≤0）总可以化为Ax+By+C>0（≥0）的形式，所以下面为了研究问题的方便，规定：①可行域不为空集；②约束条件里不等式先转换为Ax+By+C>0（≥0）的形式.给出下面几个定义，再做研究.

定义1将法向量n=（A，B）称为不等式Ax+By+C>0所表示的平面区域的指向向量.

定义2如图1，按逆时针旋转的共起点的三个向量a，b，c，称向量b在向量a，c之间.

定义3若向量a按逆时针旋转θ后与向量b同向（θ∈[0，2π]），称θ为从向量a到向量b的旋转角.

关于线性目标函数最值问题有如下命题：

命题2约束条件中的不等式组的指向向量在直角坐标系中以原点为起点，按逆时针标出依次记为n1，n2，…，nk，指向向量n1，n2，…，nk所对应的直线分别为l1，l2，…，lk，直线lm的方程为amx+bmy+cm=0（m=1，2，…，k），nm=（am，bm），线性目标函数z=ax+by+c的目标向量为n=（a，b）.则有

（1）若存在向量nm，nm+1的旋转角θ满足θ>π，则可行域是无穷开区域，且此时直线lm和lm+1的交点不是可行域的顶点；若对任意向量nm，nm+1（m∈[1，k]，规定m=k时，nm+1=n1，后同）的旋转角θ满足θ∈（0，π），则可行域是闭区域且直线lm和lm+1的交点是可行域的顶点.

（2）若目标向量n在向量nm，nm+1之间，且向量nm，nm+1的旋转角θ满足θ∈（0，π），则目标函数z=ax+by+c在点A处取得最小值；若向量-n在向量nm，nm+1之间，则线性目标函数z=ax+by+c在点A处取得最大值（如图2）.

推论若向量n与向量nm（m=1，2，…，k）共线时，则目标函数z=ax+by+c取最小值的最优解有无数个，且所有最优解在直线lm上；若向量-n与向量nm（m=1，2，…，k）共线时，则目标函数z=ax+by+c取最大值的最优解有无数个，且所有最优解在直线lm上.

由于任意两个相交直线的法向量所成角θ∈（0，π），易证命题2（1）成立，下面给出命题2（2）的证明.

图2证明因为目标向量n在向量nm，nm+1之间，且nm到nm+1的旋转角小于π，如图2，由平面向量基本定理知，存在唯一实数对s、t，使得n=s·nm+t·nm+1且s>0，t>0.

即（a，b）=s·（am，bm）+t·（am+1，bm+1）=（s·am+t·am+1，s·bm+t·bm+1）.

所以a=s·am+t·am+1，

b=s·bm+t·bm+1.

因为amx+bmy+cm≥0所以amx+bmy≥-cm，同理am+1x+bm+1y≥-cm+1，

于是z=ax+by+c=（s·am+t·am+1）x+（s·bm+t·bm+1）y+c=s·（amx+bmy）+t·（am+1x+bm+1y）+c

≥-（s·cm+t·cm+1）+c=定值.其中等号当且仅当amx+bmy+cm=0，

am+1x+bm+1y+cm+1=0时成立.

即目标函数z=ax+by+c在直线lm和lm+1的交点A处取得最小值.同理可以证明目标向量的相反向量-n在向量nm，nm+1之间时，线性目标函数z=ax+by+c在点A处取得最大值.

以上结论的逆命题也成立，其他结论的证明留给有兴趣的读者思考完成.

3应用举例

例2若x、y满足条件2x+y-12≤0，

3x-2y+10≥0，

x-4y+10≤0，求z=x+2y的最小值，并求出相应的x、y的值.

解析根据条件作出可行域，及对应的指向向量如图3所示.

显然目标向量n在向量（3，-2）和（-1，4）之间，有命题2（2）知，目标函数z=x+2y的最小值在直线3x-2y+10=0和x-4y+10=0的交点（2，-2）处取得，此时zmin=-2.图3例3已知变量x，y满足x-4y≤-3，

3x+5y≤25，

x≥1.设z=ax+y（a>0），若z取最大值时对应的点有无数个，求a的值.

解析目标向量n=（a，1），指向向量如图4所示，若z取最大值时对应的点有无数个，由命题2（2）的推论可知向量（-a，-1）与（-3，-5）同向，即-5a+3=0，a=35.

图4图5例5已知变量x，y满足约束条件x+y≤2，

x-y≤0，

x≥0.目标函数z=ax+y只在点（1，1）处取最小值，则有（）.

A.a>1B.a>-1C.a<1D.a<-1

解析显然点（1，1）是直线x+y=2和x-y=0的交点，要使目标函数z=ax+y只在点（1，1）处取最小值，可知向量（a，1）在向量（-1，-1）和（-1，1）之间，如图5所示，易知a<-1.选D.

通过直线的法向量可以直接判断对应的不等式表示的平面区域，而线性目标函数的最值相关问题可以先画出指向向量图，再作出目标向量，根据目标向量n及目标向量的相反向量-n在指向向量图中的位置关系进行判断，直接求出线性目标函数的最值.

后语：在教学过程中，经常会有一些感悟，稍纵即逝，一段时间后再次思考却很难抓住.只有带着思考去学，去教，去研究，紧紧抓住灵光一闪的那刻，可以让我们发现更广阔的天地，同时文中欠虑之处，希望各位同仁不吝指正.