Lập trình nguyên

Lập trình nguyên (LPN; tiếng Anh: integer programming, IP) — là một nhánh của tối ưu hóa toán học, trong đó nghiên cứu các bài toán mà một số hoặc tất cả các biến chỉ được phép nhận giá trị nguyên.

Trường hợp riêng được nghiên cứu kỹ nhất là lập trình tuyến tính nguyên (LPTN; tiếng Anh: integer linear programming, ILP), trong đó hàm mục tiêu và các ràng buộc đều là tuyến tính. Khác với lập trình tuyến tính, nơi các biến có thể nhận bất kỳ giá trị thực nào, yêu cầu về tính nguyên khiến các bài toán lập trình nguyên trở nên phức tạp hơn đáng kể để giải.

Lập trình nguyên được ứng dụng rộng rãi trong kinh tế, logistics, lập kế hoạch sản xuất và nhiều lĩnh vực khác, nơi các biến về bản chất mang tính rời rạc (ví dụ: số lượng đơn vị sản phẩm được sản xuất hoặc số lượng công nhân).

Định nghĩa và thuật ngữ

Bài toán lập trình tuyến tính nguyên tổng quát có thể được viết như sau:

Tìm véctơ $x$ sao cho:

tối đa hóa (hoặc tối thiểu hóa) $c^{T}x$

với các điều kiện:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (tất cả các thành phần của véctơ $x$ đều là số nguyên)

trong đó $x$ — véctơ các biến, $c$ và $b$ — các véctơ, còn $A$ — ma trận hệ số.

Tùy theo yêu cầu đối với các biến, người ta phân biệt các loại bài toán sau:

• Lập trình nguyên toàn phần: tất cả các biến phải là số nguyên.
• Lập trình nguyên hỗn hợp (tiếng Anh: mixed-integer programming, MIP): chỉ một phần các biến phải là số nguyên.
• Lập trình nhị phân (0-1): các biến chỉ nhận giá trị 0 hoặc 1, cho phép mô hình hóa các quyết định logic kiểu "có/không".

Các tính chất quan trọng và độ phức tạp

Độ phức tạp tính toán

Bài toán lập trình tuyến tính nguyên trong trường hợp tổng quát là NP-khó. Điều này có nghĩa là không tồn tại thuật toán đã biết nào có thể tìm được nghiệm tối ưu chính xác cho một bài toán lập trình nguyên tùy ý trong thời gian đa thức. Độ phức tạp xuất phát từ bản chất tổ hợp của bài toán, vì số lượng nghiệm nguyên khả thi có thể tăng theo hàm mũ khi số lượng biến tăng lên.

Liên hệ với lập trình tuyến tính (thư giãn LP)

Với bất kỳ bài toán lập trình nguyên nào, người ta có thể xây dựng thư giãn tuyến tính của nó — bài toán lập trình tuyến tính (LP) trong đó bỏ đi yêu cầu các biến phải nguyên. Nghiệm của thư giãn LP có hai tính chất quan trọng:

1. Có thể tìm được nhanh hơn đáng kể (trong thời gian đa thức).
2. Giá trị tối ưu của hàm mục tiêu trong thư giãn LP cho một ước lượng (cận trên đối với bài toán tối đa hóa và cận dưới đối với bài toán tối thiểu hóa) cho giá trị tối ưu của bài toán nguyên ban đầu.

Tuy nhiên, việc đơn giản làm tròn nghiệm phân số của thư giãn LP về số nguyên gần nhất thông thường không dẫn đến nghiệm tối ưu hay thậm chí nghiệm chấp nhận được của bài toán nguyên.

Tính chất đơn mô-đun toàn phần

Tồn tại một lớp bài toán lập trình tuyến tính nguyên quan trọng có thể được giải dễ dàng như các thư giãn LP của chúng. Đó là các bài toán mà ma trận ràng buộc $A$ là đơn mô-đun toàn phần (tức là định thức của bất kỳ ma trận con vuông nào của nó đều bằng 0, +1 hoặc −1). Nếu ma trận $A$ là đơn mô-đun toàn phần và véctơ $b$ là nguyên, thì tất cả các đỉnh của đa diện nghiệm chấp nhận được trong thư giãn LP sẽ tự động là nguyên. Do đó, nghiệm tìm được bằng phương pháp đơn hình sẽ là nghiệm nguyên. Ví dụ về các bài toán như vậy là bài toán vận tải và bài toán phân công.

Các phương pháp giải

Để giải các bài toán lập trình nguyên tổng quát không có tính chất đơn mô-đun toàn phần, người ta đã phát triển các phương pháp chính xác dựa trên ý tưởng liệt kê ngầm.

• Phương pháp nhánh và cận (tiếng Anh: Branch and Bound) — phương pháp chính xác chủ yếu, dựa trên việc phân chia có hệ thống tập nghiệm chấp nhận được thành các tập con (phân nhánh) và loại bỏ những tập con chắc chắn không chứa nghiệm tối ưu. Thư giãn LP được sử dụng để đánh giá triển vọng của các tập con.

• Phương pháp mặt cắt (phương pháp Gomory; tiếng Anh: Cutting Plane Method) — phương pháp lặp, liên tục bổ sung vào bài toán các ràng buộc tuyến tính mới ("mặt cắt"). Các mặt cắt này "cắt bỏ" các nghiệm phân số của thư giãn LP mà không ảnh hưởng đến bất kỳ nghiệm nguyên chấp nhận được nào, dần dần thu hẹp miền nghiệm chấp nhận được của thư giãn LP về bao lồi của các nghiệm nguyên.

Các bộ giải hiện đại thường sử dụng các thuật toán lai, chẳng hạn như phương pháp nhánh và cắt (tiếng Anh: Branch and Cut), kết hợp ưu điểm của cả hai phương pháp trên.

Các ví dụ và lĩnh vực ứng dụng

Lập trình nguyên cho phép mô hình hóa nhiều bài toán cổ điển trong tối ưu hóa tổ hợp.

• Bài toán ba lô: bài toán lập trình 0-1 cổ điển, trong đó cần chọn một tập hợp đồ vật có tổng giá trị lớn nhất mà không vượt quá giới hạn trọng lượng tổng.
• Bài toán người bán hàng rong: bài toán tìm hành trình ngắn nhất đi qua một tập hợp các thành phố cho trước. Có thể được xây dựng dưới dạng bài toán lập trình nguyên, trong đó các biến xác định việc đưa các cạnh của đồ thị vào hành trình cuối cùng.

Nhờ tính linh hoạt của mình, lập trình nguyên là một trong những công cụ được ứng dụng rộng rãi nhất trong nghiên cứu vận hành và được sử dụng trong các lĩnh vực như:

• Logistics và quản lý chuỗi cung ứng: tối ưu hóa tuyến đường vận chuyển, bố trí kho bãi, quản lý hàng tồn kho.
• Lập kế hoạch sản xuất: xây dựng lịch sản xuất, phân bổ nguồn lực, tải máy móc thiết bị.
• Tài chính và kinh tế: xây dựng danh mục đầu tư, lập ngân sách vốn.
• Viễn thông và năng lượng: thiết kế mạng truyền thông, lập kế hoạch vận hành các tổ máy điện.

Xem thêm

• Lập trình tuyến tính
• Phương pháp nhánh và cận

Chú thích

</references>