i

Mục lục

. . . . . . . . . . . . . . . . . . . . . . . . . ii Danh mục các hình vẽ . .

. . . . . . . . . . . . . . . . . . . . . . . . . 1 Mở đầu . . . . . . . . . .

Chương 1 Kiến thức chuẩn bị 4

1.1 Tập lồi và tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Bài toán tối ưu tuyến tính đa mục tiêu . . . . . . . . . . . . . . . . 7

1.3 Tính chất tập nghiệm hữu hiệu của bài toán . . . . . . . . . . . . . 10

Chương 2 Bài toán tối ưu hai cấp 12

2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . 12 . . . .

2.2 Đưa về bài toán tối ưu một cấp . . . . . . . . . . . . . . . . 16 . . . .

2.3 Tính chất bài toán tối ưu hai cấp . . . . . . . . . . . . . . . . 18 . . .

2.4 Bài toán tối ưu hai cấp tuyến tính . . . . . . . . . . . . . . . . 22 . . .

2.5 Một số hướng ứng dụng . . . . . . . . . . . . . . . . . . . . . 25 . . .

Chương 3 Tối ưu hai cấp tuyến tính và tối ưu đa mục tiêu 27

3.1 Nội dung vấn đề . . . . . . . . . . . . . . . . . . . . . . . . 27 . . . .

3.2 Quan hệ với tối ưu đa mục tiêu . . . . . . . . . . . . . . . . 29 . . . .

3.3 Quan hệ với tối ưu trên tập nghiệm hữu hiệu . . . . . . . . . . . . . 31

. . . . . . . . . . . . . . . . . . . . . 34 . . . . Kết luận . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . 35 . . . . Tài liệu tham khảo . . . .

ii

Danh mục các hình vẽ

Bảng 2.1 So sánh nghiệm của hai Ví dụ 2.3 và 2.2

Hình 2.1 Minh họa Ví dụ 2.1

Hình 2.2 Không gian ngiệm của cấp trên (Ví dụ 2.1)

Hình 2.3 Nghiệm tối ưu của cấp trên (Ví dụ 2.2)

Hình 2.4 Không gian ngiệm của cấp trên (Ví dụ 2.3)

Hình 2.5 Nghiệm tối ưu của cấp trên (Ví dụ 2.3)

Hình 2.6 Minh họa các tập S, S(x), P (x) và M trong Ví dụ 2.4

1

Mở đầu

Luận văn đề cập tới bài toán tối ưu hai cấp (viết tắt là BPP) có dạng:

min {F (x, y) | x ∈ X, G(x, y) ≤ 0, y ∈ arg min {f (x, y) | y ∈ Y, g(x, y) ≤ 0}},

trong đó X ⊆ Rn, Y ⊆ Rm, F, G, f, g : Rm+n → R. Đây là một bài toán qui hoạch toán học theo hai nhóm biến x ∈ Rn, y ∈ Rm và trong ràng buộc của bài toán này,

y là nghiệm của bài toán tối ưu thứ hai (với y là véctơ biến và x là véctơ tham số).

Như vậy có thể hiểu đơn giản tối ưu hai cấp là bài toán tối ưu mà trong ràng buộc

của nó lại là một bài toán tối ưu khác. Bài toán tối ưu hai cấp xuất hiện trên sách

báo, tạp chí có liên quan tới các hệ thống có sự phân cấp, trong thực tế tối ưu hai cấp

nảy sinh từ nhiều ứng dụng đa dạng trong hoạt động vận tải, kinh tế, sinh thái học,

kỹ thuật, . . . Bài toán tối ưu hai cấp hiện đang được nhiều tác giả quan tâm nghiên

cứu, do ý nghĩa khoa học và khả năng ứng dụng của bài toán.

Tối ưu hai cấp được phân ra thành: các bài toán hai cấp một mục tiêu (được

nghiên cứu và ứng dụng nhiều hơn) và bài toán hai cấp nhiều mục tiêu (khó ứng

dụng hơn do ít có thuật toán hiệu quả). Khi các hàm mục tiêu và các hàm ràng buộc

trong bài toán là các hàm tuyến tính, thì ta có bài toán tối ưu hai cấp tuyến tính.

Tối ưu hai cấp là một bài toán NP - khó và thuộc lớp các bài toán tối ưu toàn cục,

nói chung rất phức tạp và khó giải. Nói riêng nó bao hàm bài toán tối ưu trên tập

nghiệm hữu hiệu (tập điểm Pareto) như một trường hợp cụ thể. Nhiều phương pháp

xử lý đã được đề xuất, tuy nhiên hiệu quả không cao và chủ yếu đối với các bài toán

hai cấp tuyến tính với một hay nhiều mục tiêu.

Đề tài luận văn

"Một số tính chất của bài toán tối ưu hai cấp"

2

có mục đích tìm hiểu và trình bày nội dung, nguồn gốc của bài toán tối ưu hai cấp,

các dạng bài toán tối ưu hai cấp và các tính chất cần biết của bài toán, đặc biệt lưu ý

trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính, nhằm giúp việc học

tập, nghiên cứu bài toán tối ưu hai cấp được thuận lợi và dễ dàng hơn. Cuối cùng,

luận văn giới thiệu một số hướng ứng dụng của tối ưu hai cấp trong thực tế.

Nội dung luận văn gồm ba chương:

Chương 1. "Kiến thức chuẩn bị” nhắc lại một số kiến thức về tập lồi đa diện,

khái niệm nghiệm hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu đa mục tiêu và

tính chất đặc trưng đối với đỉnh và cạnh hữu hiệu của bài toán tối ưu tuyến tính đa

mục tiêu.

Chương 2. "Bài toán tối ưu hai cấp" giới thiệu khái quát nội dung, xuất xứ của

bài toán tối ưu hai cấp, các tính chất cần biết của bài toán, đặc biệt lưu ý tới trường

hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính một mục tiêu. Cuối chương,

đề cập tới một số hướng ứng dụng của tối ưu hai cấp trong thực tế.

Chương 3. "Tối ưu hai cấp tuyến tính và tối ưu đa mục tiêu" xét mối liên hệ giữa

bài toán tối ưu hai cấp tuyến tính và bài toán tối ưu tuyến tính trên tập nghiệm hữu

hiệu. Có thể mô tả bài toán này dưới dạng bài toán kia, và ngược lại, Từ đó suy ra hệ

quả là bài toán tối ưu tuyến tính trên tập nghiệm hữu hiệu là NP - khó.

Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên

dưới sự giúp đỡ và hướng dẫn tận tình của GS.TS. Trần Vũ Thiệu. Qua đây tác giả

xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy, người đã dành nhiều thời gian

và tâm huyết để hướng dẫn và tạo điều kiện cho tác giả trong suốt thời gian làm luận

văn.

Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán - Tin,

Trường Đại học Khoa học Thái Nguyên và của Viện Toán học, Viện Công nghệ

thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo

mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.

Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, Khoa Toán - Tin

trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả

3

trong suốt thời gian học tập tại trường.

Cuối cùng tác giả xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn động viên,

giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và

làm luận văn.

Thái Nguyên, tháng 06 năm 2016

Học viên

Trịnh Minh Thường

4

Chương 1

Kiến thức chuẩn bị

Chương này nhắc lại một số kiến thức về tập lồi và tập đa diện, khái niệm nghiệm

hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu tuyến tính đa mục tiêu và nêu lại

các tính chất đặc trưng của đỉnh và cạnh hữu hiệu của bài toán. Nội dung của chương

được tham khảo từ các tài liệu [1], [7] và [9].

1.1 Tập lồi và tập lồi đa diện

Trước hết ta nhắc lại khái niệm tập lồi trong Rn và các khái niệm có liên quan.

Định nghĩa 1.1. Tập C ⊆ Rn được gọi là một tập lồi nếu λa + (1 − λ)b ∈ C ∀a, b ∈ C, ∀λ ∈ [0, 1], tức là C chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó.

• Ta chú ý tới một số tập lồi đặc biệt sau:

a) Tập afin là tập chứa trọn đường thẳng đi qua hai điểm bất kỳ thuộc nó.

b) Siêu phẳng là tập có dạng H = {x ∈ Rn : aT x = α}, a ∈ Rn, a (cid:54)= 0 và

α ∈ Rn.

c) Các nửa không gian đóng

H + = {x ∈ Rn : aT x ≥ α},

H − = {x ∈ Rn : aT x ≤ α}.

• Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau:

5

a) Giao của một họ bất kỳ các tập lồi là một tập lồi: C, D lồi thì C ∩ D lồi.

b) Nếu C, D ⊂ Rn là tập lồi thì C ± D = {x ± y : x ∈ C, y ∈ D} là các tập lồi.

c) Nếu C ∈ Rm, D ∈ Rn thì tích C × D = {(x, y) : x ∈ C, y ∈ D} là một tập

lồi trong Rm+n. (Có thể mở rộng cho nhiều tập lồi).

