40 bài toán tối ưu thực tế có lời giải chi tiết là tài liệu vô cùng hữu ích mà Download.vn muốn giới thiệu đến quý thầy cô cùng các bạn học sinh lớp 12, ôn thi THPT Quốc gia 2019 cùng tham khảo.
Với tài liệu này, các bạn học sinh lớp 12 sẽ ngày càng học tập tốt hơn, quý thầy cô có được những tiết giảng bài hay và chất lượng. Sau đây là nội dung chi tiết, mời các bạn cùng tham khảo và tải tài liệu tại đây.
Bài toán tối ưu thực tế có đáp án
Download
- Lượt tải: 384
- Lượt xem: 3.466
- Phát hành:
- Dung lượng: 6,4 MB
. của bài toán min và bài toán max thỏa điều kiện f[X] = g[Y]. Vậy X, Y là phương án tối ưu của bài toán min và bài toán max. Bài tập Đối ngẫu LẬP BÀI TOÁN ĐỐI NGẪU VÀ TÌM LỜI GIẢI Bài 1 Cho bài. án tối ưu: X′ min = 0 12 7 0 14 15 3 0 21 0 0 0 12 0 0 Phương án tối ưu X′ min khác phương án tối ưu X min tại bảng 2. Vậy, bài toán không duy nhất phương án tối ưu. . [j 1,5] = 1] Giải bài toán trên. Phương án tối ưu, nếu có, có duy nhất không? 2] Hãy viết bài toán đối ngẫu và cho biết lời giải của bài đối ngẫu. Phương án tối ưu của bài đối ngẫu, nếu có,
Xem thêm: TỔNG HỢP BÀI TẬP TỐI ƯU HÓA [full], TỔNG HỢP BÀI TẬP TỐI ƯU HÓA [full]
Trong khoa học máy tính và toán học, bài toán tối ưu hóa là bài toán tìm kiếm lời giải tốt nhất trong tất cả các lời giải khả thi. Bài toán tối ưu hóa có thể được chia thành hai loại tùy thuộc vào việc các biến là liên tục hay rời rạc. Bài toán tối ưu hóa với các biến rời rạc còn được gọi là một bài toán tối ưu hóa tổ hợp. Trong một bài toán tối ưu hóa tổ hợp, chúng ta tìm kiếm một đối tượng như là một số nguyên, hoán vị hay đồ thị từ một tập hợp hữu hạn [hoặc có thể là vô hạn đếm được]. Bài toán với các biến liên tục bao gồm bài toán hạn chế và bài toán đa phương thức.
Bài toán tối ưu hóa liên tục[sửa | sửa mã nguồn]
Dạng tiêu chuẩn của một bài toán tối ưu hóa [liên tục] là
trong đó
Theo quy ước, dạng tiêu chuẩn xác định một bài toán cực tiểu hóa. Bài toán cực đại hóa có thể được giải bằng cách phủ định hàm mục tiêu.
Bài toán tối ưu hóa tổ hợp[sửa | sửa mã nguồn]
Chính thức, là một bài toán tối ưu hóa tổ hợp là một bộ tứ , trong đó
Mục tiêu là sau đó tìm ra một số trường hợp một lời giải tối ưu, có nghĩa là, là một lời giải khả thi
Đối với mỗi bài toán tối ưu hóa tổ hợp, có một bài toán quyết định tương ứng yêu cầu cho dù đó có là một lời giải khả thi đối với một số biện pháp cụ thể . Ví dụ, nếu có một đồ thị chứa các đỉnh và , một bài toán tối ưu hóa có thể là "tìm một đường đi từ tới sử dụng các cạnh ít nhất". Bài toán này có thể có một câu trả lời, đó là, 4. Một bài toán quyết định tương ứng sẽ là "một đường đi từ tới mà sử dụng 10 cạnh hoặc ít hơn?" Bài toán này có thể có được câu trả lời đơn giản hoặc là 'có' hoặc là 'không'.
Trong lĩnh vực thuật toán xấp xỉ, các thuật toán được thiết kế để tìm các lời giải gần tối ưu cho các bài toán khó. Phiên bản quyết định bình thường sau đó là một định nghĩa không đầy đủ về bài toán này kể từ khi nó chỉ xác định các lời giải chấp nhận được. Mặc dù chúng ta có thể giới thiệu các bài toán quyết định phù hợp, bài toán này được mô tả đặc điểm tự nhiên hơn như là một bài toán tối ưu hóa.
Bài toán tối ưu hóa NP[sửa | sửa mã nguồn]
Bài toán tối ưu hóa NP [NPO-"NP optimization"] là bài toán tối ưu hóa tổ hợp với các điều kiện bổ sung sau. Lưu ý rằng các đa thức dưới đây là các hàm kích thước của đầu vào của các hàm tương ứng, không phải là kích thước của một số tập hợp ẩn của các trường hợp đầu vào.
Điều này ngụ ý rằng bài toán quyết định tương ứng thì nằm trong NP. Trong khoa học máy tính, các bài toán tối ưu hóa thú vị thường có những đặc tính trên và cho nên đó là những bài toán NPO. Một bài toán ngoài ra còn được gọi là một bài toán tối ưu hóa-P [PO], nếu có tồn tại một thuật toán mà tìm các lời giải tối ưu trong thời gian đa thức. Thông thường, khi đối phó với lớp NPO, thứ được quan tâm trong các bài toán tối ưu hóa mà các phiên bản quyết định là NP-đầy đủ. Lưu ý rằng các quan hệ độ cứng luôn đối với một số phép suy giảm nào đó. Do sự kết hợp giữa các thuật toán xấp xỉ và các bài toán tối ưu hóa máy tính, các suy giảm duy trì xấp xỉ trong một số khía cạnh là dành cho đối tượng này được ưu tiên hơn so với mức giảm Turing và Karp thông thường. Một ví dụ về việc giảm như vậy sẽ giảm L. Vì lý do này,vấn đề tối ưu hóa với các phiên bản quyết định hoàn chỉnh NP không được gọi là hoàn chỉnh NPO.
NPO được chia thành các phân lớp sau tùy theo tính xấp xỉ được của chúng:
- NPO[I]: Tương đương với FPTAS. Chứa bài toán xếp ba lô.
- NPO[II]: Tương đương với PTAS. Chứa bài toán lịch Makespan.
- NPO[III]: Lớp của các bài toán NPO có các thuật toán thời gian đa thức sẽ tính toán các lời giải với chi phí ở hầu hết chi phí tối ưu c lần [đối với các bài toán cực tiểu hóa] hoặc một chi phí tối thiểu bằng chi phí tối ưu [fđối với các bài toán cực đại hóa].Trong cuốn sách của Hromkovič, đã loại trừ trong lớp này đều là các bài toán NPO [II] được lưu nếu P = NP. Nếu không có sự loại trừ, tương đương với APX. Chứa MAX-SAT và số liệu TSP [bài toán người bán hàng].
- NPO[IV]: Lớp các bài toán NPO với các thuật toán thời gian đa thức xấp xỉ lời giải tối ưu bởi một tỷ lệ đó là đa thức trong một logarit của kích thước đầu vào. Trong cuốn sách của Hromkovic, tất cả các bài toán NPO [III] được loại trừ lớp này trừ khi P = NP. Chứa bài toán bao gói tập hợp.
- NPO[V]: Lớp của các bài toán NPO với các thuật toán thời gian đa thức xấp xỉ lời giải tối ưu bởi một tỷ lệ giới hạn bởi một số hàm trên n. Trong cuốn sách của Hromkovic, tất cả các bài toán NPO [IV] được loại trừ lớp này trừ khi P = NP. Chứa hai bài toán TSP và Nhóm cực đại.
Một lớp quan tâm khác là NPOPB, NPO với các hàm chi phí đa thức bị chặn. Các bài toán với điều kiện này có nhiều tính chất mong muốn.
Xem thêm[sửa | sửa mã nguồn]
Mục tiêu là sau đó tìm ra một số trường hợp một lời giải tối ưu, có nghĩa là, là một lời giải khả thi
- Semi-infinite programming
- Bài toán quyết định
- Bài toán tìm kiếm
- Counting problem [complexity]
- Function problem
Tham khảo[sửa | sửa mã nguồn]
- Boyd, Stephen P.; Vandenberghe, Lieven [2004].
- Ausiello, Giorgio; et al. [2003], Complexity and Approximation [Corrected ed. ^ Hromkovic, Juraj [2002], Algorithmics for Hard Problems, Texts in Theoretical Computer Science [2nd ed.