線性規劃中最優解的探究

【摘要】線性規劃（LP）是運籌學中較早發展起來并已經廣泛地應用于各個領域的一個重要數學理論和方法。在高中數學教學中，線性規劃問題最優解是很重要的一部分，本文研究和討論了線性規劃最優解的幾種情形及其判定，彌補和優化了教材和專著在這方面的不足，為用線性規劃解決實際問題提供了理論依據。同時，對高中學生在學習數學時如何靈活的運用課本素材，以及學生創新思維的形成及培養方面起到了很好的示范作用。

【關鍵詞】高中數學 線性規劃 最優解

【中圖分類號】G633.6 【文獻標識碼】A 【文章編號】2095-3089（2019）33-0134-02

一、可行域中最優解的確定問題

先來看一道例題：

例1 已知變量x，y滿足下列條件

X≥0，Y≥0，X+3Y≤15，X+Y≤6， 3X+Y≤15

求目標函數Z=3X+2Y的最優解。

解：滿足這個不等式組的（X，Y）所存在的范圍即可行域如下圖所示

∵目標函數為Z=3X+2Y

∴作直線L：3X+2Y=t（t∈R），則是直線在X軸上的截距。

∴L向右平移？圳則變大？圳t變大，但這里的問題是將直線3X+2Y=t向右平移時，它究竟是在經過M點，還是經過N點時，t取得最大值呢？這就需要比較目標函數所表示直線的斜率和相關直線的斜率的大小。

∵目標函數z=3x+2y的斜率是-，而相關直線3x+y=15的斜率是-3.

x+3y=15的斜率是-. x+y=6的斜率是-1.

又∵-3<-<-1<-.

最優點在斜率為-3和斜率為-1的直線的交點M處，聯立對應的方程得方程組

3x+y=15x+y=6 解得M（）.

Zmax=3×+2×=16.5 ， 顯然Zmax=3×0+2×0

解題反思：目標函數在可行域中最優解的位置與目標函數所表示的直線的斜率及其相關直線的斜率有關，當最優解的位置不能從圖形中明顯看出來時，可在局部范圍比較它們斜率的大小（當斜率不存在時可比較其傾斜角的大小）。

二、初始等值線的選擇問題

例2 設z=2y-2x+4 ，式中x，y滿足條件 0≤x≤1，0≤y≤2，2y-x≥1， 求z的最大值和最小值。

解：作出滿足不等式組0≤x≤1，0≤y≤2，2y-x≥1，的可行域如下圖陰影所示。

再作出一組z=2y-2x+4的平行直線系，即等值線2y-2x=t，我們選t=2，就是說讓初始等值線過M點，即x=1，y=2時得t=2，作出2y-2x=2，這就是這里所選的初始等值線，有了這條初始等值線作參照，可明顯看出，平行直線過點A（0，2）時，t取得最大值，過點B（1，1）時，t有最小值，相應地Zmin=2×1-2×1+4=4，Zmax=2×2-2×0+4=8。

解題反思：按慣例，作目標函數等值線時，一般先作Ax+By=0 再作它的平行直線系找出最優解，但在實際問題中，究竟哪一點是我們所尋找的最優解的位置呢？事實上，最優解的確定與目標函數對應直線的斜率，以及相關直線的斜率有關，這在前面已經說到。這里所說的是初始等值線的選擇問題，根據本例可得出結論：在作目標函數初始等值線時，可靈活選擇其為Ax+By=Z′，而對Z′的選擇，原則是Z′與系數A，B有關，且在數形結合時，可明顯比較出相關直線斜率或傾斜角的大小，進而直觀的在可行域確定最優解的位置，如上例所選Z′=2就是很好的例證。

三、 關于整數點的最優解

求目標函數整數最優解，可利用可行域中整數網格的交點，但是利用此法對作圖要求較高，所以，有時也利用其它方法調整最優解，如通過限制一個變量的范圍，找到橫坐標（或縱坐標）中的整數，再加以比較、驗證而得到。

例3 X，Y滿足不等式組x+y≥122x+y≥15x+3y≥27x≥0，y≥0 （x，y∈Z）

求目標函數z=x+2y的最小值。

解：作出不等式組表示的平面區域，如右圖所示。

比較目標函數與相關直線的斜率得：

∵ -2<-1<-<， ∴ 由方程組x+y=12x+3y=27得A點坐標為（），但x，y∈z，∴A點不是整數最優解，需要調整。可令x=5，此時結合圖形，y的約束條件是x+3y≥27，∴y≥∵y∈z，∴y=8 得一整數點（5，8），再令y=8，此時，約束條件為2x≥15x+y≥12？圯 x≥4x≥.∴x=4.又得一整點（4，8），比較（4，8）與（5，8），顯然，可行域中使目標函數取得最小值的整數解是（4，8），即Zmin=4+2×8=20.

作者簡介：

牛郁宇（1971.5-），女，漢族，甘肅省蘭州市人，本科，中教一級，研究方向：中學數學教育。