Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu

(cid:221)(cid:216)JL(cid:210)(cid:217) (cid:238)(cid:230) (cid:222)(cid:223)H(cid:215) (cid:204)(cid:209)(cid:223)G(cid:210) O(cid:209)_(cid:215) (cid:210)(cid:217)(cid:223)]¸ ``````````````````````````````

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

CHÖÔNG 2

NH LAÄÄP BAP BAØØI TOA

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU

THATHAØØNH LA ch vaøø yyùù nghnghóóaa

MuMuïïcc ñíñích va

QUY HOAÏÏCHCH BABAØØII TOATOAÙÙNN QUY HOA NGAÃU TUYEÁÁN TN TÍÍNHNH ÑÑOOÁÁII NGAÃU TUYE

n QHTT, babaøøi toa

CH THAØØNH LA

((XemXem))

i toa ùùnn ññooáái ngaãu i toaùùn gon goáácc, ky, ky ùù hiehieääu lau la øø PP ng ta co ùù thetheåå thiethieáát lat la ääp bap ba øøi toai toa ùùn QHTT n QHTT i ngaãu , ky, ky ùù hiehieääu lau la øø DD (Dual), (Dual), thu y ta coùù thetheåå thu

((XemXem))

QUY HOAÏÏCHCH I TOAÙÙNN QUY HOA NH LAÄÄP BAP BAØØI TOA 1.1. CACAÙÙCH THA Ths. Nguyeãn Coâng Trííí Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr NGAÃU TUYEÁÁN TN TÍÍNH NH ÑÑOOÁÁII NGAÃU TUYE 2.2. CACAÙÙCC ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

VôVôùùi bai ba øøi toai toa ùùn QHTT, (Primal), chu ùùng ta co (Primal), chu khakhaùùc,c, babaøøi toa sao cho t öøöø lôlôøøi giai giaûûi cui cuûûa baa baøøi toai toaùùn nan naøøy ta co sao cho t thathaääpp ñöñöôôïïc thoâng tin ve n kia. c thoâng tin veàà lôlôøøi giai giaûûi cui cuûûa baa baøøi toai toaùùn kia. thoâng tin ca ààn thie ÑÑeeåå cocoùù thoâng tin ca n thie áát vet ve àà babaøøi toai toa ùùn gon go áác, coc, co ùù

(Xem) (Xem)

3.3. THUA

THUAÄÄT GIA

thetheåå nghieân c i ngaãu cuûûa noa noùù.. nghieân cöùöùu treân ba u treân baøøi toai toaùùnn ññooáái ngaãu cu

THUYEÁÁTT ÑÑOOÁÁII

NG DUÏÏNG CU

Hôn nööõa, khi phaân t Hôn n õa, khi phaân t íích ch ññooààng thô i ngaãu, chu ùùng ta co

4.4. MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU NGAÃU TRONG BAØØI TOA NGAÃU TRONG BA

Copyright 2001 Copyright 2001 Copyright 2001 I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU T GIAÛÛII ÑÑÔN HÌNH NG CUÛÛA LYA LYÙÙ THUYE N QHTT I TOAÙÙN QHTT

(Xem) (Xem) Ths. Nguyeãn Coâng Tr ííí Ths. Nguyeãn Coâng Tr Ths. Nguyeãn Coâng Tr

hai ba øøii ng thô øøi cai ca ûû hai ba t ra ng ta co ùù thetheåå ruruùùt ra c laãn ve àà trò ve àà mamaëët toat toa ùùn hon ho ïïc laãn ve

(Xem) (Xem)

5.5. BABAØØI TAI TAÄÄPP

Copyright 2001 Copyright 2001 Copyright 2001

toatoaùùn gon go áác vac va øø ññooáái ngaãu, chu cacaùùc kec ke áát luat lua ään con co ùù giagiaùù trò ve a kinh teáá.. mamaëët yt yùù nghnghóóa kinh te

THATHAØØNH LA

NH LAÄÄP BAP BAØØI TOA

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU ng chíính tanh taéécc

NH LAÄÄP BAP BAØØI TOA n QHTT (P) d ööôôùùi dai daïïng ch

i g(y) laøø hahaøøm mum muïïc tieâu cu n (II), ta co ùù c tieâu cuûûa baa baøøi toai toaùùn (II), ta co

THATHAØØNH LA XeXeùùt bat baøøi toai toaùùn QHTT (P) d t

()min

Pfxc x

Ax 0.

x + ytt(b (b Ax)}, vô Ax)}, vôùùi x i x 0.0. x + ytt(b (b Ax), vô Ax), vôùùi x GoGoïïi g(y) la g(y) = min{c ttx + y g(y) = min{c ccttx + y i x 0.0.

mm

P.A cuûûa baa baøøi toai toaùùn (I) th Ax = 0 vaøø n (I) thìì bb Ax = 0 va u x laøø P.A cu NeNeááu x la ,... , b, bmm))

x ,... , x, xnn))

