Luận văn nhằm tìm hiểu và trình bày một số thuật toán mới gần đây, nêu ở các tài liệu tham khảo, giải quy hoạch phân tuyến tính (nhờ đưa về quy hoạch tuyến tính) và giải quy hoạch phân thức phi tuyến (theo tiếp cận tham số). Mời các bạn tham khảo! | ĐẠ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 . 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 . HÀM PHÂN THỨC AFIN . . . . . . . . . . . . . . . . . . 7 . BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH . . . . . 9 . CÁCH TIẾP CẬN CHARNES - COOPER . . . . . . . . . 11 . 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 . PHƯƠNG PHÁP ĐƯA VỀ MỘT BÀI TOÁN LP . . . . 18 . Biến đổi LFP về bài toán tuyến tính LP . . . . 18 . Thuật toán . . . . . . . . . . . . . . . . . . . . . . 20 . Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 20 . PHƯƠNG PHÁP ĐƯA VỀ HAI BÀI TOÁN LP . . . . . 25 . Cơ sở của phương pháp . . . . . . . . . . . . . . . . 26 . Phương pháp hạn chế hàm mục tiêu ở mẫu số . . . 27 . Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 28 . 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 . THUẬT TOÁN DINKELBACH . . . . . . . . . . . . . . . 32 . Ký hiệu và kết quả chuẩn bị . . . . . . . . . . . . . 32 . Sự hội tụ toàn cục của thuật toán . . . . . . . . . . 34 . THUẬT TOÁN DINKELBACH RÚT GỌN . . . . . . . . 36 . Á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 1 DANH MỤC CÁC KÝ HIỆU R Tập các số thực Rn Không gian véctơ n chiều Rn Tập các véctơ không âm trong Rn T Ký hiệu chuyển vị véctơ hay ma trận kxk Chuẩn Euclid của véctơ x Rn x Giá trị tuyệt đối của x R xk xk Dãy điểm trong Rn hx yi Tích vô .
