簡單的線性規(guī)劃問題解法探索

李曉斌　雒莎莉

簡單的線性規(guī)劃問題的常見解法是直線平移法和交點代入法，兩種方法首先都是在直角坐標(biāo)系中畫出約束條件對應(yīng)的可行域，再進行問題解答.畫出可行域，分析目標(biāo)函數(shù)是解答這類問題的常規(guī)思路，但上面的思路能否進行優(yōu)化，很是困惑，一直思考著.困惑的原因是，直線方程的一般式Ax+By+C=0與對應(yīng)的不等式Ax+By+C>0（<0）的關(guān)系僅符號不同，表達式是相同的，能否僅從表達式的系數(shù)入手，通過系數(shù)間的關(guān)系確定由不等式（組）自身判斷所表示的平面區(qū)域？解答線性目標(biāo)函數(shù)的最值問題是否可以優(yōu)化直線平移法和交點代入法，不用求解所有交點坐標(biāo)，而能夠快速判定最優(yōu)解對應(yīng)的交點，進而求解呢？經(jīng)過筆者研究，運用直線的法向量可以使困惑釋解，剖析如下：

1不等式Ax+By+C>0（<0）表示的平面區(qū)域的確定方法

命題1已知直線l：Ax+By+C=0的法向量為n=（A，B），則向量n的方向是不等式Ax+By+C>0表示的平面區(qū)域在直線l：Ax+By+C=0的一側(cè)的方向；向量-n的方向是不等式Ax+By+C<0表示的平面區(qū)域在直線Ax+By+C=0的一側(cè)的方向.

證明設(shè)點M（x0，y0）是直線l：Ax+By+C=0上任一點，N（x1，y1）是直線外一點，且MN⊥l，直線l的法向量n=（A，B），設(shè)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表示不等式表示的平面區(qū)域在對應(yīng)直線一側(cè)的方向，故k>0時向量n的方向是不等式Ax+By+C>0表示的平面區(qū)域在直線Ax+By+C=0的一側(cè)的方向；k<0時向量n的相反方向是不等式Ax+By+C<0表示的平面區(qū)域在直線Ax+By+C=0的一側(cè)的方向.

例1不等式3x-2y+6>0表示平面區(qū)域在直線3x-2y+6=0的（）.

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

解析直線3x-2y+6=0的法向量n=（3，-2）在直角坐標(biāo)系里指向右下方，又不等號是“>”，由命題1可知不等式3x-2y+6>0表示平面區(qū)域在直線3x-2y+6=0的右下方，選C.

2可行域開閉的判定方法和線性目標(biāo)函數(shù)的最值問題求解方法

圖1因為不等式Ax+By+C<0（≤0）總可以化為Ax+By+C>0（≥0）的形式，所以下面為了研究問題的方便，規(guī)定：①可行域不為空集；②約束條件里不等式先轉(zhuǎn)換為Ax+By+C>0（≥0）的形式.給出下面幾個定義，再做研究.

定義1將法向量n=（A，B）稱為不等式Ax+By+C>0所表示的平面區(qū)域的指向向量.

定義2如圖1，按逆時針旋轉(zhuǎn)的共起點的三個向量a，b，c，稱向量b在向量a，c之間.

定義3若向量a按逆時針旋轉(zhuǎn)θ后與向量b同向（θ∈[0，2π]），稱θ為從向量a到向量b的旋轉(zhuǎn)角.

關(guān)于線性目標(biāo)函數(shù)最值問題有如下命題：

命題2約束條件中的不等式組的指向向量在直角坐標(biāo)系中以原點為起點，按逆時針標(biāo)出依次記為n1，n2，…，nk，指向向量n1，n2，…，nk所對應(yīng)的直線分別為l1，l2，…，lk，直線lm的方程為amx+bmy+cm=0（m=1，2，…，k），nm=（am，bm），線性目標(biāo)函數(shù)z=ax+by+c的目標(biāo)向量為n=（a，b）.則有