Định nghĩa 1.2. Cho E là một tập hợp bất kỳ trong Rn.

a) Giao của tất cả các tập afin chứa E gọi là bao afin của E, ký hiệu là aff E.

b) Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, ký hiệu là conv E.

Định nghĩa 1.3. a) Thứ nguyên (hay số chiều) của một tập afin M , ký hiệu dim M ,

là thứ nguyên (số chiều) của không gian con song song với nó.

b) Thứ nguyên (hay số chiều) của một tập lồi C, ký hiệu dim C, là thứ nguyên

hay số chiều của bao afin aff C của nó.

Định nghĩa 1.4. Tập lồi K ⊆ Rn được gọi là một nón lồi nếu K có thêm tính chất λx ∈ K với mọi x ∈ K và mọi λ > 0.

Định nghĩa 1.5. Một tập con lồi F của tập lồi C được gọi là một diện của C nếu

x, y ∈ C mà (1 − λ)x + λy ∈ F, 0 < λ < 1 thì [x, y] ⊂ F , tức nếu một đoạn thẳng

bất kỳ thuộc C có một điểm trong thuộc F thì cả đoạn thẳng ấy phải nằm trong F .

Một diện có số chiều 0 gọi là một điểm cực biên của C. Nói một cách khác, đó

là một điểm thuộc C mà nó không thể là một điểm trong của một đoạn thẳng bất kỳ

nào với hai đầu mút khác nhau thuộc C.

Một diện có số chiều 1 gọi là một cạnh của C: cạnh là hữu hạn nếu diện đó là

một đoạn thẳng, cạnh là vô hạn nếu diện đó là một nửa hay cả đường thẳng.

Một diện của C, khác ∅ và khác C, gọi là một diện thực sự của C. Ví dụ: các diện thực sự của một hình lập phương trong R3 là 8 đỉnh, 12 cạnh và 6 mặt của nó.

Định nghĩa 1.6. Một tập lồi mà là giao của một số hữu hạn các nửa không gian đóng

gọi là một tập lồi đa diện, ký hiệu là D. Nói cách khác, D là tập nghiệm của một hệ

6

hữu hạn các phương trình và (hoặc) bất phương trình tuyến tính.

Một tập lồi đa diện có thể bị chặn hoặc không bị chặn (không giới nội). Một tập

lồi đa diện bị chặn còn được gọi là một đa diện lồi. Các đa giác lồi theo nghĩa thông

thường trong mặt phẳng hai chiều (tam giác, hình vuông, hình tròn,...) là những ví dụ cụ thể về đa diện lồi trong R2.

Tập lồi đa diện mà đồng thời là một nón, còn được gọi là một nón lồi đa diện.

Mỗi điểm cực biên của tập lồi đa diện được gọi là một đỉnh của tập đa diện đó.

Định nghĩa 1.7. Đoạn thẳng [x1, x2], x1 (cid:54)= x2, được gọi là một cạnh hữu hạn của D nếu x1, x2 là các đỉnh của D và rank {ai : (cid:10)ai, x1(cid:11) = (cid:10)ai, x2(cid:11) = bi} = n − 1.

Định nghĩa 1.8. Tia Γ = {x0 + λd : λ ≥ 0} ⊆ D, trong đó x0 ∈ D, d ∈ Rn, được gọi là một cạnh vô hạn của D nếu

rank {ai : (cid:10)ai, x(cid:11) = bi, ∀x ∈ Γ} = n − 1.

Để hiểu rõ hơn về tập lồi đa diện ta cũng cần biết một số khái niệm sau đây.

Trong các bài toán tối ưu, ta thường gặp tập lồi đa diện có dạng

D = {x ∈ Rn : Ax ≤ b, x ≥ 0} với A ∈ Rm×n, b ∈ Rm},

tức D là tập nghiệm không âm của một hệ (hữu hạn) bất phương trình tuyến tính.

Tập này không chứa đường thẳng nào (do x ≥ 0) nên D có đỉnh. Từ các định

nghĩa nêu trên cho thấy:

a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi hệ véctơ

k = 0}

{ak : (cid:10)ak, x0(cid:11) = bk} ∪ {ek : x0

có hạng bằng n.

b) Các hướng cực biên (chuẩn hóa) của D là các nghiệm cơ sở của hệ

Ay ≤ 0, eT y = 1, y ≥ 0, trong đó eT = (1, . . . , 1).

7

c) Giả sử tia Γ = {x0 + λd : λ ≥ 0}, trong đó x0 là một đỉnh và d là một hướng cực

biên của D. Khi đó Γ là một cạnh vô hạn của D khi và chỉ khi

rank ({ak : (cid:10)ak, x(cid:11) = bk, ∀x ∈ Γ} ∪ {ek : xk = 0, ∀x ∈ Γ}) = n − 1.

Bây giờ cho tập lồi đa diện D (cid:54)= ∅ xác định bởi hệ bất phương trình tuyến tính

(cid:10)ai, x(cid:11) ≥ bi, i = 1, 2, . . . , m.

Với x ∈ D, ký hiệu I(x) = {i : (cid:10)ai, x(cid:11) = bi} là tập chỉ số những ràng buộc mà x thỏa mãn chặt. Đặt I0 = {i : (cid:10)ai, x(cid:11) = bi, ∀x ∈ D}. Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của D được cho trong định lý sau.

Định lí 1.1 (Diện của tập lồi đa diện). Một tập con lồi khác rỗng F ⊂ D là một diện

thực sự của D khi và chỉ khi

F = {x : (cid:10)ai, x(cid:11) = bi, i ∈ I, (cid:10)ai, x(cid:11) ≥ bi, i (cid:54)∈ I}

với I là tập chỉ số sao cho I0 ⊂ I ⊂ {1, . . . , m} (I gọi là tập chỉ số xác định diện

F ). Hơn nữa, ta có dim F = n − rank {ai : i ∈ I} và dim P = n − rank {ai : i ∈ I0}.

Hệ quả 1.1. Cho D là tập lồi đa diện xác định bởi hệ (cid:10)ai, x(cid:11) ≥ bi, i = 1, . . . , m:

a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi rank {ai : i ∈ I(x0)} = n, nghĩa

là x0 thỏa mãn chặt n ràng buộc độc lập tuyến tính của D;

b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) Γ ⊂ D là một cạnh

của D thì Γ được xác định bởi một tập chỉ số I sao cho rank {ai : i ∈ I} = n − 1.

1.2 Bài toán tối ưu tuyến tính đa mục tiêu

Xét bài toán tối ưu đa mục tiêu có dạng:

(MOPP) V min h(x) = [h1(x), . . . , hp(x)] với x ∈ U,

8

với h : Rn → Rp là véctơ hàm mục tiêu, U ⊆ Rn là tập ràng buộc của bài toán.

Để giải (MOPP), ta cần phải so sánh các véctơ hàm mục tiêu [h1(x), . . . , hp(x)]

đối với các x ∈ U khác nhau. Vì thế, ta cần xác định một quan hệ thứ tự trên h(U ), dùng để so sánh. Vì với p ≥ 2, trong Rp không có thứ tự toàn phần như trong R1 nên

ta chỉ có thể xác định một thứ tự bộ phận trên h(U ). Giả sử K là một nón tùy ý sao cho K ⊂ Rp, một quan hệ nhị nguyên (hai ngôi) theo nón K, ký hiệu ≤K, được xác

định bởi

a ≤K b khi và chỉ khi (b − a) ∈ K.

Quan hệ thứ tự bộ phận tạo ra bởi các nón lồi, đóng và nhọn hay được sử dụng

nhất. Do không thể tìm được một nghiệm mà là tối ưu đồng thời cho mọi hàm mục

tiêu, nên ta dùng một khái niệm yếu hơn, đó là khái niệm điểm không bị vượt trội.

Định nghĩa 1.9. Điểm y0 ∈ h(U ) gọi là điểm không bị vượt trội (non-dominated point) theo nón K nếu không tồn tại điểm y ∈ h(U ), y (cid:54)= y0 sao cho y ≤K y0. Nếu y∗ ∈ h(U ) là điểm không bị vượt trội theo nón K thì x∗ ∈ U sao cho y∗ = h(x∗) gọi

là điểm tối ưu Pareto (Pareto-optimal point) theo nón K.

Định nghĩa sau đây về các điểm hữu hiệu hay được sử dụng trên thực tế.

Định nghĩa 1.10. Điểm x∗ ∈ U gọi là điểm tối ưu Pareto hay nghiệm hữu hiệu

(efficiant solution) của bài toán (MOPP) nếu không tồn tại x ∈ U sao cho

[h1(x), . . . , hp(x)] ≤ [h1(x∗), . . . , hp(x∗)] và

[h1(x), . . . , hp(x)] (cid:54)= [h1(x∗), . . . , hp(x∗)].

Nếu x∗ là một điểm tối ưu Pareto thì h(x∗) gọi là một điểm không bị vượt trội

+ \ {0p}).

