- THUẬT TOÁN QUY HOẠCH ĐỘNG CHO BÀI TOÁN XẾP BA LÔ CÂN BẰNG {0,1}. - Bài toán cân bằng, bài toán xếp ba lô, quy hoạch động. - Trong bài báo này, một biến thể của bài toán tối ưu cân bằng với ràng buộc có dạng xếp ba lô được nghiên cứu. - Để giải quyết bài toán, một cấu trúc đặc biệt của tập các phương án chấp nhận được chỉ ra. - Dựa vào đó, một thuật toán quy hoạch động được đề xuất để giải bài toán đã nêu trong thời gian đa thức.. - Thuật toán quy hoạch động cho bài toán xếp ba lô cân bằng {0,1}. - Tối ưu tổ hợp đóng một vai trò quan trọng trong lĩnh vực vận trù học với những ứng dụng đã được kiểm chứng trong thực tế. - Một số hướng nghiên cứu quan trọng của tối ưu tổ hợp là bài toán quy hoạch tuyến tính (Kamarkar et al., 1989. - Danzig and Thapa, 2003), quy hoạch nguyên (Wolsey et al., 1998), bài toán người bán hàng (Laporte and Martello, 1990. - Zia et al., 2017), bài toán xếp ba lô (Martello and Toth, 1990. - Pisinger et al., 2004), bài toán cây khung tối tiểu (Zhong et al., 2015), bài toán vị trí (Kariv and Hakimi, 1979a, 1979b), bài toán ngược của bài toán vị trí (Nguyen and Vui, 2016. - Nguyen et al., 2019) và một số bài toán tối ưu khác trên mạng lưới đồ thị (Danzig et al., 1959).. - Trong bài báo này, bài toán tối ưu cân bằng với ràng buộc có dạng xếp ba lô được nghiên cứu. - Mô hình của bài toán tối ưu cân bằng (balanced optimization problem) gồm có một tập các dự án, mỗi dự án nếu được triển khai cần đầu tư một lượng vốn tương ứng. - Bài toán đặt ra đó là tìm một tập các dự án để triển khai sao cho độ lệch lớn nhất giữa các chi phí đầu tư là nhỏ nhất. - Một tình huống thực tế khác đó là bài toán xếp ba lô (knapsack problem). - Bài toán này được gọi là bài toán xếp ba lô {0, 1} (Pisinger et al., 2004).. - Mặc dù bài toán xếp ba lô {0, 1} và bài toán tối ưu cân bằng là hai bài toán nổi tiếng trong lĩnh vực tối ưu tổ hợp và cấu trúc của chúng bằng cách này hay cách khác liên quan mật thiết đến nhau nhưng đến giờ mối quan hệ này vẫn chưa được nghiên cứu.. - Bài báo này xem xét một bài toán với mô hình có dạng tổ hợp của hai bài toán trên, gọi là bài toán cân bằng với ràng buộc xếp ba lô. - Mỗi dự án được cho tương ứng với một mức lợi nhuận a i và một mức chi phí đầu tư c i . - Bài toán cân bằng với ràng buộc xếp ba lô sẽ chỉ ra cần đầu tư vào những dự án nào để mức chênh lệch lớn nhất giữa các chi phí đầu tư là nhỏ nhất trong khi vẫn giữ mức tổng lợi nhuận từ các dự án được đầu tư không nhỏ hơn một mức sàn định trước.. - Mô hình bài toán này giúp đảm bảo sự công bằng trong việc góp vốn đầu tư trong khi vẫn đảm bảo lợi ích tổng thể.. - phần 2 giới thiệu những khái niệm mở đầu và định nghĩa của bài toán xếp ba lô {0, 1} và bài toán tối ưu cân bằng nhằm giúp độc giả nắm được mô hình của các bài toán này cũng như ý nghĩa lịch sử của chúng. - phần 3 là kết quả nghiên cứu chính của bài báo, trình bày thuật toán quy hoạch động cho bài toán cân bằng với ràng buộc xếp ba lô. - 2 BÀI TOÁN XẾP BA LÔ {0, 1} VÀ BÀI TOÁN CÂN BẰNG. - Trong phần này, mô hình toán học của bài toán xếp ba lô dạng {0, 1} và bài toán tối ưu cân bằng được gới thiệu và làm rõ ý nghĩa của chúng.. - 2.1 Bài toán xếp ba lô {0, 1}. - Bài toán xếp ba lô (còn được biết đến với tên gọi bài toán cái túi) (knapsack problem) là một bài toán thuộc lĩnh vực tối ưu hóa tổ hợp. - Bài toán này có nhiều phiên bản nhưng đều đề cập đến một vấn đề chung đó là cần chọn những món đồ nào để xếp vào trong một cái ba lô có giới hạn về khối lượng để mang đi sao cho một tiêu chí nào đó được tối ưu (như giá trị, nhu cầu sử dụng. - Bài toán xếp ba lô dạng {0, 1} là bài toán xếp ba lô với số lượng mỗi. - Bài toán được phát biểu dạng toán học như sau:. - Khối lượng tối đa mà ta có thể mang trong ba lô là b . - Bài toán xếp balô {0,1} yêu cầu chọn ra một số đồ vật từ n đồ vật sao cho tổng khối lượng không vượt quá một khối lượng cho trước, đặt là b , và tổng giá trị của các đồ vật được chọn là lớn nhất.. - Bài toán được phát biểu dưới dạng sau:. - 2.2 Bài toán tối ưu cân bằng. - Bài toán đặt ra là tìm tập hợp các chuyến đi sao cho độ chênh lệch thời gian của chuyến đi dài nhất và chuyến đi ngắn nhất được cực tiểu hóa. - Những ví dụ nêu trên với câu hỏi phải phân công như thế nào chính là bài toán gán (assignment. - Một bài toán gán ứng với yêu cầu đạt được sự cân bằng nào đó được gọi là bài toán gán cân bằng. - Bài toán gán cân bằng chính là một dạng đặc biệt của bài toán tối ưu cân bằng.. - Bài toán tối ưu cân bằng (balanced optimization problem) lần đầu tiên được đề xuất bởi Martello et al. - Các tác giả đã chỉ ra rằng bài toán cân bằng có thể giải được trong thời gian đa thức nếu bài toán tối ưu cổ chai tương ứng có thể giải trong thời gian đa thức. - Hơn nữa, các tác giả còn đề xuất một thuật giải cho bài toán gán cân bằng với độ phức tạp. - Một cách tổng quát, bài toán tối ưu cân bằng đề cập đến các vấn đề có mô hình như sau: Giả sử rằng mỗi đối tượng được xem xét của bài toán đều được liên kết với một chi phí cho trước. - Chúng ta mong muốn tìm được một phương án chấp nhận được sao cho độ chênh lệch giữa chi phí cao nhất và chi phí thấp nhất là bé nhất.. - Ta phát biểu lại bài toán dưới dạng toán học. - Bài toán tối ưu cân bằng yêu cầu tìm một phương án chấp nhận được S. - F là nghiệm của bài toán tối ưu:. - 3 BÀI TOÁN CÂN BẰNG VỚI RÀNG BUỘC XẾP BA LÔ VÀ THUẬT TOÁN. - Trong phần này, bài toán tối ưu cân bằng với ràng buộc xếp ba lô được tập trung nghiên cứu. - Xét một bài toán cụ thể với mô hình đầu tư kinh doanh đối với n dự án cho trước. - Bài toán đặt ra đó là cần đầu tư vào những dự án nào sao cho mức chênh lệch lớn nhất giữa các chi phí đầu tư là nhỏ nhất, đồng thời, tổng lợi nhuận từ các dự án được đầu tư không thấp hơn một mức lợi nhuận đã lên kế hoạch trước. - Việc đề xuất một phương án đầu tư như vậy là cần thiết nhằm giảm thiểu tối đa sự chênh lệch trong việc góp vốn đầu tư vào các dự án trong khi vẫn đảm bảo lợi ích tổng thể.. - của E được gọi là một phương án. - Trong bài toán tối ưu cân bằng, yêu cầu đặt ra là tìm một phương án S , làm cực tiểu hóa độ lệch lớn nhất của các chi phí tương ứng với tập S. - Một phương án hữu hiệu là một phương án S có tổng lợi nhuận không nhỏ hơn một số cho trước. - Khi đó bài toán xếp ba lô cân bằng {0, 1} có thể được phát biểu: Tìm một phương án hữu hiệu S làm cực tiểu hóa hàm f S. - Phương án tối ưu là nghiệm của bài toán xếp ba lô cân bằng {0, 1}, hay có thể nói phương án tối ưu là một phương án hữu hiệu làm cực tiểu hàm f S. - Rõ ràng, bài toán là vô nghiệm nếu. - Do đó, từ đây trở về sau ta sẽ giả sử bài toán có nghiệm, nghĩa là. - c £ £¼£ c c Mệnh đề sau đây chỉ ra cấu trúc đặc biệt của một lớp các phương án tối ưu.. - Mệnh đề 2.1 Tồn tại một phương án tối ưu S. - của bài toán xếp ba lô cân bằng {0,1} sao cho nếu. - Cho trước một phương án tối ưu S. - ta xây dựng một phương án. - Khi đó, phương án S ' là phương án hữu hiệu.. - Vậy S ' cũng là phương án tối ưu cho bài toán xếp ba lô cân bằng {0,1}. - Một phương án thỏa điều kiện trong Mệnh đề 2.1 được gọi là phương án đầy đủ, nghĩa là, trong phương án này các phần tử có các giá trị tương ứng nằm trong đoạn từ giá trị bé nhất đến giá trị lớn nhất đều được lựa chọn. - Vậy rõ ràng mỗi phương án đầy đủ S sẽ tương ứng với một cặp chỉ số. - Một phương án đầy đủ ứng với cặp chỉ số. - như vậy sẽ được gọi là phương án đầy đủ tối tiểu.. - Mệnh đề sau đây chỉ ra rằng tồn tại một phương án tối ưu là một phương án đầy đủ tối tiểu.. - Mệnh đề 2.2 Tồn tại một phương án tối ưu của bài toán xếp ba lô cân bằng {0,1} sao cho phương án đó là phương án đầy đủ tối tiểu.. - s } là một phương án tối ưu đầy đủ của bài toán xếp ba lô cân bằng {0,1} và S. - không là một phương án đầy đủ tối tiểu. - S vừa là một phương án tối ưu vừa là một phương án đầy đủ tối tiểu. - Do S * không là một phương án đầy đủ tối tiểu nên s. - S = s là một phương án đầy đủ tối tiểu và tối ưu. - Mệnh đề sau đây chỉ ra rằng các phương án đầy đủ tối tiểu được sắp ‘thứ tự’.. - r s là các phương án đầy đủ tối tiểu sao cho 1. - Trên cơ sở những mệnh đề vừa được chứng minh, chúng ta sẽ xây dựng một thuật toán để giải bài toán tối ưu cân bằng với ràng buộc xếp ba lô.. - Ý tưởng thuật toán:. - Cho bài toán xếp ba lô cân bằng {0, 1} với giả sử i 1. - S r s là một phương án đầy đủ tối tiểu. - n sao cho S. - r s cũng là một phương án đầy đủ tối tiểu. - Cứ tiếp tục như vậy, ta sẽ tìm được tất cả các phương án đầy đủ tối tiểu, S. - f S nhỏ nhất trong số các phương án đầy đủ tối tiểu, ta thu được giá trị tối ưu của bài toán.. - Thuật toán 2.4: Giải bài toán cân bằng {0,1}- knapsack.. - Input: Một bài toán cân bằng {0,1}-knapsack thỏa mãn i 1. - While sum b and s n do. - Output: Một giá trị cân bằng tối ưu (min) và một cặp chỉ số tối ưu (Sol).. - Định lí 2.5 Bài toán xếp ba lô {0, 1} cân bằng được giải trong thời gian O n ( log ) n. - Input: Bài toán cân bằng {0,1}-knapsack thỏa mãn i 1. - s sum sum a. - Vì sum 10 b s. - Vì sum 15 b nên. - sum sum a. - Vậy giá mục tiêu tối ưu của bài toán tối ưu cân bằng với dữ liệu cho trong Ví dụ 2.6 là min 4 ứng với phương án tối ưu S. - Trong bài báo này, nghiên cứu Bài toán tối ưu cân bằng với ràng buộc có dạng xếp ba lô cho thấy bài toán có thể giải trong thời gian O n ( log ) n do tác động của việc sắp thứ tự các chi phí. - Một câu hỏi thú vị được đặt ra đó là liệu ta có thể cải thiện độ phức tạp của thuật toán về thời gian tuyến tính, tức là giải bài toán mà không thông qua việc sắp thứ tự.. - Hơn thế nữa, các kĩ thuật chứng minh trong bài báo có tiềm năng được tiếp tục nghiên cứu, phát triển, mở rộng và bổ sung,… để giải quyết những bài toán tối ưu cân bằng khác, ví dụ, bài toán gán cân bằng, bài toán cây bao trùm cân bằng, bài toán ngược của bài toán tối ưu cân bằng.