Một số ứng dụng trong tổ hợp

Có m chàng trai ở một vùng quê nọ. Đối với mỗi chàng trai ta biết các cô gái mà anh ta vừa ý. Hỏi khi nào thì có thể tổ chức các đám cưới trong đó chàng trai nào cũng sánh duyên với các cô gái mà mình vừa ý.Ta có thể xây dựng đồ thị với các đỉnh biểu thị các chàng trai và các cô gái, còn các cung biểu thị sự vừa ý của các chàng trai với các cô gái. Khi đó ta thu được một đồ thị hai phía.

Thí dụ. Có 4 chàng trai  T₁, T₂, T₃,T_4và 5 cô gái  G₁, G₂, G₃,G₄, G_5. Sự vừa ý cho trong bảng sau

Đồ thị tương ứng được cho trong hình 7.

Hình 7. Mạng tương ứng với bài toán đám cưới vùng quê

Đưa vào điểm phát s và điểm thu t. Nối s với tất cả các đỉnh biểu thị các chàng trai, và nối t với tất cả các đỉnh biểu thị các cô gái. Tất cả các cung của đồ thị đều có khả năng thông qua bằng 1. Bắt đầu từ luồng 0, ta tìm luồng cực đại trong mạng xây dựng được theo thuật toán Ford-Fulkerson. Từ định lý về tính nguyên, luồng trên các cung là các số hoặc 1. Rõ ràng là nếu luồng cực đại trong đồ thị có giá trị Vmax = m, thì bài toán có lời giải, và các cung với luồng bằng 1 sẽ chỉ ra cách tổ chức đám cưới thoả mãn điều kiện đặt ra. Ngược lại, nếu bài toán có lời giải thì Vmax = m. Bài toán về đám cưới vùng quê là một trường hợp riêng của bài toán về cặp ghép trên đồ thị hai phía mà để giải nó có thể xây dựng thuật toán hiệu quả hơn.

Cho tập m phần tử X= z₁, z₂, . . . ,z_m. Giả sử <A₁, A₂, . . ., A_n> và <B₁, B₂, . . ., B_n> là hai dãy các tập con của X. Dãy gồm n phần tử khác nhau của X: <a₁, a₂, . . . ,a_n> được gọi là hệ thống các đại diện chung của hai dãy đã cho nếu như tìm được một hoán vị σ của tập  1, 2,. . .,n sao cho < a₁, a₂, . . . ,a_n> là hệ thống các đại diện phân biệt của hai dãy <A₁, A₂, . . ., A_n> và <Bσ ₍₁₎, Bσ ₍₂₎, . . ., Bσ _(n)>, tức là điều kiện sau được thoả mãn: ai ∈ Ai  Bσ _(i), i = 1, 2, . . ,n. Xây dựng mạng G=(V,E) với tập đỉnh

V =  s, t   x₁, x₂, . . . ,x_n  u₁, u₂, . . . ,u_n  v₁, v₂, . . . ,v_n  y₁, y₂, . . . ,y_n.

trong đó đỉnh xi tương ứng với tập Ai, đỉnh yi tương ứng với tập Bi, các phần tử uj, yj tương ứng với phần tử zj. Tập các cung của mạng G được xác định như sau

E  =  (s,x_i): 1≤i≤n   (x_i,u_j): với z_j ∈ A_i, 1≤i≤n, 1≤j≤m  (u_j,v_j):1≤j≤m  (v_j, y_i): với z_j ∈ B_i, 1≤i≤n, 1≤j≤m   (y_i, t): 1≤i≤n

Khả năng thông qua của tất cả các cung được đặt bằng 1. Dễ dàng thấy rằng hệ thống đại diện chung của hai dãy và tồn tại khi và chỉ khi trong mạng G=(V,E) tìm được luồng với giá trị n. Để xét sự tồn tại của luồng như vậy có thể sử dụng thuật toán tìm luồng cực đại từ s đến t trong mạng G=(V,E).

Trong mục này ta sẽ trình bày thuật toán được xây dựng dựa trên thuật toán tìm luồng cực đại để giải một bài toán tối ưu rời rạc là mô hình toán học cho một số bài toán tối ưu tổ hợp.