(theo nón K ≡ Rp

Khi đó các nghiệm hữu hiệu, hay nghiệm tối ưu Pareto, là những nghiệm mà

không thể cải tiến theo một mục tiêu nào đó mà lại không làm thiệt hại ít nhất một

+ \ {0p}.

mục tiêu khác. Ta nhận xét là Định nghĩa 1.10 là một trường hợp đặc biệt của Định nghĩa 1.9 với nón được sử dụng là Rp

9

Giải một bài toán tối ưu đa mục tiêu có nghĩa là tìm một phần hay toàn bộ tập

nghiệm hữu hiệu và đệ trình nó cho người ra quyết định xem xét, đánh giá và lựa

chọn. Khi đó, nghiệm do người ra quyết định lựa chọn (chẳng hạn theo một tiêu

chuẩn nào đó) được xem là nghiệm tối ưu của bài toán tối ưu đa mục tiêu đã cho.

• Khi h(x) là một ánh xạ tuyến tính và U là một tập lồi đa diện thì ta có bài toán

tối ưu tuyến tính đa mục tiêu, ký hiệu là (MOLP). Có thể phát biểu như sau:

V min{Cx : x ∈ D} (MOLP)

với C là ma trận cấp p × n và D ⊆ Rn là một tập lồi đa diện được xác định bởi hệ

(cid:10)ai, x(cid:11) ≥ bi, i = 1, 2, . . . , m.

với ai ∈ Rn và bi ∈ R (i = 1, . . . , m) cho trước.

Sau đây là một số khái niệm về nghiệm của bài toán (MOLP).

Định nghĩa 1.11. Ta nói x0 ∈ D là một nghiệm hữu hiệu của (MOLP) nếu không tồn tại x ∈ D với Cx0 ≥ Cx và Cx0 (cid:54)= Cx. Nếu mọi điểm thuộc diện F ⊆ D là

nghiệm hữu hiệu thì ta nói F là một diện nghiệm hữu hiệu hay đơn giản, diện hữu

hiệu. Nếu diện hữu hiệu F là một đỉnh (hay cạnh) của D thì để đơn giản, ta nói F là

một đỉnh hữu hiệu (hay cạnh hữu hiệu) của (MOLP).

Định nghĩa 1.12. Ta nói x0 ∈ D là một nghiệm hữu hiệu yếu của (MOLP) nếu không có x ∈ D với Cx0 > Cx. Ta còn nói x0 ∈ D là một nghiệm hữu hiệu lý tưởng

nếu Cx0 ≤ Cx với mọi x ∈ D.

10

Hình 1.1 minh họa tập nghiệm hữu hiệu trong R2 khi C = I2 (ma trận đơn vị).

Rõ ràng một nghiệm hữu hiệu cũng là nghiệm hữu hiệu yếu, nhưng điều ngược

lại không chắc đúng.

1.3 Tính chất tập nghiệm hữu hiệu của bài toán

Ta nêu lại bài toán (MOLP):

V min{Cx : x ∈ D} với C ∈ Rp×n và D = {x ∈ Rn : (cid:10)ai, x(cid:11) ≥ bi, i = 1, 2, . . . , m},

trong đó ai ∈ Rn, bi ∈ R(i = 1, . . . , m) cho trước. Giả thiết D (cid:54)= ∅.

Mục này quan tâm chủ yếu tới các nghiệm hữu hiệu của bài toán (MOLP). Ký

hiệu E(D) là tập các nghiệm hữu hiệu của bài toán (MOLP).

Ta chú ý tới một số tính chất sau đây của tập nghiệm hữu hiệu của (MOLP).

Mệnh đề 1.1. Điểm x0 ∈ D là một nghiệm hữu hiệu của (MOLP) khi và chỉ khi tồn tại véctơ dương λ ∈ Rp (λ > 0) sao cho x0 là nghiệm cực tiểu của hàm tuyến tính

f (x) = λT Cx trên D.

Mệnh đề 1.2. Nếu tập D bị chặn thì (MOLP) chắc chắn có nghiệm hữu hiệu.

Mệnh đề 1.3. Tập nghiệm hữu hiệu của (MOLP) là liên thông đường gấp khúc, theo

nghĩa với bất kỳ hai nghiệm hữu hiệu x, y ∈ D, tồn tại hữu hạn nghiệm hữu hiệu

x1, . . . , xk sao cho x1 = x, xk = y và mọi đoạn [xi, xi+1], i = 1, . . . , k − 1, là hữu

hiệu.

Với mỗi x0 ∈ D, đặt tương ứng bài toán qui hoạch tuyến tính theo biến x:

max {eT C(x0 − y) | Cx0 ≥ Cx, x ∈ D}, (LP0)

trong đó e là véctơ p chiều với mọi phần tử bằng 1 (p - số mục tiêu trong (MOLP)).

Kết quả sau chỉ ra lược đồ hay được dùng để kiểm tra một điểm chấp nhận được

x0 là nghiệm hữu hiệu (dr tối ưu Pareto) của bài toán (MOLP1).

11

Mệnh đề 1.4. x0 ∈ E(D) khi và chỉ khi giá trị tối ưu của (LP0) bằng 0. Hơn nữa, mỗi nghiệm tối ưu của (LP0) là một nghiệm hữu hiệu, tức là thuộc E(D), bất kể x0

có là nghiệm hữu hiệu của (MOLP) hay không.

Kết luận, chương này đã đề cập tới bài toán tối ưu đa mục tiêu và trường hợp

riêng là bài toán tối ưu tuyến tính đa mục tiêu, nhắc lại một số khái niệm có liên

quan đến bài toán như: tập lồi đa diện và các đỉnh, cạnh, diện của tập lồi đa diện,

khái niệm điểm tối ưu Pareto hay nghiệm hữu hiệu của bài toán đa mục tiêu và giới

thiệu tóm tắt tính chất đặc trưng của các đỉnh và cạnh hữu hiệu của bài toán tối ưu

tuyến tính đa mục tiêu.

12

Chương 2

Bài toán tối ưu hai cấp

Chương này trình bày nội dung, nguồn gốc của bài toán tối ưu hai cấp, các tính

chất của bài toán, đặc biệt lưu ý tới trường hợp riêng quan trọng là bài toán tối ưu hai

cấp tuyến tính một mục tiêu. Cuối chương, đề cập tới một số hướng ứng dụng của

tối ưu hai cấp trong thực tế. Nội dung của chương được tham khảo chủ yếu từ các tài

liệu [2] - [8] và [10].

2.1 Nội dung bài toán

Bài toán tối ưu hai cấp (Bilevel Programming Problem, viết tắt là BPP) nảy sinh

từ nhiều ứng dụng khác nhau trong vận tải, kinh tế, sinh học, kỹ thuật,... Tối ưu hai

cấp xuất hiện trên sách báo, tạp chí thường có liên quan đến các hệ thống phân cấp.

Tối ưu hai cấp bao gồm hai bài toán tối ưu, trong đó một phần dữ liệu của bài toán

thứ nhất được xác định ẩn thông qua nghiệm của bài toán thứ hai. Người ra quyết

định ở mỗi cấp cố gắng tối ưu hóa (cực tiểu hay cực đại) hàm mục tiêu riêng của cấp

mình mà không để ý tới mục tiêu của cấp kia, nhưng quyết định của mỗi cấp lại ảnh

hưởng tới giá trị mục tiêu của cả hai cấp và tới không gian quyết định nói chung.

• Ví dụ thực tế: Bài toán thu lệ phí giao thông

Để làm ví dụ, ta xét tình huống thực tế sau đây trong lĩnh vực giao thông đường

bộ: Mạng giao thông đường bộ của một vùng nào đó (miền Bắc chẳng hạn), gồm

nhiều đường quốc lộ và đường liên tỉnh, liên kết với nhau và nối liền nhiều tỉnh,

thành phố. Cơ quan quản lý (cấp trên) dự tính thu lệ phí một số tuyến đường trong

hệ thống và mục tiêu mong muốn là tối đa hóa số tiền thu được. Với mỗi mức thu

13

phí đề ra, người tham gia giao thông (cấp dưới) sẽ đáp lại và tìm hành trình đi lại sao

cho làm cực tiểu tổng chi phí bỏ ra, có tính toán, cân nhắc các yếu tố có liên quan

như thời gian, khoảng cách, hao phí xăng xe, lệ phí... và lựa chọn hành trình đi tối

ưu, khi tham gia giao thông trong hệ thống. Nếu cấp trên đặt lệ phí quá cao, người

tham gia giao thông sẽ từ chối chọn các tuyến đường có chi phí đắt và hệ quả là cơ

quan quản lý thu được ít kinh phí hơn. Vậy bài toán đặt ra cho cơ quan quản lý (cấp

trên) là đặt mức lệ phí trên những tuyến đường nào và mức thu bao nhiêu là có lợi

nhất (thu về được nhiều tiền nhất).

• Mô hình toán học

Sau đây là phát biểu toán học của một số dạng bài toán tối ưu hai cấp.

Bài toán tối ưu hai cấp một mục tiêu:

F (x, y) với điều kiện G(x, y) ≤ 0. (BPP) Tìm min x,y

trong đó với mỗi giá trị x, y là nghiệm tối ưu của bài toán thứ hai:

y

Tìm min f (x, y) với điều kiện g(x, y) ≤ 0.

với x ∈ X ⊆ Rn, y ∈ Y ⊆ Rm, F, f : Rn × Rm → R lần lượt là hàm mục

tiêu của bài toán ngoài (bài toán cấp trên) và bài toán trong (bài toán cấp dưới), G, g : Rn × Rm → R là các hàm ràng buộc của các bài toán tương ứng. Ta thấy

(BPP) là một bài toán qui hoạch toán học có chưa bài toán tối ưu ở các ràng buộc

của nó.

• Trường hợp riêng: Khi X, Y là các tập đa diện và F, f, G, g là các hàm tuyến

tính afin, (BPP) gọi là bài toán tối ưu tuyến tính hai cấp (viết tắt là BLPP) hay trò

chơi Stackelberg tuyến tính).

• Tối ưu hai cấp đa mục tiêu Khi F và f là các véctơ hàm, tức là

F : Rn × Rm → Rp và f : Rn × Rm → Rq,

ta có bài toán tối ưu đa mục tiêu hai cấp (viết tắt là BMOPP).

Các bài toán tối ưu hai cấp, trong đó mỗi cấp chỉ có một hàm mục tiêu (bài toán

14

(BPP)) đã được nhiều người nghiên cứu. Với các bài toán mà mục tiêu và các ràng

buộc là hàm tuyến tính (bài toán (BLPP)), đã có một số kết quả lý thuyết, ứng dụng

và phương pháp giải cụ thể. Tuy nhiên, các bài toán tối ưu hai cấp, trong đó mỗi cấp

có nhiều hàm mục tiêu (bài toán (BMOPP)) ít được đề cập tới trong các tài liệu. Sự

thiếu vắng các nghiên cứu như thế có lẽ là do có những khó khăn nhất định trong tìm

kiếm và xác định các nghiệm tối ưu.

Trong bài toán hai cấp, mỗi cấp được quyền điều khiển (chọn giá trị) một số biến

quyết định của cấp mình. Mỗi cấp đề ra quyết định nhằm tối ưu hóa mục tiêu riêng

của cấp mình, tuy nhiên giá trị hàm mục tiêu đó thường phụ thuộc một phần các biến

do cấp kia điều khiển.

Sự tương tác giữa hai cấp phản ánh tình huống xây dựng quyết định theo kiểu

phi tập trung hóa, nghĩa là cấp cao hơn (cấp trên, lãnh đạo hay chủ cái) chỉ có thể

gây ảnh hưởng chứ không ra lệnh hay ép buộc cấp dưới (người dưới quyền hay người

cùng chơi) lựa chọn.

Khả năng ứng dụng của tối ưu hai cấp bị hạn chế bởi nhiều khó khăn về tính toán

do bài toán hai cấp thường là bài toán không lồi và không liên thông, thuộc lớp bài

toán NP-khó và do thiếu các thuật toán giải hiệu quả.

• Nguồn gốc bài toán tối ưu hai cấp

Tối ưu hai cấp bắt nguồn từ qui hoạch toán học và lý thuyết trò chơi.

A. Phát biểu đầu tiên về bài toán tối ưu hai cấp xuất hiện trong bài báo của

Bracken J. và McGill J. [5], mặc dù tên gọi tối ưu hai cấp và nhiều cấp chính thức

được sử dụng lần đầu trong báo cáo của Candler W. và Norton R. [6]. Tuy nhiên, mãi

sau thập kỷ 80 thế kỷ 20, các bài toán tối ưu hai cấp và nhiều cấp mới bắt đầu nhận

được sự chú ý và thực sự phát triển.

B. Được thúc đẩy bởi lý thuyết trò chơi Stackelberg [10], một số tác giả đã đẩy

mạnh nghiên cứu tối ưu hai cấp và qua đó đã thúc đẩy sự phát triển của tối ưu hai

cấp trong cộng đồng qui hoạch toán học. Một số khái niệm trong tối ưu hai cấp hay

nhiều cấp bắt nguồn từ các thuật ngữ dùng trong lý thuyết trò chơi như chủ cái, người

cùng chơi, chiến lược, xung đột, cạnh tranh, cân bằng,...

15

Mỗi trò chơi thường bao gồm nhiều người chơi, mỗi người chơi có một số cách

chơi hay chiến lược chơi và sẽ phải nộp (hay nhận) số tiền trả tương ứng với cách

chơi đó. Đơn giản nhất là trò chơi hai người với tổng 0 hay còn gọi là trò chơi đối

kháng. Trong trò chơi này, số tiền thắng của người này bằng số tiền thua của người

kia và lập nên một ma trận trả tiền. Mỗi người chơi đều biết thông tin về cách chơi

của người kia và số tiền trả tương ứng. Cả hai ra quyết định (công bố chiến lược chơi)

cùng một lúc. Hai người chơi độc lập và không hợp tác với nhau.

Các trò chơi dân gian như trò chơi tung đồng xu, trò chơi gieo xúc sắc và trò chơi

"Giấy - Búa - Kéo" (hay trò chơi "One - Two - Three") thuộc loại trò chơi đối kháng,

hai đấu thủ.

Tiếp theo là trò chơi song ma trận với hai người chơi, trong đó số tiền thắng của

người này khác số tiền thua của người kia, mỗi người chơi trả tiền theo một ma trận

riêng. Hai người chơi ra quyết định theo thứ tự qui định (người trước, kẻ sau). Mục

đích của mỗi người chơi là tìm chiến lược chơi đem lại lợí ích cao nhất (hay chi phí

thấp nhất) cho người chơi đó.

Trạng thái của trò chơi mà không người chơi nào được lợi hơn nếu người đó đơn

phương thay đổi chiến lược chơi của mình, trong khi đối phương giữ nguyên chiến

lược chơi của họ, được gọi là nghiệm cân bằng Nash (Nash equili-brium).

Phát triển tiếp là trò chơi Stackelberg với qui tắc chơi hơi khác. Người chơi giữ

quyền ra quyết định trước gọi là chủ cái (leader). Những người chơi sau đáp trả lại

quyết định (chiến lược) của chủ cái gọi là người chơi thứ cấp (followers). Hành động

của người chơi này tác động đến hàm mục tiêu (lợi ích hay chi phí) và sự lựa chọn

quyết định của người kia, và ngược lại.

Theo quan điểm qui hoạch toán học, trò chơi Stackelberg là một bài toán tối ưu

hai cấp, theo nghĩa có một bài toán mức trên (chủ cái hành động trước, cố gắng tối

ưu hóa mục tiêu của mình) và một bài toán mức dưới (những người chơi thứ cấp hành

động sau chủ cái, tìm cực tiểu chi phí hay cực đại lợi ích riêng của họ). Trong thực

tế, thường chủ cái có thể là một hãng lớn nổi trội trong một thị trường cạnh tranh nào

đó và những người chơi còn lại là những hãng kinh doanh nhỏ hơn trong thị trường

16

đó.

2.2 Đưa về bài toán tối ưu một cấp

Xét bài toán tối ưu hai cấp (BPP). Tập ràng buộc của bài toán cấp dưới phụ thuộc

x, ký hiệu S(x) với

S(x) = {y ∈ Rm : g(x, y) ≤ 0, y ∈ Y }.

Tập nghiệm cực tiểu của bài toán cấp dưới, ký hiệu P (x), được xác định bởi

P (x) = {y : y ∈ arg min {f (x, y) : y ∈ S(x)}}.

Bài toán tối ưu hai cấp (BPP) ban đầu được viết lại thành

{F (x, y) : G(x, y) ≤ 0, x ∈ X, y ∈ P (x)} min x,y

với tập ràng buộc (còn gọi là miền cảm sinh) của bài toán bây giờ là

M = {(x, y) ∈ Rn+m : G(x, y) ≤ 0, x ∈ X, y ∈ P (x)}.

Tập này nói chung không lồi, đôi khi không liên thông, thậm chí có thể rỗng.

Ví dụ 2.1. Xét một ví dụ đơn giản về bài toán tối ưu hai cấp: Tìm x, y ∈ R đạt

F (x, y) = x − 2y min x,y

với điều kiện

 −x + 3y − 4 ≤ 0 và với mỗi x ∈ R

y là nghiệm cực tiểu của bài toán

{f (x, y) = x + y : x − y ≤ 0, −x − y ≤ 0}.   min y

Tập ràng buộc của bài toán cấp dưới phụ thuộc x, ký hiệu S(x) với

S(x) = {y ∈ R : x − y ≤ 0, −x − y ≤ 0} = {y ∈ R : y ≥ |x|}.

17

