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

Qui hoạch tuyến tính (Linear programming)

Khái niệm

Qui hoạch tuyến tính trong tiếng Anh 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ác mục tiêu đề ra của một hãng, phụ thuộc vào các hạn chế và các ràng buộc. 

LP đề cập đến vấn đề phân bổ nguồn lực khan hiếm giữa các hoạt động cạnh tranh trong một phương thức tối ưu. Quyết định tối ưu mang lại hiệu quả cao nhất, lãi gộp (Contribution Margin – CM) cao nhất hay doanh thu hoặc chi phí thấp nhất. Mô hình LP gồm 2 thành phần:

– Hàm mục tiêu: Hãng phải xác định mục tiêu cụ thể phải đạt tới

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

Ví dụ:

Một hãng muốn tìm kết hợp sản phẩm tối ưu. Kết hợp tối ưu là kết hợp tối đa hóa tổng hiệu quả hay lãi gộp (CM) trong ngân sách được giới hạn và công suất sản xuất. Hoặc là hãng có thể muốn xác định kết hợp nguyên liệu đầu vào có chi phí nhỏ nhất trong khi vẫn đáp ứng được các đòi hỏi của sản xuất, tận dụng công suất sản xuất và sử dụng nhân công sẵn có. 

Ứng dụng của Qui hoạch tuyến tính

Qui hoạch tuyến tính có nhiều ứng dụng chẳng hạn như:

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

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

– Quyết định danh mục đầu tư tối ưu (hay 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 thông tin

– Lên kế hoạch sử dụng máy móc

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

 – Lên kế hoạch cho các chuyến bay

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

– Lựa chọn vị trí đặt nhà xưởng phù hợp nhất

Công thức của Qui hoạch tuyến tính

Để xây dựng một bài toán Qui hoạch tuyến tính, cần làm theo các bước sau:

– Xác định biến quyết định phải tìm

– Biểu diễn hàm mục tiêu các 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: bàn giấy và bàn ăn. Cả 2 sản phẩm cần thời gian để được xử lí trong 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 cách kết hợp 2 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₁= Số lượng bàn giấy

x₂= Số lượng bàn ăn

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

Z = 25x₁ + 40x₂

Sau đó lập công thức các ràng buộc như là các bất đẳng thức:

2x₁ + 4x₂ < 100 (ràng buộc lắp ráp)

3x₁ + 2x₂ <90 (ràng buộc hoàn thiện)

Thêm vào đó, ẩn trong bất kì công thức LP nào phải có điều kiện để làm cho x1 và x2 không âm, tức là x₁, x₂ >= 0

Tối ưu hóa: Z = 25x₁ + 40x₂

Ràng buộc: 2x₁ + 4x₂ < 100

3x₁ + 2x₂ < 90

x₁, x₂ >= 0

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