宋曉新, 肖運(yùn)海

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

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

宋曉新, 肖運(yùn)海

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

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

改進(jìn)等值線方法;目標(biāo)規(guī)劃;多目標(biāo)決策問題

1 引 言

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

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

2 課本上的例子

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

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

圖1

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

3 改進(jìn)等值線方法

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

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

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

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

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

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

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

4 改進(jìn)等值線方法的進(jìn)一步討論

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

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

圖2

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

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

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

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

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

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

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

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

[1] 甘應(yīng)愛,田豐,等.運(yùn)籌學(xué)[M].3版.北京：清華大學(xué)出版社,2005.

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

O211.6

C

1672-1454(2011)05-0146-03

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