XỬ LÝ TÍN HIỆU SỐ QUY HOẠCH PHI TUYẾN
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.08 MB, 10 trang )
BỘ GIÁO DỤC VÀ ĐÀO TẠO
HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
---------o0o--------BÁO CÁO ĐỀ TÀI GIỮA HỌC PHẦN
ĐỀ TÀI SỐ 11:
XỬ LÝ TÍN HIỆU SỐ
QUY HOẠCH PHI TUYẾN
HỌ TÊN:
LÊ ANH HUY
LỚP K26A - CHUYÊN NGÀNH: KHMT
TP.HCM, Tháng 11/2014
Quy Hoạch Phi Tuyến
1
Bài Toán Quy Hoạch Phi Tuyến: Cho trước các hàm số f, g1,..., gm của n biểu thức, hãy
xác định vectơ n chiều x = (x1, x2, ..., xn) thoả mãn các điều kiện xj ≥ 0, j = 1, 2, ..., n.
gi(x) ≤ 0, i = 1, 2, ..., m. và đạt cực tiểu toàn cục của hàm mục tiêu f(x).
CHƯƠNG X: QUY HOẠCH PHI TUYẾN : TỐI ƯU HOÁ MỘT BIẾN
ĐẶT VẤN ĐỀ :
-
-
Quy hoạch phi tuyến một biến, khơng ràng buộc có dạng :
tối ưu hố : z=f(x) khi f(x) là một hàm số (phi tuyến) theo biến x và việc
tìm kiếm giá trị tối ưu (cực đại hoặc cực tiểu) được tiến hành trên một
khoảng không xác định (-∞, +∞).
Nếu việc tìm kiếm được giới hạn thành một đoạn xác định [a, b], thì bài
tốn trở thảnh :
tối ưu hoá : z=f(x) với : a ≤x≤b đây là bài tốn một biến, có ràng buộc.
TỐI ƯU CỤC BỘ VÀ TỒN CỤC :
-
Hàm mục tiêu f(x) có cực tiểu cục bộ (cực tiểu tương đối) tại x 0 nếu tồn tại
một khoảng (nhỏ) (thuộc miền xác định của x) chứa x 0 mà f(x) ≥ f(x0) với
mọi x trong khoảng này. Nếu f(x) ≥ f(x 0) với mọi x trong miền xác định, thì
cực tiểu cục bộ tại x0 sẽ trở thành cực tiểu toàn cục (hay cực tiểu tuyệt đối).
Cực đại cục bộ và cực đại toàn cục cũng được định nghĩa tương tự (thay
lớsn hơn thành nhỏ hơn).
Ví dụ 10.1
2
-
Đồ thị của hàm số ở hình 10.1 được xác định trên đoạn [a, b].
Cực tiểu cục bộ tại : a, x2, x4
Cực đại cục bộ tại : x1, x3, b
Cực tiểu toàn cục tại : x2
Cực đại toàn cục tại : x1, b.
NHỮNG KẾT QUẢ TỪ TÍNH TỐN :
-
Định lý 10.1 : Nếu f(x) liên tục trên đoạn đóng và bị chặn [a, b] thì f(x) có
cực trị (cả cực đại lẫn cực tiểu) trên đoạn này.
Định lý 10.2 : Nếu f(x) có một cực trị cục bộ tại x 0 và f(x) khả vi (có đạo
hàm) trên khoảng chứa x0 thì f’(x0) = 0
Định lý 10.3 : Nếu f(x) có đạo hàm bậc hai trên khoảng chứa x0, và nếu
f’(x0) = 0 và f’’(x0) > 0 thì f(x) có cực tiểu cục bộ tại x0
f’(x0) = 0 và f’’(x0) < 0 thì f(x) có cực đại cục bộ tại x0
Hai định lý 10.1 và 10.2 chỉ ra rằng, nếu hàm f(x) liên tục trên đoạn [a,b]
thì cực trị cục bộ và toàn cục sẽ xảy ra tại những điểm sau : những điểm mà
f’(x) không tồn tại, những điểm mà f’(x)=0 (thường được gọi là những
điểm tới hạn hoặc điểm dừng), hoặc trong số những điểm biên x=a hoặc
x=b.
BÀI TẬP MẪU:
-
Cực đại: z = x(5π-x) trên đoạn [0, 20].
Ở đây f(x) = x(5π-x) là hàm liên tục, và f’(x) = 5π-2x. Với đạo hàm luôn
xác định, cực đại toàn cục trên đoạn [0, 20] xảy ra tại điểm biên x=0 hoặc
x=20, hoặc tại điểm dừng khi f’(x)=0. Ta tính được x=5π/2 là điểm dừng
duy nhất trên đoạn [0, 20]. Tính giá trị của hàm tại những điểm này, ta thu
được bảng sau :
x
f(x)
0
0
-
I.
5π/2
61.69
20
-85.84
Kết luận : x* = 5π/2 , với z* = -85.84
Bài Tập Áp Dụng
Bài 10.15:
Tính A[0,3]; B [0,2]; C [0,]
3
Bài Giải
Lấy đạo hàm cấp 1 ta có:
Với
A[0,3] khi cho
Tại A[0,3] độ dốc là [-1,32]
B[0,2] khi cho
Tại B[0,2] độ dốc là [-4,4]
C[0,] khi cho
Tại B[0,] độ dốc là [-4,]
CHƯƠNG XI: CHƯƠNG TRÌNH PHI TUYẾN
TỐI ƯU ĐA BIẾN KHÔNG HẠN CHẾ
HOOKE – JEEVES’ PATTERN SEARCH
Phương pháp này là một thuật tốn trực tiếp tìm kiếm mà sử dụng thăm dị, trong đó xác
định một hướng đi thích hợp và mơ hình di chuyển , trong đó đẩy mạnh việc tìm kiếm.
Phương pháp này được bắt đầu bằng cách chọn một vector ban đầu
và kích thước h
Bước 1: Di chuyển thăm dò xung quanh B được thực hiện bởi xáo trộn các thành phần
của B, theo thứ tự, bởi + hoặc - đơn vị h. Nếu một trong hai nhiễu loạn cải thiện (tức là
4
tăng) giá trị của hàm mục tiêu vượt quá giá trị hiện tại, giá trị ban đầu là f (B), giá trị
nhiễu loạn của thành phần đó được giữ lại. Sau khi mỗi thành phần đã được thử nghiệm
lần lượt, các vectơ kết quả được ký hiệu là C. Nếu C = B, đi đến Bước 2; nếu khơng thì
chuyển sang Bước 3.
Bước 2: B là vị trí của tối đa trong khả năng chịu đựng của h. Hoặc h được giảm xuống
và lặp đi lặp lại bước 1, hoặc tìm kiếm được, chấm dứt với X * = B.
Bước 3: Thực hiện chuyển mơ hình để tạm thời vector T = 2C-B. (T đạt được bằng cách
di chuyển từ B đến C và tiếp tục trong một khoảng cách bằng nhau trong cùng một
hướng.)
Bước 4: Hãy di chuyển thăm dò xung quanh T tương tự như xung quanh B được mô tả
trong Bước 1. Gọi kết quả vector S. Nếu S = T, đi đến bước 5; nếu không đi đến Bước 6.
Bước 5: Set B = C và trở về Bước 1
Bước 6: Set B = C, C = S, và quay lại Bước 3.
Bài Tập Áp Dụng:
Bài 11.21:
Tìm Max Z = -
Bài Giải
Max: Z = Chuyển bài tốn về:
Min: Z =
Ta có: => Z = 10
Khi thì là giá trị nhỏ nhất và là giá trị lớn nhất đạt được khi :
5
CHƯƠNG XII.
TỐI ƯU HỐ PHƯƠNG TRÌNH PHI TUYẾN VỚI HÀM NHIỀU BIẾN
CÓ HẰNG SỐ
Dạng chuẩn cho các quy hoạch phi tuyến chỉ chứa các ràng buộc là đẳng thức:
Cực đại:
Ràng buộc:
(12.1)
với:
Dạng chuẩn cho quy hoạch phi tuyến chỉ chứa các ràng buộc là bất đẳng thức:
Cực đại:
Ràng buộc:
(12.2)
Hoặc
Cực đại:
Ràng buộc:
(12.3)
Với:
Hai quy hoạch (12.2) và (12.3) là như nhau.
6
Quy hoạch dạng (12.3) thích hợp với các phương pháp giải yêu cầu các biến không âm.
Bài 12.17:
Minimize:
(1)
Với ràng buộc:
Bài Giải:
Đưa bài tốn về dạng chuẩn:
Maximize:
(2)
Với ràng buộc:
Ta có:
n = 2 biến, m = 1 ràng buộc
Xét hàm Lagrange:
Ta được:
(3)
(4)
(5)
Giải hệ 3 phương trình (3), (4), (5):
Từ (4):
=>
(6)
(Vì nếu thì (3) không thỏa mãn: )
Từ (5) và (6): => hoặc
(7)
7
Từ (3) và (7): => hoặc
Ta được hai không điểm: (2, 0) và (-2, 0)
Xét hàm mục tiêu tại hai điểm này:
Với
Với
Hàm mục tiêu của bài toán (2) đạt giá trị cực đại toàn cục tại (2, 0) và đạt giá trị
cực tiểu tồn cục tại (-2, 0).
Vì vậy hàm mục tiêu của bài toán (1) đạt giá trị cực tiểu tồn cục tại (2, 0):
Bài 12.22:
Tìm Min
Ràng buộc
Bài Giải:
Đưa dạng chuẩn : Min Max
Max:
Ta thấy bài tốn có 3 biến và 1 ràng buộc
Xét hàm:
8
Từ (3)
Từ (1)
Thế vào (4)
Ta được :
Trường hợp 1:
Với (A )
Thế (A) vào (4). Ta có:
Đặt
Với
Với
Với
Trường hợp 2:
Với (B)
Thế (B) vào (4) ta có:
Đặt
Với
9
_The end_
10