i x = (x11, x, x22,... y g(y) la øø momoäät cat ca ään dn dööôôùùi bai ba áát kyt ky øø cucuûûaa n (P) co ùù P.A.T.U la

nn, b = (b , b = (b11, b, b22,... P.A.T.U la øø xxoptopt vavaøø gogoïïi xi x00 lalaøø

x y R

0 m .

g(y) ccttx. Va x. Va ääy g(y) la g(y) c tieâu. hahaøøm mum muïïc tieâu. VôVôùùi x = (x GiaGiaûû ssöûöû babaøøi toai toa ùùn (P) co momoäät P.A cu GoGoïïii x = (x n (P), ta coùù ccttxxoptopt ccttxx00.. 0 sao cho i x 0 sao cho t P.A cuûûa baa baøøi toai toaùùn (P), ta co nn, vô, vôùùi x ,... , x, xnn)) x = (x 11, x, x22,... Ta tììm cam caään dn dööôôùùi lôi lôùùn nha Ta t n nhaáát Max{g(y)}, tha t Max{g(y)}, tha äät vat vaääyy AxAx bb 00 Ax)}, vôùùi x i x 0.0. Ax}, vôùùi x i x 0.0. BaBaøøi toai toaùùn tn tööôngông ñöñöông: ông: t (,)min LxycxybAx A)x}, vôùùi x i x 0.0. A)x}, vôùùi x x + ytt(b (b Ax)}, vô x + yttbb yyttAx}, vô b + (c tt yyttA)x}, vô b + min{ (c tt yyttA)x}, vô g(y) = min{c ttx + y g(y) = min{c = min{cttx + y = min{c = min{yttb + (c = min{y = y= yttb + min{ (c i x 0.0.

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU

NH LAÄÄP BAP BAØØI TOA

THATHAØØNH LA

I TOAÙÙNN ÑÑOOÁÁI NGAÃU I NGAÃU t t 0 0c

t yA x

khiy A khiy A c

fxxx

XeXeùùtt i ngaãu cuûûa baa baøøi toai toaùùn QHTT sau n QHTT sau ññaâyaây VVíí duduïï 2.1.2.1. BaBaøøi toai toaùùnn ññooáái ngaãu cu x ()286min

min c x 0 y ta ñöñöôôïïcc VaVaääy ta

14 xx 13

x 5

x 2313 3

2 xx 2

t gyybgyy b

()max()max

j 01, 5

Dfyyy

i ngaãu coùù dadaïïngng g(y) = yttbb g(y) = y Suy ra baøøi toai toaùùnn ññooáái ngaãu co Suy ra ba

ttt cyAyA c m yRy R .

lalaøø babaøøi toai toaùùnn

N g u y eãn C oân g Trí

()4413max y 12 y 1

gyy b

()max

y 1

2 3

2 0 0 8

y 3 y 3 y 3

y 2

y 1

t Ay c m y R

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

Hay baøøi toai toaùùn tn tööôngông ñöñöôngông Hay ba

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

NH LAÄÄP BAP BAØØI TOA

THATHAØØNH LA

NH LAÄÄP BAP BAØØI TOA

THATHAØØNH LA BaBaøøii toatoaùùnn gogoáácc (P)(P)

I TOAÙÙNN ÑÑOOÁÁI NGAÃU I NGAÃU BaBaøøii toatoaùùnn ññooááii ngaãu

ngaãu (D)(D)

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU ngaãu vavaøø chchææ rara cacaùùcc

fxxxx

x ()22min 123

y ()34max 12 32

VVíí duduïï 2.2.2.2. VieVieáátt babaøøii toatoaùùnn ññooááii ngaãu cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu ngaãu cucuûûaa babaøøii toatoaùùnn QHTTQHTT HaHaøømm mumuïïcc tieâutieâu fxc x ()min Pj j HaHaøømm mumuïïcc tieâutieâu fyb y ()max Di i

j 1 RaRaøøngng buobuoääcc ththöùöù ii

i ng buoääc thc thöùöù jj

xxx 123 xx 3 12 xxx 23 123

x 4 x 3 x 4

y 3 y 3 y 3

,1,

n j

aycj iji

axbi ijj

RaRaøøng buo

j 01, 2

y 3 0

y 1

y 2

i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu Dfyyy yy 12 yy 12 yy 12 y 1

0,1,

j 0,1,

iyi

khoâng raøng buoäc

AAÅÅnn ththöùöù jj AAÅÅn thn thöùöù ii 1 xyy 112 xyy 212 CaCaùùc cac caëëpp ññooáái ngaãu i ngaãu 0,321 y 3 y 3 2 221,0 y 1 4 3 y 2 0,32 xxxx 1234 33,0 xxx 123

VD2.2 VD2.2

VD2.3 VD2.3

VD2.7 VD2.7

VD2.6 VD2.6

VD2.5 VD2.5

VD2.4 VD2.4

THATHAØØNH LA

NH LAÄÄP BAP BAØØI TOA

THATHAØØNH LA

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU ngaãu vavaøø chchææ rara cacaùùcc

f xxx

fxxx

x ()28max 12

()281015min

1 012

x 1 x x

2 1

xx 74228 12 xx 3310 12 xx 2315 12

x 3 x 3 x 3

Dfyyy yy 732 12 yy 43 12 yy 23 12

j 01, 2

ngaãu cucuûûaa babaøøii toatoaùùnn QHTTQHTT VVíí duduïï 2.4.2.4. VieVieáátt babaøøii toatoaùùnn ññooááii ngaãu cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu VVíí duduïï 2.3.2.3. VieVieáátt babaøøii toatoaùùnn ññooááii ngaãu cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu ngaãu cucuûûaa babaøøii toatoaùùnn QHTTQHTT ()438min x 12 i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu

y 3 y 3 y 3 0,

0,4

y 3

y 1

x 1

2 2

i ngaãu ng buoääcc ññooáái ngaãu CaCaùùc rac raøøng buo

01, 3 x BaBaøøi toai toaùùnn ññooáái ngaãu i ngaãu y ()25max 1 10

x 2 xy 31

y 1

2,0

0,3 y 0,28 2 xx 13

y 1 25,0

xx 23

y 5 2

0;1, 2 j

2 xyy 112 xyy 212 3 4 y 1 y 3 i ngaãu CaCaùùc cac caëëpp ññooáái ngaãu 1 0,7322 y 3 0,431 y 3 74228,0 xxx 123 2315,0 xxx 123

NH LAÄÄP BAP BAØØI TOA

THATHAØØNH LA

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

CACAÙÙCC ÑÑÒNH LY

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU ngaãu vavaøø chchææ rara cacaùùcc

yyy

()438min

y 12

x 1 x

y y

4 3 8

01 12

2 5

1 0

ngaãu cucuûûaa babaøøii toatoaùùnn QHTTQHTT i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu i ngaãu nhau co ùù trò P.A.T.ÖÖ vavaøø giagiaùù trò t trong hai ba øøi toai toa ùùnn ññooáái ngaãu nhau co n kia cuõng co ùù P.A.T. ng nhau. ng baèèng nhau. a chu ùùng ba ÑÑÒNHÒNH LYLYÙÙ 1.1. NeNeááu mou mo äät trong hai ba P.A.T.ÖÖ ththìì babaøøi toai toa ùùn kia cuõng co P.A.T. hahaøøm mum muïïc tieâu cu c tieâu cuûûa chu HEHEÄÄ QUAQUAÛÛ 1.1. VVíí duduïï 2.5.2.5. VieVieáátt babaøøii toatoaùùnn ññooááii ngaãu cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu ()25max x f xx 1 10 01 12

01, 3

cho ca ùùc bac ba øøi toai toa ùùnn ññooááii moãi ba øøi toai toa ùùnn

0;1, 2 j i ngaãu ng buoääcc ññooáái ngaãu 1

0,2

y 3

N g u y eãn C oân g Trí

ÑÑieieààu kieu kie ään can ca ààn van va øø ññuuûû ññeeåå cho ca ông aùùn ton to ááii ööu lau la øø moãi ba ngaãu nhau co ùù phphööông a ngaãu nhau co t nhaáát mo ông aùùn.n. t moäät pht phööông a cocoùù íít nha HEHEÄÄ QUAQUAÛÛ 2.2.

x RaRaøøng buo xy 11 xy 22

4,0

0,25 y 3 x 1

y 1

3,0

x 2 28,0

xx 12

5 y 3

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

cho ca ùùc bac ba øøi toai toa ùùnn ññooááii P.A.T.ÖÖ lalaøø momoäät bat ba øøi toai toa ùùn con co ùù ÑÑieieààu kieu kie ään can ca ààn van va øø ññuuûû ññeeåå cho ca ngaãu nhau khoâng co ùù P.A.T. ngaãu nhau khoâng co P.A coøøn ban baøøi toai toaùùn kia khoâng co P.A co n kia khoâng co ùù P.A.P.A.

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

CACAÙÙCC ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

CACAÙÙCC ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU CH BUØØ YEYEÁÁU)U)

ÑÑÒNH LY ÒNH LYÙÙ 2.(2.(ÑÑÒNH LY ÒNH LYÙÙ ÑÑOOÄÄ LELEÄÄCH BU CH BUØØ MAMAÏÏNH)NH) ÒNH LYÙÙ 3.(3.(ÑÑÒNH LY ÒNH LYÙÙ ÑÑOOÄÄ LELEÄÄCH BU

lalaøø P.A.T.ÖÖ.. trong ca ëëp rap ra øøng buo trong ca ngaãu nhau ông aùùnn sao cho nhau cocoùù P.A.T. sao cho trong ca

optopt), Y), Yoptopt == optopt, ..., x optopt, x, x22 , ..., x nn optopt) la) la ààn ln lööôôïït lat la øø P.A.T. P.A.T.ÖÖ. cu. cu ûûa baa ba øøii

, ..., y mm

optopt, y, y22

, ..., y mm

optopt, y, y22

opt

ÑÑÒNH LY P.A.T.ÖÖ.. ththìì NeNeááuu cacaëëpp babaøøii toatoaùùnn ññooááii ngaãu trong ca ùùcc totoààn tan ta ïïi moi mo äät cat ca ëëp php ph ööông a cacaëëpp ññooáái ngaãu, ne i ngaãu, ne ááuu raraøøngng buobuoääcc nanaøøyy xaxaûûyy rara vôvôùùii dadaááuu ññaaúúngng ththöùöùcc ththìì raraøøngng buobuoääcc kiakia xaxaûûyy rara vôvôùùii dadaááuu babaáátt c ngaëët.t. ññaaúúngng ththöùöùc nga NghNghóóa laa la øø, vô, vô ùùi Xi Xoptopt = (x= (x 11 optopt, ..., y (y(y11 i ngaãu, ta coùù toatoaùùn gon goáác vac vaøø babaøøi toai toaùùnn ññooáái ngaãu, ta co m ngaãu ÑÑieieààuu kiekieäänn cacaàànn vavaøø ññuuûû ññeeåå cacaëëpp babaøøii toatoaùùnn ññooááii ngaãu ng buo ääcc ññooááii nhau cocoùù P.A.T. nhau ngaãu, ne ááuu raraøøngng buobuoääcc nanaøøyy xaxaûûyy rara vôvôùùii dadaááuu babaáátt ngaãu, ne ññaaúúngng ththöùöùcc ngangaëëtt ((>> hoahoaëëcc <<) th) thìì raraøøngng buobuoääcc kiakia xaxaûûyy rara vôvôùùii dadaááuu ññaaúúngng ththöùöùcc.. optopt), Y), Y optopt == optopt, ..., x optopt, x, x22 , ..., x nn NghNghóóa laa la øø, vô, vô ùùi Xi Xoptopt = (x= (x 11 optopt) la) la ààn ln lööôôïït lat la øø P.A.T. optopt, ..., y P.A.T.ÖÖ. cu. cu ûûa baa ba øøii (y(y11 i ngaãu, ta coùù toatoaùùn gon goáác vac vaøø babaøøi toai toaùùnn ññooáái ngaãu, ta co m c j ay iji = 0 th ìì totoààn tan taïïii c j ay iji NeNeááu xu xjj NeNeááu xu xjj

optopt > 0 th > 0 thìì , n

optopt = 0 th n

opt

optopt

b i

ax ijj

b i

ax ijj

NeNeááuu 0 (> hoaëëc <).c <). 0 (> hoa

optopt = 0= 0

NeNeááuu ththìì totoààn tan taïïi yi yii ththìì yyii

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY VVíí duduïï 2.6.2.6. ChoCho babaøøii toatoaùùnn QHTTQHTT f xxx

x ()438min 12

x 1

101

012

2 x 3

j 0,1,3

(1)(1) (2)(2) ((3)3)

xx11 = 0 (= 0 (ññònh ly o hpt cuûûa baa baøøi toai toaùùn gon goáácc = 0 vaøøo hpt cu

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY CaCaùùcc cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu ngaãu 00 vavaøø yy11 xx11 44 00 vavaøø yy22 xx22 33 00 vavaøø yy11 + 2y+ 2y22 xx33 88 Thay yoptopt = (2, 3) va ng buoääcc = (2, 3) vaøøo cao caùùc rac raøøng buo Thay y TTöøöø (1): y ònh lyùù 2).2). = 2 < 4 (1): y11 = 2 < 4 Thay x 11 = 0 va Thay x

1 01

0 12

ngaãu lalaøø yyopt opt == ((2, 32, 3)) treân. P.A.T.ÖÖ cucuûûaa babaøøii toatoaùùnn treân. cocoùù P.A.T. vavaøø f(yf(yoptopt) = 19 i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu P.A.T.ÖÖ cucuûûaa babaøøii toatoaùùnn ññooááii ngaãu ) = 19.. HaõyHaõy ttììmm P.A.T. y yy ()25max 1 1; 2 x 2 x 3 2 5 x 3 x 2 3 x 2 y 1 10 01 4 3 = (0,1,2) va øø y, P.A.T. ÖÖ cucuûûa baa ba øøi toai toa ùùn gon go áác lac la øø xxoptopt= (0,1,2) va y 12 8

x 2 x 3 VaVaääy, P.A.T. ) = 19. f(xf(xoptopt)) = f= fDD(y(yoptopt) = 19.

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY VVíí duduïï 2.7.2.7. ChoCho babaøøii toatoaùùnn QHTTQHTT

f xxxx

x 4 x 4

x 4

x ()224max 123 xxx 5650 123 xx 3216 13 xx 4323 13

) = 54.. HaõyHaõy (1)(1) (2)(2) (3)(3) (4)(4) ((5)5) (6)(6)

j 01, 4 P.A.T.ÖÖ lalaøø xxopt opt = (= (0,14, 6, 5) 0,14, 6, 5) vavaøø f(xf(xoptopt) = 54 ngaãu. P.A.T.ÖÖ cucuûûaa babaøøii toatoaùùnn ññooááii ngaãu.

00 00 ng buoääcc yy11 = 2.= 2. CoCoùù P.A.T. ttììmm P.A.T. i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu y ()501623mi n

12

3

N g u y eãn C oân g Trí

y 2 3

Dfyyy yy 534 12

y

2 y

1

3

yy11 + y+ y22 + 3y+ 3y33 = 1= 1 6y6y11 + 2y+ 2y22 + y+ y33 = 4 = 4 ông tr ìình treân, ta co nh treân, ta co ùù yy11 = 2; y = 2; y 22 == --23/5; 23/5; i ngaãu laøø y, P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùnn ññooáái ngaãu la

y

4

62 1 yy 12 yy 12

= 6/5. Vaääy, P.A.T. = (2, --23/5, 6/5) va

y

3 0;

0 AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY CaCaùùcc cacaëëpp raraøøngng buobuoääcc ññooááii ngaãu ngaãu 00 vavaøø 5y5y11 3y3y22 + 4y+ 4y33 22 xx11 xx22 22 00 vavaøø yy11 11 00 vavaøø yy11 + y+ y22 + 3y+ 3y33 xx33 44 xx44 00 vavaøø 6y6y11 + 2y+ 2y22 + y+ y33 --3x3x11 + x+ x33 + 2x+ 2x44 1616 vavaøø yy22 + 3x+ 3x33 + x+ x44 4x4x11 23 23 vavaøø yy33 Thay x optopt = (0, 14, 6, 5) va = (0, 14, 6, 5) va øøo cao caùùc rac raøøng buo Thay x = 14 > 0 (2): x22 = 14 > 0 TTöøöø (2): x (3): x33= 6 > 0 TTöøöø (3): x = 6 > 0 TTöøöø (4): x = 5 > 0 (4): x44= 5 > 0 GiaGiaûûi hei heää phphööông tr yy33 = 6/5. Va yyoptopt= (2,

23/5, 6/5) vaøø ffDD(y(yoptopt)) = 54. = 54.

2

3

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

m tra tr öïöïc tiec tie ááp, ta tha

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY VVíí duduïï 2.8.2.8. ChoCho babaøøii toatoaùùnn QHTTQHTT () fxxxxMax 12

x 4

x 2

xx 12 x 1 xx 13

x 4

01, 4 j

y 3

y X, Y, va øø T laT la øø P.A cu a maõn ca ùùc rac ra øøng buo P.A cu ûûaa ng buo ääcc p, ta tha ááy X, Y, va Z khoâng tho ûûa maõn ca P.A cuûûa baa baøøi toai toaùùn.n.

y 3

1.1. KieKieååm tra tr babaøøi toai toa ùùn. Vn. Vìì Z khoâng tho neân Z khoâng la øø P.A cu neân Z khoâng la 2.2. BaBaøøi toai toaùùnn ññooáái ngaãu i ngaãu y yyy Df ()532min 12 yy 12 y 1

y 1 0;0;

y 3

yy 12

P.A hay khoâng? c vectô coùù phaphaûûi lai laøø P.A hay khoâng?

i ngaãu ng buoääcc ññooáái ngaãu Ta coùù 7 ca7 caëëp rap raøøng buo Ta co XeXeùùt cat caùùc vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), c vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), T = (1, 2, 1, 2). Vectô na øøo lao la øø 4, 2, 0, 10) va øø T = (1, 2, 1, 2). Vectô na Z = ( --4, 2, 0, 10) va Z = ( P.A.T.ÖÖ. cu. cuûûa baa baøøi toai toaùùn?n? P.A.T. CaCaùùch gia ch gia ûûi.i. m tra caùùc vectô co 1.1. KieKieååm tra ca 2.2. VieVieáát bat baøøi toai toaùùnn ññooáái ngaãu, i ngaãu, m tra caùùc P.A co 3.3. KieKieååm tra ca c P.A coùù phaphaûûi lai laøø P.A.T. P.A.T.ÖÖ.?.?

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

(0, 2, 1) thothoûûaa cacaùùcc vectô XX**== (0, 2, 1) DeãDeã dadaøøngng kiekieååmm tratra vectô ngaãu. raraøøngng buobuoääcc cucuûûaa babaøøii toatoaùùnn ññooááii ngaãu. xx11 xx22 xx33 xx44 yy33 + y+ y33 0 va0 vaøø yy11 + y+ y22 3y3y33 0 va0 vaøø 3y3y11 + y+ y22 0 va0 vaøø 0 va0 vaøø yy11 )= 8 neânneân XX lalaøø P.A.T. P.A.T.ÖÖ.. cucuûûaa õa, ffDD((XX**)=)= f(f(XX)= 8 xx44 Hôn nööõa, Hôn n babaøøii toatoaùùnn gogoáác.c. xx11 + 3x+ 3x22 xx11 + x+ x22 Y = (2, 1, 8, 0) lalaøø P.A P.A cucuûûaa babaøøii toatoaùùnn gogoáácc vavaøø DoDo Y = (2, 1, 8, 0)

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU (1)(1) (2)(2) (3)(3) (4)(4) (5)(5) (6)(6) (7)(7)

00 00 00 + x+ x33 --11 22 11 00 5 va5 vaøø yy11 3 va3 vaøø yy22 2 va2 vaøø yy33 )= 8 neânneân YY cuõngcuõng lalaøø P.A.T. f(X) == f(Yf(Y)= 8 f(X) P.A.T.ÖÖ.. + x+ x44 --3x3x11 3.3. KieKieååm tra X, Y, T la P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùn.n. f(T)= 4 i T = (1, 2, 1, 2), ta co ùù f(T)= 4 VôVôùùi T = (1, 2, 1, 2), ta co ffmaxmax = 8= 8 P.A.T.ÖÖ. ma. maøø T chT ch ææ lalaøø phphööôngông y T khoâng pha ûûi lai la øø P.A.T. yy11 + y+ y22 3y3y33 == --11 yy33 = 1= 1 VaVaääy T khoâng pha aaùùn cun cuûûa baa baøøi toai toaùùn.n. yy11 = 0= 0 m tra X, Y, T la øø P.A.T. P.A.T.ÖÖ GiaGiaûû ssöûöû X = (3, 0, 11, 0) la X = (3, 0, 11, 0) la øø P.A.T. (1): x 11 = 3 > 0 = 3 > 0 TTöøöø (1): x =11 > 0 (3): x 33=11 > 0 TTöøöø (3): x TTöøöø (5): 3 + 0 + 0 + 0 = 3 < 5 (5): 3 + 0 + 0 + 0 = 3 < 5 GiaGiaûûi hei heää phphööông tr nh, ta ñöñöôôïïc Xc X**= (0, 2, 1). = (0, 2, 1). ông trìình, ta

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY 2.9. GiaGiaûûii babaøøii toatoaùùnn QHTTQHTT

()10 f xxx

819min x 12 2 11

x 1

VVíí duduïï 2.9. ng ca ùùch ch 00 toatoaùùnn veveàà dadaïïngng chchíínhnh tataééc bac ba èèng ca 0, y0, y66

302 125

2 5

2 x 3

01,3 j

ÑöÑöaa babaøøii 0, y0, y55 theâmtheâm 33 aaåånn phuphuïï yy44 y yyy ()625max 12

x j i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu

()625max y yyy 12

D 2 3110 1 02 12519

y 4 y 5 y 6

y 1 y 2 y 3

N g u y eãn C oân g Trí

D 23110

y 1

j 01,6

1 02

1 2519

01,3 j

n cuõng co ùù dadaïïng chua ng chuaåån.n. Ta thaááy bay baøøi toai toaùùn cuõng co Ta tha SSöûöû duduïïng thua ng thuaäät giat giaûûii ññôn hôn hììnhnh

VVíí duduïï 2.102.10

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

4y 3

5y 1 2 2

3 3

HEHEÄÄ P.AP.A AAÅÅNN HEHEÄÄ P.AP.A AAÅÅNN

0 6y 0 0 1

3 1 7

SOSOÁÁ 6 5 0 SOSOÁÁ 0 0 0

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY 6 500 2 2y 1y 3y 2 0 1 1 1 0 0 5 0

C.BC.B 1y 4 3y 2 6y 50 f x 34

6y 0 0 1 0 GHI CHUÙÙ GHI CHU

2 2y 3 0 2 2 3

5 3y 1 2 5 5 1

0 4y 1 0 0 00 1

2 3

2 1

P.A.T.ÖÖ yyoptopt=(4, 0, 2) va )= 34. =(4, 0, 2) va øø f(yf(yoptopt)= 34.

6 0 0

x 1 x

x 14 x

opt

x opt

2 3

0 0 1 0

BaBaøøi toai toaùùn con coùù P.A.T. P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùn gon goáác lac laøø P.A.T. b

6 1y 2 1 1 6 1 0 0 0

0 5y 0 1 0 0 0 1 0 0

2 2

2 7

3 00 0

x 36

2 x 3

C.BC.B 4y 10 5y 8 6y 19 f x 0 1y 5 5y 3 6y 14 f x 30

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY

ch 2: duduøøng ng ññònh ly

I NGAÃU ÒNH LYÙÙ ÑÑOOÁÁI NGAÃU ng ta cuõng co ùù thetheåå ssöûöû duduïïng quy ta

ònh lyùù ññooáái ngaãu i ngaãu 1010

AAÙÙP DUP DUÏÏNGNG ÑÑÒNH LY GHI CHU ÙÙ.. ChuChuùùng ta cuõng co GHI CHU sausau ññaâyaây ññeeåå ttììm P.A.T.

y 11

opt

ng quy ta éécc m P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùnn ññooáái ngaãu: i ngaãu: c + 2y+ 2y33

88 1919 00 00 00 n cô baûûn xn xjj (j = 1, 2, ... (1)(1) (2)(2) (3)(3) (4)(4) (5)(5) ((6)6) = (4,0,2) i ngaãu y optopt= (4,0,2)

y (j = 1, 2, ... , m) trong P.A.C.B , m) trong P.A.C.B ông p m t ööông

u tieân la ääp thap tha øønh ma tra ôn vò ca ááp m t nh ma tra äänn ññôn vò ca ng cuoáái cui cuøøng.ng. trong ba ûûng cuo n cô ba ûûnn ññaaààu tieân cu u tieân cu ûûa baa ba øøi toai toaùùnn P.A.T.ÖÖ cucuûûa baa ba øøi toai toa ùùnn i ngaãu la øø yy44, y, y55 vavaøø yy66 ththìì P.A.T. i ngaãu) la øø i ngaãu cuûûa baa baøøi toai toaùùnn ññooáái ngaãu) la yy11 yy11 + 2y+ 2y22 + 5y+ 5y33 66 vavaøø yy11 22 vavaøø yy22 55 vavaøø yy33 P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùnn ññooáái ngaãu y xx33 = 0.= 0. 2x2x11 + x+ x22 + x+ x33 = 6= 6 xx11 + 2x+ 2x22 + 5x+ 5x33 = 5= 5 PA.T.ÖÖ cucuûûa baa ba øøi toai toa ùùnn ông tr ìình, ta co nh, ta co ùù PA.T. ) = 34. = (7/3, 4/3, 0) va øø f(xf(xoptopt) = 34. CaCaùùch 2: 00 vavaøø 2y2y11 + 3y+ 3y22 + y+ y33 xx11 00 vavaøø xx22 xx33 00 vavaøø 2x2x11 + x+ x22 + x+ x33 + 2x+ 2x33 3x3x11 xx11 + 2x+ 2x22+ 5x+ 5x33 Ta coùù P.A.T. Ta co (3): 4 +4 +22 0 + 0 + 55 2 = 14 < 19 TTöøöø (3): 2 = 14 < 19 4 > 0 (4): yy11 == 4 > 0 TTöøöø (4): 2 > 0 (6): yy33== 2 > 0 TTöøöø (6): GiaGiaûûi hei he ää phphööông tr gogoáác lac laøø xxoptopt = (7/3, 4/3, 0) va ) = 34. = (7/3, 4/3, 0) va øø f(Xf(Xoptopt) = 34. VôVôùùi cai caùùc ac aåån cô ba ññaaààu tieân la öùöùng vô ng vôùùi cai caùùcc jj trong ba Trong VVíí duduïï 2.92.9, a, aåån cô ba Trong ññooáái ngaãu la gogoáác (c (ññooáái ngaãu cu XXoptopt = (7/3, 4/3, 0) va

I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU

I NGAÃU T GIAÛÛII ÑÑÔN ÔN HÌNHHÌNH ÑÑOOÁÁI NGAÃU

THUATHUAÄÄT GIA

THUAÄÄT GIAT GIAÛÛII ÑÑÔN HÌNH THUA Do Lemke G.E ññeeàà xuaxuaáát naêm 1954. Do Lemke G.E

LALAÄÄP BAP BAÛÛNGNG ÑÑÔNÔN HÌNH I NGAÃU HÌNH ÑÑOOÁÁI NGAÃU

ÑÑuuùùngng

t naêm 1954. ÑÑaây laaây la øø thuathuaäätt ng va øøo bao ba øøi toai toa ùùnn ññooááii cho baøøi toai toaùùn gon goáác.c. giagiaûûii ññôn hôn hììnhnh ñöñöôôïïc ac aùùp dup du ïïng va m P.A.T.ÖÖ cho ba ngaãu nhööngng ññeeåå ttììm P.A.T. ngaãu nh

0,0,

jj??

ii??

bbii

jj

P.A.T.ÖÖ P.A.T. ThuaThuaäät giat gia ûûii ññôn hôn hìình nh ññooáái ngaãu xua i ngaãu xua áát pha

SaiSai

ÑÑuuùùngng

ng buo ääc chc ch íính cu

0,0,

i?i?

aaijij

KEKEÁÁT THUT THUÙÙCC THUAÄÄTT GIAGIAÛÛII THUA THUAÄÄTT GIAGIAÛÛII THUA ÔN HÌNH ÑÑÔN HÌNH u (x 0), ngh

ÒNH PHÖÖÔNG A

I TOAÙÙNN

SaiSai ÔNG AÙÙN MÔN MÔÙÙII x

XAXAÙÙCC ÑÑÒNH PH ra : AAåånn ra :

BABAØØI TOA KHOÂNG COCOÙÙ P.A.T. KHOÂNG

P.A.T.ÖÖ

Minb 0i b

N g u y eãn C oân g Trí

t pha ùùt tt töøöø momoäätt nh cu ûûaa ông aùùn gian gia ûû thothoûûa caa ca ùùc rac ra øøng buo ööng khoâng ng khoâng n (nghie äämm ññuuùùng Ax = b) nh ng Ax = b) nh 0), nghóóa laa laøø ng buoääc vec veàà dadaááu (x ông u tieân khoâng co ùù phaphaààn tn töûöû ddööông i) nh ööng lang la ïïi coi co ùù

AAåånn vavaøøo :o :

Min 0ij a

phphööông a babaøøi toai toa ùùn (nghie thoathoaûû ññieieààu kieu kieään ran raøøng buo babaûûngng ññôn hôn hìình nh ññaaààu tieân khoâng co c tieâu (do øøng cuo ng mu ïïc tieâu (do ng cuo áái) nh trong do øøng mu trong do ông aùùn.n. aâm trong co äät pht phööông a phaphaààn tn töûöû aâm trong co

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

ThuaThuaäät giat gia ûûi nai na øøy thy th ööôôøøngng ñöñöôôïïc ac aùùp dup du ïïng khi ch ng khi ch ööaa t P.A.C.B na øøo cuo cu ûûa baa ba øøi toai toa ùùn gon go áác nhc nh ööng lang la ïïi coi co ùù ÔN HÌNH BIEBIEÁÁNN ÑÑOOÅÅI BAI BAÛÛNGNG ÑÑÔN HÌNH SOSOÁÁ BBÖÖÔÔÙÙC LAC LAËËPP ÕU HAÏÏNN LALAØØ HHÖÖÕU HA biebieáát P.A.C.B na sasaüün mon moäät P.A.C.B cu i ngaãu. t P.A.C.B cu ûûa baa baøøi toai toaùùnn ññooáái ngaãu.

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

THUATHUAÄÄT GIA

I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU

THUATHUAÄÄT GIA

T GIAÛÛII ÑÑÔN HÌNH

I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU

T GIAÛÛII ÑÑÔN HÌNH 2.10. GiaGiaûûi bai ba øøi toai toa ùùn QHTT trong

3 x 4

n QHTT trong VVíí duduïï 2.9 2.9 P.AP.A i ngaãu. ng thuaäät giat giaûûii ññôn hôn hìình nh ññooáái ngaãu. HeHeää sosoáá AAÅÅnn C.BC.B 00 66 1010 xx11 22 88 xx22 11 1919 xx33 11 00 xx44 11 00 xx55 00 00 xx66 00 1) cho ca ùùc rac ra øøng buo ng ch íính tanh ta ééc, roc, ro àài sau ng buo ääcc ññaaúúng th i sau ññooùù c, ta co ùù ng th öùöùc, ta co 00 22 33 00 22 00 11 00 ng chíính tanh taééc nhc nhöö sausau VVíí duduïï 2.10. babaèèng thua ÑöÑöa baa ba øøi toai toa ùùn ven ve àà dadaïïng ch nhaân (1) cho ca nhaân ( babaøøi toai toaùùn dan daïïng ch ()10819min fxxx 00 11 00 00 11 55 55 22 2 6 00 00 00 00 88 1010 1919 2 x 5 00 33 00 1010 ½½ ½½½½11 5 25 x 6 x 12 xxx 123 xx 32 13 xxx 123 00 00 77 00 11 ½½ 3/23/2 3/2 3/2 x j 0,1, 6 11 00 00 00 22 ½½ 9/29/2 3/23/2 t pha ùùt tt töøöø phphööông a X = (0,0,0, 6,6,2,2,5). 5). xx44 xx55 xx66 f(x) f(x) xx11 xx55 xx66 f(x) f(x) 00 00 00 33 55 3030 1414 XuaXuaáát pha Ta coùù babaûûngng ññôn hôn hììnhnh ññooáái ngaãu nh Ta co ông aùùn gian gia ûû X = (0,0,0, i ngaãu nhöö sausau

T GIAÛÛII ÑÑÔN HÌNH

I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU

T GIAÛÛII ÑÑÔN HÌNH P.AP.A

HeHeää sosoáá

THUATHUAÄÄT GIA AAÅÅnn C.BC.B

i thua äät giat gia ûûii ññôn hôn hìình nh ññooáái ngaãu, i ngaãu, , ta co ùù i ngaãu Y optopt, ta co m P.A.T. ÖÖ cucuûûa baa ba øøi toai toa ùùnn ññooáái ngaãu Y y 11

THUAÄÄT GIA THUA GHI CHU ÙÙ.. ÑÑooáái vôi vô ùùi thua GHI CHU ññeeåå ttììm P.A.T. c sau biebieååu thu thöùöùc sau

opt

1010 00 88 1919 xx33 22 44 33 2323 xx11 xx55 xx33 f(x) f(x) 00 xx55 00 11 00 00 88 xx22 00 00 11 00 7/37/3 55 4/34/3 3434 1010 xx11 11 00 00 00 00 xx66 1/31/3 11 2/32/3 22 00 xx44 2/32/3 22 1/31/3 44

y mm n cô ba ûûnn ññaaààu tieân cu

y 14

u tieân cu ûûa baa ba øøii Trong VVíí duduïï 2.102.10, a, aåån cô ba Trong toatoaùùnn ññooáái ngaãu la i ngaãu laøø xx44, x, x55 vavaøø xx66 ththìì

yy opt

(4)0 4 00 0 (2)0 2

25 y 36

y 1 y 2 y 3

VaVaääy, P.A.T. vavaøø y, P.A.T. ÖÖ cucuûûa baa ba øøi toai toa ùùn lan la øø xxoptopt = (7/3, 4/3, 0) = (7/3, 4/3, 0) ) = 34. f(xf(xoptopt) = 34.

= (4, 0, 2) vaøø i ngaãu la øø YYoptopt = (4, 0, 2) va P.A.T.ÖÖ cucuûûa baa baøøi toai toaùùnn ññooáái ngaãu la P.A.T. ff**(Y(Yoptopt) = 34. ) = 34.

I NGAÃU ÔN HÌNH ÑÑOOÁÁI NGAÃU

T GIAÛÛII ÑÑÔN HÌNH

THUAÄÄT GIA THUA

P.AP.A HeHeää sosoáá AAÅÅnn C.BC.B i ngaãu ññeeåå giagiaûûi bai ba øøii ch tuye áán tn tíính sau nh sau ññaâyaây

THUAÄÄT GIAT GIAÛÛII ÑÑÔN HÌNH THUA 2.11. VVíí duduïï 2.11. DuDuøøng thua toatoaùùn quy hoa

()24

5 22

x 5

fxxxxxxMin 1234 xx 12

ng thua äät giat gia ûûii ññôn hôn hìình nh ññooáái ngaãu n quy hoaïïch tuye

xxx 2

34 xx 35

22 11 00 00 0, 0,

N g u y eãn C oân g Trí

x 6 x 7

xxx 235

j 0,1, 7

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

00 22 11 11 22 11 00 00 t phaùùt tt töøöø phphööông a ông aùùn gian giaûû X = (0, 0, 0, X = (0, 0, 0, 6, 6, 2,2, 5)5) Do aDo a4j4j j = 1,..., 7 j = 1,..., 7 neân ba øøii neân ba toatoaùùn treân n treân khoâng co ùù khoâng co P.A.T.ÖÖ.. P.A.T. 22 xx11 11 00 00 00 00 11 00 00 00 00 44 11 11 xx22 xx33 xx44 22 0000 44 1111 002200 11 44 1010 44 44 1717 2424 000022 xx55 xx66 xx77 22 0000 11 0000 11 0011 1100440011 22 55 0000 22 000000 11 000011 11 001100 1100004455 77 000000 55 xx11 xx44 xx66 xx77 f(x) f(x) xx11 xx55 xx66 xx77 f(x) f(x) 22 44 22 66 00 66 44 66 1010 2020 XuaXuaáát pha i ngaãu Ta coùù babaûûngng ññôn hôn hììnhnh ññooáái ngaãu Ta co

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU

NG DUÏÏNG CU I NGAÃU TRONG BA ØØI TOA ÑÑOOÁÁI NGAÃU TRONG BA

NG CUÛÛA LYA LYÙÙ THUYE THUYEÁÁTT N QHTT I TOAÙÙN QHTT

NG DUÏÏNG CU I NGAÃU TRONG BA ØØI TOA ÑÑOOÁÁI NGAÃU TRONG BA

NG CUÛÛA LYA LYÙÙ THUYE THUYEÁÁTT N QHTT I TOAÙÙN QHTT

1.1. TÌM PH

I KHI CO ÙÙ

i ngaãu ññeeåå giagiaûûi bai baøøii 2.12. VVíí duduïï 2.12. ng thua äät giat giaûûii ññôn hôn hììnhnh ññooáái ngaãu a) Duøøng thua a) Du nh sau ññaâyaây ch tuye áán tn tíính sau n quy hoa ïïch tuye

TÌM PH ÖÖÔNG A THEÂM RAØØNG BUO THEÂM RA

ÔNG AÙÙN TON TO ÁÁII ÖÖU MÔU MÔ ÙÙI KHI CO I TOAÙÙNN (XEM) NG BUOÄÄC VAC VAØØO BAO BAØØI TOA (XEM)

2.2. TÌM NGHIE

NH BAÈÈNG THUA

ÛÛA HEA HE ÄÄ NG THUA ÄÄTT

3 x 3 x 23140 3

toatoaùùn quy hoa fxxxxMin ()151210 12 xx 342160 12 xx 12

(XEM) (XEM)

M KHOÂNG AÂM CU TÌM NGHIE ÄÄM KHOÂNG AÂM CU PHPHÖÖÔNG TRÌNH TUYE ÔNG TRÌNH TUYE ÁÁN TN TÍÍNH BA GIAGIAÛÛII ÑÑÔN HÌNH MÔ

ÔN HÌNH MÔ ÛÛ ROROÄÄNGNG

j 0,1, 3

3.3. YYÙÙ NGHNGHÓÓA KINH TE

N QUY I TOA ÙÙN QUY

A KINH TE ÁÁ CUCUÛÛA BAA BA ØØI TOA

b) Neááu theâm mo b) Ne u theâm mo äät rat raøøng buo ng buo ääc nc nööõa xõa x11 + x+ x22 + x+ x33

(XEM) (XEM)

HOAHOAÏÏCH TUYE

I NGAÃU CH TUYEÁÁN TN TÍÍNHNH ÑÑOOÁÁI NGAÃU

n treân, t ììm phm ph ööông a 6060 ông aùùn ton to ááii ööu cuu cu ûûaa vavaøøo bao ba øøi toai toa ùùn treân, t babaøøi toai toaùùn môn môùùi.i.

MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU

NG DUÏÏNG CU I NGAÃU TRONG BA ØØI TOA ÑÑOOÁÁI NGAÃU TRONG BA

THUYEÁÁTT NG CUÛÛA LYA LYÙÙ THUYE N QHTT I TOAÙÙN QHTT

HeHeää SoSoáá

NG DUÏÏNG LY MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU AAÅÅnn P.AP.A C.BC.B

fxxxxMin

1) cho ca ùùc rac ra øøng buo i sau ññooùù c, ta co ùù ng th öùöùc, ta co ng ch íính tanh ta ééc, roc, ro àài sau ng buo ääcc ññaaúúng th 00 00 ÑöÑöa baa ba øøi toai toa ùùn ven ve àà dadaïïng ch nhaân (1) cho ca nhaân ( babaøøi toai toaùùn dan daïïng ch ng chíính tanh taééc nhc nhöö sausau

3 x 4 23140

x 5

()151210 12 xxx 342160 123 xxx 123

j 0,1,5

1212 00

00 xx44 11 00 00 ¼¼ ½½ 33 3/83/8 1212 1010 ông aùùn gian giaûû X = (0, 0, 0, 160, X = (0, 0, 0, 160, t pha ùùt tt töøöø phphööông a

I NGAÃU THUYEÁÁTT ÑÑOOÁÁI NGAÃU 00 xx55 00 11 00 00 11 00 ¼¼ ½½ 22

160160 140140 00 4040 6060 480480 2525 3030 600600 a) Xua áát pha a) Xua i ngaãu 140. Ta coùù babaûûngng ññôn hôn hìình nh ññooáái ngaãu 140. Ta co

NG LYÙÙ THUYE 1515 1212 1010 xx11 xx22 xx33 33 44 22 xx44 xx55 11 22 33 1515 1212 1010 f(x) f(x) xx22 ½½11¾¾ 00½½ 22 xx55 00 66 44 f(x) f(x) 7/87/8 11 00 xx22 ¼¼ 00 ¼¼11 xx33 77 00 22 00 f(x) f(x) ) = 600. = (0, 25, 30) vaøø f(xf(xoptopt) = 600. P.A.T.ÖÖ lalaøø xxoptopt = (0, 25, 30) va P.A.T.

MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU

I NGAÃU THUYEÁÁTT ÑÑOOÁÁI NGAÃU

MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU

NG LYÙÙ THUYE

NG DUÏÏNG LY

NG CUÛÛA LYA LYÙÙ THUYE THUYEÁÁTT N QHTT I TOAÙÙN QHTT P.AP.A AAÅÅnn C.BC.B HeHeää sosoáá khoâng pha ûûi lai la øø phphööông a 00 xx44 3/83/8 1515 xx11 7/87/8 1010 xx33 00 1212 xx22 11 00 xx55 ¼¼ 00 xx66 00 1212 2525 1010 ½½ ¼¼ 3030 ¼¼ 11 00 00 ng th öùöùc bac ba èèng ca ng buo ääc bac ba áátt ññaaúúng th ng ca ùùch theâm a ch theâm a åån phu ng buo ääc xc x11 ông aùùnn c mô ùùi nai na øøy,y, ng buo ääcc 0, ta 0, ta ng buo ääc mô ng th öùöùc vec ve àà raraøøng buo n phu ïï xx66 00 6060 11 11 11 00 11 00 ng ba ûûng cuo 600600 77 22 22 00 00 00 ng buo ääc mô 3/83/8 7/87/8 1212 2525 ¼¼ 00 11 00

N g u y eãn C oân g Trí

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

ng cuo áái cui cu øøng trong caâu a) va c mô ùùii xx11 xx22 xx33 + x+ x66 == 60 va n cô ba ûûn trong ba 1010 3030 ¼¼ 00 11 ¼¼ ½½ 00 n cô baûûn trong ba 00 55 3/83/8 00 00 1/81/8 ¼¼ 11 ng trong caâu a) va øø ñöñöaa 60 vaøøo bao ba ûûngng n trong ba øøi toai toa ùùnn n trong ba øøi toai toaùùn cuõ n cuõ n mô ùùi ta i ta vectô ng 3 ññeeåå vectô ng 2 va øøo doo do øøng 3 600600 77 00 00 22 22 00 xx22 xx33 xx66 f(x) f(x) xx22 xx33 xx66 f(x) f(x) NG DUÏÏNG CU I NGAÃU TRONG BA ØØI TOA ÑÑOOÁÁI NGAÃU TRONG BA = (0, 25, 30) khoâng tho ûûa raa ra øøng buo b) Do x optopt = (0, 25, 30) khoâng tho b) Do x + x+ x22 + x+ x33 60 neân x opt opt khoâng pha 60 neân x n mô ùùi.i. ÑÑeeåå xxöûöû lylyùù raraøøng buo cucuûûa baa ba øøi toai toa ùùn mô ta ñöñöa raa ra øøng buo ta ññaaúúng th ñöñöôôïïcc xx11 xx22 xx33 + x+ x66 == 60. 60. SSöûöû duduïïng ba raraøøng buo treân. Lööu yu yùù aaåån xn x66 lalaøø aaåån cô ba treân. L mômôùùi, coi, coøøn xn x44 vavaøø xx55 lalaøø aaåån cô ba neân trong ma tra ään hen he ää sosoáá cucuûûa baa ba øøi toai toa ùùn mô neân trong ma tra cocoääng do ng do øøng 1 va cocoäätt öùöùng vô ôn vò. c vectô ññôn vò. ng 1 va øø dodoøøng 2 va ng vôùùi xi x44 vavaøø xx55 lalaøø cacaùùc vectô

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

