淺談解簡單線性規(guī)劃問題的圖解法

文香丹

摘要：線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一，也是運(yùn)籌學(xué)的最基本的方法之一。它是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。最近十多年來，線性規(guī)劃無論是在深度還是在廣度方面又都取得了重大進(jìn)展。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。

關(guān)鍵詞：圖解法；可行域；最優(yōu)解

中圖分類號：G642.4 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2014）39-0100-02

線性規(guī)劃問題研究的是在一組線性約束條件下一個線性函數(shù)最優(yōu)問題。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。簡單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時還可利用目標(biāo)函數(shù)與可行區(qū)域的關(guān)系利用圖解法求解該問題。圖解法的步驟為：（1）畫出直角坐標(biāo)系；（2）依次做每條約束線，標(biāo)出可行域的方向，并找出它們共同的可行域；（3）任取一目標(biāo)函數(shù)值作一條目標(biāo)函數(shù)線（稱等值線），根據(jù)目標(biāo)函數(shù)（最大或最?。╊愋停揭圃撝本€即將離開可行域上，則與目標(biāo)函數(shù)線接觸的最終點即表示最優(yōu)解。

一、無界

例1 用圖解法解線性規(guī)劃。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：該問題的可行區(qū)域如圖1所示。

目標(biāo)函數(shù)z=-2x1+x2沿著它的負(fù)法線方向（2，-1）T移動，由于可行域D無界，因此，移動可以無限制下去，而目標(biāo)函數(shù)值一直減小，所以該線性規(guī)劃問題無有限最優(yōu)解，即該問題無界。

二、唯一最優(yōu)解

例2 求解線性規(guī)劃。

min z=x1-x2

s.t.2x

-x

≥-2

x

-2x

≤2

x

+x

≤5

x

≥0，x

≥0

解：可行區(qū)域如圖2所示。在區(qū)域0A1A2A3A40的內(nèi)部及邊界上的每一個點都是可行點，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動，函數(shù)值會減小，當(dāng)移動到點A2=（1，4）T時，再繼續(xù)移動就離開區(qū)域D了。于是點A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

可以看出，點0、A1、A2、A3、A4都是該線性規(guī)劃問題可行域的頂點。

三、無窮多最優(yōu)解

例3 如果將例2中的目標(biāo)函數(shù)改為minz=4x1-2x2，可行區(qū)域不變，用圖解法求解的過程如圖3所示。

由于目標(biāo)函數(shù)z=4x1-2x2的等值線與直線A1A2平行，當(dāng)目標(biāo)函數(shù)的等值線與直線A1A2重合（此時z=-4）時，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個點均為該問題的最優(yōu)解。特別地，線段A1A2的兩個端點，即可行區(qū)域D的兩個頂點A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時，最優(yōu)解不唯一。

從圖解法的幾何直觀容易得到下面幾個重要結(jié)論：

1.線性規(guī)劃的可行區(qū)域是若干個半平面的交集，它形成了一個多面凸集（也可能是空集）。

2.對于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域的某個頂點上達(dá)到。在這種情況下還包含兩種情況：有唯一解和有無窮多解。若有兩個最優(yōu)解，則其連線上的點都是最優(yōu)解。

3.如果可行域無界，線性規(guī)劃問題的目標(biāo)函數(shù)可能有無界的情況。

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語數(shù)外學(xué)習(xí)，2013，（8）.

[2]兌松杰.構(gòu)造向量巧解線性規(guī)劃問題[J].中學(xué)數(shù)學(xué)高中版，2012，（7）.

[3]孫殿武.別樣的線性規(guī)劃問題更精彩[J].河北理科教學(xué)研究，2012，（2）.

[4]張香云.線性規(guī)劃[M].浙江：浙江大學(xué)出版社，2013.endprint

摘要：線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一，也是運(yùn)籌學(xué)的最基本的方法之一。它是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。最近十多年來，線性規(guī)劃無論是在深度還是在廣度方面又都取得了重大進(jìn)展。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。

關(guān)鍵詞：圖解法；可行域；最優(yōu)解

中圖分類號：G642.4 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2014）39-0100-02

線性規(guī)劃問題研究的是在一組線性約束條件下一個線性函數(shù)最優(yōu)問題。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。簡單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時還可利用目標(biāo)函數(shù)與可行區(qū)域的關(guān)系利用圖解法求解該問題。圖解法的步驟為：（1）畫出直角坐標(biāo)系；（2）依次做每條約束線，標(biāo)出可行域的方向，并找出它們共同的可行域；（3）任取一目標(biāo)函數(shù)值作一條目標(biāo)函數(shù)線（稱等值線），根據(jù)目標(biāo)函數(shù)（最大或最?。╊愋?，平移該直線即將離開可行域上，則與目標(biāo)函數(shù)線接觸的最終點即表示最優(yōu)解。

一、無界

例1 用圖解法解線性規(guī)劃。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：該問題的可行區(qū)域如圖1所示。

目標(biāo)函數(shù)z=-2x1+x2沿著它的負(fù)法線方向（2，-1）T移動，由于可行域D無界，因此，移動可以無限制下去，而目標(biāo)函數(shù)值一直減小，所以該線性規(guī)劃問題無有限最優(yōu)解，即該問題無界。

二、唯一最優(yōu)解

例2 求解線性規(guī)劃。

min z=x1-x2

s.t.2x

-x

≥-2

x

-2x

≤2

x

+x

≤5

x

≥0，x

≥0

解：可行區(qū)域如圖2所示。在區(qū)域0A1A2A3A40的內(nèi)部及邊界上的每一個點都是可行點，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動，函數(shù)值會減小，當(dāng)移動到點A2=（1，4）T時，再繼續(xù)移動就離開區(qū)域D了。于是點A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

可以看出，點0、A1、A2、A3、A4都是該線性規(guī)劃問題可行域的頂點。

三、無窮多最優(yōu)解

例3 如果將例2中的目標(biāo)函數(shù)改為minz=4x1-2x2，可行區(qū)域不變，用圖解法求解的過程如圖3所示。

由于目標(biāo)函數(shù)z=4x1-2x2的等值線與直線A1A2平行，當(dāng)目標(biāo)函數(shù)的等值線與直線A1A2重合（此時z=-4）時，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個點均為該問題的最優(yōu)解。特別地，線段A1A2的兩個端點，即可行區(qū)域D的兩個頂點A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時，最優(yōu)解不唯一。

從圖解法的幾何直觀容易得到下面幾個重要結(jié)論：

1.線性規(guī)劃的可行區(qū)域是若干個半平面的交集，它形成了一個多面凸集（也可能是空集）。

2.對于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域的某個頂點上達(dá)到。在這種情況下還包含兩種情況：有唯一解和有無窮多解。若有兩個最優(yōu)解，則其連線上的點都是最優(yōu)解。

3.如果可行域無界，線性規(guī)劃問題的目標(biāo)函數(shù)可能有無界的情況。

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語數(shù)外學(xué)習(xí)，2013，（8）.

[2]兌松杰.構(gòu)造向量巧解線性規(guī)劃問題[J].中學(xué)數(shù)學(xué)高中版，2012，（7）.

[3]孫殿武.別樣的線性規(guī)劃問題更精彩[J].河北理科教學(xué)研究，2012，（2）.

[4]張香云.線性規(guī)劃[M].浙江：浙江大學(xué)出版社，2013.endprint

摘要：線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一，也是運(yùn)籌學(xué)的最基本的方法之一。它是解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。最近十多年來，線性規(guī)劃無論是在深度還是在廣度方面又都取得了重大進(jìn)展。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。

關(guān)鍵詞：圖解法；可行域；最優(yōu)解

中圖分類號：G642.4 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2014）39-0100-02

線性規(guī)劃問題研究的是在一組線性約束條件下一個線性函數(shù)最優(yōu)問題。簡單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個變量的線性規(guī)劃。本文主要介紹簡單線性規(guī)劃問題求解的幾種可能情況及解簡單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對解簡單線性規(guī)劃問題的圖解法作一些探討。簡單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時還可利用目標(biāo)函數(shù)與可行區(qū)域的關(guān)系利用圖解法求解該問題。圖解法的步驟為：（1）畫出直角坐標(biāo)系；（2）依次做每條約束線，標(biāo)出可行域的方向，并找出它們共同的可行域；（3）任取一目標(biāo)函數(shù)值作一條目標(biāo)函數(shù)線（稱等值線），根據(jù)目標(biāo)函數(shù)（最大或最?。╊愋停揭圃撝本€即將離開可行域上，則與目標(biāo)函數(shù)線接觸的最終點即表示最優(yōu)解。

一、無界

例1 用圖解法解線性規(guī)劃。

min z=-2x1+x2

s.t.x

+x

≥1

x

-3x

≥-3

x

≥0，x

≥0

解：該問題的可行區(qū)域如圖1所示。

目標(biāo)函數(shù)z=-2x1+x2沿著它的負(fù)法線方向（2，-1）T移動，由于可行域D無界，因此，移動可以無限制下去，而目標(biāo)函數(shù)值一直減小，所以該線性規(guī)劃問題無有限最優(yōu)解，即該問題無界。

二、唯一最優(yōu)解

例2 求解線性規(guī)劃。

min z=x1-x2

s.t.2x

-x

≥-2

x

-2x

≤2

x

+x

≤5

x

≥0，x

≥0

解：可行區(qū)域如圖2所示。在區(qū)域0A1A2A3A40的內(nèi)部及邊界上的每一個點都是可行點，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動，函數(shù)值會減小，當(dāng)移動到點A2=（1，4）T時，再繼續(xù)移動就離開區(qū)域D了。于是點A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

可以看出，點0、A1、A2、A3、A4都是該線性規(guī)劃問題可行域的頂點。

三、無窮多最優(yōu)解

例3 如果將例2中的目標(biāo)函數(shù)改為minz=4x1-2x2，可行區(qū)域不變，用圖解法求解的過程如圖3所示。

由于目標(biāo)函數(shù)z=4x1-2x2的等值線與直線A1A2平行，當(dāng)目標(biāo)函數(shù)的等值線與直線A1A2重合（此時z=-4）時，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個點均為該問題的最優(yōu)解。特別地，線段A1A2的兩個端點，即可行區(qū)域D的兩個頂點A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時，最優(yōu)解不唯一。

從圖解法的幾何直觀容易得到下面幾個重要結(jié)論：

1.線性規(guī)劃的可行區(qū)域是若干個半平面的交集，它形成了一個多面凸集（也可能是空集）。

2.對于給定的線性規(guī)劃問題，如果它有最優(yōu)解，最優(yōu)解總可以在可行域的某個頂點上達(dá)到。在這種情況下還包含兩種情況：有唯一解和有無窮多解。若有兩個最優(yōu)解，則其連線上的點都是最優(yōu)解。

3.如果可行域無界，線性規(guī)劃問題的目標(biāo)函數(shù)可能有無界的情況。

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語數(shù)外學(xué)習(xí)，2013，（8）.

[2]兌松杰.構(gòu)造向量巧解線性規(guī)劃問題[J].中學(xué)數(shù)學(xué)高中版，2012，（7）.

[3]孫殿武.別樣的線性規(guī)劃問題更精彩[J].河北理科教學(xué)研究，2012，（2）.

[4]張香云.線性規(guī)劃[M].浙江：浙江大學(xué)出版社，2013.endprint