Quy hoạch tuyến tính với bảng tính

Với vai trò là một nhà quản lý, bạn luôn có nguồn lực hữu hạn hoặc giới hạn, và ban lãnh đạo kỳ vọng bạn tận dụng tối đa nguồn lực đó. Từ năng suất thời gian đến sử dụng vốn, đất đai đến lao động, và từ chuỗi cung ứng đến sản xuất—hầu như mọi việc bạn làm đều nhằm tối ưu hóa năng suất.

Phần lớn các hãng hàng không tối ưu hóa lịch bay để đạt doanh thu cao nhất và chi phí thấp nhất. Các lịch bay này liên quan đến rất nhiều tình huống và ràng buộc như số lượng máy bay tại một địa điểm nhất định, nhiên liệu, phi hành đoàn và loại đường bay (tuyến phổ biến và sinh lợi). Những tình huống và ràng buộc này được gọi là các ràng buộc khi khai thác máy bay trên những tuyến phổ biến và sinh lợi nhất. Quy hoạch tuyến tính được dùng để tìm lời giải cho bài toán có ràng buộc đã cho.

Trong hướng dẫn này, bạn sẽ tìm hiểu về quy hoạch tuyến tính, với các nội dung sau:

• Giới thiệu về Quy hoạch tuyến tính
• Các khái niệm cơ bản của LPP
  • Biến quyết định
  • Các ràng buộc
  • Hàm mục tiêu
  • Lời giải tối ưu
  • Lời giải chấp nhận được
  • Lời giải không chấp nhận được
  • Miền chấp nhận được
  • Ràng buộc không âm
• Mô hình hóa bài toán LPP (Kèm ví dụ)
• Phương pháp đồ thị để giải LPP trong bảng tính
• Các trường hợp sử dụng LPP
• Kết luận

Giới thiệu về Quy hoạch tuyến tính

Về mặt toán học, quy hoạch tuyến tính tối ưu hóa (tối thiểu hóa hoặc tối đa hóa) một hàm mục tiêu tuyến tính của nhiều biến, dưới các điều kiện/ràng buộc đã cho thỏa mãn một hệ bất đẳng thức tuyến tính. Quy hoạch tuyến tính có thể áp dụng trong việc lập kế hoạch các hoạt động kinh tế như vận chuyển hàng hóa và dịch vụ, sản xuất sản phẩm, tối ưu hóa hệ thống điện, và dòng chảy mạng. Các bài toán LP có thể được giải bằng nhiều kỹ thuật như phương pháp đồ thị, Simplex và phương pháp Karmakar.

Các khái niệm cơ bản của LPP

Hãy cùng xem các thuật ngữ cơ bản của quy hoạch tuyến tính:

• Biến quyết định là các biến được sử dụng trong hàm mục tiêu. Các biến này quyết định đầu ra của bạn. Người ra quyết định có thể kiểm soát giá trị của hàm mục tiêu thông qua biến quyết định. Khi giải bất kỳ bài toán quy hoạch tuyến tính nào, trước tiên bạn cần xác định các biến quyết định.

• Các ràng buộc là tập hợp các giới hạn hoặc điều kiện tình huống. Ràng buộc có thể ở dạng đẳng thức hoặc bất đẳng thức. Ràng buộc hạn chế giá trị của các biến quyết định.

• Hàm mục tiêu là hàm lợi nhuận hoặc chi phí cần tối đa hóa hoặc tối thiểu hóa. Đây là mục tiêu chính của việc ra quyết định.

• Lời giải tối ưu là một trong các lời giải chấp nhận được mà tại đó hàm mục tiêu đạt cực đại hoặc cực tiểu, ví dụ lợi nhuận tối đa hoặc chi phí tối thiểu. Đây là giá trị tốt nhất của hàm mục tiêu.

• Lời giải chấp nhận được là tập giá trị khả dĩ cho các biến quyết định thỏa mãn tất cả các ràng buộc. Bài toán LP là chấp nhận được nếu tồn tại ít nhất một lời giải chấp nhận được.

• Lời giải không chấp nhận được là tập giá trị khả dĩ cho các biến quyết định nhưng không thỏa mãn tất cả các ràng buộc, tức là không có lời giải tối ưu. Bài toán LP là không chấp nhận được nếu không tồn tại lời giải nào thỏa mãn tất cả các ràng buộc.

• Miền chấp nhận được là vùng bao phủ bởi toàn bộ tập giá trị khả dĩ thỏa mãn các ràng buộc hoặc là giao của tất cả các ràng buộc. Nó bao gồm tất cả các bất đẳng thức, đẳng thức và ràng buộc nguyên.

• Ràng buộc không âm áp dụng cho các biến quyết định chỉ nhận giá trị không âm. Các ràng buộc như vậy lớn hơn hoặc bằng không.

