Các thuật toán giải bài tập quy hoạch tuyến tính đa mục tiêu và ra quyết định nhóm cho hệ hỗ trợ ra quyết định quy hoạch và cân đối quỹ đất

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

999
lượt xem 238
download

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

Tài liệu tham khảo Các thuật toán giải bài tập quy hoạch tuyến tính đa mục tiêu và ra quyết định nhóm cho hệ hỗ trợ ra quyết định quy hoạch và cân đối quỹ đất - PGS.TS. Nguyễn Hải Thanh , khoa Công nghệ thông tin trường ĐH Nông Nghiệp Hà Nội

Chủ đề:

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

Lưu

Nội dung Text: Các thuật toán giải bài tập quy hoạch tuyến tính đa mục tiêu và ra quyết định nhóm cho hệ hỗ trợ ra quyết định quy hoạch và cân đối quỹ đất

Trư ng i h c Nông nghi p Hà N i Khoa Công ngh thông tin PGS.TS. NGUY N H I THANH CÁC THU T TOÁN GI I BTQHTT A M C TIÊU VÀ RA QUY T NH NHÓM cho h h tr ra quy t nh quy ho ch và cân i qu t HÀ N I, THÁNG 10 NĂM 2008 http://www.ebook.edu.vn 1
I. KHÁI NI M V H H TR RA QUY T NH 1.1. Quy trình ra quy t nh ã có nhi u sơ ư c phát tri n mô t quy trình ra quy t nh c a con ngư i. Ph bi n nh t l à s ơ ba giai o n: tri th c, thi t k và ch n l a. y hơn, pha tri n khai ư c thêm vào như là m t s m r ng cho sơ trên (trích d n theo Mora và c ng s , 2003). Trong pha tri th c, ngư i ra quy t nh quan sát th c t , có ư c hi u bi t v v n ang kh o sát ho c là các cơ h i m i cũng như các òi h i cho ch t lư ng t ng th và ch t lư ng thông tin c n thi t nh m xác nh rõ v n . pha thi t k , ngư i ra quy t nh phát tri n m t b n mô t và phác ho mô hình có th ki m tra m t cách h th ng quá trình khám phá và gi i quy t v n . Pha thi t k bao g m vi c phát sinh các tiêu chu n quy t nh và các phương án quy t nh, xác nh các s ki n không ki m soát ư c có liên quan cũng như mô t các quan h gi a tiêu chu n, phương án và s ki n. Pha thi t k cũng s d ng các mô hình x lí nh lư ng ánh giá logic các phương án ư c mô t và sinh ra các hành ng g i ý chuy n sang pha ch n l a quy t nh. Trong pha ch n l a, ngư i ra quy t nh s ph i cân nh c các phân tích và các ánh giá v các quy t nh, ánh giá các k t qu hành ng ra quy t nh, xác nh tin c y trong các quy t nh, xây d ng k ho ch tri n khai, và b o m t các ngu n l c c n thi t trư c khi th c thi k ho ch. Sau khi l a ch n cu i cùng (quy t nh cu i cùng) ư c th c hi n, ngư i ra quy t nh nên quan sát k t qu th c t và ghi nh n khâu nào phù h p ho c chưa phù h p, theo các pha c a quy trình ra quy t nh là tri th c, thi t k , ch n l a, và tri n khai. K t qu u ra s có ư c sau khi ch n l a cu i cùng ư c tri n khai. 1.2. Ki n trúc c a m t h h tr quy t nh Khái ni m v ki n trúc c a m t h h tr quy t nh ư c hi u khá a d ng và khác nhau tùy theo t ng tác gi . Theo Power (trích d n theo Mora và c ng s , 2003), h h tr quy t nh bao g m b n thành ph n chính: giao di n ngư i s d ng, cơ s d li u, các mô hình và công c phân tích, thành ph n cu i cùng là ki n trúc và m ng c a h h tr quy t nh. Còn Marakas l i xu t m t ki n trúc g m năm thành ph n riêng bi t: H th ng qu n lí d li u, h th ng qu n lí m u, b máy tri th c, giao di n ngư i s d ng và ngư i s d ng (trích d n theo Mora và c ng s , 2003). Hi n nay, có nhi u h th ng thông tin ã ư c phát tri n ưa ra s h tr cho ngư i s d ng trong các bư c c a quy trình ra quy t nh (Nguy n Khang, 2004). D a vào ch c năng h tr c a các h th ng ó Manuel Mora và c ng s , 2003, ã ưa ra cách phân lo i như sau: H h tr quy t nh (DSS), H th ng x lí thông tin (EIS), H cơ s tri th c (KBS), H máy h c (MLS), H tăng cư ng tính sáng t o (CES). M i h th ng trên s góp ph n gi i quy t m t s khâu nh t nh trong quy trình ra quy t nh. Vi c tích h p ư c các h th ng ó v i nhau là gi i pháp t t nh m t o ra m t h h tr ra quy t nh hoàn ch nh. Trong m t h h tr ra quy t nh, d li u bài toán có th có t ngu n bên ngoài ho c là ngu n bên trong h th ng. tr giúp quy trình ra quy t nh thì d li u ó ph i ư c nh nghĩa, lưu tr và ghi nh n, ư c truy c p và bi u di n. Data warehousing s h tr lưu tr , truy c p và báo cáo cho ơn gi n hơn, trong khi data mining óng vai trò h tr bi u di n thông tin. H th ng x lí thông tin EIS áp ng ư c các yêu c u này t t hơn h h tr ra quy t nh DSS thông qua vi c nh n và lưu tr d li u bài toán t c ngu n bên trong và ngu n bên ngoài. EIS s d ng các mô hình th ng kê mô t t ch c d li u, các mô hình th ng kê ho c mô hình toán h c khác dùng khai phá d li u. Ngư i ra quy t nh s d ng máy tính phân tích và khai phá d li u, k t qu ư c ưa ra dư i d ng các báo cáo tr ng thái, báo cáo luy n và các tham s ki n ngh . H th ng thông tin a lí GIS là m t d ng c a h th ng EIS t p trung vào vi c truy c p d li u và báo cáo trong nh ng bài toán liên quan n http://www.ebook.edu.vn 2
không gian. Các k thu t và hi u bi t chuyên môn v m t lĩnh v c nào ó cũng s r t c n thi t nh n d ng, tính toán và gi i quy t nhi u v n quy t nh ph c t p ho c các v n l a ch n cơ h i. Th c t là kh năng chuyên môn ó l i có ư c nhi u chuyên gia bên ngoài t ch c. H th ng cơ s tri th c KBS s giúp cho quá trình thu th p các tri th c t bên ngoài m t cách hi u qu . Nói cách khác, h th ng cơ s tri th c tr c ti p h tr pha thi t k và pha ch n l a trong quy trình h tr ra quy t nh. Do h h tr ra quy t nh là m t quy trình liên t c và thư ng xuyên, vi c áp d ng h th ng máy h c MLS s giúp h h tr ra quy t nh thư ng xuyên ư c thay i, c p nh t (xem thêm Recio và cs, 2003; Matthews và cs, 1999). 1.3. Thi t k tiêu chu n ra quy t nh và các phương án quy t nh Các quy trình ra quy t nh s d ng các phương pháp khác nhau trong vi c thi t k và xây d ng các tiêu chu n quy t nh cũng như các phương án quy t nh. Có th hi u tiêu chu n ra quy t nh hay phương án quy t nh chính là m t b giá tr c a các bi n quy t nh xi, v i i = 1, 2, …, n, tho mãn (các) m c tiêu t ra m t cách t t nh t trong các i u ki n cho phép c a th c t . Trư c ây và cũng như hi n nay, bài toán quy ho ch tuy n tính (BTQHTT) ư c s d ng r t r ng rãi thi t k các tiêu chu n ra quy t nh trong nhi u lĩnh v c qu n lí và công ngh , c bi t trong các v n qu n lí và quy ho ch t ai. BTQHTT có d ng t ng quát như sau: Max (Min) z = c1x1 + c2x2 + .... + cnxn v i các i u ki n ràng bu c a11x1 + a12x2 + ... + a1nxn Θ b1 a21x1 + a22x2 + ... + a2nxn Θ b2 ... am1x1 + am2x2 + ... + amnxn Θ bm x1 Θ 0, x2Θ 0, ..., xn Θ 0. Trong ó ký hi u Θ có th hi u là ≤ , ≥ ho c = i v i các ràng bu c. iv i iu ki n v d u c a các bi n Θ 0 có th hi u là ≥ 0, ≤ 0 ho c có d u tuỳ ý. BTQHTT ch có úng m t m c tiêu, các m c tiêu khác (n u có) u cho dư i d ng các i u ki n ràng bu c. Có r t nhi u thu t toán gi i BTQHTT, nhưng thu t toán hai pha là thu t toán i n hình và ư c áp d ng r ng rãi nh t. Trong nhi u trư ng h p các mô hình toán h c, trong ó có bài toán quy ho ch tuy n tính a m c tiêu có th ư c áp d ng. Trong các bài toán công ngh , qu n lí... n y sinh t th c t , chúng ta thư ng ph i xem xét t i ưu hoá ng th i m t lúc nhi u m c tiêu. Vi c gi i các bài toán t i ưu a m c tiêu, t c là tìm ra m t phương án kh thi t t nh t theo m t nghĩa nào ó, th c ch t chính là m t bài toán ra quy t nh. Bài toán quy ho ch tuy n tính (BTQHTT) a m c tiêu v i p m c tiêu có d ng sau: Max (Min) z = ci1x1 + ci2x2 + .... + cinxn , i =1, 2, …, p v i các i u ki n ràng bu c a11x1 + a12x2 + ... + a1nxn Θ b1 a21x1 + a22x2 + ... + a2nxn Θ b2 ... am1x1 + am2x2 + ... + amnxn Θ bm x1 Θ 0, x2Θ 0, ..., xn Θ 0. http://www.ebook.edu.vn 3
M t s phương pháp gi i BTQHTT a m c tiêu ã ư c công b bao g m: phương pháp tìm nghi m có kho ng cách ng n nh t n nghi m lí tư ng, phương pháp gi i theo dãy các m c tiêu, phương pháp ngư i − máy c a Geoffrion, Dyer và Fienberg (xem Steuer, 1986), phương pháp tho d ng m tương tác c i biên (Nguy n H i Thanh, 2008). 1.4. Thi t k cơ ch ch n l a b ng ra quy t nh nhóm Ra quy t nh nói chung và ra quy t nh nhóm nói riêng là m t v n r t quan tr ng và có ng d ng r ng rãi trong nhi u lĩnh v c kinh t , qu n lí và xã h i. V m t khoa h c, ây là m t v n luôn có nhi u v n m c n ti p t c nghiên c u tr l i các câu h i: th nào là m t quy t nh t t và m t quy trình như th nào giúp ch n l a ư c m t quy t nh t t. M t quy trình ra quy t nh nhóm t ng quát bao g m ba bư c cơ b n: − Bư c 1: T ng cá th trong nhóm ph i xác nh các hàm giá tr th t / hay hàm th a d ng / ho c quan h ưu tiên (rõ / m ) tương ng xác nh trên t p các phương án / l a ch n (xem Zimmermann, 1986). − Bư c 2: Xác nh hàm giá tr th t / hay hàm th a d ng / ho c quan h ưu tiên (rõ / m ) c a nhóm d a trên vi c k t h p các giá tr th t / hay giá tr th a d ng / quan h ưu tiên bư c trư c. − Bư c 3: N u các ý ki n c a m i cá th trong nhóm ã ư c th ng nh t (consensus) ho c ã c m sát nhau (cluster), ã ư c hoà hoãn ch p nh n ư c (compromise) ho c ã có s ông th ng th (majority vote) ho c ã ư c ngư i lãnh o quy t nh (decision by leader) ho c ã ư c tr ng tài thuy t ph c (arbitration) thì quá trình d ng v i s ch n l a quy t nh thích h p. N u trái l i, sau khi trao i m t s thông tin c a các cá th hay c a toàn nhóm, tr v bư c 1. Có nhi u quy trình ra quy t nh nhóm như phương pháp Delphi, phương pháp LOWA s d ng toán t tích h p ngôn ng … Trong nghiên c u này chúng tôi xu t quy trình ra quy t nh Delphi c i biên x lí và t ng h p ý ki n chuyên gia nh m ánh giá s p h ng các phương án t i ưu c a BTQHTT a m c tiêu (Nguy n H i Thanh, 2008). Ngoài ra, vi c c i ti n phương pháp LOWA cũng ư c chúng tôi nghiên c u xu t. 1.5. Nh n xét v t m quan tr ng c a các thu t toán Phân tích có tính ch t t ng h p trên ây cho th y các thành ph n t o nên m t h h tr ra quy t nh. Hai thành ph n r t quan tr ng chính là: − Thu t toán gi i BTQHTT m t m c tiêu và a m c tiêu. − Thu t toán ra quy t nh nhóm hay còn g i là ra quy t nh t p t h . Trong các h h tr ra quy t nh quy ho ch và cân i qu t, các thu t toán trên giúp tìm ra các phương án h p lí và ra quy t nh úng n ch n l a ra m t (ho c) m t s phương án t t nh t. http://www.ebook.edu.vn 4
II. THU T TOÁN GI I BTQHTT M T M C TIÊU VÀ A M C TIÊU 2.1. Thu t toán ơn hình hai pha gi i BTQHTT m t m c tiêu n z = ∑ cj xj → Min/ Max Xét bài toán g c: j=1 v i các ràng bu c (gi s các bi n u không âm)  ∑ a x ≤ b ( i = 1, m ) n 1  j = 1 ij j i n  ∑ a ij x j ≥ b i ( i = m 1 + 1, m 1 + m 2 )  j=1   ∑ a x = b ( i = m + m + 1, m + m + m ) n 1 2 1 2 3  j = 1 ij j i   x j ≥ 0 ( j = 1, n + m 1 + m 2 + m 3 )  Bư c 1: - Nh p d ng bài toán Min / Max và ưa các bi n v d ng không âm. - Nh p t ng s ràng bu c m bao g m các ràng bu c mang d u: ≤ (m1 ràng bu c) , ≥ (m2 ràng bu c) và = (m3 ràng bu c). - Nh p s bi n: n bi n. - Nh p véc tơ h s hàm m c tiêu: C = [ c1, c2, . . ., cn ]. - Nh p véc tơ h s v ph i: b = [ b1, b2, . . ., bm ]. - Nh p ma tr n h s ràng bu c: A = [ai j ]m x n. Bư c 2: ưa bài toán v d ng chính t c. - ưa BTQHTT v d ng Max - Thêm các bi n bù: xn+i, i = 1, m 1 , Bi n bù thi u: m1 bi n Bi n bù th a: m2 bi n xn+ m1+p, p = 1, m 2 , Bi n gi : m2 + m3 bi n xn+m1+m2+q, q = 1,m 2 + m 3 . N u m2 + m3 = 0, chuy n sang bư c 4. N u m2 + m3 ≠ 0, gi i bài toán theo hai pha b ng cách chuy n sang bư c 3. Bư c 3: Pha th nh t. Xây d ng và gi i bài toán ph : m 2 + m3 ∑ ω= xm1 + m2+q+n → Min q v i các ràng bu c http://www.ebook.edu.vn 5
 m1 + 2*m 2 + m3 ∑ a ijx j = bi (i = 1, m1 + m 2 + m3 )    j=1   x j ≥ 0 ∀j = 1, (n + m1 + 2 * m 2 + m3 ).  Bt u Kh i t o, i d u, thêm bi n bù, bi n gi Y Có bi n gi pha I ? Gi i pha I pha II N Gi i pha II Tính ∆k Tính ∆k N ∃k,∆k 0 Tính Max ∆ k , ∆k