Tập nghiệm cực tiểu của bài toán cấp dưới, ký hiệu P (x), được xác định bởi

P (x) = {y : y ∈ arg min {x + y : y ∈ S(x)}} = {y : y = |x|}

Bài toán tối ưu hai cấp (BPP) ban đầu được viết lại thành

{x − 2y : − x + 3y − 4 ≤ 0, y ∈ P (x)}. min x,y

Tập ràng buộc (còn gọi là miền cảm sinh) của bài toán cấp trên (Hình 2.1)

M = {(x, y) : − x +3y − 4 ≤ 0, y ∈ P (x)} = {(x, y) : − x +3y − 4 ≤ 0, y = |x|}.

Miền cảm sinh của bài toán hai cấp không lồi, nhưng liên thông. Đó là tập

M = {(x, y) : − x + 3y − 4 ≤ 0, y ∈ P (x)}

= {(x, y) : − x + 3y − 4 ≤ 0, y = |x|}

= {(x, y) : y = −x, −1 ≤ x ≤ 0} ∪ {(x, y) : y = x, 0 ≤ x ≤ 2}.

• Nếu như ràng buộc của bài toán hai cấp nêu trên được đổi thành

−x + 3y − 4 ≤ 0, −y + 0, 5 ≤ 0

thì miền cảm sinh của bài toán đó trở thành tập không lồi và không liên thông:

M = {(x, y) : y = −x, −1 ≤ x ≤ −0, 5} ∪ {(x, y) : y = x, 0, 5 ≤ x ≤ 2}.

Trong cả hai trường hợp, bài toán hai cấp có hai điểm cực tiểu địa phương

(- 1, 1) và (2, 2), trong đó điểm (- 1, 1) là cực tiểu toàn cục của bài toán với

Fmin = F (−1, 1) = −3.

18

2.3 Tính chất bài toán tối ưu hai cấp

Tối ưu hai cấp nghiên cứu sự tồn tại nghiệm và các tính chất nghiệm của bài toán,

các điều kiện tối ưu, các thuật toán tìm nghiệm và phân tích độ phức tạp của bài toán.

Bài toán tối ưu hai cấp có một số điểm cần chú ý như sau.

• Về độ phức tạp của bài toán: Người ta đã chứng minh được rằng ngay cả bài

toán tối ưu hai cấp tuyến tính, trong đó mọi hàm là tuyến tính, là một bài toán NP -

khó, theo nghĩa nếu bài toán này có thể giải được bằng một thuật toán thời gian đa

thức thì nhiều bài toán khó khác cũng sẽ giải được bằng các thuật toán thời gian đa

thức. Cũng có thể dễ dàng xây dựng các bài toán tối ưu hai cấp tuyến tính có số điểm

cực tiểu địa phương tăng theo cấp hàm mũ theo số biến của bài toán. Nhiều kết quả

lý thuyết đáng chú ý khác cũng đã được chứng minh về mối liên hệ giữa tối ưu hai

cấp với các lĩnh vực khác của qui hoạch toán học. Chẳng hạn, có thể chỉ ra rằng các

bài toán minmax, bài toán qui hoạch tuyến tính, qui hoạch nguyên, qui hoạch song

tuyến tính và qui hoạch toàn phương đều là các trường hợp riêng của bài toán tối ưu

hai cấp. Các lớp bài toán khác như bài toán tối ưu đa mục tiêu, bài toán Stackelberg

tĩnh cũng có quan hệ mật thiết vối bài toán tối ưu hai cấp.

• Về thuật toán giải: Có các thuật toán điểm cực biên cho bài toán tối ưu hai cấp

tuyến tính, thuật toán nhánh cận và thuật toán xoay vần bù tìm cực tiểu toàn cục cho

bài toán với cấp trên tuyến tính, cấp dưới tuyến tính hoặc lồi toàn phương. Phương

pháp hướng giảm và phương pháp phạt tìm cực tiểu địa phương cho các bài toán tối

ưu hai cấp phi tuyến.

• Một số mở rộng: Có thể phát triển bài toán tối ưu hai cấp theo nhiều cách khác

nhau. Chẳng hạn, nếu x hoặc y hoặc cả hai bị hạn chế nhận các giá trị nguyên thì ta

có bài toán tối ưu hai cấp nguyên, nếu thay bài toán cấp dưới bằng bài toán bù tuyến

tính (hay phi tuyến) hoặc bằng bài toán bất đẳng thức biến phân thì ta có bài toán

tối ưu hai cấp suy rộng, thường gọi là bài toán tối ưu với ràng buộc cân bằng; nếu

bài toán cấp trên là một qui hoạch tuyến tính và ở cấp dưới là một bài toán tối ưu đa

mục tiêu, khi đó bài toán tối ưu hai cấp (BPP) trở thành bài toán tối ưu trên tập điểm

19

Pareto,...

• Về sự tồn tại nghiệm: Có thể thấy

+) Bài toán tối ưu hai cấp có thể vô nghiệm. Ví dụ 2.2 nêu dưới đây cho thấy điều

này.

+) Với các hàm mục tiêu F, f và các hàm ràng buộc G, g liên tục, bị chặn cũng

không đảm bảo bài toán có nghiệm.

Ví dụ 2.2 (Bard, 1998). Xét bài toán tối ưu hai cấp (BPP):

{F (x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2} min x,y

với các điều kiện

 x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0,

với mỗi x thỏa mãn điều kiện trên, y là nghiệm tối ưu của bài toán

{f (x, y) = −(x1 + 3x2)y1 − (4x1 + 2x2)y2 : y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0}.   min y

Ta thấy nghiệm tối ưu ˆy của bài toán cấp dưới (hàm phụ thuộc x) có dạng

 (1, 0) khi x1 + 3x2 > 4x1 + 2x2 hay x1 < 1 4,

ˆy(x) = y1 + y2 = 1 khi x1 = 1 4,

(0, 1)   khi x1 > 1 4.

Thay các giá trị này vào hàm mục tiêu của bài toán cấp trên ta nhận được

2x1 + 4x2 ; x1 < 1 4,

2 (0 ≤ y1 ≤ 1)

F = 2y1 + 3 ; x1 = 1 4, min x

3x1 + x2   ; x1 > 1 4.

với điều kiện x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0.

20

4, 3

4) giá trị mục tiêu của cấp dưới là f = −2, 5 và đạt tại một điểm bất kỳ trên đoạn thẳng y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0. Giá trị tối ưu tương ứng của cấp trên bằng F = 2y1 + 3

2, do đó F ∈ [ 3

2, 7

2] (do 0 ≤ y1 ≤ 1). Vì thế, cấp trên không có cách nào đảm bảo cho họ đạt được số tiền trả cực tiểu. Cho nên

Tính toán cho thấy tại x = ( 1

trong trường hợp này bài toán vô nghiệm.

• Tính đối xứng của bài toán:

+) Thứ tự ai ra quyết định trước, ai ra quyết định sau là rất quan trọng.

+) Vai trò của cấp trên và cấp dưới không đổi cho nhau được.

Ví dụ 2.3 (đảo lại thứ tự trong bài toán cho ở Ví dụ 2.2). Bài toán có nghiệm:

{f (x, y) = −(x1 + 3x2)y1 − (4x1 + 2x2)y2} min x,y

với các điều kiện

 y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0,

với mỗi y thỏa mãn các điều kiện trên, x là nghiệm tối ưu của bài toán,

{F (x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2 : x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0}.   min y

21

Nghiệm tối ưu ˆx của bài toán tối ưu cấp dưới (hàm của biến y) có dạng

 (1, 0) khi 2y1 + 3y2 < 4y1 + y2 hay y1 > 1 2,

ˆx(y) = x1 + x2 = 1 khi y1 = 1 2,

(0, 1)   khi x1 < 1 2.

Thay các giá trị này vào hàm mục tiêu của bài toán cấp trên ta nhận được

−y1 − 4y2 ; y1 > 1 2,

f = −(3 − 2x1)y1 − (2x1 + 2)y2 ; y1 = 1 2, min y

−3y1 − 2y2   ; x1 < 1 2.

với điều kiện y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0.

2, 1

2) giá trị tối ưu của bài toán cấp dưới là F = 2, 5 đạt tại một điểm