MOMOÄÄT SOT SOÁÁ ÖÙÖÙNG DU

NG DUÏÏNG LY

NG LYÙÙ THUYE

I NGAÃU THUYEÁÁTT ÑÑOOÁÁI NGAÃU

TÌM NGHIEÄÄM KHOÂNG AÂM CU TÌM NGHIE HEHEÄÄ PHPHÖÖÔNG TRÌNH TUYE

M KHOÂNG AÂM CU ÛÛAA ÔNG TRÌNH TUYE ÁÁN TN TÍÍNHNH

P.AP.A HeHeää sosoáá AAÅÅnn C.BC.B

1212 2020 1515 xx11 ½½ 1212 xx22 11 1010 xx33 00 00 xx44 ½½ 00 xx55 00 00 xx66 11

mm cocoùù thetheåå quy ve

min

fxM x

g j

g b

AXX

0,0,

ông tr ìình nh ûûa hea he ää phphööông tr 0 (1), trong ññooùù A laA la øø ma ma 0 (1), trong n quy quy veàà giagiaûûi bai baøøi toai toaùùn quy 1010 4040 ½½ 00 ½½11 00 22 TTììm nghie m khoâng aâm cu m nghie ääm khoâng aâm cu tuyetuyeáán tn tíính AX = b, X nh AX = b, X tratraään mn m n, bn, b hoahoaïïch tuye ch tuye áán tn tíínhnh 00 11 00 44 2020 ½½00 3/2 3/2 44 xx22 xx33 xx55 f(x) f(x) 00 00 00 11 88 640640

