Bài giảng Quy hoạch tuyến tính Chương 4: ThS. Nguyễn Văn Phong (Chuẩn nhất)

11/5/2011

ÑAÏI HOÏC TAØI CHÍNH –––––––– MARKETING ÑAÏI HOÏC TAØI CHÍNH MARKETING MARKETING MARKETING ÑAÏI HOÏC TAØI CHÍNH ÑAÏI HOÏC TAØI CHÍNH MARKETING MARKETING MARKETING MARKETING ÑAÏI HOÏC TAØI CHÍNH ÑAÏI HOÏC TAØI CHÍNH ÑAÏI HOÏC TAØI CHÍNH ÑAÏI HOÏC TAØI CHÍNH KHOA CÔ BAÛN BOÄ MOÂN TOAÙN –––––––– KHOA CÔ BAÛN KHOA CÔ BAÛN KHOA CÔ BAÛN BOÄ MOÂN TOAÙN BOÄ MOÂN TOAÙN BOÄ MOÂN TOAÙN KHOA CÔ BAÛN KHOA CÔ BAÛN KHOA CÔ BAÛN KHOA CÔ BAÛN BOÄ MOÂN TOAÙN BOÄ MOÂN TOAÙN BOÄ MOÂN TOAÙN BOÄ MOÂN TOAÙN

Baøi giaûng

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

Phong Nguyeãn VaênVaênVaênVaênVaênVaênVaênVaên Phong Phong Phong ThSThSThSThSThSThSThSThS. . . . . . . . Nguyeãn Nguyeãn Nguyeãn Phong Phong Phong Phong Nguyeãn Nguyeãn Nguyeãn Nguyeãn

ChChChChChChChChươươngngngngngngngng 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI 4. BAØI TOAÙN VAÄN TAÛI

Email : nvphong1980@gmail.com, nv.phong@ufm.edu.com

QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH QUY HOAÏCH TUYEÁN TÍNH

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN PHAÙT BIEÅU BAØI TOAÙN

TOAÙN........ PHAÙT BIEÅUBIEÅUBIEÅUBIEÅUBIEÅUBIEÅUBIEÅUBIEÅU BAØIBAØIBAØIBAØIBAØIBAØIBAØIBAØI TOAÙN TOAÙN TOAÙN 1.1.1.1.1.1.1.1. PHAÙT PHAÙT PHAÙT TOAÙN TOAÙN TOAÙN TOAÙN PHAÙT PHAÙT PHAÙT PHAÙT BAÛNG DAÏNG BAÛNG BAÛNG BAÛNG TOAÙN VAÄNVAÄNVAÄNVAÄNVAÄNVAÄNVAÄNVAÄN TAÛITAÛITAÛITAÛITAÛITAÛITAÛITAÛI DAÏNG DAÏNGDAÏNG 2.2.2.2.2.2.2.2. BAØIBAØIBAØIBAØIBAØIBAØIBAØIBAØI TOAÙN TOAÙN TOAÙN BAÛNG BAÛNG BAÛNG BAÛNG DAÏNGDAÏNG DAÏNGDAÏNG TOAÙN TOAÙN TOAÙN TOAÙN KHAÙI NIEÄMNIEÄMNIEÄMNIEÄMNIEÄMNIEÄMNIEÄMNIEÄM 3.3.3.3.3.3.3.3. MOÄTMOÄTMOÄTMOÄTMOÄTMOÄTMOÄTMOÄT SOÁSOÁSOÁSOÁSOÁSOÁSOÁSOÁ KHAÙI KHAÙI KHAÙI KHAÙI KHAÙI KHAÙI KHAÙI CHAÁT 4.4.4.4.4.4.4.4. MOÄTMOÄTMOÄTMOÄTMOÄTMOÄTMOÄTMOÄT SOÁSOÁSOÁSOÁSOÁSOÁSOÁSOÁ TÍNHTÍNHTÍNHTÍNHTÍNHTÍNHTÍNHTÍNH CHAÁT CHAÁT CHAÁT CHAÁT CHAÁT CHAÁT CHAÁT PHAÙT XUAÁT PHAÙT PHAÙT PHAÙT PHÖÔNG AÙNAÙNAÙNAÙNAÙNAÙNAÙNAÙN XUAÁT XUAÁT XUAÁT PHAÙP TÌMTÌMTÌMTÌMTÌMTÌMTÌMTÌM PHÖÔNG PHÖÔNG PHÖÔNG PHÖÔNG PHAÙP PHAÙP PHAÙP 5.5.5.5.5.5.5.5. PHÖÔNG PHÖÔNG PHÖÔNG PHAÙT PHAÙT PHAÙT PHAÙT XUAÁT XUAÁT XUAÁT XUAÁT PHÖÔNG PHÖÔNG PHÖÔNG PHÖÔNG PHAÙP PHAÙP PHAÙP PHAÙP PHÖÔNG PHÖÔNG PHÖÔNG PHÖÔNG THEÁ VÒVÒVÒVÒVÒVÒVÒVÒ TOAÙN THEÁ THEÁTHEÁ THUAÄT TOAÙN TOAÙN TOAÙN 6.6.6.6.6.6.6.6. THUAÄT THUAÄT THUAÄT THEÁTHEÁ THEÁTHEÁ TOAÙN TOAÙN TOAÙN TOAÙN THUAÄT THUAÄT THUAÄT THUAÄT

