Phương pháp giải một lớp bài toán quy hoạch nguyên phi tuyến

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

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

NGUYỄN DUY LONG

PHƯƠNG PHÁP GIẢI MỘT LỚP

BÀI TOÁN QUY HOẠCH

NGUYÊN PHI TUYẾN

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

Thái Nguyên - Năm 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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

NGUYỄN DUY LONG

PHƯƠNG PHÁP GIẢI MỘT LỚP

BÀI TOÁN QUY HOẠCH

NGUYÊN PHI TUYẾN

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số : 60.46.36

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 - Năm 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

Mục lục

Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i

LỜI NÓI ĐẦU 1

Nội dung 4

1 MỘT SỐ KIẾN THỨC CHUẨN BỊ 4

1.1 Tập lồi, hàm lồi và một số tính chất . . . . . . . . . . . . . 4

1.1.1 Tập hợp lồi. . . . . . . . . . . . . . . . . . . . . . . 4

1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Thuật toán đa thức . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Bài toán quy hoạch nguyên phi tuyến . . . . . . . . . . . . 10

2 PHƯƠNG PHÁP TRỰC TIẾP GIẢI BÀI TOÁN (P) 13

2.1 Tính chất nghiệm của bài toán(P). . . . . . . . . . . . . . 13

2.2 Cơ sở phương pháp giải . . . . . . . . . . . . . . . . . . . 16

2.3 Thuật toán đa thức giải bài toán . . . . . . . . . . . . . . . 21

2.3.1 Thuật toán A. . . . . . . . . . . . . . . . . . . . . 21

2.3.2 Đánh giá độ phức tạp của thuật toán. . . . . . . . . 22

3 MỘT SỐ HƯỚNG MỞ RỘNG BÀI TOÁN (P) 28

3.1 Giảm kích thước bài toán (P) . . . . . . . . . . . . . . . . . 28

3.2 Thay đổi ràng buộc . . . . . . . . . . . . . . . . . . . . . . 33

3.2.1 Thêm, bớt sinh viên. . . . . . . . . . . . . . . . . . 33

3.2.2 Thêm, bớt chuyên đề. . . . . . . . . . . . . . . . . 34

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

3.2.3 Thêm điều kiện phụ vào bài toán (P) . . . . . . . . 35

3.3 Thay đổi hàm mục tiêu của bài toán (P) . . . . . . . . . . . 37

3.3.1 Bài toán với hàm mục tiêu mở rộng . . . . . . . . . 37

3.3.2 Bài toán với hàm mục tiêu lõm . . . . . . . . . . . . 40

3.3.3 Bài toán vận tải với điều kiện phụ. . . . . . . . . . . 42

KẾT LUẬN 44

Tài liệu tham khảo 45

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn