文香丹

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

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

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

線性規(guī)劃問題研究的是在一組線性約束條件下一個(gè)線性函數(shù)最優(yōu)問題。簡(jiǎn)單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個(gè)變量的線性規(guī)劃。本文主要介紹簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況及解簡(jiǎn)單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對(duì)解簡(jiǎn)單線性規(guī)劃問題的圖解法作一些探討。簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡(jiǎn)單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時(shí)還可利用目標(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ù)線接觸的最終點(diǎn)即表示最優(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òng)，由于可行域D無界，因此，移動(dòng)可以無限制下去，而目標(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)部及邊界上的每一個(gè)點(diǎn)都是可行點(diǎn)，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動(dòng)，函數(shù)值會(huì)減小，當(dāng)移動(dòng)到點(diǎn)A2=（1，4）T時(shí)，再繼續(xù)移動(dòng)就離開區(qū)域D了。于是點(diǎn)A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

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

三、無窮多最優(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重合（此時(shí)z=-4）時(shí)，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個(gè)點(diǎn)均為該問題的最優(yōu)解。特別地，線段A1A2的兩個(gè)端點(diǎn)，即可行區(qū)域D的兩個(gè)頂點(diǎn)A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時(shí)，最優(yōu)解不唯一。

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

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

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

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

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語(yǔ)數(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)展。簡(jiǎn)單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個(gè)變量的線性規(guī)劃。本文主要介紹簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況及解簡(jiǎn)單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對(duì)解簡(jiǎn)單線性規(guī)劃問題的圖解法作一些探討。

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

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

線性規(guī)劃問題研究的是在一組線性約束條件下一個(gè)線性函數(shù)最優(yōu)問題。簡(jiǎn)單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個(gè)變量的線性規(guī)劃。本文主要介紹簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況及解簡(jiǎn)單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對(duì)解簡(jiǎn)單線性規(guī)劃問題的圖解法作一些探討。簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡(jiǎn)單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時(shí)還可利用目標(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ù)線接觸的最終點(diǎn)即表示最優(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òng)，由于可行域D無界，因此，移動(dòng)可以無限制下去，而目標(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)部及邊界上的每一個(gè)點(diǎn)都是可行點(diǎn)，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動(dòng)，函數(shù)值會(huì)減小，當(dāng)移動(dòng)到點(diǎn)A2=（1，4）T時(shí)，再繼續(xù)移動(dòng)就離開區(qū)域D了。于是點(diǎn)A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

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

三、無窮多最優(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重合（此時(shí)z=-4）時(shí)，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個(gè)點(diǎn)均為該問題的最優(yōu)解。特別地，線段A1A2的兩個(gè)端點(diǎn)，即可行區(qū)域D的兩個(gè)頂點(diǎn)A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時(shí)，最優(yōu)解不唯一。

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

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

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

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

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語(yǔ)數(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)展。簡(jiǎn)單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個(gè)變量的線性規(guī)劃。本文主要介紹簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況及解簡(jiǎn)單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對(duì)解簡(jiǎn)單線性規(guī)劃問題的圖解法作一些探討。

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

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

線性規(guī)劃問題研究的是在一組線性約束條件下一個(gè)線性函數(shù)最優(yōu)問題。簡(jiǎn)單線性規(guī)劃指的是目標(biāo)函數(shù)含兩個(gè)變量的線性規(guī)劃。本文主要介紹簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況及解簡(jiǎn)單線性規(guī)劃問題的基本方法即圖解法的基本思想和算法步驟，并通過例子對(duì)解簡(jiǎn)單線性規(guī)劃問題的圖解法作一些探討。簡(jiǎn)單線性規(guī)劃問題求解的幾種可能情況：（1）無可行解（可行域是空集）；（2）無界（可行域不空集，但目標(biāo)函數(shù)在可行域上無界）；（3）最優(yōu)解（可行域不空集，且目標(biāo)函數(shù)有有限的最優(yōu)值）。簡(jiǎn)單線性規(guī)劃問題我們可以直觀了解可行區(qū)域的結(jié)構(gòu)，同時(shí)還可利用目標(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ù)線接觸的最終點(diǎn)即表示最優(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òng)，由于可行域D無界，因此，移動(dòng)可以無限制下去，而目標(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)部及邊界上的每一個(gè)點(diǎn)都是可行點(diǎn)，目標(biāo)函數(shù)z=-x1+x2的等直線沿著它的負(fù)梯度方向（1，-1）T移動(dòng)，函數(shù)值會(huì)減小，當(dāng)移動(dòng)到點(diǎn)A2=（1，4）T時(shí)，再繼續(xù)移動(dòng)就離開區(qū)域D了。于是點(diǎn)A2就是最優(yōu)解，而最優(yōu)值為z=1-4=-3。

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

三、無窮多最優(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重合（此時(shí)z=-4）時(shí)，目標(biāo)函數(shù)達(dá)z=4x1-2x2到最小值-4，于是，線段A1A2上的每一個(gè)點(diǎn)均為該問題的最優(yōu)解。特別地，線段A1A2的兩個(gè)端點(diǎn)，即可行區(qū)域D的兩個(gè)頂點(diǎn)A1=（0，2）T，A2=（1，4）T均是該線性規(guī)劃問題的最優(yōu)解。此時(shí)，最優(yōu)解不唯一。

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

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

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

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

參考文獻(xiàn)：

[1]石衛(wèi)東，王媛.例談目標(biāo)函數(shù)新視角[J].語(yǔ)數(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