Admin
14/09/2023
Share
Qui hoạch tuyến tính, còn được gọi là Linear programming, là một thuật toán để tìm ra phương án tối ưu hoặc kế hoạch tối ưu từ một số lượng không đếm được các phương án quyết định.
Hình minh hoạ. Nguồn: studentfeels1211.
Qui hoạch tuyến tính (Linear programming)
Khái niệm.
Qui hoạch tuyến tính trong tiếng Anh được gọi là Linear programming, viết tắt là LP.
Qui hoạch tuyến tính (LP) là một thuật toán nhằm tìm ra phương án tối ưu (hoặc kế hoạch tối ưu) từ vô số các phương án quyết định. Phương án tối ưu là phương án thỏa mãn các mục tiêu đề ra của một hãng, dựa trên các hạn chế và ràng buộc.
LP là viết tắt của “Linear Programming” (Lập trình tuyến tính), là một phương pháp để phân bổ nguồn lực khan hiếm giữa các hoạt động cạnh tranh một cách tối ưu. Quyết định tối ưu có thể dựa trên việc tối đa hóa hiệu quả, lãi gộp (Contribution Margin – CM), doanh thu hoặc tối thiểu hóa chi phí. Mô hình LP bao gồm hai thành phần chính.
Mục đích chính: Công ty phải đặt ra mục tiêu cụ thể cần đạt được.
Các ràng buộc trong qui hoạch tuyến tính được định dạng dưới dạng các hạn chế về nguồn lực có sẵn hoặc đáp ứng các yêu cầu tối thiểu. Cả hàm mục tiêu và các ràng buộc trong qui hoạch tuyến tính đều được biểu diễn dưới dạng tuyến tính.
Ví dụ:.
Một công ty muốn tìm cách kết hợp sản phẩm một cách tối ưu. Kết hợp tối ưu là kết hợp sao cho tổng hiệu quả hoặc lãi gộp (CM) được tối đa hóa trong ngân sách và công suất sản xuất có giới hạn. Hoặc có thể là công ty muốn xác định cách kết hợp nguyên liệu đầu vào sao cho có chi phí nhỏ nhất trong khi vẫn đáp ứng được yêu cầu sản xuất, tận dụng công suất sản xuất và sử dụng nhân công hiện có.
Các ứng dụng của Qui hoạch tuyến tính
Qui hoạch đường thẳng có nhiều ứng dụng khác nhau như:
Lựa chọn sự kết hợp đầu vào có chi phí thấp nhất cho sản phẩm được sản xuất.
Xác định ngân sách lý tưởng.
Quyết định danh sách đầu tư tối ưu (hay phân bổ tài sản).
Phân chia ngân sách quảng cáo cho các phương tiện truyền thông.
Lên kế hoạch sử dụng thiết bị công nghệ.
Quyết định phương thức di chuyển có chi phí thấp nhất.
Đặt kế hoạch cho các chuyến bay.
Tối ưu phân bố nhân sự.
Chọn vị trí đặt nhà máy phù hợp nhất.
Công thức của Qui hoạch tuyến đường
Để tạo ra một bài toán Linear Programming, cần thực hiện theo các giai đoạn sau:
Xác định các yếu tố quyết định cần phải tìm.
Các biến quyết định được sử dụng để biểu diễn hàm mục tiêu và các ràng buộc tương ứng. Tất cả các phương trình phải được biểu diễn dưới dạng tuyến tính.
Ví dụ.
Công ty XXX chuyên sản xuất đồ nội thất, bao gồm 2 sản phẩm chính là bàn giấy và bàn ăn. Cả hai sản phẩm đều cần được xử lí qua hai bộ phận khác nhau, đó là bộ phận lắp ráp và bộ phận hoàn thiện. Dưới đây là thông tin chi tiết về hai sản phẩm này:
Công ty mong muốn tìm ra phương pháp kết hợp tốt nhất giữa hai loại sản phẩm này để đạt được lợi ích cao nhất.
Bước 1, xác định các biến quyết định theo cách sau:.
X1= Số lượng tờ giấy.
X2= Số lượng bàn tiệc.
Bước 2, mục đích chính để tối đa hóa hiệu suất (Z) được biểu thị dưới đây:.
Z = 25lần1 + 40lần2.
Sau đó tạo ra các công thức các ràng buộc như là các bất phương trình.
2×1 + 4×2 < 100 (ràng buộc lắp ráp).
3 lần 1 cộng 2 lần 2 nhỏ hơn 90 (điều kiện hoàn chỉnh).
Ngoài ra, trong mọi công thức LP, điều kiện x1 và x2 không âm phải được đảm bảo, tức là x1, x2 >= 0.
Tối ưu hóa: Z = 25lần1 + 40lần2.
Ràng buộc: 2×1 + 4×2 < 100.
3 lần 1 cộng 2 lần 2 nhỏ hơn 90.
X1, x2 >= 0.
(Theo sách giáo trình Quản trị kinh doanh, nhà xuất bản Đại học Kinh tế Quốc dân).
