Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------

PHỦ CHỈÅNG 4

QUI HOẢCH TUÚN TÊNH

--- oOo --Mäüt trong cạc phỉång phạp chn phỉång ạn täúi ỉu, thût toạn Qui hoảch Tuú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 bi toạn Quy hoảch Tuún tênh:

 Vê dủ thỉï 1:

Näng dán Hai Lụa cọ 50 ha âáút. Bãn cảnh k thût kinh nghiãûm canh tạc v tiãn
âoạn thë trỉåìng tiãu thủ, dỉûa vo âiãưu kiãûn âáút âai, nhán lỉûc v ngưn nỉåïc, Hai
Lụa quút âënh träưng 2 loải hoa mu l Bàõp v Âáûu. Säø tay Träưng trt ca Hai Lụa
cho biãút âãø cọ 1 Táún sn pháøm tỉìng loải hoa mu thç cáưn:
úu täú
sn xút

Âån vë
tênh

Âáút âai
Nhán lỉûc
Ngưn nỉåïc
Tiãưn låìi

Ha/Táún
Ngỉåìi - Vủ/Táún

10 6 m3/ Táún
Tr.Â/ Táún

Hoa mu
Bàõp (1)
Âáûu (2)
2
6
20
18

3
4
5
21

Ngưn ti
ngun låïn nháút
50 Ha
90 Ngỉåìi - Vủ
250 x 10 6 m3

Hy âënh phỉång ạn huy âäüng ngưn ti ngun âãø cọ säú sn pháøm bạn låìi nháút.
Hỉåïng gii:
Gi X1 l säú táún thu hoảch cho vủ Bàõp, X2 l säú táún thu hoảch cho vủ Âáûu.
Giạ bạn cho säú sn pháøm ny:
Z = 18.X1 + 21.X2
(täøng låüi nhûn thu âỉåüc theo phỉång ạn sn xút)
Mủc tiãu ca Hai Lụa l cọ giạ trë Zmax.
Gi


Z=

C
n

j 1

j

X j  max. Z gi l hm mủc tiãu (Objective Function).

trong âọ Cj l låüi nhûn thu âỉåüc cho 1 âån vë sm pháøm Xj . Trong bi toạn trãn,
giạ trë X1 v X2 bë rng büc båíi cạc úu täú khạc (úu täú hản chãú ti ngun):
 Âáút âai
(i=1):
2X1 + 3X2  50 (ha)
 Nhán lỉûc
(i=2):
6X1 + 4X2  90 (ngỉåìi - vủ)
 Ngưn nỉåïc
(i=3):
20X1 + 5X2  250 (106 m3)
Täøng quạt:


n

j1


a ij X

j

 b i , våïi i = 1 .. m, j = 1 .. n

Cạc rng büc ny gi l cạc rng büc ch âäüng (Active Constrains)
Dé nhiãn, X1 v X2 biãøu thë sn pháøm nãn: X1  0 v X2  0
hay
Xj  0 våïi j = 1 .. m
Gi l cạc rng büc thủ âäüng (Inactive Constrains)

--------------------------------------------------------------------------------------------------------- 66

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------

Tọm lải ta cọ bi toạn täøng quạt:
Z=

C

X j  max

n


j 1

a

j

n

j 1

ij

X

j

 b i , våïi i = 1 .. m, j = 1 .. n

Xj  0
Hãû phỉång trçnh dảng ny gi l bi toạn Qui hoảch Tuún tênh dảng Chøn.

 Vê dủ thỉï 2:

Cọ 3 häư chỉïa nỉåïc A, B v C, nãúu mún khai thạc cọ låüi thç lỉåüng nỉåïc láúy âi phi
êt nháút láưn lỉåüt l 20, 30, v 50 Triãûu m3 trong ma khä. Hai huûn I v II cọ nhu
cáưu nỉåïc täúi thiãøu âãø canh tạc trong ma khä láưn lỉåüt l 40 v 60 Triãûu m3.
Chi phê khai thạc nỉåïc cho åí bng sau:
Huûn
I
II


Chi phê khai thạc nỉåïc (106 $/ Triãûu m3)

A (20 Triãûu m3)
2
3

B (30 Triãûu m3)
4
6

C (50 Triãûu m3)
5
7

Hy âënh phỉång ạn khai thạc nỉåïc våïi chi phê nh nháút.
Hỉåïng gii:
Gi X1, X2 v X3 l khäúi lỉåüng nỉåïc tỉì häư A, B v C vãư huûn I.
X4, X5 v X6 l khäúi lỉåüng nỉåïc tỉì häư A, B v C vãư huûn II.
Dé nhiãn, X1, X2, X3, X4, X5 v X6  0
Täøng kinh phê khai thạc ngưn nỉåïc phi nh nháút, nghéa l:
Z = 2X1 + 4X2 + 5X3 + 3X4 + 6X5 +7X6  min
Âãø âm bo nhu cáưu nỉåïc täúi thiãøu cho mäùi huûn, ta cọ:
X1 + X2 + X3  40 (huûn I)
X4 + X5 + X6  60 (huûn II)
Mỉïc khai thạc nỉåïc täúi thiãøu cọ 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 CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------

Täøng quạt (theo cạc k hiãûu trãn):
Z=

C
n

j 1

a

j

X j  min
 b i , våïi i = 1 .. m, j = 1 .. n

n

j 1

X

ij


j

Xj  0
Dảng ny gi l bi toạn Qui hoảch Tuún tênh dảng Cå bn.

 Trong trỉåìng håüp:
Z=

C
n

j 1

a

j

X j  min

 b i , våïi i = 1 .. m, j = 1 .. n

n

j 1

ij

X


j

Xj  0
Dảng ny gi l bi toạn Qui hoảch Tuún tênh dảng Chênh tàõc.

 Dảng täøng quạt chung:
Z=

C
n

j 1

a

j

X j  max (min)

n

ij

j 1

Xj


=



bi , våïi i = 1 .. m, j = 1 .. n



Xj = 0 hồûc khäng hản chãú


Vê dủ: Mäüt hãû thäúng thy låüi nhỉ hçnh v, cạc dỉỵ liãûu liãn quan âãún diãùn biãún ca
ca ngưn nỉåïc (âån vë l triãûu m3) âỉåüc xạc âënh theo cå såí trung bçnh theo ma
nhỉ sau:
t =1 : Ma xn;
t = 2 : Ma hả;
t = 3 : Ma thu;
t = 4 : Ma âäng.
Âiãưu kiãûn bi toạn:
 Dng chy âãún häư chỉïa v dng bäø xung hàòng nàm l äøn âënh (thỉûc tãú cọ thãø
xẹt theo táưn sút xút hiãûn)
 Thåìi gian xẹt l 1 nàm thy vàn (tỉì âáưu ma xn âãún cúi ma âäng)
--------------------------------------------------------------------------------------------------------- 68

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tú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 cọ
dung têch l K,
lỉåün g trỉỵ l St

Lỉåüng x :
R1 = 1,99
R3 = 0,41

K2I = 0,375.I
K4I = 0,125.I

Näng trang
Nhu cáưu nỉåïc I (106 m3/nàm)

Tỉåïi

Säng 1 bäø xung :
Z21 = 0,79
S22 = 2,20
Z23 = 0

S24 = 0,09

Lỉåüng tỉåïi:
K1I = 0,5.I
K3I = 0

R2 = 2,5
R4 = 0,4

Lỉåüng nỉåïc tr vãư :
K’1I = 0,18.I
K’2I = 0,12.I
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

Nh mạy thy âiãûn E (KWH/nàm)

Cạc biãún quú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 x tỉì häư nhàòm bo âm dng chy hả lỉu (cho giao
thäng, thy sn, cạc hoảt âäüng khạc, ... )
 St
: lỉåüng nỉåïc trỉỵ trong häư.
Hm phạt âiãûn:
Et = 0,144 Qt

Qt : lỉåüng nỉåïc chy qua turbine åí ma t

Et
: nàng lỉåüng phạt ra åí ma t
Viãûc sn xút nàng lỉåüng phi âỉåüc phán bäú âãưu hàòng nàm: Et 
Nàng lüng thỉìa:

( Et 

E
4

E
) s dng båm nỉåïc tråí lải häư.
4

Hm mủc tiãu:
 Tiãưn låìi bạn âiãûn:
 Tiãưn tỉåïi nỉåïc:
 Tiãưn bo dỉåỵng häư chỉïa:

200 $/KWH/nàm

40 $/106.m3/nàm
24 $/106.m3/nàm

--------------------------------------------------------------------------------------------------------- 69

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------

Gii:
Hm mủc tiãu:

Rng büc:
 Lỉåüng nỉåïc x:

max Z = 200 E + 40 I - 24 K
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 v r rè khäng âạng kãø)
ÅÍ ma xn, t = 1, cho St-1 = S4 (ca nàm trỉåïc)




Dung têch häư chỉïa:



Dng chy åí âiãøm láúy nỉåïc tỉåïi:
Z2t + Rt - KtI  0



Lỉåüng nỉåïc cho nh mạy thy âiãûn phi låïn hån lỉåüng nỉåïc cáưn thiãút cho
mạy chảy:
E
Z2t + Rt - Kt.I + K't.I + Z3t 
våïi t = 1 .. 4
4  0,144



