Thuật toán phân rã giải bài toán phân bố sản xuất với chi phí lõm

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

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

PHẠM TIẾN ĐỘ

THUẬT TOÁN PHÂN RÃ GIẢI BÀI TOÁN PHÂN

BỐ SẢN XUẤT VỚI CHI PHÍ LÕM

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

Thái Nguyên - 12/2015

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

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

PHẠM TIẾN ĐỘ

THUẬT TOÁN PHÂN RÃ GIẢI BÀI TOÁN PHÂN

BỐ SẢN XUẤT VỚI CHI PHÍ LÕM

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

Mã số: 60 46 01 12

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 - 12/2015

1

Mục lục

Mở đầu 2

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 XÁC ĐỊNH CÁC ĐỈNH CỦA ĐA DIỆN LỒI . . . . . . . . . . . . 6

1.3 HÀM LỒI, HÀM LÕM VÀ HÀM TỰA LÕM . . . . . . . . . . . . 12

2 QUI HOẠCH LÕM VỚI RÀNG BUỘC TUYẾN TÍNH 16

2.1 CỰC ĐẠI HÀM LỒI, CỰC TIỂU HÀM LÕM . . . . . . . . . . . . 16

2.2 BÀI TOÁN QUI HOẠCH LÕM . . . . . . . . . . . . . . . . . . . 19

2.3 THUẬT TOÁN XẤP XỈ NGOÀI GIẢI QUI HOẠCH LÕM . . . . . 21

2.3.1 Ý tưởng phương pháp . . . . . . . . . . . . . . . . . . . . . 21

2.3.2 Trường hợp ràng buộc tuyến tính . . . . . . . . . . . . . . . 22

2.4 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 BÀI TOÁN PHÂN BỐ SẢN XUẤT VỚI CHI PHÍ LÕM 28

3.1 NỘI DUNG VÀ Ý NGHĨA BÀI TOÁN . . . . . . . . . . . . . . . 28

3.2 Ý TƯỞNG PHÂN RÃ BÀI TOÁN . . . . . . . . . . . . . . . . . . 29

3.3 THUẬT TOÁN PHÂN RÃ . . . . . . . . . . . . . . . . . . . . . . 30

3.4 VÍ DỤ MINH HỌA THUẬT TOÁN . . . . . . . . . . . . . . . . . 34

Kết luận 39

Tài liệu tham khảo 40

2

MỞ ĐẦU

Bài toán cực tiểu hàm lõm trên một tập lồi đóng gọi là bài toán qui hoạch lõm

(Concave Programming Problem). Đây là một bài toán cơ bản của tối ưu toàn cục,

vì tính phổ biến của nó và vì nhiều bài toán tối ưu toàn cục quy về nó hoặc dựa ít

nhiều trên phép giải của nó. Đơn giản hơn cả và được nghiên cứu nhiều là bài toán

qui hoạch lõm với ràng buộc tuyến tính, hiện còn ít đề tài cao học đề cập tới.

Sách tham khảo [2], [5] nêu nhiều kết quả lý thuyết và phương pháp giải lớp bài

toán này. Các tài liệu tham khảo [3], [4] chủ yếu đề cập tới bài toán qui hoạch lõm

với các ràng buộc tuyến tính và mô hình bài toán phân bố sản xuất thường gặp.

Sau khi được học các chuyên đề về giải tích lồi, tối ưu hóa và các kiến thức có

liên quan, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học và các ứng

dụng của những kiến thức này, tôi chọn đề tài luận văn:

"Thuật toán phân rã giải bài toán phân bố sản xuất với chi phí lõm".

Mục đích chính của luận văn là tìm hiểu về bài toán qui hoạch lõm, chủ yếu là

bài toán với ràng buộc tuyến tính và thuật toán xấp xỉ ngoài giải bài toán. Đặc biệt

chú ý tới thuật toán phân rã giải mô hình bài toán phân bố sản xuất với chi phí lõm.

Luận văn được viết dựa trên các tài liệu tham khảo [1]- [5].

Các kết quả cần đạt được: hiểu và trình bày được một số nội dung chính sau:

a) Hàm lõm và bài toán cực tiểu hàm lõm trên tập lồi đa diện.

b Thuật toán xấp xỉ ngoài giải bài toán qui hoạch lõm ràng buộc tuyến tính.

c) Bài toán phân bố sản xuất với chi phí lõm và thuật toán phân rã giải bài toán, dựa

trên kỹ thuật xấp xỉ ngoài.