g M P.A.T.ÖÖ vvìì (0,b) la (0,b) la øø

0 n (2) luoân luoân co ùù P.A.T.

P.A.T.ÖÖ lalaøø xx// P.A.T. = (0, 20, 40) vaøø f(xf(x// ) = 640. optopt) = 640.

optopt = (0, 20, 40) va

momoäät P.A va c tieâu bò cha ëën [f(x)

P.A.T.ÖÖ cucuûûa baa baøøi toai toa ùùn treân la j thj th ìì xxoptopt lalaøø nghie

XX BaBaøøi toai toa ùùn (2) luoân luoân co t P.A vaøø hahaøøm mum muïïc tieâu bò cha GiaGiaûû ssöûöû P.A.T. optopt = 0, = 0,

n [f(x) 0]. 0]. n treân la øø (x(xoptopt, x, xgg optopt), ), nghie ääm cum cu ûûa baa ba øøi toai toa ùùnn n (1) 0 th0 th ìì babaøøi toai toa ùùn (1) neneááu xu xgg (1). Ng ööôôïïc lac la ïïi nei ne ááu tou to ààn tan ta ïïi xi xgg (1). Ng jj voâ nghieääm.m. voâ nghie

M KHOÂNG AÂM CUÛÛA HEA HEÄÄ PHPHÖÖÔNG TRÌNH TUYE