K t thúc pha 1 có th x y ra ba trư ng h p sau ây: − Phương án t i ưu không có bi n gi , l y ó làm phương án xu t phát, thay l i h s hàm m c tiêu, lo i tr các c t bi n gi và sang bư c 4. − Phương án t i ưu có bi n gi khác 0 thì bài toán t i ưu không có phương án. D ng. − Phương án t i ưu có ch a bi n gi nhưng bi n gi b ng 0, xoá các dòng ch a các bi n gi này, thay l i h s hàm m c tiêu, lo i tr các c t bi n gi và sang bư c 4. Bư c 4: Pha th 2. Gi i bài toán g c v i phương án xu t phát tìm ư c b ng phương pháp ơn hình. Bư c 5: In k t qu . Sơ thu t gi i cho BTQHTT g c là bài toán Max ư c cho trên hình II.1. 2.2. Thu t gi i ơn hình gi i BTQHTT d ng chính t c Thu t toán hai pha trên ây ã s d ng m t th t c gi i BTQHTT d ng chính t c. Sau ây là phát bi u v BTQHTT d ng chính t c và thu t gi i ơn hình: Max z = c1x1 + c2x2 + ... + cnxn + cn+1xn+1 + ... + cn+mxn+m v i các ràng bu c a11x1 + a12x2 + ... + a1nxn + xn+1 = b1 a21x1 + a22x2 + ... + a2nxn + xn+2 = b2 ... am1x1 + am2x2 + ... + amnxn + xn+m = bm x1, x2, ..., xn, xn+1, ..., xn+m ≥ 0 Bư c kh i t o – Nh p các h s hàm m c tiêu c, ma tr n ràng bu c A và các h s v ph i b. – t d1 = cn+1, ..., dm = cn+m , t c là cB = (d1, ..., dm)T. – t ch s bi n cơ s : r(1) = n + 1, ..., r(m) = n + m. – Gán xr(i) = bi , i = 1, m . – t flag = 2. Các bư c l p Bư c 1: – Tính cTx = z = d1xr(1) + ... + dmxr(m). m – Tính zj = ∑ a pjd p , ∀j = 1, n + m . p =1 – Tìm ∆ = [∆N , ∆B] = [ cT – cT B–1N, cT – cT B–1B], trong ó ∆B = 0. Như v y ∆j = cj – zj, N B B B m v i zj = ∑ a pjd p , ∀j ∈ N và ∆j = cj – zj = 0, ∀j ∈ B, (t c là zN = cT B–1N và zB = cT B–1B). B B p =1 Bư c 2: N u t n t i ch s j ∈ N sao cho ∆j > 0 thì th c hi n th t c xoay. – Xác nh c t xoay: ch n c t xoay s ng v i m t ch s j có tính ch t ∆j > 0. Thông thư ng ch n j ng v i ∆j > 0 l n nh t, ho c ch n ng u nhiên. – Xác nh hàng xoay q theo quy t c t s dương bé nh t: x r (q )  x r (i)  = Min   , ∀ a is > 0 . a qs  a is  Trong trư ng h p không t n t i ais > 0, t flag = 0 và chuy n sang bư c k t thúc. http://www.ebook.edu.vn 7
– Xác nh ph n t xoay aqs. – Tính l i ( chuy n sang b ng ơn hình m i): bq := bq/aqs, aqj := aqj/aqs, ∀j . ∀ i ≠ q tính l i bi := bi – bqais và aij = aij – aqj ais, ∀j. – t l i ch s các bi n cơ s : r(q) := s, dq := cs, và xr(i) = bi , i = 1, m . – Quay v bư c 1. Bư c 3: N u ∆j ≤ 0, ∀j ∈ N thì t flag = 1 và chuy n sang bư c k t thúc. Bư c k t thúc Ghi l i d li u u vào c a BTQHTT và k t qu cu i cùng. N u flag = 0 thì k t lu n BTQHTT có hàm m c tiêu không b ch n trên. Còn n u flag = 1 thì k t lu n BTQHTT có phương án t i ưu ã tìm ư c. D ng. 2.3. Thu t toán tho d ng m tương tác c i biên gi i BTQHTT a m c tiêu thi t k các phương án quy t nh cho mô hình quy ho ch tuy n tính a m c tiêu có th áp d ng m t s phương pháp, trong ó có phương pháp tho d ng m c i biên do chúng tôi xu t. Sau ây là thu t gi i áp d ng phương pháp này. Bư c kh i t o i) Nh p s li u cho các hàm m c tiêu tuy n tính zi (i = 1, 2, ..., p) và m i u ki n ràng bu c. Gi i BTQHTT cho t ng m c tiêu zi (i = 1, 2, ..., p) v i mi n ràng bu c D ư c thu ư c các phương án t i ưu x1, x2, ..., xp (n u v i xác nh b i m ràng bu c ban u m t m c tiêu nào ó bài toán không cho phương án t i ưu thì c n xem xét ch n h s a l i các i u ki n ràng bu c ban u). ii) Tính giá tr các hàm m c tiêu t i p phương án x1, x2, ..., xp và l p b ng pay−off. z iB z iw c a m c tiêu zi (i =1, 2,..., p), v i ziB = Xác nh giá tr c n trên và giá tr c n dư i w zi(xi) và z i = Min {zi(xj): j = 1, 2, …, p}. nh các hàm tho d ng m µ1(z1), µ2(z2), ..., µp(zp) cho t ng m c tiêu theo iii) Xác zi − ziw công th c: µi (z i ) = B , i = 1, 2, ..., p. z i − z iw a i( k ) z iB t: SP = {x1, x2, ..., xp}, k :=1 và iv) = v i i = 1, 2, ..., p. Các bư c l p (xét bư c l p th k) Bư c 1: i) Xây d ng hàm tho d ng t h p t các hàm tho d ng trên: u = w1µ1(z1) + w2µ2(z2) + ... + wpµp(zp) → Max Trong ó: w1, w2, ..., wp là các tr ng s (ph n ánh t m quan tr ng c a t ng hàm tho d ng trong thành ph n hàm tho d ng t h p) ư c ngư i gi i l a ch n tho mãn i u ki n: w1 + w2 +... + wp = 1 và 0 ≤ w1, w2, ..., wp ≤ 1. ii) Gi i BTQHTT v i hàm tho d ng t h p v i m ràng bu c ban u và p ràng bu c ( k) b sung zi(x) ≤ a i , i = 1, 2, ..., p, tìm ư c phương án t i ưu c a bư c l p th k là x(k) và giá tr c a các hàm m c tiêu zi cũng như c a các hàm tho d ng µi(zi) (v i i =1, 2, ..., p). Bư c 2: i) N u µmin = Min {µi(zi): i = 1, 2, ..., p} bé hơn m t ngư ng t nào ó (t ư c l a ch n trong o n [0, 1] và có th ư c s a ch nh l i trong quá trình gi i bài toán) thì phương án tìm ư c x(k) không ư c ch p nh n. Trong trư ng h p trái l i, phương án x(k) ư c ch p nh n vào t p SP các phương án t i ưu Pareto (t i ưu Pareto y u) c n xem xét n u x(k) ∉ SP. http://www.ebook.edu.vn 8
ii) N u ngư i gi i bài toán còn mu n ti p t c m r ng t p SP thì t k := k + 1. N u k > L1 ho c s l n bư c l p liên ti p t p SP không ư c m r ng vư t quá L2 a i( k ) z iB v i i = 1, 2, ..., p và ch n ng u nhiên (L1 và L2 ư c ngư i gi i tùy ch n) thì t = a (hk ) ∈ ( z h , z B ]. w m t ch s h ∈ {1, 2, ..., p} t l i giá tr c t h Quay v bư c 1. iii) N u ngư i gi i bài toán không mu n m r ng t p SP thì chuy n sang bư c 3. Bư c 3: i) Lo i kh i t p SP các phương án b tr i. ii) K t thúc. 2.4. Trư ng h p kh o sát 1 Bài toán quy ho ch s d ng t s n xu t nông nghi p trên a bàn huy n Tam Nông BTQHTT a m c tiêu có t t c 44 bi n quy t nh v i ba m c tiêu c n c c i hoá là: T ng thu nh p Z1 = X_1_2_5*10941 + X_1_2_6*6239 + X_2_1_3*27746 + X_3_1_1*14051 + X_3_1_2*11914 + X_3_2_3*27746 + X_3_2_4*12854 + X_3_2_5*10941 + X_3_2_6*6239 + X_4_1_1*14051 + X_4_2_2*11914 + X_4_2_3*27746 + X_4_2_4*12854 + X_4_2_5*10941 + X_4_2_6*6239 + X_5_2_1*14051 + X_5_1_2*11914 + X_5_2_3*27746 + X_5_2_4*12854 + X_5_2_5*10941 + X_5_2_6*6239 + X_6_2_1*14051 + X_6_2_2*11914 + X_6_2_4*12854 + X_7_2_1*14051 + X_7_2_2*11914 + X_7_2_4*12854 + X_7_2_5*10941 + X_7_2_6*6239 + X_8_2_1*14051 + X_8_2_2*11914 + X_8_2_3*27746 + X_8_2_4*12854 + X_9_2_1*14051 + X_9_2_2*11914 + X_9_2_3*27746 + X_9_2_4*12854 + X_9_2_6*6239 + X_10_2_1*14051 + X_10_2_2*11914 + X_10_2_3*27746 + X_10_2_4*12854 + X_10_2_5*10941 + X_10_2_6*6239 T ng m c thích h p l n nh t Z2 = X_2_1_3*1 + X_3_1_1*1 + X_3_1_2*1 + X_4_1_1*1 + X_5_1_2*1 T ng hi u su t ng v n Z3 = X_1_2_5*1.69 + X_1_2_6*2.33 + X_2_1_3*1.82 + X_3_1_1*0.88 + X_3_1_2*0.87 + X_3_2_3*1.82 + X_3_2_4*0.93 + X_3_2_5*1.69 + X_3_2_6*2.33 + X_4_1_1*0.88 + X_4_2_2*0.87 + X_4_2_3*1.82 + X_4_2_4*0.93 + X_4_2_5*1.69 + X_4_2_6*2.33 + X_5_2_1*0.88 + X_5_1_2*0.87 + X_5_2_3*1.82 + X_5_2_4*0.93 + X_5_2_5*1.69 + X_5_2_6*2.33 + X_6_2_1*0.88 + X_6_2_2*0.87 + X_6_2_4*0.93 + X_7_2_1*0.88 + X_7_2_2*0.87 + X_7_2_4*0.93 + X_7_2_5*1.69 + X_7_2_6*2.33 + X_8_2_1*0.88 + X_8_2_2*0.87 + X_8_2_3*1.82 + X_8_2_4*0.93 + X_9_2_1*0.88 + X_9_2_2*0.87 + X_9_2_3*1.82 + X_9_2_4*0.93 + X_9_2_6*2.33 + X_10_2_1*0.88 + X_10_2_2*0.87 + X_10_2_3*1.82 + X_10_2_4*0.93 + X_10_2_5*1.69 + X_10_2_6*2.33 Các ràng bu c c a bài toán bao g m: Các ràng bu c v di n tích X_1_2_5*1 + X_1_2_6*1 = 4680.41 X_2_1_3*1 = 2135.53 X_3_1_1*1 + X_3_1_2*1 + X_3_2_3*1 + X_3_2_4*1 + X_3_2_5*1 + X_3_2_6*1 = 319.36 X_4_1_1*1 + X_4_2_2*1 + X_4_2_3*1 + X_4_2_4*1 +X_4_2_5*1 + X_4_2_6*1 = 640.3 X_5_2_1*1 + X_5_1_2*1 + X_5_2_3*1 + X_5_2_4*1 + X_5_2_5*1 + X_5_2_6*1 = 188.67 X_6_2_1*1 + X_6_2_2*1 + X_6_2_4*1 = 3.08 X_7_2_1*1 + X_7_2_2*1 + X_7_2_4*1 + X_7_2_5*1 + X_7_2_6*1 = 575.61 http://www.ebook.edu.vn 9
X_8_2_1*1 + X_8_2_2*1 + X_8_2_3*1 + X_8_2_4*1 = 11.93 X_9_2_1*1 + X_9_2_2*1 + X_9_2_3*1 + X_9_2_4*1 + X_9_2_6*1 = 597.64 X_10_2_1*1 + X_10_2_2*1 + X_10_2_3*1 + X_10_2_4*1 + X_10_2_5*1 + X_10_2_6*1 = 1163.15 Các ràng bu c tương quan t l X_3_1_1*1 + X_4_1_1*1 + X_5_2_1*1 + X_6_2_1*1 + X_7_2_1*1 + X_8_2_1*1 + X_9_2_1*1 + X_10_2_1*1 ≤ 3499.74 X_3_1_2*1 + X_4_2_2*1 + X_5_1_2*1 + X_6_2_2*1 + X_7_2_2*1 + X_8_2_2*1 + X_9_2_2*1 + X_10_2_2*1 ≤ 3499.74 X_2_1_3*1 + X_3_2_3*1 + X_4_2_3*1 + X_5_2_3*1 + X_8_2_3*1 + X_9_2_3*1 + X_10_2_3*1 ≤ 5056.58 X_3_2_4*1 + X_4_2_4*1 + X_5_2_4*1 + X_6_2_4*1 + X_7_2_4*1 + X_8_2_4*1 + X_9_2_4*1 + X_10_2_4*1 ≤ 3499.74 X_1_2_5*1 + X_3_2_5*1 + X_4_2_5*1 + X_5_2_5*1 + X_7_2_5*1 + X_10_2_5*1 ≤ 7567.5 X_1_2_6*1 + X_3_2_6*1 + X_4_2_6*1 + X_5_2_6*1 + X_7_2_6*1 + X_9_2_6*1 + X_10_2_6*1 ≤ 8165.14 Ràng bu c v m c s d ng lao ng X_1_2_5*401 + X_1_2_6*371 + X_2_1_3*860 + X_3_1_1*892 + X_3_1_2*858 + X_3_2_3*860 + X_3_2_4*893 + X_3_2_5*401 + X_3_2_6*371 + X_4_1_1*892 + X_4_2_2*858 + X_4_2_3*860 + X_4_2_4*893 + X_4_2_5*401 + X_4_2_6*371 + X_5_2_1*892 + X_5_1_2*858 + X_5_2_3*860 + X_5_2_4*893 + X_5_2_5*401 + X_5_2_6*371 + X_6_2_1*892 + X_6_2_2*858 + X_6_2_4*893 + X_7_2_1*892 + X_7_2_2*858 + X_7_2_4*893 + X_7_2_5*401 + X_7_2_6*371 + X_8_2_1*892 + X_8_2_2*858 + X_8_2_3*860 + X_8_2_4*893 + X_9_2_1*892 + X_9_2_2*858 + X_9_2_3*860 + X_9_2_4*893 + X_9_2_6*371 + X_10_2_1*892 + X_10_2_2*858 + X_10_2_3*860 + X_10_2_4*893 + X_10_2_5*401 + X_10_2_6*371 ≥ 2500000 i u ki n không âm c a các bi n: ∀ Xi ≥ 0 (i = 1, ...,44). Các giá tr v ph i c a các ràng bu c v di n tích, tương quan t l và m c s d ng lao ng ư c tính toán căn c các s li u i u tra ư c v các ơn v t ai, m c thích h p c a các ơn v t ai theo m c ích s d ng và d báo v nhân l c s n xu t nông nghi p (xem Nguy n H i Thanh, 2008). Áp d ng thu t gi i tho d ng m tương tác s thu ư c các k t qu sau: Bư c kh i t o Khi c c i hoá riêng hàm m c tiêu Z1, s thu ư c phương án v i Z1Max = 199639407.68, Z2 = 2135.53, Z3 = 17622.1157. Khi c c i hoá riêng hàm m c tiêu Z2, s thu ư c phương án v i Z1 = 118973195.5, Z2Max = 3283.86, Z3 = 21257.6844. Khi c c i hoá riêng hàm m c tiêu Z3, s thu ư c phương án v i Z1 = 110565323.94, Z2 = 2135.53, Z3 Max = 22936.0178. Lúc này d a trên thông tin pay−off, các hàm tho d ng m tương ng v i ba m c tiêu ư c xác nh theo công th c: zi − ziw µi (zi ) = , i = 1, 2, 3. ziB − ziw Các bư c l p Hàm tho d ng t h p ư c xây d ng t các hàm tho d ng trên: u = w1µ1(z1) + w2µ2(z2) + w3µ3(z3) → Max. http://www.ebook.edu.vn 10
Trong ó: w1, w2, w3 là các tr ng s (ph n ánh t m quan tr ng c a t ng hàm tho d ng trong thành ph n hàm tho d ng t h p) ư c ngư i gi i l a ch n tho mãn i u ki n: w1 + w2 + w3 = 1 và 0 ≤ w1, w2, w3 ≤ 1. Gi s ngư i s d ng coi vi c t ư c t ng thu nh p l n nh t là quan tr ng nh t, còn các m c tiêu khác ít quan tr ng hơn. Vi c này có th th c hi n ư c b ng cách kích trên menu phía dư i, bên trái Gi i a m c tiêu, sau ó nh p tr ng s cho các hàm m c tiêu: hàm m c tiêu nào quan tr ng hơn thì có tr ng s cao hơn. T ng các tr ng s ph i b ng 1. Ngư i s d ng nh p W1 = 0.8, W2 = 0.1, W3 = 0.1. K t qu thu ư c cho bi t giá tr c a các hàm m c tiêu: Z1 = 199639407.68, Z2 = 2135.53, Z3 = 17622.115. Chúng ta ý k t qu này trùng v i gi i hàm m c tiêu Z1. N u W1 = 0.4, W2 = 0.3, W3 = 0.3. K t qu thu ư c cho bi t giá tr các hàm m c tiêu: Z1 = 157005887.4, Z2 = 3283.86, Z3 = 20370.8957. N u W1 = 0.6, W2= 0.2, W3 = 0.2. K t qu thu ư c cho bi t giá tr các hàm m c tiêu: Z1 = 181719693.44, Z2 = 3283.8, Z3 = 17007.0429. Ngư i s d ng mu n giá tr hàm m c tiêu Z1 nh hơn m t ngư ng nào ó, giá tr này ph i n m trong kho ng Z1Max, Z1Min. Ngư i s d ng ph i nh p giá tr c t cho hàm m c tiêu Z1 n m trong kho ng (110565323.94, 199639407.68), ch ng h n là 180000000. Ch n W1 = 0.4, W2 = 0.3, W3 = 0.3. K t qu gi i bài toán: X_1_2_6 = 4680.41 | X_2_1_3 = 2135.53 | X_3_1_1 = 319.36 | X_4_1_1 = 640.3 | X_5_1_2 = 188.67 | X_6_2_1 = 3.08 | X_7_2_6 = 575.61 | X_8_2_3 = 11.93 | X_9_2_3 = 597.64 | X_10_2_3 = 1163.15 | s[53] = 2537 | s[54] = 3311.07 | s[55] = 1148.33 | s[56] = 3499.74 | s[57] = 7567.5 | s[58] = 2909.12 | s[59] = 22994112.6 | s[60] = 1163.15 | s[61] = 3831721.36 | s[62] = 2135.53 | s[63] = 319.36 | s[64] = 640.3 | s[65] = 188.67 | s[66] = 3.08 | s[67] = 4680.41 | s[68] = 11.93 | s[69] = 597.64 | s[70] = 575.61, các bi n khác có giá tr b ng 0. Giá tr các hàm m c tiêu: Z1 = 157005887.4, Z2 = 3283.86, Z3 = 20370.8957. 2.4. Nh n xét v phương pháp tho d ng m tương tác ây là phương pháp d l p trình, có tác d ng giúp ngư i ra quy t nh ưa ư c các m c tiêu khác nhau v cùng m t thang b c tho d ng (t 0% t i 100%). Do ó phương pháp có ưu i m n i b t là giúp gi i quy t ư c các BTQHTT v i các m c tiêu khác nhau v ơn v o. Ngoài ra, phương pháp cho phép tìm ki m các phương án t i ưu m t cách linh ho t b ng cách s d ng các lát c t b sung. Như v y phương pháp giúp ưa ra ư c nhi u phương án h p lí tăng thêm thông tin cho b máy ra quy t nh. Ch ng h n, trong trư ng h p kh o sát trên ây, phương pháp ã t o ra ư c năm phương án t i ưu (hai phương án ã b lo i do có các phương án khác “tr i” hơn) ưa vào ch n l a. http://www.ebook.edu.vn 11
III. MÔ HÌNH RA QUY T NH T P TH 3.1. Ra quy t nh nhóm Sau khi phát tri n các tiêu chu n quy t nh và phát tri n các phương án quy t nh, pha ti p theo s xây d ng cơ ch ch n l a có th ánh giá ư c các phương án quy t nh ó. Trong trư ng h p m t nhóm / t p th chuyên gia có quy n ra quy t nh, c n thi t l p ư c các quy trình ra quy t nh t p th (hay còn g i là ra quy t nh nhóm) h p lí , m t m t i t i ư c s th ng nh t i v i quy t nh cu i cùng, m t khác l i phát huy ư c tính dân ch và tri th c chuyên môn c a m i cá nhân trong nhóm. Ra quy t nh nhóm (Group Decision Making) là m t v n r t quan tr ng và có ng d ng r ng rãi trong nhi u lĩnh v c kinh t , qu n lí và xã h i. ây là m t lĩnh v c nghiên c u cơ b n và ng d ng ã xu t hi n t r t s m, nhưng luôn có tính c p thi t và tính m , òi h i nhi u công s c nghiên c u c a các nhà khoa h c và qu n lí. c bi t ngày nay, v i s phát tri n c a Lí thuy t t p m và h th ng m , ra quy t nh nhóm l i có nh ng cơ s m i phát tri n và ng d ng. M t quy trình ra quy t nh nhóm bao g m ba bư c cơ b n như ã trình bày m c 1.4. Nói m t cách ng n g n, ưa ra quy t nh ch n l a phương án trong các các phương án c a t p A = {a, b, c,…}, m i thành viên c a nhóm c n xác l p hàm th a d ng c a mình s p th t các phương án, mà d a vào ó hàm th a d ng c a c nhóm s ư c t h p. Quy t nh ư c ưa ra d a vào hàm tho d ng t h p này sau m t s bư c l p các cá th có th s a ch nh l i các ánh giá c a mình. Ch ng h n, ch n l a m t trong s n phương án c a t p A = {x1, x2, …, xn} b ng vi c ra quy t nh nhóm v i N chuyên gia, có th th c hi n quy trình ra quy t nh nhóm sau: Bư c 1. Xác nh hàm th a d ng Up, cho t ng cá th p = 1,…, N, v i Up∈ [0,1] ∀ p. [ ] 1 1 + U ( x i ) − U ( x j ) ho c tính theo công th c rij Tính rij theo m t trong hai công th c rij = 2 = U(xi)/ [U(xi)+U(xj)] , ∀i, j xác nh tr i hơn /hay kém hơn c a phương án (t p h p các giá tr rij cũng ng th i xác nh m t quan h ưu tiên m ). D th y rij ∈ [0,1] ∀ i, j. 1N P ∑ rij Bư c 2. Tính r = G xác l p quan h ưu tiên m cho c nhóm ( ây là ij N P =1 hàm k t h p trung bình c ng). Bư c 3. Ki m tra n u d u hi u d ng ư c tho mãn thì d ng. Trái l i c n thông báo m t s thông tin giúp các chuyên gia quay v bư c 1 và s a ch nh các giá tr tho d ng c a mình. Trong m t s tài nghiên c u g n ây, chúng tôi áp d ng phương pháp Delphi c i biên ra quy t nh nhóm nh m l a ch n ư c phương án quy t nh h p lí nh t t t p h p các phương án quy t nh ã thi t l p ư c. Cũng có th áp d ng phương pháp DELOWA (xem Nguy n H i Thanh, 2008), tuy nhiên trong chuyên này chúng ta ch c p ch y u t i phương pháp Delphi c i biên. 3.2. Phương pháp Delphi c i biên x lí và t ng h p ý ki n chuyên gia Quy trình ra quy t nh Delphi ã ư c nghiên c u và ng d ng nhi u trong các quy trình ra quy t nh nhóm / t p th (xem Kaufmann và Gupta, 1991; Nguy n H i Thanh, 2006). Trong tài nghiên c u này, chúng tôi xu t quy trình ra quy t nh Delphi c i biên x lí và t ng h p ý ki n chuyên gia nh m: http://www.ebook.edu.vn 12
− T n d ng ư c tri th c c a các chuyên gia trong nhi u lĩnh v c khác nhau, v i các nh n bi t, c m nh n khác nhau v cùng m t v n . − Giúp các chuyên gia cân nh c và xem xét s a ch nh l i các ánh giá mang tính ch quan c a mình. − ưa ra m t quy trình gi khách quan nh m phân c m các ý ki n trong t ng bư c, và làm cho các ý ki n h i t v m t cách ánh giá th ng nh t. So v i thu t toán Delphi g c c a Kaufmann A. và Gupta, 1991, thu t toán Delphi c i biên khác hai i m: − Các chuyên gia s p h ng các phương án b i s m ch không ph i s rõ. i u này làm cho s ánh giá ư c “m m” hơn, th c t hơn. − B ng cách áp d ng phương pháp phân c m d li u, thông tin sau m i bư c l p cung c p cho các chuyên gia không ch bao g m thông tin v i m trung bình c ng toán nhóm c a t ng phương án, mà còn bao g m c i m trung bình (là s m ) trong các l p c m có ch a nhi u ý ki n. i u này giúp cho vi c s a ch nh l i các ánh giá c a t ng chuyên gia trong bư c l p ti p theo ư c thu n l i hơn. Phân c m các d li u s thông thư ng như ã quen bi t trong a s các chuyên ngành nghiên c u hi n nay ư c g i là phân c m d li u rõ (crisp data). Khi thu th p d li u, ta thư ng ti n hành phương pháp ch n m u A g m n cá th . B ng cách nh lư ng hoá các c tính c a các cá th ó, m i cá th s ng v i m t b m s tương ng v i m c tính ư c xem xét. Bài toán phân c m t ra ây là ưa vào m t khái ni m hàm kho ng cách d thích h p nh m ánh giá " g n gũi" gi a các cá th ó, t ó có th xem xét và xu t các phương pháp phân c m / phân lo i phù h p. Gi s ta ã quy t nh phân c m m u A ra l l p. D a trên hàm kho ng cách ã ra, c n tìm ư c phân c m t i ưu c a t p m u A theo m t nghĩa nào ó. Sau ây là hai tiêu chu n quan tr ng, tiêu chu n kho ng cách (tr ng tâm) c c ti u và tiêu chu n bình phương bé nh t thư ng ư c dùng trong th c t . Cho A = { a1, a2, ..., an } g m n cá th , m i cá th là m t véc tơ m chi u ai = (xi1 , xi2 , ..., xim ) ∈ Rm mô t m c tính. G i d là m t kho ng cách (metric) trong A, k ∈ N, 1 < k < n. Tiêu chu n bình phương bé nh t: Gi s C = { C1, C2 , ... Cl } là m t phân ho ch b t kỳ c a t p h p A, ni là s ph n t c a l p Ci = { aij ∈ A / ∀j = 1, n i } trong phân ho ch C. ni 1 ni 2 t l(Ci) = ∑ d (a ij , ai ) ai = ∑ a i j là tr ng tâm c a l p Ci. thì D (C) n j=1 j=1 ni l l = ∑ l (C i ) = ∑ ∑ d 2 (a i j , a i ) . Phân ho ch C* = {C1* , C2* , ..., Cl*} tho mãn D(C*) = min i =1 i = 1 j =1 D(C) ư c g i là phân ho ch t i ưu c a A theo nghĩa bình phương bé nh t. Như v y trong phân ho ch theo tiêu chu n bình phương bé nh t thì phân ho ch t i ưu * C có t ng các bình phương c a t t c các kho ng cách d (kho ng cách Euclidt theo nghĩa thông thư ng) t m i ph n t c a A t i tr ng tâm c a l p (mà nó thu c vào) t giá tr bé nh t (t c là n u xét m t phân ho ch b t kỳ C có cùng s l p l , ta luôn có D(C*) ≤ D(C)). nh nghĩa: Phân ho ch C* = {C1* , C2* , ..., Cl*} ư c g i là phân ho ch v i kho ng cách c c ti u n u ∀aij(*)∈ Ci* thì d(a (ij*) , ai ) ≤ d(a ij , a r ) ∀ r ≠ i. Như v y n u C* là phân ho ch (*) t i ưu theo tiêu chu n kho ng cách c c ti u c a A thì các cá th trong cùng m t l p "g n" v i tr ng tâm c a l p ó hơn tr ng tâm c a l p khác. nh lí: T p các phân ho ch t i ưu theo tiêu chu n kho ng cách c c ti u ch a t p các phân ho ch t i ưu theo tiêu chu n bình phương bé nh t. http://www.ebook.edu.vn 13
Trong th c t , t p m u A thư ng có kích thư c n tương i l n, nên s các phân ho ch g m m t l p c a A cũng r t l n. Vì v y thu t gi i chính xác tìm phân ho ch t i ưu d a trên các tiêu chu n trình bày trên thư ng t ra ít hi u qu . Do ó, ngư i ta thư ng dùng các thu t gi i x p x tìm ra các phân ho ch x p x phân ho ch t i ưu d a trên các tiêu chu n kho ng cách c c ti u và bình phương bé nh t. Thu t gi i x p x tìm phân ho ch “g n t i ưu” Bư c kh i t o − Ch n s l p l và ch n ng u nhiên m t phân ho ch kh i u l C0 = { C1(0), C2(0) , ... , Cl(0) }, l p Ci(0) có ni ph n t , ∑ n i = n. i =1 − Ch n sai s ε dương bé. 0 − Tính D(C ). Ch n bi n m k, b t ut 0 và ch n h ng kmax > 0. Các bư c l p (bư c l p th k) 1 ni (k) a (k) tính ai = (k) ∑ ij Ci(k)={ai1(k),…, ai,ni(k)}, ∀i = 1, 2, …, l. Bư c 1: V i n i j=1 Bư c 2: Tìm m t phân ho ch m i Ck+1 = { C1(k+1), C2(k+1), ..., Cl(k+1) } sao cho Ci(k+1) (k +1) : d(a ij +1) , ai (k) ) = min d (a ij +1) , a r (k) ) , ∀ r = 1, l} , i = 1, 2,…, l. Như v y, căn c (k (k = {a ij (k ) v i i = 1,l c a các l p trong phân ho ch Ck, c n t o nên l p Ci(k+1) trong các tr ng tâm ai phân ho ch m i Ck+1. Bư c 3: Tính D(Ck+1). N u D (Ck+1) < D(Ck) - ε và k < kmax thì thay k b i k+1 r i quay v bư c 1. N u trái l i (các trư ng h p khác), d ng và in ra phân ho ch x p x t i ưu. Phân lo i d li u m Ngày nay, trong nhi u tình hu ng thu th p, x lí, qu n lí d li u và ra quy t nh, các phương pháp phân lo i i v i các d li u s thông thư ng (d li u rõ) như ã bi t cũng ã t ra thi u phù h p. ó là vì, các d li u thu th p ư c trên th c t thư ng ch a ng các bt n nh, ư c phân chia ra hai lo i chính : − nhoà ph n ánh tính b t n nh khách quan luôn hàm ch a trong các d li u thu th p t th c t . − nhoà ph n ánh nh tính ch quan xu t hi n t phía ngư i thu th p x lí d li u). nhoà - b t n nh − Lý thuy t t p m ư c s d ng tìm cách nh lư ng các nh tính luôn ti m tàng trong các d li u như ã nói trên (các d li u như v y s ư c g i là d li u m ) cũng như tìm ra các hàm kho ng cách thích h p i v i các d li u ó nh m ưa ra các phương pháp và thu t gi i phân lo i / phân ho ch thích h p. µ· A1 A2 1 B2 C1 C2 x 0 B1 Hình III.1. Tính kho ng cách gi a hai s m http://www.ebook.edu.vn 14
nh nghĩa: Xét hai s m d ng tam giác ã1= (xB1,xA1,xC1), ã2 =(xB2,xA2,xC2). như th hi n trên hình III.1. Lúc ó kho ng cách θ gi a ã1 , ã2 s ư c xác nh b i công th c sau: θ(ã1,ã2) 1 1 = 2( x A1 − x A 2 ) + ( x B1 − x B 2 ) + ( xC1 − xC 2 ) + ( 2 x A1 − x A 2 + x B1 − x B 2 + xC1 − xC 2 ) 4 8 Lúc ó, bi u th c th nh t v ph i có th ư c coi là kho ng cách gi a các tr ng tâm c a hai t giác A1B1C1D1 và A2B2C2D2, v i D1 r t sát g n A1 và D2 r t sát g n A2. Tuy nhiên, có th xây d ng ư c các t giác A1B1C1D1 và A2B2C2D2, v i D1 r t sát g n A1 và D2 r t sát g n A2, khá khác bi t nhau mà v n có tr ng tâm trùng nhau. Bi u th c th hai v ph i cho phép tính n các khác bi t gi a hai tam giác A1B1C1 và A2B2C2 khi xác nh kho ng cách gi a hai s m ã cho. D dàng ki m tra ư c r ng, hàm kho ng cách trong nh nghĩa 2 có y c ba tính ch t thông thư ng c a hàm kho ng cách. Tính ch t 1. d(ã1, ã2) = d(ã2 , ã1) (≥ 0) Tính ch t 2. d(ã1, ã3) ≤ d(ã1 , ã2) + d(ã2, ã3) ∀ ã1, ã2, ã3. Trong m t s trư ng h p, có th dùng kho ng cách quy chu n gi a hai s m : d*(ã1 , ã2) = kd(ã1, ã2) v i k là h s quy chu n sao cho ∀ã1, ã2 thì 0 ≤ d*(ã1, ã2) ≤ 1. Tính ch t 3: d(ã1, ã2) = 0 khi và ch khi ã1 = ã2. D a trên thu t gi i x p x và hàm kho ng cách như trong nh nghĩa 2 có th ti n hành phân lo i d li u m . V n lư ng hóa ý ki n chuyên gia Ý ki n chuyên gia khi ánh giá m t cách t ng h p m t phương án (quy ho ch s d ng t) nào ó ư c cho các m c: r t t t, t t, khá phù h p, không phù h p, kém hi u qu , không nên tri n khai. i u này cho phép các chuyên gia ưa ra ý ki n m t cách tương i d dàng. Gi s các m c ó có th minh ho b ng các s m m t chi u là: (0.9, 0.95, 1.0), (0.7, 0.8, 0.9), (0.5, 0.6, 0.7), (0.3, 0.4, 0.5), (0.1, 0.2, 0.3) và (0, 0.05, 0.1). Ch ng h n, (0.9, 0.95, 1.0) có nghĩa là phương án ư c ánh giá r t t t, th a mãn ư c t 90% t i 100% mong mu n c a chuyên gia, mà trong gi i này thì 95% m c mong mu n là t ư c v i kh năng nhi u nh t. Thu t gi i Delphi c i biên x lí và t ng h p ý ki n chuyên gia Bư c kh i t o − Xin ý ki n n chuyên gia ánh giá m t phương án các m c: r t t t, t t, khá phù h p, không phù h p, kém hi u qu , không nên tri n khai. − Ch n l là s l p phân ho ch ý ki n các chuyên gia, thông thư ng ch n l = 3 ho c l = 4. − Ch n kmax là s bư c l p t i a c n th c hi n (thông thư ng ch n kmax = 10 n 15. t k = 1. Các bư c l p Bư c 1: S d ng phương pháp phân lo i d li u căn c vào thu t gi i x p x d a trên các tiêu chu n kho ng cách c c ti u và bình phương bé nh t ã bi t (dùng công th c tính kho ng cách θ(ã1,ã2) gi a hai s m ã1,ã2 là các giá tr lư ng hoá hai ý kiên khác nhau) Bư c 2: − N u có ít nh t 75% ý ki n chuyên gia trong m t l p nào ó thì chuy n sang bư c 3. − N u có chưa t i 75% ý ki n chuyên gia trong cùng m t l p nào ó, nhưng k+1 > kmax thì cũng chuy n sang bư c 3. − N u trái l i thì thông báo cho các chuyên gia ý ki n trung bình c a m t ho c m t s l p ( ã ư c quy v m c nh tính g n nh t trong s 6 m c nh tính ã ưa ra) có nhi u ý ki n t p chung nh t (thông thư ng là m t ho c hai l p có nhi u ý ki n nh t). http://www.ebook.edu.vn 15
− Xin các chuyên gia s a ch nh l i ý ki n c a mình căn c thông báo trên và chuy n v bư c 1. Bư c 3: Thông báo cho các chuyên gia bi t ý ki n trung bình c a t t c các ý ki n thu c các l p có ch a ít nh t 2 ý ki n và có s ý ki n ≥ 0,1n (như v y các các ý ki n thu c vào các l p “thi u s ” v i s ý ki n < 0,1n b lo i ra). Ý ki n trung bình này ư c l y làm ý ki n th ng nh t c a nhóm chuyên gia. Chú ý. Ta có th so sánh và s p h ng các phương án, và sau ó gi l i m t s phương án t t nh t (thông thư ng là 3 phương án). s p h ng hai phương án A và B nào ó v i các ý ki n ánh giá ã ư c th ng nh t (x1, y1, z1), (x2, y2, z2), c n tính ch s Cf = 0.5(x1 – x2 + z1 – z2) + (y1 – y2). N u Cf > 0 thì phương án A ư c coi là t t hơn phương án B, n u Cf < 0 thì A x u hơn B, còn n u Cf = 0 thì A và B ngang nhau. 3.3. Trư ng h p kh o sát 2 Ra quy t nh nhóm l a ch n phương án t t nh t ph c v quy ho ch s d ng t s n xu t nông nghi p trên a bàn Tam Nông, Phú Th b ng thu t gi i Delphi c i biên Theo m c 2.3 và 2.4. sau khi gi i BTQHTT v i ba m c tiêu, thu t gi i tho d ng m tương tác ưa ra năm phương án t i ưu Pareto như ư c t ng h p trên b ng III.1 (hai phương án ã b lo i do có các phương án khác “tr i” hơn). ó là các phương án thu ư c khi gi i BTQHTT riêng r cho t ng m c tiêu và các phương án ng v i các b tr ng s (0.4, 0.3, 0.3) và (0.6, 0.2, 0.2). B ng III.1. Các phương án t i ưu PhuongAn TrongSo Z1 Z2 Z3 Phuong an 1 PayOff1 199639407.68 2135.53 17622.12 Phuong an 2 PayOff2 118973195.52 3283.86 21257.68 Phuong an 3 PayOff3 110565323.94 2135.53 22936.02 Phuong an 4 b(0.4,0.3,0.3) 157005887.40 3283.86 20370.9 Phuong an 5 c(0.6,0.2,0.2) 181719693.44 3283.86 17007.04 Các chuyên gia nh p ý ki n ánh giá 05 phương án này m t cách ng th i. Gi s bài toán 5 chuyên gia ánh giá và s bư c l p t i a cho phép là 5 bư c, s l p trong m t phân ho ch là 3. Bư c l p th 1: Ý ki n chuyên gia ư c t ng h p trong b ng III.2. Ch ng h n i v i phương án 1, ý ki n ánh giá c a các chuyên gia 1, 2, 3, 4 và 5 l n lư t là: t t, r t t t, khá phù h p, t t và t t. Chú ý r ng các m c ánh giá r t t t, t t, khá phù h p, không phù h p, kém hi u qu , không nên tri n khai ư c nh lư ng b ng các s m m t chi u là: (0.9, 0.95, 1.0), (0.7, 0.8, 0.9), (0.5, 0.6, 0.7), (0.3, 0.4, 0.5), (0.1, 0.2, 0.3) và (0, 0.05, 0.1). B ng III.2. Ý ki n các chuyên gia bư c l p 1 Chuyen PhuongAn1 PhuongAn2 PhuongAn3 PhuongAn4 PhuongAn5 Gia cg1 Tt Không phù Kém hi u qu Khá phù h p R tt t hp cg2 R tt t Không phù Không phù Tt Tt hp hp cg3 Khá phù Không phù Không phù Khá phù h p Khá phù h p hp hp hp cg4 Tt Kém hi u qu Kém hi u qu Khá phù h p R tt t cg5 Tt Không phù Không nên Khá phù h p R tt t hp tri n khai http://www.ebook.edu.vn 16
K t qu sau l n l p u tiên: 0.7 , 0.8 , 0.9 0.3 , 0.4 , 0.5 0.1 , 0.2 , 0.3 0.5 , 0.6 , 0.7 0.9 , 0.95 , 1 0.65 , 0.75 , 0.85 0.26 , 0.36 , 0.46 0.2 , 0.3 , 0.4 0.54 , 0.64 , 0.74 0.78 , 0.85 , 0.92 0.7 , 0.79 , 0.88 0.26 , 0.36 , 0.46 0.16 , 0.25 , 0.34 0.54 , 0.64 , 0.74 0.78 , 0.85 , 0.92 Trong t ng c t ng v i m i phương án: Hàng th nh t th hi n i m trung bình c a l p có nhi u chuyên gia nh t. Hàng th hai th hi n i m trung bình c a hai l p có nhi u chuyên gia nh t. Hàng th ba là i m trung bình chung c a t ng phương án. Phương án 2 ã ư c các chuyên gia th ng nh t ánh giá m c không phù h p. Phương án 4 cũng ã ư c các chuyên gia th ng nh t ánh giá. Các phương án khác chưa th ng nh t ư c ý ki n chuyên gia (ý ki n ư c coi là th ng nh t n u có t 75% tr lên ý ki n ánh giá trùng nhau), c n ph i ti n hành bư c l p ti p theo. Căn c các thông tin trên, các chuyên gia cho ý ki n ánh giá l i. Bư c l p th 2: Ý ki n chuyên gia cho trong b ng III.3. B ng III.3. Ý ki n các chuyên gia bư c l p 2 Chuyen PhuongAn1 PhuongAn2 PhuongAn3 PhuongAn4 PhuongAn5 Gia cg1 Tt Không phù Kém hi u qu Khá phù h p R tt t hp cg2 R tt t Không phù Không phù Tt Tt hp hp cg3 Tt Không phù Không phù Khá phù h p Tt hp hp cg4 Tt Kém hi u qu Kém hi u qu Khá phù h p Tt cg5 Tt Không phù Không phù Khá phù h p R tt t hp hp K t qu sau bư c l p th hai : 0.7 , 0.8 , 0.9 0.3 , 0.4 , 0.5 0.3 , 0.4 , 0.5 0.5 , 0.6 , 0.7 0.7 , 0.8 , 0.9 0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.22 , 0.32 , 0.42 0.54 , 0.64 , 0.74 0.78 , 0.86 , 0.94 0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.22 , 0.32 , 0.42 0.54 , 0.64 , 0.74 0.78 , 0.86 , 0.94 Phương án 1, 2 và 4 ã ư c các chuyên gia th ng nh t ánh giá. Phương án 3 và 5 chưa th ng nh t ư c ý ki n chuyên gia, c n ph i ti n hành bư c l p ti p theo. Bư c l p th 3: Ý ki n chuyên gia cho trong b ng III.4. B ng III.4. Ý ki n các chuyên gia bư c l p 3 Chuyen PhuongAn1 PhuongAn2 PhuongAn3 PhuongAn4 PhuongAn5 Gia cg1 Tt Không phù Không phù Khá phù h p R tt t hp hp cg2 R tt t Không phù Không phù Tt R tt t hp hp cg3 Tt Không phù Không phù Khá phù h p R tt t hp hp cg4 Tt Kém hi u qu Kém hi u qu Khá phù h p Tt cg5 Tt Không phù Không phù Khá phù h p R tt t hp hp http://www.ebook.edu.vn 17
K t qu sau bư c l p th ba: 0.7 , 0.8 , 0.9 0.3 , 0.4 , 0.5 0.3 , 0.4 , 0.5 0.5 , 0.6 , 0.7 0.9 , 0.95 , 1 0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.26 , 0.36 , 0.46 0.54 , 0.64 , 0.74 0.86 , 0.92 , 0.98 0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.26 , 0.36 , 0.46 0.54 , 0.64 , 0.74 0.86 , 0.92 , 0.98 Các ý ki n chuyên gia ã ư c th ng nh t nên chương trình d ng và s in ra ba phương án có ý ki n ánh giá th ng nh t t t nh t lưu l i, như sau ây: K T QU T NG H P Ý KI N CHUYÊN GIA CÁC PHƯƠNG ÁN T T NH T Phương án : 5 >R t t t Phương án : 1 > T t Phương án : 4 >Khá phù h p Trung bình = (0.9,0.95,1) Trung bình = (0.7,0.8,0.9) Trung bình = (0.5,0.6,0.7) X p x = (0.9,0.95,1) X p x = (0.7,0.8,0.9) X p x = (0.5,0.6,0.7) Căn c vào k t qu gi i ta th y phương án 5 ư c chuyên gia ánh giá là t t nh t có ý ki n trung bình c a các chuyên gia là (0.9, 0.95, 1.0). Ti p theo là phương án 1 có ý ki n trung bình các chuyên gia là (0.7, 0.8, 0.9). Phương án 4 có ý ki n trung bình (0.5, 0.6, 0.7) x p th ba. Các phương án trên ư c lưu tr và báo cáo l i cho b máy qu n lý. Sau khi cân nh c, phương án 5 ư c ưa ra tri n khai. 3.4. Mô hình ra quy t nh t p th d a trên toán t DELOWA Xét bài toán ra quy t nh nhóm khi c n l a ch n t t p h p n phương án quy t nh ra m t phương án h p lí nh t d a trên ý ki n c a m chuyên gia. Kí hi u: X = {x1, ..., xn} là t p các phương án hành i) ng c n l a ch n. ii) N = {e1, ...., em} là t p các chuyên gia. iii) w: N→ [0, 1] là hàm tr ng s , ánh giá t m quan tr ng c a m i chuyên gia, ư c nh nghĩa b i: ek → wk = w(k). Ký hi u véc tơ các tr ng s là w = (w1, ...,wm). Chu n hóa véc tơ tr ng s b ng cách: tính w0 = ∑ wi, t w’= (w’1, ...,w’n) v i w’i = wi / w0. iv) S = {S1, S2, ..., ST} là t p các nhãn (hay t p các giá tr m c a bi n ngôn ng S). ây, chúng ta gi s T là s l và các nhãn s p th t toàn ph n (t c là tho mãn các tính ch t ph n x , max-min b c c u, ph n i x ng) Ví d : S = Tu i = {tr , trung niên, già}, S = Ưu tiên hơn = {kém h n, kém nhi u, kém ít, không hơn m y, hơn ít, hơn nhi u, hơn h n}. T p nhãn S c n có tính ch t sau: i) ∀i > j: Si f Sj. ~ ii) T n t i các toán t ph nh: Neg(Si) = Sj, j = T +1 – i . iii) T n t i toán t Max thay cho toán t h p: Max {Si, Sj} = Si (v i Si f S). ~ ( ây là m t tính ch t còn tranh cãi do chưa tính t i s bù tr - compensation) Như v y, t p nhãn S xác nh m t quan h m ngôn ng . Ch ng h n, n u S là bi n ngôn ng Ưu tiên hơn, thì MR(x1, x2) = S1 có nghĩa là x1 kém h n so v i x2. http://www.ebook.edu.vn 18
iv) ng v i S là bi n ngôn ng Ưu tiên hơn, khi ánh giá hay s p x p các phương án c a t p phương án x, m i chuyên gia s ưa ra m t ma tr n ưu tiên ngôn ng riêng c a mình [rij]nxn, rij ∈ S, th a mãn: − rij = ST thì x i ư c ưu tiên hơn xj m c ST. − S(T+1)/2 < rij < ST thì xi ư c ưu tiên rõ ràng hơn xj . − rij = S(t+1)/2 có nghĩa là m c ưu tiên gi a xi và xj là m c bàng quan (ưu tiên như nhau / không hơn m y). Như v y ng v i m i chuyên gia ek, có m t quan h ưu tiên m ngôn ng Pk: X×X → S v i tính ch t: n u Pk(xi, xj) = rij = S l thì Pk(xj, xi) = rji = Neg(S l) ∈ S . Ngoài ra, ∀i u có: Pk(xi, xi) = rii = S(t+1)/2. i u này v m t nào ó gi ng như yêu c u: rij + rji = 1, ∀i≠j rii = 0 , như trong quan h ưu tiên m . Các lư ng t m không gi m Trong ngôn ng thông thư ng chúng ta thư ng g p các lư ng t ngôn ng như: ph n nhi u, ít nh t là 50%, … C n mô hình hoá các lư ng t này như th nào? nh nghĩa: Hàm Q: [0, 1] → [0, 1], ư c g i là lư ng t quan h n u Q(0) = 0 và t n t i z ∈ [0,1] sao cho: Q(z) =1. Lư ng t quan h Q ư c g i là lư ng t không gi m n u Q(z1) ≤ Q(z2) m t khi z1 < z2. không gi m Q1[a, b] v i a, b ∈ [0, 1] là lư ng t có d ng sau: Ta xét lư ng t zb  Ví d : Lư ng t quan h “ít nh t 50%” Q1[0; 0,5] có th ư c bi u di n trên th trên hình III.2. 1 0,5 0 1 z Hình III.2. Lư ng t quan h “ít nh t 50%” Tương t , cũng có th bi u di n ư c lư ng t “ph n nhi u”Q1[0,3; 0,8]. nh nghĩa: Lư ng t ngôn ng Q2 tương ng v i Q1[a, b] và bi n ngôn ng S ư c xác nh như m t hàm nh n giá tr là các nhãn c a bi n ngôn ng S,t c là Q2: [0,1] → S v i quy t c sau: http://www.ebook.edu.vn 19
S1 n u z b.  z−a  max µt  z − a  } trong  Trong ó Si = max {Sl: Sl∈ M}, v i M= {Sl: µl  = ó  st ∈S  b−a   b−a  µt(.) là hàm liên thu c xác nh t p m S t . Ví d : Xét s m d ng t giác: St = (at, bt, ct, dt) = (a, b, c, d) v i th hàm liên thu c trên hình III.3. 1 µt at ut bt ct Hình III.3. S m d ng t giác: St = (at, bt, ct, dt)  z−a   = µt(0,8) , v i a = 0, b = 0,5 và z th trên hình III.3 có th th y: µ t  D a vào  b−a  = 0,4. ng v i lư ng t Q1[a, b] ã bi t, µt(.) ánh giá xem v i giá tr z ã cho giá tr (z-a)/(b- a) thu c St v i thu c là bao nhiêu. Lúc ó Q2(z) s nh n giá tr là nhãn Si theo cách xác nh trên ây (Si là nhãn mà (z-a)/(b-a) thu c vào Si v i thu c l n nh t). Ch ng h n v i z = 0,4, n u xét các lư ng t so sánh: − I (impossible − không so sánh ư c) = (0; 0; 0; 0) − EU (extremely unlikely − r t khó so sánh) = (0; 0,01; 0,02; 0,07) − VLC (very low chance − th p hơn khá nhi u) = (0,04; 0,1; 0,18, 0,23) − IM (it may – như nhau) = (0,32; 0,41; 0,58; 0,65) − MC (meaningful chance – hơn ít) = (0,58; 0,63; 0,80; 0,86) − ML (most likely – hơn nhi u) = (0,72; 0,78; 0,92; 0,97) − EL (extremely likely – hơn h n) = (0,93; 0,98; 0,99; 1) − C (certain − t t nhiên hơn h n) = (1; 1; 1; 1) thì M = {MC, ML} và do ó Q2(0,4) = ML. Mô t t p S1 , …, ST St = (at, bt, ct, dt), v i a1 = b1 = 0, b1 ≤ c1 ≤ d1 ; aT ≤ bT ≤ cT = dT = 1; at < bt ≤ ct< dt ; và at < at+1, bt < bt+1, ct < ct+1, dt < dt+1 ∀ t . http://www.ebook.edu.vn 20