Tối ưu hóa là một ngành toán học ứng dụng, đã và đang được nhiều người quan tâm nghiên cứu, tìm hiểu và ứng dụng vào thực tiễn. Bài toán tối ưu là kết quả của việc mô hình hóa những vấn đề nảy sinh từ thực tế, chúng có thể được diễn đạt dưới dạng toán học là tìm các biến số thỏa mãn những điều kiện nhất định và làm cho một hàm số cho trước đạt giá trịcực tiểu hay cực đại.
16 trang |
Chia sẻ: vietpd | Lượt xem: 3928 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Đề tài Ứng dụng lý thuyết tối ưu giải bài toán lập lịch, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
6
CHƯƠNG 1.
3BTỐI ƯU RỜI RẠC VÀ MỘT SỐ HƯỚNG TIẾP CẬN
1.1. 8B ÀI TOÁN TỐI ƯU
Tối ưu hóa là một ngành toán học ứng dụng, đã và đang được nhiều người
quan tâm nghiên cứu, tìm hiểu và ứng dụng vào thực tiễn. Bài toán tối ưu là kết quả
của việc mô hình hóa những vấn đề nảy sinh từ thực tế, chúng có thể được diễn đạt
dưới dạng toán học là tìm các biến số thỏa mãn những điều kiện nhất định và làm
cho một hàm số cho trước đạt giá trị cực tiểu hay cực đại.
1.1.1. 18BDạng tổng quát của bài toán tối ưu
Tìm vectơ 1( ,... ,..., )k nx x x x= thỏa mãn:
f(x) Æ min(max) (1.1)
với điều kiện
≤( ) 0ig x , i = 1, 2, ..., p (1.2)
( ) 0jh x = , j = 1, 2, ..., q (1.3)
x ∈ X ⊂ RPnP, k = 1, 2, …, n (1.4)
Trong đó f, gRiR, hRjR (i = 1, 2, …, p; j = 1, 2, …, q) là các hàm số cho trước của n
biến số (f, gRiR, hRjR: R Pn P Æ R) và X ⊂ RPnP là tập đóng, thường có dạng
X = +
nR ≡ {x ∈ RPnP : xRjR ≥ 0, j = 1, 2, …, n}
Bài toán (1.1) – (1.4) có tên gọi là bài toán quy hoạch toán học. Hàm f(x)
được gọi là hàm mục tiêu, còn gRiR(x) và hRjR(x) là các hàm ràng buộc và ràng buộc
dạng xRjR ≥ 0, j = 1, 2, …, n, được gọi là các ràng buộc về dấu. Tập hợp:
D = { x ∈ X: ≤( ) 0ig x , i = 1, 2, ..., p; ( ) 0jh x = , j = 1, 2, ..., q},
7
gọi là miền ràng buộc hoặc miền chấp nhận được. Mỗi véctơ x ∈ D được gọi là một
phương án hoặc một lời giải chấp nhận được của bài toán. Phương án làm cho hàm
số f(x) đạt giá trị cực tiểu hoặc cực đại được gọi là phương án tối ưu hoặc lời giải
của bài toán.
1.1.2. 19BPhân loại các bài toán tối ưu
Các bài toán tối ưu nói chung rất phong phú và đa dạng. Để tìm lời giải cho
các bài toán này, có thể có một cách chung và đơn giản nhất là duyệt toàn bộ các
phương án có thể có của bài toán đặt ra để chọn phương án tối ưu. Song do số
phương án của các bài toán dạng này thường là một số rất lớn, thậm chí không đếm
được, nên cách làm này không phải bao giờ cũng thực hiện được, ngay cả khi kích
thước của bài toán không lớn lắm. Vì thế cần phải có những nghiên cứu về mặt lý
thuyết để tách ra những lớp bài toán riêng, khai thác cấu trúc đặc thù của nó để đề ra
phương pháp giải thích hợp. Sau đây là một số lớp bài toán tối ưu thường gặp:
- Quy hoạch tuyến tính: Khi hàm mục tiêu f(x) và tất cả các hàm ràng buộc
gRiR(x), hRjR(x) là tuyến tính, tập X là tập lồi đa diện (giao của một số hữu hạn các nửa
không gian đóng).
- Quy hoạch tham số: Khi các hệ số trong biểu thức của hàm mục tiêu và của
các ràng buộc phụ thuộc tham số.
- Quy hoạch phi tuyến: Khi hàm mục tiêu f(x) hoặc tồn tại ít nhất một trong
các hàm ràng buộc gRiR(x), hRjR(x) không phải là tuyến tính, hoặc tập X khác tập lồi
đa diện.
- Quy hoạch lồi: Khi hàm mục tiêu f(x) là hàm lồi (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Quy hoạch lõm: Khi hàm mục tiêu f(x) là hàm lõm (nếu xét bài toán tìm cực
tiểu) và miền ràng buộc D là tập hợp lồi.
- Tối ưu rời rạc: Khi X là tập rời rạc. Các bài toán tối ưu rời rạc thường xuất
hiện khi nghiên cứu các quá trình hay đối tượng rời rạc. Trong trường hợp riêng khi
8
các biến chỉ nhận giá trị nguyên ta có quy hoạch nguyên. Một trường hợp riêng của
quy hoạch nguyên là quy hoạch Boole, khi mà các biến số chỉ nhận giá trị 0 hoặc 1.
Có thể chứng minh rằng: mọi bài toán tối ưu rời rạc đều có thể đưa về bài
toán quy hoạch Boole. Thật vậy, giả sử biến số x chỉ có thể lấy một trong các giá trị
cho trước aR1R, aR2R, …, aRkR. Khi đó bằng cách đặt:
x = aR1RuR1R + aR2RuR2R + … + aRkRuRk R,
uR1R + uR2R + …+ uRkR = 1, uRj R∈ {0, 1}, j = 1, 2, …, k
thì biến rời rạc x có thể thay thế bởi một số biến uRjR chỉ nhận giá trị 0 hay 1, gọi tắt là
biến 0-1 hay biến Boole.
Tương tự, nếu x ∈ {0, 1, …, k} thì ta có thể viết:
x = uR1R + uR2R + …+ uRkR với uRj R∈ {0, 1}, j = 1, 2, …, k
nghĩa là bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về bài
toán với các biến 0-1. Điều này cho thấy bài toán quy hoạch nguyên 0-1 giữ vai trò
quan trọng trong tối ưu rời rạc.
1.2. 9BCÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC
Tối ưu rời rạc hay còn gọi là tối ưu tổ hợp là một lĩnh vực quan trọng trong
lý thuyết tối ưu hóa. Các bài toán tối ưu nói chung và các bài toán tối ưu tổ hợp nói
riêng rất phong phú và đa dạng. Chúng có nhiều ứng dụng rộng rãi trong thực tiễn.
Sau đây là một số công cụ thường dùng trong tối ưu tổ hợp. Đó là các
phương pháp cắt nổi tiếng của Gomory và phương pháp “nhánh và cận” rất có hiệu
quả với nhiều biến dạng khác nhau cho các bài toán cụ thể: phương pháp quy hoạch
động, phương pháp tìm kiếm ngẫu nhiên…
9
1.2.1. 20BPhương pháp cắt Gomory
Xét bài toán quy hoạch tuyến tính có thêm điều kiện nguyên, gọi là bài toán
quy hoạch nguyên tuyến tính.
0
1
n
j j
j
x c x
=
= ∑ → min
với các ràng buộc:
∑
=
n
j
jij xa
1
= bRiR , i = 1, 2, ..., m;
xRjR ≥ 0, j = 1, 2, ..., n;
xRjR nguyên, j = 1, 2, ..., nR1R ≤ n
Nếu nR1R = n ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu nR1R < n thì có
bài toán quy hoạch nguyên bộ phận.
Gomory là người đầu tiên đưa ra các thuật toán cắt giải quy hoạch nguyên
tuyến tính. Ý đại thể của phương pháp Gomory như sau: giải quy hoạch tuyến tính
không có điều kiện nguyên, nếu bài toán này không có lời giải thì bài toán nguyên
cũng không có lời giải. Nếu bài toán có lời giải và lời giải đó thỏa điều kiện nguyên
thì đó là lời giải của bài toán nguyên, còn nếu lời giải đó không nguyên thì ta sẽ
thêm vào một ràng buộc tuyến tính mới, cắt bỏ lời giải không nguyên này và vẫn
giữ lại các điểm nguyên của miền ràng buộc. Ràng buộc thêm vào như thế gọi là
siêu phẳng cắt hay lát cắt. Rồi lại giải quy hoạch tuyến tính tương ứng (không có
điều kiện nguyên)... Với những điều kiện nhất định, quá trình trên sẽ dẫn đến lời
giải nguyên sau một số hữu hạn bước lặp.
Để áp dụng được phương pháp Gomory, cần có các giả thiết sau đây:
a) Hàm mục tiêu 0x bị chặn dưới (đối với bài toán min) trên miền ràng
buộc không có điều kiện nguyên.
10
b) Tập phương án tối ưu (lời giải) của bài toán tuyến tính không có điều
kiện nguyên nếu khác rỗng thì phải bị chặn.
c) 0x đòi hỏi phải nguyên (chẳng hạn, mọi cRjR nguyên).
d) Có một trong hai điều kiện sau:
- Hàm mục tiêu xR0R bị chặn trên miền ràng buộc không có
điều kiện nguyên.
- Bài toán có phương án (điểm) nguyên.
Tóm lại, các điều kiện trên sẽ được thỏa mãn nếu miền ràng buộc (không kể
điều kiện nguyên) là bị chặn và các hệ số aRijR, bRiR, cRjR đều nguyên.
Có ba cách khác nhau thể hiện ý tưởng phương pháp giải nêu trên.
1.2.1.1. 42BThuật giải Gomory 1
Thuật toán này áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n).
Nội dung thuật toán như sau: Áp dụng phương pháp đơn hình đối ngẫu từ
vựng giải quy hoạch tuyến tính không có điều kiện nguyên, nếu bài toán không giải
được thì bài toán nguyên cũng không giải được. Nếu bài toán giải được và lời giải
thỏa mãn điều kiện nguyên thì lời giải đó đồng thời là lời giải cần tìm (quá trình giải
kết thúc). Nếu lời giải đó không nguyên, ta chuyển sang bước lặp k = 0.
Bước k ≥ 0. Giả sử ta đã có lời giải xPkP không nguyên. Ký hiệu NRkR là tập chỉ số
các biến phi (ngoài) cơ sở. Biểu diến hàm mục tiêu 0x = cP
T
Px và các biến xR1R, xR2R, ...,
xRnR qua các biến phi cơ sở xRjR ( j ∈ NRkR):
xRiR = 0
k
k k
i ij j
j N
x x x
∈
− ∑ , i = 0, 1, 2, ..., n
và bảng các hệ số TRkR = kijx là l-chuẩn, nghĩa là ở mỗi cột j ∈ NRkR ∪ {0} phần tử
khác không đầu tiên phải là số dương.
11
Chọn dòng có chỉ số nhỏ nhất mà kix 0 không nguyên:
t = min {i ∈ {0, 1, 2, ..., n} | ktx 0 không nguyên}
và xây dựng siêu phẳng cắt tương ứng:
xRn+k+1R = ( )0{ } { }
k
k k
t ij j
j N
x x x
∈
− − −∑
xRn+k+1R ≥ 0 và nguyên.
([x] : phần nguyên của x, {x} = x – [x] : phần lẻ của x)
Thêm dòng xRn+k+1R vào phía dưới bảng TRkR và được bảng đơn hình không chấp
nhận được (chỉ ở dòng xRn+k+1R!). Áp dụng phương pháp đơn hình đối ngẫu từ vựng,
nếu kết quả ta nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính
không giải được thì bài toán quy hoạch nguyên cũng không giải được, nếu trái lại
kiểm tra tính nguyên của lời giải thu được. Nếu điều kiện nguyên được thỏa mãn thì
đó là lời giải cần tìm, nếu trái lại ta chuyển sang bước lặp k + 1.
Nếu có các giải thiết như đã nêu trên thì thuật toán Gomory 1 kết thúc sau
một số hữu hạn bước lặp k.
1.2.1.2. 43BThuật toán Gomory 2
Áp dụng cho bài toán quy hoạch nguyên bộ phận (nR1R ≤ n).
Về cơ bản, thuật toán Gomory 2 giống như thuật toán Gomory 1, chỉ khác ở
cách xây dựng siêu phẳng cắt. Nhờ thuật toán Gomory 2 (trong trường hợp nR1R = n)
cũng có thể giải bài toán quy hoạch nguyên hoàn toàn. Nhưng trong trường hợp này
không có cơ sở để so sánh hiệu quả của thuật toán Gomory 1 và 2 với nhau.
Cách xây dựng siêu phẳng cắt trong thuật toán Gomory 2 như sau:
Giả sử ktx 0 không nguyên. Khi đó bất đẳng thức:
12
z = 00 ≥+− ∑
∈ kNj
jj xss là siêu phẳng cắt.
Ở đây, sR0R = )( 0ktx và sRjR =
⎪⎪
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎪⎪
⎨
⎧
<+≥−−
≥+≥
>≤−−
≤≤
0,1)(
}{1
}{
0,1
}{}{,}){1(
}{1
}{
}{}{,}{
1
0
0
1
01
0
0
01
k
ij
k
ijk
t
k
t
k
ij
k
ij
k
t
k
ij
k
ijk
t
k
t
k
t
k
ij
k
ij
xnjx
x
x
xnjx
xxnjx
x
x
xxnjx
Các điều kiện bảo đảm tính hữu hạn của thuật toán Gomory 2 hoàn toàn
giống như các điều kiện của thuật toán Gomory 1.
1.2.1.3. 44BThuật toán Gomory 3
Áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n). Thuật toán 3 có
ưu điểm là không bị ảnh hưởng bởi sai số làm tròn trong quá trình tính toán.
Ý tưởng của thuật toán này như sau: xuất phát từ bảng nguyên, l-chuẩn (phần
tử khác không đầu tiên của của mỗi cột là số dương) và không chấp nhận được (cột
phương án còn có thành phần âm). Xây dựng ràng buộc mới sao cho dùng nó làm
dòng quay với phần tử quay (còn gọi là phần tử chính) bằng -1, rồi biến đổi bảng
đơn hình,... cho đến khi nào bảng là chấp nhận được thì ta có lời giải cần tìm.
Cách xây dựng ràng buộc mới - siêu phẳng cắt – là như sau:
Cho bảng nguyên, l-chuẩn và không chấp nhận được
T = ijx , i = 0, 1, ..., n; j ∈ {0} ∪ NRk
Giả sử t (1 ≤ t ≤ n) là chỉ số sao cho xRt0R < 0. Khi đó z = −1 + ∑
<
∈
≥
0
0
tj
k
x
Nj
jx
là siêu phẳng cắt. Ta có thể chọn siêu phẳng cắt tốt hơn, nhưng khá phức tạp.
13
1.2.2. 21BPhương pháp nhánh cận Land – Doig
Xét bài toán quy hoạch nguyên tuyến tính sau đây
∑
=
n
j
jj xc
1
→ min (1.5)
với các điều kiện:
∑
=
n
j
jij xa
1
= bRiR, i = 1, 2, ..., m (1.6)
0 ≤ xRj R≤ uRjR, j = 1, 2, ..., n (1.7)
xRjR nguyên, j ∈ J với J ⊆ {1, 2, ..., n} (1.8)
trong đó uRjR là cận trên của biến xRjR (có thể uRjR = +∞).
Để cho bài toán (1.5) - (1.8) có hữu hạn phương án nguyên, ta giả thiết tập
tất cả các điểm x thỏa (1.6) - (1.7) là bị chặn (chẳng hạn, mọi uRjR đều hữu hạn).
Nếu J ≡ {1, 2, ..., n}, ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu
J ⊂ {1, 2, ..., n} thì có bài toán quy hoạch nguyên bộ phận.
Trong bài toán trên, cùng với các ràng buộc đẳng thức có thể còn có các ràng
buộc bất đẳng thức ≤ hay ≥. Ngoài ra, như thường lệ, bài toán tìm max có thể qui về
bài toán tìm min bằng các đổi dấu hàm mục tiêu.
Nội dung phương pháp: Ký hiệu PR1R là bài toán quy hoạch tuyến tính tương
ứng với bài toán quy hoạch nguyên (1.5) - (1.8) (tạm bỏ qua điều kiện nguyên). Bài
toán (1.5) - (1.8) sẽ được chia nhỏ dần thành một số hữu hạn các bài toán nhỏ hơn
(theo nghĩa số phương án nguyên ít hơn), gọi tắt là các bài toán con. Mỗi bài toán
con đều nhận được từ bài toán ban đầu bằng cách thêm vào một số ràng buộc dạng:
xRjR ≥ αRjR ( j ∈ JR1R), xRjR ≤ βRjR ( j ∈ JR1R) với JR1R, JR2R ⊆ J, (1.9)
trong đó αRjR, βRj Rlà những số nguyên nào đó (có thể JR1R hoặc JR2R bằng ∅).
14
Với mỗi bài toán con nhận được, ta xét bài toán quy hoạch tuyến tính tương
ứng (bỏ qua điều kiện nguyên), thực chất đó là bài toán PR1 Rcó thêm các ràng buộc
(1.9) nêu trên.
Khi giải các bài toán quy hoạch tuyến tính tương ứng, ta có thể gặp một
trong các tình huống sau:
a) Bài toán không có phương án (miền ràng buộc rỗng), do đó nó cũng
không có phương án nguyên, vì thế bài toán con đang xét sẽ bị loại (không cần xét
tiếp nữa).
b) Bài toán có phương án tối ưu nguyên (mọi thành phần j thuộc J nguyên).
Khi đó ta nhận được một phương án của bài toán nguyên ban đầu (1.5) - (1.8) và giá
trị hàm mục tiêu, thường được gọi là giá trị kỷ lục. Bài toán con tương ứng cũng đã
xét xong và bị loại.
c) Bài toán có phương án tối ưu, nhưng trong đó có ít nhất một thành phần j
thuộc J không nguyên. Khi đó, giá trị tối ưu nhận được là một cận dưới cho mọi
phương án nguyên của bài toán con đang xét. Bài toán con nào có cận dưới lớn hơn
hay bằng giá trị kỷ lục sẽ bị loại, vì nó sẽ không chứa phương án nguyên tốt hơn.
Tiếp đó, trong số các bài toán con còn lại, ta chọn bài toán có cận dưới nhỏ
nhất (với hy vọng nó có nhiều khả năng chứa phương án nguyên tốt hơn). Giả sử
bài toán quy hoạch tuyến tính tương ứng với bài toán con được chọn là bài toán PRkR
và cận dưới nhỏ nhất này tương ứng với phương án tối ưu không nguyên xRkR của bài
toán PRkR đã tìm được trước đó. Giả sử thành phần ktx không nguyên.Khi đó, bài toán
con đang xét được chia thành hai bài toán con mới bằng cách thêm vào ràng buộc:
[ ] 1+≥ ktt xx hoặc [ ]ktt xx ≤
Để tính cận dưới cho mỗi bài toán con mới, ta lại giải bài toán quy hoạch
tuyến tính tương ứng với bài toán con đó (bỏ qua điều kiện nguyên).
15
Tùy theo kết quả giải, ta có thể loại bớt một số bài toán con mà chắc chắn nó
không chứa phương án nguyên tốt hơn phương án hiện biết.
Tiếp tục làm như vậy làm như vậy cho đến khi không còn bài toán con nào
để xét nữa thì dừng.
1.3. 10B ÀI TOÁN LUỒNG TRÊN MẠNG
1.3.1. 22BLuồng trên mạng
Trong nhiều ứng dụng liên quan đến đồ thị, cần thiết phải sử dụng các biến
đo lượng dòng chảy qua mỗi cung, chẳng hạn như hệ thống mạng điện, mạng viễn
thông, mạng sản xuất và phân phối, mạng giao thông, mạng ống dẫn nước, mạng
máy tính,… Trên những hệ thống mạng như thế, chúng ta muốn chuyển một lượng
chất liệu từ nơi này đến nơi khác sao cho đạt hiệu quả cao nhất. Hiệu quả ở đây có
thể xét theo tiêu chuẩn thời gian, độ dài quãng đường, chi phí tiền bạc, mức độ an
toàn,… Dạng bài toán này được gọi là bài toán luồng trên mạng.
Mạng là một đồ thị có hướng G(V, E) với V là tập đỉnh, E là tập các cung;
trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát và có duy
nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e = (v, w) ∈ E
được gán với một số không âm c(e) = c(v, w) gọi là khả năng thông qua của cung e
(nếu không có cung (v, w) thì khả năng thông qua c(v, w) được gán bằng 0).
Một luồng f trong mạng G(V, E) là ánh xạ f: E Æ RPnP, gán cho mỗi cung
e = (v, w) của đồ thị một số không âm f(e) = f(v, w), gọi là luồng trên cung e,
thoả mãn các điều kiện:
16
1) Luồng trên mỗi cung e không vượt quá khả năng thông qua của nó:
0 ≤ f(e) ≤ c(e) với mọi cung e ∈ E;
2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: tổng luồng trên mỗi
cung đi vào đỉnh v (trừ s, t) bằng tổng luồng trên các cung đi ra khỏi đỉnh v:
( )
( )
w s
f w, v
+∈Γ
∑ =
( )
( )
w s
f w, v
−∈Γ
∑
với ( )v−Γ = {w ∈ V: (w, v) ∈ E} và ( )v+Γ = {w ∈ V: (v, w) ∈ E}.
3) Giá trị của luồng f là số:
val( f ) =
( )
( )
w s
f s, w
+∈Γ
∑ =
( )
( )
w s
f w, t
−∈Γ
∑
Bài toán luồng cực đại trong mạng: Cho mạng G = (V, E). Hãy tìm luồng
f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng f* được gọi là luồng cực
đại trong mạng.
1.3.2. 23BPhân loại các thuật toán luồng trên mạng
Các thuật toán trên mạng nói chung có thể được phân thành 3 loại sau:
- Cải tiến chi phí nguyên thủy (Primal cost improvement): Thực hiện các
vòng lặp cải tiến chi phí đến giá trị tối ưu của nó bằng cách xây dựng một dãy các
luồng khả thi tương ứng.
- Cải tiến chi phí đối ngẫu (Dual cost improvement): Ở đây ta xây dựng bài
toán có liên hệ với bài toán luồng trên mạng ban đầu, gọi là bài toán đối ngẫu, có
các biến được gọi là các giá. Sau đó thực hiện các vòng lặp cải tiến chi phí đối ngẫu
đến giá trị tối ưu của nó bằng cách xây dựng một dãy các giá tương ứng.
- Đấu giá: Ở đây ta sinh ra một dãy các giá theo kiểu đấu giá trong cuộc
sống thực. Cụ thể, sẽ không có việc cải tiến chi phí đối ngẫu và nguyên thủy ở đây,
mặc dù ta có thể xem rằng việc đầu giá như là xấp xỉ của quá trình cải tiến đối ngẫu.
17
1.3.3. 24BThuật toán tìm luồng cực đại trong mạng
Hiện nay có nhiều thuật toán để giải bài toán luồng cực đại trên mạng: Ford-
Fulkerson (1956), Edmonds-Karp (1969), Dinic (1970), Karzanov (1974),
Malhotra-Kumar-Maheshwari (1977), Sleator-Tarian (1980), Goldberg-Tarjan
(1986), …
Sau đây ta xét hai thuật toán thường sử dụng nhất là thuật toán
Ford-Fulkerson và thuật toán Edmonds-Karp.
1.3.3.1. 45BThuật toán Ford-Fulkerson
Ta đưa thêm vào một số khái niệm sau: Giả sử f là một luồng trong mạng
G = (V, E). Từ mạng G = (V, E) ta xây dựng đồ thị có trọng số trên mạng
GRfR = (V, ERf R), với tập các cung ERfR và trọng số trên các cung được xác định như sau:
1) Nếu e = (v, w) thuộc E với f(v, w) = 0, thì (v,w) thuộc ERfR với
trọng số c(v,w).
2) Nếu e = (v, w) thuộc E với f(v,w) = c(v, w), thì (w, v) thuộc ERfR với
trọng số f(v,w).
3) Nếu e = (v, w) thuộc E với 0 < f(v,w) < c(v, w) thì (v, w) thuộc ERfR
với trọng số c(v, w) - f(v, w) và (w, v) thuộc ERfR với trọng số f(v, w).
Các cung của GRfR đồng thời cũng là cung của G được gọi là cung thuận, các
cung còn lại được gọi là cung nghịch. Đồ thị GRfR được gọi là đồ thị tăng luồng.
Ví dụ: Các số viết cạnh các cung của G ở Hình vẽ 1.1 theo thứ tự là khả năng
thông qua và luồng f trên các cung.
18
Hình 1.1. Khả năng thông qua và luồng trên cung
Giả sử P = (s ≡ vR1R, vR2R, vR3R,.. , vRkR ≡ t) là một đường đi từ s đến t trên đồ thị tăng
luồng GRfR. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P.
Xây dựng luồng f ' trên mạng G theo quy tắc sau:
f(u,v) + d nếu (u, v) thuộc P là cung thuận;
f '(u, v) = f(u,v) - d nếu (v, u) thuộc P là cung nghịch;
⎧⎪⎨⎪⎩
f(u,v) nếu (u, v) không thuộc P.
Ta gọi thủ tục biến đổi luồng nêu trên là tăng luồng dọc theo đường P.
Đường đi từ s đến t trên đồ thị tăng luồng GRfR gọi là đường tăng luồng.
Bắt đầu từ luồng với tất cả các cung bằng 0 ta tìm đường tăng luồng trên đồ
thị tăng luồng và thực hiện tăng luồng theo đường đi vừa tìm được. Sơ đồ thuật toán
Ford-Fulkerson được mô tả trong thủ tục sau đây:
Procedure Max_Flow;
(*Thuật toán Ford-Fulkerson *)
Begin
(* khởi tạo bắt đầu từ luồng với giá trị 0 *)
for u thuộc V do
for v thuộc V do f(u,v):=0;
Stop:= false;
while not Stop do
if {tìm được đường tăng luồng P}then
{tăng luồng dọc theo P}
else stop:=true;
End;
19
Thuật toán Ford-Fulkerson có độ phức tạp là O(m.val(f*)), với f* là luồng
cực đại trong mạng. Để tìm được đường tăng luồng trong GRfR có thể sử dụng thuật
toán tìm kiếm theo chiều rộng hay tìm kiếm theo chiều sâu bắt đầu từ đỉnh s, nhưng
sử dụng thuật toán gán nhãn của Ford-Fulkerson sẽ tối ưu hơn.
Thuật toán được thực hiện bắt đầu với duy nhất đỉnh s được khởi tạo nhãn và
nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại đều chưa có nhãn. Từ s ta gán
nhãn tất cả các đỉnh kề với nó và nhãn của đỉnh s trở thành đã xét. Tiếp theo, từ mỗi
đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả đỉnh chưa có nhãn kề với nó và
nhãn của đỉnh v trở thành đã xét. Quá trình cứ lặp lại cho tới khi: hoặc là đỉnh t trở
thành có nhãn hoặc là nhãn của tất cả các đỉnh có nhãn đều trở thành đã xét nhưng
đỉnh t vẫn không có nhãn. Trong trường hợp thứ nhất ta tìm được đường tăng luồng,
còn trường hợp thứ hai đối với luồng đang xét không tồn tại đường tăng luồng (tức
là luồng đã là cực đại). Mỗi khi tìm được đường tăng luồng, ta