A KINH TEÁÁ CUCUÛÛA BAA BAØØI TOA

m nghie ääm khoâng aâm cu n khaååu pha

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU u phaààn thn thöùöùc aênc aên

YYÙÙ NGHNGHÓÓA KINH TE XeXeùùt bat baøøi toai toaùùn gon goáác lac laøø babaøøi toai toaùùn kha

7 nh tuyeáán tn tíínhnh ThThöùöùc aênc aên 24 9 jj 22 11 nn ...... ...... ChaChaáát dinh t dinh ôõng (%) ddööôõng (%) x 3 x 3 4 x 3

TÌM NGHIEÄÄM KHOÂNG AÂM CU ÔNG TRÌNH TUYEÁÁN TN TÍÍNHNH TÌM NGHIE VVíí duduïï 2.1.2.1.TTììm nghie m khoâng aâm cu ûûa hea he ää phphööông ông 23 xx trtrìình tuye 12 xx 12 32 xx 12 quy baøøi toai toaùùn treân ve

6 x 4 24

x 5

45 xxx 123 xxx 123 xxx 123

x 6

j 0,1, 6

n QHTT n treân ve àà babaøøi toai toaùùn QHTT Ta coùù thetheåå quy ba Ta co fxMxxxMin ( )

MMöùöùcc dinh dööôõngôõng dinh d i thieååuu totoáái thie bb11 bb22 ...... bbii ...... bbmm c P.A.T. n treân, ta ñöñöôôïïc P.A.T. lalaøø (x(xoptopt, x, xgg ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... aa1111 aa2121 ...... aai1i1 ...... aam1m1 cc11 aa1212 aa2222 ...... aai2i2 ...... aam2m2 cc22 aa1j1j aa2j2j ...... aaijij ...... aamjmj ccjj aa1n1n aa2n2n ...... aainin ...... aamnmn ccnn

optopt)) m khoâng aâm cu ûûa hea he ää