Tại y∗ = ( 1

bất kỳ trên đoạn thẳng x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0.

22

Như vậy, có thể thấy bài toán tối ưu hai cấp có các tính chất đáng chú ý sau.

∗ Nói chung, tối ưu hai cấp là một bài toán tối ưu không lồi, có thể không liên thông

và thuộc loại bài toán NP - khó.

∗ Bài toán hai cấp có thể không có nghiệm tối ưu hay nghiệm Pareto khi có nhiều

mục tiêu.

∗ Bài toán cấp trên và cấp dưới không thể đổi chỗ cho nhau, nghĩa là thứ tự theo đó

các quyết định được đưa ra là rất quan trọng.

2.4 Bài toán tối ưu hai cấp tuyến tính

Bài toán tối ưu tuyến tính hai cấp có dạng:

F (x, y) = c1x + d1y (BLPP) min x,y

với các điều kiện

 A1x + B1y ≤ b1, x ∈ X,

f (x, y) = c2x + d2y,   min y y nghiệm đúng

 A2x + B2y ≤ b2, ∀y ∈ Y.  

trong đó X ⊂ Rn, Y ⊂ Rm, x, c1, c2 ∈ Rn, y, d1, d2 ∈ Rm, A1, B1, A2, B2 và

b1, b2 là các ma trận và véctơ có kích thước thích hợp. Ta nêu một số định nghĩa:

∗ Miền ràng buộc của bài toán (BLPP):

S = {(x, y) : x ∈ X, y ∈ Y, A1x + B1y ≤ b1, A2x + B2y ≤ b2}.

∗ Tập chấp nhận được của bài toán cấp dưới với mỗi x ∈ X cố định:

S(x) = {y ∈ Y : B2y ≤ b2 − A2x}.

∗ Tập nghiệm tối ưu của bài toán cấp dưới:

P (x) = {y ∈ Y : y ∈ arg min {f (x, y) : y ∈ S(x)}}.

23

∗ Tập chấp nhận được (còn gọi là miền cảm sinh) của bài toán (BLPP):

M = {(x, y) ∈ S : y ∈ P (x)}.

Khi S và P (x) khác rỗng, bài toán (BLPP) có thể viết lại thành bài toán tối ưu

một cấp thông thường:

min {F (x, y) : (x, y) ∈ S, y ∈ P (x)} = min {F (x, y) : (x, y) ∈ M }.

Các khái niệm trên được minh họa qua ví dụ bằng số sau đây.

Ví dụ 2.4. Xét bài toán tối ưu hai cấp tuyến tính

F (x, y) = x − 4y min x≥0

với điều kiện

{f (y) = y : − x − y ≤ −3, −2x + y ≤ 0, 2x + y ≤ 12, −3x + 2y ≤ −4}. min y≥0

Với bài toán này tập S, S(x), P (x) và miền cảm sinh M được vẽ ở Hình 2.6.

24

Với bài toán hai cấp tuyến tính, Bard J. F. [4] đã chứng minh

Định lí 2.1. Tập chấp nhận được M của bài toán (BLPP) là tập nghiệm của một

ràng buộc đẳng thức tuyến tính từng khúc và tạo nên bởi giao của S với một số siêu

phẳng tựa của S.

Định lí 2.2. Nghiệm tối ưu (x∗, y∗) của bài toán (BLPP) đạt tại một đỉnh của tập S.

Các định lý này được sử dụng trong thuật toán liệt kê đỉnh của Candler và Towns-

ley. Ngoài ra, cách tiếp cận dựa trên phương pháp đơn hình và nhiều phương pháp

phạt khác nhau cũng được đề xuất.

• Sau đây là cách tiếp cận sử dụng điều kiện Karush - Kuhn - Tucker.

Cách tiếp cận này thay bài toán tối ưu cấp dưới bằng điều kiện KKT: Cố định

x = ˆx, điều kiện KKT cho điểm cực tiểu địa phương y∗ của bài toán

{f (ˆx, y) : g(ˆx, y) ≥ 0} min y

là

∇yf (ˆx, y∗) − µT ∇yg(ˆx, y∗) = 0,

µT g(ˆx, y∗) = 0, µ ≥ 0.

Bài toán cấp dưới

{f (x, y) = c2x + d2y : A2x + B2y ≤ b2, y ≥ 0} = min y∈Y

{f (x, y) = c2x + d2y : b2 − A2x − B2y ≥ 0, y ≥ 0} min y∈Y

được thay bằng điều kiện KKT (các biến đối ngẫu u, v là các véctơ hàng):

d2 + uB2 − v = 0,

u(b2 − A2x − B2y) + vy = 0,

u, v ≥ 0.

Khi đó có thể viết lại bài toán (BLPP) thành (theo các biến x, y, u, v)

{F (x, y) = c1x + d1y} min x∈X

25

với các điều kiện

A1x + B1y ≤ b1,

uB2 − v = −d2,

u(b2 − A2x − B2y) + vy = 0,

A2x + B2y ≤ b2,

x ≥ 0, y ≥ 0, u ≥ 0, v ≥ 0.

2.5 Một số hướng ứng dụng

Mô hình bài toán tối ưu hai cấp thường được áp dụng vào các hệ thống có cấu

trúc phân cấp, trong đó quyết định của cấp trên có ảnh hưởng tới quyết định của cấp

dưới mà không cần can thiệp trực tiếp vào hoạt động của cấp dưới và hàm mục tiêu

của bộ phận này phụ thuộc một phần vào các biến bị điều khiển bởi bộ phận khác,

hoạt động ở cấp cao hơn hay cấp thấp hơn.

Tối ưu hai cấp còn có thể được áp dụng trong công tác lập kế hoạch phát triển

kinh tế, xã hội cho một vùng lãnh thổ hay một quốc gia: cấp trên là nhà nước nắm

quyền điều khiển các biến chính sách như biểu thuế, tỉ giá, côta nhập khẩu,... nhằm

mục tiêu tạo ra nhiều việc làm, cực tiểu nguồn lực sử dụng,... Cấp dưới là các công

ty với mục tiêu tối đa hóa thu nhập ròng với các ràng buộc về kinh tế và quản lý của

cấp trên.

Cũng có thể áp dụng tối ưu hai cấp trong phân bổ nguồn lực (Resource Alloca-

tion) ở một hãng hay công ty có phân cấp quản lý. Cấp trên giữ vai trò của trung tâm

cung cấp nguồn lực (vốn, vật tư, lao động) nhằm đạt cực đại lợi nhuận của toàn công

ty. Cấp dưới là các nhà máy sản xuất sản phẩm ở các địa điểm khác nhau, quyết định

tỉ lệ, sản lượng sản xuất riêng nhằm tối đa hóa hiệu suất của đơn vị mình.

Cuối cùng, tối ưu hai cấp cũng được áp dụng trong thiết kế mạng hệ thống vận

tải và trong các thị trường năng lượng (Energy Markets).

• Cuối chương, chúng tôi giới thiệu một mô hình đơn giản về bài toán tối ưu hai

cấp trong thị trường điện năng.

26

Giả sử có n nhà máy cùng tham gia vào thị trường sản xuất điện năng, trong đó

có một nhà máy (đánh số 1) có sản lượng lớn nhất và giữ vai trò chủ đạo (chủ cái),

các nhà máy còn lại đánh số 2, 3, . . . , n. Gọi xi là sản lượng điện cần sản xuất của

nhà máy thứ i, i = 1, 2, . . . , n và fi(xi) là chi phí sản xuất của nhà máy i. Giá bán

điện p sẽ phụ thuộc vào tổng lượng điện do các nhà máy sản xuất ra. Nhà máy 1 công

bố mức sản lượng của mình trước và các nhà máy khác sẽ phản ứng lại đối với số

lượng này. Mỗi nhà máy đều mong muốn tối đa hóa lợi nhuận thu được (số tiền bán

điện sau khi trừ chi phí sản xuất). Khi đó, bài toán tối ưu hai cấp đặt ra là

i=1

(cid:33) (cid:41) (cid:40) (cid:32) n (cid:88) xi − f1(x1) x1p max x1

với điều kiện

xi

i=1

(cid:40) (cid:32) n (cid:33) (cid:41) (cid:88) , i = 2, . . . , n. xi ∈ arg max xip xi − fi(xi)

Tóm lại, chương này đã giới thiệu khái quát một số kiến thức cơ bản về bài toán

tối ưu hai cấp, một trong những lớp bài toán qui hoạch toán học đang thu hút sự quan

tâm của nhiều nhà nghiên cứu ở trong và ngoài nước. Phân tích nội dung, xuất xứ

của bài toán và các tính chất cần biết về bài toán, nhằm giúp việc học tập, nghiên

cứu bài toán tối ưu hai cấp được thuận lợi và dễ dàng hơn.

Đáng chú ý và được nghiên cứu nhiều hơn cả là các bài toán tối ưu hai cấp tuyến

tính một hay nhiều mục tiêu. Tuy nhiên, khả năng ứng dụng của tối ưu hai cấp hiện

còn bị hạn chế, do thiếu các thuật toán giải hiệu quả.

27

Chương 3

Tối ưu hai cấp tuyến tính và tối ưu đa mục tiêu

Chương này đề cập tới một mô hình bài toán tối ưu hai cấp tuyến tính, cùng với

bài toán tối ưu (một cấp) đa mục tiêu có liên quan và xét mối liên hệ giữa bài toán tối

ưu hai cấp tuyến tính với bài toán tối ưu trên tập nghiệm hữu hiệu (tập điểm Pareto).

Nội dung chương tham khảo chủ yếu từ các tài liệu [2], [7] và [9].

3.1 Nội dung vấn đề

Chương này xét mối quan hệ giữa hai bài toán qui hoạch toán học đặc biệt.

A. Bài toán thứ nhất cần xét là bài toán tối ưu hai cấp tuyến tính:

11x + cT

12y(cid:9) ,

(cid:8)cT (3.1) max x

trong đó y là nghiệm tối ưu của bài toán

21x + cT

22y : A1x + A2y ≤ b(cid:9) ,

max (cid:8)cT (3.2)

với x, c11, c21 ∈ Rn, y, c12, c22 ∈ Rp, b ∈ Rm, A1 ∈ Rm×n, A2 ∈ Rm×p, T là ký

hiệu chuyển vị véctơ hay ma trận.

Bài toán dạng (3.1) - (3.2) có thể nảy sinh khi có hai chủ thể được quyền ra quyết

định ở hai mức phân cấp khác nhau: cấp trên và cấp dưới, hai cấp có chung các

ràng buộc, nhưng với hai lợi ích (mục tiêu) khác nhau và có thể xung đột nhau. Quá

trình đề ra quyết định thực hiện theo thứ bậc. Cấp trên quản lý các biến x, được lựa

chọn quyết định trước, do đó hạn chế không gian quyết định của cấp dưới, được phân

28

quyền quản lý các biến y.

Bài toán thứ hai cần xét có liên quan tới bài toán tối ưu tuyến tính đa mục tiêu

V max {Cz : z ∈ P }, (3.3)

trong đó z ∈ RN , C ∈ Rk×n, P ⊆ RN là tập lồi đa diện. Ta nhắc lại rằng điểm ¯z ∈ RN là một nghiệm hữu hiệu của (3.3) khi ¯z ∈ P và không tồn tại z ∈ P sao

cho Cz ≥ C ¯z và Cx (cid:54)= C ¯z. Ký hiệu E(P ) là tập các nghiệm hữu hiệu của bài toán

(3.3).

B. Bài toán thứ hai cần xét là bài toán tối ưu trên tập nghiệm hữu hiệu:

max {dT x : x ∈ E(P )}, (3.4)

trong đó d ∈ RN . Bài toán (3.4) là mô hình toán học của bài toán tối ưu tuyến tính

trên tập nghiệm hữu hiệu (tập điểm Pareto) E(P ) của bài toán tối ưu tuyến tính đa

mục tiêu (3.3). Tối ưu tuyến tính trên tập điểm hữu hiệu có một số ứng dụng trong

tối ưu đa mục tiêu và là một chủ đề nghiên cứu quan trọng trong tối ưu toàn cục.

Đã có nhiều nỗ lực để thiết lập mối liên hệ giữa bài toán tối ưu hai cấp tuyến tính

(3.1) - (3.2) và bài toán tối ưu tuyến tính hai mục tiêu (3.3) với

 

C =   cT 11 cT 12 cT 21 cT 22

và P = {(x, y) : A1x + A2y ≤ b} là tập lồi đa diện (n + p) chiều.

Cùng với sự qua tâm về mặt lý thuyết, mối liên hệ như thế có thể hữu ích về mặt

tính toán, do có các thuật toán hiệu quả cho tối ưu hai mục tiêu. Tuy nhiên, người ta

đã chỉ ra rằng nói chung không có mối liên hệ nào giữa bài toán tối ưu hai cấp (3.1)

- (3.2) với bài toán tối ưu hai mục tiêu (3.3) đã mô tả. Hơn nữa, với hai véctơ cho

trước bất kỳ c12 và c22 không tỉ lệ với nhau, có thể xây dựng bài toán (3.1) - (3.2) sao

cho nghiệm tối ưu của (3.1) - (3.2) không là nghiệm hữu hiệu của bài toán hai mục

tiêu (3.3) xây dựng ở trên.

Tiếp theo, Mục 3.2 giới thiệu một kết quả nghiên cứu cho biết rằng có thể xây

dựng bài toán tối ưu tuyến tính đa mục tiêu sao cho tập nghiệm chấp nhận được của

29

(3.1) - (3.2) trùng với tập nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu đã xây

dựng. Bài toán tối ưu da mục tiêu này có r + 2 tiêu chuẩn mục tiêu, trong đó

r = rank A1. Như vậy bài toán (3.1) - (3.2) có thể diễn đạt như một bài toán (3.4).

Từ đó dẫn tới hệ quả đáng chú ý là bài toán tối ưu tuyến tính trên tập hữu hiệu là NP

- khó.

Cuối cùng, Mục 3.2 đề cập tới cách diễn đạt theo chiều hướng ngược lại: Với bất

kỳ bài toán (3.4), có thể xây dựng bài toán tối ưu hai cấp tuyến tính (3.1) - (3.2) sao

cho giá trị tối ưu của hai bài toán này là trùng nhau và tồn tại phép tương ứng đơn

giản giữa các nghiệm tối ưu của hai bài toán.

3.2 Quan hệ với tối ưu đa mục tiêu

Trở lại bài toán (3.1) - (3.2). Cặp (¯x, ¯y), trong đó ¯x ∈ Rn và ¯y ∈ Rp, là một

nghiệm chấp nhận được của (3.1) - (3.2) khi A1¯x + A2 ¯y ≤ b và ¯y là nghiệm tối ưu

của bài toán:

21¯x + cT

22y : A2y ≤ b − A1¯x},