Xét bài toán tối ưu rời rạc:

f(x₁,x₂,...,x_n) = (1)

với điều kiện

trong đó a_ij ∈  0,1 , i = 1, 2, . . . , m; j=1, 2, . . . n, p_i –nguyên dương, i = 1, 2, . . .,m.

Bài toán (1)-(3) là mô hình toán học cho nhiều bài toán tối ưu tổ hợp thực tế. Dưới đây ta dẫn ra một vài ví dụ điển hình.

Bài toán phân nhóm sinh hoạt. Có m sinh viên và n nhóm sinh hoạt chuyên đề. Với mỗi sinh viên i, biết a_ij =1, nếu sinh viên i có nguyện vọng tham gia vào nhóm j,a_ij =0, nếu ngược lại,và pij là số lượng nhóm chuyên đề mà sinh viên i phải tham dự, i = 1, 2, . . . ,m; j=1, 2,. . . ,n. Trong số các cách phân các sinh viên vào nhóm chuyên đề mà họ có nguyện vọng tham gia và đảm bảo mỗi sinh viên i phải tham gia đúng pi nhóm, hãy tìm cách phân phối với số người trong nhóm có nhiều sinh viên tham gia nhất là nhỏ nhất có thể được.

Đưa vào biến số

x_ij=1_, nếu sinh viên i tham gia vào nhóm j,

x_ij=0_, nếu ngược lại,

i=1, 2, . . .,m, j=1, 2,. . .,n, khi đó dễ thấy mô hình toán học cho bài toán đặt ra chính là bài toán (1)-(3).

Bài toán lập lịch cho hội nghị. Một hội nghị có m tiểu ban, mỗi tiểu ban cần sinh hoạt trong một ngày tại phòng họp phù hợp với nó. Có n phòng họp dành cho việc sinh hoạt của các tiểu ban. Biết

a_ij = 1, nếu phòng họp i là thích hợp với tiểu ban j,aij=0, nếu ngược lại,i=1, 2, . . .,m, j=1, 2,. . .,n. Hãy bố trí các phòng họp cho các tiểu ban sao cho hội nghị kết thúc sau ít ngày làm việc nhất.

Đưa vào biến số x_ij = 1, nếu bố trí tiểu ban i làm việc ở phòng j,x_ij=0, nếu ngược lại,i=1, 2, . . .,m, j=1, 2,. . .,n, khi đó dễ thấy mô hình toán học cho bài toán đặt ra chính là bài toán (1)-(3), trong đó p_i=1, i=1, 2, . . .,m.

Bổ đề 2.

Bài toán (1)-(3) có phương án tối ưu khi và chỉ khi

Chứng minh. Điều kiện cần của bổ đề là hiển nhiên vì từ sự tồn tại phương án của bài toán suy ra các bất đẳng thức trong (4) được thực hiện ít nhất dưới dạng dấu đẳng thức. Để chứng minh điều kiện đủ, chỉ cần chỉ ra rằng nếu điều kiện (4) được thực hiện thì bài toán luôn có phương án. Thực vậy, giả sử điều kiện (4) được thực hiện. Khi đó nếu ký hiệu I_+i= 1≤j≤n: aij_=1,thì  I_+i≥ pi, i = 1, 2, . . .,m. Do đó nếu gọi Ii_⊂I_+i,  Ii =pi, i=1, 2,. . . ,m,thì X^* = (x^*_ij)_mxn với các thành phần được xác định theo công thức

x^*_ij = 1, j∈ Ii, x^*_ij =0_, j∉ Ii, i= 1, 2, . . .,m,là phương án của bài toán (1)-(3). Bổ đề được chứng minh.

Do (4) là điều kiện cần để bài toán (1)-(3) có phương án, nên trong phần tiếp theo ta sẽ luôn giả thiết rằng điều kiện này được thực hiện.

Bây giờ ta chỉ ra rằng việc giải bài toán (1)-(3) có thể dẫn về việc giải một số hữu hạn bài toán luồng cực đại trong mạng. Trước hết, với mỗi số nguyên dương k, xây dựng mạng G(k) =(V,E) với tập đỉnh

