Download miễn phí Đề tài Tối ưu số cho bài toán tối ưu một mục tiêu
PHẦN 0: MỞ ĐẦU 1
PHẦN 1: TỔNG QUAN 3
I. Khái quát 4
II. Phạm vi sử dụng 4
III. Người sử dụng 4
IV. Nhiệm vụ 4
PHẦN 2: GIỚI THIỆU CÁC PHƯƠNG PHÁP TỐI ƯU CỔ ĐIỂN
A. Mở Đầu 6
I. Đối tượng nghiên cứu 6
1. Bài toán tối ưu tổng quát 6
2. Phân loại các bài toán 7
II. Vấn đề mô hình hóa toán học 8
1. Xây dựng mô hình hóa toán học cho một vấn đề thực tế 8
2. Một số mô hình thực tế 9
B. Các loại bài toán tối ưu và phương pháp cổ điển 10
I. Quy hoạch tuyến tính 10
1. Bài toán quy hoạch tuyến tính 10
a. Bài toán tổng quát 10
b. Dạng chuẩn và dạng chính tắc 11
2. Một số tính chất chung 12
3. Phương pháp đơn hình giải QHTT 12
a. Đường lối chung của thuật toán 12
b. Thuật toán đơn hình 13
4. Thuật toán đơn hình cải biên 15
II. Quy hoạch đối ngẫu 17
1. QHTT dưới dạng chuẩn, cặp bài toán tuyến tính đối ngẫu đối xứng 17
2. QHTTdưới dạng chính tắc,cặp bài toán tuyến tính đối ngẫu không đx 17
3. Cặp bài toán đối ngẫu tổng quát 18
4. Ý nghĩa cặp bài toán đối ngẫu 19
a. Ý nghĩa toán học 19
b. Ý nghĩa kinh tế 19
5. Thuật toán đơn hình đối ngẫu 21
http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2017-07-19-de_tai_toi_uu_so_cho_bai_toan_toi_uu_mot_muc_tieu_eD1yqGX6qW.png /tai-lieu/de-tai-toi-uu-so-cho-bai-toan-toi-uu-mot-muc-tieu-92807/ Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn. Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn
Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ặp xây dựng dãy íxký hội tụ tới điểm tối ưu (hay điểm dừng) x*. Giả sử ta đang ở điểm xk thuộc lân cận của x*, khi đó để làm cho hàm mục tiêu giảm ta nên chuyển động theo hướng p làm với f’(xk) một góc tù, tức là xác định.
xk+1 = xk + ap, trong đó a > 0. (f’(xk),p) < 0.
Thật vậy, khai triển f(x) theo chuỗi Taylo:
F(x) = f(xk) + a( f,p) + a2/2
trong đó f = f’(xk), f = f’’(xkc), xkc = xk + q(x - xkc), q Ỵ [0,1]. Nếu < 0 thì với a nhỏ ta có f(x) < f(xk) (vì dấu của phần vế phải xác định bởi phần tuyến tính đối với a).
Việc lựa chọn hướng dịch chuyển p và độ dài bước a khác nhau cho ta các phương pháp cực tiểu khác nhau. Phương pháp gradient (hay còn gọi là phương pháp tụt nhanh nhất) có dạng
xk+1 = xk - akf’(xk), ak > 0, k = 0,1, ... (1)
tức là chọn pk = f’(xk). Đây là phương pháp thông dụng nhất để tìm cực tiểu, nó rất đơn giản và áp dụng được cho những lớp hàm rất rộng.
Thuật toán xác định ak tại mỗi bước lặp:
Chọn giá trị tùy ý a (và cố định, ví dụ a = 1) và xác định điểm x=xk - af.
Tính f(x) = f(xk - af).
Kiểm tra bất đẳng thức
f(x) – f(xk) £ ea = -ea êêf êê2, (2)
trong đó 0 < e < 1 là một hằng số chọn tùy ý và cố định.
Nếu (2) thỏa mãn thì ta chọn giá trị a làm giá trị phải tìm: ak=a. Nếu (2) không thỏa mãn thì ta chia a (bằng cách nhân a với số l < 1) cho đến khi bất đẳng thức (2) được thỏa mãn.
Các dạng khác của phương pháp Gradient
Phương pháp gradient với bước dịch chuyển cố định.
Phương pháp gradient với việc cực tiểu hàm theo hương chuyển động.
PHƯƠNG PHÁP MONTE-CARLO
Phát biểu bài toán
Trong kinh tế cũng như trong kỹ thuật, chúng ta thường gặp bài toán tối ưu mà hàm mục tiêu không phải là tuyến tính, không lồi, không lõm, còn miền ràng buộc cũng không lồi. Nhiều khi hàm mục tiêu không viết được dưới dạng hiển mà chỉ có một quy trình tính toán phức tạp để được một giá trị. Xét bài toán
min f(x) (1)
với các ràng buộc
x Ỵ D (2)
aj £ xj £ bj, j = 1, .... , n (3)
trong đó x = (x1, ... , xn), D là một tập thuộc Rn và hàm mục tiêu f là ánh xạ từ Rn vào R1. Hàm f(x) và miền ràng buộc D có thể được xác định bởi những hàm phi tuyến rất khó tính.
Để giải những bài toán như vậy, chúng ta chỉ còn hy vọng vào phương pháp Monte-Carlo để tìm lời giải tối ưu toàn cục. Phương pháp này chỉ áp dụng được cho bài toán (1)-(3) với số biến không nhiều (n £ 30).
Nội dung phương pháp
Biến it được dùng để đếm số điểm tạo ngẫu nhiên trong siêu hợp S=íx:aj £ xj £ bj, j = 1, .... , n ý Ì Rn, sf để đếm số phương án chấp nhận được tìm được. Tại mỗi bước lặp gọi x là phương án tốt nhất hiện biết với trị hàm mục tiêu a=f(x). Phương pháp Monte-Carlo gồm các bước sau:
Bước 1: Đặt it = 0, sf = 0, a = M (M là số dương đủ lớn, chẳng hạn 1030).
Bước 2: Mở đầu bước lặp với việc tăng số điểm tạo ngẫu nhiên lên một: it = it +1. Với mỗi j ta tạo một số ngẫu nhiên phân bố đều trên đoạn [aj, bj] theo công thức
x’j = aj + x(bj - aj). (4)
trong đó x là một số ngẫu nhiên phân bố đều trên đoạn [0,1]. Lưu ý rằng với mỗi số j số x trong (4) là khác nhau. Như vậy sau n lần tạo số ngẫu nhiên ta được một bộ giá trị x’=(x’j, ... , x’n).
Bước 3: Kiểm tra xem x’ có thuộc D hay không. Nếu x’ Ï D thì chuyển lên bước 2. Nếu x’ Ỵ D thì số phương án tìm được tăng lên một đơn vị sf=sf + 1 và sang bước 4.
Bước 4: Tính giá trị hàm mục tiêu f(x’)
Nếu f(x’) > a thì chuyển tới bước 2.
Nếu f(x’) < a (x’ là phương án của bài toán (1)-(3) tốt hơn phương án x cũ) thì lấy x’ thay cho x và lấy a = f(x’). Chuyển lên bước 2.
Người ta có thể chứng minh được rằng nếu bài toán (1)-(3) có phương án tối ưu thì khi it đủ lớn ta có thể tìm được lời giải của bài toán với xác suất bằng 1.
Cách dừng thuật toán:
Trong quá trình giải, sau một số lần tạo điểm x’ theo (4) ta lại in lên màn hình số điểm chấp nhận được đã tìm được, giá trị hàm mục tiêu cùng phương án tốt nhất cho tới lúc này: sf, a và x. Nếu số điểm chấp nhận được đủ nhiều, phương án x và f(x) phù hợp với thực tiễn thì dừng tính toán.
Nếu số bước lặp it đã quá lớn hay thời gian tính toán đã quá lâu mà giá trị hàm mục tiêu không cải tiến thêm thì dừng tính toán. Khi dừng tính toán theo cách này mà số phương án sf = 0 thì ta nghi ngờ bài toán (1)-(3) không có phương án, cần xét lại cách đặt các ràng buộc sao cho hợp lý.
KẾT LUẬN
Qua các phương pháp nêu trên, ta thấy có rất nhiều phương pháp để giải bài toán tối ưu hóa. Các phương pháp đều đưa ra được các lời giải tối ưu, nhưng chưa đạt được độ chính xác cao và đối với các bài toán lớn với hơn hàng trăm ràng buộc thì phải tốn nhiều thời gian để thực hiện các bước trong phương pháp. Để khắc phục các nhược điểm đó, người ta đã đưa ra một thuật giải mới : Thuật Giải Di Truyền.
Phần 3
GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN
TỔNG QUAN VỀ THUẬT GIẢI DI TRUYỀN (GENETIC ALGORITHMS - GA)
ĐẠI CƯƠNG
Trong sinh hoạt hằng ngày, chúng ta thường gặp những vấn đề từ đơn giản đến phức tạp như chọn trường cho con em, tìm đường đi ngắn nhất để đi làm, hoạch định chương trình chạy máy để tận dụng khả năng các công cụ
Để giải quyết vấn đề thường dựa vào các cách sau:
Dựa trên các công thức toán học hay những định luật khoa học (tiếp cận chính xác).
Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm).
Dựa theo sự tiến hóa, bắt chước lối cải thiện thích nghi mà con người hay sinh vật nói chung, đã dùng để tồn tại và phát triển (tiếp cận thử và sai).
cách dựa trên các công thức toán học hay những định luật khoa học thường cho những đáp số rất chính xác. Nhưng ta phải tìm ra công thức hay giả tưởng những điều kiện hoạt động cho giống với thực tế, điều này không thể thực hiện một cách dễ dàng.
Trong những năm 70, mạng Nơron nhân tạo, logic mờ cùng với thuật giải di truyền được nghiện cứu và áp dụng trong việc giải quyết các trường hợp phức tạp.
Nhìn chung, con người và sinh vật đều phải “tiến hóa để thích nghi với hoàn cảnh”.
“Tiến hóa cho thích nghi” không có nghĩa là luôn tìm ra giải pháp tuyệt đối cho vấn đề, nhưng có thể chỉ là tương đối trong điều kiện cho phép.
THUẬT GIẢI DI TRUYỀN GIẢI QUYẾT VẤN ĐỀ TRÊN MÁY VI TÍNH
GA bắt nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên.
GA là cách giải quyết vấn đề bắt chước lối hành xử của con người để sinh tồn và phát triển.
GA giải quyết được vấn đề trên máy vi tính nhờ vào chương trình tin học để thể hiện những ý tưởng cơ bản như tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện thời gian và không gian cho phép.
Không giống các phương pháp khác, GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp, sau đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có hệ số thích nghi ngày càng cao. Do đó khi giải quyết vấn đề bằng GA, chúng ta phải thông qua các giai đoạn sau:
Chọn mô hình (model) để tượng trưng cho các giải pháp. Các mô hình có thể là dãy (String) những số nhị phân : 1 và 0, thập phân và có thể là chữ hay hỗn hợp của chữ và số.
Aùp dụng lý luận và cách biến hóa trên mô hình này, thay vì trên các giải pháp.
Chọn hàm số thích nghi để dùng làm tiêu chuan đánh giá các giải pháp.
Tiếp tục các hình thức biến hóa cho đến khi đạt được giải pháp tốt nhất hay đến khi thời gian cho phép chấm dứt.
Như vậy, GA là một hình thức tìm kiếm có tính ngẫu nhiên nhưng được hướng dẫn bởi hàm số thích nghi. GA không thể luôn tìm ra giải pháp tối ưu, nhưng chắc chắn sẽ cung cấp những giải pháp tương đối trên nền tảng vững chắc và trong thời gian nhanh nhất.
TỔNG KẾT
Tuy chỉ mới được hình thành cách đây chưa đầy 25 năm, GA đã có được cơ sở toán học vững chắc về lý thuyết và số lượng những áp dụng ngày càng gia tăng bao gồm nhiều lĩnh vực khác nhau.
GA đã kết hợp với các kỹ thuật thuộc lĩnh vực trí tuệ nhân tạo như Expert Systems (Hệ Chuyên Gia), Artificial Neural Network (mạng Nơron nhân tạo) và Fuzzy Logic (Logic mờ) nhằm tìm giải pháp tối ưu cho những vấn đề phức tạp mà các cách cổ điển đã không giải quyết thỏa đáng.
GA được ứng dụng trong nhiều lĩnh vực khác nhau. Nhìn chung, những ứng dụng này có thể chia làm 3 nhóm chính:
Tìm mô hình tối ưu cho vấn đề. Tìm kiếmvà tối ưu hóa giải pháp là đề tài thích hợp nhất của GA.
Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận trong môi trường.
Chọn lựa các nhóm hay thành phần trong một tổ chúc.
Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh tế-tài chính, kỹ thuật, nghiên cứu và phát triển.
NHỮNG NGUYÊN TẮC CƠ BẢN CỦA THUẬT GIẢI DI TRUYỀN
ĐẠI CƯƠNG
GA không chú trọng đến giải pháp duy nhất và chính xác như phương pháp cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốt nhất nếu không nói là tối ưu. GA tuy dựa trên tính ngẫu nhiên nhưng có hướng dẫn bởi hàm số thích nghi, do đó không có nghĩa là “đoán mò” như nhiều người hiểu lầm, trái lại GA có một nền tảng toán học vững chắc.
CÁC TÍNH CHẤT ĐẶC THÙ CỦA THUẬT GIẢI DI TRUYỀN
GA lập luận mang tính chất ngẫu nhiên (stochastic...
