Bài toán quy hoạch phân tuyến tính

Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/

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

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

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

NGUYỄN VĂN HÙNG

BÀI TOÁN QUI HOẠCH PHÂN TUYẾN TÍNH

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

Thái Nguyên - 2013

Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/

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

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

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

NGUYỄN VĂN HÙNG

BÀI TOÁN QUI HOẠCH PHÂN TUYẾN TÍNH

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 - 2013

Mục lục

Mở đầu 3

1 Kiến thức chuẩn bị 5

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

1.2 Hàm lồi, hàm lõm và mở rộng . . . . . . . . . . . . . . . . . 8

1.3 Cực tiểu địa phương và toàn cục . . . . . . . . . . . . . . . . 11

2 Bài toán qui hoạch phân tuyến tính 15

2.1 Bài toán và tính chất . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Dạng chính tắc và dạng tổng quát . . . . . . . . . . . . . . . 18

2.3 Liên hệ với quy hoạch tuyến tính . . . . . . . . . . . . . . . . 20

2.4 Bài toán hai biến số . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.1 Lời giải tối ưu duy nhất . . . . . . . . . . . . . . . . . 21

2.4.2 Nhiều lời giải tối ưu . . . . . . . . . . . . . . . . . . . 23

2.4.3 Lời giải tối ưu hữu hạn và vô cực . . . . . . . . . . . . 23

2.4.4 Lời giải tối ưu tiệm cận . . . . . . . . . . . . . . . . . 24

3 Phương pháp giải qui hoạch phân tuyến tính 27

3.1 Biến đổi Charnes và Cooper . . . . . . . . . . . . . . . . . . 27

3.2 Thuật toán Gilmore và Gomory . . . . . . . . . . . . . . . . 31

3.3 Thuật toán Dinkelbach . . . . . . . . . . . . . . . . . . . . . 34

3.4 Thuật toán Béla Martos . . . . . . . . . . . . . . . . . . . . 38

3.4.1 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . 38

3.4.2 Các bước thuật toán . . . . . . . . . . . . . . . . . . . 39

Kết luận 44

Tài liệu tham khảo 45

1

Soá hoùa bôûi trung taâm hoïc lieäu http://lrc.tnu.edu.vn/

LỜI CẢM ƠN

Luận văn này đượ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ự hướng dẫn tận tình của Giáo sư Tiến sĩ Trần Vũ Thiệu. Tác

giả xin bày tỏ lòng biết ơn chân thành và sâu sắc về sự tận tâm và nhiệt tình

của Thầy trong suốt quá trình tác giả thực hiện luận văn.

Trong quá trình học tập và làm luận văn, từ bài giảng của các Giáo sư,

Phó Giáo sư công tác tại 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 Việt Nam, các Thầy, cô trong Đại học Thái Nguyên,

tác giả đã trau dồi thêm rất nhiều kiến thức phục vụ cho việc nghiên cứu và

công tác của bản thân. Từ đáy lòng mình, tác giả xin bày tỏ lòng cảm ơn sâu

sắc tới các Thầy cô.

Tác giả xin chân thành cám ơn Ban Giám hiệu, phòng Đào tạo Khoa học

và Quan hệ quốc tế, 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ả trong suốt thời gian học tập tại

trường.

Tác giả xin chân thành cảm ơn Sở Giáo dục và Đào tạo tỉnh Hòa Bình, Ban

giám hiệu, các tổ chức Đoàn thể, tổ chuyên môn, nhóm toán trường THPT

Lạc Thủy B cùng bạn bè đồng nghiệp và gia đình đã tạo mọi điều kiện giúp

đỡ, động viên tác giả hoàn thành luận văn này.

Tác giả

Nguyễn Văn Hùng

2

Soá hoùa bôûi trung taâm hoïc lieäu http://lrc.tnu.edu.vn/