V=  s   u_i :i=1, 2,. . . ,m   w_j : j=1, 2, . . .,n   t

trong đó s là điểm phát, t là điểm thu, và tập cung

E=  (s,u_i):i=1, 2,. . .,m   (u_i,w_j):i=1, 2,. . . ,m; j=1, 2, . . .,n   (w_j,t): j=1, 2, . . .,n .

Mỗi cung e ∈ E được gán với khả năng thông qua q(e) theo qui tắc sau:

q(s,u_i)=p_i, i=1, 2,. . .m,

q(u_i,w_i)=a_ij, i=1, 2,. . .m; j=1, 2, . . .,n;

q(w_j,t)=k, j=1, 2, . . .,n.

Hình 8 chỉ ra cách xây dựng mạng G(k).

Hình 8. Mạng G(k).

Bổ đề sau đây cho thấy mối liên hệ giữa luồng cực đại trong mạng G(k) và phương án của bài toán (1)-(3).

Bổ đề 3.

Giả sử đối với số nguyên dương k nào đó, luồng cực đại nguyên trong mạng G(k) có giá trị là σ . Khi đó X^* = (x^*_ij)_mxn với các thành phần được xác định theo công thức

x^*_ij =  ^* (u_i,w_j), i=1, 2,. . .,m; j=1, 2,. . . ,n.

là phương án của bài toán (1)-(3).

Chứng minh. Thực vậy, do luồng cực đại trong mạng có giá trị σ và là luồng nguyên nên

 ^* (s,u_i)=p_i, i=1, 2,. . .,m,

 ^* (u_i,w_j) ∈  0,1 , i=1, 2,. . .,m, j=1, 2,. . .,n,

từ đó suy ra  

Vậy X^* là phương án của bài toán (1)-(3). Bổ đề được chứng minh.

Bổ đề 4.

Giả sử X^* =(x^*_ij) là phương án tối ưu và k^* là giá trị tối ưu của bài toán (1)-(3). Khi đó luồng cực đại trong mạng G(k^*) có giá trị σ .

Chứng minh. Do giá trị của luồng cực đại trong mạng G(k^*) không vượt quá σ , nên để chứng minh bổ đề ta chỉ cần chỉ ra luồng với giá trị σ trong mạng G(k^*).

Xây dựng luồng  ^* theo công thức sau:

 ^* (s,u_i) = p_i,  ^* (u_i, w_j) = x^*_ij,

Dễ dàng kiểm tra được  ^* là luồng trong mạng G(m) có giá trị σ . Bổ đề được chứng minh.

Bổ đề 5. Nếu k=m thì luồng cực đại trong mạng G(m) có giá trị σ .

Chứng minh. Lập luận tương tự như trong Bổ đề 4, ta chỉ cần chỉ ra luồng với giá trị σ trong mạng G(m). Thực vậy, giả sử X^* = (x^*_ij)_mxn là phương án của bài toán (1)-(3) xây dựng theo công thức (5). Xây dựng luồng  ^* theo công thức giống như trong chứng minh bổ đề 4, ta có luồng với giá trị σ . Bổ đề được chứng minh.

Từ bổ đề 3 và 4 suy ra việc giải bài toán (1)-(3) dẫn về việc tìm giá trị k^* nguyên dương nhỏ nhất sao cho luồng cực đại trong mạng G(k^*) có giá trị σ. Bổ đề 5 cho ta thấy giá trị k^* ∈ [1,m]. Vì vậy để giải bài toán (1)-(3) ta có thể áp dụng phương pháp tìm kiếm nhị phân trên đoạn [1,m] để tìm giá trị k^*, trong đó ở mỗi bước cần giải một bài toán luồng cực đại. Để giải bài toán tìm luồng cực đại trong mạng có thể sử dụng các thuật toán đa thức như đã nói ở trên. Từ đó suy ra kết quả sau

Định lý 5.

Bài toán (1)-(3) giải được nhờ thuật toán đa thức với độ phức tạp tính toán là log₂m.ONF, trong đó ONF là độ phức tạp tính toán của bài toán tìm luồng cực đại trong mạng G(k).