Cải tiến phương pháp đơn hình giải quy hoạch tuyến tính

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