Đối với các bài toán lớn trong lĩnh vực quản lý hệ thống nông nghiệp, các phần
mềm tối ưu đơn lẻ, chuyên biệt tỏ ra không thật sự hiệu quả. Có thể nhận thấy rằng, các
cơ sở dữ liệu hệ thống nông nghiệp là rất lớn, luôn cần được bổ sung, cập nhật cũng như
xử lý. Nhiều quyết định quản lý có thể được xây dựng dựa trên cơ sở áp dụng phương
pháp mô hình hoá bao gồm các mô hình phân tích / cơ chế và các mô hình tiện dụng
cũng như các phương pháp toán học đa dạng như: xử lý thống kê, tối ưu hoá, lý thuyết
ra quyết định, mô phỏng ngẫu nhiên Chính vì vậy, các phần mềm tính toán khoa học
và ra quyết định cần được tích hợp thành một hệ phần mềm hỗ trợ ra quyết định để xử
lý các dữ liệu thu thập được. Việc tạo ra hệ hỗ trợ ra quyết định cho các bài toán quản lý
hệ thống nông nghiệp ở Việt nam là một vấn đề nghiên cứu quan trọng và thiết thực,
nhằm thực hiện các chủ trương của nhà nước trong vấn đề chuyển đổi cơ cấu kinh tế
nông nghiệp trong nền kinh tế hàng hoá - thị trường có định hướng.
45 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1053 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Giáo trình môn Hệ điều hành - Chương IV: Giải bài toán quy hoạch tuyến tính đa mục tiêu bằng phương pháp thoả dụng mờ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
cua cac ham thoa dung - Lan thu 4
Z[1] = 17023792.2600000 pZ[1] = 0.5440364
Z[2] = 350.0000000 pZ[2] = 0.4486101
Z[3] = 38822.7751000 pZ[3] = 0.6460748
Gia tri Max cua ham lien hop 4 : 0.5657665
***** Ket thu ham muc tieu lien hop 4 *****
Tap cac phuong an toi uu sau khi giai bai toan la:
X(1)
X(1,1)=27.620
X(1,2)=41.520
X(1,3)=0.000
X(1,4)=0.000
X(1,5)=48.490
X(1,6)=0.000
X(1,7)=85.020
X(1,8)=0.000
X(1,9)=163.150
X(1,10)=92.870
X(1,11)=16.490
X(1,12)=0.000
X(1,13)=0.000
X(1,14)=0.000
X(1,15)=0.000
X(1,16)=0.000
X(1,17)=0.000
X(1,18)=0.000
Z(X(1))
Z(1X(1))=18546863.0800
Z(2X(1))=475.1600
Z(3X(1))=36218.4010
X(3)
X(3,1)=0.000
X(3,2)=0.000
X(3,3)=0.000
X(3,4)=0.000
X(3,5)=0.000
X(3,6)=0.000
X(3,7)=85.020
X(3,8)=0.000
X(3,9)=163.150
X(3,10)=0.000
X(3,11)=0.000
X(3,12)=0.000
X(3,13)=0.000
X(3,14)=92.870
69
X(3,15)=16.490
X(3,16)=27.620
X(3,17)=48.490
X(3,18)=41.520
Z(X(3))
Z(1X(3))=15206528.6600
Z(2X(3))=248.1700
Z(3X(3))=40895.0218
X(5)(Nghiem ham lien hop 2)
X(5,1)=27.620
X(5,2)=41.520
X(5,3)=0.000
X(5,4)=0.000
X(5,5)=0.000
X(5,6)=0.000
X(5,7)=85.020
X(5,8)=0.000
X(5,9)=163.150
X(5,10)=92.870
X(5,11)=16.490
X(5,12)=0.000
X(5,13)=0.000
X(5,14)=0.000
X(5,15)=0.000
X(5,16)=0.000
X(5,17)=48.490
X(5,18)=0.000
Z(X(5))
Z(1X(5))=17884489.6800
Z(2X(5))=426.6700
Z(3X(5))=37429.6812
X(6)(Nghiem ham lien hop 3)
X(6,1)=27.620
X(6,2)=41.520
X(6,3)=0.000
X(6,4)=0.000
X(6,5)=0.000
X(6,6)=0.000
X(6,7)=85.020
X(6,8)=0.000
X(6,9)=163.150
X(6,10)=14.081
X(6,11)=16.490
X(6,12)=0.000
X(6,13)=0.000
X(6,14)=78.789
X(6,15)=0.000
X(6,16)=0.000
X(6,17)=48.490
X(6,18)=0.000
Z(X(6))
Z(1X(6))=17000000.0000
Z(2X(6))=347.8806
Z(3X(6))=38861.2844
X(7)(Nghiem ham lien hop 4)
X(7,1)=27.620
X(7,2)=41.520
70
X(7,3)=0.000
X(7,4)=0.000
X(7,5)=0.000
X(7,6)=0.000
X(7,7)=85.020
X(7,8)=0.000
X(7,9)=163.150
X(7,10)=16.200
X(7,11)=16.490
X(7,12)=0.000
X(7,13)=0.000
X(7,14)=76.670
X(7,15)=0.000
X(7,16)=0.000
X(7,17)=48.490
X(7,18)=0.000
Z(X(7))
Z(1X(7))=17023792.2600
Z(2X(7))=350.0000
Z(3X(7))=38822.7751
******** KET THUC BAI TOAN - THE END ********
2.3. Bài toán quy hoạch đất xã Trâu Quỳ
File vào TNG.DAT
10 6 2 2 2 1
189.6407 189.6407 26.4 1700.5 43.8931 18
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
5.14 4.98 3.77 0 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 1 1 1
4.48 4.2 2.59 0.98 5.8 15.61 29.67 39.21 116.58 105.13
0.6205 0.5915 0.465 0.1583 0.7065 0.5864 1.2996 1.2735 1.1726 1.756
0.0217 0.0206 0.0154 0.0045 0.0248 0.0109 0.0241 0.0349 0.09 0.0811
206 204 168 216 234 1428 1232 1124 1296 1296
0.7 0.778 1.1273 1.75 1 0.368 0.875 3 3 3
71
Chương V
MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU PHI TUYẾN ĐA MỤC TIÊU
1. BÀI TOÁN TỐI ƯU PHI TUYẾN TRONG MÔI TRƯỜNG MỜ / NGẪU
NHIÊN
1.1. Phát biểu bài toán và phương pháp mức ưu tiên
Xét mô hình tối ưu đa mục tiêu:
Min fj(X), X = (x1, x2, , xn) j=1, 2,, p (p ≥2)
với: (i) gj(X) ≤ 0, j = 1, 2, , k,
(ii) gj(X) = 0, j = k+1, k+2, , m,
(iii) ai ≤ xi ≤ bi, i = 1, 2, , n.
Chúng ta nhắc lại rằng trong mô hình này, các hệ số của các hàm mục tiêu và
ràng buộc nói chung được giả sử là các giá trị thực xác định (giá trị rõ). Nhưng trong
các bài toán thực tiễn không phải lúc nào cũng như vậy. Các hệ số có thể thuộc loại mờ
hay ngẫu nhiên tuỳ theo bản chất của chúng cũng như sự đánh giá chủ quan của con
người. Vì vậy, cần tìm kiếm một phương pháp tổng quát hơn có khả năng giải quyết các
bài toán tối ưu đa mục tiêu (với hệ số) mờ và ngẫu nhiên sau đây:
với:
(5.1)
Ký pháp ~ được sử dụng để chỉ các tham số mờ, ký pháp ^ dùng để chỉ các tham
số ngẫu nhiên, ký pháp được hiểu là phép cộng trong môi trường mờ (trong trường
hợp không gây ra hiểu nhầm, có thể vẫn dùng ký pháp +).
Trong bài toán trên yi(X), với i=1, 2, , n, là các hàm tuyến tính hay phi tuyến
của x1, x2, , xp trong môi trường rõ và được xác định trong miền S = [a1,b1] × [a2,b2]×
× [ap,bp] Є Rp. Với n=p và yi=xi với mọi i=1, 2, ,n, thì bài toán trở thành bài toán
tối ưu đa mục tiêu mờ/ngẫu nhiên tuyến tính (MultiObjective Mixed Fuzzy-Stochastic
Linear Programming Problem-MOFSLPP).
Đồng thời cũng giả sử rằng các tham số mờ tuân theo quy luật phân bố khả
năng. Mỗi tham số mờ được viết dưới dạng bộ bốn số: điểm tham chiếu trái, điểm tham
chiếu phải, độ căng trái và độ căng phải:
(5.2)
Để đơn giản, chúng ta giả sử các hàm tham chiếu L và R là các hàm tuyến tính,
tuy nhiên các trường hợp khác cũng có thể được xem xét. Thông thường, điểm tham
72
chiếu trái và phải trùng nhau và lúc đó, yếu tố mờ được biểu diễn bởi 3 điểm (dạng tam
giác). Ngoài ra, chúng ta cũng giả sử các tham số ngẫu nhiên tuân theo các luật phân bố
xác suất chuẩn và được coi là các biến ngẫu nhiên độc lập.
Một trong các phương pháp giải bài toán quy hoạch đa mục tiêu trong môi
trường hỗn hợp mờ/ngẫu nhiên là phương pháp tương tác dựa trên mức ưu tiên
(Preference Level Interative Method) với các mức ưu tiên được người ra quyết định sửa
chỉnh dần trong quá trình đối thoại / tương tác với máy tính. Như vậy, thông qua một
quy trình tính toán được máy tính trợ giúp, người ra quyết định sửa chỉnh dần các
quyết định trung gian để cuối cùng sẽ chọn ra trong các phương án tối ưu Pareto một
phương án tốt nhất dựa trên cơ cấu ưu tiên của mình. Phương pháp này cho phép giải
các bài toán tuyến tính và phi tuyến với các biến nguyên cũng như biến liên tục. Cần
chú ý rằng, phương pháp này đã sử dụng hướng tiếp cận mờ hoá trong đó việc xử lý các
mục tiêu ngẫu nhiên dựa trên cơ sở của mô hình kỳ vọng suy rộng E (Extended E-
model) và các ràng buộc ngẫu nhiên được mờ hoá. Do đó, người ra quyết định (decision
maker)/ người giải bài toán tạo được sự cân bằng giữa mục tiêu/ràng buộc ngẫu nhiên
và mục tiêu/ràng buộc mờ trong quá trình lặp để tìm phương án tối ưu thoả dụng.
Phương pháp tương tác dựa trên mức ưu tiên giải bài toán bao gồm ba thành
phần cơ bản:
i) Diễn giải và xử lý các ràng buộc và mục tiêu mờ / ngẫu nhiên, sau đó kết hợp
các mục tiêu phát sinh thành một hàm mục tiêu duy nhất.
ii) Các pha lặp trợ giúp người ra quyết định lựa chọn các mức ưu tiên và sửa
chỉnh dần chúng trong quá trình tìm kiếm một phương án thoả dụng có tính chất tối ưu
Pateto theo một nghĩa nào đó.
iii) Một thuật toán tối ưu toàn cục cho phép giải bài toán tối ưu đơn mục tiêu
được hình thành trong môi trường rõ tại mỗi pha lặp.
1.2. Xử lý các ràng buộc
Các ràng buộc ngẫu nhiên (1(iv)) có thể được biểu diễn trong môi trường mờ
dựa trên ràng buộc khả năng được mờ hoá (fuzzified chance constraints). Giả sử người
ra quyết định đã xác định mức mong đợi mờ của xác xuất là '
~
kp mà tại đó ràng buộc
ngẫu nhiên thứ k’ phải được thoả dụng:
(5.3)
Bất đẳng thức (5.3) có thể được giải thích như sau: Xác suất vế trái phải thật sự
lớn hơn '
~
kp , với '~kp được xác định bởi số mờ dạng tam giác '~kp ( )LKkkk ppp ''' ,,= với
'kp , 'kp và 'kp là giá trị trung bình, độ căng trái và độ căng phải ( các hàm tham chiếu
L và R được coi là tuyến tính).
Để xác định mức mong đợi mờ '
~
kp , người ra quyết định chỉ cần xác định giá trị
trung bình 'kp và độ căng trái bởi vì độ căng phải không có ý nghĩa trong (5.3). So với
phương pháp ràng buộc khả năng thông thường trong quy hoạch ngẫu nhiên, phương
73
pháp tiếp cận ràng buộc khả năng mờ cho phép sự linh động trong việc xác định mức
xác suất cực tiểu của ràng buộc ngẫu nhiên. Sử dụng ký hiệu:
, bất đẳng thức (5.3) được xử lý bởi:
(5.4)
(5.5)
Điều kiện (5.4) có nghĩa là các ràng buộc ngẫu nhiên phải được thoả mãn tối
thiểu tại mức 'kp – 'kp . Trong (5),
s
kC '
~ là mục tiêu mờ tương ứng với ràng buộc ngẫu
nhiên thứ k’, (.)
'
~ s
kC
μ là hàm thuộc (membership function) của ]0ˆ)(ˆ[Pr '' ≤− kk bYaob
biểu diễn đánh giá chủ quan (của người ra quyết định) về xác suất ứng với '
~
kp . Sử
dụng ký hiệu: ='Pr kob ]0ˆ)(ˆ[Pr '' ≤− kk bYaob , (.)'~ skCμ được định nghĩa như sau:
(5.6)
với a
k
p
'
là mức ưu tiên về xác suất / mức xác suất chốt tương ứng với độ thoả
dụng chốt mong muốn đạt được λ* xác định bởi người ra quyết định cho Probk’ mà tại
đó ràng buộc ngẫu nhiên thứ k thoả mãn. Đồ thị của (.)
'
~ s
kC
μ cho trên hình sau:
Do:
với Φ là hàm phân phối của biến chuẩn N(0,1) nên bất đẳng thức (5.4) được viết
lại như sau:
*λ
(.)
'
~s
kC
μ
'Pr kob
'kp
'' kk
pp −
1
0 a
k
p
'
74
(5.7)
Xử lý các ràng buộc mờ (1(iv)) cũng giống như các mục tiêu mờ, có thể chuyển
chúng sang các dạng tất định sau:
(5.8)
(5.9)
Bất đẳng thức (5.8) có nghĩa là bất cứ giá trị nào của số mờ ở vế trái trong
(1(iii)) có mức hàm thuộc lớn hơn ε phải không vượt quá bj’ + bj’(1-ε), với ε Є [0,1] là
mức tin cậy xác định bởi người ra quyết định. Hàm thuộc (.)
'
~ s
kC
μ có thể được giải
thích như sự đánh giá chủ quan về ∑ =ni iRij ya1 ' tương ứng với số mờ '~jb ở vế phải. Nó
có thể được biểu diễn bởi một hàm tuyến tính phân hai đoạn như sau:
(5.10)
trong đó, ajb ' là mức xác suất ưu tiên / chốt của ∑ =ni iRij ya1 ' tương ứng với độ thoả
dụng chốt mong muốn đạt được λ* và có thể được thay đổi trong quá trình tương tác lặp.
Giá trị của nó được xác định bởi người ra quyết định và nằm trong khoảng bj’ và bj’ + bj’
(1 - ε). Vì thế *'~ )(' λμ =ajC bsk .
1.3. Xử lý các mục tiêu
Các mục tiêu ngẫu nhiên (1(ii)) có thể được giải thích dựa trên mô hình kỳ
vọng suy rộng và được xử lý trong môi trường mờ một cách thích hợp. Trước hết, với
mỗi mục tiêu ngẫu nhiên, giá trị kỳ vọng / mong đợi lớn nhất ( ký hiệu là ek) được tính
75
toán dựa trên các ràng buộc (5.7) và (5.8). Nói cách khác, chúng ta thu được ek từ bài
toán tối ưu đơn mục tiêu sau:
Ở đây, E là ký hiệu của kỳ vọng toán (mathematical expectation). Ký hiệu
k
e là
độ trượt cho phép (do người ra quyết định lựa chọn) ứng với mục tiêu ngẫu nhiên,
kk
ee − có thể được coi như là ngưỡng tối thiểu cho ∑ =ni iki yc1 ˆ . Áp dụng phương pháp
tiếp cận rủi ro tối thiểu (minimum-risk) cho ngưỡng này, mục tiêu ngẫu nhiên thứ k có
thể được diễn giải bởi:
Xử lý mục tiêu này như mục tiêu mờ trong quy hoạch mờ, ta có:
(5.11)
với kh
~ là mức độ mong muốn mờ xác định bởi người ra quyết định cho xác suất
vế trái. Ký hiệu kh
~ = (hk, hk)LL và xử lý (5.11) giống như đã làm với (5.3), ta được:
(5.12)
(5.13)
với skG
~ là mục tiêu mờ tương ứng với mục tiêu ngẫu nhiên thứ k. Ký hiệu
=kobPr ]0)(ˆ[Pr 1 ≥−−∑ = kni kki eecob , hàm thuộc biểu diễn đánh giá chủ quan về
xác suất kobrP
~ , được định nghĩa như sau:
(5.14)
76
Trong (5.14), ),( ' kkk
c
k hhhh −∈ là giá trị xác định bởi người ra quyết định và có
nghĩa tương tự như a
k
p
'
. Đồ thị của (.)~ s
kG
μ như trên hình II.23. Chú ý rằng kobrP~ là
xác suất mà với nó, mục tiêu ngẫu nhiên thứ k có thể nhận giá trị không nhỏ hơn
kk
ee − , và ckh là mức xác suất ưu tiên / chốt cho ràng buộc này.
Theo định nghĩa ta có:
trong đó φ là hàm phân phối của biến chuẩn N(0,1). Do đó, bất đẳng thức (5.12)
có thể viết lại thành:
hoặc là:
(5.15)
Xử lý các mục tiêu mờ (1(i)) tương tự như các ràng buộc mờ. Ký hi ệu jd
~ = (dj,
dj)LL là mức độ mong đợi xác định bởi người ra quyết định cho mục tiêu mờ thứ j,
chúng ta có:
(.)~s
kG
μ
kobrP
~
c
kh khkk hh −
1
0
*λ
77
Bất đẳng thức mờ này tương đương với hệ điều kiện sau:
(5.16)
(5.17)
Bất đẳng thức (5.16) có nghĩa là bất cứ giá trị có thể nào của mục tiêu thứ j
njnjj ycycyc ~...~~ 2211 +++ với mức hàm thuộc lớn hơn ε đều không được nhỏ hơn dj – dj
(1 – ε). Hàm thuộc (.)~ f
jG
μ (được diễn giải như sự đánh giá chủ quan về ini Lji yc∑ =1
tương ứng với jd
~ ) được định nghĩa như sau:
(5.18)
trong đó, cjd được xác định bởi người ra quyết định và có thể được chỉnh sửa
trong quá trình tương tác lặp. Rõ ràng là cjd là một kiểu mức ưu tiên / chốt của
i
n
i
L
ji yc∑ =1 tương ứng với độ thoả dụng chốt mong muốn đạt được λ*.
1.4. Sử dụng thông tin pay-off để đoán nhận
k
e , jd
~
Với mục đích trợ giúp quá trình xác định mức ưu tiên / chốt cho độ trượt
k
e từ
ek của mục tiêu ngẫu nhiên thứ k, thông tin dạng pay-off ẩn chứa trong cấu trúc của bài
toán có thể đóng vai trò khá quan trọng. Ký hiệu Xs* (s = 1, 2,, m+q) các phương án
tối ưu của m+q bài toán tối ưu đơn mục tiêu tương ứng với m mục tiêu mờ và q mục
tiêu ngẫu nhiên sau đây:
(5.19)
(5.20)
Cận dưới của tất cả các giá trị kỳ vọng của mục tiêu ngẫu nhiên thứ k đạt được
tại Xs* (s = 1, 2,, m+q) được tính như sau:
78
với giá trị nhỏ nhất được chọn trong tập {Ys* = Y(Xs*), s = 1,2,,m+q}.
Giá trị ( kk ee − ) có thể coi như là độ trượt lớn nhất của ke , và vì thế người ra
quyết định xác định giá trị của
k
e trong đoạn [0, kk ee − ].
Để tính toán mức độ mong đợi mờ jd
~ = (dj, dj)LL, dj và dj có thể được xác định
như sau:
với X* là phương án tối ưu của bài toán:
(5.21)
và dj có thể được tính ra từ:
(5.22)
trong đó, giá trị min được tính ra trên tập {Ys* = Y(Xs*), s = 1, 2,, 2m+q} với
Xs* (s = 1, 2,, 2m+q) là các phương án tối ưu của 2m+q bài toán sau:
(5.23)
(5. 24)
(5.25)
Cần chú ý rằng việc xây dựng các mức mong đợi mờ jd
~ cho các mục tiêu mờ
cũng như các độ trượt
k
e cho các mục tiêu ngẫu nhiên, thực chất, là dựa trên thông tin
79
dạng pay-off ẩn chứa trong bài toán. Tuy nhiên, người ra quyết định có thể chủ động
xác định các mức ưu tiên trên kết hợp với / hay không kết hợp với thông tin pay-off.
1.5. Mô hình tất định tương đương của bài toán
Với cách biểu diễn và xử lý các mục tiêu và ràng buộc như trên, MOFSPP được
viết lại thành:
(5.26)
Sử dụng toán tử min (Bellman-Zadeh min-operator) làm toán tử kết hợp
(aggregation operator), (5.26) được đưa về dạng bài toán max-min tối ưu đơn mục tiêu
tất định sau:
(5.27)
1.6. Khái niệm tối ưu hoá PL-Pareto
Khái niệm sau đây về phương án tối ưu PL-Pareto (Preference Level - PL) được
định nghĩa cho các bài toán dạng (5.1):
Định nghĩa 1. Phương án X của (5.26) được gọi là tối ưu PL-Pareto yếu với bài
toán (5.1) tại mức độ tin cậy ε và các độ trượt
k
e với mọi k, nếu không tồn tại một
phương án khác X’ của (5.26) mà tại đó tất cả các mức xác suất của mục tiêu ngẫu
nhiên và ràng buộc ngẫu nhiên ( kobrP
~ với mọi k, kobrP
~ với mọi k’) và tất cả các giá
trị với độ thực hiện cao nhất (các điểm chốt trái của các mục tiêu mờ i
n
i
L
ji yc∑ =1 , j∀ và
các điểm chốt phải của vế trái của các ràng buộc mờ ∑ =ni iRij ya1 ' , 'j∀ ), đều tốt hơn các
giá trị tương ứng đạt được tại X.
Định nghĩa 2. Phương án X của (5.26) được gọi là tối ưu PL-Pareto với bài toán
(5.1) tại mức độ tin cậy ε và các độ trượt
k
e với mọi k, nếu không tồn tại một phương
án khác X’ của (5.26) mà tại đó tất cả các mức xác suất của mục tiêu ngẫu nhiên và ràng
buộc ngẫu nhiên ( kobrP
~ với mọi k, kobrP
~ với mọi k’) và tất cả các giá trị với độ thực
hiện cao nhất (các điểm chốt trái của các mục tiêu mờ và các điểm chốt phải của vế trái
80
của các ràng buộc mờ), lần lượt, đều không tồi hơn các giá trị tương ứng đạt được tại X,
và ít nhất một trong số các giá trị đó là tốt thực sự.
Định lý 1.
(i) Nếu X là phương án tối ưu toàn cục của (5.27) (λ là giá trị tối ưu của hàm
mục tiêu của (5.27) đạt được tại X với 0<λ<1) thì X là phương án tối ưu PL-Pareto yếu
của (5.1) với mức độ tin cậy ε và các độ trượt
k
e đã lựa chọn.
(ii) Nếu X là phương án tối ưu toàn cục duy nhất của (5.27) (λ là giá trị tối ưu
của hàm mục tiêu của (5.27) đạt được tại X với 0<λ<1) thì X là phương án tối ưu PL-
Pareto của (5.1) với mức độ tin cậy ε và các độ trượt
k
e đã lựa chọn.
Để giải quyết bài toán max-min (5.27), cần một giải thuật tính toán hiệu quả.
Thuật giải RST2ANU được thiết kế bởi C.Mohan và Nguyễn Hải Thanh có thể được áp
dụng trong thành phần thứ ba của phương pháp tương tác dựa trên mức ưu tiên.
2. THUẬT GIẢI TƯƠNG TÁC LẶP PRELIME VÀ MỘT SỐ ỨNG DỤNG
2.1. Phát biểu thuật giải
Có thể tóm tắt các bước giải bài toán tối ưu đa mục tiêu mờ / ngẫu nhiên như sau:
Bước khởi tạo
(Cụm từ “xác định” dùng để chỉ hành động của người ra quyết định)
Xác định )]1(,[,, '''
* ελε −∈ jjaj bbb , j’=1, 2, , m’ và 'kp , 'kp ,
∈a
k
p
'
],[ ''' kkk ppp − , k’ = 1,2,,q’ để thu được ke , ke , k = 1, 2, , q, và jd , jd , j
= 1, 2, , m.
Sau đó xác định
k
e ∈ [0, kk ee − ] với k = 1, 2, ,q và
)]1(,[ ε−−∈ jjjcj dddd với j=1, 2, , m.
Cuối cùng, xác định kh , kh , ),( ' kkk
c
k hhhh −∈ , k =1, 2, , q.
Đặt chỉ số bước lặp l=1.
Các bước lặp
Bước 1: Giải bài toán tất định max-min (5.27), sau đó cung cấp cho người ra
quyết định / người sử dụng các thông tin sau :
(i) Phương án thoả hiệp (compromising solution) ),...,,( 21
l
p
ll
l xxxX = và giá trị
tương ứng của hàm mục tiêu tổng hợp λl.
(ii) Giá trị của các điểm tham chiếu trái của các mục tiêu mờ i
n
i
L
ji yc∑ =1 , j =
1,2,,m, các giá trị kỳ vọng của các mục tiêu ngẫu nhiên i
n
i ki
ycm )ˆ(
1∑ = và các mức
xác suất tương ứng kobrP
~ để các mục tiêu nhận giá trị lớn hơn
kk
ee − , k = 1,2,,q.
81
(iii) Giá trị của các điểm tham chiếu phải của vế trái của các ràng buộc mờ
∑ =ni iRij ya1 ' , j’ = 1,2,,m’, giá trị kỳ vọng của vế trái của các ràng buộc ngẫu nhiên
∑ =ni iik yam1 ' )ˆ( và xác suất tương ứng 'Pr kob , k = 1,2,,q’ mà các ràng buộc được thoả mãn.
Bước 2:
(i) Nếu |λ1 - λ*| < δ (với δ là một số dương nhỏ được người sử dụng chọn trước),
quá trình lặp có thể dừng với phương án thoả dụng Xl.
(ii) Nếu λ1 > λ* + δ và người sử dụng thoả mãn với Xl, quá trình lặp cũng có thể
kết thúc với phương án thoả mãn Xl. Tuy nhiên, nếu như người sử dụng muốn tiếp tục
tìm kiếm các phương án thoả dụng khác, thì có thể tăng ít nhất một trong các đại lượng
sau đây: cjd , j=1,2,m;
c
kh , k = 1,2,,q;
a
k
p
'
, k’ = 1,2,,q’ và / hoặc giảm ít nhất một
trong số các đại lượng: ajb ' , j’= 1 ,2,,m’; ke , k=1,2,,q để cải thiện kết quả.
(iii) Nếu λ1 < λ* + δ thì Xl không phải là phương án thoả mãn. Cần phải tăng ít
nhất một trong các đại lượng: ajb ' , j’= 1 ,2,,m’; ke , k=1,2,,q và / hoặc giảm ít nhất
một trong số các đại lượng: cjd , j=1,2,m;
c
kh , k = 1,2,,q;
a
k
p
'
, k’ = 1,2,,q’
(iv) Tăng l lên 1 đơn vị rồi quay lại bước 1.
2.2. Bài toán Chakraborty
Một xí nghiệp sản xuất ba loại sản phẩm 1, 2, và 3. Các dữ liệu về giá cả, chi
phí, lợi nhuận, của các loại sản phẩm và mức dự trữ hiện có được cho trong bảng
sau. Bài toán đặt ra là xác định số lượng các loại sản phẩm (sản xuất trong một ngày)
sao cho:
i) Tổng lợi nhuận thu được là lớn nhất.
ii) Tổng mức độ mong muốn sử dụng sản phẩm của khách hàng là lớn nhất.
Tiêu hao / đơn vị
sản phẩm
Sản phẩm 1 Sản phẩm 2 Sản phẩm 3 Mức dự trữ
hiện có
Điện và thiết bị 0,5 4 2 130
Thời gian N(2,1) N(3,1) N(1, 0,4) N(102, 2)
Nguyên liệu (7, 7, 2, 2)LR (10, 10, 1, 1)LR (9, 9, 2, 2)LR (420, 20)RR
Lợi nhuận N(11,1) N(14, 2) N(5, 0,5)
Độ thỏa mãn của
người tiêu dùng
(2, 2, 1, 1)LR
(7, 7, 2, 2)LR
(5, 5, 1,1)LR
Ví dụ trên dẫn đến việc giải bài toán sau:
với các ràng buộc
82
Sử dụng phần mềm PRELIME, cần soạn
Thủ tục tính các hàm mục tiêu và các ràng buộc
void ren(int index)
{ int i;
switch(index)
{ case 0:
for(i=0;i<n;++i)
y[i]=x[i];
break;
case 1:
for(i=0;i<n;++i)
y[i]=x[i];
break;
case 2:
for(i=0;i<n;++i)
y[i]=x[i];
break;
case 3:
for(i=0;i<n;++i)
y[i]=x[i];
break;
case 4:
for(i=0;i<n;++i)
y[i]=x[i];
break;
}
return;
}
File dữ liệu đầu vào MP1.IN
3 3 3 1 2 1 1 1
2 1 1 7 2 2 5 1 1
11 1 14 2 5 0.5
0.5 0 0 4 0 0 2 0 0
7 2 2 10 1 1 9 2 2
2 1 3 1 1 0.4
130 0 0 450 0 20
102 2
0 30 0 30 0 30
0 1 2
0.001 0.001 0.01
8000 2000 0 2000
3 2 0 0 1 1
/* bảng phân phối chuẩn cần cho chương trình tự động tìm xác suất */
.0000 .0040 .0080 .0120 .0160 .0199 .0239 .0279 .0319 .0359
.0398 .0438 .0478 .0517 .0557 .0596 .0636 .0675 .0714 .0754
83
.0793 .0832 .0871 .0910 .0948 .0987 .1026 .1064 .1103 .1141
.1179 .1217 .1255 .1293 .1331 .1368 .1406 .1443 .1480 .1517
.1554 .1591 .1628 .1664 .1700 .1736 .1772 .1808 .1844 .1879
.1915 .1950 .1985 .2019 .2054 .2088 .2123 .2157 .2190 .2224
.2258 .2291 .2324 .2357 .2389 .2422 .2524 .2486 .2518 .2549
.2580 .2612 .2642 .2673 .2704 .2734 .2764 .2794 .2823 .2852
.2881 .2910 .2939 .2967 .2996 .3023 .3051 .3078 .3106 .3133
.3159 .3186 .3212 .3238 .3264 .3289 .3315 .3340 .3365 .3389
.3413 .3438 .3461 .3485 .3508 .3531 .3554 .3577 .3599 .3621
.3643 .3665 .3686 .3708 .3729 .3749 .3770 .3790 .3810 .3830
.3849 .3869 .3888 .3907 .3925 .3944 .3962 .3980 .3997 .4015
.4032 .4049 .4066 .4082 .4099 .4115 .4131 .4147 .4162 .4177
.4192 .4207 .4222 .4236 .4251 .4265 .4279 .4292 .4306 .4319
.4332 .4345 .4357 .4370 .4328 .4394 .4406 .4418 .4429 .4441
.4452 .4463 .4474 .4484 .4495 .4505 .4515 .4525 .4535 .4545
.4554 .4564 .4573 .4582 .4591 .4599 .4608 .4616 .4625 .4633
.4641 .4649 .4656 .4664 .4671 .4678 .4686 .4693 .4699 .4706
.4713 .4719 .4726 .4732 .4738 .4744 .4750 .4756 .4761 .4767
.4772 .4778 .4783 .4788 .4793 .4798 .4803 .4808 .4812 .4817
.4821 .4826 .4830 .4834 .4838 .4842 .4846 .4850 .4854 .4857
.4861 .4864 .4868 .4871 .4875 .4878 .4881 .4884 .4887 .4890
.4893 .4896 .4898 .4901 .4904 .4904 .4909 .4911 .4913 .4916
.4918 .4920 .4922 .4925 .4927 .4929 .4931 .4932 .4934 .4936
.4938 .4940 .4941 .4943 .4945 .4946 .4948 .4949 .4951 .4952
.4953 .4955 .4956 .4957 .4959 .4960 .4961 .4962 .4963 .4964
.4965 .4966 .4967 .4968 .4969 .4970 .4971 .4972 .4973 .4974
.4974 .4975 .4976 .4977 .4977 .4978 .4979 .4979 .4980 .4981
.4981 .4982 .4982 .4983 .4984 .4894 .4985 .4985 .4986 .4986
.4987 .4987 .4987 .4988 .4988 .4989 .4989 .4989 .4990 .4990
.4990 .4991 .4991 .4991 .4992 .4992 .4992 .4992 .4993 .4993
.4993 .4993 .4994 .4994 .4994 .4994 .4994 .4995 .4995 .4995
.4995 .4995 .4995 .4996 .4996 .4996 .4996 .4996 .4996 .4997
.4997 .4997 .4997 .4997 .4997 .4997 .4997 .4997 .4997 .4998
.4998 .4998 .4998 .4998 .4998 .4998 .4998 .4998 .4998 .4998
.4998 .4998 .4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999
.4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999
.4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999 .4999
.5000 .5000 .5000 .5000 .5000 .5000 .5000 .5000 .5000 .5000
Cuối cùng ta thu được file kết quả đầu ra như sau:
File MP1.OUT
n=3,n2=3,m1=1,m2=2,q1=1,q2=1,m3=1,nint=3
cf[0][0]=~(2.000000,1.000000,1.000000)
84
cf[0][0]=~(2.000000e+00,1.000000e+00,1.000000e+00)
cf[0][1]=~(7.000000,2.000000,2.000000)
cf[0][1]=~(7.000000e+00,2.000000e+00,2.000000e+00)
cf[0][2]=~(5.000000,1.000000,1.000000)
cf[0][2]=~(5.000000e+00,1.000000e+00,1.000000e+00)
cs[0][0]=^(11.000000,1.000000)
cs[0][1]=^(14.000000,2.000000)
cs[0][2]=^(5.000000,0.500000)
af[0][0]=~(0.500000,0.000000,0.000000)
af[0][1]=~(4.000000,0.000000,0.000000)
af[0][2]=~(2.000000,0.000000,0.000000)
af[1][0]=~(7.000000,2.000000,2.000000)
af[1][1]=~(10.000000,1.000000,1.000000)
af[1][2]=~(9.000000,2.000000,2.000000)
as[0][0]=^(2.000000,1.000000)
as[0][1]=^(3.000000,1.000000)
as[0][2]=^(1.000000,0.400000)
bf[0]=~(130.000000,0.000000,0.000000)
bf[1]=~(450.000000,0.000000,20.000000)
bs[0]=^(102.000000,2.000000)
xmin[0]=0.000000,xmax[0]=30.000000
xmin[1]=0.000000,xmax[1]=30.000000
xmin[2]=0.000000,xmax[2]=30.000000
noninteger variables are:
x[0]x[1]x[2]Parameters for crs() are:
0.001000,0.001000,0.010000
8000,2000,0,2000,3,2
0,0,1,1
Phi[200]=0.477200
epsilon=0.100000,lamda=0.500000
/* nhập ε =0.1, λ = 0.5 */
anpha[0]=0.600000,denanpha[0]=0.200000
/* nhập h1 = 0.6, c1 1h 0.45, h 0.2= = */
gama[0]=0.000000
/* luôn đặt γ = 0*/
ps[0]=0.550000,beta1[0]=0.570000,beta[0]=0.650000
/* nhập p1 = 0.65, a1 1p 0.57, p 0.1= = */
THE Uj OBJECTIVE VALUES ARE:
*, s*,f=-498.436768,fm=-497.952515,iter=587,ifun=5470
*, s*,f=-500.923218,fm=-500.425415,iter=1186,ifun=11124
*, s*,f=-495.241272,fm=-494.746765,iter=898,ifun=7685
*, s*,f=-509.498840,fm=-508.989868,iter=740,ifun=6299
t*, f= 509.498840,iter2=3411 ifun2=30578
u[0]=509.498840,x[0]=29.806744,x[1]=10.353548,x[2]=7.335000,
/* Vậy hàm mục tiêu ngẫu nhiên có kỳ vọng cực đại là : e1 = 509.498840 */
FUZZY ASPIRATION ARE:
85
*, s*,f=-250.603195,fm=-250.353546,iter=646,ifun=5565
*, s*,f=-256.724731,fm=-256.472076,iter=1188,ifun=9069
*, s*,f=-255.401428,fm=-255.147598,iter=892,ifun=7188
*, s*,f=-255.560532,fm=-255.308609,iter=894,ifun=7025
t*, f= 256.724731,iter2=3620 ifun2=28847
*, s*,f=-194.656174,fm=-194.461990,iter=805,ifun=6380
*, s*,f=-200.524338,fm=-200.324539,iter=1113,ifun=8682
*, s*,f=-196.544815,fm=-196.350510,iter=1151,ifun=8989
*, s*,f=-196.538406,fm=-196.344437,iter=694,ifun=5682
t*, f= 200.524338,iter2=3763 ifun2=29733
/* Vậy hàm mục tiêu mờ có giá trị lớn nhất là d1 = 256.724737 */
PARAMETERS ARE:
d[0]=(116.699371,150.000000,256.724731)
bf[1]=(450.000000,465.000000,468.000000)
U[0]=509.498840,U[0]-DenU[0]=479.498840 U[0]-DenUl[0]=445.414215
anpha[0]~(0.400000,0.450000,0.600000)
/* Đặt c1d 150= , 1e 30= */
***ITERATION 1
*, s*,f=-0.720325,fm=-0.719616,iter=1445,ifun=11385
*, s*,f=-0.713683,fm=-0.712970,iter=1202,ifun=10567
*, s*,f=-0.676134,fm=-0.675460,iter=2067,ifun=15409
*, s*,f=-0.725293,fm=-0.724583,iter=1670,ifun=14131
t*, f= 0.725293,iter2=6384 ifun2=-14044
(lamda[1],X)=(0.725293,19.960680,14.773745,10.951034,)
Zf[0]=198.092743
Zs[0]=481.155060
0-stoch-objective probability=~0.518305
Zcf[0]=90.977386
Zcf[1]=386.021515
Zcs[0]=95.193627
0-stoch-cons hold with probability=0.606047
NEW PARAMETERS ARE:
d[0]=(116.699371,160.000000,256.724731)
bf[1]=(450.000000,455.000000,468.000000)
U[0]=509.498840,U[0]-DenU[0]=491.498840
anpha[0]=0.600000
anpha[0]~(0.400000,0.480000,0.600000)
gama[0]=0.000000
beta[0]=0.650000
beta[0]~(0.550000,0.590000,0.650000)
***ITERATION 2
*,cs*,f=-0.226025,fm=-0.000000,iter=2001,ifun=13657
*,cs*,f=-0.187145,fm=-0.000000,iter=2001,ifun=13836
*,cs*,f=-0.000000,fm=-0.000000,iter=0,ifun=1562
*,cs*,f=-0.559870,fm=-0.000000,iter=2001,ifun=13782
t*, f= 0.559870,iter2=6003 ifun2=-22699
(lamda[2],X)=(0.559870,28.427076,9.145482,10.274362,)
86
Zf[0]=172.244339
Zs[0]=492.106384
0-stoch-objective probability=~0.507108
Zcf[0]=71.344193
Zcf[1]=382.913635
Zcs[0]=94.564961
0-stoch-cons hold with probability=0.597184
NEW PARAMETERS ARE:
d[0]=(116.699371,174.000000,256.724731)
bf[1]=(450.000000,455.000000,468.000000)
U[0]=509.498840,U[0]-DenU[0]=491.498840
anpha[0]=0.600000
anpha[0]~(0.400000,0.500000,0.600000)
gama[0]=0.000000
beta[0]=0.650000
beta[0]~(0.550000,0.600000,0.650000)
***ITERATION 3
*,cs*,f=-0.471844,fm=-0.000000,iter=2001,ifun=13734
*,cs*,f=-0.149716,fm=-0.000000,iter=2001,ifun=13836
*,cs*,f=-0.000000,fm=-0.000000,iter=0,ifun=1562
*,cs*,f=-0.064333,fm=-0.000000,iter=2001,ifun=13654
st*, f= 0.471844,iter2=6003 ifun2=-22750
(lamda[3],X)=(0.471844,28.427076,9.145482,10.274362,)
Zf[0]=172.244339
Zs[0]=492.106384
0-stoch-objective probability=~0.507108
Zcf[0]=71.344193
Zcf[1]=382.913635
Zcs[0]=94.564961
0-stoch-cons hold with probability=0.597184
Giải thích kí hiệu
epsilon = ε = 0.1 là 10% đáy số mờ bỏ qua,
lamda =λ = 0.5 là mức mong muốn 50% của tất cả các hàm thoả dụng,
anpha[0] = h1 = 0.60 là mức xác suất cao nhất cho mục tiêu ngẫu nhiên,
denanpha[0]= 1h = 0.20 là lượng cho phép giảm tối đa của h1,
anpha1[0] = c1h 0.45= là mức xác suất thoả mãn 50%,
anpha[0]~(0.400000,0.450000,0.600000) là mức xác suất mờ cho mục tiêu mờ,
gama[0] = 0, luôn đặt γ = 0,
ps[0] = 1 1p p− = 0.55 là mức xác suất thoả mãn 0% của ràng buộc xác suất,
beta1[0] = a1p = 0.570000 là mức xác suất thoả mãn 50% của ràng buộc xác suất,
beta[0] = p1 = 0.650000 là mức xác suất thoả mãn 100% của ràng buộc xác suất,
ps(0) = 1p 0.1= là lượng cho phép giảm tối đa của mức xác suất từ p1,
Da[0]= c1d 150= = là mức thoả mãn 50% đối với hàm mục tiêu mờ,
d[0]=(116.699371,150.000000,256.724731) là mức mong muốn mờ của mục tiêu,
87
Ga[1] = a2b = 465 là mức thoả mãn 50% đối với ràng buộc mờ,
bf[1] = (450.000000,465.000000,468.000000) là hệ số vế phải của ràng buộc mờ,
U[0] = e1 = 509.498840 là giá trị kỳ vọng cực đại của mục tiêu ngẫu nhiên
U[0]-DenUl[0] = Min1 = 445.414215 là giá trị chặn dưới của hàm ngẫu nhiên
DenU[0]= 1e 30= là mức giảm cho phép của kỳ vọng hàm ngẫu nhiên,
U[0]-DenU[0]=479.498840 U[0]-DenUl[0]=445.414215.
2.3. Bài toán xác định cơ cấu đầu tư cho các hộ chăn nuôi cá
Thủ tục tính giá trị hàm mục tiêu và các ràng buộc
void ren(int index)
{ int i;
switch(index)
{ case 0:
y[0]=pow(x[0],0.236)*pow(x[1],0.104)*pow(x[2],0.096)*pow(x[3],0.056);
y[0]=y[0]*pow(x[4],0.056)*exp(0.168*x[5])*exp(0.066*x[6]);
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 1:
y[0]=pow(x[0],0.236)*pow(x[1],0.104)*pow(x[2],0.096)*pow(x[3],0.056);
y[0]=y[0]*pow(x[4],0.056)*exp(0.168*x[5])*exp(0.066*x[6]);
y[1]=x[0]+x[1]+x[2]+x[3]+x[4];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 2:
y[0]=pow(x[0],0.236)*pow(x[1],0.104)*pow(x[2],0.096)*pow(x[3],0.056);
y[0]=y[0]*pow(x[4],0.056)*exp(0.168*x[5])*exp(0.066*x[6]);
y[1]=x[0]+x[1]+x[3]+x[4];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 3:
y[0]=x[0];
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 4:
y[0]=x[5];
y[1]=x[6];
break;
}
88
return;
}
File dữ liệu đầu vào test1.in
7 5 5 3 2 0 0 2
19.375 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19.375 0 0 -1 0 0 0 0 0 0 0 0 0 0 0
19.375 0 0 -1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
75 0 0
1.001 0 0
0 40 0 30 0 20 0 15 0 15 0 1 0 1
0 1 2 3 4
0.001 0.001 0.01
8000 2000 0 2000
3 2 0 0 1 1
Chú ý: Còn có thêm bảng tra xác xuất chuẩn.
2.4. Bài toán quy hoạch sử dụng đất trên địa bàn huyện Trùng Khánh
Kết quả điều tra nông hộ và kết quả xử lý số liệu cho thấy: số liệu điều tra là
biến động và có tính ngẫu nhiên. Do đó một số hệ số của mô hình là các biến ngẫu
nhiên (tuân theo luật chuẩn) nên mô hình được áp dụng là mô hình quy hoạch tuyến tính
ngẫu nhiên.
Trên cơ sở các biến số, hệ số, các ràng buộc và hàm mục tiêu được xây dựng
một cách phù hợp, ta có mô hình quy hoạch tuyến tính ngẫu nhiên đa mục tiêu được
phát biểu như sau:
Hãy tìm giá trị không âm của các biến số Xj (j = 1,..., 12) thoả mãn các điều kiện
ràng buộc sao cho các hàm mục tiêu Z1, Z2, Z3 đạt giá trị lớn nhất.
Z1 = (6847,12 ; 1227,36) (X1 + X2 + X3) + (5011,45 ; 1096,94) (X4 + X5 + X6) +
(3801,45 ; 1325,61) (X7 + X8 + X9) + (3651,74 ; 703,21) (X10 + X11) + (17604,65 ;
3161,43) X12 → Max
Z2 = (4411,75 ; 978,77) (X1 + X2 + X3) + (3135,63 ; 1087,87) (X4 + X5 + X6) +
(2906,75 ; 1153,83) (X7 + X8 + X9) + (2253,17 ; 655,69) (X10 + X11) + (6516,88 ;
2138,27) X12 → Max
Z3 = (2,15 ; 1,21) (X1 + X2 + X3) + (1,94 ; 1,13) (X4 + X5 + X6) + (3,45 ; 1,27)
(X7 + X8 + X9) + (1,63 ; 0,53) (X10 + X11) + (0,60 ; 0,21) X12 → Max.
Với các ràng buộc:
X1 = 1400,00; X2 = 1400,00; X3 = 2820,00;
X4 + X7 + X10 = 2820,00; X5 + X8 + X11 + X12 = 2511,65;
X6 + X9 + X12 = 2511,65; X8 + X9 ≤ 2511,65;
(3,78; 0,76)(X1 + X2 + X3) + (3,00; 0,71)(X4 + X5 + X6) ≥ Q~ (22000,0 ; 1000,0);
Xj ≥ 0 (j= 1,...,12).
Trong đó:
89
- Xj (j = 1, 2, ..., 12) là các biến số quyết định của bài toán (diện tích 5 loại cây
trồng trên 3 loại hình sử dụng đất).
- Zi là các hàm mục tiêu: Z1 là tổng giá trị sản xuất (GO) tối đa (Z1 =
MaxXP~
12
1i
ii →∑
=
) với iP
~ là giá trị sản xuất đạt được trên một đơn vị diện tích cây trồng,
iP
~ là hệ số ngẫu nhiên. Z2 là tổng thu nhập hỗn hợp (MI) tối đa (Z2 = MaxXC~
12
1i
ii →∑
=
) với
iC
~ là thu nhập hỗn hợp đạt được trên một đơn vị diện tích cây trồng, iC
~ là hệ số ngẫu
nhiên. Z3 là tổng tỷ suất lợi nhuận tối đa (Z3 = MaxXR
~12
1i
ii →∑
=
) với iR
~ là tỷ suất lợi
nhuận thu được trên một đơn vị diện tích cây trồng, iR
~ là hệ số ngẫu nhiên.
-Q~ (22000,0 ; 1000,0) là tổng sản lượng lương thực (có hạt) trong giai đoạn tới.
Đây là một giá trị ngẫu nhiên có kỳ vọng 22000,0 tấn và độ lệch chuẩn là 1000,0 tấn.
Sau khi xây dựng được mô hình, ta giải mô hình bằng phần mềm PRELIME (C.
Mohan và Nguyễn Hải Thanh, 2001). Kết quả giải mô hình được tổng hợp trong bảng
V.1 với ba phương án tối ưu thoả dụng có thể được lựa chọn.
Bảng V.1. Kết quả chạy bài toán tối ưu
Từng mục tiêu Kết hợp cả ba mục tiêu
Giá trị
Z1 → Max Z2 → Max Z3 → Max Giá trị 1 Giá trị 2 Giá trị 3
X1(ha) 1400,00 1400,00 1400,00 1400,00 1400,00 1400,00
X2(ha) 1400,00 1400,00 1400,00 1400,00 1400,00 1400,00
X3(ha) 2820,00 2820,00 2820,00 2820,00 2820,00 2820,00
X4(ha) 2653,83 2815,62 10,86 2270,08 2289,50 2495,94
X5(ha) 0,00 422,25 1453,26 1306,54 1241,00 1021,24
X6(ha) 0,00 1186,07 839,19 1712,76 1492,14 1293,04
X7(ha) 0,00 0,00 2808,67 549,61 528,54 324,03
X8(ha) 0,00 784,34 837,59 419,15 255,33 303,87
X9(ha) 0,00 35,41 1671,40 14,01 4,28 32,96
X10(ha) 166,17 4,38 0,47 0,31 1,96 0,03
X10(ha) 0,00 14,90 219,75 1,08 0,09 0,90
X10(ha) 2511,65 1290,17 1,05 784,88 1015,23 1185,64
Z1
(1000 đ) 96603880,0
82546840,0
* 73,56%
84527912,0
* 85,31%
85975488,0
* 71,41%
Z2
(1000 đ) 49499980,0
49354340,0
* 54,14%
49454884,0
* 56,16%
49426864,0
* 57,29%
Z3 35256,97
26208,16
* 54,14%
25158,50
* 62,76%
24407,70
*5 7,49%
λ 0,805 0,899 0,676
SLLT
(tấn)
37111,74
* 99,56%
36311,54
* 99,43%
35674,27
* 99,31%
Ghi chú:- λ : Độ thoả dụng tổng hợp của các mục tiêu.
- Zi: Giá trị kỳ vọng của các mục tiêu.
- *: Xác suất để giá trị mục tiêu Zi hay sản lượng lương thực (SLLT) đạt
hơn mức chốt đề ra.
90
Đối với từng mục tiêu và hàm liên hợp 3 mục tiêu, các cây trồng được đề nghị
khuyến khích trồng là lúa (được khuyến khích trên tất cả các diện tích có khả năng trồng
lúa), ngô, đậu tương và mía, không khuyến khích trồng khoai lang. Điều này là dễ hiểu,
bởi khoai lang thường cho hiệu quả thấp hơn so với các cây trồng trên.
Từ các kết quả thu được, có thể đưa ra nhận xét: Vấn đề có tính chiến lược hiện
nay trên địa bàn huyện Trùng Khánh là phát triển các cây lương thực như lúa, ngô và
chuyển đổi cơ cấu theo hướng sản xuất hàng hoá có giá trị hiệu quả cao, dành một tỷ lệ
đất màu khoảng 40 - 45% cho phát triển cây mía
Thủ tục tính giá trị hàm mục tiêu và các ràng buộc
void ren(int index)
{ int i;
switch(index)
{ case 0:
x[0]=1400.0; x[1]=1400;x[2]=2820;
y[0]=x[0]+x[1]+x[2];
y[1]=x[3]+x[4]+x[5];
y[2]=x[6]+x[7]+x[8];
y[3]=x[9]+x[10];
y[4]=x[11];
break;
case 1:
x[0]=1400.0; x[1]=1400;x[2]=2820;
y[0]=x[0]+x[1]+x[2];
y[1]=x[3]+x[4]+x[5];
y[2]=x[6]+x[7]+x[8];
y[3]=x[9]+x[10];
y[4]=x[11];
break;
case 2:
x[9]=2820-x[3]-x[6];
if(x[9]<0.000001)
y[0]=2822;
else
y[0]=x[3]+x[6]+x[9];
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 3:
x[10]=2511.65-x[4]-x[7]-x[11];
if(x[10]<0.000001)
y[0]=2513;
else
y[0]=x[4]+x[7]+x[10]+x[11];
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
91
y[4]=x[4];
break;
case 4:
x[8]=2511.65-x[5]-x[11];
if(x[8]<0.000001)
y[0]=2513;
else
y[0]=x[5]+x[8]+x[11];
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 5:
y[0]=x[7]+x[8];
y[1]=x[1];
y[2]=x[2];
y[3]=x[3];
y[4]=x[4];
break;
case 6:
y[0]=-x[0]-x[1]-x[2];
y[1]=-x[3]-x[4]-x[5];
y[2]=-x[9]-x[10];
y[3]=x[3];
y[4]=x[4];
break;
}
return;
}
File dữ liệu đầu vào Test2.in
12 5 12 0 4 3 1 4
6847.12 1227.36 5011.45 1096.94 3801.45 1325.61 3651.74 703.21 17604.65 3161.43
4411.75 978.77 3135.63 1087.87 2906.75 1153.83 2253.17 655.69 6516.88 2138.27
2.15 1.21 1.94 1.13 3.45 1.27 1.63 0.53 0.60 0.21
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3.78 0.76 3.0 0.71 0 0 0 0 0 0
2821 0 0
2512 0 0
2512 0 0
2511.65 0 0
-22000 1000
0 1400 0 1400 0 2820 0 2820 0 2511.65 0 2511.65
0 2820 0 2511.65 0 2511.65 0 2820 0 2511.65 0 2511.65
0 1 2 3 4 5 6 7 8 9 10 11
0.001 0.001 0.01
8000 4000 0 4000
6 4 0 0 1 1
92
Chương VI
KẾT LUẬN VÀ ĐỀ XUẤT MỘT SỐ HƯỚNG NGHIÊN CỨU
1. ÁP DỤNG CÁC MÔ HÌNH TỐI ƯU TRONG NÔNG NGHIỆP
Các mô hình tối ưu có một vai trò quan trọng trong nhiều lĩnh vực của nông
nghiệp như:
- Quy hoạch sử dụng đất và tài nguyên hợp lý, chuyển đổi cơ cấu cây trồng – vật
nuôi nhằm đạt hiệu quả kinh tế, hiệu quả sử dụng đất và tài nguyên, hiệu quả sinh thái
môi trường.
- Hoạch định các chính sách tối ưu trong quản lý hệ thống nông – lâm – ngư
nghiệp trên cơ sở thu thập và khai phá các dữ liệu thực tế.
- Tin sinh học, bảo vệ thực vật, công nghệ chế biến, thiết kế chế tạo máy nông
nghiệp, các thiết bị tự động hoá
Ngoài ra, còn nhiều lĩnh vực nông nghiệp khác mà các mô hình tối ưu có thể
mang lại các lợi ích thiết thực. Một số ví dụ được đã được đề cập tới trong chương I minh
hoạ khá rõ ràng cho vấn đề này. Đó là các vấn đề nghiên cứu chuyên khảo (study cases)
đã được Khoa Công nghệ thông tin phối hợp với các chuyên gia nhiều lĩnh vực cộng tác
triển khai trên thực tế. Qua những vấn đề nghiên cứu khảo sát đó có thể nhận thấy tầm
quan trọng của việc đưa ra các mô hình tối ưu để giải quyết các bài toán thực tiễn.
Để thiết lập một mô hình tối ưu phải xác định rõ các yêu cầu, các mục tiêu cụ
thể cần đạt tới, các điều kiện hạn chế (ràng buộc) của bài toán, các yếu tố (biến quyết
định) cần xem xét cũng như phải bỏ ra nhiều công sức để thu thập được các dữ liệu thực
tế đa dạng và có độ tin cậy cao . Sau đó, cần lựa chọn một phương pháp tối ưu toán học
phù hợp làm công cụ để giải quyết mô hình. Việc phân tích các kết quả tính toán đạt
được cũng như triển khai, đánh giá và kiểm nghiệm các phương án tối ưu trên thực tế
cần nên thận trọng và chính xác với sự cộng tác chặt chẽ của các chuyên gia trong lĩnh
vực nông nghiệp và các chuyên gia về toán – tin ứng dụng.
2. NGHIÊN CỨU ÁP DỤNG VÀ ĐỀ XUẤT CÁC PHƯƠNG PHÁP TỐI ƯU
Các phương pháp tối ưu toán học có thể áp dụng trong lĩnh vực nông nghiệp
cũng rất đa dạng như trong hầu hết các lĩnh vực kinh tế – xã hội khác. Đó là các phương
pháp tối ưu đơn mục tiêu và đa mục tiêu, tuyến tính cũng như phi tuyến với các biến
liên tục, nguyên cũng như hỗn hợp nguyên. Các tham số của mô hình có thể là các số
thực thông thường, các hệ số ngẫu nhiên / biến ngẫu nhiên, các hệ số mờ tuỳ theo bản
chất của chúng và của vấn đề cần giải quyết. Vì vậy, ngoài các phương pháp tối ưu cổ
điển, có thể áp dụng các phương pháp quy hoạch ngẫu nhiên và quy hoạch mờ. Một số
khía cạnh của của quy hoạch ngẫu nhiên và quy hoạch mờ đã được đề cập tới trong bài
báo của C. Mohan và Nguyễn Hải Thanh “An interactive satisficing method for solving
multiobjective mixed fuzzy-stochastic programming problems”, International Journal for Fuzzy
Sets and Systems, Vol. 117, No.1, pp. 61-79, 2001, cũng như trong bài báo của Nguyễn Tuấn
Anh và Nguyễn Hải Thanh, “Ứng dụng mô hình toán học nhằm nâng cao hiệu quả sử dụng đất
93
cho nông hộ trên địa bàn huyện Trùng Khánh, tính Cao Bằng”, Tạp chí Khoa học kỹ thuật Nông
nghiệp, Tập 4, Số 4+5, trang 175–182, 2006.
Có thể nhận thấy rằng, các dữ liệu đầu vào cũng như các mục tiêu, yêu cầu đưa
ra, nhìn chung, chỉ được coi là không đổi / tĩnh (static) trong khoảng thời gian ngắn.
Chúng sẽ biến đổi một cách khách quan và được sửa chỉnh một cách chủ quan, tuần tự
từ giai đoạn này tới giai đoạn khác, phù hợp với các kết quả đã đạt được. Việc giải các
bài toán quy hoạch dài hạn đòi hỏi phải nghiên cứu và áp dụng các phương pháp tối ưu
đa dạng như các phương pháp quy hoạch động (dynamic programming), các phương
pháp mô phỏng (simulation methods) và nhiều phương pháp tối ưu khác.
Lý thuyết tối ưu toán học cũng gắn liền chặt chẽ với lý thuyết ra quyết định một
người ra quyết định hay tập thể / nhóm người ra quyết định. Ngày nay, lĩnh vực này của
khoa học quản lý / toán ứng dụng được áp dụng rộng rãi trong nhiều chuyên ngành, bao
gồm nhiều lĩnh vực nông nghiệp như quản lý kinh tế ông nghiệp, sử dụng đất và tài
nguyên, dự báo thị trường nông sản và ra quyết định đầu tư Có thể nói, lý thuyết tối
ưu toán học tỏ ra rất hiệu quả trong việc “khai phá dữ liệu” còn lý thuyết ra quyết định
lại là một công cụ mạnh trong việc “khai phá kinh nghiệm và tri thức”.
3. XÂY DỰNG CÁC PHẦN MỀM TỐI ƯU
Việc tìm kiếm các phương án khả thi và hợp lý cho các mô hình tối ưu đã thiết
lập được, cũng như kiểm nghiệm và phân tích sự phù hợp của kết quả với các dữ liệu
thực tế đa dạng đòi hỏi phải tạo ra các chương trình máy tính đủ mạnh. Hơn nữa, các
chương trình này cần được đóng gói thành các phần mềm dễ sử dụng, có giao diện thân
thiện với người dùng. Điều này sẽ giúp cho các chuyên gia trong lĩnh vực nông nghiệp
có thể khai phá các dữ liệu nông nghiệp một cách hiệu quả và cho phép họ tìm hiểu sâu
hơn về mô hình cũng như phát huy được các kinh nghiệm và tri thức chuyên ngành sẵn
có của mình. Việc xây dựng và sử dụng các phần mềm tối ưu cũng thúc đẩy khoa học
về mô hình hoá và tính toán khoa học phát triển rộng rãi hơn nữa trong các chuyên
ngành nông nghiệp.
Các phần mềm thương phẩm đóng gói của nước ngoài (chẳng hạn như Excel,
Lingo, v.v) không thể cung cấp đầy đủ các công cụ cần thiết để giải quyết các bài
toán, các mô hình tối ưu phát sinh từ thực tế trong các lĩnh vực kinh tế nông nghiệp,
quản lý sử dụng đất và tài nguyên, cơ khí - tự động hoá nông nghiệp... Nói riêng, đối
với các mô hình tối ưu phi tuyến một mục tiêu, mô hình tối ưu đa mục tiêu thường gặp
trong đào tạo và nghiên cứu khoa học, các phần mềm tính toán khoa học vẫn chưa sẵn
có. Vì vậy, vấn đề xây dựng qui trình tính toán, thiết kế thuật giải và cài đặt hệ chương
trình máy tính – phần mềm tối ưu là một vấn đề liên ngành được nhiều chuyên ngành
nông nghiệp cũng như các chuyên gia toán học và tin học quan tâm. Kinh nghiệm của
chúng tôi trong thiết kế các phần mềm tối ưu RST2AU, MULTIOPT và PRELIME cho
thấy vấn đề này đòi hỏi người thiết kế phải có cơ sở vững về phương pháp mô hình hoá,
về các phương pháp tối ưu, có kiến thức về thuật giải và lập trình, cũng như biết cách
cộng tác với các chuyên gia trong các lĩnh vực nông nghiệp.
94
Tuy nhiên, việc khai thác tối đa 100% tính năng của các phần mềm tối ưu hiện
có cũng là một vấn đề cần chú trọng cho các bài toán trong lĩnh vực nông nghiệp.
4. XÂY DỰNG HỆ HỖ TRỢ RA QUYẾT ĐỊNH
CÀI ĐẶT TRÊN MẠNG MÁY TÍNH
Đối với các bài toán lớn trong lĩnh vực quản lý hệ thống nông nghiệp, các phần
mềm tối ưu đơn lẻ, chuyên biệt tỏ ra không thật sự hiệu quả. Có thể nhận thấy rằng, các
cơ sở dữ liệu hệ thống nông nghiệp là rất lớn, luôn cần được bổ sung, cập nhật cũng như
xử lý. Nhiều quyết định quản lý có thể được xây dựng dựa trên cơ sở áp dụng phương
pháp mô hình hoá bao gồm các mô hình phân tích / cơ chế và các mô hình tiện dụng
cũng như các phương pháp toán học đa dạng như: xử lý thống kê, tối ưu hoá, lý thuyết
ra quyết định, mô phỏng ngẫu nhiên Chính vì vậy, các phần mềm tính toán khoa học
và ra quyết định cần được tích hợp thành một hệ phần mềm hỗ trợ ra quyết định để xử
lý các dữ liệu thu thập được. Việc tạo ra hệ hỗ trợ ra quyết định cho các bài toán quản lý
hệ thống nông nghiệp ở Việt nam là một vấn đề nghiên cứu quan trọng và thiết thực,
nhằm thực hiện các chủ trương của nhà nước trong vấn đề chuyển đổi cơ cấu kinh tế
nông nghiệp trong nền kinh tế hàng hoá - thị trường có định hướng.
Một hướng nghiên cứu gần đây là “Xây dựng hệ hỗ trợ ra quyết định trong quy
hoạch sử dụng và quản lý đất nông nghiệp trên địa bàn cấp huyện” (đề tài cấp bộ
đang được triển khai). Trước hết, cần lựa chọn được một mô hình thích hợp (có thể là sự
tích hợp từ các mô hình khác nhau). Chúng tôi đã lựa chọn các mô hình sau để tích hợp
và xây dựng mô hình tổng thể.
- Mô hình tối ưu đa mục tiêu: Cần lựa chọn các biến quyết định, đưa ra các mục
tiêu cần tối ưu hoá (có thể là các tiêu chuẩn về tổ chức sử dụng đất hợp lý, bảo vệ môi
trưòng và cân bằng sinh thái), xác định các điều kiện hạn chế / ràng buộc (dựa trên
các nguồn dự trữ hiện có, các dự báo về thị trường và công nghệ mới, kinh nghiệm của
các hộ nông dân, các chính sách và qui chế cấp vĩ mô). Mô hình tối ưu đa mục tiêu sẽ
được áp dụng chủ yếu trên địa bàn cấp xã.
- Mô hình ra quyết định tập thể: Trước hết, cần lượng hoá được các đánh giá và
ý kiến của các chuyên gia trong nhiều lĩnh vực khác nhau. Sau đó, đưa ra một mô hình
để xử lý các ý kiến đó một cách tương tác nhằm cuối cùng tìm ra một đánh giá thống
nhất của tập thể chuyên gia. Mô hình ra quyết định tập thể có thể được áp dụng để hỗ
trợ cho việc lượng hoá các chỉ tiêu định tính về kinh tế – xã hội cũng như chọn ra các
phương án quy hoạch sử dụng đất cho địa bàn cấp xã / cấp huyện.
- Mô hình mô phỏng: Trước hết, cần phải xử lý thống kê các số liệu thu được và
kết hợp với các số liệu của hệ thống thông tin địa lý (GIS) để xây dựng các cơ sở dữ liệu
động về các nguồn dự trữ, về sinh thái môi trường, dự báo thị trường nông sản, các dữ
liệu về kinh nghiệm truyền thống của hộ nông dân cũng như các chỉ tiêu, chính sách cấp
vi mô. Sau đó, áp dụng mô phỏng để tìm ra các phương án tối ưu trong quy hoạch sử
dụng đất cho địa bàn từng xã và tổng hợp cho địa bàn cấp huyện.
95
Sơ đồ hệ hỗ trợ ra quyết định quy hoạch sử dụng đất
Các phương pháp toán ứng dụng có thể áp dụng để giải quyết mô hình là:
- Phương pháp hàm thoả dụng tổ hợp và phương pháp mức ưu tiên để giải các
mô hình tối ưu đa mục tiêu.
- Phương pháp Delphi hoặc Delowa hỗ trợ ra quyết định nhóm / tập thể.
- Phương pháp mô phỏng để giải bài toán quy hoạch sử dụng đất trên địa bàn
cấp huyện.
- Phương pháp lập luận xấp xỉ dựa trên lô gíc mờ và lô gíc ngôn ngữ.
Để hỗ cho việc sửa chỉnh các quyết định trung gian và tìm ra quyết định cuối
cùng trong việc quy hoạch sử dụng và quản lý đất trên địa bàn cấp huyện, một hệ hỗ
trợ ra quyết định sẽ được xây dựng và triển khai theo sơ đồ trên.
Các phương pháp nêu trên phải được chi tiết hoá bằng các thuật giải nhằm xây
dựng hệ phần mềm tích hợp. Cũng cần chú ý rằng để xây dựng và triển khai thành công
hệ hỗ trợ ra quyết định, cần:
- Đưa ra được các phương pháp lượng hoá thích hợp các chỉ tiêu định tính về
môi trường - xã hội,
- Biết cách phân tích / kiểm nghiệm các kết quả tính toán do hệ hỗ trợ ra quyết
định cung cấp,
- Đưa ra được các phương pháp thu thập và xử lý ý kiến của nông dân và của các
chuyên gia.
Dữ liệu thực tế
Xử lý
thống kê,
GIS
Xây dựng các cơ sở
dữ liệu và hệ thông
tin nông nghiệp
Triển khai ,
phân tích ,
đánh giá,
sửa đổi
Lựa chọn
phương án,
thử nghiệm,
phân tích,
đánh giá
Xử lý dữ liệu
trên máy tính,
qua hệ phần
mềm tích hợp
Ra quyết định
dựa trên ý kiến
chuyên gia
Các phương án
Lựa chọn phương án
hợp lý nhất
96
DANH MỤC TÀI LIỆU THAM KHẢO
1. Nguyễn Đức Nghĩa, Tối ưu hoá, Nhà xuất bản Giáo dục, Hà Nội, 2000.
2. Phan Quốc Khánh, Trần Huệ Nương, Quy hoạch tuyến tính, Nxb. Giáo dục,
2003.
3. Nguyễn Hải Thanh, Mô hình toán tối ưu xây dựng cơ cấu cây trồng, Báo cáo
tổng kết đề tài khoa học cấp Bộ mã số B99 – 32 - 54, 2001.
4. Nguyễn Hải Thanh (chủ biên) và các tác giả khác, Tin học ứng dụng trong
ngành nông nghiệp, Nxb. Khoa học và Kỹ thuật, 2005.
5. Nguyễn Hải Thanh, Toán ứng dụng, Nxb. Đại học Sư phạm Hà Nội, 2005.
6. Nguyễn Hải Thanh, Tối ưu hoá, Giáo trình cho ngành Công nghệ thông tin và
Tin học, Nhà xuất bản Bách khoa, Hà Nội, 2006.
7. M. S. Bazaraa, C. M. Shetty, Nonlinear programming: Theory and algorithms,
John Wiley and Sons, New York, 1990.
8. B. E. Gillett, Introduction to operations research: A computer–oriented
algorithmic approach, McGraw–Hill, New York, 1990.
9. Sy−Ming Guu and Yan−Kuen Wu, Two− phase approach for solving the fuzzy
linear programming problem, International Journal Fuzzy Set and Systems, Vol.
107, pp. 191−195, 1996.
10. George J. Klir, Fuzzy sets and fuzzy logic, theory and application, Prentice Hall,
1995.
11. C. Mohan and Nguyen Hai Thanh (1997), “A fuzzifying approach to stochastic
programming”, Opsearch, Vol. 34, No. 2, pp. 73-96.
12. C. Mohan and Nguyen Hai Thanh (1998), “Reference direction method for
solving multiobjective fuzzy programming”, European Journal of Operational
Research, Vol. 107, pp. 599-613.
13. C. Mohan and Nguyen Hai Thanh (1999), “Preference level interactive method
for solving multiobjectve fuzzy programming problems”, Asia-pacific Journal of
Operational Research, Vol. 16, pp. 63-86.
14. C. Mohan and Nguyen Hai Thanh (1999), “A controlled random search
technique incorporating the simulated annealing concept for solving integer and
mixed integer global optimization problems”, Computational Optimization and
Applications, Vol. 14, pp. 103-132.
15. C. Mohan and Nguyen Hai Thanh (2001), “An interactive satisficing method for
solving multiobjective mixed fuzzy-stochastic programming problems”,
International Journal for Fuzzy Sets and Systems, Vol. 117, No.1, pp. 61-79.
16. A. Osyczka, Multicriterion Optimization in Engineering with Fortran Programs,
Ellis Horwood Limited, New York, 1984.
17. H. A. Taha, Operations research, MacMillan, New York, 1989.
Các file đính kèm theo tài liệu này:
- baigiangcacmohinh_phanmemtoiuuphan2_7888.pdf