目標(biāo)規(guī)劃圖解法63標(biāo)規(guī)劃單純形法課件

第二節(jié)目標(biāo)規(guī)劃問題的圖解法

minZ=d-100X1+80X2-d++d-=100004X1+2X2

4002X1+4X2

500X1,

X2,

d-,

d+0

d+.d-=0例11第二節(jié)目標(biāo)規(guī)劃問題的圖解法minZ=d-100X1+X2X1O50100501001252X1+4X2=5004X1+2X2=400CEB絕對(duì)約束可行域OBEC2X2X1O50100501001252X1+4X2=50X2X1O50100501001252X1+4X2=500100X1+80X2=100004X1+2X2=400CEBd+目標(biāo)約束滿意域BEC3X2X1O50100501001252X1+4X2=50(1)絕對(duì)約束可行域OBEC(2)目標(biāo)約束滿意域BEC(3)多個(gè)可行滿意解：

(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=04(1)絕對(duì)約束可行域OBEC4例2minZ=P1d1++P2(d2-+d2+)+P3(d3-)2X1+X211X1

-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+05例2minZ=P1d1++P2(d2-+d2+)+P3(d3111057X2X1AB2X1+X2=11O可行域⊿OAB6111057X2X1AB2X1+X2=11O可行域⊿OAB111010557X2X1ABCDEFd2+d1-d3+X1+2X2=10X1-X2=08X1+10X2=562X1+X2=11O可行域⊿OAB目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段G7111010557X2X1ABCDEFd2+d1-d3+X1解：①可行域⊿OAB②目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段③用8X1+10X2=56X1+2X2=10求G=(2,4)利潤(rùn)=568解：①可行域⊿OAB②目標(biāo)1：⊿OBC③用

X1-X2=0

X1+2X2=10D=(10/3,10/3)利潤(rùn)=60解為X==

α+(1-α)(0α1)X1210/3

X2410/3④Zmin=09X1-X2=0D=(10/3,1例3minZ=P1d1-+P2d2++P3(2d3-+d4-)X1+X2+d1--d1+=40①

X1

+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④10例3minZ=P1d1-+P2d2++P3(2d3-+d4-X230304050X1OBACDEFd3+d4+d1+d2-X1+X2=40X1+X2=50X2=30X1=24解：G11X230304050X1OBACDEFd3+d4+d1+d2(1)、滿足目標(biāo)①、②的滿意域?yàn)锳BCD(2)、先考慮③的滿意域?yàn)锳BEF再考慮④，無公共滿意域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)12(1)、滿足目標(biāo)①、②的滿意域?yàn)锳BCD(2)、先考慮③的滿(4)、d4-=30-X2+d4+=30-26=4>0因?yàn)閄2+d4--d4+=30所以d4-=30–X2+d4+ZE=P3d4-=P3(30-x2+d4+)=P3(30-26)=4P3而因?yàn)閤1+d3--d3+=24ZG=P3*2d3-=P3*2(24-20)=8P3所以，取E點(diǎn)13(4)、d4-=30-X2+d4+=30-26=4§6.3目標(biāo)規(guī)劃問題的單純形法

目標(biāo)規(guī)劃的數(shù)學(xué)模型，特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)不止是一個(gè)，雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個(gè)函數(shù)的形式，但在計(jì)算中無法按單目標(biāo)處理，所以可用單純形法進(jìn)行適當(dāng)改進(jìn)后求解。在組織、構(gòu)造算法時(shí)，我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1)因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是相反的；一、目標(biāo)規(guī)劃問題單純形法的特點(diǎn)

14§6.3目標(biāo)規(guī)劃問題的單純形法目標(biāo)規(guī)

(2)因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，Pi>>Pi+1，i=1,2,,L-1.于是從每個(gè)檢驗(yàn)數(shù)的整體來看：Pi+1（i=1,2,,L-1）優(yōu)先級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)首先決定于P1

，P2，…，Pi

優(yōu)先級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)。若P1

級(jí)第k個(gè)檢驗(yàn)數(shù)為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于P2級(jí)第k個(gè)檢驗(yàn)數(shù)；若P2

級(jí)第k個(gè)檢驗(yàn)數(shù)仍為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于P3級(jí)第k個(gè)檢驗(yàn)數(shù)，依次類推。換一句話說，當(dāng)某Pi級(jí)第k個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)時(shí)，計(jì)算中不必再考察Pj（j>i）級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)情況；

