Một thuật toán tìm nghiệm tối ưu của bài toán quy hoạch song tuyến tính

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

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

—————————————————

NGUYỄN THỊ HẢI NHƯ

MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU

CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH

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

Thái Nguyên - Năm 2017

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

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

—————————————————

NGUYỄN THỊ HẢI NHƯ

MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU

CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số: 60.46.01.12

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 - Năm 2017

i

Lời cảm ơn

Tôi xin bày tỏ lòng biết ơn tới GS.TS Trần Vũ Thiệu, người đã định hướng

chọn đề tài và tận tình hướng dẫn, cho tôi những nhận xét quý báu để tôi có

thể hoàn thành luận văn.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới phòng Sau Đại học, các thầy

cô giáo dạy cao học chuyên ngành Toán ứng dụng trường Đại học Khoa Học -

Đại học Thái Nguyên đã giúp đỡ và tạo điều kiện cho tôi trong suốt quá trình

học tập và nghiên cứu khoa học.

Nhân dịp này tôi cũng xin gửi lời cảm ơn chân thành tới gia đình, bạn bè

đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong suốt quá

trình học tập.

Thái Nguyên, tháng 6 năm 2017

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

Nguyễn Thị Hải Như

ii

Mục lục

Lời cảm ơn i

Mục lục i

Một số ký hiệu viết tắt 1

Mở đầu 1

1 Bài toán quy hoạch song tuyến tính 5

1.1 Đối ngẫu trong quy hoạch tuyến tính . . . . . . . . . . . . . . 5

1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính . . . . . . . . 8

1.2.1 Hàm lõm và tính chất . . . . . . . . . . . . . . . . . . . 8

1.2.2 Bài toán quy hoạch lõm . . . . . . . . . . . . . . . . . 10

1.3 Bài toán quy hoạch song tuyến tính . . . . . . . . . . . . . . . 11

1.3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . 12

1.3.2 Quan hệ với bài toán quy hoạch lõm . . . . . . . . . . . 13

1.3.3 Tính chất nghiệm của bài toán song tuyến tính . . . . . 15

1.4 Tìm nghiệm cực tiểu địa phương . . . . . . . . . . . . . . . . . 16

iii

2 Thuật toán giải quy hoạch song tuyến tính 19

2.1 Cơ sở lý thuyết của thuật toán . . . . . . . . . . . . . . . . . . 19

2.1.1 Biến đổi bài toán quy hoạch song tuyến tính . . . . . . 19

2.1.2 Điều kiện tối ưu của thuật toán . . . . . . . . . . . . . 23

2.2 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.1 Các bước của thuật toán . . . . . . . . . . . . . . . . . 25

2.2.2 Suy biến . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2.3 Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3 Cách tiếp cận siêu phẳng cắt . . . . . . . . . . . . . . . . . . . 34

2.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . 36

Tài liệu tham khảo 46