Xem mẫu
- 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
j1
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Æ
nguon tai.lieu . vn