Mô hình hóa bài toán LPP (Kèm ví dụ)

Mô hình hóa quy hoạch tuyến tính gồm các bước sau:

• Xác định các biến quyết định
• Xác định hàm mục tiêu
• Xác định các ràng buộc
• Định nghĩa các ràng buộc không âm

Trong một bài toán quy hoạch tuyến tính, các biến quyết định, hàm mục tiêu và ràng buộc đều phải là hàm tuyến tính

Bài toán: Một người buôn bàn ghế chỉ kinh doanh hai mặt hàng—bàn và ghế. Ông có 50.000 Rs để đầu tư và có không gian lưu trữ tối đa 60 sản phẩm. Một chiếc bàn có giá 2.500 Rs và một chiếc ghế 500 Rs. Ông ước tính rằng từ việc bán một chiếc bàn, ông có thể lãi 250 Rs và từ việc bán một chiếc ghế lãi 75 Rs. Ông muốn biết cần mua bao nhiêu bàn và ghế với số tiền hiện có để tối đa hóa tổng lợi nhuận, giả định rằng ông có thể bán hết các mặt hàng đã mua. (Nguồn)

Trong ví dụ này, bạn nhận thấy rằng—

1. Người buôn có thể đầu tư tiền vào mua bàn hoặc ghế hoặc kết hợp cả hai. Hơn nữa, ông sẽ thu được các mức lợi nhuận khác nhau theo những chiến lược đầu tư khác nhau. (Nguồn)
2. Số tiền đầu tư của ông bị giới hạn tối đa 50.000 Rs, và không gian lưu trữ cũng chỉ tối đa 60 sản phẩm. (Nguồn)

Biểu diễn toán học:

Giả sử ông quyết định chỉ mua bàn và không mua ghế. Khi đó, ông có thể mua 50000/2500 = 20 bàn. Trong trường hợp này, ông sẽ lãi 250 x 20 = 5.000 Rs. Hoặc ông quyết định chỉ mua ghế và không mua bàn. Khi đó, ông có thể mua 50000/500 = 100 ghế.

Trong trường hợp này, ông sẽ lãi 75 x 60 = 4.500 Rs.

Có thể có nhiều tổ hợp bàn và ghế mà ông có thể mua.

Giả sử ông mua X chiếc bàn và Y chiếc ghế. Khi đó X và Y phải không âm.

1. Người buôn có tối đa 50.000 Rs để mua bàn và ghế, do đó—

   2500 X + 500 Y <= 50000 (Ràng buộc đầu tư) hoặc 5 * X + Y <= 100 ................................................ Eq.1

1. Số lượng sản phẩm tối đa ông có thể lưu trữ là 60.

   X + Y <= 60 ................................................ Eq.2

1. Người buôn muốn mua với số lượng sao cho tối đa hóa lợi nhuận Z, do đó phương trình sẽ là—

   Max Z : 250 X + 75 Y

Hàm mục tiêu: Max Z: 250 X + 75 Y

Với các ràng buộc:

5 * X + Y <= 100,
X + Y <= 60 and
X,Y >= 0

Nguồn: http://ncert.nic.in/ncerts/l/lemh206.pdf

Phương pháp đồ thị để giải LPP trong bảng tính

Ví dụ Quy hoạch tuyến tính

Hàm mục tiêu: Max Z: 250 X + 75 Y

Với các ràng buộc:

5 * X + Y <= 100,

X + Y <= 60 and

Where X,Y >= 0

Bước 1: Hãy viết các hàm trong Excel như minh họa dưới đây.

Bước 2: Sau khi viết hàm mục tiêu và các ràng buộc trong bảng tính, hãy tính các giá trị cho ràng buộc C1 và C2. Bạn có thể tính bằng cách cho biến còn lại bằng không. Ví dụ với C1, tại X = 0, giá trị của Y sẽ là Y = 100 và tại Y = 0, giá trị của X sẽ là X = 20. Tương tự với ràng buộc C2.

Bước 3: Bây giờ, sau khi tính các giá trị, hãy vẽ đồ thị. Chọn các giá trị của ràng buộc C1, vào Insert và vẽ biểu đồ Scatter với đường làm mượt. Bạn có thể thấy biểu đồ như thế này.

Nếu trông như vậy, đừng lo, hãy làm theo các bước dưới đây để thay đổi. Nhấp chuột phải vào biểu đồ, vào Select Data, bạn sẽ thấy hai chuỗi, hãy xóa Series 2 và chỉnh sửa Series 1.

Đặt tên chuỗi là C1 và đổi giá trị X thành các giá trị cột A của C1 và giá trị Y thành các giá trị cột B của C1. Rồi bấm Ok. Bạn sẽ thấy biểu đồ như dưới đây:

