R và thuật toán điểm trong cho quy hoạch tuyến tính

Ngôn ngữ mã nguồn mở R là môi trường tốt cho tính toán thống kê và phân tích dữ liệu. R cũng là công cụ cực tốt để tiếp cận Toán, và sử dụng Toán cho các ứng dụng của người dùng. Bài viết dùng R cho việc giải quy hoạch tuyến tính bằng thuật toán điểm trong. Khía cạnh được đưa ra trong bài viết là thực thi thuật toán bằng ngôn ngữ R, cả phía người dạy và người học. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
R và thuật toán điểm trong cho quy hoạch tuyến tính KỶ YẾU HỘI THẢO KHOA HỌC ĐÀO TẠO NGÀNH TOÁN KINH TẾ TRONG BỐI CẢNH HIỆN NAY VÀ CÁC VẤN ĐỀ LIÊN QUAN 29. R VÀ THUẬT TOÁN ĐIỂM TRONG CHO QUY HOẠCH TUYẾN TÍNH ThS. Phạm Việt Huy Trường Đại học Tài chính - Marketing Tóm tắt Ngôn ngữ mã nguồn mở R là môi trường tốt cho tính toán thống kê và phân tích dữ liệu. R cũng là công cụ cực tốt để tiếp cận Toán, và sử dụng Toán cho các ứng dụng của người dùng. Bài viết dùng R cho việc giải quy hoạch tuyến tính bằng thuật toán điểm trong. Khía cạnh được đưa ra trong bài viết là thực thi thuật toán bằng ngôn ngữ R, cả phía người dạy và người học. Từ khóa: Quy hoạch tuyến tính, thuật toán điểm trong, Affine scaling, barrier, R, dạy và học. 1. GIỚI THIỆU Đơn hình (simplex method, SM) là phương pháp phổ biến để giải các quy hoạch tuyến tính, đến khi phương pháp điểm trong phát triển. Với SM, việc đạt tới nghiệm tối ưu của quy hoạch tuyến tính thực hiện qua hành động chuyển từ đỉnh này tới đỉnh khác dọc theo các cạnh của miền ràng buộc đa diện, theo hướng thay đổi hàm mục tiêu. Điểm trong, như tên gọi, đi từ điểm nằm hẳn bên trong tập chấp nhận được, không nằm trên biên, theo hướng tốt dần để tới nghiệm tối ưu. Karmarkar (1984), được xem là người tiên phong của lĩnh vực phương pháp điểm trong. Phương pháp Projective scaling của Karmarkar có thể cạnh tranh với SM khi áp dụng vào các bài toán thực tế. Thuật toán điểm trong mượn những ý đơn giản từ 307 KỶ YẾU HỘI THẢO KHOA HỌC ĐÀO TẠO NGÀNH TOÁN KINH TẾ TRONG BỐI CẢNH HIỆN NAY VÀ CÁC VẤN ĐỀ LIÊN QUAN tối ưu phi tuyến, và với quy hoạch tuyến tính thì chúng đủ cơ bản để phát triển. Với quy hoạch tuyến tính, phương pháp điểm trong đạt đến nghiệm tối ưu (giờ được biết là nằm trên biên của miền chấp nhận được) thông qua một dãy các điểm trong. Kết quả các phép lặp của phương pháp điểm trong không nằm trên biên, mà là các điểm trong thật sự của miền chấp nhận được. Có nhiều hướng đi đến các điểm trong kế tiếp từ điểm trong khởi đầu, tập trung vào hai nhóm chính. Một là thay đổi tỷ lệ để giữ các điểm hiện tại cách xa biên, và hạn chế bước nhảy để không chạm biên. Hướng này có trong phương pháp affine scaling của Dikin. Hai là thêm lực đẩy biên vào hàm mục tiêu để chặn di chuyển đến biên của miền ràng buộc. Hướng này được biết là phương pháp barrier. Chính ngay trong từng hướng, đã có sự cải tiến từng chút từng chút một, làm cho các phương pháp điểm trong càng ngày càng tinh tế. Chẳng hạn, Boah D.K và Twum S.B. (2019) đưa ra một thay đổi cho phương pháp affine scaling. Thay đổi rõ từ nghiên cứu này là số lượng các bước lặp ứng với từng lựa chọn của tỷ lệ. [2] Boah D.K và Twum sử dụng MatLab cho các tính toán của mình. Và ngay MatLab cũng có gói linprog để giải quy hoạch tuyến tính, mà lựa chọn điểm trong đã xuất hiện. Gói linprog đã xuất hiện trong R, và cùng với lpSolve, là công cụ đắc lực để giải quy hoạch tuyến tính. Bài viết tập trung vào hướng thực hiện thuật toán điểm trong gốc đối ngẫu affine scaling và thuật toán điểm trong barrier cho quy hoạch tuyến tính. Trước đó, chúng tôi tóm lại ý tưởng của các thuật toán và các kết quả liên quan, có tham khảo tài liệu [3], [4], [6]. Bài viết dùng ngôn ngữ R minh họa mã hóa đoạn chính thể hiện bước lặp chuyển sang điểm trong mới. Với hướng này, người dạy và người học đọc ra sự di chuyển của dãy điểm trong, có thể điều chỉnh theo ý muốn, và nắm lại ý tưởng của từng thuật toán. Hơn nữa, thực hiện R như một ngôn ngữ lập trình cũng là một điều phù hợp. Ở Việt Nam, thuật toán điểm trong đã được giới thiệu và nghiên cứu từ lâu. Riêng cho quy hoạch tuyến tính giải bằng thuật toán điểm trong, chúng tôi có tham khảo một sản phẩm từ tác giả Nguyễn Thị Hồng Lê và Trần Vũ Thiệu (2011) [7]. Hướng thực thi là phần để mở phía sau của tài liệu [7]. Thuật toán đơn hình, hay thuật toán điểm trong, ngay khi xuất hiện đã đi kèm luôn nội dung thực thi. Hoạt động thực thi được hỗ trợ cực mạnh từ nhiều nguồn lực. [5] cho một tổng quan về công cụ giải quyết quy hoạch tuyến tính bằng thuật toán điểm trong, cả nguồn mở và nguồn thương mại. 308 KỶ YẾU HỘI THẢO KHOA HỌC ĐÀO TẠO NGÀNH TOÁN KINH TẾ TRONG BỐI CẢNH HIỆN NAY VÀ CÁC VẤN ĐỀ LIÊN QUAN 2. THUẬT TOÁN ĐIỂM TRONG VÀ QUY HOẠCH TUYẾN TÍNH 2.1. Bài toán Bài toán được xem xét trong bài viết là: mincT Ax = b x ≥ 0, x là vector n thành phần. Đối ngẫu của bài ...