Thạc Sĩ Phương pháp Hungari giải bài toán giao việc tuyến tính và mở rộng

2
MỤC LỤC

Trang
LỜI NÓI ĐẦU 2
Chương 1. PHƯƠNG PHÁP HUNGARI VÀ BÀI TOÁN GIAO VIỆC 4
1.1. Bài toán giao việc 4
1.2. Phương pháp Hungari 8
1.3. Ví dụ áp dụng 12
1.4. Bài toán tìm cực đại 15
Chương 2. PHƯƠNG PHÁP THU HẸP CHÍNH TẮC 18
2.1. Bài toán vận tải tuyến tính 18
2.2. Phương pháp thu hẹp chính tắc 21
2.4. Ví dụ minh họa 27
KẾT LUẬN 31
TÀI LIỆU THAM KHẢO 32







Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

3
LỜI NÓI ĐẦU

Bài toán giao việc (Assignment Problem) là một trường hợp riêng quan
trọng của bài toán qui hoạch tuyến tính và có quan hệ gần gũi với bài toán vận
tải (Transportation Problem) và bài toán người du lịch (Traveling Salesman
Problem) trong tối ưu tổ hợp và lý thuyết đồ thị. Bài toán giao việc có nhiều
ứng dụng thiết thực, đa dạng trong thực tiễn và luôn là chủ đề hấp dẫn của tối
ưu hóa. Hiện vẫn có nhiều nghiên cứu đề cập tới bài toán giao việc nhằm tổng
quát và mở rộng phạm vi ứng dụng của bài toán.
Phương pháp Hungari (Hungarian Method) rất độc đáo và hiệu qủa để
giải bài toán giao việc. Tên gọi của phương pháp là để tưởng nhớ hai nhà toán
học Hungari: König và Egeváry, đã có công đầu tạo ra cơ sở lý luận cho
phương pháp. Harold W. Kuhn là người đã phát triển và công bố phương
pháp này năm 1955 (xem [6]).
Phương pháp Hungari đã trở nên quen thuộc, được dùng rộng rãi và có
thể mở rộng cho nhiều bài toán khác của qui hoạch tuyến tính, trong đó có bài
toán vận tải mà thuật toán "thu hẹp chính tắc" là một dạng mở rộng như thế.
Luận văn "Phương pháp Hungari giải bài toán giao việc tuyến tính và
mở rộng" nhằm mục đích tìm hiểu bài toán giao việc với hàm mục tiêu tuyến
tính và các ứng dụng của bài toán; Phương pháp Hungari giải bài toán giao
việc tuyến tính và phương pháp "thu hẹp chính tắc" giải bài toán vận tải (ở
dạng ma trận) của qui hoạch tuyến tính.
Luận văn được trình bày trong hai chương.
Chương 1 "Phương pháp Hungari và bài toán giao việc" trình bày nội
dung bài toán giao việc với hàm mục tiêu tuyến tính và một số ứng dụng của
bài toán, đồng thời đề cập tới một số bài toán có liên quan: Bài toán vận tải và
bài toán người du lich. Tiếp đó, luận văn trình bày phương pháp Hungari quen
thuộc giải bài toán và các ví dụ minh họa. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

4
Chương 2 "Phương pháp thu hẹp chính tắc" đề cập tới bài toán vận tải
với hàm mục tiêu tuyến tính, một dạng mở rộng của bài toán giao việc tuyến
tính (khi vế phải nguyên, khác 1) và trình bày phương pháp "thu hẹp chính
tắc" do Giả sử Hoàng Tụy đưa ra trong [3] (có chung ý tưởng với phương
pháp Hungari) để giải bài toán.Luận văn đã nêu các ví dụ minh họa cho thuật
toán giải đã trình bày. Phân tích quan hệ giữa phương pháp thu hẹp chính tắc
với phương pháp Hungari và một số phương pháp giải khác có cùng ý tưởng.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn
có những thiếu sót nhất định, kính mong quí thầy, cô và các bạn đóng góp ý
kiến để tác giả tiếp tục hoàn thiện luận văn sau này.
Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS - TS
Trần Vũ Thiệu, người đã tận tình giúp đỡ trong suốt quá trình làm luận văn.
Tác giả chân thành cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học -
Đại học Thái Nguyên, Viện Toán hoc - Viện Hàn lâm Khoa học và Công
nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác
giả học tập và nghiên cứu.