MÔ HÌNH VẬN TRÙ

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. MÔ HÌNH VẬN TRÙ

Nghiên cứu vận trù đầu tiên là ở nước Anh thời Đệ nhị thế chiến, khi ấy các nhà khoa học người Anh, dựa trên cơ sở khoa học, ra quyết định về việc sử dụng vật tư nguyên liệu sao cho tốt nhất. Sau chiến tranh, các ý tưởng vận trù khoa học đã áp dụng trong lĩnh vực quân sự được áp dụng trong việc nâng cao hiệu quả và năng suất của các hệ thống sản xuất trong lĩnh vực dân dụng.

Vận trù học dựa vào các mô hình toán học để giải các bài toán thực tế qua việc tìm lời giải tối ưu trong các lời giải khả thi bằng các tính toán lặp lại. Việc xác định chính xác vấn đề là rất quan trọng trong nghiên cứu vận trù, tuy nghiên cứu vận trù dựa vào toán học nhưng ảnh hưởng của các yếu tố định tính cũng rất quan trọng và cần được cân nhắc trước khi ra quyết định cuối cùng.

Mô hình vận trù  bao gồm ba thành phần cơ bản:

• Phương án
• Mục tiêu
• Ràng buộc

Số phương án quyết định phụ thuộc vào bài toán, có thể là hữu hạn mà cũng có thể là vô hạn. Mục tiêu là tiêu chuẩn để đánh giá tính tối ưu phương án. Ràng buộc là tiêu chuẩn để đánh giá tính khả thi của phương án. Dạng thức tổng quát của mô hình vận trù là

            Cực đại / Cực tiểu       Hàm mục tiêu

            Thỏa mãn                    Ràng buộc

Hay theo ngôn ngữ mô hình toán học:

            Max / Min       Hàm mục tiêu

            St.                    Ràng buộc

Lời giải mô hình là khả thi khi nó thỏa tất cả các ràng buộc. Trong các lời giải khả thi sẽ có lời giải tối ưu khi nó tạo ra giá trị tốt nhất thỏa hàm mục tiêu.

Mô hình vận trù được sử dụng để tối ưu hóa một hàm mục tiêu, đồng thời thỏa các ràng bụôc. Tuy nhiên chất lượng lời giải phụ thuộc vào việc mô hình hóa. Với các mô hình có số phương án hữu hạn, lời giải tìm được là lời giải tốt nhất trong các phương án đề ra, không hẳn là lời giải tối ưu.

b.  GIẢI MÔ HÌNH VẬN TRÙ

Không có kỹ thuật nào giải được mọi mô hình toán trong vận trù. Tùy thuộc lọai và mức độ  phức tạp của mô hình toán mà có những kỹ thuật giải khác nhau, từ đơn giản như xếp hạng các phương án theo một tiêu chuẩn nào đó đến phức tạp hơn như sử dụng các phép tính vi phân trong tối ưu kinh điển. Một kỹ thuật giải mô hình vận trù nổi bật là quy hoạch tuyến tính các kỹ thuật khác như quy hoạch mục tiêu, quy hoạch nguyên, quy hoạch động, quy hoạch phi tuyến,….

Một đặc điểm của các kỹ thuật giải mô hình vận trù là lời giải thường không từ các công thức toán học mà từ các giải thuật. Giải thuật là tập các quy tắc tính toán được áp dụng lập đi lập lại cho bài toán, với mỗi bước lặp, kết quả sẽ tiến gần đến lời giải tối ưu.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010