D1 · Decision Mathematics 1

Toán ra quyết định 1 (D1, đề WDM01/01, 1 giờ 30 phút, 75 điểm, đánh giá lần đầu tháng Sáu 2019) là phần tùy chọn rời rạc của IAL: P1–P2 được giả định, và mỗi phương pháp đều là định dạng yêu cầu. Tài liệu tham khảo này bao gồm các thuật toán sắp xếp và đóng gói, cây bao trùm tối thiểu, đường đi ngắn nhất, bài toán bưu chính viên Trung Quốc và bài toán người bán hàng du lịch, phân tích đường đi quan trọng và quy hoạch tuyến tính. Quy tắc nhà cho câu trả lời thuật toán: phân tích và quy hoạch tuyến tính.

Quy tắc nhà cho câu trả lời thuật toán:

Sắp xếp bong bóng so sánh các phần tử kề nhau, hoán đổi các cặp sai thứ tự, thực hiện một lượt một lúc; một lượt không có sự hoán đổi sẽ kết thúc. Quick sort chọn phần tử TRUNG GIỮA trong danh sách làm mốc, phân chia các phần tử còn lại thành nhóm "nhỏ hơn mốc", "bằng mốc" và "lớn hơn mốc" (giữ lại mọi bản sao); sắp xếp đệ quy theo thứ tự tăng dần hai nhóm nhỏ hơn và lớn hơn — luôn trích dẫn mốc và sau mỗi lần phân chia. Chương trình học quy định việc chọn phần tử giữa phải theo phương pháp được định nghĩa trong từ điển chuyên ngành, vì vậy các danh sách bài tập ở đây phải giữ số lượng phần tử là số lẻ và phần tử giữa là phần tử tại vị trí $\tfrac{n+1}2$. Đóng thùng: first-fit đặt mỗi phần tử vào thùng đầu tiên còn chỗ trống; first-fit decreasing sắp xếp các phần tử từ lớn đến nhỏ rồi áp dụng first-fit; đóng thùng đầy tìm kiếm các tổ hợp lấp đầy chính xác một thùng.

Ví dụ minh họa — quick sort (bản gốc). Sắp xếp 9, 2, 7, 5, 3, 4, 6. Phần tử giữa (vị trí 4 của 7) là 5: nhỏ hơn = 2, 3, 4; lớn hơn = 9, 7, 6, cho 2, 3, 4, 5, 9, 7, 6. Danh sách con 2, 3, 4 (chốt 3): 2, 3, 4 — đã sắp xếp. Danh sách con 9, 7, 6 (chốt 7): 6, 7, 9 — đã sắp xếp. Danh sách cuối cùng: 2, 3, 4, 5, 6, 7, 9.

Ví dụ có lời giải — bài toán đóng gói thùng (gốc). Thùng chứa dung tích 10; các vật phẩm 7, 5, 4, 3, 6, 2 (tổng 27, nên cần ít nhất 3 thùng). Đưa vào lần đầu: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): các thùng (7,3), (5,4), (6,2). Đưa vào giảm dần lần đầu: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): các thùng (7,3), (6,4), (5,2) — cũng là 3 thùng.

Một cây bao phủ tối thiểu (MST) kết nối mọi đỉnh với tổng trọng số nhỏ nhất. Thuật toán Kruskal: sắp xếp các cạnh theo trọng số, thêm cạnh nhỏ nhất không tạo thành chu trình (từ chối và chuyển sang cạnh khác khi sẽ tạo chu trình). Thuật toán Prim: mở rộng một cây từ bất kỳ đỉnh bắt đầu nào, liên tục thêm cạnh rẻ nhất từ cây đến một đỉnh mới. Dạng ma trận của Prim: gạch bỏ hàng bắt đầu, khoanh ô giá trị nhỏ nhất còn lại trong cột của đỉnh đã chọn, và tiếp tục. Kruskal điều khiển bởi cạnh (tốt cho mạng vẽ); Prim điều khiển bởi đỉnh (tốt cho ma trận). Cả hai đều cho cùng tổng; các cạnh chỉ khác nhau khi trọng số bằng nhau. mạng); Prim là thuật toán theo đỉnh (tốt trên ma trận). Cả hai đều cho tổng như nhau; cạnh có thể khác nhau chỉ khi trọng số bằng nhau.

