Một số phương pháp giải bài toán cái túi

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 45 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: Một số phương pháp giải bài toán cái túi

Một số phương pháp giải bài toán cái túi

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan

Một số phương pháp giải bài toán cái túi ng, có nhiéu kíp bài toán d-ợc nghiên cứu tỷ mỷ hơn vé mạt định tính (điểu kiện tổn tại nghiệm, điều kiện cán và đú tối - u. ...) lân mặt xây dựng các

thuật toán hữu hiệu đế giòi quyết chúng trên các máy tính điện tử và máy vi tinh. Vì vậy tối - u hóa là lình vực cùa toán học nghiên cứu lý thuyết và Một số phương pháp giải bài toán cái túi

thuật (oán giái các bài toán cực trị ngày càng đ-ợc phát triển và ứng dụng nhiều trong đời sống, khoa học kỹ thuật.Bài toán cái túi là bài toán làm c

Một số phương pháp giải bài toán cái túi

ục đại (cực tiểu) cùa hàm mục tiêu tuyến tính trong số nguyên không âm với mọi ràng buộc tuyến tính dạng đẳng thức hoặc bất đẵng thức. Bài toán cái tú

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan

Một số phương pháp giải bài toán cái túi mọi bài toán quy hoạch nguyên tuyến tính với biến sò' giới nội đều có thể đ- a về bài toán cái túi và để giải bài toán cái túi có (hể sử dụng những th

uật toán t-ơng dôi hữu hiệu. Do đó chúng tôi đã chọn đề tài "Một so phương pháp giãi bài toán cái túiũTrong phạm vi cùa khoa luận tôt nghiệp, chúng tô Một số phương pháp giải bài toán cái túi

i chí dam nêu mục đích cùa đề tài đ- a ra bài toán cái túi và một sò' ph- ơng pháp để giãi bài toánKhoá luận đ-ợc chia thành 2 ch-ơng:Ch- ơng I: Trình

Một số phương pháp giải bài toán cái túi

bày bãi toán cái túi,mô hình bài toan và ph- ơng pháp đ-a bài toán quy hoạch nguyên vé bài toan cái (úi.Ch-ơng 2: Trình bày một sô' ph-ơng pháp để gi

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan

Một số phương pháp giải bài toán cái túi giáo Th.s. Nguyền Illi Thanh Hiền và sự góp ý giúp đỡ cùa các tháy, cô giáo trong tổ Xác suất thòng kẻ vù Toan úng1dụng trong khoa toán. Nhân dịp này

tôi xin bày tò lõng biết ơn chân thành đến cô, các thầy, cổ giáo trong khoa Toán và bạn bẽ đã tạo điều kiên giúp đờ trong quá trình học tập và hoàn t Một số phương pháp giải bài toán cái túi

hành kỉioá luận nayDo thời gian và khá nang có hạn cua tác già. khoá luân không tránh khói những thiếu sót. Rat mong sự góp ý cùa thầy, có giáo vã các

Một số phương pháp giải bài toán cái túi

bạn.Tôi xin chân thành câm ơn.Vinh, tháng 5- 2008.Tác già.2Ch- ong 1BẢI TOÁN CÁI TÚ1.1.Bài toán1.1.1.Bài loán. MỘI ng-ời đi du lịch cần mang Ihco mội

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan

Một số phương pháp giải bài toán cái túi là C;(j=l./Ỉ). lĩoi ng-ời này cần mang theo các loại dó vật nào và với số l-ựng bao nhiêu dể tổng giá trị sử dụng cua các dổ vật mang theo là lớn nhấ

t?1.1.2 . Mo hình toán học. Ta cán tìm sô' dó vật d- ợc xếp vào túi sao cho tổng giá trị dổ vật mang theo là lớn nhất.Gọi X, là so đổ vật loại J (j=l. Một số phương pháp giải bài toán cái túi

n ) d- ực xếp vào túi. Khi dó mõ hình toán học cùa bài toán có dạng sau đây:5=1r È«;x 0 và nguyên , j = 1. n.Bài toán này là bài toán quy hoạ

Một số phương pháp giải bài toán cái túi

ch tuyến tính nguyên và mọi bài toán quy hoạch nguyên tuyên tính với biến số giới nội déu có thê d-a về bài toán cái lúi. đe giái bài loán cái lúi có

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan

Một số phương pháp giải bài toán cái túi hoá lù ph- ưng pháp đ- a hệ các ph- ưng trình luycn tính với các hệ sô' và biên số nguyên vé một ph- ong trình ĩ- ưng d- ưng Là tổ hợp luyến lính cua

các ph-ưng trình đa cho. Từ hựp nhái hoá chúng la có ph-ơng pháp khá hiệu qua đẽ giái bài loán cái lúi.3Ph- ơng pháp hợp nhất hoá đ-ợc xây dựng dựa t Một số phương pháp giải bài toán cái túi

rên cơ sớ định lý sau đây:1.2.1.Định lý. Nèíi nh- tj, t2 lờ hơi sốnguyên tố cùng nhơn ( ký hiệu lờ(tj, hl-l I tin niọi nghiệm nguyên cúơ ph- ơng trình

Một số phương pháp giải bài toán cái túi

Z/-.V;=0(1-1)dều có thè biêu diễn d- ới dự/igyt=-(f-f2-y2=dfj

LÒI NÓIĐẦUNgày nay. do sự phát triển mạnh mè của các ph- ong tiện tính toán và nhu cầu về việc giòi các bài toán tối - u trong thực tiễn ngày càng tan