Xem mẫu
- 2.Bài toán quy ho ch tuy n tính (QHTT)
Tình hu ng: M t công ty c n lên m t k ho ch qu ng cáo cho s n ph m c mình trên sóng
phát thanh và sóng truy n hình. Chi phí cho 1 phút qu ng cáo trên sóng phát thành là 80.000
ñ, trên sóng truy n hình là 400.000 ñ. ðài phát thanh ch nh n qu ng cáo các chương trình
dài ít nh t 5 phút. Còn ñài truy n hình ch nh n phát các chương trình t i ña 4 phút. Theo các
phân tích xã h i hoc, cùng m t th i lư ng 1 phút qu ng cáo trên truy n hình s có hi u qu
g p 6 l n trên sóng phát thanh. Công ty d ñ nh ch chi t i ña là 1.600.000 ñ cho qu ng cáo.
H i c n ñ t th i lư ng qu ng có trên sóng phát thanh và sóng truy n hình như th nào cho
ñ t hi u qu nh t?
Mô hình hóa: G i th i lư ng công ty ñ t qu ng cáo trên sóng phát thanh là a phút.
Trên sóng truy n hình là b phút . chi phí cho vi c này là 80.000*a + 400.000*b ≤ 1.600.000 ñ.
Trong ñó; a ≥ 5; b ≤ 4; a ≥ 0; b ≥ 0. Hi u qu chung c a qu ng cáo là a + 6.b
Bài toán: Xác ñinh a; b sao cho a + 6b Max
V i ñi u ki n : 80.000*a + 400.000*b ≤ 1.600.000 ñ.
a ≥ 5; b ≤ 4
và: a ≥ 0; b ≥ 0.
Bài toán có c u trúc như trên là m t ví d v bài toán QHTT.
Chú ý : do Maxf(x) = -Minf(x) nên t nay v sau ta ch nói t i bài toán tìm Minf(x)
2.1Các ñ nh nghĩa:
Bài toán: Xác ñ nh véc tơ x = ( x1; x2 ;...; xn ) sao cho
Trong ñó I1; I 2 ; I 3 là t p các ch s không giao nhau kí hi u i = I1 ∪ I 2 ∪ I 3 ; a ii ; b ii ; c j là các
h s ; xj j:=1,2,…,n là các bi n.
+Hàm f(x) g i là hàm m c tiêu
+H (1.1) ñ n (1.4) g i là h ràng bu c ( h ñi u ki n) c a bài toán .
V i m i ch s i ta có m t phương trình ho c b t phương trình tương ng và ñư c g i là ràng
bu c th i.Các h s v trái trong m i ràng bu c th i là m t véc tơ dòng
A * =(ai1; ai2;….;ain) . M t nhóm ràng bu c có h véc tơ Ai* ñ c l p tuy n tính ñư c g i là các
i
ràng bu c ñ c l p tuy n tính. xj ≥ 0; xj ≤ 0 g i là các ràng bu c v d u ñ i v i xj
+ Trong h t (1.1) ñ n (1.4) xét các ràng bu c không ph i là ràng bu c v d u các h s v
trái tương ng v i m i ràng bu c này là m t ma tr n, ký hi u là A. Ma tr n A có n c t, m i
c t này là m t véc tơ, ký hi u là Aj – chính là véc tơ các h s c a bi n xj Aj g i là véc tơ ñi u
ki n ng v i bi n xj
+ Phương án: m t véc tơ x th a mãn h ràng bu c c a bài toán g i là m t phương án c a bài
toán. Trong ràng bu c th i n u d u “=” x y ra thì ta nói phương án x th a mãn ch t ñ i v i
ràng bu c th i; còn n u x y ra d u ≤ ho c (≥ ) thì phương án x là l ng ñ i v i ràng bu c th i
+ Phương án t i ưu: là phương án mà hàm m c tiêu ñ t ñư c Min
+ Phương án t t hơn N u f(x1) ≤ f(x2) thì phương án x1 g i là t t hơn phương án x2
M t bài toán t n t i phương án t i ưu g i là bài toán gi i ñư c, n u không có phương
án t i ưu g i là bài toán không gi i ñư c.
- +Phương án c c biên: M t phương án th a mãn ch t n ràng bu c ñ c l p tuy n tính ñư c g i
là phương án c c biên (PACB)
* phương án c c biên th a mãn ch t ñúng n ràng bu c g i là phương án c c biên
không suy bi n, th a mãn ch t hơn n ràng bu c g i là phương án c c biên suy bi n.
Thí d 1: Cho
.f(x) = x1 + x2 – 2x3 + x4 + x5 Min
.x1 + x2 + x3 - x5 ≤ 40 (1)
.-2x1 – 2x2 + 5x3 + 2x5 = 65 (2)
.x2 + x3 +x4 + 2x5 ≥ 12 (3)
.xj ≥ 0 v i j:=1,2,..,5
A1* = (1;1;1;0;−1) 1 1 1 0 − 1
*
Ta có: A = (−2;−2;5;0;2) A1 = − 2 ; A2 = − 2 ; A3 = 5 ; A4 = 0 ; A5 = 2
2
0 1 1 1 2
*
A3 = (0;1;1;1;2)
1 1 1 0 − 1
− 2 − 2 5 0 2
Ma tr n A =
0 1 1 1 2
V i x1 = ( 0; 0; 13; 0; 0) ; x2 = ( 0; 0; 1; 0; 30) ñây là hai phương án c a bài toán.
Phương án x1 th a mãn ch t ñ i v i ràng bu c (2) và là l ng ñ i v i (1) và (3) và x3 ≥ 0
Phương án x2 th a mãn ch t ñ i v i (2) và l ng ñ i v i (1); (3) và x3 ≥ 0; x5 ≥ 0
Do f(x1) < f(x2) nên phương án x1 t t hơn th c s phương án x2
Thí d 2: f(x) = - x1 - 6x2 Min
80.000.x1 + 400.000x2 ≤ 1.600.000
.x1 ≥ 5; x2 ≤ 4
.x1 ≥ 0; x2 ≥ 0
Các phương án x1 = ( 5;3); x2 = ( 0;4); x3 = (20;0) là các phương án c c biên c a bài toán
N u t t c các phương án c c biên c a bài toán ñ u không suy bi n thì bài toán g i là
•
không suy bi n; trái l i, g i là bài toán suy bi n.
2.2.Các d ng ñ c bi t c a bài toán QHTT
a. D ng chính t c:
n
f ( x ) = ∑ c j x j ⇒ Min
j =1
n
∑a x i = 1,2,..., m
= bi
ij j
j =1
xj ≥ 0 j = 1,2,.., n
* Nh n xét : M i bài toán QHTT ñ u có th ñưa v bài toán QHTT d ng chính t c tương
ñương ( b ng cách thêm, b t m t lư ng không âm vào m i ràng bu c ñ có d u “ =” trong
- ràng bu c ñó). Khi y tr t i ưu c a hàm m c tiêu trong hai bài toán là trùng nhau, t phương
án, phương án t i ưu c a bài toán này suy ra phương án, phương án t i ưu c a bài toán kia.
Thí d 3: Bài toán thí d 1 tương ñương v i bài toán chính t c sau:
f(x) = - x1 - 6x2 Min
80.000.x1 + 400.000x2 + x3 = 1.600.000
.x1 - x4 =5
.x2 + x5 = 4
.xj ≥ 0; j =1,2,..,5
b.ð c ñi m c a phương án c c biên c a bài toán d ng chính t c
ð nh lý 1: Phương án x c a bài toán d ng chính t c là c c biên khi và ch khi h th ng các
véc tơ {Aj } tương ng v i các thành ph n dương c a phương án là ñ c l p tuy n tính.
( Hi n nhiên vì khi ñó h các ràng bu c là h Crame nên có nghiêm duy nh t, hay nghi m ñó
chính là m t phương án c c biên c a bài toán)
80.000 400.000 0
1
Trong thí d 3 phương án x = ( 5;3;0;0;1) có A1 = 1 ; A2 = 0 ; A5 = 0 là ba
0 1 1
véc tơ ñ c l p tuy n tính nên x1 là phương án c c biên.
c. Cơ s c a phương án c c biên: ( v i bài toán d ng chính t c)
M t h g m m véc tơ {Aj} ñ c l p tuy n tính bao hàm h th ng các véc tơ tương ng
v i các thành ph n dương c a phương án c c biên x là cơ s c a phương án c c biên y, ký
hi u m t cách quy ư c là j, trong ñó J = {J: Aj thu c cơ s }
+ V i phương án x = (x1;x2;,…,xn) g i thành ph n xj ( j ∈ J ) là thành ph n cơ s ; xk
( k ∉ J ) là thành ph n phi cơ s .D nh n th y các thành ph n phi cơ s c a phương án c c
biên luôn b ng 0. M t phương án c c biên không suy bi n thì m i thành ph n cơ s ñ u
dương, còn phương án c c biên suy bi n thì có ít nh t m t thành ph n cơ s b ng 0
trên phương án x1 là phương án c c biên (PACB) không suy bi n
Trong thí d 3
d. Bài toán d ng chu n:
N u bài toán dang chính t c trong ñó bi ≥ 0 v i m i i:=1,2,…,m và m i phương trình
trong h ràng bu c ñ u có m t bi n s v i h s b ng 1 ñ ng th i bi n này khôn gcos trong
các phương trình khác g i là bài toán có d ng chu n.
2.3. Các tính ch t c a bài toán QHTT
Tính ch t 1: N u bài toán có phương án và h ng c a ma trân h ràng bu c b ng n ( n là s
bi n s ) thì bài toán có phương án c c biên.
Thí d 1: Cho bài toán QHTT:
.f(x) = 3x1 + x2 + 2x3 + 6x4 Min
-3x1 + 2x2 + 5x3 – x4 ≥ -16
3x2 + 2x3 + 7x4 =0
.x1 – 4x2 + 3x4 – x5 ≤ 34
2x1 - 6x3 + 2x4 ≥ -2
- .x1 ≥0
.x2 ≥0
.x3 ≥0
.x4 ≥0
.x5 ≥ 0
Ch ng t r ng bài toán có PACB.
Gi i: D th y h ng c a ma trân h ràng bu c b ng 5, thêm n a x = ( 0; 0;0;0;0) là m t
phương án v y theo tính ch t 1 suy ra bài toán có PACB.
Tính ch t 2: N u bài toán có phương án và tr s c a hàm m c tiêu b ch n dư i khi f(x)
Min trên t p phương án thì bài toán có phương án t i ưu.
Thí du 2. Ch ng t bài toán trong thí d 1 có PACB t i ưu.
Gi i: theo thí d 1 ta ñã ch ng t bài toán có PACB thêm n a do ràng bu c v d u ta suy ra
f(x) ≥ 0 trên tâp phương án. V y theo tính ch t 2 ch ng t bài toán có PACB t i ưu.
Tính ch t 3: S phương án c c biên c a bài toán QHTT là h u h n.
3. Phương pháp ñơn hình gi i bài toán QHTT
3.1.N i dung c a phương pháp.
Xu t phát t m t PACB, ta tìm cách ñánh giá PACB ñó, n u nó chưa t i ưu thì tìm
cách di chuy n sang m t phương án c c biên m i t t hơn, quá trình này ñư c ti p t c l p. Vì
s phương án c c biên là h u h n, nên sau m t s h u h n bư c l p, ho c ta tìm ñư c phương
án c c biên t i ưu, ho c là ta k t lu n bài toán không gi i ñư c vì hàm m c tiêu khôn gbij
ch n. ðó là n i dung cơ b n c a phương pháp ñơn hình.
3.2. ð c ñi m c a phương án c c biên c a bài toán d ng chính t c.
a. Quan h gi a phương án c c biên và phương án c a bài toán:
Xét bài toán d ng chính t c
n
f ( x) = ∑ c j x j ⇒ Min
j =1
n
∑a x i := 1,.., m
= bi
ij j
j =1
xj ≥ 0 j := 1,2,..., n
Và cho x0 là PACB v i cơ s J0 Ta ký hi u véc tơ g m các thành ph n cơ s c a PACB x0 là
X j 0 (vi t theo c t) và ma trân các véc tơ cơ s là Aj 0 = [ Aj : j ∈ J 0 ] khi ñó
x0 = 0 (∀k ∉ J 0 ) Do ñó : Aj0 X j0 = b → X j0 = A−01b
k
j
Các véc tơ phi cơ s Ak v i k ∉ J 0 cũng phân tích ñư c qua cơ s J0 G i các h s phân tích
∑x
c a Ak là xjk véc tơ h s phân tích tương ng là Xk như v y: Ak = Aj = AJ 0 X k
jk
j∈J 0
do ñó Xk = AJ−01 Ak .
- ∑c x
Ư c lư ng c a bi n xk theo cơ s J0 ký hi u và ñư c xác ñ nh b i: ∆ k = v i:
− ck
j jk
j∈ J 0
cj = {c j : j ∈ J 0 }
V i nh ng xj ( j ∈ J 0 ) thì ư c lư ng c a nó ∆ j = 0
ð i v i cơ s J0 n u phương án ñang xét không là PACB t i ưu thì b ng phép ñ i cơ s ta s
ñi t i m t phương án x biên t t hơn.
3.3.D u hi u t i ưu và các ñ nh lý cơ b n.
ð nh lý 2: D u hi u t i ưu c a phương án c c biên
N u ñ i v i PACB x0 v i cơ s J0 c a bài toán d ng chính t c mà:
Min thì x0 là phương án t i ưu.
∆ k ≤ 0 (∀k ∉ J 0 ) v i bài toán f(x)
Chú ý : ð nh lý 2 là ñi u ki n ñ , tuy nhiên n u x0 là PACB không suy bi n thì ñó cũng là
ñi u ki n c n ñ x0 là phương án t i ưu.
ð nh lý 3: D u hi u bài toán không gi i ñư c
N u ñ i v i phương án c c biên x0 v i cơ s J0 c a bài toán d ng chính t c mà:
T n t i ∆ k > 0 mà x jk ≤ 0 ∀k ∉ J 0 v i bài toán f(x) Min Thì bài toán không gi i
ñư c ( Hàm m c tiêu không b ch n dư i)
ð nh lý 4: D u hi u ñi u ch nh phương án c c biên.
N u ñ i v i m t phương án c c biên x0 v i cơc s J0 c a bài toán d ng chính t c mà :
v i m i ∆ k > 0 ñ u t n t i xjk > 0 v i bài toán f(x) Min thì ta có th ñi u ch nh phương án
0
c c biên x chuy n sang m t phương án c c biên t t hơn.
3.4.Công th c ñ i cơ s :
Trong không gian Rn cho véc tơ x0 cho hai cơ s
r r r
α 1; α 2;….; α n (1) β 1; β 2;….; β n (2)
n n
x 0 = ∑ xiα i x0 = ∑ y j β j
Gi s Tìm m i liên h gi a các t a ñ xj ; yj
i =1 j =1
n
G i T = (tij) là ma tr n chuy n t cơ s (1) sang cơ s (2) khi y β j = ∑ tijα i j = 1,2,.., n
i =1
n n n n n n n
Do ñó x 0 = ∑ xiα i = ∑ y j β j = ∑ y j ∑ tijα i = ∑ (∑ tij y j )α i V y: xi = ∑ tij y j
i =1 j =1 j =1 i =1 i =1 j =1 j =1
3.4.Thu t toán c a phương pháp ñơn hình:
Gi s bài toán ph i gi i là bài toán QHTT d ng chính t c, ñã bi t m t phương án c c biên
x0 và cơ s J0 . không m t tính t ng quát ta gi s J0 g m m véc tơ ñ u tiên, t là cơ s g m m
véc tơ A1,A2,…..,Am.
- Bư c 1: L p b ng ñơn hình ng v i phương án c c biên x0
H Cơ Phương .c1 c2………cr………..cm cm+1 cm+2 … ..ck……..cs……....cn
S S án .x1 x2………xr…….xm xm+1 xm+2…….xk……..xs………xn
cj J0
.c1 .x1 1 0 …… 0……..0 x1m+1 x1m+2……x1k…….x1s……..x1n
x10
.c2 .x2 0 1………..0……..0 x2m+1 x2m+2……x2k…….x2s……..x2n
0
x2
… … …. ……………… …… ..…………………………….
. cr .xr 0 0………..1……..0 xrm+1 xrm+2……xrk……..xrs……...xrn
x r0
… … …. ………………………… ……………………………………….
.cm .xm 0 0………..0…… 1 xmm+1 xmm+2 …….xmk…….xms……..xmn
0
x m
.f(x) .f(x0) 0 0 ……….0……...0 ∆ m +1 ∆m+2 ∆k ∆s ∆n
- Dòng cj là các h s c a các bi n trong hàm m c tiêu f(x)
- C t cj là h s c a bi n xj ng v i véc tơ cơ s Ajx
∑c x
- − ck thí d ∆ s = (c1.x1s + c2 x2 s + ... + cr xrs + ... + cm xms ) − cs
∆k = j jk
j∈ J 0
Bư c 2: Ki m tra d u hi u t i ưu c a PACB
Min thì x0 là phương án t i ưu
- N u ∆k ≤ 0 ∀k ∉ J 0 v i bài toán f(x)
N u ∃∆ k > 0 thì x0 không là phương án t i ưu, chuy n sang bư c 3
-
Bư c 3: ki m tra tính không gi i ñư c c a bài toán.
- N u ∃∆ k > 0 mà xjk ≤ 0 v i m i j ∈ J 0 v i bài toán f(x) min thì bài toán không gi i
ñư c vì hàm m c tiêu có tr không b ch n dư i
- N u v i m i ∆ k > 0 ñ u có ít nh t xjk > 0 thì chuy n sang bư c 4
Bư c 4: ði u ch nh PACB và l p b ng ñơn hình m i.
- Ch n phương án ñưa vào cơ s : Tìm max ∆ k ∀∆ k > 0 gi s max ∆ k = ∆ s thì véc tơ As
ñư c ñưa vào cơ s
x0 x0 x0
- Tìm Min v i m i xjs > 0 ; j ∈ J 0 gi i s Min j = r khi y véc tơ Ar b lo i kh i
j
x js x js xrs
cơ s . ph n t xrs g i là ph n t tr c và ñư c ñóng khung trong b ng
- Bi n ñ i b ng:
+ L p b ng ñơn hình m i. thay véc tơ cơ s v a l a chon trên cs thay cho cr trong c t cj
.xs thay cho xr trong c t cơ s
+ Tính các dòng m i ( b t ñ u t c t th 3 tr ñi)
ð tính dòng ng v i dòng có véc tơ .xs m i ñưa vào trong b ng m i ta l y dòng ng
v i véc tơ l y ra xr trong b ng cũ chia cho ph n t tr c. Dòng này g i là dòng chu n.
- ð tính dòng xj trong b ng m i ta l y dòng xj trong b ng cũ tr ñi dòng chu n sau khi ñã
nhân dòng nó ( dòng chu n) v i xjs
ð tính dòng cu i c a b ng m i, ta l y dòng cu i c a b ng cũ tr ñi dòng chu n sau khi
nhân nó (dòng chu n) v i ∆ s
Ti n trình trên ñư c l p l i sau h u h n bư c ta có k t lu n v l i gi i c a bài toán ñang
xét.
Thí d 1: Gi i bài toán QHTT sau:
⇒ min
f ( x) = 4.x1 − 2.x2 + x3 − 3 x4
+ x3 + x4 + 3 x5 = 16
x1
2 x1 − 3 x2 − 2 x3 + 2 x5 + x6 = 52
− 2 x5 = 24
x2 + x3 + x7
x j ≥ 0, j = 1,2,3,...,7
Bài toán ñã cho có d ng chu n, các bi n cô l p là x4;x6;x7 nên phương án c c biên là
x0=(0;0;0;16;0;52;24) cơ s J0 là A4; A6; A7 ta l p ngay ñư c b ng ñơn hình sau
B ng ñơn hình
x0 0 0 0 16 0 52 24
x0'
4 -2 1 -3 0 0 0
Cj J Xj x1 x2 x3 x4 x5 x6 x7
-3 x4 16 1 0 1 1 3 0 0
0 x6 52 2 -3 -2 0 2 1 0
0 x7 24 0 [1] 1 0 -2 0 1
f(x) -48 -7 2 -4 0 -9 0 0
-3 x4 16 1 0 1 1 3 0 0
0 x6 52 2 0 1 0 -4 1 3
-2 x2 24 0 1 1 0 -2 0 1
f(x) -96 -7 0 -6 0 -5 0 -2
Phương án m i .x1= (0; 24; 0; 16; 0; 52)
Sau khi k t thúc b ng 1 t dòng cu i ta th y phương án x0 chưa t i ưu do có ∆2 > 0 véc tơ A2
ñư c ñưa vào cơ s
x7
Thêm n a Min{ } =24/1 nên véc tơ A7 ñư c ñưa ra kh i cơ s ph n t tr c là [1] trong
x72
b ng 1
Note: Th c ch t trong b ng 1 các c t xj là t a ñ c a véc tơ Aj ñ i v i cơ s chính t c khi
chuy n sang b ng 2 ta ñã ñ i cơ s {A4;A6;A2} trong b ng 2 các c t xj là t a ñ c a véc tơ Aj
qua cơ s m i. Do ñó mu n tìm t a ñ c a các Aj qua cơ s m i ta ch vi c.Tìm ma tr n
chuy n t cơ s m i sang cơ s chính t c ( bi u th tuy n tính các véc tơ chính t c qua cơ s
m i r i l y ma tr n chuy n v c a ma trân các h s trong s bi u th trên), g i nó là ma trân
T=(tij) ; khi y T.Aj =A’j trong ñó A’j là t a ñ c a Aj ñ i v i cơ s m i.
T b ng 2 ta th y ∆k
- .f(x) = 2x1-3x2-x3 Min
2x1 – x2 + x3 ≤ 18
3x1 + x2 -2x3 ≤ 20
.x1 +2x2 ≤ 12
.x1≥ 0; .x2 ≥ 0; x3 ≥ 0
f ( x) = 2 x1 − 3 x2 − x3 ⇒ Min
Ta ñưa v bài toán chính t c sau:
2 x1 − x2 + x3 + x4 = 18
3 x1 + x2 − 2 x3 + x5 = 20
x1 + 2 x2 + x6 = 12
x j ≥ 0 ∀j : 1,2,...,6
Bài toán có d ng chu n, các bi n cô l p x4; x5; x6 nên phương án c c biên
x0 = ( 0;0;0;18;20;12) cơ s J0={A4;A5;A6}
B ng ñơn hình
H I J K L M N O P
x0 0 0 0 18 20 12
26 2 -3 -1 0 0 0
27 Cj J Xj x1 x2 x3 x4 x5 x6
28 0 x4 18 2 -1 1 1 0 0
29 0 x5 20 3 1 -2 0 1 0
30 0 x6 12 1 [2] 0 0 0 1
31 f(x) 0 -2 3 1 0 0 0
32 0 x4 18 2.5 0 [1] 1 0 0.5
33 0 x5 20 2.5 0 -2 0 1 -0.5
34 -3 x2 -18 0.5 1 0 0 0 0.5
35 f(x) -18 -3.5 0 1 0 0 -1.5
36 -1 x3 24 2.5 0 1 1 0 0.5
37 0 x5 62 7.5 0 0 2 1 0.5
38 -3 x2 6 0.5 1 0 0 0 0.5
39 f(x) -42 -6 0 0 -1 0 -2
Phương án x2 =( 0;6;24;0;62;0) là phương án t i ưu duy nh t.
Trên b ng tính Excel: dòng 34(dòng chu n) t c t K tr ñi ñư c thi t l p nh công th c
K34= K30/$L$30 rê chu t tuy n tính theo dòng K34 ta có k t qu L34;M34:…P34.
Dòng 32 :K32 = K28 –K34*$L$28 rê chu t như trên ñ có các k t qu c a các c t cùng dòng
Dòng 33 Tương t như trên
Dòng 35: K35 = K31-K34*$L$31
ð tính x2;x3;x5 ph i gi i h phương trình tương ng h ràng bu c ( các bi n khác ñ u
b ng 0)
3.5.Các chú ý khi áp d ng thu t toán:
+ khi c n gi i bài toán f(x) Max thì ta gi i bài toán –f(x) Min
+ n u khi chon vecto ñưa vào cơ s ho c ñưa ra kh i cơ s có nhi u véc tơ thu c di n l a
ch n thì tùy ch n m t trong s ñó
- x0
+Trư ng h p bài toán suy bi n có th d n t i min j
= 0 v i m i xjs > 0 ; j ∈ J 0 v n th c hi n
x js
thu t toán m t cách bình thư ng
+ Khi áp d ng thu t toán c n lưu ý:
Phương án x0 có cơ sơt J0 là cơ s ñơn v ( còn g i là cơ s chính t c), ma tr n
i)
các h s v trái trong h ràng bu c có các c t tương ng là t a ñ c a vecto
Aj theo cơ s ñó. Ta l p ngay ñư c b ng ñơn hình. ðây là bài toán d ng chu n
ii) Khi J0 không ph i là cơ s chính t c ta ph i tìm ma tr n các h s trong h ràng
bu c phân tích qua cơ s chính t c J0 b ng cách bi n ñ i các dòng c a ma tr n
b sung c a h ràng bu c làm xu t hi n cơ s J0.
4. Phương pháp tìm phương án c c biên:
Có nh ng bài toán có d ng chính t c, nhưng không ph i d ng chu n, ñ ng th i ta chưa
bi t PACB, do ñó mu n áp d ng thu n toán ñơn hình ta ph i tìm ñư c m t PACB c a nó.
Xét bài toán d ng chính t c:
n
f ( x) = ∑ c j x j ⇒ Min
j =1
n
∑a x i := 1,.., m (I)
= bi
ij j
j =1
xj ≥ 0 j := 1,2,..., n
Không m t tính t ng quát gi s bi ≥ 0 m i i = 1,2,…,m.(n u bi 0 Khi ñó bài toán (I) không có phương án.
ii) n u Pmin = 0 khi ñó x là phương án c biên c a bài toán (I). ð áp d ng thu t toán cho bài
toán (I) ta c n bi t cơ s J0 c a nó. Có hai trư ng h p sau:
a).Trong cơ s c a phương án c c biên ( x ; x g = 0) không có các vectơ tương ng v i
các bi n gi , khi ñó cơ s này cũng là cơ s c a phương án c c biên x . Ti n hành thu t toán
bình thư ng.
- b). Trong cơ s c a phương án c c biên ( x ; x g = 0) có ít nh t m t vectơ tương ng v i
các bi n gi , lúc này PACB là suy bi n. ð ti p t c gi i bài toán (I) ta lo i các c t ng v i
∆ j ( P) < 0 và các c t xig phi cơ s ra kh i b ng, sau ñó tính l i các ư c lư ng ∆k theo hàm f
và ti p t c thu t toán.
Chú ý: - Khi xây d ng bài toán ph ta ch c ng thêm bi n gi vào nh ng phương trình ràng
bu c c n thi t ñ t o ra cơ s ñơn v trong ma tr n ñi u ki n.
- N u trong quá trình gi i bài toán P, m t bư c ñi u ch nh nào ñó mà t t c các bi n
gi ñ u b lo i ra kh i cơ s thì k t thúc vi c gi i bài toán ph P ( vì PACB bài toán (I) ñã tìm
ñư c). Ti p t c gi i bài toán (I) v i PACB v a có.
Thí d 1: Gi i bài toán sau b ng phương pháp ñơn hình:
.f(x) = 3x1 +4x2 +2x3 + 2x4 Min
2x1 + 2x2 + x4 = 28
.x1 +5x2 + 3x3 – 2x4 ≤ 31
2x1 – 2x2 +2x3 + x4 = 16
.xj ≥ 0 ( j=1,..,4)
Gi i: ðưa bài toán ñã cho v d ng chính t c: .
f(x) = 3x1 +4x2 +2x3 + 2x4 Min
2x1 + 2x2 + x4 = 28
.x1 +5x2 + 3x3 – 2x4 + x5 = 31
2x1 – 2x2 +2x3 + x4 = 16
.xj ≥ 0 ( j=1,..,5)
Bài toán không có d ng chu n nên ta ñưa ra bài toán ph (P)
P(x,xg) = xg1 + xg3 Min
+ xg1
2x1 + 2x2 + x4 = 28
.x1 +5x2 + 3x3 – 2x4 + x5 = 31
xg3
2x1 – 2x2 +2x3 + x4 = 16
.xj ≥ 0 ( j=1,..,5) xg1≥ 0; xg2 ≥ 0
B ng ñơn hình hai pha
- H I J K L M N O P Q
46 f 3 4 2 2 0
47 P 0 0 0 0 0 1 1
48 Cj J Xj x1 x2 x3 x4 x5 xg1 xg3
49 1 xg1 28 2 2 0 1 0 1 0
50 0 x5 31 1 5 3 -2 1 0 0
51 1 xg3 16 [2] -2 2 1 0 0 1
52 P 44 4 0 2 2 0 0 0
53 1 xg1 12 0 [4] -2 0 0 1
54 0 x5 23 0 6 2 -2.5 1 0
55 0 x1 8 1 -1 1 0.5 0 0
56 P 12 0 4 -2 0 0 0
57 4 x2 3 0 1 -0.5 0 0
58 0 x5 5 0 0 5 -2.5 1
59 3 x1 11 1 0 0.5 0.5 0
60 f 45 0 0 -2.5 -0.5 0
M t bi n gi b lo i kh i cơ s ta b qua nó b ng ñơn hình ti p theo.
Dòng 60 do không còn ph thu c bi n gi ta tính ∆k theo hàm f
( ch ng h n K60 = ($h$57*k57+$h$58*k58+$h$59*k59)-k46) tương t cho các c t còn l i
c a dòng 60.
- CHƯƠNG VI: BÀI TOÁN ð I NG U (3)
Trong th c t có nh ng c p bài toán QHTT có m i quan h m t thi t v i nhau, do v y
t các k t qu nghiên c u ñư c c a bài toán này có th suy ra các k t qu tương ng c a bài
toán kia và ngư c l i. ngư i ta g i c c c p bài toán như th là c p các bài toán ñ i ng u nhau.
ð c bi t các c p bài toán ñ i ng u có n i dung th c t , vi c phân tích m i quan h gi a bài
toán ban ñ u và bài toán ñ i ng u còn ñem l i nh ng thông tin có ý nghĩa lý lu n và th c
hành.
1.Cách thành l p bài toán ñ i ng u:
Bài toán ban ñ u Bài toán ñ i ng u
~
n m
f ( x) = ∑ c j x j ⇒ Min( Max) f ( y ) = ∑ bi yi ⇒ Max( Min)
j =1 i =1
.yi không có ràng bu c v d u
n
∑a x = bi i ∈ I1
ij j
i =1
n
∑a x ≥ (≤)bi i ∈ I2 yi ≥ 0 i ∈ I2
ij j
i =1
n
∑a x ≤ (≥)bi i ∈ I3 yi ≤ 0 i ∈ I3
ij j
i =1
m
∑a
.xj không ràng bu c v d u j ∈ J1 yi = c j j ∈ J1
ij
i =1
m
xj ≥ 0 j ∈ J2
∑a yi ≤ (≥)c j j ∈ J2
ij
i =1
xj ≤ 0 m
j ∈ J3
∑a yi ≥ (≤)c j j ∈ J3
ij
i =1
Thí d 1: Vi t bài toán ñ i ng u c a bài toán sau và ch ra các c p ràng bu c ñ i ng u:
.f(x) = -4x1 + x2 + 5x3 + 3x5 Min
3x1 – 6x2 – x3 + 2x4 – 4x5 ≥ -15 (1)
-2x1 +3x2 +4x3 +5x4 – x5 ≤8 (2)
-6x2 + 3x3 +8x4 - 4x5 =9
3x1+2x2 -3x4 + x5 ≥ 24 (3)
.x1 ≥ 0 (4); x3 ≤ 0 (5) x5 ≥ 0 (6)
Gi i: Bài toán ñ i ng u:
- ~
f ( y ) = −15 y1 + 8 y2 + 9 y3 + 24 y4 ⇒ Max
3 y1 − 2 y2 + 3 y 4 ≤ −4 (7 )
− 6 y1 + 3 y2 − 6 y3 + 2 y4 = 1
− y1 + 4 y2 + 3 y3 ≥ 5 (8)
2 y1 + 5 y2 + 8 y3 − 3 y4 = 0
− 4 y1 − y2 − 4 y3 + y4 ≤ 3 (9)
≤0 (10)
− y1
≤0 (11)
y2
y4 ≥ 0 (12)
Các c p ràng bu c ñ i ng u là: (1-10);(2-11); (3-12);(4-7);(5-8);(6-9)
Thí d 2: Vi t bài toán ñ i ng u c a bài toán sau:
.f(x) = -3x1 +5 x2 + 4x3 -2x4 + x5 Max
2x1 – 3x2 – x3 + 6x4 – 2x5 +2x6 = -14
-x1 + 2x2 + 5x3 + 3x5 – 4x6 = 8
6x1- 3x2 + 2x3 - x4 + x5 + 3x6 = 12
3x1+2x2 -3x4 + x5 ≥ 24
.xj ≥ 0 j=1,2,…,6
2. Các tính ch t và ñ nh lý ñ i ng u:
2.1.Xét c p bài toán ñ i ng u v i các hàm m c tiêu:
~
f ( x ) ⇒ Min( Max) f ( y ) ⇒ Max( Min)
Tính ch t 1: V i m i c p phương án x và y c a hai bài toán ñ i ng u ta luôn có
~
f ( x ) ≤ (≥ ) f ( y )
Tính ch t 2: N u ñ i v i hai phương án x* và y* c a m t c p bài toán ñ i ng u mà:
~
f ( x* ) = f ( y * )thì x*và y * tương ng là hai phương án t i ưu.
ð nh lý 1: N u m t trong hai bài toán ñ i ng u mà gi i ñư c thì bài toán kia cũng gi i ñư c
~
và khi ñó v i m i phương án t i ưu x* , y* ta luôn có: f ( x* ) = f ( y* )
H qu 1: ði u ki n c n và ñ ñ hai bài toán ñ i ng u gi i ñư c là m i bài toán có ít nh t
m t phương án.
H qu 2: ði u ki n c n và ñ ñ m t bài toán có phương án còn m t bài toán không có
phương án là tr s c a hàm m c tiêu c a bài toán có phương án không b ch n trên t p các
phương án c a nó.
ð nh ly 2: ði u ki n c n và ñ ñ hai phương án x và y c a m t c p bài toán ñ i ng u t i ưu
là trong các c p ràng bu c ñ i ng u n u m t ràng bu c th a mãn v i d u b t ñ ng th c th c
s (l ng) thì ràng bu c kia ph i th a mãn v i d u b ng (ch t)
H qu 1: N u m t ràng bu c là l ng v i m t phương án t i ưu c a bài toán này thì ràng
bu c ñ i ng u c a nó ph i là ch t ñ i v i phương án t i ưu c a bài toán kia.
2.2. M t s ng d ng c a tính ch t và các ñ nh lý ñ i ng u:
- a) Kh o sát s t n t i phương án, phương án t i ưu:
Thí d 1: Cho bài toán QHTT
.f(x) = 2x1 – x2 + 3x3 – 2x4 Min
.x1 – x2 = 15
.x3 – x4 =8
.xj ≥ 0 m i j=1,2,3,4
Hãy vi t bài toán ñ i ng u và ch ng t nó có phương án t i ưu.
Gi i: Bài toán ñ i ng u:
~
f ( y ) = 15 y1 + 8 y2 ⇒ Max
≤2
y1
≤ −1
− y1
≤3
y3
− y 4 ≤ −2
Ta nh n th y x* = ( 15;0;8;0) là m t phương án c a bài toán g c
.y* = ( 1;2 ) là m t phương án c a bài toán ñ i ng u . V y theo h qu 1 ñ nh lý 1 suy ra hai
bài toán này là gi i ñư c, hay c p bài toán có phương án t i ưu. Thêm n a h ng c a ma tr n
h ràng bu c trong bài toán ñ i ng u b ng 2 nên nó có PACB t i ưu.
Thí d 2: Cho bài toán QHTT
.f(x) = x1 +2x2 + px3 – 2x4 + x5 Max
2x1 – x2 + x4 – x5 ≥ 4p +1
. x2 - x3 + 2x4 – x5 ≤ 32
.x1 - x2 + x3 + x5 = 18
.x3 ≥ 0; x4 ≥ 0 v i p là tham s .
Hãy vi t bài toán ñ i ng u và d a vào bài toán này ñ bi n lu n theo tham s p v s t n t i
phương án t i ưu c a bài toán g c.
Gi i: Bài toán ñ i ng u:
~
f ( y ) = (4 p + 1) y1 + 32 y2 + 18 y3 ⇒ Min
2 y1 + y3 = 1 (1)
− y1 + y2 − y3 = 2 (2)
(3)
− y2 + y3 ≥p
y1 + 2 y2 ≥ −2 (4)
− y1 − y2 + y3 = 1 (5)
y1 ≤ 0; (6) y2 ≥ 0 (7 )
H phương trình t o b i các ràng bu c (1-2-5) cho ta h phương trình có nghi m duy nh t
.y0 =( 0;3;1) nghi m này th a mãn các ràng bu c (4-6-7 ) cho nên nó tr thành m t phương án
duy nh t n u th a mãn ràng bu c (3) và ta có ñó là phương án t i ưu.
Thay vào (3) suy ra : p ≤ -2
- b)Phân tích tính ch t t i ưu c a m t phương án và xác ñ nh t p phương án t i ưu:
Gi s v i m t phương án x c a bài toán g c, ta c n phân tích xem ñó có ph i là phương án
t i ưu không? Gi s x là phương án t i ưu. v y theo ñ nh lý 2 (ñ i ng u) m i phương án t i
ưu y c a bài toán ñ i ng u ph i th a mãn ch t các ràng bu c ñ i ng u v i các ràng bu c l ng
c a phương án x bài toán g c. T p h p các ràng bu c ch t này t o thành m t h phương
trình ñ i v i y. gi i h này, n u h vô nghi m thì x không th là phương án t i ưu. N u h có
nghi m thì ph i th các nghi m này vào các ràng bu c còn l i c a bài toán ñ i ng u, n u m i
nghi m ñ u không ph i là phương án thì x không là phương án t i ưu. N u có m t nghiêm y
c a h là phương án c a bài toán ñ i ng u thì x là phương án t i ưu, ñ ng th i phương án y
cũng t i ưu.
Thí du 3: Cho bài toán: f(x) = 7x1 + 6x2 – 12x3 + x4 Max.
2x1 – 2x2 - 3x3 +2x4 = 8 (1)
3x2 + 2x3 – 2x4 ≤ -1 (2)
2x1 - 3x3 + x4 = 10 (3)
.x1 ≥ 0 j=1,2,3,4 (4)
Và vecto x = ( 0;6;0;10) Vi t bài toán ñ i ng u. phân tích các tính ch t c a x0 ñ i v i bài
0
toán ñã cho. Xác ñ nh t p phương án t i ưu c a bài toán. Ch ra m t phương án t i ưu không
c c biên c bài toán g c.
Gi i: Bài toán ñ i ng u
~
f ( y ) = 8 y1 − y2 + 10 y3 ⇒ Min
2 y1 + 2 y3 ≥ 7 (5)
− 2 y1 + 3 y2 ≥ 6 (6)
− 3 y1 + 2 y2 − 3 y3 ≥ −12 (7 )
2 y1 − 2 y2 + y3 ≥ 1 (8)
y2 ≥ 0 (9)
.x0 th a mãn các ràng bu c c a bài toán g c, nên nó là m t phương án, thêm n a x0 th a mãn
ch t các rang bu c(1-3) và hai ràng bu c d u ( x1=0; x3 = 0) , x0 th a mãn ch t 4 ràng bu c và
nh ng ràng bu c này ñ c l p tuy n tính nên x0 là PACB không suy bi n. phương án x0 th a
mãn lòng ràng bu c (2) và hai ràng bu c d u ( x2; x4). Gi s x0 là phương án t i ưu theo ñ nh
lý 2 m i phương án t i ưu c a bài toán ñ i ng u ph i th o mãn: (chú ý: các c p ràng bu c ñ i
ng u là (2-9);(d u x2--6) ;( d u x4- 8))
-2y1 + 3y2 =0
2y1 - 2y2 + y3 = 0
.y2 = 0
h có nghi m duy nh t y0 = ( -3;0;7) th y0 vào ràng bu c (5-7) ta th y nó th a mãn, y0 là
phương án suy ra x0 là phương án t i ưu ñ ng th i y0 là phương án t i ưu và hơn n a là
phương án t i ưu duy nh t.
Phương án y0 ch th a mãn l ng ràng bu c 5 nên m i phương án t i ưu x ph i th a
mãn
- =0
x1
− 2 x1 − 3 x2 + 2 x3 = 8
gán cho x4 tham s và gi i h có
− 3 x3 + x4 = 10
1 10 1
.x = (0;1 + ; x4 ) Th x vào ràng bu c (2) còn l i:
;− +
2 x4 3 3 x4
3x2 +2x3 -2x4 ≤ -1 suy ra 3 +3/2.x4 -20/3 +2/3.x4 -2x4 ≤ -1 hay x4 ≤ 16
Thêm n a x2 = 1 +1/2.x4 ≥ 0 suy ra x4 ≥ -2; x3 = -10/3 +1/3.x4 ≥ 0 suy ra x4 ≥ 10
Tóm l i : 10 ≤ x4 ≤ 16. V i ñi u ki n này x là phương án ñ ng th i là phương án t i ưu c a
bài toán g c.
M t phương án t i ưu không c c biên c a bài toán g c là PACB mà các véc tơ c t trong h
ràng bu c tương ng v i các thành ph n dương c a phương án không ñ c l p tuy n tính.
ch ng h n; x = (0;15/2;1;13)
.x4 = 0;16 có hai PACB t i ưu tương ng
- CHƯƠNG VII: BÀI TOÁN V N T I (9+2+1)
1.N i dung và các ñ c ñi m:
1.1.N i dung kinh t và d ng toán h c:
a)Bài toán: Gi s ta c n v n chuy n m t lo i hàng hóa thu n nh t t m ñ a ñi m nào ñó
t i n v trí khác nhau có nhu c u v lo i hàng hóa ñó ( ta hi u hàng hóa ñây có th là các
d ng v t ch t thông thư ng, cũng có th là lo i ñ c thù như v n, lao ñ ng, thông tin,…). Ta
ký hi u nơi cung c p hàng là Ai ( i=1,2,…,m) và g i chúng là các tr m phát, n nơi có nhu c u
là Bj j=1,2,…,n và g i chúng là các tr m thu. Lư ng hàng hóa cung ng tr m phát Ai là ai
ñơn v , lư ng hàng hóa yêu c u tr m thu Bj là bj ñơn v . Gi s chi phí v n chuy n m t ñơn
v hàng hóa t tr m phát Ai t i tr m thu Bj là cij ≥ 0 ( khái ni m chi phí hi u theo nghĩa r ng
có th là chi phí th c, có th là ñ dài quãng ñư ng t Ai ñ n Bj , ho c s hao phí nhiên li u,
ho c th i gian c n thi t ñ v n chuy n,…. Bài toán ñ t ra là tìm phương án th c hi n vi c v n
chuy n hàng hóa nói trên sao cho chi phí là nh nh t.
G i xij là lư ng hàng hóa chuy n t tr m phát Ai ñ n tr m thu Bj ( xij ≥ 0). Yêu c u
m
∑x
c a tr m thu ñ u th a mãn ñ y ñ nghĩa là j = 1,2,.., n ; hàng hóa t t c các
= bj
ij
i =1
tr m phát ñ u ñư c s d ng h t ñ ñáp ng yêu c u c a các tr m thu nên
n m n
∑ xij = ai i = 1,2,.., m . Khi ñó t ng chi phí v n chuy n s là : ∑∑ cij xij Bài toán có mô
j =1 i =1 j =1
hình như sau g i là bài toán v n t i:
Tìm h th ng {xij} ( i=1,2,..,m; j=1,2,…,n) sao cho:
m n
f ( x) = ∑ ∑ cij xij ⇒ Min (1)
i =1 j =1
n
∑x i = 1,2,.., m (2)
= ai
ij
j =1
m
∑x (3)
j = 1,2,.., n
= bj
ij
i =1
.xij ≥ 0 m i i;j (4)
n m
∑b = ∑ ai
N u: Ta có bài toán cân b ng thu phát (bài toán có d ng chính t c)
j
j =1 i =1
n n
m
> ∑ b j Thì (2) thay b i: ∑x
∑ ai i = 1,2,.., m
Nu ≤ ai
ij
j =1 j =1
i =1
n
m m
< ∑ b j Thì (3) thay b i
∑ ai ∑x
Nu j = 1,2,.., n
≤ bj
ij
j =1
i =1 i =1
B ng cách thêm bi n ph m i bài toán ñ u có th ñưa v bài toán cân b ng thu phát. ( có th
dùng thu t toán ñơn hình ñ gi i, song do có nhi u bi n nên ph c t p.)
b. Các ñ c ñi m c a bài toán:
* Bài toán cân b ng thu phát luôn có phương án c c biên t i ưu
* Mô t bài toán dư i d ng b ng:
Thu .b1 .b2 ………………….. .bn
Phát
.a1 .c11 .c12 ……………….. .c1n
- .a2 .c21 .c22 …………………. .c2n
…………. …… ……. ………………… …..
.am .cm1 .cm2 ………………. .cmn
Cho x ={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án c a bài toán. N u xij > 0 thì ta gi giá tr
này vào góc dư i phía ph i c a ô (i;j); n u xij = 0 thì không ghi. V y ng v i m t phương án
ta có m t t p h p các ô tương ng v i các thành ph n dương c a phương án. N u phương án
x là c c biên thì h véc tơ ñi u ki n {Aij } tương ng v i thành ph n xij >0 s ñ c l p tuy n
tính.
Ta g i là vòng m t t p h p ô trên b ng mà trong ñó m i ô ñ u n m cùng hàng (cùng
c t) ch v i m t ô ñ ng trư c ñó, ñ ng th i n m cùng c t ( cùng hàng) ch v i m t ô ñ ng sau
nó. Như v y m t hàng ho c m t c t mà vòng ñi qua thì ph i ch qua hai ô, do ñó t ng s ô
trong vòng là m t s ch n ( ít nh t là 4 ô) .M t t p h p ô không ch a vòng g i là t p ô không
t o thành vòng.
Ngư i ta ch ng minh ñư c r ng:
ð nh lý : ð c ñi m c a phương án c biên
Phương án x={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án c c biên khi và ch khi t p
h p các ô (i;j) tương ng v i xiJ > 0 không t o thành vòng.
Do h ng c a ma tr n h ràng bu c là m + n -1nên m t phương án c c biên t i ưu có
t i ña m +n -1 thành ph n dương và do ñó s t i ña các ô trong b ng không t o thành vòng
cũng b ng m +n -1. N u x là phương án c c biên ta g i m +n -1 ô không t o thành vòng là t p
h p ô cơ s ( ô ch n), các ô còn l i g i là ô phi cơ s ( ô lo i) c a phương án c biên x.
2. Xây d ng phương án c c biên:
2.1. Nguyên t c phân ph i t i ña: Khi xây d ng PACB ng v i m t ô ij nào ñó ta gán cho xil
= α . ta nói ñã phân ph i cho ô (i,j) m t lư ng hàng hóa là α và gi α vào ô này.
- L y m t ô (i,j) tùy ý và phân ph i cho nó lư ng hàng hóa t i ña có th , t c là α =
min{ai;bj}. khi ñó :
+ N u xiJ = α = ai yêu c u c a tr m phát Ai ñư c th a mãn, lo i hàng i ra kh i b ng,
s a l i yêu c u c a tram thu b’j = bj – α
+ N u xij = α = bj yêu c u c a tr m thu Bj ñư c th a mãn, lo i c t j ra kh i b ng, s a
l i yêu c u c a tr m phát a’i = ai – α
+ N u xij = α =ai = bj thì yêu c u c a tr m phát và thu ñ u th a mãn, lo i hàng i c t j
ra kh i b ng.
Ti p t c như trên cho t i khi yêu c u c a m i tr m thu, phát ñ u th a mãn.
Các ô ñư c phân ph i có xij > 0 khi ñó t p h p x ={xij} ( i=1,2,…,m; j=1,2,…,n) là m t
phương án c a bài toán vì chúng th a mãn m i ràng bu c. hơn n a nó còn là phương án c c
biên, t p h p các ô ñư c phân ph i chính là t p h p ô cơ s . N u phân ph i ñư c ñúng m +n -
1 ô thì PACB tương ng không suy bi n, n u ít hơn m+n-1 ô thì ñó là PACB suy bi n, ñ có
ñư c t p h p ô cơ s c n b sung s ô cho t i khi ñ m+n-1 ô, ô b sung có xij =0 và không
t o thành vòng v i nh ng ô cơ s ñã có.
2.2.Các phương pháp xây dưng phương án c c biên:
S d ng nguyên t c phân ph i t i ña, tùy thu c vào cách ưu tiên phân ph i ta có
nh ng phương pháp khác nhau ñ xây d ng phương án c c biên.
- - phương pháp góc tây – b c:
Luôn ưu tiên phân ph i cho ô n m góc tây-b c c a b ng ( góc trên bên trái b ng).
Phương pháp này không quan tâm t i chi phí mà th c hi n máy móc theo s phân b c a các
tr m trên b ng.
- Phương pháp chi phí nh nh t (ñư ng g n) Luôn ưu tiên phân ph i cho ô có ciJ nh nh t
trong b ng ñang xét. Phương án c c biên thu ñư c t phương pháp này g n v i phương án t i
ưu hơn.
Thí d 2:
Thu 30 20 25 35 40
Phát
30 13 7 6 2 12
[30]
20 5 1 10 5 11
[20]
40 10 5 3 7 14
[0] [5] [35]
60 6 3 2 11 10
[30] [25] [5]
Ô (2;2) có cư c phí c22 =1 nh nh t nên ưu tiên phân ph i th a yêu c u thu và phát, lo i dòng
2, c t 2 .
Ô (1;4) có c14 = 2 ñư c ưu tiên th hai l y c a tr m phát A1 là a1 = 30 , tr m thu B4 còn c n
lư ng hàng là 35 -30 =5 Ch có th l y t các tr m phát còn hàng do ô (3;4) có cư c phí nh
nh t trong các ô cùng c t, l y 5 ñơn v hàng hóa t tr m phát A3,……
K t qu trên ñã phân ph i cho 7 ô ta ñư c m t phương án c c biên suy bi n. ð có t p ô là cơ
s c n b sung thêm m t ô v i x j = 0 ch ng h n ô (3;2)
3. Phương pháp th v gi i bài toán v n t i.
3.1. Bài toán ñ i ng u và tiêu chu n t i ưu:
Xét bài toán v n t i:
m n
f ( x) = ∑ ∑ cij xij ⇒ Min (1)
i =1 j =1
n
∑x i = 1,2,.., m (2)
= ai
ij
j =1
m
∑x (3)
j = 1,2,.., n
= bj
ij
i =1
.xij ≥ 0 m i i;j (4)
Ký hi u ui; vj là các bi n ñ i ng u ñ i v i h ràng bu c (2) và (3); u = {ui}; v = {vj};
~
f (u; v ) là hàm m c tiêu c a bài toán ñ i ng u, ñ ti n cho vi c gi i thích ý nghĩa kinh t ta
ñ i d u h ràng bu c (2). Khi ñó bài toán ñ i ng u có d ng:
- ~ n m
f (u; v) = ∑ b j v j − ∑ aiui ⇒ Max
j =1 i =1
v j − ui ≤ cij ∀i; j
Trong c p bài toán ñ i ng u này có m*n c p ràng bu c ñ i ng u: xij ≥ 0 và vj – ui ≤ cij
i=1,2,..,m; j =1,2,..,n
ð nh lý: Tiêu chu n t i ưu
ði u ki n c n và ñ ñ phương án x = {xij} c a bài toán v n t i t i ưu là t n t i h
th ng {ui;vj} th a mãn ñi u ki n:
i) vj – ui ≤ cij ( v i m i i, j)
ii) vj –ui = cij n u xij > 0
Tr s c a các ui; vj trong tiêu chu n g i là các th v hàng và c t
Bài toán ñ i ng u có ý nghĩa kinh t hi u như sau: xem th v hàng ui là giá tr m t ñơn v
hàng hóa t i nơi s n xu t Ai , còn th v vj là giá tr m t ñơn v hàng hóa t i nơi tiêu th Bj .
ði u ki n ii) cho th y trong m t phương án v n chuy n t i ưu m t ñơn v hàng hóa t i nơi
tiêu th có giá tr b ng giá tr m t ñơn v hàng hóa t i nơi s n xu t c ng thêm chi phí v n
chuy n c j. ði u ki n i) cho th y chênh l ch v giá tr hàng hóa gi a nơi tiêu th và nơi s n
xu t b t kỳ ñ u không vư t quá chi phí v n chuy n gi a hai nơi y.
3.2. Thu t toán c a phương pháp th v :
Bư c 1: xây d ng phương án c c biên
S d ng m t trong các phương pháp xây d ng phương án c c biên ñã bi t ( ch ng h n
phương án chi phí nh nh t) ký hi u phương án là x0 ( có ñ m + n -1 thành ph n cơ s )
Bư c 2: Xây d ng h th ng th v {ui, vi}:
-L y m t hàng i b t kỳ, cho nó m t th v tùy ý ( thư ng là ui = 0 ). Các th v hàng, c t còn
l i xác ñ nh theo công th c: vj = ui + ciJ ; ui ñã bi t và (i,j) ∈ S 0
.ui = vj – cij , vj ñã bi t và (i,j) ∈ S0
Bư c 3: ki m tra tiêu chu n t i ưu
Theo cách xây d ng, h th ng th v {ui, vj } th a mãn ñi u ki n ii) ñ i v i các ô cơ s
(i,j) ∈ S0 do ñó ch c n ki m tra ñi u ki n i) ñ i v i các ô phi cơ s (i,j) ∉ S 0 n u chúng th a
mãn ñi u ki n i) thì phương án x0 tương ng là phương án t i ưu. N u có m t ô phi cơ s (i,j)
∉ S 0 mà vj – ui > cij thì hi n nhiên x0 chưa là phương án t i ưu. G i nh ng ô này là ô vi ph m.
Tính ñ i lư ng: ∆ ij = v j − ui − uij .
Bư c 4: ði u ch nh phương án.
Gi s Max ∆ ij = ∆ rk (r , k ) ∉ S0 ô (r,k) ñư c ch n làm ô ñi u ch nh , ô (r,k) s t o
∆ ij > 0
thành vòng duy nh t v i m t s ô thu c S0. Tìm vòng này và ký hi u là V . Trên vòng ñánh
d u ô l , ch n sen k nhau b t ñ u t ô (r,k) là ô l . ký hi u là Vl; Vc
0 0 0
-Tìm Min xij ; (i, j ) ∈ Vc Gi s Min xiJ = xst = q (i, j ) ∈ Vc rõ ràng q ≥ 0 và q g i là lư ng
ñi u ch nh.
-Th c hi n phép bi n ñ i trên vòng V theo công th c:
nguon tai.lieu . vn
