Cặp ghép trong lập trình pascal

Cặp Ghép

Lê Văn Chương

Định nghĩa cặp ghép

Xét hai tập hữu hạn X, Y gồm n phần tử:

X= {x1, x2,...,xn}

Y= {y1, y2,...,yn}

Cặp phần tử (x,y) với x thuộc X, y thuộc Y được gọi là một cặpghép. Hai cặp ghép (x,y) và

(x', ý) được gọi là rời nhau nếu x # x' và y # ý.Tập M gồm các cặp ghép rời nhau được gọi

là một tập cặp ghép.

{ Thông thường bài toánxây dựng các cặp ghép được tiếp cận theo 2 hướng hoặc thỏa mãn

một điều kiệnghép cặp nào đấy, khi đó người ta quan tâm đến khả năng ghép cặp tối đa,

hoặclượng hoá việc ghép cặp, khi đó người ta quan tâm đến phương án ghép cặp tối

ưutheo các giá trị đã lượng hoá. }

Vì số tập cặp ghép là hữu hạn, nên một phương pháp xây dựngđơn giản là thử tất cả các

khả năng. Tuy nhiên, số khả năng như vậy là rất lớn.Vì thế, phải tìm kiếm những thuật giải

thật hữu hiệu, dễ cài đặt chương trìnhvà có tính khả thi cao.

Bài toán tìm cặp ghép đầy đủtối ưu

a. Giới thiệu bài toán:Bài toán tìm cặp ghép đầy đủ tối ưu có nhiều mô hình ứng dụng thực

tế.Một trong những mô hình này là người ta quan tâm đến việc ghép cặp sao cho cóhiệu

quả nhất.

Để lượng hoá việc ghép mỗi phần tử x thuộc X với một phần tử y thuộc Y,người ta đưa

vào ma trận số Cij (i,j = 1, 2,..., n) với ý nghĩa Cijmô tả hiệu quả của việc ghép xi với yj. Bài

toán được đặtra là: Xây dựng một tập cặp ghép đầy đủ có tổng hiệu quả lớn nhất.

Bài toán vừa nêu thường được phát biểu dưới dạng một mô hìnhthực tế là bài toán phân

công:

Bài toán phân công: Cón người và n công việc. Biết Cij là số tiền làm ra nếu giao

côngviệc j cho người i thực hiện. Hãy tìm cách phân công mỗi người mỗi việc để tổngsố

tiền làm ra là lớn nhất.

b. Định lý về cặp ghép: Việcxây dựng tập cặp ghép đầy đủ tối ưu dựa vào dấu hiệu nhận

biết một tập cặp ghépđầy đủ khi nào là tối ưu. Dĩ nhiên việc thử dấu hiệu này không phải