Miền khả thi

Miền nghiệm chấp nhận được (MNCDN) (còn gọi là tập nghiệm chấp nhận được, tiếng Anh: Feasible region, feasible set) — trong nghiên cứu vận trù, tối ưu hóa và mô hình hóa toán học, đây là tập hợp tất cả các nghiệm có thể (các bộ giá trị biến số) thỏa mãn tất cả các ràng buộc được đặt ra cho bài toán.

MNADN là một không gian con trong đó tiến hành tìm kiếm nghiệm tối ưu. Bất kỳ nghiệm nào nằm ngoài miền này đều là nghiệm không chấp nhận được.

Định nghĩa và cách hình thành

Miền nghiệm chấp nhận được được hình thành như là giao của các tập hợp được xác định bởi từng ràng buộc riêng lẻ của bài toán. Các ràng buộc có thể được biểu diễn dưới dạng:

• Bất đẳng thức: Xác lập giới hạn trên hoặc giới hạn dưới cho giá trị các biến hoặc tổ hợp của chúng (ví dụ: "mức tiêu thụ tài nguyên A không được vượt quá 100 đơn vị", "số lượng sản phẩm sản xuất ra phải không ít hơn 50 chiếc").
• Đẳng thức: Yêu cầu điều kiện được thỏa mãn chính xác (ví dụ: "tổng khối lượng vận chuyển phải bằng 1000 tấn", "cân bằng các luồng vào và ra bằng không").
• Điều kiện về dấu của biến: Thông thường các biến phải không âm, nguyên hoặc thuộc một tập rời rạc nhất định.

Một điểm (hoặc vector giá trị các biến) thuộc MNCDN khi và chỉ khi nó đồng thời thỏa mãn tất cả các ràng buộc này.

Diễn giải hình học

MNADN thường có diễn giải hình học trực quan, đặc biệt trong các bài toán có ít biến số:

• Trong không gian hai chiều (2 biến): Mỗi ràng buộc bất đẳng thức tuyến tính xác định một nửa mặt phẳng. MNCDN là giao của các nửa mặt phẳng này — một đa giác lồi (có thể không bị chặn hoặc rỗng).
• Trong không gian ba chiều (3 biến): Mỗi ràng buộc bất đẳng thức tuyến tính xác định một nửa không gian. MNCDN là giao của các nửa không gian này — một đa diện lồi (polyhedron).
• Trong không gian nhiều chiều: MNCDN được xác định bởi các ràng buộc tuyến tính là một đa diện lồi (polytope).

Trong trường hợp ràng buộc phi tuyến, MNCDN có thể có dạng phức tạp hơn và không nhất thiết là tập lồi.

Vai trò trong tối ưu hóa

Miền nghiệm chấp nhận được đóng vai trò nền tảng trong tối ưu hóa:

1. Xác định không gian tìm kiếm: Nghiệm tối ưu của bài toán (nếu tồn tại) luôn nằm bên trong MNCDN hoặc trên biên của nó. Các thuật toán tối ưu hóa tìm kiếm cực trị của hàm mục tiêu chính trong miền này. 2. Kiểm tra sự tồn tại của nghiệm: Nếu MNCDN là tập rỗng (tức là các ràng buộc mâu thuẫn nhau), thì bài toán không có nghiệm chấp nhận được, và do đó cũng không có nghiệm tối ưu. 3. Ảnh hưởng đến nghiệm tối ưu: Hình dạng và kích thước của MNCDN ảnh hưởng trực tiếp đến khả năng đạt được cực trị của hàm mục tiêu và đến giá trị của cực trị đó.

Tính chất của MNCDN (trong bài toán quy hoạch tuyến tính)

Trong các bài toán quy hoạch tuyến tính (QHTT), khi tất cả các ràng buộc và hàm mục tiêu đều tuyến tính, MNCDN có các tính chất quan trọng:

• Tính lồi: Nếu hai điểm thuộc MNCDN, thì toàn bộ đoạn thẳng nối hai điểm đó cũng thuộc MNCDN. Tính chất này đảm bảo rằng nghiệm tối ưu (nếu tồn tại và duy nhất) sẽ nằm tại một trong các đỉnh của đa diện MNCDN.
• Tính đóng: MNCDN bao gồm cả biên của nó (do các bất đẳng thức không chặt ≤, ≥ và đẳng thức).

MNADN có thể là:

• Bị chặn: Có kích thước hữu hạn.
• Không bị chặn: Trải dài vô hạn theo một hoặc nhiều hướng.
• Rỗng: Không chứa bất kỳ điểm nào.

Tài liệu tham khảo

• Ventzel E. S. Nghiên cứu vận trù: bài toán, nguyên tắc, phương pháp luận. — Moskva: Nauka, 1988.
• Akof R., Sasieni M. Cơ sở nghiên cứu vận trù. — Moskva: Mir, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Xem thêm

• Nghiên cứu vận trù
• Tối ưu hóa
• Mô hình toán học
• Ràng buộc
• Nghiệm chấp nhận được
• Nghiệm tối ưu
• Hàm mục tiêu
• Quy hoạch tuyến tính
• Tập lồi