Thạc Sĩ Một phương pháp xấp xỉ trong giải bài toán quy hoạch nguyên phân tuyến tính theo phương pháp nhánh c

i
Mục lục
Lời cam đoan iii
Mở đầu 1
1 Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất
phương trình tuyến tính và thuật toán giải 3
1.1 Một số bài toán thực tế đưa về bài toán quy hoạch phân tuyến
tính và quy hoạch nguyên phân tuyến tính 3
1.1.1 Bài toán vận tải phân tuyến tính . 4
1.1.2 Bài toán cực tiểu giá thành sản phẩm 4
1.1.3 Bài toán cực đại hiệu suất tiêu diệt mục tiêu địch 5
1.2 Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ
bất phương trình tuyến tính và một vài tính chất của nó . 6
1.2.1 Bài toán quy hoạch phân tuyến tính với miền ràng buộc
là hệ bất phương trình tuyến tính . 6
1.2.2 Một vài tính chất của bài toán quy hoạch phân tuyến
tính với miền ràng buộc là hệ bất phương trình tuyến tính 7
1.3 Thuật toán nón xoay xấp xỉ trong giải bài toán quy hoạch phân
tuyến tính . 10
1.3.1 Khái niệm về nón đơn hình tuyến tính 11
1.3.2 Khái niệm về cạnh và phương của cạnh của nón đơn hình 11
1.3.3 Khái niệm nón xoay M(r,s) sinh ra từ nón M . 18
1.3.4 Dấu hiệu tối ưu (Điều kiện tối ưu): 22ii
1.3.5 Thuật toán nón xoay xấp xỉ trong giải bài toán quy
hoạch phân tuyến tính 23
1.4 Bảng lặp giải bài toán quy hoạch phân tuyến tính bởi thuật toán
PTT 25
1.5 Thuật toán nón xoay tìm một nghiệm của hệ bất phương trình
tuyến tính . 30
1.5.1 Thuật toán nón xoay tìm một nghiệm của hệ bất phương
trình tuyến tính với cơ sở xuất phát từ gốc toạ độ là đỉnh
của nón R
n
+ 31
1.5.2 Bảng lặp tìm một nghiệm của hệ bất phương trình tuyến
tính với cơ sở xuất phát từ gốc toạ độ là đỉnh của nón R
n
+ 32
2 Thuật toán nhánh cận xấp xỉ trong giải bài toán quy hoạch nguyên
phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến
tính và ứng dụng 34
2.1 Bài toán quy hoạch nguyên phân tuyến tính với miền ràng buộc
là hệ bất phương trình tuyến tính và thuật toán Land-Doig 34
2.1.1 Bài toán quy hoạch nguyên phân tuyến tính . 35
2.1.2 Thuật toán Land-Doig giải bài toán quy hoạch nguyên
phân tuyến tính 36
2.2 Thuật toán nhánh cận xấp xỉ trong giải bài toán quy hoạch
nguyên tuyến tính . 40
2.3 Minh họa ứng dụng thuật toán nhánh cận xấp xỉ trong ILF giải
bài toán quy hoạch nguyên phân tuyến tính có số chiều nhỏ với
miền ràng buộc là hệ bất phương trình tuyến tính 42
Kết luận và Đề nghị 57
Tài liệu tham khảo 58iii
Lời cam đoan
Tôi xin cam đoan đây là công trình nghiên cứu của tôi.
Thái Nguyên, ngày 20 tháng 04 năm 2015
Học viên
Đinh Quang Ngọc1
Mở đầu
Nhiều bài toán thực tế trong kinh tế cũng như trong toán học, thường gặp
trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong cắt nguyên vật liệu,
trong mạng vận tải và trong định giá thành sản phẩm, . dẫn đến chúng ta
phải đi giải các bài toán quy hoạch nguyên phân tuyến tính. Một phương pháp
hiệu quả thường sử dụng để giải bài toán này đó là phương pháp nhánh cận
Land-Doig.
Để giải bài toán quy hoạch nguyên phân tuyến tính thông thường là chúng ta
phải tiến hành giải các bài toán quy hoạch phân tuyến tính tương ứng khi chưa
có điều kiện nguyên của biến với các ràng buộc bổ sung dạng bất phương trình
cho các thành phần của biến. Rõ ràng khi sử dụng phương pháp nhánh cận để đi
tìm các cận dưới tốt hơn (đối với bài toán min) cho bài toán quy hoạch nguyên
thì ta thường phải giải các bài toán tương ứng khi chưa có điều kiện nguyên
với miền ràng buộc được bổ sung thêm sau mỗi bước một ràng buộc dạng bất
phương trình đối với thành phần chưa nguyên của biến.
Các thuật toán giải bài toán quy hoạch nguyên phân tuyến tính với miền ràng
buộc là hệ phương trình tuyến tính với các biến không âm đã có nhiều thuật toán
giải tương tự như thuật toán đơn hình trong quy hoạch tuyến tính (xem [2], [8]).
Tuy nhiên trên thực tế bài toán thường có miền ràng buộc là hệ bất phương trình
tuyến tính. Do đó việc sử dụng các thuật toán giải trực tiếp bài toán quy hoạch
phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính là khá ưu
việt và hiệu quả hơn (vì không phải thêm vào các biến bù) khi ta phải đi giải
chúng bởi các phương pháp mà miền ràng buộc đòi hỏi ở dạng chính tắc (tức
là miền ràng buộc là hệ phương trình tuyến tính đối với các ràng buộc chính).
Chính vì vậy, luận văn này trình bày việc xây dựng một thuật toán xấp xỉ trong2
giải bài toán quy hoạch nguyên phân tuyến tính với miền ràng buộc là hệ bất
phương trình tuyến tính và khai thác đặc thù riêng của hàm mục tiêu có tính đơn
điệu chứng minh bài toán nếu có lời giải thì nó có lời giải đạt ở biên của miền
chấp nhận, do đó trong mỗi bước để tìm các cận dưới đúng của bài toán nguyên,
chúng ta chỉ phải đi giải các bài toán quy hoạch tuyến tính tương ứng khi chưa
có điều kiện nguyên có số chiều là n ư 1 (n là số chiều của bài toán). Như vậy
thuật toán sẽ hiệu quả khi giải bài toán quy hoạch nguyên tuyến tính dạng chuẩn
có số chiều là 2.
Thái Nguyên, tháng 04 năm 2015
Đinh Quang Ngọc
Học viên Cao học Toán K7A
Chuyên ngành Toán ứng dụng
Trường Đại học Khoa học - Đại học Thái Nguyên
Email: [email protected]
Chương 1
Bài toán quy hoạch phân tuyến tính với miền
ràng buộc là hệ bất phương trình tuyến tính và
thuật toán giải
Như chúng ta đã biết, nhiều bài toán thực tế trong kinh tế cũng như trong
toán học, thường gặp trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong
cắt nguyên vật liệu, trong mạng vận tải và trong định giá thành sản phẩm, .
đều có mô hình toán học dạng các bài toán quy hoạch nguyên phân tuyến tính.
Vì vậy nội dung của chương này sẽ giới thiệu một số mô hình thực tế có dạng
bài toán này và sau đó trình bày thuật toán xấp xỉ trong giải bài toán quy hoạch
phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính, làm cơ sở
để xây dựng thuật toán giải bài toán quy hoạch nguyên phân tuyến tính với miền
ràng buộc là hệ bất phương trình tuyến tính trình bày trong chương 2.
1.1 Một số bài toán thực tế đưa về bài toán quy hoạch phân
tuyến tính và quy hoạch nguyên phân tuyến tính
Sau đây chúng ta trình bày một số mô hình bài toán thực tế có dạng bài toán
quy hoạch phân tuyến tính và bài toán quy hoạch nguyên phân tuyến tính với
miền ràng buộc là hệ bất phương trình tuyến tính.