: cöôùc phí töø

ñeán B

ijc c ij

A i

: löôïng haøng töø A ñeán B

TOAÙN LAÄPLAÄPLAÄPLAÄP BAØIBAØIBAØIBAØI TOAÙN TOAÙN TOAÙN PHAÙT TOAÙN.... PHAÙT BIEÅUBIEÅUBIEÅUBIEÅU BAØIBAØIBAØIBAØI TOAÙN TOAÙN TOAÙN PHAÙT PHAÙT PHAÙT nnnn :::: ÑIEÅMÑIEÅMÑIEÅMÑIEÅM THUTHUTHUTHU mmmm :::: ÑIEÅMÑIEÅMÑIEÅMÑIEÅM PHAÙT PHAÙT PHAÙT

m n

ijx x

Muïc tieâu:

min

∑∑

c x ij

= 1

i =

i m 1 , ,

∑

i j

= 1

)

1 ,

∑

i j

     

= 1

)

∑ ∑ = a

= 1

ﬁ

i III x )

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

‡

1 11/5/2011

BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG

11c

11x

(cid:215) (cid:215) (cid:215) (cid:215) (cid:215) (cid:215)

i j Moät oâ ( , )

ijc

ijx

(cid:215) (cid:215) (cid:215)

mnc

mnx

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

}

1 2 , ,...,

(cid:215) (cid:215) (cid:215)

m j 1 2 , ,..., ; }0

G x ( )

MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM { = i j i ( , ) { = i j x ( , ) ij i j G x ( , ) ( )

TaäpTaäpTaäpTaäp caùccaùccaùccaùc oâoâoâoâ choïn TaäpTaäpTaäpTaäp caùccaùccaùccaùc oâoâoâoâ choïn choïnchoïn ˇ loaïi CCCCaùcaùcaùcaùc oâoâoâoâ loaïi loaïi loaïi

phaàn töûtöûtöûtöû cuûacuûacuûacuûa GGGG((((xxxx)))) ||||GGGG((((xxxx)| )| )| )| laø laø soásoásoásoá phaàn phaàn phaàn laølaø Phöông aùnaùnaùnaùn cöïccöïccöïccöïc bieânbieânbieânbieân :::: laø Phöông quaù mmmm ++++ nnnn ----1111 khoâng quaù phöông aùnaùnaùnaùn coùcoùcoùcoù khoâng laø phöông quaù quaù khoâng khoâng phöông phöông laølaø Phöông Phöông choïn oâoâoâoâ choïn choïnchoïn

Phöông ñuùng phöông aùnaùnaùnaùn coùcoùcoùcoù ñuùng laø phöông khoâng suysuysuysuy bieánbieánbieánbieán :::: laø Phöông aùnaùnaùnaùn cöïccöïccöïccöïc bieânbieânbieânbieân khoâng ñuùng ñuùng phöông phöông laølaø khoâng khoâng Phöông Phöông choïn m+nm+nm+nm+n----1111 oâoâoâoâ choïn choïnchoïn

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM MOÄT SOÁ KHAÙI NIEÄM

trình:::: TaäpTaäpTaäpTaäp caùccaùccaùccaùc oâoâoâoâ ((((i,ji,ji,ji,j)))) ñöôïc ChuChuChuChu trình trình neáuneáuneáuneáu laø moätmoätmoätmoät chuchuchuchu trình ñöôïc goïigoïigoïigoïi laø trình trình trình trình laølaø ñöôïc ñöôïc iiii)))) HaiHaiHaiHai oâoâoâoâ caïnh cuøng haøng phaûi naèmnaèmnaèmnaèm treântreântreântreân cuøng haøng hayhayhayhay moätmoätmoätmoät coätcoätcoätcoät,,,, nhau phaûi caïnh nhau haøng haøng cuøng cuøng phaûi phaûi nhaunhau caïnh caïnh iiiiiiii)))) Khoâng haøng hayhayhayhay moätmoätmoätmoät coätcoätcoätcoät,,,, cuøng moätmoätmoätmoät haøng Khoâng coùcoùcoùcoù 3333 oâoâoâoâ naèmnaèmnaèmnaèm treântreântreântreân cuøng haøng haøng cuøng cuøng Khoâng Khoâng iiiiiiiiiiii)))) OÂOÂOÂOÂ ñaàuñaàuñaàuñaàu tieântieântieântieân vaøvaøvaøvaø oâoâoâoâ cuoái nhau.... truøng nhau cuøng truøng cuoái cuøng nhaunhau truøng truøng cuøng cuøng cuoái cuoái