11 22 ...... ii ...... mm GiaGiaùù momoäätt ññôn ôn vò thvò thöùöùc aênc aên y nghie ääm khoâng aâm cu x = (3, 1, 2). nh treân laøø x = (3, 1, 2). nh tuyeáán tn tíính treân la GiaGiaûûi bai ba øøi toai toa ùùn treân, ta = (3, 1, 2, 0, 0, 0). Va ääy nghie = (3, 1, 2, 0, 0, 0). Va phphööông tr ông tr ìình tuye

A KINH TEÁÁ CUCUÛÛA BAA BAØØI TOA

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU

YYÙÙ NGHNGHÓÓA KINH TE

t vieân thuo áác boc bo åå cocoùù chchöùöùaa

A KINH TEÁÁ CUCUÛÛA BAA BAØØI TOA (j = 1, 2, ..., n) la øø sosoáá ññôn vò th a, ta coùù moâ hmoâ hìình ba

I NGAÃU I TOAÙÙNN ÑÑOOÁÁI NGAÃU ôn vò th öùöùc aên trong c aên trong nh baøøi toai toaùùn QHTT nh n QHTT nh öö sausau min

YYÙÙ NGHNGHÓÓA KINH TE GoGoïïi xi xjj (j = 1, 2, ..., n) la moãi bmoãi böûöûa, ta co fxcxcxc x

