Giáo trình tối ưu hóa - Chương 5 pptx

105

Chương V

Một số phương pháp quy hoạch phi tuyến

1. Các khái niệm cơ bản của bài toán tối ưu phi tuyến

1.1. Phát biểu bài toán tối ưu phi tuyến

Cho các hàm số f, gj : Rn → R, j = 1, 2, ..., m. Bài toán tối ưu tổng quát có dạng chính tắc

như sau:

Max (Min) f(x),

với các ràng buộc

(i) gj(x) ≤ 0, j = 1, 2, …, k,

(ii) gj(x) = 0, j = k+1, k+2, …, m.

Nếu hàm mục tiêu f(x) hoặc ít nhất một trong các hàm ràng buộc gj(x), j = 1,

2, …, m là phi tuyến thì chúng ta có bài toán tối ưu phi tuyến, hay còn gọi là bài toán quy hoạch

phi tuyến (BTQHPT). Các dạng khác của bài toán tối ưu có thể đưa về dạng chính tắc trên đây

theo những quy tắc nhất định.

Với ký hiệu D ⊂ Rn

là miền ràng buộc (hay miền các phương án khả thi) cho bởi các ràng

buộc (i) và / hoặc (ii) thì BTQHPT có thể viết gọn hơn như sau: f(x) → Max (Min), với x ∈ D.

Trong trường hợp D ≡ Rn

, ta có BTQHPT không ràng buộc. Nếu trái lại, D là tập con thực sự của

Rn

thì có BTQHPT có ràng buộc.

Ví dụ 1. Bài toán sau là BTQHPT không có ràng buộc:

Min z = f(x) = 2x1

2

+ 3x2

2

+ 4x1x2 – 6x1 – 3x2.

Trong khi đó, bài toán sau đây là BTQHPT có ràng buộc:

Min f(x) = 2x1

2

+ 3x2

2

+ 4x1x2 – 6x1 – 3x2

với các ràng buộc

1 2

1 2

1 2

x x1

2x 3x 4

x ,x 0.

⎧ + ≤

⎪

⎨ + ≤

⎪ ≥ ⎩

106

Định nghĩa 1. Điểm x = (x1, x2, ..., xn) ∈ D ⊂ Rn được gọi là phương án khả thi (hay

phương án, nếu nói vắn tắt) của bài toán tối ưu: Max (Min) f(x), với x ∈ D ⊂ Rn

. Các toạ độ thành

phần của điểm x được gọi là các biến quyết định.

Định nghĩa 2. Đối với bài toán cực đại hoá: Max f(x), với x ∈ D ⊂ Rn

, điểm

x* = ( 1 x∗ , 2 x∗ , ..., n x∗ ) ∈ Rn được gọi là điểm tối ưu (hay phương án tối ưu) toàn cục nếu x* ∈ D

và f(x*) ≥ f(x), ∀x ∈ D. Điểm x ∈ Rn được gọi là điểm tối ưu (hay phương án tối ưu) địa phương

nếu x ∈ D và f( x ) ≥ f(x), ∀x ∈ Nε ∩ D với Nε là một lân cận đủ nhỏ của điểm x . Đối với bài

toán cực tiểu hoá: Min f(x), với x ∈ D ⊂ Rn

, điểm x* ∈ Rn được gọi là điểm tối ưu (hay phương

án tối ưu) toàn cục nếu x* ∈ D và f(x*) ≤ f(x), ∀x ∈ D. Điểm x ∈ Rn được gọi là điểm tối ưu

(hay phương án tối ưu) địa phương nếu x ∈ D và f( x ) ≤ f(x), ∀x ∈ Nε ∩ D với Nε là một lân cận

đủ nhỏ của điểm x .

Các phương án tối ưu địa phương hay toàn cục đều được gọi chung là phương án tối ưu. Dễ

thấy, mọi phương án tối ưu toàn cục cũng là phương án tối ưu địa phương, trong khi đó một

phương án tối ưu địa phương không nhất thiết là phương án tối ưu toàn cục. Trong các BTQHPT

ứng dụng, phương án tối ưu toàn cục có một ý nghĩa quan trọng. Chẳng hạn trong thiết kế máy,

sau khi dùng phương pháp phân tích hồi quy nhiều chiều, ta thường thu được hàm mục tiêu f(x)

có dạng phi tuyến và sau đó phải tìm kiếm phương án tối ưu toàn cục. Các BTQHPT toàn cục

cũng có thể nảy sinh trong quy hoạch kinh tế – sinh thái vùng, chuyển đổi cơ cấu cây trồng và

nhiều lĩnh vực kinh tế – kỹ thuật khác.

Có nhiều phương pháp giải các lớp BTQHPT, nhưng chưa có phương pháp nào tỏ ra hữu

hiệu cho mọi BTQHPT. Bởi vậy lý thuyết và thuật toán tối ưu phi tuyến là một khoa học đang

ngày càng phát triển phong phú cả về chiều sâu cũng như chiều rộng.

1.2. Phân loại các phương pháp giải bài toán quy hoạch phi tuyến toàn cục

Các phương pháp giải BTQHPT toàn cục được phân ra thành hai lớp: phương pháp tất định

(deterministic methods) và phương pháp ngẫu nhiên (stochastic methods).

Phương pháp tất định sử dụng các tính chất giải tích của hàm mục tiêu và các hàm ràng

buộc. Một số dạng bài toán tối ưu toàn cục với những tính chất giải tích nhất định của hàm mục

tiêu và các hàm ràng buộc có thể giải được bằng các phương pháp tất định thích hợp, chẳng hạn

như phương pháp quy hoạch toàn phương, quy hoạch tách, quy hoạch lồi, quy hoạch d.c… Trong

các trường hợp đó phương án tối ưu toàn cục có thể tìm được sau một số hữu hạn bước tính toán

với độ chính xác chọn trước. Tuy nhiên, đối với nhiều lớp bài toán tối ưu toàn cục phương pháp

tất định tỏ ra không có hiệu quả.

Trong khi đó, các phương pháp ngẫu nhiên như: phương pháp đa khởi tạo (multistart), mô

phỏng tôi (simulated annealing), thuật giải di truyền (genetic algorithm), kỹ thuật tìm kiếm ngẫu

nhiên có điều khiển (controlled random search technique)… có thể áp dụng để giải các bài toán

tối ưu toàn cục dạng bất kỳ, không đòi hỏi các tính chất đặc biệt của hàm mục tiêu hay các hàm

ràng buộc. Các phương pháp ngẫu nhiên đặc biệt tỏ ra có hiệu quả đối với các BTQHPT nguyên

107

và hỗn hợp nguyên. Tuy nhiên, các phương pháp này thường chỉ cho phương án “gần” tối ưu khá

tốt sau một số hữu hạn bước mà không kiểm soát được độ chính xác của phương án tìm được.

Để bắt đầu nghiên cứu về quy hoạch phi tuyến, trong chương này, chúng ta sẽ giới hạn

trong việc tìm hiểu một số khái niệm cơ bản cũng như làm quen với một số phương pháp cổ điển

trong tối ưu phi tuyến.

1.3. Bài toán quy hoạch lồi

Định nghĩa 3. Tập lồi là tập S ⊂ Rn

có tính chất: mọi đoạn thẳng nối x1

, x

2

∈ S đều

nằm trong S. Nói cách khác, S ⊂ Rn

là tập lồi khi và chỉ khi ∀ x

1

, x

2

∈ S, ∀ λ ∈ [0,1] thì x

= λx

1

+ (1 – λ) x2

∈ S.

Ví dụ 2. Các tập S sau đây là tập lồi:

i) S = {x = (x1, x2, x3) ∈ R3

: 2x1 – x2 + 3x3 = 5}.

ii) S = {x = (x1, x2, , x3) ∈ R3

: 2x1 – x2 + 3x3 ≤5}.

iii) S = {x = (x1, x2, , x3)

T

∈ R3

: Ax ≤ b} là tập lồi, với

A =

2

3

⎡

⎢

⎣

1

1

−

3

2

⎤

⎥

⎦

, x =

1

2

3

x

x

x

⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦

, b =

5

10

⎡ ⎤ ⎢ ⎥ ⎣ ⎦

.

Trong trường hợp iii) S là giao của các nửa không gian đóng.

iv) S = {x∈ R: x = (x1, x2): x1

2

+ x2

2 ≤ 9}.

Các tính chất của tập lồi

Cho các tập lồi S1, S2 ⊂ Rn

. Khi đó:

1) S1 ∩ S2 là tập lồi.

2) S1 + S2 = {x: x = x1

+ x2

với x1

∈S1, x

2

∈ S2} là tập lồi.

3) S1 – S2 cũng là tập lồi.

Chứng minh

Chúng ta chứng minh tính chất 2 chẳng hạn theo hướng sau: Do x ∈ S1 + S2 nên x = x1

+

x

2

với x1

∈ S1, x

2

∈ S2; y ∈ S1 + S2 nên y = y1

+ y2

với y1

∈ S1, y

2

∈ S2. Dễ dàng chứng minh

được ∀ λ ∈ [0, 1] thì λ x + (1– λ)y ∈ S1 + S2. „

Định nghĩa 4. Cho tập lồi khác rỗng S ⊂ Rn

. Hàm số f: S → R được gọi là hàm lồi nếu ∀

x

1

, x

2

∈S, ∀λ ∈ [0, 1] thì f(λx

1

+ (1 – λ)x2

) ≤ λf(x1

) + (1–λ)f(x2

) .

Ví dụ 3.

i) Xét hàm số f: S ≡ R → R với f(x) = x2

. Đây là một hàm lồi. Thật vậy, dễ thấy S là tập

lồi. Ngoài ra, f(λx

1

+ (1 – λ)x2

) ≤ λf(x1

) + (1–λ)f(x2

), ∀λ ∈ [0, 1] và ∀ x

1

, x

2

∈S (xem hình V.1).

Chẳng hạn với λ = 1/3, x1 = –1, x2 = 2 ta có λx

1

+ (1 – λ)x2

= (1/3) × (–1) + (2/3) × 2 = 1 và f(λx1 +

(1–λ)x2) = f(1) = 1 ≤ (1/3)f(–1) + (2/3)f(2) = (1/3) + (2/3) × 4 = 3.