Skip to content

Tối ưu hóa các ràng buộc

Tháng Ba 30, 2013

Le problème du “sac à dos” et du “voyageur de commerce”.

Khái niệm túi mang trên lưng và người đi buôn di động

Ngày xưa, tôi vẫn  kể cho các con tôi nghe chuyện một con gà mái ấp trứng vịt. 21 ngày dài. Lại chăm lo nghe ngóng để mổ trứng cho nó vỡ ra khi thấy động tịnh bên trong…Tới lúc vịt con nở ra, biết đi biết chạy và ù té sà xuống ao tắm mát, gà mẹ ngơ ngác hoảng sợ chạy chung quanh ao, kêu cứu…

Các con tôi bây giờ đủ lông đủ cánh và «bung» ra đường đời như lủ vịt con trong truyện ấy. Thỉnh thoảng chúng về nhà và kể cho tôi nghe những chuyện mà tôi hoàn toàn mù tịt.

Những lúc ấy, tôi nghe không khác nào như «vịt nghe sấm». Lại một thành ngữ Việt Nam khác. Mà vịt ở đây là … vịt mẹ chứ không phải vịt con như truyện ở trên.

Một thí dụ :  tối ưu hóa là chuyên môn của con trai út tôi – optimization, hiện cậu ấy làm việc ở ĐH Waterloo. Và để cho một người dốt toán hiểu chút ít, hôm nay cháu kiên nhẩn giải thích cho tôi hai khái niệm – với những từ thông dụng – như tôi đã làm khi kể chuyện cổ tích cho cháu, hơn hai mươi năm về trước…

.

Khái niệm túi mang trên lưng – sac à dos –

Khái niệm này được cụ thể hóa bằng chuyện  của một kẻ trộm vào một ngân hàng với một túi mang trên lưng. Cái túi này có một dung tích nhất định. Trong phòng an toàn của ngân hàng, tên trộm này đứng trước một số kiện hàng có kích thước và giá trị khác nhau. Tên trộm phải làm sao lấy được số hàng có giá trị cao nhất mà tổng kích thước cuối cùng cho vào được trong cái túi anh mang trên lưng. Chỉ có hai ràng buộc thôi. Con tính có vẻ không khó lắm…

«Con làm những con toán như vậy đó mẹ» con trai tôi kết luận, rất là thỏa mãn và hài lòng vì thấy tôi … hiểu bài.

A ra thế, tôi vừa nhớ ra là cách đây không lâu, tôi có nghe cháu tổ chức phân công phiên trực trong một bệnh viện thành phố với gần 700 bác sĩ của các chuyên khoa khác nhau, mỗi bác sĩ lại có những sinh hoạt riêng và những đời hỏi về thời dụng biểu khác nhau.

.

Khái niệm người đi buôn di động – voyageur de commerce

Một cách rất là sư phạm và gần gũi – cái này không biết cháu học ở đâu – con trai tôi nói «mẹ vẫn tổ chức các chuyến du lịch của gia đình, mẹ quen lên internet so sánh giá các công ty hàng không – người đi buôn di động cũng như mẹ thôi. Ông hay bà ấy phải rời thành phố X và trở về đó, sau khi đi bán hàng ở 9, 10 hay 100 thành phố khác. Ông hay bà ấy phải chọn lộ trình nào  thuận tiện nhất, ít tốn thời gian nhất,  rẻ nhất đồng thời có khả năng bán được nhiều hàng nhất ».

Ràng buộc ở đây nhiều hơn, bài toán khó hơn. Nhưng vẫn có cách tối ưu hoá các ràng buộc.

Ứng dụng nhiều lắm mẹ ạ, con tôi kể tiếp.

Thí dụ một nhà máy nào đó, chỉ có một cánh tay robot phải đục 100 lỗ trên một tấm tôle. Bố cục của các lỗ này rắc rối chứ không đơn giản. Tối ưu hóa là phải tính lộ trình của robot – đi tới đi lui rẽ phải rẽ trái – để nó làm nhanh nhất. Cho năng suất cao nhất.

Hôm nay tôi biết thêm được hai khái niệm toán học. Rõ ràng là học suốt đời …

Tối ưu hóa các ràng buộc cũng rất cần cho quản lý các  cải tổ hệ thống giáo dục, hành chính, kinh tế, thị trường, … mà Việt nam đang lo.

Nguyễn Huỳnh Mai

Advertisements

Đã đóng bình luận.