【正文】 FF* 則稱 F*為像集 F(R)的 弱有效點(diǎn) ，弱有效點(diǎn)的全體記為 Ewp*. 多目標(biāo)規(guī)劃解的性質(zhì) ?類似地可證明：像集 F(R)的有效點(diǎn)一定是弱有效點(diǎn)，即 ?通過在像集 F(R)上尋找有效點(diǎn)（或弱有效點(diǎn)），就可以確定約束集合 R上的有效解（或弱有效解）。 ?但是，當(dāng)目標(biāo)函數(shù) f1(X), f2(X),…,f p(X)為線性函數(shù)，約束集合 R為凸多面體時(shí)，可以證明：像集 F(R)為 EP中的凸多面體。 多目標(biāo)規(guī)劃解的性質(zhì) ? 2. 多目標(biāo)規(guī)劃問題的像集 在（ VP）中，取定一可行解 X0∈ R，可得到其相應(yīng)的目標(biāo)函數(shù)值 F(X0)=( f1(X0), …, f p(X0))T 此為 EP空間中的一個(gè)點(diǎn)，從而確定了從 X到F(X)的一個(gè)映射，即 F X—— →F(X) 集合 F(R)={F(X) |X∈ R}稱為約束集合 R在映射 F之下的像集。 *1*jpjab RR ??? 多目標(biāo)規(guī)劃解的性質(zhì) 多目標(biāo)規(guī)劃解的性質(zhì) ?定義 4 如果 f1(X), f2(X),…,f p(X)和 g1(X), g2(X),…,g m(X)均為凸函數(shù)，則稱多目標(biāo)數(shù)學(xué)規(guī)劃（ VP）為 凸多目標(biāo)數(shù)學(xué)規(guī)劃 。弱有效解的全體記為Rwp* 多目標(biāo)規(guī)劃解的性質(zhì) 記 Rj*為單目標(biāo)問題 (Pj) min fj(X) . gi(X)≤0, i=1,2,…,m 的最優(yōu)解集合， j=1,2,…,p ，可見 而 R， Rab*， Rpa*， Rwp*， R1*,…, R p*之間的關(guān)系有下列圖示。最優(yōu)解的全體記為 Rab* 多目標(biāo)規(guī)劃解的概念 對(duì)于無絕對(duì)最優(yōu)解的情況，引進(jìn)下面的偏好關(guān)系 ： 設(shè) F1=(f11, f21, …,f p1)T, F2=(f12, f22, …,f p2)T (1)F1F2意味著 F1每個(gè)分量都嚴(yán)格小于 F2的相應(yīng)分量，即 fj1fj2, j=1,2,…,p (2)F1≤F2等價(jià)于 fj1≤fj2, j=1,2,…,p ，且至少存在某個(gè) j0 (1≤j0≤p), 使 fj01fj02 (3)F1≦ F2等價(jià)于 fj1≤fj2, j=1,2,…,p 多目標(biāo)規(guī)劃解的概念 ? 定義 2 設(shè) X*∈ R，若不存在 X∈ R滿足F(X)≤F(X*), 則稱 X*為問題 (VP)的 有效解（ 或 Pareto解 ）。這時(shí)稱 BC上的點(diǎn)為非劣解 ，或 有效解 。因此需要根據(jù)別的原則，權(quán)衡兩者之間的得失，從 R中找出滿意的方案來。 由此可得共同的最優(yōu)解 X*并不存在。問：是否能找到一個(gè)可行解 X*=(x1*, x2*)T使之同時(shí)為 f1(X)與 f2(X)的最大解？ ? 在可行域內(nèi)容易求解 max f1(X)的唯一最優(yōu)解為 (100, 300), 見圖中 B點(diǎn)。 第二個(gè)目標(biāo)的最優(yōu)解 x(2)=1, 為同一點(diǎn)，取 x*=1作為多目標(biāo)問題的最優(yōu)解，其目標(biāo)函數(shù)值 F*(x) =(2,1). 可以用變量空間和目標(biāo)函數(shù)空間來分別描述各種解的情況。 167。 ?????????????????????mixxaxaxcxxxfxaxxxfiixiimiiimiiimmiiimi,...,2,1,0)1(,),...,(,),...,(01112121211且要滿足下列約束條件取最大而最小問題即求個(gè)項(xiàng)目不投資若對(duì)第個(gè)項(xiàng)目投資若決定對(duì)第設(shè) 多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式 ?Vmin F(X)=(f1(X), f2(X),…,f p(X))T . gi(X)≤0, i=1,2,…,m 其中 X=(x1,x2,…,x n)T, p≥2 這里 Vmin 是指對(duì)向量形式的 p個(gè)目標(biāo) (f1(X), f2(X),…,f p(X))T求最小。 生產(chǎn)計(jì)劃問題 ? [問題分析 ] 設(shè)每日生產(chǎn)甲、乙的數(shù)量分別為 x1, x2, 令 X=(x1, x2), 則其目標(biāo)函數(shù)為利潤(rùn) f1(X)=4x1 + 3x2 甲的產(chǎn)量 f2(X)=x1 都取最大值 滿足約束條件 x1 + x2≤400（原料供應(yīng)約束） 2x1 + x2≤500（加工時(shí)間約束） x1≥0， x2≥0 多目標(biāo)規(guī)劃問題舉例 ?例 2投資問題 ?假設(shè)在一段時(shí)間內(nèi)有 a（億元）的資金可用于建廠投資，若可供選擇的項(xiàng)目記為 1,2,…,m, 而且一旦對(duì)第 i個(gè)項(xiàng)目投資，則必須用掉 ai（億元） 。 1多目標(biāo)規(guī)劃問題舉例 ? 例 1生產(chǎn)計(jì)劃問題 某工廠計(jì)劃生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)每件甲的利潤(rùn)為 4元，生產(chǎn)每件乙的利潤(rùn)為 3元，每件甲的加工時(shí)間為每件乙的兩倍，若全部時(shí)間用來加工乙，則每日可生產(chǎn)乙 500件，但工廠每日供給的原料只夠生產(chǎn)甲和乙的總數(shù)共 400件，產(chǎn)品甲是緊俏商品，預(yù)測(cè)市場(chǎng)日需求量為 300件。至今多目標(biāo)規(guī)劃已廣泛應(yīng)用于經(jīng)濟(jì)、管理、系統(tǒng)工程等科技的各個(gè)領(lǐng)域。這類問題即為多目標(biāo)數(shù)學(xué)規(guī)劃問題。第五章 多目標(biāo)規(guī)劃 ? 在實(shí)際問題中，衡量一個(gè)設(shè)計(jì)方案的好壞往往不止一個(gè)。例如：設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程遠(yuǎn)，命中率高，還要耗燃料少；又如：選擇新廠址，除了要考慮運(yùn)費(fèi)、造價(jià)、燃料供應(yīng)費(fèi)等經(jīng)濟(jì)指標(biāo)外，還要考慮對(duì)環(huán)境的污染等社會(huì)因素。 第五章 多目標(biāo)規(guī)劃 ?早在 1772年， Franklin就提出了多目標(biāo)問題矛盾如何協(xié)調(diào)的問題， 1896年，Pareto首次從數(shù)學(xué)角度提出了多目標(biāo)最優(yōu)決策問題，直到二十世紀(jì) 5070年代 Charnes, Karlin, Zadeh等人先后做了許多較有影響的工作，多目標(biāo)規(guī)劃受到人們的關(guān)注。 167。決策者希望制定一個(gè)日生產(chǎn)方案，不僅能得到最大的利潤(rùn)，且能最大地滿足市場(chǎng)需求。 而在這段時(shí)間內(nèi)這第個(gè)項(xiàng)目可得到的收益為 ci（億元） , 其中 i=1,2,…,m, 問如何確定最佳的投資方案？ 投資問題 ? [問題分析 ] ? 上述要求的最佳方案應(yīng)為：投資少，收益大。 ?一般假設(shè)多目標(biāo)規(guī)劃中的目標(biāo)函數(shù)已經(jīng)是規(guī)范化了的。 2 多目標(biāo)規(guī)劃解的概念與性質(zhì) ? 1. 多目標(biāo)規(guī)劃解的概念 ? 例 3 ? [解 ]分別對(duì)單個(gè)目標(biāo)求出其最優(yōu)解，對(duì)于第一個(gè)目標(biāo)的最優(yōu)解 x(1)=1。 RxxFVRxxxxxfxxxf???????????????)(min],2,0[213210)(,42)( 221求設(shè) 多目標(biāo)規(guī)劃解的概念 ? 下面考察例 1中生產(chǎn)計(jì)劃問題。 max f2(X)的唯一最優(yōu)解為 (250, 0), 見圖中 C點(diǎn)。當(dāng)一目標(biāo)達(dá)到最優(yōu)時(shí)，另一目標(biāo)達(dá)不到最優(yōu)，兩目標(biāo)相互矛盾。 多目標(biāo)規(guī)劃解的概念 如何比較方案的好壞呢？ 就上述問題，設(shè) X∈ R， Y∈ R，稱 X比 Y好（或 Y比 X劣），若 f1(X)f1(Y) f2(X) ≥f2(Y) 或 f1(X)≥f1(Y) f2(X) f2(Y) 不難得到除線段 BC之外的其余 R上的點(diǎn)均為劣解，而 BC上無劣解，且兩兩無法比較，因此決策者只有根據(jù)某些別的考慮從 BC上挑選出滿意的方案來。 多目標(biāo)規(guī)劃解的概念 對(duì)于一般的多目標(biāo)規(guī)劃問題： (VP) Vmin F(X)=(f1(X), f2(X),…,f p(X))T . gi(X)≤0, i=1,2,…,m 其中 X=(x1,x2,…,x n)T, p≥2 設(shè) R={X| gi(X)≤0, i=1,2,…,m} 定義 1 設(shè) X*∈ R，若對(duì)任意 j=1,2,…,p, 以及任意X∈ R均有 fj(X)≥fj(X*), j=1,2,…,p 則稱 X*為問題 (VP)的 絕對(duì)最優(yōu)解 。有效解的全體記為 Rpa* ? 定義 3 設(shè) X*∈ R，若不存在 X∈ R滿足F(X)F(X*), 則稱 X*為問題 (VP)的 弱有效解（ 或弱 Pareto解 ）。并有下列定理。 ?一般來說，即使（ VP）為凸多目標(biāo)數(shù)學(xué)規(guī)劃， Rwp*和 Rpa*也不一定為凸集。 多目標(biāo)規(guī)劃解的性質(zhì) ?一般來說，即使（ VP）是凸多目標(biāo)規(guī)劃，像集 F(R)也不一定為凸集（見例 3）。 多目標(biāo)規(guī)劃解的性質(zhì) 對(duì)于像集 F(R)，還可以定義有效點(diǎn)及弱有效點(diǎn)。對(duì)此，有如下的定理。 }),(|{** RXXFFXRpaEFpa ??? ?? }),(|{** RXXFFXRwpEFwp ??? ?? 167。 2中，注意到，要使多目標(biāo)規(guī)劃（ VP）中所有子目標(biāo)同時(shí)實(shí)現(xiàn)最優(yōu)經(jīng)常是不可解的，那么如何制定比較標(biāo)準(zhǔn)在（弱）有效解集中找到滿意解呢？ 處理多目標(biāo)規(guī)劃的一些方法 ? 約束法（主要目標(biāo)法） 在目標(biāo)函數(shù) f1(X), f2(X),…,f p(X)中，選出其中的一個(gè)作為主要目標(biāo)，如 f1(X), 而其它的目標(biāo) f2(X),…,f p(X)只要滿足一定的條件即可。不妨設(shè) p個(gè)目標(biāo)責(zé)任制的重要性序列為 f1(X), f2(X),…,f p(X) 首先求第一個(gè)目標(biāo) f1(X)的最優(yōu)解 (P1) min f1(X) X∈ R 設(shè)其最優(yōu)值為 f1*，再求第二個(gè)目標(biāo)的最優(yōu)解 處理多目標(biāo)規(guī)劃的一些方法 ? (P2) min f2(X) X∈ R1 其中 R1=R∩{X |f1(X)≤f1*} 其最優(yōu)值為 f2*，然后求第三個(gè)目標(biāo)的最優(yōu)解 (P3) min f3(X) X∈ R2 其中 R2=R1∩{X |f2(X)≤f2*} 求得最優(yōu)值為 f3*,… ，最后求第 p個(gè)目標(biāo)的最優(yōu)解 (Pp) min fp(X) X∈ R p1 其中 Rp1=Rp2∩{X |fp1(X)≤fp1*} 處理多目標(biāo)規(guī)劃的一些方法 ?此時(shí)求得最優(yōu)解 X*，最優(yōu)值為 fp*，則X*就是多目標(biāo)問題 (VP)在分層序列意義下的最優(yōu)解。 ?定理 6 設(shè) X*是由分層序列法所得到的最優(yōu)解，則 X*∈ Rpa*. 處理多目標(biāo)規(guī)劃的一些方法 ? [證明 ]用反證法證明。 X∈ R 處理多目標(biāo)規(guī)劃的一些方法 ? (2)若 fj(Y)= fj(X*), j=1,2,…,j 01 但 fj0(Y)fj0(X*) 2≤j0≤p 此時(shí)必有 fj(Y)= fj(X*)≤fj*, j=1,2,…,j 01 因此， Y是問題 (Pj0) min fp(X) X∈ Rj02∩{X |fj01(X)≤fj01*} 的可行解，又由 fj0(Y)fj0(X*)≤fj0* 此與 fj0*是問題 (Pj0)的最優(yōu)值相矛盾。 處理多目標(biāo)規(guī)劃的一些方法 ? 評(píng)價(jià)函數(shù)法 直接求解多目標(biāo)規(guī)劃問題是比較困難的，有一類方法是通過構(gòu)造一個(gè)評(píng)價(jià)函數(shù)（或效用函數(shù)） U(F(X))將多目標(biāo)規(guī)劃問題 (VP)轉(zhuǎn)化為單目標(biāo)規(guī)劃問題 min U(F(X)) X∈ R 然后求解該問題，并將其最優(yōu)解 X*作為 (VP)的最優(yōu)解。 處理多目標(biāo)規(guī)劃的一些方法 ? 1. 線性加權(quán)和法 ? 對(duì) (VP)中的 p個(gè)目標(biāo) f1(X), f2(X),…,f p(X)按其重要程度給以適當(dāng)?shù)臋?quán)系數(shù) λj≥0(j=1,2,…,p),且 ∑ λj=1，然后構(gòu)造評(píng)價(jià)函數(shù) ? 目標(biāo)函數(shù)是一種和的形式，這里要求所有應(yīng)具有相同量綱，若量綱不同，必須進(jìn)行統(tǒng)一量綱或無量綱化處理。 (1)“老手法” (2)α方法 處理多目標(biāo)規(guī)劃的一些方法 ?2. 平方和加權(quán)法 對(duì)單目標(biāo)規(guī)劃問題 (Pj) min fj(X) j=1,2,…,p X∈ R 求出一個(gè)盡可能好的下界 f10,…,f p0（可看成是規(guī)定值）， min fj(X)≥ fj0