15(2)因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級(jí)（3）根據(jù)（LGP）模型特征，當(dāng)不含絕對(duì)約束時(shí)，di-（i=1,2,…,K）構(gòu)成了一組基本可行解。在尋找單純形法初始可行點(diǎn)時(shí)，這個(gè)特點(diǎn)是很有用。16（3）根據(jù)（LGP）模型特征，當(dāng)不含絕對(duì)約束時(shí)，di-（i二、目標(biāo)規(guī)劃問題單純形法的計(jì)算步驟(1)建立初始單純形表．在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行解計(jì)算出來，方法同基本單純形法。當(dāng)不含絕對(duì)約束時(shí)，di-（i=1,2,…,K）構(gòu)成了一組基本可行解，即可得到初始單純形表。17二、目標(biāo)規(guī)劃問題單純形法的計(jì)算步驟17(2)確定換入變量：按優(yōu)先級(jí)順序，檢查檢驗(yàn)數(shù)是否存在負(fù)值，選取優(yōu)先級(jí)最高的最小負(fù)值對(duì)應(yīng)的變量入基；(3)按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量；

18(2)確定換入變量：按優(yōu)先級(jí)順序，檢查檢驗(yàn)數(shù)是(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的單純形表；(5)迭代計(jì)算停止判別準(zhǔn)則：如果各優(yōu)先級(jí)的檢驗(yàn)數(shù)均為非負(fù)；某一優(yōu)先級(jí)有負(fù)檢驗(yàn)數(shù)，但是該負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的上一級(jí)優(yōu)先級(jí)的檢驗(yàn)數(shù)為正檢驗(yàn)數(shù)。

19(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的單純?nèi)?、?yīng)用實(shí)例

Min{P1(d1-+d2+),P2d3-}

x1+d1--d1+=102x1+x2+d2--d2+

=403x1+2x2+d3--d3+=100x1,

x2,di-,di+

≥020三、應(yīng)用實(shí)例Min{P1(d例

Min{P1d1-,P2d2+,P3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1,

x2,di-,di+

≥0+x3=6021例Min{P1d1-,P2000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000122000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000123000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000124000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000125000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3120011-100-110x124/51002/5-0.4000.1-0.10d2-36/5000-2/50.41-1-0.60.60x212/5010-0.30.3000.05-0.05σp1000100000p2000000100p300000001026000p100p2p30CBXBbx1x2x3d1-d1+d因有兩個(gè)非基變量的檢驗(yàn)數(shù)為0，所以，有無窮多解。27因有兩個(gè)非基變量的檢驗(yàn)數(shù)為0，所以，有無窮多解。27例試用單純形法來求解Minz=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)x1

+d1--d1+=9x2

+d2--d2+=84x1

+6x2+d3--d3+=6012x1+18x2

+d4--d4+=252x1,x2

,di-,di+0,i=1,2,3,4.

28例試用單純形法來求解28解:

由于P1,P2

優(yōu)先級(jí)對(duì)應(yīng)的目標(biāo)函數(shù)中不含di-,所以其檢驗(yàn)數(shù)只需取系數(shù)。分別為(0，0，0，1，0，1，0，0，0，0)和(0，0，0，0，0，0，0，1，0，0)

29解:29

x1x2d1-d1+d2-d2+d3-d3+d4-d4+bP10001010000

P20000000100

P3-12-1800000001

P4-1-201020000

d1-101-10000009

d2-01001-100008d3-4600001-10060d4-12180000001-125230

x1x2d1-d1+d2-d2+d3-d3+d4-d4+2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+0min{P1d1+

,

P2(d2-+d2+),P3(d3-)}練習(xí)：312X1+X211min{P1d1+,P2(d2-+演講完畢，謝謝觀看！演講完畢，謝謝觀看！第二節(jié)目標(biāo)規(guī)劃問題的圖解法

minZ=d-100X1+80X2-d++d-=100004X1+2X2

4002X1+4X2

500X1,

X2,

d-,

d+0

d+.d-=0例133第二節(jié)目標(biāo)規(guī)劃問題的圖解法minZ=d-100X1+X2X1O50100501001252X1+4X2=5004X1+2X2=400CEB絕對(duì)約束可行域OBEC34X2X1O50100501001252X1+4X2=50X2X1O50100501001252X1+4X2=500100X1+80X2=100004X1+2X2=400CEBd+目標(biāo)約束滿意域BEC35X2X1O50100501001252X1+4X2=50(1)絕對(duì)約束可行域OBEC(2)目標(biāo)約束滿意域BEC(3)多個(gè)可行滿意解：

(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=036(1)絕對(duì)約束可行域OBEC4例2minZ=P1d1++P2(d2-+d2+)+P3(d3-)2X1+X211X1

-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+037例2minZ=P1d1++P2(d2-+d2+)+P3(d3111057X2X1AB2X1+X2=11O可行域⊿OAB38111057X2X1AB2X1+X2=11O可行域⊿OAB111010557X2X1ABCDEFd2+d1-d3+X1+2X2=10X1-X2=08X1+10X2=562X1+X2=11O可行域⊿OAB目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段G39111010557X2X1ABCDEFd2+d1-d3+X1解：①可行域⊿OAB②目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段③用8X1+10X2=56X1+2X2=10求G=(2,4)利潤(rùn)=5640解：①可行域⊿OAB②目標(biāo)1：⊿OBC③用

X1-X2=0

X1+2X2=10D=(10/3,10/3)利潤(rùn)=60解為X==

α+(1-α)(0α1)X1210/3

X2410/3④Zmin=041X1-X2=0D=(10/3,1例3minZ=P1d1-+P2d2++P3(2d3-+d4-)X1+X2+d1--d1+=40①

X1

+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④42例3minZ=P1d1-+P2d2++P3(2d3-+d4-X230304050X1OBACDEFd3+d4+d1+d2-X1+X2=40X1+X2=50X2=30X1=24解：G43X230304050X1OBACDEFd3+d4+d1+d2(1)、滿足目標(biāo)①、②的滿意域?yàn)锳BCD(2)、先考慮③的滿意域?yàn)锳BEF再考慮④，無公共滿意域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)44(1)、滿足目標(biāo)①、②的滿意域?yàn)锳BCD(2)、先考慮③的滿(4)、d4-=30-X2+d4+=30-26=4>0因?yàn)閄2+d4--d4+=30所以d4-=30–X2+d4+ZE=P3d4-=P3(30-x2+d4+)=P3(30-26)=4P3而因?yàn)閤1+d3--d3+=24ZG=P3*2d3-=P3*2(24-20)=8P3所以，取E點(diǎn)45(4)、d4-=30-X2+d4+=30-26=4§6.3目標(biāo)規(guī)劃問題的單純形法

目標(biāo)規(guī)劃的數(shù)學(xué)模型，特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)不止是一個(gè)，雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個(gè)函數(shù)的形式，但在計(jì)算中無法按單目標(biāo)處理，所以可用單純形法進(jìn)行適當(dāng)改進(jìn)后求解。在組織、構(gòu)造算法時(shí)，我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：(1)因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是相反的；一、目標(biāo)規(guī)劃問題單純形法的特點(diǎn)

46§6.3目標(biāo)規(guī)劃問題的單純形法目標(biāo)規(guī)

(2)因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，Pi>>Pi+1，i=1,2,,L-1.于是從每個(gè)檢驗(yàn)數(shù)的整體來看：Pi+1（i=1,2,,L-1）優(yōu)先級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)首先決定于P1

，P2，…，Pi

優(yōu)先級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)。若P1

