Quy hoạch tuyến tính suy rộng

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

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

Phạm Đình Phước

QUI HOẠCH TUYẾN TÍNH SUY RỘNG

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

Thái Nguyên - 2013

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

i

Mục lục

Mở đầu 1

1 Kiến thức cơ sở về qui hoạch tuyến tính 4

1.1 Bài toán qui hoạch tuyến tính và tính chất . . . . . . . 4

1.1.1 Nội dung bài toán . . . . . . . . . . . . . . . . . 4

1.1.2 Các tính chất . . . . . . . . . . . . . . . . . . . 6

1.2 Qui hoạch tuyến tính đối ngẫu . . . . . . . . . . . . . . 7

1.2.1 Cặp bài toán đối ngẫu . . . . . . . . . . . . . . 7

1.2.2 Các quan hệ đối ngẫu . . . . . . . . . . . . . . . 8

1.2.3 Ví dụ bài toán đối ngẫu . . . . . . . . . . . . . . 10

1.3 Phương pháp đơn hình . . . . . . . . . . . . . . . . . . 11

1.3.1 Cơ sở lý thuyết . . . . . . . . . . . . . . . . . . 11

1.3.2 Các bước thuật toán . . . . . . . . . . . . . . . . 12

1.3.3 Ví dụ về thuật toán đơn hình . . . . . . . . . . . 13

2 Qui hoạch tuyến tính suy rộng 15

2.1 Bài toán qui hoạch tuyến tính suy rộng . . . . . . . . . 15

2.1.1 Mô hình toán học . . . . . . . . . . . . . . . . . 15

2.1.2 Bài toán suy rộng tương đương . . . . . . . . . . 16

2.1.3 Ví dụ về bài toán qui hoạch tuyến tính suy rộng 20

2.1.4 Trường hợp riêng . . . . . . . . . . . . . . . . . 21

2.2 Phương pháp Wolfe . . . . . . . . . . . . . . . . . . . . 23

2.2.1 Cơ sơ phương pháp giải . . . . . . . . . . . . . . 24

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

ii

2.2.2 Ví dụ minh họa phương pháp Wolfe . . . . . . . 29

2.2.3 Trường hợp Dj không bị chặn . . . . . . . . . . 33

2.2.4 Sự hội tụ hữu hạn . . . . . . . . . . . . . . . . 38

Kết luận 40

Tài liệu tham khảo 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

iii

Lời cảm ơn

Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn

và giúp đỡ của GS.TS Trần Vũ Thiệu (Viện Toán học Việt Nam). Tôi

xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy.

Tôi xin cảm ơn quý thầy, cô giảng dạy lớp cao học khóa 5 (2011 -

2013) đã mang đến cho tôi nhiều kiến thức bổ ích trong khoa học và

cuộc sống.

Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những

thiếu sót. Tác giả mong nhận được những ý kiến đóng góp của quý thầy,

cô và bạn đọc để luận văn được hoàn thiện hơn.

Xin trân trọng cảm ơn!

Hải Phòng, tháng 01 năm 2013.

Người viết Luận văn

Phạm Đình Phước

4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn