87
Chương 4
MỘT SỐ BÀI TOÁN ĐIỀU KHIỂN TỐI ƯU QUAN TRỌNG
4.1 Đặt vấn đề
Giống như bài toán tối ưu nói chung, các bài toán điều khiển tối ưu có rất
nhiều dạng khác nhau, tùy theo điều kiện tối ưu và tiêu chuẩn tối ưu mà người ta đặt
ra. Tuy nhiên, một cách khái quát bài toán điều khiển tối ưu rời rạc có thể đặt ra như
sau:
Cho T= {0,1,2,...,N} tập các điểm rời rạc.
U là tập các điều khiển chấp nhận được và giả sử động thái của hệ được mô tả
bởi:
X(t)= G[x(t0) , u(t), t0, t]
Y(t)= H[x(t), u(t), t]
Trong đó : u(t)
U
G: (X x U x T x T) →X
H: (X x U x T) → Y
Giả sử S
X x Y x T là tập mục tiêu. Ta nói rằng tác động u(t)
U chuyển
(x0, t0) đến S nếu x(t0) = x0 và
{G[x(t0) , u(t), t0, t] ; H[G[x(t0) , u(t) , t0, t]; t
t0]}
S
Ø
Nếu t1 là thời điểm sớm nhất mà
(x(t), y(t), t)
S
Thì t1 –t0 gọi là thời gian chuyển. Khi đó bài toán điều khiển tối ưu hệ thống
mà ta đang xét là:
F(x0, t0, u(t),t1) → min
Trong đó F là phiếm hàm mục tiêu hay phiếm hàm chất lượng.
Ví dụ:
Xét nền kinh tế với thời gian rời rạc:
x(t+1) = (1-b)x(t) + z(t)
88
x(0) = x0, x(N)
M
y(t) = c(t) +z(t)
Trong đó : x(t) là vốn cơ bản, b là tỷ lệ hao mòn vốn cơ bản 0<b<1; z(t) là vốn
đầu tư ở năm t.
y(t) là thu nhập quốc dân, c(t) quỹ tiêu dùng ở năm t
Tham số điều khiển là u(t)= )(
)(
ty
tz là tỷ lệ tích lũy ở năm t.
Thông thường thu nhập quốc dân là hàm của vốn cơ bản
y(t)= h[x(t)] z(t)=u(t)h[x(t)]
Khi đó ta có bài toán:
x(t+1)= ax(t) + u(t) h[x(t)]
x(0) = x0 , x(N)
M
F=
1
0
max)]([))(1(
N
t
txhtu
Trong đó a=1-b; 1-u(t) là tỷ lệ tiêu dùng
Mục tiêu của bài toán điều khiển ở đây: chọn tỷ lệ tích lũy hàng năm như thế
nào để cho đến năm N vốn cơ bản x(N)
M (đạt được mức M) và tổng quỹ tiêu
dùng cho cả kỳ kế hoạch là lớn nhất. Nếu tính tới hệ số chiết khấu tiền tệ α(t) thì
hàm mục tiêu sẽ là:
F=
1
0
max)]([)())(1(
N
n
txhttu
Nếu hệ số chiết khấu hàng năm là không đổi thì α(t) = αN-1-t trong đó α>1.
Khi nghiên cứu các bài toán điều khiển tối ưu trong thực tế; có 3 vấn đề quan
trọng mà ta sẽ đề cập đến trong chương này:
- Một là bài toán điều khiển hệ động cỡ lớn và có nhiều bước. Vấn đề đặt ra là
ta phải tìm toàn bộ quỹ đạo của hệ trong tình huống mà cấu trúc của hệ trong tình
huống mà cấu trúc của hệ trong tình huống mà cấu trúc của hệ cũng có thể thay đổi
theo thời gian. Tất nhiên đối với bài toán rời rạc về thời gian, ta có thể đưa bài toán
động về bài toán tĩnh bằng cách tăng thứ nguyên của bài toán. Theo cách này ta sẽ
gặp khó khăn khi giải quyết các bài toán cỡ lớn. Vì vậy phải tìm mọi cách xử lý
khác, chẳng hạn thuật toán phân chia tương tự như trong phương pháp Quy hoạch
89
động: phân chia bài toán tối ưu trong không gian n chiều thành n bài toán tối ưu 1
chiều.
- Hai là đối với bài toán điều khiển các hệ thống phức tạp, cấu trúc của hệ
thường là yếu, thông tin lại không đầy đủ, thậm chí mục tiêu cũng không rõ ràng.
Trong trường hợp này lý thuyết “tối ưu mờ“ có thể là một cách tiếp cận bắt buộc và
có hiệu quả.
- Ba là Bài toán điều khiển tối ưu theo nhiều mục tiêu đồng thời trong đó có
những mục tiêu không tương thích với nhau và cũng có những mục tiêu mâu thuẫn
nhau; ở đây lý thuyết cực trị thông thường tỏ ra không thích hợp, chúng ta phải tìm
một giải pháp khác.
Ta sẽ lần lượt nghiên cứu giải pháp cho từng tình huống nêu trên.
4.2 Điều khiển tối ưu của hệ động cỡ lớn nhiều bước
Trong phạm vi cuốn sách này ta chỉ xét những hệ tuyến tính để việc diễn giải
dễ dàng hơn và thuật toán phân chia cũng dễ thực hiện hơn, đối với những hệ phai
tuyến, về nguyên tắc vẫn có thể áp dụng nhưng kỹ thuật tính toán cụ thể đòi hỏi
phải có những bổ sung thích hợp do đó phức tạp hơn.
Bài toán quy hoạch tuyến tính nhiều bước tổng quát có dạng:
F[x(t) , u(t), c(t)]
min
x(t+1) =Ax(t) +Bu(t) +S(t)
Px(t)+ Qu(t)
R(t)
x(t)
0, t=0,1,2,...,N
Ví dụ : bài toán lập kế hoạch sản xuất có dạng
F=
N
t
tutc
1
min)(),(
x(t) = x(t-1) +Bu(t) – h(t)
Du(t) = d(t)
x(0) =x0
Trong đó : x(t) mức dự trữ sản phẩm ở năm t
u(t) mức hoạt động sản xuất ở năm t
B ma trận các hệ số “hoạt động – ra“
90
D ma trận các hệ số “hoạt động – vào“
h(t) mức tiêu thụ ở năm t
d(t) hạn chế về tài nguyên, công suất ở năm t.
c(t) chi phí (hao phí) cho một đơn vị cường độ hoạt động sản xuất ở năm t.
Để giải bài toán này ta có thể đổi chỉ số để đưa về bài toán quy hoạch tuyến
tính thông thường, nhưng tốt hơn vẫn là lợi dụng cấu trúc đặc biệt của bài toán này
để giải trực tiếp bằng cách phân chia thành các bài toán nhỏ, theo phương pháp
phân chia của Dantzig – Wolfe.
Ta viết lại bào toán này như sau:
<C(1),u(1)+<C(2),U(2)>+...+<C(N),U(N)>
min
x0 +Bu(1) – x(1) = h(1)
Du(1) = d(1)
x(1) +Bu(2) – x(2) = h(2)
Du(2) = d(2)
...
X(N-1)+Bu(N) =x(N) = h(N)
Du(N) =d(N)
Cấu trúc của bài toán này rất đặc biệt, nó bao gồm các khối tuy có “dính” nhau
nhưng chỉ “dính” rất ít. Phương pháp Dantzig – Wolfe cho phép tách bài toán này
thành dãy các bài toán con đơn giản hơn. Cụ thể là :
- Khối (1) độc lập với các khối khác, nên có thể tách ra thành một bài toán con
để giải.
<C(1),u(1)>
min
x0 +Bu(1) – x(1) = h(1)
Du(1) = d(1)
Trong bài toán này có dính đến x0 nhưng x0 là điều kiện ban đầu cho trước
- Khối (2 ) có dính đến khối (1) bởi x(1)
<C(2),u(2)>
min
X(1) +Bu(2) – x(2) = h(2)
91
Du(2) = d(2)
Nhưng khi giải bài toán khối (1) thì x(1) đã được hoàn toàn xác định một cách
tối ưu và được coi là điều kiện ban đầu của bài toán khối (2).
- Khối (N) tương tự như trên có dính đến khối (N - 1) bởi x(N-1), đã được xác
định một cách tối ưu khi giải bài toán khối (N-1)
<C(N),u(N)>
min
x(N-1) +Bu(N) – x(N) = h(N)
Du(N) = d(N)
Và x(N-1) được coi là điều kiện ban đầu của bài toán khối (N). Nhờ cách này
ta đã phân chia được một bài toán N bước cỡ lớn thành N bài toán 1 bước cỡ nhỏ và
đơn giản hơn.
Đối với bài toán quy hoạch tuyến tính cỡ lớn, bên cạnh thuật toán phân chia
như trên, phương pháp nhân tử Lagrange tỏ ra có hiệu lực. Chẳng hạn ta xét bài
toán
F(x)= CTx
min
Ax
b, x
0
Trong đó CT là chuyển vị của C
Ta viết lại điều kiện Ax
b dưới dạng g(x)= b-Ax
0, khi đó hàm Lagrange có
dạng.
L(x,
)= CTx + λT(b-Ax) = (C – ATλ)x + λTb
Trong đó C
Rn, λ
Rm còn λT là chuyển vị của λ.
Bài toán tìm cực tiểu của hàm L(x,λ) tương đương với bài toán đối ngẫu
λTb
max
ATλ
C, λ
0
Trong thực tế, có không ít trường hợp, bài toán đối ngẫu dễ giải hơn bài toán
gốc; khi ấy phương pháp nhân từ Lagrange cho phép chúng ta phân chia một bài
toán quy hoạch lồi cỡ lớn thành một dãy các bài toán quy hoạch lồi đơn giản hơn,
với một số giả thiết nhất định.