LẬP TRÌNH PHI TUYẾN: CÁC PHƯƠNG PHÁP VÀ BÀI TẬP - TOÁN HỌC - 2025

Các lập trình phi tuyến là quá trình tối ưu hóa một hàm phụ thuộc vào nhiều biến độc lập, do đó phải chịu hạn chế.

Nếu một hoặc nhiều ràng buộc, hoặc nếu hàm cực đại hoặc cực tiểu (được gọi là hàm mục tiêu), không được biểu thị dưới dạng kết hợp tuyến tính của các biến, thì bạn có vấn đề về lập trình phi tuyến.

Hình 1. Bài toán lập trình phi tuyến (NLP). trong đó G là hàm (phi tuyến tính) để tối ưu hóa trong vùng màu xanh lá cây, được xác định bởi các ràng buộc. Nguồn: F. Zapata.

Và do đó không thể sử dụng các thủ tục và phương pháp của lập trình tuyến tính.

Ví dụ, không thể sử dụng phương pháp Simplex nổi tiếng, phương pháp này chỉ áp dụng khi hàm mục tiêu và các ràng buộc đều là tổ hợp tuyến tính của các biến trong bài toán.

Phương pháp lập trình tuyến tính

Đối với các bài toán lập trình phi tuyến tính, các phương pháp chính được sử dụng là:

1.- Phương pháp đồ họa.

2.- Nhân Lagrange để khám phá ranh giới của vùng giải pháp.

3. Tính toán gradient để khám phá các điểm cực trị của hàm mục tiêu.

4.- Phương pháp giảm dần các bước, để tìm các điểm gradient rỗng.

5.- Phương pháp sửa đổi của các số nhân Lagrange (với điều kiện Karush-Kuhn-Tucker).

Ví dụ về giải pháp với phương pháp đồ họa

Ví dụ về giải pháp với phương pháp đồ họa là ví dụ có thể thấy trong hình 2:

Hình 2. Ví dụ về một bài toán phi tuyến tính với các hạn chế phi tuyến tính và giải pháp đồ họa của nó. Nguồn: F. Zapata.

Bài tập

- Bài tập 1 (Phương pháp đồ họa)

Lợi nhuận G của một công ty nhất định phụ thuộc vào lượng bán sản phẩm X và lượng bán sản phẩm Y, ngoài ra lợi nhuận được xác định theo công thức sau:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Số tiền X và Y được biết là có các hạn chế sau:

X≥0; Y≥0 và X + Y ≤ 7

Xác định giá trị của X và Y để sản phẩm đạt được tối đa.

Hình 3. Lợi nhuận của một công ty có thể được lập mô hình toán học để tìm ra lợi nhuận tối đa bằng cách sử dụng lập trình phi tuyến. Nguồn: Pixabay.

Giải pháp

Trong bài toán này, hàm mục tiêu là phi tuyến tính, trong khi các bất đẳng thức xác định các ràng buộc là. Đây là một vấn đề lập trình phi tuyến.

Đối với giải pháp của vấn đề này, phương pháp đồ họa sẽ được chọn.

Đầu tiên, khu vực giải pháp sẽ được xác định, được đưa ra bởi các hạn chế.

Như X≥0; Y≥0, nghiệm phải được tìm thấy trong góc phần tư thứ nhất của mặt phẳng XY, nhưng vì nó cũng phải đúng với X + Y ≤ 7, nghiệm nằm trong nửa mặt phẳng dưới của đường thẳng X + Y = 7.

Vùng giải pháp là giao điểm của góc phần tư thứ nhất với nửa mặt phẳng bên dưới của đoạn thẳng, dẫn đến một vùng tam giác nơi tìm thấy nghiệm. Nó giống như được chỉ ra trong hình 1.

Mặt khác, độ lợi G cũng có thể được biểu diễn trong mặt phẳng Descartes, vì phương trình của nó là một hình elip với tâm (2,3).

Hình elip được thể hiện trong Hình 1 cho các giá trị khác nhau của G. Giá trị của G càng cao, độ lợi càng lớn.

Có những giải pháp thuộc về vùng, nhưng không cho giá trị G lớn nhất, trong khi những giải pháp khác, chẳng hạn như G = 92,4, nằm ngoài vùng xanh, tức là vùng giải pháp.

Khi đó, giá trị lớn nhất của G sao cho X và Y thuộc vùng nghiệm tương ứng là:

G = 77 (mức tăng tối đa), tương ứng với X = 7 và Y = 0.

Điều thú vị là lợi nhuận tối đa xảy ra khi lượng bán sản phẩm Y bằng 0, trong khi lượng sản phẩm X đạt giá trị cao nhất có thể.

- Bài tập 2 (Phương pháp giải tích: Bội số Lagrange)

Tìm nghiệm (x, y) khiến hàm số f (x, y) = x ² + 2y ² đạt cực đại trong miền g (x, y) = x ² + y ² - 1 = 0.

Giải pháp

Rõ ràng đây là một bài toán lập trình phi tuyến tính, vì cả hàm mục tiêu f (x, y) và giới hạn g (x, y) = 0, không phải là tổ hợp tuyến tính của các biến x và y.

Phương pháp nhân Lagrange sẽ được sử dụng, phương pháp này đầu tiên yêu cầu xác định hàm Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Trong đó λ là một tham số được gọi là hệ số nhân Lagrange.

Để xác định các giá trị cực trị của hàm mục tiêu f, trong vùng nghiệm cho bởi giới hạn g (x, y) = 0, hãy làm theo các bước sau:

-Tìm các đạo hàm riêng của hàm Lagrange L, đối với x, y, λ.

-Cung cấp mỗi đạo hàm về không.

Dưới đây là trình tự của các hoạt động này:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Các giải pháp hệ thống khả thi

Một nghiệm khả dĩ của hệ này là λ = 1 để phương trình thứ nhất thỏa mãn, trong đó y = 0 để phương trình thứ hai thỏa mãn.

Giải pháp này ngụ ý rằng x = 1 hoặc x = -1 để phương trình thứ ba thỏa mãn. Theo cách này, người ta thu được hai dung dịch S1 và S2:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Phương án khác là λ = 2 để phương trình thứ hai được thỏa mãn, bất kể giá trị y.

Trong trường hợp này, cách duy nhất để phương trình đầu tiên được thỏa mãn là cho x = 0. Xét phương trình thứ ba, chỉ có hai nghiệm khả dĩ, chúng ta gọi là S3 và S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Để tìm ra nghiệm nào hoặc nghiệm nào trong số này tối đa hóa hàm mục tiêu, chúng ta tiến hành thay thế vào f (x, y):

S1: f (1, 0) = 1 ² + 2.0 ² = 1

S2: f (-1, 0) = (-1) ² + 2.0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Ta kết luận rằng các nghiệm đạt cực đại f khi x và y thuộc chu vi g (x, y) = 0 là S3 và S4.

Các cặp giá trị (x = 0, y = 1) và (x = 0, y = -1) f (x, y) cực đại trong miền nghiệm g (x, y) = 0.

- Bài tập 3 (Null gradient)

Tìm nghiệm (x, y) cho hàm mục tiêu:

f (x, y) = x ² + 2 y ²

Đặt giá trị cực đại trong vùng g (x, y) = x ² + y ² - 1 ≤ 0.

Giải pháp

Bài tập này tương tự như bài tập 2, nhưng vùng nghiệm (hoặc giới hạn) mở rộng đến vùng bên trong của chu vi g (x, y) = 0, nghĩa là đối với đường tròn g (x, y) ≤ 0. Điều này bao gồm đến chu vi và vùng bên trong của nó.

Giải pháp ở biên giới đã được xác định trong bài tập 2, nhưng khu vực nội địa vẫn còn phải được khám phá.

Để làm điều này, gradient của hàm f (x, y) phải được tính toán và đặt bằng 0, để tìm các giá trị cực trị trong vùng nghiệm. Điều này tương đương với việc tính các đạo hàm riêng của f tương ứng với x và y và đặt nó bằng 0:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Hệ phương trình này có nghiệm duy nhất (x = 0, y = 0) thuộc đường tròn g (x, y) ≤ 0.

Thay giá trị này trong hàm f cho kết quả:

f (0, 0) = 0

Suy ra, giá trị lớn nhất mà hàm nhận trong vùng nghiệm là 2 và xuất hiện tại ranh giới của vùng nghiệm, với các giá trị (x = 0, y = 1) và (x = 0, y = -1) .

Người giới thiệu

1. Avriel, M. 2003. Lập trình phi tuyến. Nhà xuất bản Dover.
2. Bazaraa. 1979. Lập trình phi tuyến. John Wiley và các con trai.
3. Bertsekas, D. 1999. Lập trình phi tuyến: ấn bản thứ 2. Athena Scientific.
4. Nocedal, J. 1999. Tối ưu hóa số. Springer-Verlag.
5. Wikipedia. Lập trình phi tuyến. Phục hồi từ: es.wikipedia.com