ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
NGUYỄN THU HẰNG
THUẬT TOÁN GIẢI BÀI TOÁN
PHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ
KHOẢNG Ở HÀM MỤC TIÊU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
NGUYỄN THU HẰNG
THUẬT TOÁN GIẢI BÀI TOÁN
PHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ
KHOẢNG Ở HÀM 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 - 2016
i
Mục lục
Danh mục các hình vẽ ii
Mở đầu 1
1 Một số kiến thức chuẩn bị 4
1.1. Bài toán qui hoạch phân tuyến tính . . . . . . . . . . . . . . . . 4
1.2. Tính chất nghiệm của bài toán . . . . . . . . . . . . . . . . . . 8
1.3. Minh họa hình học . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1. Nghiệm tối ưu duy nhất . . . . . . . . . . . . . . . . . 10
1.3.2. Nhiều nghiệm tối ưu . . . . . . . . . . . . . . . . . . . 11
1.3.3. Nghiệm tối ưu hữu hạn và vô cực . . . . . . . . . . . . 12
1.3.4. Nghiệm tối ưu tiệm cận . . . . . . . . . . . . . . . . . . 13
1.3.5. Bài toán vô nghiệm . . . . . . . . . . . . . . . . . . . . 13
1.4. Biến đổi về bài toán tuyến tính tương đương . . . . . . . . . . . 14
2 Qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu 18
2.1. Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2. Thuật toán đưa về qui hoạch tuyến tính . . . . . . . . . . . . . . 21
2.3. Thuật toán dùng phép tính khoảng . . . . . . . . . . . . . . . . 25
2.3.1. Phép tính khoảng . . . . . . . . . . . . . . . . . . . . . 25
2.3.2. Qui hoạch phân tuyến tính khoảng . . . . . . . . . . . . 28
2.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Kết luận 38
i
Tài liệu tham khảo 39
ii
Danh mục các hình vẽ
Hình 1.1. Phân bổ công suất phát sóng tối ưu
Hình 1.2. Năm tập mức trong R2với
γ
1>0>
γ
2>
γ
3>
γ
4.
Hình 1.3. Nghiệm tối ưu duy nhất đạt tại x∗
Hình 1.4. Nhiều nghiệm tối ưu: xopt ∈[x∗,x∗∗]
Hình 1.5. Nghiệm tối ưu hữu hạn và vô cực
Hình 1.6. Nghiệm tối ưu tiệm cận ( f∗hữu hạn, không đạt được)
Hình 1.7. Bài toán vô nghiệm (f(x)ց −∞)
Hình 1.8. Tập ràng buộc của bài toán ở Ví dụ 1.1
Hình 2.1. Tập ràng buộc Xcủa bài toán ở Ví dụ 2.1
Hình 2.2. Tập ràng buộc Xcủa bài toán ở Ví dụ 2.2
Hình 2.3. Tập ràng buộc Xcủa bài toán ở Ví dụ 2.4