VíVíVíVí duïduïduïduï (cid:215) (cid:215) (cid:215) (cid:215) (cid:215) (cid:215)

(cid:215) (cid:215) (cid:215)

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

(cid:215) (cid:215) (cid:215)

2 11/5/2011

MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT MOÄT SOÁ TÍNH CHAÁT

Phöông aùnaùnaùnaùn xxxx laølaølaølaø phöông 1111.... Phöông phöông aùnaùnaùnaùn cöïccöïccöïccöïc bieânbieânbieânbieân neáuneáuneáuneáu GGGG((((xxxx)))) khoâng khoâng Phöông khoâng khoâng phöông phöông Phöông trình chöùa chuchuchuchu trình chöùa trình trình chöùa chöùa

2222.... MoïiMoïiMoïiMoïi taäptaäptaäptaäp GGGG cocococoùùùù ||||GGGG((((xxxx)|=)|=)|=)|=mmmm++++nnnn ñeàuñeàuñeàuñeàu chöùa trình.... chöùa chuchuchuchu trình trình trình chöùa chöùa

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT TÌM PHÖÔNG AÙN XUAÁT PHAÙT

3333.... ChoChoChoCho PPPP laølaølaølaø taäptaäptaäptaäp goàmgoàmgoàmgoàm mmmm++++nnnn ----1111 oâoâoâoâ khoâng trình vaøvaøvaøvaø chöùa chuchuchuchu trình khoâng chöùa trình trình chöùa chöùa khoâng khoâng j ) chöùa moätmoätmoätmoät seõseõseõseõ chöùa chöùa chöùa ∪ P i ( , 0 thuoäc veàveàveàveà PPPP.... KhiKhiKhiKhi ñoùñoùñoùñoù ((((iiii0000,,,, jjjj0000)))) khoâng khoâng thuoäc thuoäc thuoäc khoâng khoâng nhaát trình duyduyduyduy nhaát chuchuchuchu trình nhaát nhaát trình trình

neáu a

}

min