Ví dụ hướng dẫn (gốc). Cạnh AB 4, AC 2, BC 3, BD 5, CD 1: Kruskal chọn CD 1, AC 2, BC 3 (B nối — không tạo chu trình), sau đó loại bỏ AB 4 và BD 5 (tạo chu trình): tổng MST 6. Prim từ A: AC 2, CD 1 (cạnh rẻ nhất từ {A,C} đến một đỉnh mới), CB 3: cùng một cây, và tổng 6 ✓. Luôn liệt kê các cạnh theo thứ tự đã chọn và đưa ra tổng.

Đối với trọng số cạnh không âm, thuật toán Dijkstra gắn nhãn cho các đỉnh với tổng khoảng cách nhỏ nhất tìm được đến thời điểm đó: đỉnh bắt đầu có nhãn 0; liên tục chọn đỉnh chưa có nhãn tạm thời có giá trị nhỏ nhất, chuyển nó thành nhãn vĩnh viễn, và cập nhật các đỉnh lân cận (mới = vĩnh viễn + trọng số, chỉ nếu nhỏ hơn). Ghi lại thứ tự trở thành vĩnh viễn và các nhãn cuối cùng; tuyến đường được khôi phục bằng cách truy ngược qua các đỉnh có nhãn bằng nhãn cuối cùng trừ đi trọng số cạnh nối.

Ví dụ minh họa (bản gốc). Các cạnh AB 4, AC 2, BC 1, BD 5, CD 8. Nhãn: A = 0 vĩnh viễn; C = 2 vĩnh viễn; B = min(4, 2+1) = 3 vĩnh viễn; D = min(3+5, 2+8) = 8 vĩnh viễn. Tuyến đường ngắn nhất từ A đến D có độ dài 8: A–C–B–D (truy ngược: 8 = 3 + 5 tại B, 3 = 2 + 1 tại C).

Bài toán kiểm tra tuyến (bưu kiện Trung Hoa) yêu cầu traversing mọi CẠNH ít nhất một lần và quay về điểm xuất phát. Tổng độ dài = tổng tất cả các cạnh + cách ngắn nhất để bổ sung các cạnh sao cho mọi đỉnh đều có bậc chẵn. Tìm các đỉnh lẻ (tối đa bốn), liệt kê các cặp ghép của chúng, chọn cặp ghép có tổng trọng số nhỏ nhất, và nhân đôi những cạnh đó. Nêu cặp ghép trước khi tính tổng.

Ví dụ minh họa (bản gốc). Các cạnh AB 4, AC 2, BC 3, BD 5, CD 1 (tổng 15). Bậc: A 2, B 3, C 3, D 2 — các đỉnh lẻ là B và C, nên nhân đôi BC (trọng số 3): tuyến đóng ngắn nhất traversing mọi cạnh ít nhất một lần có độ dài 15 + 3 = 18.

Bài toán người bán hàng du lịch cổ điển đi qua mỗi ĐỈNH đúng một lần và trả về, trên đồ thị đầy đủ có bất đẳng thức tam giác. Bound: MST của mạng gấp đôi là đường đi đường biên trên (duyệt mỗi cạnh MST hai lần); đường tắt mang lại đường biên trên tốt hơn. Đường biên dưới đến từ lập luận dựa trên MST (ví dụ: MST cây bao trùm tối thiểu, hoặc xóa một đỉnh và thêm hai cạnh rẻ nhất của nó). Thuật toán hàng xóm gần nhất xây dựng một hành trình: từ đỉnh xuất phát liên tục di chuyển đến đỉnh chưa thăm gần nhất, sau đó quay về. Chuyển đổi sang mạng đầy đủ khoảng cách ngắn nhất trước khi đồ thị không đầy đủ (thông qua thuật toán Dijkstra hoặc quan sát).

Ví dụ tính toán (bản gốc). Mạng đầy đủ: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (điều bất đẳng thức tam giác được thỏa mãn trong suốt). Hàng xóm gần nhất từ A: A–C (2), C–B (3), B–D (5), D–A (7): độ dài hành trình 17 — một giới hạn trên. Cây bao trùm tối thiểu là AC + BC + BD = 10, do đó nhân đôi nó cho ra giới hạn trên thô sơ 20, được cải thiện thành 17 bằng các đoạn shortcut; một giới hạn dưới từ việc xóa A (cây bao trùm tối thiểu của B, C, D là 3 + 5 = 8, cộng với hai cạnh rẻ nhất của A là AC + AB = 2 + 4 = 6) là 14. Hành trình tối ưu nằm giữa 14 và 17.

