Quy hoạch thủy lợi - Phụ chương 4

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

93
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một trong các phương pháp chọn phương án tối ưu, thuật toán Qui hoạch Tuyến tính (Linear Programming) được sử dụng nhiều trong phân tích kinh tế. Sau đây là các ví dụ dẫn đến các bài toán Quy hoạch Tuyến tính: QUI HOẠCH TUYẾN TÍNH ? Ví dụ thứ 1: Nông dân Hai Lúa có 50 ha đất. Bên cạnh kỹ thuật kinh nghiệm canh tác và tiên đoán thị trường tiêu thụ, dựa vào điều kiện đất đai, nhân lực và nguồn nước, Hai Lúa quyết định trồng 2 loại hoa màu là Bắp và Đậu. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Quy hoạch thủy lợi - Phụ chương 4

Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- PHUÛ CHÆÅNG 4 QUI HOAÛCH TUYÃÚN TÊNH --- oOo --- Mäüt trong caïc phæång phaïp choün phæång aïn täúi æu, thuáût toaïn Qui hoaûch Tuyãún tênh (Linear Programming ) âæåüc sæí duûng nhiãöu trong phán têch kinh tãú. Sau âáy laì caïc vê duû dáùn âãún caïc baìi toaïn Quy hoaûch Tuyãún tênh:  Vê duû thæï 1: Näng dán Hai Luïa coï 50 ha âáút. Bãn caûnh kyî thuáût kinh nghiãûm canh taïc vaì tiãn âoaïn thë træåìng tiãu thuû, dæûa vaìo âiãöu kiãûn âáút âai, nhán læûc vaì nguäön næåïc, Hai Luïa quyãút âënh träöng 2 loaûi hoa maìu laì Bàõp vaì Âáûu. Säø tay Träöng troüt cuía Hai Luïa cho biãút âãø coï 1 Táún saín pháøm tæìng loaûi hoa maìu thç cáön: Yãúu täú Âån vë Hoa maìu Nguäön taìi saín xuáút tênh nguyãn låïn nháút Bàõp (1) Âáûu (2) Âáút âai Ha/Táún 2 3 50 Ha Nhán læûc Ngæåìi - Vuû/Táún 6 4 90 Ngæåìi - Vuû Nguäön næåïc 10 6 m3/ Táún 20 5 250 x 10 6 m3 Tiãön låìi Tr.Â/ Táún 18 21 Haîy âënh phæång aïn huy âäüng nguäön taìi nguyãn âãø coï säú saín pháøm baïn låìi nháút. Hæåïng giaíi: Goüi X1 laì säú táún thu hoaûch cho vuû Bàõp, X2 laì säú táún thu hoaûch cho vuû Âáûu. Giaï baïn cho säú saín pháøm naìy: Z = 18.X1 + 21.X2 (täøng låüi nhuáûn thu âæåüc theo phæång aïn saín xuáút) Muûc tiãu cuía Hai Luïa laì coï giaï trë Zmax. C Goüi Z= X j  max. Z goüi laì haìm muûc tiãu (Objective Function). n j j 1 trong âoï Cj laì låüi nhuáûn thu âæåüc cho 1 âån vë saím pháøm Xj . Trong baìi toaïn trãn, giaï trë X1 vaì X2 bë raìng buäüc båíi caïc yãúu täú khaïc (yãúu täú haûn chãú taìi nguyãn):  Âáút âai (i=1): 2X1 + 3X2  50 (ha)  Nhán læûc (i=2): 6X1 + 4X2  90 (ngæåìi - vuû)  Nguäön næåïc (i=3): 20X1 + 5X2  250 (106 m3)  Täøng quaït:  b i , våïi i = 1 .. m, j = 1 .. n n a ij X j j1 Caïc raìng buäüc naìy goüi laì caïc raìng buäüc chuí âäüng (Active Constrains) Dé nhiãn, X1 vaì X2 biãøu thë saín pháøm nãn: X1  0 vaì X2  0 hay Xj  0 våïi j = 1 .. m Goüi laì caïc raìng buäüc thuû âäüng (Inactive Constrains) --------------------------------------------------------------------------------------------------------- 66 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- Toïm laûi ta coï baìi toaïn täøng quaït: C Z= X j  max n j j 1 a n  b i , våïi i = 1 .. m, j = 1 .. n X ij j j 1 Xj  0 Hãû phæång trçnh daûng naìy goüi laì baìi toaïn Qui hoaûch Tuyãún tênh daûng Chuáøn.  Vê duû thæï 2: Coï 3 häö chæïa næåïc A, B vaì C, nãúu muäún khai thaïc coï låüi thç læåüng næåïc láúy âi phaíi êt nháút láön læåüt laì 20, 30, vaì 50 Triãûu m3 trong muìa khä. Hai huyãûn I vaì II coï nhu cáöu næåïc täúi thiãøu âãø canh taïc trong muìa khä láön læåüt laì 40 vaì 60 Triãûu m3. Chi phê khai thaïc næåïc cho åí baíng sau: Huyãûn Chi phê khai thaïc næåïc (106 $ / Triãûu m3) A (20 Triãûu m3) B (30 Triãûu m3) C (50 Triãûu m3) I 2 4 5 II 3 6 7 Haîy âënh phæång aïn khai thaïc næåïc våïi chi phê nhoí nháút. Hæåïng giaíi: Goüi X1, X2 vaì X3 laì khäúi læåüng næåïc tæì häö A, B vaì C vãö huyãûn I. X4, X5 vaì X6 laì khäúi læåüng næåïc tæì häö A, B vaì C vãö huyãûn II. Dé nhiãn, X1, X2, X3, X4, X5 vaì X6  0 Täøng kinh phê khai thaïc nguäön næåïc phaíi nhoí nháút, nghéa laì: Z = 2X1 + 4X2 + 5 X3 + 3 X4 + 6X5 +7X6  min Âãø âaím baío nhu cáöu næåïc täúi thiãøu cho mäùi huyãûn, ta coï: X1 + X2 + X3  40 (huyãûn I) X4 + X5 + X6  60 (huyãûn II) Mæïc khai thaïc næåïc täúi thiãøu coï låüi cho tæìng häö chæïa:  Häö A: X1 + X4  20 (Triãûu m3)  Häö B: X2 + X5  30 (Triãûu m3)  Häö C: X3 + X6  50 (Triãûu m3) --------------------------------------------------------------------------------------------------------- 67 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- Täøng quaït (theo caïc kyï hiãûu trãn): C Z= X j  min n j j 1 a n  b i , våïi i = 1 .. m, j = 1 .. n X ij j j 1 Xj  0 Daûng naìy goüi laì baìi toaïn Qui hoaûch Tuyãún tênh daûng Cå baín.  Trong træåìng håüp: C Z= X j  min n j j 1 a  b i , våïi i = 1 .. m, j = 1 .. n n X ij j j 1 Xj  0 Daûng naìy goüi laì baìi toaïn Qui hoaûch Tuyãún tênh daûng Chênh tàõc.  Daûng täøng quaït chung: C Z= X j  max (min) n j j 1 a n  bi , våïi i = 1 .. m, j = 1 .. n Xj = ij j 1   Xj = 0 hoàûc khäng haûn chãú  Vê duû: Mäüt hãû thäúng thuíy låüi nhæ hçnh veî, caïc dæî liãûu liãn quan âãún diãùn biãún cuía cuía nguäön næåïc (âån vë laì triãûu m3) âæåüc xaïc âënh theo cå såí trung bçnh theo muìa nhæ sau: t =1 : Muìa xuán; t = 2 : Muìa haû; t = 3 : Muìa thu; t = 4 : Muìa âäng. Âiãöu kiãûn baìi toaïn:  Doìng chaíy âãún häö chæïa vaì doìng bäø xung hàòng nàm laì äøn âënh (thæûc tãú coï thãø xeït theo táön suáút xuáút hiãûn)  Thåìi gian xeït laì 1 nàm thuíy vàn (tæì âáöu muìa xuán âãún cuäúi muìa âäng) --------------------------------------------------------------------------------------------------------- 68 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- Læåüng næåïc âãún : Z11 = 0,4 Z12 = 0,3 Z13 = 0,5 S14 = 1,1 Læåüng træî trong häö : S1 = 0,79 S2 = 2,20 S3 = 0 S4 = 0,09 Häö chæïa næåïc coï Læåüng xaí : dung têch laì K, L æåüng tæåïi: R1 = 1,99 R2 = 2,5 læåün g træî laì St K1I = 0,5.I K2I = 0,375.I R3 = 0,41 R4 = 0,4 K3I = 0 K4I = 0,125.I Näng trang Tæåïi Nhu cáöu næåïc I (106 m3/nàm) Säng 1 bäø xung : L æåüng næåïc traí vãö : Z21 = 0,79 S22 = 2,20 K’1I = 0,18.I K’2I = 0,12.I Z23 = 0 S24 = 0,09 K’3I = 0,12 K’4I = 0,08.I Säng 2 bäø xung : Z31 = 0,3 S32 = 0,3 Z33 = 0,6 S34 = 1,3 Nhaì maïy thuíy âiãûn E (KWH/nàm) Caïc biãún quyãút âënh: K : dung têch häö chæïa I : læåüng næåïc tæåïi cho näng trang/ nàm E : håüp âäöng cung cáúp âiãûn  Rt : læåüng næåïc xaí tæì häö nhàòm baío âaím doìng chaíy haû læu (cho giao thäng, thuíy saín, caïc hoaût âäüng khaïc, ... )  St : læåüng næåïc træî trong häö. Haìm phaït âiãûn: Et = 0 ,144 Qt Qt : læåüng næåïc chaíy qua turbine åí muìa t  Et : nàng læåüng phaït ra åí muìa t  Viãûc saín xuáút nàng læåüng phaíi âæåüc phán bäú âãöu hàòng nàm: Et  E 4 Nàng luåüng thæìa: ) seî duìng båm næåïc tråí laûi häö. ( Et  E 4 Haìm muûc tiãu:  Tiãön låìi baïn âiãûn: 200 $/KWH/nàm  Tiãön tæåïi næåïc: 40 $/106.m3/nàm  Tiãön baío dæåîng häö chæïa: 24 $/106.m3/nàm --------------------------------------------------------------------------------------------------------- 69 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- Giaíi: Haìm muûc tiãu: max Z = 200 E + 40 I - 24 K Raìng buäüc:  Læåüng næåïc xaí: Rt  St + Z1t våïi t = 1 .. 4 Cán bàòng næåïc häö chæïa:  St = St-1 + Z1 t-1 - Rt-1 (xem læåüng bäúc håi vaì roì rè khäng âaïng kãø) ÅÍ muìa xuán, t = 1, cho St-1 = S4 (cuía nàm træåïc) Dung têch häö chæïa:  St + Z1t - Rt  K Doìng chaíy åí âiãøm láúy næåïc tæåïi:  Z2t + Rt - KtI  0 våïi t = 1 .. 4 Læåüng næåïc cho nhaì maïy thuíy âiãûn phaíi låïn hån læåüng næåïc cáön thiãút cho  maïy chaûy: Z2t + Rt - Kt.I + K't.I + Z3t  våïi t = 1 .. 4 E 4  0,144 Caïc raìng buäüc thuû âäüng:  St, Rt, E, I vaì K  0 Caïc baìi toaïn qui hoaûch tuyãún tênh coï thãø giaíi bàòng caïc phæång phaïp sau:  Phæång phaïp âäö giaíi (Graphical method )  Phæång phaïp âån hçnh (Simplex method)  Phæång phaïp âäúi ngáùu (Dual method ) Hiãûn nay, coï ráút chæång trçnh maïy tênh âaî âæåüc láûp sàôn âãø giuïp viãûc giaíi caïc baìi toaïn qui hoaûch tuyãún tênh, vê duû nhæ pháön mãöm QSB (Quantitative Systems for Bussiness) cuía taïc giaí Yih-Long Chang vaì Robert S. Sullian, 1986. --------------------------------------------------------------------------------------------------------- 70 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún  ---------------------------------------------------------------------------------------------------------------------- GIAÍI BAÌI TOAÏN QUI HOAÛCH TUYÃÚN TÊNH BÀÒNG ÂÄÖ GIAÍI Duìng âäö giaíi âãø tçm kãút quaí cho nhæîng baìi toaïn qui hoaûch tuyãún tênh: AÏp duûng cho nhæîng haìm âa biãún  Âäü tin cáûy phuû thuäüc vaìo sæû chi ly cuía ngæåìi giaíi.  Vê duû thæï 1: ÁØn säú cuía baìi toaïn X1 vaì X2 (Táún) Haìm muûc tiãu: max Z = 18.X1 + 21.X2 Raìng buäüc: + Âáút: 2.X1 + 3.X2  50 + Nhán læûc: 6.X1 + 4.X2  90 Raìng buäüc chuí âäüng + Næåïc: 20X1 + 5.X2  250 X1  0 vaì X2  0 Raìng buäüc thuû âäüng X2 Nghiãûm coï toüa âäü: 50 -- A (7, 12)  Z = 378  20X1 + 5.X2  250 B (11,5)  Z = 303 40 -- C (0,16.6) D (12.4,0) 30 -- 6.X1 + 4.X2  90 20 -- C 2.X1 + 3.X2  50 A 10 -- B 0| -- | | | | | D 0 10 20 30 40 50 X1 Thãú vaìo baíng kãú hoaûch saín xuáút, ta seî coï: Yãúu täú Hoa maìu (Táún) Taìi nguyãn Taìi nguyãn saín xuáút låïn nháút sæí duûng Bàõp (1) Âáûu (2) Âáút âai (Ha/Táún) 14 36 50 50 (duìng hãút) Nhán læûc (Ngæåìi - Vuû/Táún) 42 48 90 50 (duìng hãút) Nguäön næåïc (10 6 m3/ Táún) 140 60 250 200 (dæ 50) Tiãön låìi (Tr.Â) 126 252 Täøng laîi = 378 Tr.Â --------------------------------------------------------------------------------------------------------- 71 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún  ---------------------------------------------------------------------------------------------------------------------- GIAÍI BAÌI TOAÏN QUI HOAÛCH TUYÃÚN TÊNH BÀÒNG PHÆÅNG PHAÏP ÂÅN HÇNH (SIMPLEX METHOD) Vê duû: Mäüt häö chæïa næåïc muìa khä coï dung têch laì 8 x 10 6 m3 næåïc phuûc vuû cho 2 muûc tiãu laì phaït âiãûn vaì tæåïi. Coï 2 khu væûc cáön cung cáúp mäüt læåüng næåïc tæåïi âäöng thåìi. Do âiãöu kiãûn cäng trçnh, täøng læåüng doìng chaíy cho tæåïi khäng quaï 3 x 10 6 m3 vaì cho thuíy âiãûn khäng quaï 4 x 106 m3. Giaï 1 m3 næåïc cho tæåïi laì 1,5 $ vaì 1 m3 næåïc cho phaït âiãûn laì 2 $. Tçm giaíi phaïp cáúp næåïc cho 2 cäng trçnh coï låüi nháút. PHAÏT ÂIÃÛN X1 HÄÖ CHÆÏA TÆÅÏI NÆÅÏC X2 TÆÅÏI NÆÅÏC X2 Giaíi: Goüi X1 laì læåüng næåïc cáúp cho âiãûn (x 106 m3) X2 laì læåüng næåïc cáúp cho tæåïi (x 106 m3) åí 1 khu væûc. Haìm muûc tiãu: Z = 2.X1 + 2(1,5)X2 = 2.X1 + 3 .X2  max Raìng buäüc: X1  4 X2  3 chuí âäüng X1 + 2X2  8 X1  0; X2  0 thuû âäüng Phæång trçnh coï thãø viãút: Z - 2.X1 + 3.X2 =0 X1 + X3 =4 X2 + X4 =3 X1 + 2X2 + X5 =8 Xj  0; j = 1, 2, 3, 4, 5 X3, X4, X5 laì nhæîng áøn säú phuû. Baìi toaïn naìy ngoaìi caïch giaíi bàòng âäö thë nhæng khäng chênh xaïc vç coìn phuû thuäüc vaìo caïch veî cuía ngæåìi tênh vaì khäng âæåüc täøng quaït. Phæång phaïp âån hçnh laì 1 tiãún trçnh bao quaït chuyãøn 1 âiãøm tæì cæûc trë naìy sang 1 cæûc trë kãú cáûn coï tênh æu viãût hån. Khi khäng coìn âiãøm cæûc trë naìo maì tênh æu viãût cao hån thç cháúm dæït bæïc tênh. Phæång phaïp naìy laì 1 tiãún trçnh âaûi säú âãø tçm baìi giaíi täúi æu bàòng 1 quaï trçnh thæí dáön âãø coï kãút quaí cuäúi cuìng täút nháút cho muûc tiãu. --------------------------------------------------------------------------------------------------------- 72 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- LÁÛP BAÍNG ÂÅN HÇNH (SIMPLEX TABLEAU): duìng biãún giaí nhæ biãún cå baín: Cäüt chuí chäút Biãún Haìng Caïc hãû säú cuía Pháön phaíi cuía phæång trçnh cå baín thæï Z X1 X2 X3 X4 X5 Z 0 1 -2 -3 0 0 0 0 X3 1 0 1 0 1 0 0 4 X4 2 0 0 1 0 1 0 3 X5 3 0 1 2 0 0 1 8 Säú chuí chäút Haìng chuí chäút Cäüt chuí chäút (Pivot column): xaïc âënh bàòng caïch láúy giaï trë ám nhoí nháút cuía  haìng Z. Haìng chuí chäút (Pivot row): láúy giaï trë dæång nhoí nháút qua pheïp thæí tè säú min  (minimum ration test), nhæ sau (láúy pháön phaíi cuía phæång trçnh chia cho caïc hãû säú trong cäüt chuí chäút - træåìng håüp hãû säú trong cäüt chuí chäút laì 0 thç gaïn laì 1): Láúy = 3 (min) ; =4 ; =4 3 4 8 1 1 2 Säú giao giæîa cäüt chuí chäút vaì haìng chuí chäút goüi laì säú chuí chäút (pivot number)  Nguyãn tàõc biãún âäøi trong phæång phaïp âån hçnh: + Tçm moüi caïch âæa hãû säú cäüt chäút vãö säú 0 (bàòng caïch nhán haìng chuí chäút våïi hãû säú cäüt chäút räöi træì nhau) + Haìng chäút giæîa nguyãn + Tiãún trçnh cháúm dæït khi moüi hãû säú cuía haìm muûc tiãu (Z) bàòng 0. [ -2 0 0 0 0 ] Haìng 0 -3 - [ 0 0 1 0 3 ] Haìng chäút x (-3) 1 [ -2 0 3 0 9 ] Haìng 0 (måïi) 0 [ 1 0 1 0 0 4 ] Haìng 1 (giæî y nguyãn vç hãû säú cuía cäüt chäút bàòng 0) [ -2 -3 0 0 0 0 ] Haìng 2 (giæî y nguyãn vç âáy laì haìng chuí chäút) [ 1 0 0 1 8 ] Haìng 3 2 - [ 0 1 0 1 0 3 ] Haìng chäút x (-2) [ 1 0 -2 1 2 ] Haìng 3 (måïi) 0 --------------------------------------------------------------------------------------------------------- 73 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ
Giaïo trçnh QUI HOAÛCH THUÍY LÅÜI ThS. Lã Anh Tuáún ---------------------------------------------------------------------------------------------------------------------- Sau khi biãún âäøi láön thæï 1, ta coï baíng måïi nhæ sau: Biãún Haìng Caïc hãû säú cuía Pháön phaíi cuía phæång trçnh cå baín thæï Z X1 X2 X3 X4 X5 Z 0 1 -2 0 0 3 0 9 X3 1 0 0 1 0 1 0 3 X4 2 0 1 0 1 0 0 4 X5 3 0 1 0 0 -2 1 2 Láûp laûi tiãún trçnh nhæ váûy, ta seî coï baíng kãút quaí sau: Láön Biãún Caïc hãû säú cuía Pháön phaíi cuía phæång thæíï cå baín Z X1 X2 X3 X4 X5 trçnh Z 1 -2 -3 0 0 0 0 1 X3 0 1 0 1 0 0 4 X4 0 0 1 0 1 0 3 X5 0 1 2 0 0 1 8 Z 1 -2 0 0 3 0 9 2 X3 0 0 1 0 1 0 3 X4 0 1 0 1 0 0 4 X5 0 1 0 0 -2 1 2 Z 1 0 0 0 -1 2 13 3 X3 0 1 0 0 -2 1 2 X4 0 0 1 0 1 0 3 X5 0 0 0 1 2 -1 2 Z 1 0 0 (1/2) 0 (3/2) 14 4 X3 0 1 0 1 0 0 4 X4 0 0 1 - (1/2) 0 (1/2) 2 X5 0 0 0 0 2 -1 2 Nghiãûm cuía baìi toaïn: Z* = 14 X1* = 4 X2* = 2 =========================================================== --------------------------------------------------------------------------------------------------------- 74 Chæång 4: LÆÛA CHOÜN PHÆÅNG AÏN ÂÁÖU TÆ