官术网_书友最值得收藏!

任務二 線性規劃的圖解法

在建立了線性規劃的模型之后,接下來就要求解模型了。在求解線性規劃模型時,最簡單的方法就是圖解法。

當線性規劃問題中變量個數為2時,我們可以在直角坐標系中把變量及其變化方向、范圍等用圖直觀地表示出來,從而求得目標函數的最佳取值,這種方法就是圖解法。在應用中,圖解法相對是比較缺乏實際意義的,但通過這種方法,可以形象地說明線性規劃的許多特征。

接下來,我們用圖解法求解例2-1-1。之前,我們建立出了例2-1-1的模型:

在以x1x2為坐標軸的直角坐標系中,非負條件是指位于第一象限。每一個約束條件都代表一個半平面。我們先將這個規劃的可行域畫出來。約束條件x1+2x2≤8表示以直線x1+2x2=8為邊界(包括邊界)的左下半平面。同理,4x1≤16表示以直線4x1=16為邊界,包括邊界在內的左下半平面,而4x2≤12則表示以直線4x2=12為邊界,包括邊界在內的左下半平面。因此,結合非負約束限定的第一象限,我們可以作出同時滿足所有約束條件的區域,如圖2-2-1所示。在線性規劃中,滿足所有約束條件的解稱為可行解。我們可以看到,在圖2-2-1中,陰影區域中的每一個點(包括邊界點)都是可行解。陰影部分就是同時滿足了4個約束條件的解的集合,我們把這個區域稱為該線性規劃問題的可行域

圖2-2-1

目標函數z=2x1+3x2在這個坐標平面上,它可以表示以z為參數、為斜率的一族平行線:,其中代表斜率,代表截距。現在我們要在這個可行域中求得一個使目標函數達到最大的點,其實也就是說,當目標函數z=0時,作出目標函數的一條直線,在這條直線上,決策變量x1x2的任何取值,對應目標函數z的取值都相等,我們把這條直線叫做等值線。隨著z的增大,直線一直向右平移,當直線平移到剛好要離開陰影部分的臨界點時,再向右平移就與可行域沒有交點了,這時就得到了z的最大化目標值,如圖2-2-2所示。

圖2-2-2

因此,在等值線與陰影區域的臨界交匯點就是滿足約束條件的最優解,該點坐標x1=4,x2=2就是滿足約束條件的最優解,將它們代入目標函數求得z=14,也就是目標函數的最優值。

同理,當平行線向下移動時,當它移動到剛好要離開陰影部分的臨界點時,我們就能得到z的最小值。因此,圖解法既可以求解最大化問題,也可以求解最小化問題。

另外,由圖2-2-2可以看出,線性規劃的最優解出現在可行域的一個頂點上,此時線性規劃問題有唯一解。但有時線性規劃問題還可能出現其他解的情況。接下來通過例題來說明。

(1)如果將例2-1-1中的目標函數改為求maxz=2x1+4x2,這時目標函數的等值線就與邊界線x1+2x2=8平行,所以當等值線向右平移到陰影區域時,臨界點不是一個點,而是一條邊界線,這時,邊界線上的任意一點都是這個線性規劃的最優解,如圖2-2-3所示。這時,線性規劃問題有無窮多個最優解。

圖2-2-3

(2)如果在例2-1-1的基礎上增加約束條件x1x2≥9,那么該問題的可行域是空集,所以,這個問題不存在可行解,當然更不可能存在最優解,如圖2-2-4所示。

圖2-2-4

例2-2-1 用圖解法求解線性規劃。

解:這個線性規劃問題,當我們畫出它的可行域和目標函數時,我們發現,這是個無界集,不管目標函數的等值線怎么向右平移,目標函數和可行域總是有交集,這時目標函數值可以無限增大,也就是說,這個問題有可行解,但沒有最優解,如圖2-2-5所示。

圖2-2-5

所以我們可以看出,線性規劃可能有一個最優解,可能有可行解而無最優解,可能有無窮多最優解,也可能根本就沒有可行解。

主站蜘蛛池模板: 卫辉市| 桃园市| 景泰县| 农安县| 万全县| 科尔| 龙山县| 扶沟县| 枣强县| 张家界市| 鹤岗市| 上思县| 溧水县| 邵武市| 和政县| 修水县| 新宾| 萨迦县| 平阴县| 前郭尔| 柏乡县| 绥芬河市| 汾西县| 宜都市| 双流县| 尼玛县| 和平区| 乌拉特前旗| 黔西县| 特克斯县| 泊头市| 交口县| 大新县| 徐闻县| 永善县| 会同县| 临朐县| 东乌珠穆沁旗| 昌邑市| 沽源县| 乌鲁木齐县|