{ a b , i

neáu a

 a =  b 

phaùp GoùcGoùcGoùcGoùc taâytaâytaâytaây baécbaécbaécbaéc Phöông phaùp 1.1.1.1. Phöông Phöông phaùp phaùp Phöông ---- ÑiÑiÑiÑi töøtöøtöøtöø ooooââââ ((((1111,,,,1111)))) ñeánñeánñeánñeán oâoâoâoâ ((((mmmm,,,,nnnn)))) theo döôùi xuoáng döôùi höôùng töøtöøtöøtöø treântreântreântreân xuoáng theo höôùng döôùidöôùi xuoáng xuoáng höôùng höôùng theotheo phaûi.... sang phaûi traùi sang töøtöøtöøtöø traùi phaûi phaûi sang sang traùi traùi haøng vaøovaøovaøovaøo oâoâoâoâ ((((iiii,,,,jjjj)))).... phoái toáitoáitoáitoái ñañañaña haøng ---- PhaânPhaânPhaânPhaân phoái haøng haøng phoái phoái £ £

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ

phaùp CCCCminminminmin Phöông phaùp 2222.... Phöông phaùp phaùp Phöông Phöông Duyeät taáttaáttaáttaát caûcaûcaûcaû caùccaùccaùccaùc oâoâoâoâ töøtöøtöøtöø ((((1111,,,,1111)))) ñeánñeánñeánñeán oâoâoâoâ ((((mmmm,,,,nnnn)))) ---- Duyeät Duyeät Duyeät haøng vaøovaøovaøovaøo oâoâoâoâ ((((iiii,,,,jjjj)))) coùcoùcoùcoù ccccminminminmin.... phoái toáitoáitoáitoái ñañañaña haøng ---- PhaânPhaânPhaânPhaân phoái haøng haøng phoái phoái

m j ;

u v , i

;

i j G X ( , )

(

)

neáu

c ij

;

i j G X ( , )

(

)

neáu

c ij

 u i  u  i

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

1.1.1.1. ÑieàuÑieàuÑieàuÑieàu kieänkieänkieänkieän toáitoáitoáitoái öuöuöuöu:::: phöông aùnaùnaùnaùn toáitoáitoáitoái phöông aùnaùnaùnaùn XXXX laølaølaølaø phöông ---- ÑieàuÑieàuÑieàuÑieàu kieänkieänkieänkieän caàncaàncaàncaàn vaøvaøvaøvaø ñuûñuûñuûñuû ñeåñeåñeåñeå moätmoätmoätmoät phöông phöông phöông phöông phöông theá vòvòvòvò öuöuöuöu,,,, neáuneáuneáuneáu toàntoàntoàntoàn taïitaïitaïitaïi caùccaùccaùccaùc theá theá theá = = 1 2 , ,.., 1 2 , ,..., thoaû maõnmaõnmaõnmaõn thoaû thoaû thoaû ˛ £ ˇ

3 11/5/2011

THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ

x= ( = i =

m j ; i j G X ( , )

)ij 1 2 , ,.., ; neáu

c ij v

;

i j G X ( , )

(

)

taïi

X 0 u v , , i j + u v i D = ij

j + u i

c ij

2222.... Thuaät toaùn Thuaät toaùn toaùntoaùn Thuaät Thuaät phaùt suaát phaùt phöông aùnaùnaùnaùn suaát BöôùcBöôùcBöôùcBöôùc 1111:::: TìmTìmTìmTìm phöông phaùt phaùt suaát suaát phöông phöông theá vòvòvòvò BöôùcBöôùcBöôùcBöôùc 2: 2: 2: 2: TìmTìmTìmTìm caùccaùccaùccaùc theá theá theá ˛ ((((GoùcGoùcGoùcGoùc taâytaâytaâytaây baécbaécbaécbaéc,,,, CCCCminminminmin)))) n 1 2 , ,..., ) ( thoaû maõnmaõnmaõnmaõn thoaû thoaû thoaû - ˇ

ThìThìThìThì XXXX laø PATÖ laø PATÖ PATÖPATÖ laølaø

---- NeáuNeáuNeáuNeáu

(

( , )

böôùc 5555 qua böôùc Chuyeån qua Chuyeån böôùcböôùc qua qua Chuyeån Chuyeån

---- NeáuNeáuNeáuNeáu

" ˇ D £ BöôùcBöôùcBöôùcBöôùc 3: 3: 3: 3: TínhTínhTínhTính ñoäñoäñoäñoä cheânh cheânh leächleächleächleäch cheânh cheânh BöôùcBöôùcBöôùcBöôùc 4: 4: 4: 4: KieåmKieåmKieåmKieåm tratratratra tínhtínhtínhtính toáitoáitoáitoái öuöuöuöu i j G X $ ˇ 0

max{

)

)}

chænh ---- XaùcXaùcXaùcXaùc ñònhñònhñònhñònh oâoâoâoâ hieäuhieäuhieäuhieäu chænh chænh chænh

