LẬP TRÌNH TUYẾN TÍNH: NÓ DÙNG ĐỂ LÀM GÌ, MÔ HÌNH, RÀNG BUỘC, ỨNG DỤNG - TOÁN HỌC - 2025

Các quy hoạch tuyến tính là một phương pháp toán học được sử dụng để tối ưu hóa (tối đa hóa hoặc giảm thiểu nếu thích hợp) một hàm mà biến được hạn chế, như miễn là các chức năng và những hạn chế là tuyến tính biến phụ thuộc.

Nói chung, chức năng được tối ưu hóa mô hình một tình huống thực tế, chẳng hạn như lợi nhuận của một nhà sản xuất có đầu vào, lao động hoặc máy móc bị hạn chế.

Hình 1. Lập trình tuyến tính được sử dụng rộng rãi để tối ưu hóa lợi nhuận. Nguồn: Piqsel.

Một trong những trường hợp đơn giản nhất là hàm tuyến tính cực đại, chỉ phụ thuộc vào hai biến, được gọi là biến quyết định. Nó có thể có dạng:

Z = k ₁ x + k ₂ y

Với k ₁ và k ₂ không đổi. Hàm này được gọi là hàm mục tiêu. Tất nhiên, có những tình huống có giá trị hơn hai biến số cho nghiên cứu, phức tạp hơn:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Và các ràng buộc cũng được mô hình toán học bởi một hệ phương trình hoặc bất phương trình, tuyến tính như nhau theo x và y.

Tập hợp các giải pháp trong hệ thống này được gọi là giải pháp khả thi hoặc điểm khả thi. Và trong số các điểm khả thi có ít nhất một điểm tối ưu hóa hàm mục tiêu.

Lập trình tuyến tính được phát triển độc lập bởi nhà vật lý và toán học người Mỹ George Dantzig (1914-2005) và nhà toán học và kinh tế học người Nga Leonid Kantorovich (1912-1986) ngay sau Thế chiến thứ hai.

Phương pháp giải quyết vấn đề được gọi là phương pháp đơn giản là sản phẩm trí tuệ của Dantzig, người từng làm việc cho Không quân Hoa Kỳ, Đại học Berkeley và Đại học Stanford.

Hình 2. Các nhà toán học George Dantzig (trái) và Leonid Kantorovich (phải). Nguồn: F. Zapata.

Mô hình lập trình tuyến tính

Các yếu tố cần thiết để thiết lập một mô hình lập trình tuyến tính, phù hợp với tình huống thực tế, là:

-Hàm mục tiêu

-Các biến quyết định

-Những hạn chế

Trong hàm mục tiêu, bạn xác định những gì bạn muốn đạt được. Ví dụ: giả sử bạn muốn tối đa hóa lợi nhuận thu được từ việc sản xuất một số sản phẩm nhất định. Sau đó, chức năng "lợi nhuận" được thiết lập, theo giá mà các sản phẩm được bán.

Theo thuật ngữ toán học, hàm này có thể được viết tắt bằng cách sử dụng ký hiệu tổng:

Z = ∑k _i x _i

Trong phương trình này, k _i là hệ số và x _i là biến quyết định.

Các biến quyết định là các phần tử của hệ thống có quyền kiểm soát và giá trị của chúng là các số thực dương. Trong ví dụ được đề xuất, các biến quyết định là số lượng của mỗi sản phẩm được sản xuất để thu được lợi nhuận tối đa.

Cuối cùng, chúng ta có các ràng buộc, đó là các phương trình tuyến tính hoặc bất đẳng thức về các biến quyết định. Chúng mô tả những hạn chế của vấn đề, những hạn chế đã biết và có thể là, ví dụ, số lượng nguyên liệu thô có sẵn trong quá trình sản xuất.

Các loại hạn chế

Bạn có thể có một số giới hạn M, bắt đầu từ j = 1 đến j = M. Về mặt toán học, các hạn chế có ba loại:

1. A _j = ∑ a _ij . x _tôi
2. B _j ≥ ∑ b _ij . x _tôi
3. C _j ≤ ∑ c _ij . x _tôi

Hạn chế đầu tiên thuộc loại phương trình tuyến tính và có nghĩa là giá trị A _j , đã biết, phải được tôn trọng.

Hai hạn chế còn lại là bất bình đẳng tuyến tính và nó có nghĩa là các giá trị đã biết B _j và C _j có thể được tôn trọng hoặc vượt quá, khi ký hiệu xuất hiện là ≥ (lớn hơn hoặc bằng) hoặc được tôn trọng hoặc không vượt quá, nếu ký hiệu ≤ (ít hơn hoặc bằng).

Mẫu ví dụ

