Bài giảng Lý thuyết hệ thống và điều khiển học: Phần 2 - ĐH CNTT&TT

Chia sẻ: Kiếp Này Bình Yên | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

143
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

(NB) Phần 2 của bài giảng "Lý thuyết hệ thống và điều khiển học" trình bày một số bài toán điều khiển tối ưu quan trọng và tổ chức xây dựng và quản lý hệ thống kinh tế. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết hệ thống và điều khiển học: Phần 2 - ĐH CNTT&TT

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) 87
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
độ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 N F=   c(t ), u(t )  min t 1 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“ 89
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:
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)  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. 91
4.3 Điều khiển tối ưu mờ 4.3.1 Vấn đề Khi nào xuất hiện bài toán điều khiển tối ưu mờ? - Trước tiên để lựa chọn một tác động điều khiển thì ta phải biết tập các phương án có thể có để lựa chọn. Trong trường hợp thiếu những thông tin xác định, thì tập các phương án này là không rõ ràng là mờ. Ví dụ như trong bài toán quy hoạch tuyến tính, tập các phương án có dạng {Ax=b, x  0}, trong đó thành phần bi của vec- tơ b lại không xác định; mà chỉ biết bi lấy các giá trị trong khoảng [αi, βi] với các xác xuất tương ứng khác nhau; đó là lý do mà ta phải nghiên cứu điều khiển mờ. - Muốn lựa chọn tác động điều khiển, ta phải biết mục tiêu điều khiển, coi đó là tiêu chuẩn so sánh để lựa chọn phương án. Nhưng trong nhiều trường hợp mục tiêu lại không rõ ràng, ví dụ như: phương án lựa chọn phải “khá gần y” hoặc sau 3 năm phải xóa được đói và giảm được nghèo, xóa đói là rõ, nhưng giảm nghèo lại là mờ, một số mục tiêu như phấn đấu giảm lạm phát, theo định hướng xã hội chủ nghĩa trở thành một nước công nghiệp tiên tiến,.v.v… đều là các khái niệm mờ. Mục tiêu ta muốn đạt đến là khái niệm mờ thì vấn đề tối ưu đặt ra phải là “tối ưu mờ”. Như vậy là, nếu bài toán điều khiển đặt ra mà “ràng buộc không rõ” hoặc “mục tiêu không rõ” hoặc “cả ràng buộc và mục tiêu đều không rõ” thì chúng ta phải xử lý theo những nguyên tắc của “lý thuyết mờ”; vì vậy các bài toán đó gọi là các bài toán “điều khiển tối ưu mờ”. Để giải quyết vấn đề này, trước tiên chúng ta cần tìm hiểu một số khái niệm cơ bản của lý thuyết mờ. 4.3.2 Một số khái niệm cơ bản trong lý thuyết mờ a)Định nghĩa tập mờ Để trình bày khái niệm tập mờ được dễ hiểu ta quy ước gọi khái niệm tập hợp mà ta đã quen biết là “tập rõ”. Cho một “tập rõ” A, ta đưa ra một đối tượng x nào đó thì phải khẳng định được: - Hoặc là x  A; điều này cũng có nghĩa là P {x  A}=1 tức là xác suất để x  A là bằng 1, đó là sự kiện chắc chắn. - Hoặc là x  A, tương đương với P{x  A}=0. Không có trường hợp nào khác. 92
Bây giờ ta xét trường hợp mà ta không khẳng định được x có thuộc A hay không mà chỉ khẳng định được x thuộc A với một xác suất nào đó. Khi đó A gọi là tập mờ . Một cách khái quát ta có định nghĩa tập mờ như sau. Ký hiệu X là “tập vũ trụ” trong vấn đề đang xét ; A  X được cho bởi ánh xạ  A:X →L= [0,1] Được gọi là “tập mờ” (fuzzy set )của X. Như vậy ứng với mỗi x  X ta có một số  A(x)  [0,1] biểu thị mức độ “x thuộc A”. Nếu  A(x) gần 0 thì mức độ x thuộc A là thấp; và như vậy mỗi phần tử của X thuộc tập mờ A với những mức độ khác nhau từ [0,1]. Hàm  A gọi là hàm thuộc (membership function), như vậy một tập rõ của X, có thể xem như một tập mờ mà hàm thuộc chỉ lấy giá trị 0 hoặc 1 mà không lấy các giá trị trung gian:  A(x)  {0,1}  x  A X đôi khi gọi là không gian nền. Giá tựa của tập mờ A , ký hiệu là suppA là tập con (rõ) của X được xác định bởi suppA={x  X;  A(x)>0} Đôi khi ta còn ký hiệu tập mờ như sau: A={ x } A( x) , x  sup pA Tức là liệt kê tất cả các phần tử x của A, kèm theo giá trị của hàm  A(x)>0. Ví dụ X là tập các số tự nhiên từ 1 đến 10 và A={ 3 0,5 , 4 0,2 , 5 0,8 , 81 , } Có nghĩa là tập mờ mà  A(3)= 0,5,  A(4)= 0,2;  A(5)= 0,8;  A(8)=0,1 và  A(x)=0 với các số tự nhiên còn lại. Khi định nghĩa một tập mờ A nếu x và 1 ( x) x x x  2 ( x) đều xuất hiện và  1(x)<  2(x) thì chỉ lấy  2 ( x) và bỏ đi 1 ( x) và tập A được thu gọn lại Ví dụ: A={ a 0,2 , a 0,5 , b 0,1 } thì rút gọn lại thành A= { a 0,5 , b 0,1 } 93
Tập mức của A.    [0,1]; tập mức  của A ký hiệu là N  (  A ) ={ x  X;  A(x)   } Dễ dàng thấy rằng đây là một tập rõ và N0(  A)= X b) Các phép toán trên tập mờ Trước tiên ta quy ước nếu u,v là 2 số thực thì u  v= max {u, v} u  v= min{u, v} - Hợp của 2 tập mờ A và B là tập mờ A  B mà  A  B(x)=  A(x)   B(x) Hoặc có thể viết: A  B={ x  ( x) : x  sup pA  sup pB;  A ( x)   B ( x) } - Giao của hai tập mờ A và B là tập mờ A  B mà  A  B(x)=  A(x)   B(x) Hoặc cũng có thể viết A  B={ x  ( x) : x  sup pA  sup pB;  A ( x)   B ( x) } x Phần bù của tập mờ A là tập mờ  A={ (x) : x 1A(x) với  A(x)
y 1 V A1 (x1)  A2 (x2 ) ... An (xn ) } { ( y). f ( y) Ø;  (y)= x1, x2 ,...,xnf 1( y) Tích của tập mờ A với số thực λ là ảnh của tập mờ A qua ánh xạ: x →λx λA={ x  ( x) : x  sup pA;  ( x)   A ( x  ) } Vậy : Tổng của 2 tập mờ A và B là tập mờ A+B= f(A,B) Trong đó : f: X x X →X là ánh xạ (x1 , x2)→ x1 + x2 Vậy: A+B=  x  ( x) : x  sup pA  sup pB;  ( x)  { xV  A(x1)  B (x2 ) }} 1x2 Tích trực tiếp của 2 tập mờ A và B là tập mờ A x B A x B= { ( x, y )  ( x, y) : x  A, y  B;  ( x, y )   A ( x )   B ( y ) } c) Quan hệ giữa 2 tập X và Y: là tập con mờ của X x Y R={ ( x, y )  ( x, y) : x  X , y  Y } R Trong đó:  R ( x, y) : X x Y→[0,1] Mở rộng quan hệ mờ n ngôi: là tập mờ của X1 x X2 x…x Xn R  x1 , x2 ,..., xn  ( x , x ,..., x ) xi  X  R 1 2 n ( i 1, n )  Trong đó  R ( x1 , x2 ,..., xn ): X1 x X2 x…x Xn→[0,1] Phép hợp thành R● S của các quan hệ mờ Cho R là quan hệ mờ giữa X và Y S là quan hệ mờ giữa Y và Z Thì hợp thành R● S là quan hệ mờ R● S ={( ( x, z )  ( x, z ) ) :x  X, z  Z}  ( x, z ) =y V{  R ( x, y )   S ( y, z ) } 95
Khi áp dụng lý thuyết mờ để nghiên cứu các bài toán điều khiển tối ưu mờ, một điều cần nhấn mạnh là: đối tượng nghiên cứu là mờ nên vệc tính toán có nhiều phiền phức hơn so với đối tượng nghiên cứu là rõ, nhưng phương pháp nghiên cứu vẫn phải dựa trên những tư duy rõ ràng, chặt chẽ và chính xác như khi nghiên cứu các đối tượng toán học rõ ràng khác. 4.3.3 Bài toán tối ưu mờ Trong ngôn ngữ của lý thuyết mờ, muốn lựa chọn một quyết định phải có bộ ba sau đây: - Tập các phương án để lựa chọn : X - Tập các ánh xạ μ0 , μ1,...,μm: X→ L=[0,1] xác định các tập con mờ A0, A1, ..., Am của X, biểu thị các tiêu chuẩn so sánh các khả năng. D= μ0  μ1  ...  μm Khi đó ta nói một bài toán tối ưu mờ được cho bởi bộ ba (X, D, L) là bài toán tìm x*  X (nếu có) sao cho: D(x*)= supD(x) xX x* được gọi là phương án tối ưu của bào toán. Đó là cách đặt vấn đề của Bellman và Zadeh. Chú ý: Thực ra trong bài toán của Bellman và Zadeh, L không nhất thiết phải là khoảng [0.1] mà chỉ đòi hỏi “L là 1 dàn phân phối đầy đủ” theo nghĩa: - Mọi tập con trong L đều có cận trên đúng và cận dưới đúng. -  x, y  L, tồn tại cận trên bé nhất x  y và cận dưới lớn nhất x  y thỏa điều kiện (tính chất phân phối) (x  y)  z=(x  z )  (y  z ) Dưới đây ta chứng minh một số mệnh đề làm cơ sở cho việc giải quyết bài toán tối ưu mờ nêu trên. Cho X là 1 tập; L=[0,1], mỗi tập con mờ của X được cho bởi ánh xạ μ: X→L; để cho tiện ta gọi μ là tập mờ, (tức là đồng nhất tập mờ với hàm thuộc μ của nó) Với mỗi α  L; tập Nα(μ)={x  X: μ(x> α)} gọi là tập mức α của tập mờ μ; 96
Ký hiệu M(X) là họ tất cả các tập mờ của X. Ta chứng minh một số mệnh đề sau: Mệnh đề 1: Nếu μ  M(X) thì μ= V (   (a ) )  L Trong đó  ( a ) là hàm đặc trưng của tập mức Nα(μ), tức là: 1nếu x  Nα(μ)  (a ) (x)=  0nếu x   Nα(μ) với μ (x)   1)  (a ) (x)=  Nếu trái lại 0 Chứng minh: V (α   ( ) )( x) =  V    ( ) ( x)   V    ( ) ( x)  L  N (  )   N (  )  = V (  1) = V  = μ(x) điều phải chứng minh  N (  )  N (  ) Bây giờ xét bài toán tối ưu mờ(X,D,L) D=μ0  μ1  ...  μm; L=[0,1] Ta sẽ chứng minh rằng: sup D(x) = sup  0 (x) với một A  X nào đó. xA xA Mệnh đề 2: Sup D(x)= V [α1  α2  …  αm  sup  0 ( x) ] 1 ..., m L )  1(1 ) ...  m ( m Chứng minh: Trước tiên chú ý rằng m   1 1  ...   m m =  N αi(μi) i 1 Theo mệnh đề 1 ta có: μi = V (  1  1( ) ) (i=1,2,…,m); do đó, ta có : 1 1L 97
supD(x)= V [ μ0(x)  μ1(x)  ...  μm(x)] x X = V [ μ0(x)  V ( α1  1 ( x))  …  V ( αm   m  (x)) ] 1 m x X 1L  m L Do tính chất phân phối nên: D(x)= V V [ α1  …  αm   0 ( x)  1 ( x)  ...   m  ( x) ] 1 m x X 1 ..., m L = V [ α1  …  αm V (  0 ( x)  1 ( x)  ...   m ( x) )] 1 m 1 ..., m L x X = V [ α1  …  αm  sup  0 ( x ) ] 1 ..., mL m x  N  i (  i ) i 1 Đó là điều cần chứng minh. Không giảm tính tổng quát của bài toán, ta có thể coi như bài toán chỉ có một ràng buộc μ (m=1). Khi đó D=μ0  μ. Ta xét hàm φ: L→L sao cho: φ (α)= sup 0 ( x) xN (  ) Khi đó ta có: (α  β)  (N α(μ)  N β(μ))  ( φ (α)  φ (β))  α,β  L Ký hiệu g(α)= α  φ (α) ; Theo mệnh đề 2 ta có: Sup D(x) = V ( α  sup (x))  L xN (  ) = V ( α  φ (α))= V g(α)=  L  L sup g(α)  L Mệnh đề 3: Nếu φ là hàm liên tục thì   L sao cho: φ (  ) =  và  = sup g(α)  L Chứng minh: Sự tồn tại của  là do định lý điểm bất động. Chỉ cần chứng minh  = sup g(α)  L 98
Nếu α α g(α)= α  φ (α)= α <  Còn nếu  >α thì φ (α)  φ (  )=   Vậy = sup g(α)= sup D(x)  L  L Như vậy để có cực đại của  0 với ràng buộc mờ  thì phải tìm cực đại của  0 trên tập rõ: N (  ) Định lý 1: Với giả thiết φ liên tục sup D(x)= sup  0 (x)  L xL Trong đó: A={x  X:  (x)   0 (x)} Chứng minh: sup [  0 (x)   (x)]= ( sup  0 (x))  ( sup  (x))  sup  0 (x) xL xA x A x A Ta lại có: nếu x  μ    (x)   = sup  0 (x)   0 (x) x A  x  A; nghĩa là: μ   A Do đó theo mệnh đề 3 sup [  0 (x)   (x)]= sup  0 (x) sup  0 (x) xL x  x A Suy ra sup D(x)= sup  0 (x) điều cần chứng minh. xX xA 99
Bây giờ ta hãy xét bài toán với X=Rn. định lý 2 dưới đây sẽ cho ta thấy có thể đưa bài toán tối ưu mờ về bài toán tối ưu thông thường. Định lý 2 0 Phương án x0  X là tối ưu khi và chỉ khi véc – tơ y=(x0, xn1 )  X x L 0 0 Trong đó x n 1 = min  ( x i ) là lời giải của bài toán quy hoạch i max xn1  (P)  xn1   i ( x) (i=0,1,…,m) x  X  Chứng minh: Ta có (P)  max min xX i[ 0 ,1,..., m ]  sup (  0 (x)  1 (x)  ...   m (x)) điều phải chứng mình. xX Ví dụ: Bài toán kế hoạch mềm dẻo(flexible planning) Nhiều bài toán kế hoạch được thể hiện bởi bài toán quy hoạch tuyến tính với các ràng buộc n a j 1 ij x j  bi (i=1,2,...,m) Thông thường để cho bài toán ứng phó được với những biến động trong thực tế, tức là để cho kế hoạch được mềm dẻo, người ta thay bi bởi một khoảng [αi ,βi] và coi như x=(x1, x2,...,xn) là phương án chấp nhận được nếu: n a j 1 ij x j  [ i ,  i ] Bây giờ ta xét các tập mờ với các hàm thuộc φi : Rn →L=[0,1] (i=1,2,...,m) trong đó: 100
n  i   aij x j j 1 φi (x)= i   i thì ta có bài toán quy hoạch mờ (Rn,D, L) với D=( φ1  φ2  ...  φm) Tức là tìm sup =( φ1  φ2  ...  φm) (x) xR n Theo định lý 2 ta có bài toán max xn 1  n  (  i   i ) x n 1   i   aij x j (i=1,2,...,m)  j 1 x  R  n Và cuối cùng ta đưa được bài toán “mềm dẻo” về dạng bài toán quy hoạch thông thường. 4.4 Bài toán tối ưu mờ trong quản lý Trong mục trên, ta sử dụng lý thuyết mờ làm công cụ nghiên cứu và xử lý các bài toán điều khiển tối ưu mờ, đó là các bài toán mà thông tin về mục tiêu, về ràng buộc và về đối tượng điều khiển là không đầy đủ, không chính xác hoặc không xác định. Tuy nhiên trong khoa học quản lý và hẹp hơn, trong lý thuyết chọn quyết định bài toán này được đặt ra một cách khác, tức là có một cách tiếp cận khác và do đó có một giải pháp khác. Bài toán được đặt ra là : Ký hiệu S là đối tượng quản lý, U= {u1, u2,..., um} tập các giải pháp quản lý; Y={y1, y2, ...,yn} tập các trạng thái của S. Khi ta chọn giải pháp quản lý ui nào đó (cũng là tác động điều khiển) ta cũng không thể khẳng định được hệ S sẽ có trạng thái ra nào với xác suất tương ứng là bao nhiêu, nhưng biết rằng nếu ta chọn giải pháp ui mà hệ S rơi vào trạng thái yj thì ta thu được một mức hiệu quả là cij>0. Bài toán đặt ra là phải lựa chọn giải pháp quản lý nào để có được mức hiệu quả cao nhất với độ tin cậy cao nhất. Đây là bài toán tối ưu mờ, vì thông tin về đối tượng quản lý là không đầy đủ, thông tin về mục tiêu cũng không rõ ràng. Đã có nhiều công trình nghiên cứ và nêu lên những “tiêu chuẩn lựa chọn” khác nhau cho bài toán này. Ta điểm qua các tiêu chuẩn đó. 101
Trường hợp 1: Ta hoàn toàn không biết gì về mức độ chắc chắn (xác suất) hệ S sẽ rơi vào trạng thái nào. Khi ấy có thể xử lý theo các cách sau đây: a)Tiêu chuẩn Laplace Coi xác suất để S rơi vào các trạng thái là như sau và bằng 1/n 1 n Đặt ci=  cij (i=1, m ) n j 1 Ta sẽ chọn giải pháp quản lý ur nếu cr= max ci i b)Tiêu chuẩn Wald Theo tiêu chuẩn này ta giả thiết rằng với mỗi giải pháp quản lý ui, hệ đều rơi vào trạng thái ra “tồi tệ” nhất. Ta sẽ chọn cái tốt nhất trong số những “cái tồi tệ ” đó. Cụ thể là: Đặt hi= min cij (i= 1, m ) j Giải pháp ur được chọn nếu hr = maxh i i c)Tiêu chuẩn Hurwicz Ta chọn một số q  (0,1) ai= minc ij j và đặt: bi= maxcij j ci= qai +(1-q)bi (i=1,...,m) Giải pháp trung gian giữa cách chọn cái tốt nhất trong những cái tồi nhất và chọn cái tồi nhất trong những cái tốt nhất. Khi q-1 thì ta có tiêu chuẩn Wald. d)Tiêu chuẩn Savage Ta lập một ma trận mới (aij) Trong đó: aij= cij- maxc kj (i=1, m ), j= 1, n ) k Và áp dụng tiêu chuẩn Wald cho ma trận này: 102
Đặt: ai= mina ij (i= 1, m ) j Giải pháp ur sẽ được chọn nếu ar= maxai Khó có thể nói rằng tiêu chuẩn nào hợp lý hơn tiêu chuẩn nào. Thông thường người ta áp dụng tất cả các tiêu chuẩn; mỗi tiêu chuẩn chọn ra được một giải pháp. Người ta cho rằng giải pháp nào hội tụ được nhiều tiêu chuẩn hơn, sẽ là “hợp lý hơn”. Trường hợp 2 Giả thiết rằng ta biết các xác xuất để S rơi vào trạng thái yj là pj>0 và n p c j 1 j ij (i= 1, m ) n Ta đặt ci =  p j cij (i= 1, m ) j 1 Giải pháp ur sẽ được chọn nếu cr = max ci 4.4.1 Bài toán tối ưu đa mục tiêu Như đã biết một trong những đặc trưng của hệ thống lớn và phức tạp đó là tính “đa mục tiêu”; do đó bài toán tối ưu trong hệ thống lớn thường là các bài toán “tối ưu đa mục tiêu”; đó là tình huống mà ta phải cân nhắc nhiều mục tiêu cùng một lúc khi lựa chọn phương án cuối cùng. Trong thực tế “hầu như không bao giờ” có một phương án cuối cùng. Trong thực tế “hầu như không bao giờ” có một phương án tốt nhất về mọi phương diện, nghĩa là về mọi mục tiêu nó đều tốt hơn tất cả các phương án khác. Điều này dễ hiểu vì trong số các mục tiêu đề ra, có những mục tiêu tương thích với nhau, nhưng cũng có những mục tiêu không tương thích với nhau, nghĩa là sự tốt lên của mục tiêu này lại kéo theo sự tồi đi của mục tiêu khác. Phương án tốt nhất về mọi phương diện, được gọi là “phương án lý tưởng” phương án này không thuộc miền xác định của bài toán; tức là không có trong thực tế. Người ta coi nó như 1 điểm trong không gian các hàm mục tiêu để từ đó quan sát và ước lượng xem các phương án chấp nhận được của bài toán “gần” hay “xa” vị trí này theo một ma trận nào đó . Một cách khái quát bào toán tối ưu đa mục tiêu đặt ra như sau: Cho F(x)=(f1(x), f2(x),..., fm(x)) xác định trên X  Rn 103
Tìm x*  X sao cho F(x*)= min F(x) hay F(x*)= max F(x) x X xX 4.4.2 Tìm tập Pareto Giả sử fi(x)= xi (i=1,2,...,m) . D là tập compac và x0  D. Với mỗi x  D ta đặt: Dx = {y  D:y  x} Và x *i =sup{xi: x  D x } 0 Khi đó điểm x*=( x 1* ,.., x *n )  Rn gọi là điểm lý tưởng đối với xn. Nói chung x*  D sao cho: 1) x1  x0 2) x1 gần x* nhất có thể được 3) x1 là điểm Pareto của D. 0 Mức độ gần x* của x1 đo bởi hàm thuộc d xx* : Dx 0 →[0,1] 0 xi  xi0 Với d xx* (x)= min iI xi*  xi0 I x = {i: x 0i
Một vài phương pháp thông dụng: a)Thỏa hiệp dần từng bước - Mỗi mục tiêu đề ra 1 mức tối thiểu nào đó: fi(x)  f i (i=1.m ) Đặt P1={x  P: xi  f i ; i=1.m } Nếu p1  Ø. Thuật toán kết thúc khi tập P được thu nhỏ dần đến một mức cho phép nào đó. Trong ví dụ đã nêu ở trên , thu tục thường thấy có thể như sau: A(a1,a2) x2 A1 x* B1 f2 f1 B(b1,b2) 0 x1 Hình 4.3: Thỏa hiệp dần từng bước 1 1 f1 = (a1 + b1) f2 = (a2 + b2) 2 2 f1 và f 2 có ý nghĩa như một mức trung bình. Sau bước này P1 là các điểm trên cung A1B1 và quá trình cứ thế tiếp diễn cho đến khi nào cung AkBk <  nào đó. b)Tìm điểm gần lý tưởng nhất Tức là tìm x  P sao cho:  ( x ,x*)   (x,x*) xP Trong đó: m  2 (x,x*)=  ( xi  xi* ) 2 i 1 105
Trong đó ví dụ trên thì x là điểm tiếp xúc giữa cung AB với đường tòn tâm x*(với bán kính thích hợp) x2 A x* x B 0 x1 Hình 4.4: Điểm gần lý tưởng nhất c)Phối hợp cả 2 phương pháp trên Ban đầu người ta thỏa hiệp dần từng bước . Đến bước k ta tìm được tập tối ưu Pareto Pk (đã được thu gọn sau k bước). Từ Pk ta tìm trên Pk một điểm gần điểm gần điểm lý tưởng x*k và sau đó tìm trên Pk một điểm gần điểm lý tưởng x*k nhất; để coi nó là phương án tối ưu của bài toán. 4.5 Tối ưu đa mục tiêu của một hệ phân cấp Trong quản lý nền kinh tế quốc dân, ta thường gặp bài toán sau đây: Có một hệ S gồm n phân hệ (cấp 1) S1, S2, ...,Sn. Hệ S và mỗi phân hệ đều có mục tiêu riêng của mình. Hãy tìm một giải pháp ”quản lý tối ưu” cho tất cả các mục tiêu đó. Ví dụ như cần phân phối 1 cách tối ưu một nguồn lực (tài nguyên hoặc tài chính) nào đó cho các đối tượng trên: Đứng trên góc độ toàn bộ hệ thống S; cơ quan quản lý muốn dự trữ một số nguồn lực “đủ an toàn” cho công tác quản lý của mình nghĩa là đủ để ứng phó với những “tai biến” có thể xảy ra đối với toàn hệ thống, hoặc đủ để điều chỉnh khi thấy có những bất hợp lý giữa các hệ con. Còn mỗi hệ con lại có mục tiêu riêng của mình nên luôn có mong muốn có một nguồn lực tối đa có thể được. Vậy giải pháp tối ưu là gì? Trước hết cần thấy sự khác nhau cơ bản giữa bài toán này với bài toán đặt ra trong mục 4.4. Trong lý thuyết quyết định bào toán trong mục 4.4 là bài toán có “một chủ thể quyết định” và “đa mục tiêu” để so sánh và lựa chọn phương án. Sự 106