D ˇ

): 0 D > i j G X ( , ) ): ( 0 phöông aùnaùnaùnaùn chænh phöông BöôùcBöôùcBöôùcBöôùc 5: 5: 5: 5: ÑieàuÑieàuÑieàuÑieàu chænh phöông phöông chænh chænh D > j i 0 |( , ) ( , ij i j s s s s ∪ G X ) ( nhaát K K K K trong trong chænh duyduyduyduy nhaát trình ñieàuñieàuñieàuñieàu chænh ---- TìmTìmTìmTìm moätmoätmoätmoät chuchuchuchu trình trong trong nhaátnhaát chænh chænh trình trình 0 j i ) trong K K K K vôùivôùivôùivôùi ( , ---- ÑaùnhÑaùnhÑaùnhÑaùnh daáudaáudaáudaáu (+), ( (+), (----) ) ) ) xenxenxenxen keûkeûkeûkeû vaøovaøovaøovaøo caùccaùccaùccaùc oâoâoâoâ trong trong trong (+), ( (+), ( s s = i j K x min{ |( , ) chænh löôïng hieäuhieäuhieäuhieäu chænh ---- XaùcXaùcXaùcXaùc ñònhñònhñònhñònh löôïng chænh chænh löôïng löôïng

i j G X ( 0 j i ) ( , s s K + }

0 i j ,

0 i r

j r

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ

vôùivôùivôùivôùi

x= (

˛ - ˛

)ij

i j K ( , )

neáu

0 ij

i j K ( , )

neáu

1 ij

0 ij

i j K ( , )

neáu

0 ij

 x = x   x 

Trong ñoùñoùñoùñoù Trong Trong Trong

{ Caùc oâ trong

} ñöôïc ñaùnh daáu +

---- XaâyXaâyXaâyXaây döïng phöông aùnaùnaùnaùn môùimôùimôùimôùi döïng phöông phöông phöông döïng döïng ˛ - - ˛ ˇ

{ Caùc oâ trong

} ñöôïc ñaùnh daáu -

KhiKhiKhiKhi ñoùñoùñoùñoù, , , ,

f X (

)

f X (

)

i j s s

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ THUAÄT TOAÙN THEÁ VÒ

VíVíVíVí duïduïduïduï....

phaùt môùimôùimôùimôùi. (Quay ---- Ta Ta Ta Ta coùcoùcoùcoù moätmoätmoätmoät phöông böôùc 1) 1) 1) 1) laïi böôùc . (Quay laïi xuaát phaùt phöông aùnaùnaùnaùn xuaát . (Quay böôùc böôùc laïi laïi . (Quay phaùt phaùt xuaát xuaát phöông phöông ---- VôùiVôùiVôùiVôùi giaùgiaùgiaùgiaù tròtròtròtrò cuûacuûacuûacuûa haømhaømhaømhaøm muïcmuïcmuïcmuïc tieâutieâutieâutieâu môùimôùimôùimôùi ñöôïc ñöôïc xaùcxaùcxaùcxaùc ñònhñònhñònhñònh ñöôïc ñöôïc = - · D

60 30 40 70

5 2 4 1 50

3 6 8 4 70

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

5 3 1 2 80

4 11/5/2011

CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN CAÙC TRÖÔØNG HÔÏP SUY BIEÁN

hay

∑ ∑ > a

∑ ∑ < a

= 1

phaùt baèng thuthuthuthu phaùt Khoâng caâncaâncaâncaân baèng iiii)))) Khoâng phaùt phaùt baèng baèng Khoâng Khoâng n m

= i 1 phaùt XXXX0000 suysuysuysuy bieánbieánbieánbieán xuaát phaùt Phöông aùnaùnaùnaùn xuaát ii)ii)ii)ii) Phöông phaùt phaùt xuaát xuaát Phöông Phöông < )|

+ - m n 1 G X ( |

NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG NGUYEÃN VAÊN PHONG

haøng töøtöøtöøtöø aaaaiiii ñeánñeánñeánñeán chuyeån haøng theå chuyeån khoâng theå iii)iii)iii)iii) BaøiBaøiBaøiBaøi toaùntoaùntoaùntoaùn coùcoùcoùcoù oâoâoâoâ caámcaámcaámcaám:::: KhiKhiKhiKhi tatatata khoâng haønghaøng chuyeån chuyeån theå theå khoâng khoâng trong moätmoätmoätmoät soásoásoásoá ñieàuñieàuñieàuñieàu kieänkieänkieänkieän naøonaøonaøonaøo ñoùñoùñoùñoù)))) thìthìthìthì oâoâoâoâ ((((i,ji,ji,ji,j )))) laø bbbbjjjj ((((trong laø oâoâoâoâ caámcaámcaámcaám laølaø trong trong