max {cT (3.5)

21¯x chỉ là một hằng số trong hàm mục tiêu của (3.5),

trong đó ¯x đã được cố định. Vì cT

nên có thể loại bỏ số hạng này hoặc đơn giản là thay c21 bởi véctơ 0. Cặp (¯x, ¯y) là

một nghiệm tối ưu của (3.1) - (3.2) khi (¯x, ¯y)) là một nghiệm chấp nhận được của

11¯x + cT cT

12 ¯y ≥ cT

11x + cT

12y,

(3.1) - (3.2) và

với một nghiệm chấp nhận được bất kỳ (x, y) của (3.1) - (3.2).

Với bài toán (3.1) - (3.2) đã cho, ta xác định bài toán tối ưu đa mục tiêu (3.3) như

sau. Đặt N = n + p và A = [A1, A2] là ma trận cấp m × n và đặt

P = {z = (x, y) ∈ RN | Az ≤ b}, (3.6)

P là một tập lồi đa diện trong RN . Giả sử r = rank A1. Không giảm tổng quát, ta có

A1 =  , thể giả thiết rằng A1 được phân tách thành  ¯A1  ˆA1

30

trong đó ¯A1 là ma trận r × n và r = rank ¯A1. Giả sử k = r + 2 và ma trận mục tiêu

C cấp k × N được xác định bởi

  ¯A1

, (3.7) C =     O   −eT ¯A1 0T  2  cT 22 0T 1

trong đó O là ma trận không cấp r × p, 01 và 02 lần lượt là các véctơ không n và p chiều và e ∈ Rr với mọi phần tử bằng 1.

Mệnh đề 3.1. Cặp (¯x, ¯y) là một nghiệm chấp nhận được của (3.1) - (3.2) khi và chỉ

khi   ¯x ¯z =   ¯y

là một nghiệm hữu hiệu của (3.3) xác định bởi (3.6) và (3.7).

Chứng minh. Giả sử (¯x, ¯y) là một nghiệm chấp nhận được của (3.1) - (3.2) nhưng

¯z không là nghiệm hữu hiệu của (3.3). Khi đó tồn tại z ∈ P sao cho Cz ≥ C ¯z và Cz (cid:54)= C ¯z. Giả sử z được phân tách thành zT = [xT , yT ], trong đó x ∈ Rn và y ∈ Rp. Do ¯A1x ≥ ¯A1¯x và −eT ¯A1x ≥ −eT ¯A1¯x nên ta nhận được ¯A1x = ¯A1¯x và

A1x = A1¯x. Thêm vào đó, từ A1x + A2y ≤ b suy ra y là một nghiệm chấp nhận

22y > cT

22 ¯y. Bất đẳng thức này mâu

được của (3.5). Hơn nữa Cz (cid:54)= C ¯z kéo theo cT

thuẫn với ¯y là nghiệm tối ưu của (3.5) và (¯x, ¯y) là nghiệm chấp nhận được của (3.1)

- (3.2).

Ngược lại, giả sử ¯z là một nghiệm hữu hiệu của (3.3) nhưng (¯x, ¯y) không là

22 ¯y. Đăt véctơ ˜z xác định bởi

22 ˜y > cT

nghiệm chấp nhận được của (3.1) - (3.2). Tập ràng buộc của (3.5) là không rỗng, chẳng hạn ¯y là một nghiệm chấp nhận được. Tồn tại ˜y ∈ Rp sao cho ˜y là chấp nhận được của (3.5) và cT

  ¯x ˜z =   ˜y

Rõ ràng là ˜z ∈ P, C ˜z ≥ C ¯z và C ˜z (cid:54)= C ¯z. Điều này mâu thuẫn với ¯z là một

