Thuật toán giải một số bài toán tối ưu phân thức tuyến tính và phi tuyến

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

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

-------------------------------

LÊ ĐÌNH THẢN

THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU

PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN

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

THÁI NGUYÊN - 2018

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

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

-------------------------------

LÊ ĐÌNH THẢN

THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU

PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN

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

Mã số : 8460112

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

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

GS.TS. Trần Vũ Thiệu

THÁI NGUYÊN - 2018

iii

Mục lục

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

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

Mở đầu 4

1 KIẾN THỨC CHUẨN BỊ 7

1.1. HÀM PHÂN THỨC AFIN . . . . . . . . . . . . . . . . . . 7

1.2. BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH . . . . . 9

1.3. CÁCH TIẾP CẬN CHARNES - COOPER . . . . . . . . . 11

1.4. PHƯƠNG PHÁP GIẢI CỔ ĐIỂN . . . . . . . . . . . . . . 14

2 THUẬT TOÁN CẢI TIẾN GIẢI QUY HOẠCH PHÂN

TUYẾN TÍNH 18

2.1. PHƯƠNG PHÁP ĐƯA VỀ MỘT BÀI TOÁN (LP) . . . . 18

2.1.1. Biến đổi (LFP) về bài toán tuyến tính (LP) . . . . 18

2.1.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . 20

2.1.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 20

2.2. PHƯƠNG PHÁP ĐƯA VỀ HAI BÀI TOÁN (LP) . . . . . 25

2.2.1. Cơ sở của phương pháp . . . . . . . . . . . . . . . . 26

2.2.2. Phương pháp hạn chế hàm mục tiêu ở mẫu số . . . 27

2.2.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 28

2.2.4. Bài toán cực tiểu . . . . . . . . . . . . . . . . . . . 29

3 TIẾP CẬN THAM SỐ GIẢI QUY HOẠCH PHÂN THỨC

PHI TUYẾN 32

iv

3.1. THUẬT TOÁN DINKELBACH . . . . . . . . . . . . . . . 32

3.1.1. Ký hiệu và kết quả chuẩn bị . . . . . . . . . . . . . 32

3.1.2. Sự hội tụ toàn cục của thuật toán . . . . . . . . . . 34

3.2. THUẬT TOÁN DINKELBACH RÚT GỌN . . . . . . . . 36

3.3. ÁP DỤNG GIẢI QUY HOẠCH PHÂN TUYẾN TÍNH . . 39

Kết luận 44

Tài liệu tham khảo 45