（1）若存在向量nm，nm+1的旋轉(zhuǎn)角θ滿足θ>π，則可行域是無窮開區(qū)域，且此時直線lm和lm+1的交點不是可行域的頂點；若對任意向量nm，nm+1（m∈[1，k]，規(guī)定m=k時，nm+1=n1，后同）的旋轉(zhuǎn)角θ滿足θ∈（0，π），則可行域是閉區(qū)域且直線lm和lm+1的交點是可行域的頂點.

（2）若目標(biāo)向量n在向量nm，nm+1之間，且向量nm，nm+1的旋轉(zhuǎn)角θ滿足θ∈（0，π），則目標(biāo)函數(shù)z=ax+by+c在點A處取得最小值；若向量-n在向量nm，nm+1之間，則線性目標(biāo)函數(shù)z=ax+by+c在點A處取得最大值（如圖2）.

推論若向量n與向量nm（m=1，2，…，k）共線時，則目標(biāo)函數(shù)z=ax+by+c取最小值的最優(yōu)解有無數(shù)個，且所有最優(yōu)解在直線lm上；若向量-n與向量nm（m=1，2，…，k）共線時，則目標(biāo)函數(shù)z=ax+by+c取最大值的最優(yōu)解有無數(shù)個，且所有最優(yōu)解在直線lm上.

由于任意兩個相交直線的法向量所成角θ∈（0，π），易證命題2（1）成立，下面給出命題2（2）的證明.

圖2證明因為目標(biāo)向量n在向量nm，nm+1之間，且nm到nm+1的旋轉(zhuǎn)角小于π，如圖2，由平面向量基本定理知，存在唯一實數(shù)對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=定值.其中等號當(dāng)且僅當(dāng)amx+bmy+cm=0，

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

即目標(biāo)函數(shù)z=ax+by+c在直線lm和lm+1的交點A處取得最小值.同理可以證明目標(biāo)向量的相反向量-n在向量nm，nm+1之間時，線性目標(biāo)函數(shù)z=ax+by+c在點A處取得最大值.

以上結(jié)論的逆命題也成立，其他結(jié)論的證明留給有興趣的讀者思考完成.

3應(yīng)用舉例

例2若x、y滿足條件2x+y-12≤0，

3x-2y+10≥0，

x-4y+10≤0，求z=x+2y的最小值，并求出相應(yīng)的x、y的值.

解析根據(jù)條件作出可行域，及對應(yīng)的指向向量如圖3所示.

顯然目標(biāo)向量n在向量（3，-2）和（-1，4）之間，有命題2（2）知，目標(biāo)函數(shù)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.設(shè)z=ax+y（a>0），若z取最大值時對應(yīng)的點有無數(shù)個，求a的值.

解析目標(biāo)向量n=（a，1），指向向量如圖4所示，若z取最大值時對應(yīng)的點有無數(shù)個，由命題2（2）的推論可知向量（-a，-1）與（-3，-5）同向，即-5a+3=0，a=35.

圖4圖5例5已知變量x，y滿足約束條件x+y≤2，

x-y≤0，

x≥0.目標(biāo)函數(shù)z=ax+y只在點（1，1）處取最小值，則有（）.

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

解析顯然點（1，1）是直線x+y=2和x-y=0的交點，要使目標(biāo)函數(shù)z=ax+y只在點（1，1）處取最小值，可知向量（a，1）在向量（-1，-1）和（-1，1）之間，如圖5所示，易知a<-1.選D.

通過直線的法向量可以直接判斷對應(yīng)的不等式表示的平面區(qū)域，而線性目標(biāo)函數(shù)的最值相關(guān)問題可以先畫出指向向量圖，再作出目標(biāo)向量，根據(jù)目標(biāo)向量n及目標(biāo)向量的相反向量-n在指向向量圖中的位置關(guān)系進行判斷，直接求出線性目標(biāo)函數(shù)的最值.

后語：在教學(xué)過程中，經(jīng)常會有一些感悟，稍縱即逝，一段時間后再次思考卻很難抓住.只有帶著思考去學(xué)，去教，去研究，緊緊抓住靈光一閃的那刻，可以讓我們發(fā)現(xiàn)更廣闊的天地，同時文中欠慮之處，希望各位同仁不吝指正.