1
UBND TỈNH QUẢNG NAM
TRƢỜNG ĐẠI HỌC QUẢNG NAM
KHOA: TOÁN
----------
PHAN THỊ BÍCH THẢO
MỘT SỐ VẤN ĐỀ HẬU TỐI ƢU
CỦA THUẬT TOÁN ĐƠN HÌNH
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Quảng Nam, tháng 4 năm 2017
2
Phần 1. MỞ ĐẦU
1.1. Lý do chọn đề tài
Quy hoạch tuyến tính (QHTT) là một bộ phận quan trọng của toán học ứng
dụng, có nhiều ứng dụng trong nhiều lĩnh vực đặc biệt là kinh tế và công nghệ
thông tin. Quy hoạch tuyến tính nghiên cứu các bài toán tối ưu với hữu hạn biến,
trong đó mục tiêu và các điều kiện ràng buộc được biểu thị bằng các hàm số, các
phương trình hay bất phương trình tuyến tính. Khi thực hiện công việc nào đó
của mình, con người luôn hướng đến cách làm tốt nhất trong các cách có thể làm
được hay là chọn phương án tối ưu trong các phương án. Cùng với sự phát triển
của khoa học máy tính ngày nay thì QHTT ngày càng phát triển và cần thiết.
Những vấn đề tối ưu trong cuộc sống đều được mô hình hóa thành các bài toán
tối ưu, biểu thị các mục tiêu cần đạt được các yêu cầu hay các điều kiện thỏa mãn
bằng ngôn ngữ toán học thông qua các bài toán QHTT để tìm ra lời giải tối ưu
cho nó.
Hiện nay, học phần QHTT được giảng dạy cho ngành ĐHSP Toán với thời
lượng 2 tín chỉ nên chỉ đề cập đến những nội dung cơ bản mà chưa đi sâu nghiên
cứu các nội dung liên quan, đặc biệt là thuật toán đơn hình. Vì vậy, với tinh thần
mong muốn được học hỏi, tìm hiểu và trao dồi vốn kiến thức một cách sâu sắc
hơn kết hợp với kiến thức tích lũy trong quá trình học tập, nên tôi chọn đề tài
“Một số vấn đề hậu tối ưu của thuật toán đơn hình” cho khóa luận này.
1.2. Mục tiêu của đề tài
- Tìm hiểu về tính hữu hạn của thuật toán đơn hình.
- Tìm tập phương án tối ưu của bài toán quy hoạch tuyến tính.
- Tìm tập phương án tối ưu của bài toán khi bổ sung thêm ràng buộc
)(xf
- Giải bài toán quy hoạch tuyến tính bằng thuật toán đơn hình theo phương
án cực biên cho trước.
1.3. Đối tƣợng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: vấn đề hậu tối ưu của thuật toán đơn hình.
- Phạm vi nghiên cứu: kiến thức quy hoạch tuyến tính ở bậc đại học.
UBND TỈNH QUẢNG NAM
TRƢỜNG ĐẠI HỌC QUẢNG NAM
KHOA TOÁN
----------
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Tên đề tài:
MỘT SỐ VẤN ĐỀ HẬU TỐI ƢU
CỦA THUẬT TOÁN ĐƠN HÌNH
Sinh viên thực hiện
PHAN THỊ BÍCH THẢO
MSSV: 21130101350
CHUYÊN NGÀNH: SƢ PHẠM TOÁN
KHÓA: 2013 – 2017
Cán bộ hướng dẫn
ThS. PHẠM NGỌC HOÀNG
MSCB: ………….
Quảng Nam, tháng 4 năm 2017
3
Phần 1. MỞ ĐẦU
1.1. Lý do chọn đề tài
Quy hoạch tuyến tính (QHTT) là một bộ phận quan trọng của toán học ứng
dụng, có nhiều ứng dụng trong nhiều lĩnh vực đặc biệt là kinh tế và công nghệ
thông tin. Quy hoạch tuyến tính nghiên cứu các bài toán tối ưu với hữu hạn biến,
trong đó mục tiêu và các điều kiện ràng buộc được biểu thị bằng các hàm số, các
phương trình hay bất phương trình tuyến tính. Khi thực hiện công việc nào đó
của mình, con người luôn hướng đến cách làm tốt nhất trong các cách có thể làm
được hay là chọn phương án tối ưu trong các phương án. Cùng với sự phát triển
của khoa học máy tính ngày nay thì QHTT ngày càng phát triển và cần thiết.
Những vấn đề tối ưu trong cuộc sống đều được mô hình hóa thành các bài toán
tối ưu, biểu thị các mục tiêu cần đạt được các yêu cầu hay các điều kiện thỏa mãn
bằng ngôn ngữ toán học thông qua các bài toán QHTT để tìm ra lời giải tối ưu
cho nó.
Hiện nay, học phần QHTT được giảng dạy cho ngành ĐHSP Toán với thời
lượng 2 tín chỉ nên chỉ đề cập đến những nội dung cơ bản mà chưa đi sâu nghiên
cứu các nội dung liên quan, đặc biệt là thuật toán đơn hình. Vì vậy, với tinh thần
mong muốn được học hỏi, tìm hiểu và trao dồi vốn kiến thức một cách sâu sắc
hơn kết hợp với kiến thức tích lũy trong quá trình học tập, nên tôi chọn đề tài
“Một số vấn đề hậu tối ưu của thuật toán đơn hình” cho khóa luận này.
1.2. Mục tiêu của đề tài
- Tìm hiểu về tính hữu hạn của thuật toán đơn hình.
- Tìm tập phương án tối ưu của bài toán quy hoạch tuyến tính.
- Tìm tập phương án tối ưu của bài toán khi bổ sung thêm ràng buộc
)(xf
- Giải bài toán quy hoạch tuyến tính bằng thuật toán đơn hình theo phương
án cực biên cho trước.
1.3. Đối tƣợng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: vấn đề hậu tối ưu của thuật toán đơn hình.
- Phạm vi nghiên cứu: kiến thức quy hoạch tuyến tính ở bậc đại học.
4
1.4. Phƣơng pháp nghiên cứu
- Phân tích tổng hợp lí thuyết.
- Phương pháp nghiên cứu lí luận.
- Tham khảo ý kiến của thầy hướng dẫn.
1.5. Lịch sử nghiên cứu
Đã có những công trình nghiên cứu liên quan đến một số vấn đề hậu tối ưu
của thuật toán đơn hình của các tác giả như: Phí Mạnh Ban, Trần Vũ Thiệu,
Nguyễn Đức Nghĩa…
1.6. Đóng góp của đề tài
- Trình bày chi tiết các định nghĩa của từng vấn đề.
- Đưa ra các ví dụ cụ thể.
- Trình bày định lí và chứng minh định lí.
- Nêu một số mệnh đề và các nhận xét liên quan.
1.7. Cấu trúc đề tài
Bài khóa luận được chia làm 2 chương:
Chương 1: Thuật toán đơn hình giải bài toán quy hoạch tuyến tính.
Chương 2: Một số vấn đề hậu tối ưu của thuật toán đơn hình.
5
Phần 2. NỘI DUNG NGHIÊN CỨU
Chƣơng 1: THUẬT TOÁN ĐƠN HÌNH GIẢI BÀI TOÁN
QUI HOẠCH TUYẾN TÍNH
1.1. Bài toán QHTT
Bài toán QHTT dạng tổng quát với n ẩn là bài toán có dạng
max(min))( 1 jj
n
jxcxf
(1)
mibxc ijj
n
j,...,2,1,
1
(2)
0, 1,2,...,
j
x j n
(3)
trong đó:
(1) là hàm mục tiêu.
(2) là hệ ràng buộc chính.
(3) là ràng buộc dấu.
Đặt
nmij
aA
)(
,
),...,,( 21 n
cccc
,
,
1
2
m
b
b
b
b






Khi đó bài toán trở thành
max)( cxxf
Ax b




0x
- Mỗi vectơ
),...,,( 21 n
xxxx
thỏa (2) và (3) được gọi là một phương án của
bài toán.
- Mỗi phương án
x
thỏa (1), tại đó hàm mục tiêu đạt giá trị nhỏ nhất (lớn
nhất) trên tập phương án được gọi là phương án tối ưu của bài toán.
- Giải một bài toán QHTT là đi tìm một phương án tối ưu của nó hoặc chỉ ra
rằng bài toán vô nghiệm hay không có phương án tối ưu.