目標規(guī)劃的圖解法與等值線

宋曉新, 肖運海

(河南大學數(shù)學與信息科學學院,河南開封 475001)

目標規(guī)劃的圖解法與等值線

宋曉新, 肖運海

(河南大學數(shù)學與信息科學學院,河南開封 475001)

運用和發(fā)展了等值線的思想方法,研究目標規(guī)劃中的多目標決策問題的圖解法,提出了運用改進等值線方法研究多目標決策問題的新思路.

改進等值線方法;目標規(guī)劃;多目標決策問題

1 引 言

我校當前正在使用的《運籌學》(第三版)教材的編著者是國內(nèi)最優(yōu)秀的各個領域的專家,此教材經(jīng)過了多次的修改和完善,是一部內(nèi)容深入淺出,文字通俗易懂的高水平教材.但是在多目標規(guī)劃的圖解法這個小問題上,仍然有需要改善的地方.本文作者希望能夠?qū)Υ私滩牡倪M一步完善貢獻自己的一份綿薄之力.本文中將用改進等值線方法來解決這一問題.

目標規(guī)劃方法是解決多目標決策問題的方法之一.一個規(guī)劃問題常常有若干目標.但是決策者在要求達到這些目標時,有主次或輕重緩急的不同.對于各個目標我們賦予不同的優(yōu)先因子.若要區(qū)別具有相同優(yōu)先因子的兩個目標的差別,這時可分別賦予它們不同的權(quán)系數(shù)wj,這些都由決策者按具體情況而定.

2 課本上的例子

下文中我們將給出《運籌學》(第三版)第103頁例3的數(shù)學模型以及課本上的圖解法證明.原題與本文關系不大,故略去.

解 設x1和x2分別表示彩色和黑白電視機的產(chǎn)量.這個問題的目標規(guī)劃模型為

圖1

用圖解法求解,見圖1.從圖中看到,在考慮具有P1,P2的目標實現(xiàn)后,x1,x2的取值范圍為AB CD.考慮P3的要求時,因為d-3的權(quán)系數(shù)大于d-4,故先考慮mind-3,這時x1,x2的取值范圍縮小為AB EF區(qū)域.然后考慮mind-4,最終取E(24,26)為滿意解.由于d-3與d-4是具有相同優(yōu)先因子的兩個目標函數(shù),因而在上述證明中采用的先考慮mind-3,后考慮mind-4的研究路線是值得探討的.

3 改進等值線方法

在第一章中,我們定義具有相同目標函數(shù)值的點的集合構(gòu)成的直線為等值線.用等值線平行移動的方法來尋求最優(yōu)解,是圖解法的基本思想.在本文中,我們將要對這種方法進行改進,推廣等值線的定義,以解決上文中提出的問題.

用圖解法求解,見圖1.從圖中看到,在考慮具有P1,P2的目標實現(xiàn)后,x1,x2的取值范圍為AB CD.下文中從整體上考慮P3的要求,即考慮min(2+).對于E點,我們有我們下面分四個區(qū)域來刻劃的等值線P.區(qū)域甲,0

在這個區(qū)域內(nèi),P代表一個線段,兩個端點分別是X(22,30)和E(24,26).區(qū)域乙,0≤x1≤24,x2≥30.此時,

在這個區(qū)域內(nèi),P代表一條與x2軸平行的射線,端點為X(22,30).區(qū)域丙,x1≥24,0≤x2≤30.此時,

在這個區(qū)域內(nèi),P代表一條與x1軸平行的射線,端點為E(24,26).

區(qū)域丁,x1≥24,x2≥30.此時2+=4無解.在這個區(qū)域內(nèi),沒有滿足條件2+=4的點.

在上文中,我們選擇刻劃經(jīng)過E點的等值線,令人信服地證明了E點為滿意解.實際上,我們可以刻劃經(jīng)過任何一點的等值線,用等值線平行移動的方法得到經(jīng)過任何其它點的等值線,從而尋求滿意解.

4 改進等值線方法的進一步討論

在下文中,我們看到,等值線也可以是閉合折線.考慮如下目標規(guī)劃問題. minz=P1d+P2+P3(5+3)+P3(3+5d),

用圖解法求解,見圖2.從圖中看到,在考慮具有P1,P2的目標實現(xiàn)后,x1,x2的取值范圍為AB CD.下文中從整體上考慮P3的要求,即考慮min(5+3d+3d+5d).對于E點,我們有

圖2

區(qū)域甲,0≤x1≤70,0≤x2≤45.此時,

在這個區(qū)域內(nèi),Q代表一個線段,兩個端點分別是Z(55,45)和E(70,20).

區(qū)域乙,0≤x1≤70,x2≥45.此時,

在這個區(qū)域內(nèi),Q代表一個線段,兩個端點分別是Z(55,45)和Y(70,60).

區(qū)域丙,x1≥70,x2≥45.此時,

在這個區(qū)域內(nèi),Q代表一個線段,兩個端點分別是X(95,45)和Y(70,60).

區(qū)域丁,x1≥70,0≤x2≤45.此時,

在這個區(qū)域內(nèi),Q代表一個線段,兩個端點分別是X(95,45)和E(70,20).

[1] 甘應愛,田豐,等.運籌學[M].3版.北京：清華大學出版社,2005.

[2] 管梅谷,等.線性規(guī)劃[M].濟南：山東科技出版社,1983.

O211.6

C

1672-1454(2011)05-0146-03

2008-12-23; [修日期]2009-04-27