Cực đại hàm tuyến tính trên tập hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

—————o0o—————

LÊ NHƯ QUỲNH

CỰC ĐẠI HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU

CỦA BÀI TOÁN TỐI ƯU TUYẾN TÍNH ĐA MỤC TIÊU

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2017

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

—————o0o—————

LÊ NHƯ QUỲNH

CỰC ĐẠI HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU

CỦA BÀI TOÁN TỐI ƯU TUYẾN TÍNH ĐA MỤC TIÊU

LUẬN VĂN THẠC SĨ TOÁN HỌC

Chuyên ngành: Toán ứng dụng

Mã số: 60 46 01 12

NGƯỜI HƯỚNG DẪN KHOA HỌC

GS.TS. TRẦN VŨ THIỆU

Thái Nguyên - 2017

i

Mục lục

Danh mục các ký hiệu i

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

Mở đầu 1

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

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

1.2 Bài toán quy hoạch song tuyến tính . . . . . . . . . . . . . . . . . 7

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

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

Chương 2. Thuật toán giải bài toán cực đại hàm tuyến tính trên tập điểm

hữu hiệu 25

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

2.2 Cơ sở lý thuyết của thuật toán . . . . . . . . . . . . . . . . . . . 27

2.3 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . 30

2.4 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Kết luận 40

Tài liệu tham khảo 42

Một số thuật ngữ thường sử dụng 44

i

Danh mục các ký hiệu

R

n Không gian Euclide n-chiều

R

n

+ Góc không âm trong R

n

R

n

++ Góc dương trong R

n

e Véc tơ với mọi thành phần bằng 1 (e = (1,...,1) ∈ R

p

)

x ≤ y Véctơ x nhỏ hơn hay bằng véctơ y (xi ≤ yi

,∀i = 1,...,n)

x ≥ y Véctơ x lớn hơn hay bằng véctơ y (xi ≥ yi

,∀i = 1,...,n)

x ∈ X là một phần tử của tập X

x ∈/ X x không là phần tử của tập X

∅ Tập hợp rỗng (tập không có phần tử nào)

D Ký hiệu tập lồi đa diện

F Ký hiệu diện của tập lồi đa diện

A∪B Hợp của hai tập A và B

A∩B Giao của hai tập A và B

A ⊂ B A là tập hợp con của B

A ⊆ B A là tập hợp con (có thể bằng) của B

conv S Bao lồi của tập S ⊂ R

n

dimS Thứ nguyên (hay số chiều) của tập S ⊂ R

n

∃x Tồn tại x

∀x Với mọi x

(P) Ký hiệu bài toán tối ưu tuyến tính đa mục tiêu

(Q) Ký hiệu bài toán cực đại hàm tuyến tính trên tập E

P

ii

(BP) Ký hiệu bài toán quy hoạch song tuyến tính

E

P Tập các điểm hữu hiệu của bài toán (P)

E

P

d

Tập các diện hữu hiệu của bài toán (P)