級(jí)第k個(gè)檢驗(yàn)數(shù)為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于P2級(jí)第k個(gè)檢驗(yàn)數(shù)；若P2

級(jí)第k個(gè)檢驗(yàn)數(shù)仍為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于P3級(jí)第k個(gè)檢驗(yàn)數(shù)，依次類推。換一句話說，當(dāng)某Pi級(jí)第k個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)時(shí)，計(jì)算中不必再考察Pj（j>i）級(jí)第k個(gè)檢驗(yàn)數(shù)的正、負(fù)情況；

47(2)因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級(jí)（3）根據(jù)（LGP）模型特征，當(dāng)不含絕對(duì)約束時(shí)，di-（i=1,2,…,K）構(gòu)成了一組基本可行解。在尋找單純形法初始可行點(diǎn)時(shí)，這個(gè)特點(diǎn)是很有用。48（3）根據(jù)（LGP）模型特征，當(dāng)不含絕對(duì)約束時(shí)，di-（i二、目標(biāo)規(guī)劃問題單純形法的計(jì)算步驟(1)建立初始單純形表．在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行解計(jì)算出來，方法同基本單純形法。當(dāng)不含絕對(duì)約束時(shí)，di-（i=1,2,…,K）構(gòu)成了一組基本可行解，即可得到初始單純形表。49二、目標(biāo)規(guī)劃問題單純形法的計(jì)算步驟17(2)確定換入變量：按優(yōu)先級(jí)順序，檢查檢驗(yàn)數(shù)是否存在負(fù)值，選取優(yōu)先級(jí)最高的最小負(fù)值對(duì)應(yīng)的變量入基；(3)按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量；

50(2)確定換入變量：按優(yōu)先級(jí)順序，檢查檢驗(yàn)數(shù)是(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的單純形表；(5)迭代計(jì)算停止判別準(zhǔn)則：如果各優(yōu)先級(jí)的檢驗(yàn)數(shù)均為非負(fù)；某一優(yōu)先級(jí)有負(fù)檢驗(yàn)數(shù)，但是該負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的上一級(jí)優(yōu)先級(jí)的檢驗(yàn)數(shù)為正檢驗(yàn)數(shù)。

51(4)按單純形法進(jìn)行基變換運(yùn)算，建立新的單純?nèi)?、?yīng)用實(shí)例

Min{P1(d1-+d2+),P2d3-}

x1+d1--d1+=102x1+x2+d2--d2+

=403x1+2x2+d3--d3+=100x1,

x2,di-,di+

≥052三、應(yīng)用實(shí)例Min{P1(d例

Min{P1d1-,P2d2+,P3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1,

x2,di-,di+

≥0+x3=6053例Min{P1d1-,P2000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000154000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000155000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000156000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000157000p100p2p30CBXBbx1x2x3d1-d1+d000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3120011