Bước 4: Lại vào Select Data bằng cách nhấp chuột phải vào biểu đồ và thêm một chuỗi nữa. Đặt tên là C2 và ở X values chọn các giá trị cột X của ràng buộc C2, còn ở Y values chọn các giá trị cột Y của ràng buộc C2. Biểu đồ của bạn sẽ như sau:

Bước 5: Giờ đồ thị đã được vẽ, bạn cần xác định miền chấp nhận được:

Bây giờ bạn có 4 điểm (O, A, B, C) trong vùng miền chấp nhận được, bạn cần tính giá trị hàm mục tiêu tại tất cả các điểm để xem điểm nào cho giá trị lớn nhất của mục tiêu.

Bước 6: Để tính giá trị hàm mục tiêu, hãy làm theo các bước sau:

Tính hàm mục tiêu cho mỗi giá trị tại các điểm:

• Tại điểm O, tọa độ (X, Y) là (0, 0). Khi đó giá trị hàm mục tiêu = (2500+750) = 0
• Tại điểm A, tọa độ (X, Y) là (0, 60). Khi đó giá trị hàm mục tiêu = (2500+753) = 4500
• Tại điểm B, tọa độ (X, Y) là (20, 0). Khi đó giá trị hàm mục tiêu = (2503+750) = 5000

• Tại điểm C Để tìm tọa độ tại điểm Z, bạn cần tìm điểm giao nhau của hai đường ràng buộc C1 và C2. Bạn sẽ dùng hàm MMULT() và MINVERSE() để tính giao điểm của hai phương trình.

• MMULT(MINVERSE(array),array) # Hàm này cho ra nghiệm của hệ phương trình hai biến Hoặc, =MMULT(MINVERSE(AB17:AC18), AE17:AE18), Trước khi dùng công thức này, hãy chọn các ô giá trị X và Y (ô được tô vàng) và dùng hàm này để tính giao điểm của hai phương trình rồi nhấn CTRL+SHIFT+ENTER

Giá trị cuối cùng của Z:

Như bạn thấy, trong bài toán tối đa hóa này, bạn nhận được giá trị lớn nhất của Z tại Điểm B, và giá trị tối đa là 6.250 Rs. Do đó, để tối đa hóa lợi nhuận, người buôn nên mua 10 bàn và 50 ghế.

Các trường hợp sử dụng LPP

Quy hoạch tuyến tính được áp dụng để tìm lời giải tối ưu cho nghiên cứu vận hành. LP có thể tìm lời giải tối ưu nhất trong các ràng buộc và giới hạn đã cho. LP áp dụng cho mọi loại bài toán như các hoạt động kinh tế trong nông nghiệp, kỹ thuật, sản xuất, năng lượng, logistics và chuỗi cung ứng.

• Kỹ sư áp dụng quy hoạch tuyến tính trong ngành sản xuất và chế tạo để tối ưu hóa nguồn lực sẵn có, giúp đạt lợi nhuận tối đa.

• Ngành logistics và vận tải dùng quy hoạch tuyến tính để tìm đường đi/tuyến ngắn nhất, thời gian di chuyển và chiến lược định giá.

• Các kỹ sư áp dụng quy hoạch tuyến tính trong lĩnh vực năng lượng. Họ tối ưu hóa phụ tải điện, các tuyến phân phối ngắn nhất và tối ưu hóa thiết kế lưới điện.

• Trong ngành nông nghiệp, quy hoạch tuyến tính có thể được các kỹ sư dùng để xác định loại cây trồng và sản lượng nên trồng nhằm gia tăng doanh thu hiệu quả.

• Trong ngành thực phẩm, quy hoạch tuyến tính có thể giúp các quản lý y tế và chuyên gia dinh dưỡng lập kế hoạch nhu cầu dinh dưỡng và bộ sản phẩm thực phẩm chi phí thấp nhằm phòng tránh bệnh không lây nhiễm.

Kết luận

Chúc mừng bạn đã hoàn thành hướng dẫn này!

Bạn đã tìm hiểu rất nhiều về quy hoạch tuyến tính. Bạn đã biết quy hoạch tuyến tính là gì, các khái niệm và thuật ngữ cơ bản trong LP, cách mô hình hóa bài toán LP, giải bài toán LP bằng phương pháp đồ thị và các trường hợp sử dụng bài toán LP.

Hy vọng bạn có thể vận dụng các khái niệm quy hoạch tuyến tính để ra quyết định trong tổ chức của mình hoặc tối ưu kết quả cho người ra quyết định. Cảm ơn bạn đã đọc hướng dẫn này!

Xem thêm hướng dẫn Biểu đồ trong Bảng tính của chúng tôi.

Nếu bạn muốn tìm hiểu thêm về bảng tính, hãy tham gia các khóa học DataCamp sau: