Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Cải tiến phương pháp đơn hình giải quy hoạch tuyến tính
Nội dung xem thử
Mô tả chi tiết
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 THỊ HUỆ
CẢI TIẾN PHƯƠNG PHÁP ĐƠN HÌNH
GIẢI QUY HOẠCH TUYẾN TÍNH
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 – 2011
NGUYỄN THỊ HUỆ
Đề tài: CẢI TIẾN THUẬT TOÁN ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH
Soạn thảo văn bản LATEX bởi công cụ MikTeX & TeXmaker
Thái Nguyên, ngày 10 tháng 10 năm 2011
1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Mục lục
1 KIẾN THỨC CHUẨN BỊ 6
1.1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH
CHẤT . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Nội dung bài toán . . . . . . . . . . . . . . . 6
1.1.2 Một số tính chất . . . . . . . . . . . . . . . . 8
1.2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 11
1.2.1 Dạng bài toán đối ngẫu . . . . . . . . . . . . 11
1.2.2 Định lí đối ngẫu . . . . . . . . . . . . . . . . 12
1.3 PHƯƠNG PHÁP ĐƠN HÌNH . . . . . . . . . . . . . . 13
1.3.1 Thuật toán đơn hình gốc . . . . . . . . . . . 14
1.3.2 Thuật toán đơn hình đối ngẫu . . . . . . . 17
2 PHƯƠNG PHÁP ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI
BIÊN 22
2.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 22
2.1.1 Nội dung bài toán và các kí hiệu . . . . . . 22
2.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . 23
2.2 THUẬT TOÁN ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI
BIÊN (RPDSA) . . . . . . . . . . . . . . . . . . . . . . 25
2.3 PHƯƠNG PHÁP M - LỚN ( BIG M - METHOD) . . 27
2.3.1 Tìm cơ sở đối ngẫu chấp nhận được B và
phân hoạch ( B, N ) ban đầu. . . . . . . . . 27
2.3.2 Tìm điểm gốc chấp nhận được y ban đầu 27
2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1
2.3.3 Phương pháp M - lớn ( Big - M Method . 28
2.3.4 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . 30
3 HAI PHƯƠNG PHÁP CẢI TIẾN KHÁC 33
3.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 33
3.1.1 Nội dung bài toán và các kí hiệu . . . . . . 33
3.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . . 34
3.2 PHƯƠNG PHÁP GÓC NGHIÊNG NHỎ NHẤT . . . . 37
3.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . 37
3.2.2 Ví dụ 3.1 . . . . . . . . . . . . . . . . . . . . . 39
3.3 PHƯƠNG PHÁP CÔSIN ĐƠN HÌNH . . . . . . . . . 41
3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2