Bài viết & Thông báo

Quy hoạch tuyến tính và phương pháp Simplex

Quy hoạch tuyến tính (linear programming) là một phương pháp tối ưu hóa dùng để lựa chọn phương án tốt nhất trong điều kiện tài nguyên, năng lực hoặc yêu cầu bị giới hạn bởi các quan hệ tuyến tính. Một mô hình linear programming có ba thành phần chính: biến quyết định, objective function và constraint. Khi mô hình đã được chuẩn hóa, phương pháp Simplex (Simplex method) có thể tìm nghiệm tối ưu bằng cách di chuyển giữa các đỉnh của miền nghiệm khả thi. Bài luận này trình bày lại nền tảng của linear programming, cách xây dựng mô hình, một số lớp bài toán thường gặp và quy trình giải bằng Simplex method, trong đó có trường hợp phải dùng Simplex hai pha (two phase Simplex).