|
 Thuật ngữ VietnamBiz
Kiến thức Kinh tế

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

12:14 | 12/08/2019
Chia sẻ
Qui hoạch tuyến tính (tiếng Anh: Linear programming) 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.
Linear-programming

Hình minh họa. 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 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:

Screenshot (435)-crop

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:

x1= Số lượng bàn giấy

x2= 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 = 25x1 + 40x2

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

2x1 + 4x2 < 100 (ràng buộc lắp ráp)

3x1 + 2x2 <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à x1, x2 >= 0

Tối ưu hóa: Z = 25x1 + 40x2

Ràng buộc: 2x1 + 4x2 < 100

3x1 + 2x2 < 90

x1, x2 >= 0

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


Diễn đàn Đầu tư Việt Nam 2025 (Vietnam Investment Forum 2025) với chủ đề “Khai thông & Bứt phá” do trang TTĐT tổng hợp VietnamBiz, Việt Nam Mới tổ chức sẽ diễn ra vào ngày 8/11/2024 tại GEM CENTER, TP HCM.

Sự kiện quy tụ giới chuyên gia cao cấp trong lĩnh vực đầu tư, tài chính là các nhà làm chính sách, CEO, CFO, CIO các ngân hàng, công ty chứng khoán, quỹ đầu tư, công ty bất động sản, các hãng xếp hạng, công ty cung cấp dữ liệu và hàng trăm nhà đầu tư có kinh nghiệm lâu năm trên thị trường chứng khoán và bất động sản.

Diễn đàn hứa hẹn mang lại không gian để các chuyên gia bàn luận về các xu hướng đầu tư mới, các góc nhìn chiến lược, mở ra nhiều ý tưởng đầu tư phù hợp cho giai đoạn mới. Đồng thời tạo cơ hội gặp gỡ, kết nối giữa nhà đầu tư và các đối tác tiềm năng trên thị trường.

Thông tin chi tiết chương trình: https://event.vietnambiz.vn/

Lam Anh

Ngành thép quý III: Hoà Phát là điểm sáng, hai gọng kìm bóp chặt lợi nhuận nhóm tôn mạ
Trong nhóm sản xuất và thương mại thép, Hoà Phát nổi lên là điểm sáng trong khi VNSteel, SMC, Tisco,... lần lượt báo lỗ. Với nhóm tôn mạ, ngoài áp lực cạnh tranh từ tôn mạ nhập khẩu của Trung Quốc và Hàn Quốc thì chi phí vận chuyển leo thang đã bóp nghẹt lợi nhuận nhóm này trong quý vừa qua.