n n

112 2

lalaøø giagiaùù babaùùn mon mo äät vieân thuo t dinh dööôõng i (i = 1, 2, ..., m). ôõng i (i = 1, 2, ..., m). i chaên nuoâi seõ phaûûi li löïöïa cho GoGoïïi yi yii chachaáát dinh d NgNgööôôøøi chaên nuoâi seõ pha a choïïn:n: ,1, m axaxaxbi 112 2 iiinn +... + a njnjyynn < c< cjj.. ònh ly ùù = 0 ( ññònh ly Mua thuoáác boc boåå, ne, neááu au a1j1jyy11 + a+ a2j2jyy22 +... + a Mua thuo hôn va øø luluùùc nac na øøy xy xjj = 0 ( n 0,1,

max

112

ch bu øø yeyeááu,u, ònh ly ùù ññooää c aên, theo ññònh ly leleääch bu xj j i ngaãu BaBaøøi toai toaùùnn ññooáái ngaãu fybybyb y Dm m > 0 thìì aai1i1xx11 + a+ ai2i2xx22 ++ + a+ aininxxnn = b= bii,,

N g u y eãn C oân g Trí

,1,

n j

ayayaycj 112 jjmjm

m 0,1,

yi i

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

nhu caààu tou toáái thie a chaáát dinh d ôõng thay the áá: nha t thuo áácc y, khi phaân t íích ca t vieân thuo áác boc boåå khakhaùù cao th cao th ìì i chaên nuoâi seõ mua ca ùùc loac loa ïïi thi th öùöùc aên sao c aên sao t dinh dööôõng. ôõng. i thieååu cuu cuûûa cha i ngaãu nhau ch ca ëëp bap ba øøi toai toa ùùnn ññooáái ngaãu nhau n xua áát thuo : nha øø sasaûûn xua ôõng treân. t dinh d ööôõng treân. c chaáát dinh d ChaChaáát dinh d boboåå ttööôngông öùöùng vô t dinh d ööôõng thay the ng vôùùi cai caùùc cha VVìì giagiaùù thuothuoáác boc boåå rereûû hôn va ññooää leleääch bu ch buøø yeyeááu).u). Mua th öùöùc aên, theo Mua th neneááu yu yii > 0 th NghNghóóa laa la øø, ne, neááu giau giaùù momoäät vieân thuo ngngööôôøøi chaên nuoâi seõ mua ca cho thoaûû nhu ca cho thoa VaVaääy, khi phaân t chchíính lanh laøø phaân t nh T.ÖÖ cucuûûa ta töøöøng ba phaân tíích tch tíính T. ng baøøi toai toaùùn.n.