Mô hình hóa dự án thành một mạng hoạt động trên cung từ bảng thứ tự thực hiện; cung giả (cung trọng số không) giải quyết các phụ thuộc mà các điểm đầu chung không thể biểu diễn. Đường găng là chuỗi dài nhất xuyên qua mạng: thời gian hoàn thành dự án. Tính toán thời điểm sự kiện sớm nhất (lặp tiến: giá trị lớn nhất của sự kiện đến) và thời điểm sự kiện muộn nhất (lặp lùi: giá trị nhỏ nhất của sự kiện đi). Tổng thời gian linh hoạt của một hoạt động = thời điểm kết thúc muộn nhất − thời điểm bắt đầu sớm nhất − thời lượng; đường găng các hoạt động có độ trễ bằng không. Biểu đồ Gantt (thác) biểu diễn từng hoạt động dưới dạng thanh bắt đầu từ thời điểm sớm nhất với độ trễ được thể hiện như khoảng trống phía sau; lập lịch phân bổ lao động ngày một ngày hai. bắt đầu sớm nhất kèm theo thời gian linh hoạt dưới dạng khoảng trắng ở cuối; phân công lịch trình giao người lao động từng ngày.

Ví dụ minh họa (gốc). Các hoạt động A (3 ngày), B (4), C (4 sau A), D (1 sau B), E (5 sau C và D). Chuỗi A–C–E = 12 ngày; chuỗi B–D–E = 10 ngày: đường găng là A–C–E và dự án mất 12 ngày; độ trễ toàn phần của D = 12 − (4 + 1 + 5) = 2 ngày.

Xây dựng mô hình: xác định các biến quyết định, viết hàm mục tiêu (tối đa/tối thiểu) và mọi ràng buộc dưới dạng bất phương trình, bao gồm $x, y \ge 0$. Giải bài toán hai biến bằng đồ thị: b tô vùng khả thi, sau đó sử dụng phương pháp thước kẻ (di chuyển thước dọc theo hệ số góc của hàm mục tiêu) hoặc phương pháp đỉnh (xét giá trị hàm mục tiêu tại mỗi đỉnh của vùng khả thi). Nghiệm nguyên: kiểm tra các điểm nguyên gần đỉnh tối ưu nằm trong vùng khả thi.

Ví dụ minh họa — quy hoạch tuyến tính (bản gốc). Tối đa hoá $P = 3x + 2y$ với các ràng buộc $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. Các đỉnh của miền khả thi là $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; đánh giá $P$: 0, 21, 24, 20 — giá trị lớn nhất là $P = 24$ tại $(4,6)$, nơi cả hai ràng buộc đều đạt giá trị bằng nhau.

• Thực hiện sắp xếp bong bóng và sắp xếp nhanh hiển thị từng lượt duyệt và điểm chia; đóng gói thùng theo first-fit, first-fit decreasing và full-bin với vị trí đặt hàng hóa được thể hiện rõ.
• Tìm cây bao trùm nhỏ nhất (MST) bằng thuật toán Kruskal và Prim (dạng nút và dạng ma trận); vẽ mạng lưới từ ma trận và ngược lại.
• Thực thi thuật toán Dijkstra với nhãn theo thứ tự cố định; khôi phục tuyến đường, không chỉ độ dài.
• Giải bài toán kiểm tra tuyến: các nút lẻ, tất cả các cặp ghép có trọng số, lượng sao chép tối thiểu, tổng chiều dài tuyến đi.
• Bound bài toán TSP cổ điển: MST nhân đôi và đường tắt cho cận trên, xóa MST cho cận dưới; chạy thuật toán lân cận gần nhất trên mạng lưới khoảng cách ngắn nhất đầy đủ.
• Xây dựng mạng lưới hoạt động với các hoạt động giả; lượt đi trước và lượt đi sau để tính thời điểm sự kiện; độ trễ toàn phần; xác định đường găng; vẽ biểu đồ Gantt và lập lịch.
• Xây dựng đầy đủ bài toán quy hoạch tuyến tính; giải bằng phương pháp đồ thị dùng thước kẻ hoặc phương pháp đỉnh; tìm nghiệm nguyên tốt nhất.