NEW Qui hoạch tuyến tính (Linear programming) là gì? Công thức và ví dụ

Hình minh họa. Nguồn: studentfeels1211

Lập trình tuyến tính

Ý tưởng

Quy hoạch tuyến tính trong tiếng anh gọi là Lập trình tuyến tính, Được viết tắt là LP.

Lập trình tuyến tính (LP) là một thuật toán để tìm giải pháp tối ưu (hoặc phương án 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 đã nêu của một doanh nghiệp, có các ràng buộc và ràng buộc.

LP giải quyết vấn đề 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 mang lại hiệu quả cao nhất, Biên lợi nhuận đóng góp (CM) cao nhất hoặc doanh thu hoặc chi phí thấp nhất. Mô hình LP bao gồm hai thành phần:

– Hàm mục tiêu: Công ty phải xác định các mục tiêu cụ thể cần đạt được

– Ràng buộc: Các ràng buộc dưới dạng hạn chế về sự sẵn có của nguồn lực hoặc sự thỏa mãn các yêu cầu tối thiểu. Như tên của nó, cả hàm mục tiêu và các ràng buộc phải là tuyến tính.

Ví dụ:

Một công ty muốn tìm ra sự kết hợp sản phẩm tối ưu. Sự kết hợp tối ưu là sự kết hợp tối đa hóa tổng hiệu suất hoặc tổng lợi nhuận (CM) trong phạm vi ngân sách và năng lực sản xuất hạn chế. Hoặc doanh nghiệp có thể muốn xác định hỗn hợp đầu vào có chi phí thấp nhất trong khi đáp ứng các yêu cầu sản xuất, tận dụng năng lực sản xuất và sử dụng lao động sẵn có.

Các ứng dụng của lập trình tuyến tính

Quy hoạch tuyến tính Có nhiều ứng dụng như:

– Chọn kết hợp đầu vào có chi phí thấp nhất cho sản phẩm đầu ra

– Xác định ngân sách tối ưu

Quyết định danh mục đầu tư tối ưu (hoặc phân bổ tài sản)

– Phân bổ ngân sách quảng cáo cho các phương tiện truyền thông

– Kế hoạch sử dụng máy móc

– Quyết định phương thức vận chuyển chi phí thấp nhất

– Lên kế hoạch chuyến bay

– Phân bổ nhân lực tối ưu

– Chọn vị trí đặt nhà máy phù hợp nhất

Công thức lập trình tuyến tính

Để xây dựng một vấn đề Quy hoạch tuyến tính, cần làm theo các bước sau:

– Xác định biến quyết định cần tìm

– Biểu diễn hàm mục tiêu của các ràng buộc theo các biến quyết định này. Các phương trình phải có dạng tuyến tính.

Ví dụ

Công ty sản xuất nội thất XXX sản xuất 2 sản phẩm là bàn làm việc và bàn ăn. Cả hai sản phẩm đều mất thời gian để gia công ở 2 bộ phận: bộ phận lắp ráp và bộ phận hoàn thiện. Dữ liệu về hai sản phẩm này như sau:

Công ty muốn tìm cách kết hợp hai loại sản phẩm này sao cho có lợi nhất.

Bước 1, xác định các biến quyết định như sau:

x_{Đầu tiên}= Số bàn làm việc

x₂= Số bàn ăn

Bước 2, hàm mục tiêu để tối đa hóa hiệu quả (Z) được hiển thị dưới đây:

Z = 25x_{Đầu tiên} + 40x₂

Sau đó công thức các ràng buộc dưới dạng bất đẳng thức:

2x_{Đầu tiên} + 4x₂

3x_{Đầu tiên} + 2x₂

Ngoài ra, ngầm định trong bất kỳ công thức LP nào phải có điều kiện để x1 và x2 không âm, tức là x_{Đầu tiên}, x₂ > = 0

Tối ưu hóa: Z = 25x_{Đầu tiên} + 40x₂

Ràng buộc: 2x_{Đầu tiên} + 4x₂

3x_{Đầu tiên} + 2x₂

x_{Đầu tiên}, x₂ > = 0

(Theo Giáo trình Quản trị kinh doanh, NXB Đại học Kinh tế Quốc dân)