PDF created with pdfFactory Pro trial version www.pdffactory.com

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

`````````````````````````````` BAØI TAÄP CHÖÔNG 2

LAÄP BAØI TOAÙN ÑOÁI NGAÃU

[1] Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa caùc baøi toaùn quy

hoaïch tuyeán tính sau ñaây

f x ( )

x x

min 1

4 2

x 2 x 2 x 2 x 2

x 3 x 3 x 3 x 3 0,

x 1 x 1 x 1 x 1 0,

4 0

x 1

x 3

f x ( )

max

x x

8 9

x 1 x 1 x 1 x 1

2 0,

x 3 x 3 x 3 x 3 0,

x 4 x 4 x 4 x 4 0

x 3

x 2

x 4

[2] Chöùng minh baøi toaùn quy hoaïch tuyeán tính sau ñaây truøng vôùi baøi toaùn ñoái ngaãu cuûa

noù (Baøi toaùn töï ñoái ngaãu).

min

( ) f x

x 1

x 3 x 3 x 3

1 1

x 1 x 1 0,

2 0

x 3

x 1

SÖÛ DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

xf )(

max

[3] Cho baøi toaùn quy hoaïch tuyeán tính x

x 1

4 x

2 x

3 3

4,1

a)Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân.

b)Giaûi baøi toaùn goác, suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu.

2, 0,

1, 0,

, 0

x opt

opt

1 4

3 4

N g u y eãn C oân g Trí

)

Ñs:

f x

opt

11 4

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

[4] Cho baøi toaùn quy hoaïch tuyeán tính

xf )(

min

x 1 2

3 3

x x

12 6

x 1 x 1 x 1 0

2 3,1

x j

a)Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân.

lôøi giaûi cuûa baøi toaùn goác.

b)Giaûi baøi toaùn ñoái ngaãu, suy ra

,0,

3, 0, 3

opt

x opt

3 2

)

: Ñs

f x

opt

[5]

Cho baøi toaùn quy hoaïch tuyeán tính

x 9

min

f xxxxx ( ) 5

x 3

x x

3 x

5 x x

1 4

xx 1 x 1 xx 1

j 02,5

a)Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân.

ngaù ncöï cbieân, suy bieán hay khoâng suy bieán)

b)Phaântíchtínhchaát(phöô cuûa vectô X = (0, 1, 0, 2, 0).

gaùntoá iöucuû abaøitoaù nñoáingaãu.

c)Cho bieát

f(xopt)=5.Tìmphöôn

Ñs

: b) X = (0, 1, 0, 2, 0) khoâng laø P.A.C.B. X laø P.A.T.Ö.

, 2

opty

y 3

)

1 3

1 6

( ) 3

max

f x

x 4

[6] Cho baøi toaùn quy hoaïch tuyeán tính x 3

x 4

0 3 0 6

2 3 2

2 2

x 3 x 3 3 x 3

x 1 x 1 x 1 x 1

x 2 x 2 x 2

x 4

j 01, 4

N g u y eãn C oân g Trí

Cho caùc vectô:

X = (-1, 2, 3, 4); Y = (0,2,1,3); Z = (0, 0, 0, 8), T = (14, 0, 0, 1); S = (18, 2, 0, 0)

Trong caùc vectô treân, vectô naøo laø phöông aùn toái ö

ucuûabaøitoaù n?Haõygiaû ithích.

Ñs

: X, Y k

hoângphaû ilaøphöôngaù n.

T, S laø phöông aùn toái öu.

‚‹‹(cid:176)(cid:230)ææ†‰‹ﬁ•(cid:242)‰–(cid:242)‰‰

PDF created with pdfFactory Pro trial version www.pdffactory.com

``````````````````````````````

(cid:204)‚›(cid:242) (cid:210)„«§»=† (cid:221)–>†„ (cid:204)ﬁ3 ``````````````````````````````

PHÖÔNG PHAÙP ÑÔN HÌNH ÑOÁI NGAÃU

[7]

Duøng phöông phaùp ñôn hình ñoái ngaãu giaûi caùc baøi toaùn quy hoaïch tuyeán tính sau øi giaûi cuûa baøi toaùn goác suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu ñaây vaø töø lô

f x ( )

min

8 9

x 3 x 3 x 3 x 3 0,

x 4 x 4 x 4 x 4 0

x 2 0,

x 1 x 1 x 1 x 1 0,

x 3

x 2

x 4

x 1

0, 4, 5, 0