Các lĩnh vực áp dụng rất đa dạng, từ quản trị kinh doanh đến dinh dưỡng, nhưng để hiểu rõ về phương pháp, một mô hình đơn giản của một tình huống thực tế với hai biến được đề xuất dưới đây.

Một tiệm bánh ở địa phương được biết đến với hai món đặc sản: bánh rừng đen và bánh thánh.

Trong quá trình chuẩn bị, họ cần có trứng và đường. Đối với khu rừng đen, bạn cần 9 quả trứng và 500 g đường, trong khi đối với khu rừng đen, bạn cần 8 quả trứng và 800 g đường. Giá bán tương ứng là $ 8 và $ 10.

Bài toán đặt ra là: Tiệm bánh phải làm bao nhiêu cái bánh mỗi loại để thu được lợi nhuận tối đa, biết rằng tiệm bánh đó có 10 kg đường và 144 quả trứng?

Các biến quyết định

Các biến quyết định là "x" và "y", nhận các giá trị thực:

-x: số lượng bánh rừng đen

-y: loại bánh tráng men.

Những hạn chế

Các hạn chế được đưa ra là do số lượng bánh là số lượng dương và số lượng nguyên liệu thô để chế biến chúng có hạn.

Do đó, ở dạng toán học, những hạn chế này có dạng:

1. x ≥ 0
2. và ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Ràng buộc 1 và 2 tạo thành điều kiện không phủ định đã được phơi bày trước đó, và tất cả các bất đẳng thức nêu ra là tuyến tính. Trong hạn chế 3 và 4 là các giá trị không được vượt quá: 144 quả trứng và 10 kg đường.

Hàm mục tiêu

Cuối cùng, hàm mục tiêu là lợi nhuận thu được khi sản xuất số lượng “x” của bánh rừng đen cộng với số lượng “y” của các chất hy sinh. Nó được xây dựng bằng cách nhân giá với số lượng bánh được làm và cộng cho từng loại. Nó là một hàm tuyến tính mà chúng ta sẽ gọi là G (x, y):

G = 8x + 10y

Phương pháp giải quyết

Các phương pháp giải khác nhau bao gồm phương pháp đồ họa, thuật toán simplex và phương pháp điểm bên trong, để kể tên một số phương pháp.

- Phương pháp đồ họa hoặc hình học

Khi bạn gặp một bài toán hai biến giống như trong phần trước, các ràng buộc xác định một vùng đa giác trong mặt phẳng xy, được gọi là vùng khả thi hoặc vùng khả thi.

Hình 3. Vùng khả thi, nơi tìm ra lời giải của bài toán tối ưu. Nguồn: Wikimedia Commons.

Vùng này được xây dựng bằng cách sử dụng các đường giới hạn, là các đường thu được từ sự bất bình đẳng của các giới hạn, chỉ hoạt động với dấu bằng.

Trong trường hợp tiệm bánh muốn tối ưu hóa lợi nhuận, các đường giới hạn là:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Tất cả các điểm trong khu vực được bao quanh bởi các đường này đều là các giải pháp khả thi, vì vậy có vô số điểm trong số đó. Ngoại trừ trường hợp vùng khả thi bị bỏ trống, trong trường hợp đó vấn đề đặt ra không có giải pháp.

May mắn thay, đối với vấn đề bánh ngọt, vùng khả thi không trống, chúng tôi có nó bên dưới.

Hình 4. Vùng khả thi của vấn đề bánh ngọt. Dòng có độ lợi 0 đi qua điểm gốc. Nguồn: F. Zapata với Geogebra.

Giải pháp tối ưu, nếu nó tồn tại, được tìm thấy với sự trợ giúp của hàm mục tiêu. Ví dụ, khi cố gắng tìm lợi nhuận tối đa G, chúng ta có dòng sau, được gọi là đường đẳng lợi nhuận:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Với đường thẳng này, chúng ta thu được tất cả các cặp (x, y) cung cấp độ lợi G cho trước, do đó, có một họ đường theo giá trị của G, nhưng tất cả đều có cùng hệ số góc -k ₁ / k ₂ , vì vậy chúng những đường thẳng song song.

Giải pháp tối ưu

Bây giờ, có thể chứng minh rằng nghiệm tối ưu của một bài toán tuyến tính luôn là một điểm cực trị hoặc một đỉnh của vùng khả thi. Vì thế:

Nếu đường gần điểm gốc nhất có toàn bộ một đoạn chung với vùng khả thi, người ta nói rằng có vô số nghiệm. Trường hợp này xảy ra nếu độ dốc của đường đẳng lợi bằng độ dốc của bất kỳ đường nào khác giới hạn vùng.

Đối với bánh ngọt của chúng tôi, các đỉnh ứng viên là A, B và C.

- Phương pháp đơn giản của Dantzig

Phương pháp đồ thị hoặc hình học có thể áp dụng cho hai biến. Tuy nhiên, nó phức tạp hơn khi có ba biến và không thể sử dụng cho số lượng biến lớn hơn.

Khi xử lý các vấn đề có nhiều hơn hai biến, phương pháp simplex được sử dụng, phương pháp này bao gồm một loạt các thuật toán để tối ưu hóa các hàm mục tiêu. Ma trận và số học đơn giản thường được sử dụng để thực hiện các phép tính.

Phương pháp simplex bắt đầu bằng cách chọn một giải pháp khả thi và kiểm tra xem nó có phải là tối ưu hay không. Nếu đúng, chúng tôi đã giải quyết được vấn đề, nhưng nếu không, chúng tôi tiếp tục hướng tới một giải pháp gần với tối ưu hóa hơn. Nếu giải pháp tồn tại, thuật toán sẽ tìm thấy nó sau một vài lần thử.

Các ứng dụng

Lập trình tuyến tính và phi tuyến tính được áp dụng trong nhiều lĩnh vực để đưa ra quyết định tốt nhất về giảm chi phí và tăng lợi nhuận, không phải lúc nào cũng là tiền tệ, vì chúng có thể được đo lường trong thời gian, chẳng hạn, nếu bạn muốn giảm thiểu thời gian cần thiết. để thực hiện một loạt các hoạt động.

Đây là một số trường:

-Trong marketing, nó được sử dụng để tìm ra sự kết hợp tốt nhất của các phương tiện truyền thông (mạng xã hội, truyền hình, báo chí và những phương tiện khác) để quảng cáo một sản phẩm nhất định.

- Đối với việc phân công các nhiệm vụ đầy đủ cho nhân viên của một công ty hoặc nhà máy hoặc lịch trình cho họ.

-Trong việc lựa chọn thức ăn giàu dinh dưỡng nhất và giá thành thấp nhất trong các ngành chăn nuôi gia súc, gia cầm.

Bài tập đã giải

- Bài tập 1

Giải quyết một cách đồ họa mô hình lập trình tuyến tính đã nêu trong các phần trước.

Giải pháp

Cần phải vẽ biểu đồ tập hợp các giá trị được xác định bởi hệ thống các hạn chế được chỉ định trong bài toán:

1. x ≥ 0
2. và ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Vùng cho bởi bất đẳng thức 1 và 2 tương ứng với góc phần tư thứ nhất của mặt phẳng Descartes. Về bất đẳng thức 3 và 4, chúng ta bắt đầu bằng cách tìm các đường giới hạn:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Vùng khả thi là một tứ giác có các đỉnh là các điểm A, B, C và D.

Lợi nhuận tối thiểu là 0, do đó đường 8x + 10y = 0 là giới hạn dưới và đường đẳng lợi có độ dốc -8/10 = - 0,8.

Giá trị này khác với độ dốc của các đường giới hạn khác và vì vùng khả thi bị giới hạn nên giải pháp duy nhất tồn tại.

Hình 5. Đồ thị lời giải của bài tập 1, thể hiện vùng khả thi và điểm giải C tại một trong các đỉnh của vùng nói trên. Nguồn: F. Zapata.

Giải pháp này tương ứng với một đường có độ dốc -0,8 đi qua bất kỳ điểm nào trong số các điểm A, B hoặc C, có tọa độ là:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Giải pháp tối ưu

Chúng tôi tính giá trị của G cho mỗi điểm sau:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Lợi nhuận cao nhất được tìm thấy là sản xuất 11 bánh rừng đen và 5.625 bánh hy sinh. Giải pháp này đồng ý với giải pháp được tìm thấy thông qua phần mềm.

- Bài tập 2

Xác minh kết quả của bài tập trước bằng cách sử dụng hàm Solver có sẵn trong hầu hết các bảng tính như Excel hoặc LibreOffice Calc, kết hợp thuật toán Simplex để tối ưu hóa trong lập trình tuyến tính.

Giải pháp

Hình 6. Chi tiết lời giải từ bài tập 1 thông qua bảng tính Libre Office Calc. Nguồn: F. Zapata.

Hình 7. Chi tiết lời giải từ bài tập 1 thông qua bảng tính Libre Office Calc. Nguồn: F. Zapata.

Người giới thiệu

1. Xuất sắc. Lập trình tuyến tính. Phục hồi từ: glow.org.
2. Eppen, G. 2000. Nghiên cứu Hoạt động trong Khoa học Hành chính. ngày 5. Phiên bản. Sảnh Prentice.
3. Haeussler, E. 1992. Toán học Quản lý và Kinh tế. lần 2. Phiên bản. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lập trình tuyến tính. Đã khôi phục từ: hiru.eus.
5. Wikipedia. Lập trình tuyến tính. Được phục hồi từ: es. wikipedia.org.