nghiệm hữu hiệu của (3.3).

31

Bổ đề 3.1. Cặp (¯x, ¯y) là một nghiệm tối ưu của (3.1) - (3.2) khi và chỉ khi

  ¯x ¯z =   ¯y

là một nghiệm tối ưu của (3.4) xác định bởi (3.6) và (3.7) và

  c11 d =   . c12

Mệnh đề 3.2. Bài toán (3.4) là NP - khó.

Chứng minh. Bài toán tối ưu hai cấp (3.1) - (3.2) là NP - khó. Như vừa thấy ở trên,

(3.1) - (3.2) có thể qui dẫn về bài toán (3.4) qua một phép biến đổi đa thức. Từ đó

trực tiếp suy ra mệnh đề cần chứng minh.

3.3 Quan hệ với tối ưu trên tập nghiệm hữu hiệu

Xét bài toán tối ưu tuyến tính đa mục tiêu (3.3), trong đó C là ma trận cấp k × N, P = {z = (x, y) ∈ RN | Az ≤ ¯b}, A là ma trận cấp ¯m × N, z ∈ RN và ¯b ∈ R ¯m. Mỗi z ∈ P được đặt tương ứng với một bài toán qui hoạch tuyến tính theo

biến w:

max {eT C(w − z) | Cw ≥ Cz, w ∈ P }, (3.8)

trong đó e là véctơ k chiều với mọi phần tử bằng 1. Có thể chỉ ra rằng z ∈ E(P ) khi

và chỉ khi giá trị tối ưu của (3.8) bằng 0. Hơn nữa, mỗi nghiệm tối ưu của (3.8) là

một nghiệm hữu hiệu, tức là thuộc E(P ), bất kể z có là nghiệm hữu hiệu hay không.

Xét bài toán tối ưu hai cấp tuyến tính (cấp trên chọn z, cấp dưới chọn w):

dT w. (3.9) max z

trong đó w là nghiệm tối ưu của bài toán

max {−eT Cz + eT Cw | Az ≤ ¯b, Aw ≤ ¯b, Cz − Cw ≤ 0}, (3.10)

32

   trong đó d ∈ RN . Nếu đặt n = p = N, m = 2 ¯m + k, x = z, y = w, c11 = 0, c12 = d, c21 = −eT C, c22 = eT C,   O A

, và b = , A2 = A1 = A O                      ¯b  ¯b    0 −C C

trong đó O là ma trận không cấp ¯m × N và 0 là véctơ không k chiều, thì bài toán tối

ưu hai cấp tuyến tính (3.9) - (3.10) có thể viết lại thành dạng (3.1) - (3.2).

Với bài toán đa mục tiêu (3.3) và bài toán hai cấp (3.9) - (3.10) vừa mô tả ta có

Mệnh đề 3.3. Với ¯z ∈ RN , các mệnh đề sau là tương đương:

(a) ¯z là một nghiệm hữu hiệu của (3.3).

(b) Cặp (¯z, ¯z) là một nghiệm chấp nhận được của (3.9) - (3.10).

(c) Tồn tại z ∈ RN sao cho cặp (z, ¯z) là một nghiệm chấp nhận được của (3.9) -

(3.10).

Chứng minh. (a) ⇒ (b): Do ¯z là một nghiệm hữu hiệu của (3.3) nên giá trị tối ưu

của bài toán (3.8) xác định bởi z = ¯z bằng 0 và w = ¯z là một nghiệm tối ưu. Do đó

nếu cấp trên chọn z = ¯z trong (3.9) - (3.10) thì w = ¯z là một nghiệm tối ưu của bài

toán cấp dưới (3.10). Do đó cặp (¯z, ¯z) là một nghiệm chấp nhận được của bài toán

(3.9) - (3.10).

(b) ⇒ (c): Hiển nhiên với z = ¯z.

(c) ⇒ (a): Do cặp (z, ¯z) là chấp nhận được của (3.9) - (3.10) nên w = ¯z là nghiệm

tối ưu của (3.10), khi cấp trên chọn z. Cũng vậy, w = ¯z là nghiệm tối ưu của bài toán

(3.8) xác định bởi z. Từ đó ¯z là một nghiệm hữu hiệu của (3.3).

Bổ đề 3.2. Bài toán (3.3) có nghiệm hữu hiệu khi và chỉ khi bài toán (3.9) - (3.10)

có nghiệm chấp nhận được. Bài toán (3.4) có giá trị tối ưu hữu hạn khi và chỉ khi bài

toán (3.9) - (3.10) có giá trị tối ưu hữu hạn và hai giá trị tối ưu là bằng nhau. Với ¯z ∈ RN , các mệnh đề sau là tương đương:

33

(a) ¯z là một nghiệm tối ưu của (3.4).

(b) Cặp (¯z, ¯z) là một nghiệm tối ưu của (3.9) - (3.10).

(c) Tồn tại z ∈ RN sao cho cặp (z, ¯z) là một nghiệm tối ưu của (3.9) - (3.10).

Tóm lại, chương này đã trình bày mối liên hệ giữa bài toán tối ưu hai cấp tuyến

tính và bài toán tối ưu tuyến tính trên tập nghiệm hữu hiệu. Có thể mô tả bài toán

này dưới dạng bài toán kia, và ngược lại, Từ đó suy ra hệ quả đáng chú ý là bài toán

tối ưu tuyến tính trên tập nghiệm hữu hiệu là NP - khó.

34

Kết luận

Luận văn đã giới thiệu về bài toán tối ưu hai cấp, các tính chất cần biết của bài

toán, đặc biệt lưu ý trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính

và một số hướng ứng dụng của tối ưu hai cấp trong thực tế, nhằm giúp việc học tập,

nghiên cứu bài toán tối ưu hai cấp được thuận lợi và dễ dàng hơn.

Luận văn đã trình bày các chủ đề cụ thể sau.

1. Một số kiến thức về tập lồi đa diện, khái niệm nghiệm hữu hiệu (điểm tối ưu

Pareto) của bài toán tối ưu đa mục tiêu và tính chất đặc trưng của tập nghiệm

hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu.

2. Nội dung, xuất xứ của bài toán tối ưu hai cấp, các tính chất cần biết của bài

toán, đặc biệt lưu ý tới trường hợp riêng quan trọng là bài toán tối ưu hai cấp

tuyến tính một mục tiêu và một số hướng ứng dụng của tối ưu hai cấp trong

thực tế.

3. Mối liên hệ giữa bài toán tối ưu hai cấp tuyến tính và bài toán tối ưu tuyến tính

trên tập nghiệm hữu hiệu. Có thể mô tả bài toán này dưới dạng bài toán kia, và

ngược lại, chú ý là bài toán tối ưu tuyến tính trên tập nghiệm hữu hiệu là NP -

khó.

Hy vọng trong tương lai tác giả sẽ có dịp tìm hiểu thêm những bài nghiên cứu

hoặc tổng quan sâu sắc hơn về bài toán tối ưu hai cấp, đặc biệt là các kỹ thuật xử lý

bài toán và các ứng dụng cụ thể của bài toán.

35

Tài liệu tham khảo

Tiếng Việt

[1] Trần Vũ Thiệu và Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến,

Nxb Đại học Quốc gia Hà Nội.

Tiếng Anh

[2] Ansari E., Zhiani Rezai H. (2011), "Solving Multi-objective Linear Bilevel

Multi-Follower Programming Problem", Int. J. Industrial Mathematics, Vol.

3, (No. 4), p. 303 - 316.

[3] Bard J. F. (1991), "Some properties of the bilevel programming problem",

Journal of Optimization Theory and Applications, 68, p. 371 - 378.

[4] Bard J. F. (1998), Practical Bilevel Optimization: Applications and Algorithms,

Kluwer Academic Press.

[5] Bracken J. and McGill J. (1973), "Mathematical Programs with Optimi-zation

Problems in the Constraints", Operations Research, (21), p. 37 - 44.

[6] Candler W. and Norton R. (1977), Multilevel Programming, Tech. Rep. 20,

World Bank Development Research Center,Washington D.C.

[7] Colson B., Marcotte P. and Savard G. (2005), "Bilevel Programming: A Servey.

A Quarterly Journal of Operations Research", Springer –Verlag, (3), p. 87 –

107.

36

[8] Fricke C., An Introduction to Bilevel Programming, Department of Mathe-

matics and Statistics, University of Melbourne. http://www.neevia.com

[9] Pieume C. O. et al. (2011), "Solving Bilevel Linear Multiojective Program-

ming Problem", American Journal of Operations Research, 1, p. 214 - 219.

[10] Stackelberg H. (1952), The Theory of the Market Economy, Oxford University

Press.

[11] F¨ul¨op J. (1993), "On the equivalence between a linear bilevel programming

problem and linear optimization over the efficient set", Technical report, Lab-

oratory of Operations Research and Decision Systems, Computer and Automa-

tion Institute, Hungarian Academy of Sciences, Budapest, working paper 93-1.