Cạc rng büc thủ âäüng:
St, Rt, E, I v K  0

St + Z1t - Rt  K
våïi t = 1 .. 4

Cạc bi toạn qui hoảch tuún tênh cọ thãø gii bàòng cạc phỉång phạp sau:
 Phỉång phạp âäư gii (Graphical method)
 Phỉång phạp âån hçnh (Simplex method)
 Phỉång phạp âäúi ngáùu (Dual method)
Hiãûn nay, cọ ráút chỉång trçnh mạy tênh â âỉåüc láûp sàơn âãø giụp viãûc gii cạc bi
toạn qui hoảch tuún tênh, vê dủ nhỉ pháưn mãưm QSB (Quantitative Systems for

Bussiness) ca tạc gi Yih-Long Chang v Robert S. Sullian, 1986.

--------------------------------------------------------------------------------------------------------- 70

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------






GII BI TOẠN QUI HOẢCH TUÚN TÊNH BÀỊNG ÂÄƯ GII

Dng âäư gii âãø tçm kãút qu cho nhỉỵng bi toạn qui hoảch tuún tênh:
Ạp dủng cho nhỉỵng hm âa biãún
Âäü tin cáûy phủ thüc vo sỉû chi ly ca ngỉåìi gii.

Vê dủ thỉï 1:

ÁØn säú ca bi toạn
Hm mủc tiãu:
Rng büc:
+ Âáút:
+ Nhán lỉûc:
+ Nỉåïc:


X1 v X2 (Táún)
max Z = 18.X1 + 21.X2
2.X1 + 3.X2  50
6.X1 + 4.X2  90
20X1 + 5.X2  250
X1  0 v X2  0

X2

A (7, 12)  Z = 378 
B (11,5)
 Z = 303
C (0,16.6)
D (12.4,0)

20X1 + 5.X2  250

40 -30 --

6.X1 + 4.X2  90

20 --

0|
-0

A
B
|

|
D
10
20

2.X1 + 3.X2  50
|
30

Thãú vo bng kãú hoảch sn xút, ta s cọ:
úu täú
sn xút

Rng büc thủ âäüng

Nghiãûm cọ ta âäü:

50 --

C
10 --

Rng büc ch âäüng

Âáút âai (Ha/Táún)
Nhán lỉûc (Ngỉåìi - Vủ/Táún)
Ngưn nỉåïc (10 6 m3/ Táún)
Tiãưn låìi (Tr.Â)

|

40

Hoa mu (Táún)

Bàõp (1)
14
42
140
126

|
50

Âáûu (2)
36
48
60
252

X1

Ti ngun
låïn nháút
50
90
250

Ti ngun
sỉí dủng


50 (dng hãút)
50 (dng hãút)
200 (dỉ 50)

Täøng li = 378 Tr.Â

--------------------------------------------------------------------------------------------------------- 71

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giạo trçnh QUI HOẢCH THY LÅÜI
ThS. Lã Anh Tún
----------------------------------------------------------------------------------------------------------------------



GII BI TOẠN QUI HOẢCH TUÚN TÊNH BÀỊNG PHỈÅNG PHẠP

ÂÅN HÇNH (SIMPLEX METHOD)

Vê dủ: Mäüt häư chỉïa nỉåïc ma khä cọ dung têch l 8 x 10 6 m3 nỉåïc phủc vủ cho 2
mủc tiãu l phạt âiãûn v tỉåïi. Cọ 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 dng chy cho tỉåïi khäng quạ 3 x
10 6 m3 v cho thy âiãûn khäng quạ 4 x 106 m3. Giạ 1 m3 nỉåïc cho tỉåïi l 1,5 $ v 1
m3 nỉåïc cho phạt âiãûn l 2 $. Tçm gii phạp cáúp nỉåïc cho 2 cäng trçnh cọ låüi nháút.
PHẠT ÂIÃÛN X1

HÄƯ CHỈÏA


TỈÅÏI NỈÅÏC X2
TỈÅÏI NỈÅÏC X2

Gii:
Gi X1 l lỉåüng nỉåïc cáúp cho âiãûn (x 106 m3)
X2 l lỉåüng nỉåïc cáúp cho tỉåïi (x 106 m3) åí 1 khu vỉûc.
Hm mủc tiãu:
Rng büc:

Z = 2.X1 + 2(1,5)X2 = 2.X1 + 3.X2  max
X1  4
X2  3
ch âäüng
X1 + 2X2  8
X1  0; X2  0
thủ âäüng

