ứng dụng luồng cực đại trong bài toán tối ưu rời rạc
Đức Trọng
I. Bài toán
Xétbài toán:
Trongđó a
ij
thuộc {0,1}
p
i
nguyên dương
i = 1,2,…,m;
j = 1,2,…,n
Bài toán trên là mô hình toán học của nhiều bàitoán tối ưu tổ hợp trong thực tế. Ví dụ:
II. Vídụ
1. Bài toán phânnhó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êni có nguyện vọng tham gia vào nhóm j
- a
ij
=0, nếu ngượclại
- p
i
là số lượngnhó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ảitham gia đúng p
i
nhóm, hãy tìm cách phân phối với số
người trong nhómcó nhiều sinh viên tham gia nhất là nhỏ nhất có thể được.

Bổ đề 1:
Bài toán (1)-(2) có nghiệm tối ưu khi và chỉ khi:
Chứng minh:
Điều kiện cần là hiển nhiên vì sự tồn tại phương án của bàitoán suy ra bất đẳng thức trong
(3) được thực hiện ít nhất dưới dạng dấu đẳngthức.
Điều kiện đủ: Chỉ cần chỉ ra rằng nếu có (3) thì luôn có phươngán.
Giả sử (3) đúng, gọi:
Do(3) là điều kiện để (1)-(2) có nghiệm nên trong phần tiếp theo ta luôngiả thiết rằng điều
kiệnđược thực hiên.
Bâygiờ ta chỉ ra rằng bài toán (1)-(2) có thể chuyển về giải một số hữuhạn bài toán luồng
cực đại trong mạng. Trước hết với mỗi k nguyêndương ta xây dựng mạng G
(k)
= (V,E) với
e thuộc E:khả năng thông qua c(e)
c(s,u
i
) = p
i

c(u
i
,v
j
) = a
ij

c(v
j
,t) = k
Bổđề 2: Giả sử vớik nào đó luồng cực đại trong mạng G

trong 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ồngvới giá trị Δ trong mạng G
(k*)
.
Ta xây dựng luồng Φ như sau:
Dễ dàng chứng minh Φ là luồng trong mạng G
(m)
có giá trị Δ.(đpcm)
Bổđề 4:
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ự bổ đề 3 ta chỉ cần chỉ ra luồng với giátrị Δ trong mạng G
(m)
.
Thậtvậy, giả sử x* là nghiệm bài toán (1)-(2) được xây dựngtheo công thức như bổ đề 1,
xây dựng Φ theo bổ đề 3 ta có luồng giá trị Δ.(đpcm)
IV. Thuậttoán:
Từ nhận xét 2 và 3 suy ra việc giải bài toán (1)-(2) là tìm k*nguyên dương nhỏ nhất sao
cho luồng cực đại trong mạng G
(k*)
có giá trị Δ.Nhận xét 4 giới hạn giá trị k* thuộc [1,m].
Từ đây rút ra thuật toán: áp dụng phương pháp chia nhị phântrên đoạn [1,m] tìm k* trong
mỗi bước giải bài toán tìm luồngcực đại trong.

Delta:=0;
For i:=1 to m do begin
read(fi,p[i]);
Delta:=Delta+p[i];
End;
For i:=1 to m do
For j:=1 to n do read(fi,a[i,j]);
Close(fi);
s:=m+1;t:=n+1;
For i:=1 to m do a[s,i]:=p[i];
End;
FunctionFindPath:Boolean;
Var
Queue:Array[1..100]of Integer;
i,j,First,Last,v:Integer;
Begin
Fillchar(TraceX,Sizeof(TraceX),0);
Fillchar(TraceY,Sizeof(TraceY),0);
First:=1;Last:=0;
For i:=1 to m do
If x[s,i]
inc(last);
Queue[last]:=i;
traceX[i]:=-1;
end;
While First<=Last do Begin
i:=Queue[First];Inc(first);
For j:=1 to n do
If (traceY[j]=0)and(x[i,j]
traceY[j]:=i;