Phỉång trçnh cọ 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 l nhỉỵng áøn säú phủ.
Bi toạn ny ngoi cạch gii bàòng âäư thë nhỉng khäng chênh xạc vç cn phủ thüc

vo cạch v ca ngỉåìi tênh v khäng âỉåüc täøng quạt. Phỉång phạp âån hçnh l 1
tiãún trçnh bao quạt chuøn 1 âiãøm tỉì cỉûc trë ny sang 1 cỉûc trë kãú cáûn cọ tênh ỉu
viãût hån. Khi khäng cn âiãøm cỉûc trë no m tênh ỉu viãût cao hån thç cháúm dỉït bỉïc
tênh. Phỉång phạp ny l 1 tiãún trçnh âải säú âãø tçm bi gii täúi ỉu bàòng 1 quạ trçnh
thỉí dáưn âãø cọ kãút qu cúi cng täút nháút cho mủc tiãu.
--------------------------------------------------------------------------------------------------------- 72

Chỉång 4: LỈÛA CHN PHỈÅNG ẠN ÂÁƯU TỈ


Giaùo trỗnh QUI HOACH THUY LĩI
ThS. Ló Anh Tuỏỳn
----------------------------------------------------------------------------------------------------------------------

LP BANG N HầNH (SIMPLEX TABLEAU): duỡng bióỳn giaớ nhổ bióỳn cồ baớn:
Cọỹt chuớ chọỳt

Bióỳn
cồ baớn
Z
X3
X4
X5

Haỡng
thổù

Z

0

1
2
3

X1

1
0
0
0

-2
1
0
1

Caùc hóỷ sọỳ cuớa
X2
X3
-3
0
1
2

X4

0
1
0
0







X5

0
0
1
0

Sọỳ chuớ chọỳt

Phỏửn phaới cuớa
phổồng trỗnh

0
0
0
1

0
4
3
8

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):
3
4
8
Lỏỳy = 3 (min)
;
=4
;
=4
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.
0
0

0
3

]

]

[
1
0
1
0
0
Haỡng 1
(giổợ y nguyón vỗ hóỷ sọỳ cuớa cọỹt chọỳt bũng 0)

4

]

[
-2
-3
0
0
Haỡng 2
(giổợ y nguyón vỗ õỏy laỡ haỡng chuớ chọỳt)

0

0

]

1

0
1

8
3
2

]
]
]

Haỡng 0

-

Haỡng 0 (mồùi)

Haỡng 3

Haỡng 3 (mồùi)

[
[
[

[
[
[

-2

0
-2

1
0
1

-3
1
0

2
1
0

0
0
0

0
0
0

0
1
3

0
1
-2


0

9

]

Haỡng chọỳt x (-3)

Haỡng chọỳt x (-2)

--------------------------------------------------------------------------------------------------------- 73

Chổồng 4: LặA CHOĩN PHặNG AẽN ệU Tặ


Giaùo trỗnh QUI HOACH THUY 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
cồ baớn
Z
X3
X4
X5

Haỡng
thổù


Z
1
0
0
0

0
1
2
3

X1
-2
0
1
1

Caùc hóỷ sọỳ cuớa
X2
0
1
0
0

X3
0
0
1
0


X4
3
1
0
-2

Phỏửn phaới cuớa
phổồng trỗnh

X5
0
0
0
1

9
3
4
2

Lỏỷp laỷi tióỳn trỗnh nhổ vỏỷy, ta seợ coù baớng kóỳt quaớ sau:
Lỏửn
thổớù
1

2

3


4

Bióỳn
cồ baớn

Z

X1

X2

X3

X4

X5

Z
X3
X4
X5

1
0
0
0

-2
1
0

1

-3
0
1
2

0
1
0
0

0
0
1
0

0
0
0
1

Z
X3
X4
X5

1
0
0

0

-2
0
1
1

0
1
0
0

0
0
1
0

3
1
0
-2

0
0
0
1

9
3
4

2

Z
X3
X4
X5

1
0
0
0

0
1
0
0

0
0
1
0

0
0
0
1

-1
-2
1

2

2
1
0
-1

13
2
3
2

Z
X3
X4
X5

1
0
0
0

0
1
0
0

0
0
1

0

(1/2)
1
- (1/2)
0

0
0
0
2

(3/2)
0
(1/2)
-1

14
4
2
2

Nghióỷm cuớa baỡi toaùn:

Caùc hóỷ sọỳ cuớa

Phỏửn phaới
cuớa phổồng
trỗnh


0
4
3
8

Z* = 14
X1* = 4
X2* = 2

===========================================================
--------------------------------------------------------------------------------------------------------- 74

Chổồng 4: LặA CHOĩN PHặNG AẽN ệU Tặ