Bài giảng Một số bài toán ra quyết định

HỆ TRỢ GIÚP QUYẾT ĐỊNH
Lớp HTTT + Pháp
Năm học 2009 - 2010
Bài 7 – Một số bài toán ra quyết định
3.4. Một số bài toán ra quyết định:
NỘI DUNG :
- Mô phỏng
- Dự báo
- Lập lịch
- Các kỹ thuật tính toán mềm
TD Khang – ĐHBK Hà Nội
A/ Dự báo
Dự báo là nghệ thuật và khoa học tiên đoán các sự
kiện xảy ra trong tương lai dựa trên các sự kiện
trong quá khứ, hiện tại, hoặc sử dụng các mô hình
toán học
TD Khang – ĐHBK Hà Nội
Các bước dự báo
Xác định vấn đề
Tìm kiếm, thu thập thông tin
Chọn phương pháp, mô hình, giả thuyết
Thiết kế thí nghiệm
Thực hiện thí nghiệm
Phân tích kết quả
Tiếp tục duy trì và xác nhận
TD Khang – ĐHBK Hà Nội
Các phương pháp
Phương pháp phán đoán
Phương pháp đếm
Phân tích theo chuỗi thời gian
Phương pháp nhân quả
TD Khang – ĐHBK Hà Nội
Nhận xét
Các phương pháp phán đoán, phương pháp đếm được
dùng khi các phương pháp sau không phù hợp do: 
dữ liệu quá khứ quá phức tạp, hoặc ít thời gian, ít
kinh phí, thiếu dữ liệu, ...
Với các bài toán kinh tế, xã hội, thường dùng dữ báo
theo chuỗi thời gian
TD Khang – ĐHBK Hà Nội
Dự báo theo chuỗi thời gian
Tương lai được biểu diễn như là hàm số của quá khứ
mà không quan tâm đến ảnh hưởng của các biến
bên ngoài
Giá trị tương lai = f (Giá trị quá khứ) 
TD Khang – ĐHBK Hà Nội
Ví dụ: Ngoại suy
Cho các giá trị
Tháng 1 3
Tháng 2 5.5
Tháng 3 5
Tháng 4 7.5
Tháng 5 8
Tính kết quả của các tháng tiếp theo
Xấp xỉ về đường thẳng: y = 2.8 x + 1.5 
TD Khang – ĐHBK Hà Nội
Các phương pháp làm trơn
z Khi chuỗi thời gian không ổn định, không có
những thành phần biến đổi theo khuynh hướng, 
theo chu kỳ
z Phương pháp bình quân động
z Phương pháp làm trơn đa thức
z Phương pháp làm trơn hàm mũ
TD Khang – ĐHBK Hà Nội
Các phương pháp phân rã
Chia nhỏ dữ liệu đã qua thành các thời kỳ nhỏ hơn để
dễ dàng phân tích. Có 4 yếu tố cần xem xét:
- Xu thế: sự thay đổi xét trên một thời gian dài
- Chu kỳ của hiện tượng: thời gian mà hiện tượng sẽ
lặp lại
- Biến đổi trong chu kỳ: sự thay đổi tăng, giảm trong
một chu kỳ
- Dao động ngẫu nhiên: sự dao động xung quanh xu
thế, làm ảnh hưởng đến chu kỳ và biến đổi trong chu
kỳ
TD Khang – ĐHBK Hà Nội
Các dạng mẫu dữ liệu trong dự báo
theo chuỗi thời gian
Mẫu dữ liệu ngẫu nhiên
Mẫu theo khuynh hướng (tăng giảm, ...)
Mẫu theo mùa (lặp)
Mẫu theo chu kỳ (quay vòng)
Mẫu tự tương quan (thể hiện mối quan hệ giữa hai
biến)
Kết hợp các mẫu
TD Khang – ĐHBK Hà Nội
B/ Mô phỏng
z Mô phỏng bao gồm các kỹ thuật nhằm bắt chước
các hành vi (các trạng thái) của một thực thể nào đó. 
Mô phỏng gắn với hành vi (bên ngoài) chứ không
gắn với cấu trúc, mối liên hệ (bên trong).
z Mô phỏng liên quan chặt chẽ với môi trường quyết
định và hành vi ra quyết định
TD Khang – ĐHBK Hà Nội
Đặc trưng
z Mô phỏng không phải là loại mô hình biểu diễn
thực sự mà chỉ là bắt chước, là công cụ mô tả.
z Mô phỏng là một kỹ thuật dùng cho việc điều khiển
các thí nghiệm, kiểm thử dữ liệu cụ thể của quyết
định hoặc các biến không điều khiển được và quan
sát sự tác động lên các biến ra.
z Mô phỏng được dùng khi gặp các vấn đề quá phức
tạp, không xử lý được bằng các kỹ thuật tối ưu
TD Khang – ĐHBK Hà Nội
Quá trình mô phỏng
TD Khang – ĐHBK Hà Nội
Ưu điểm
Đơn giản.
Không phụ thuộc vào yếu tố thời gian
Cho phép quan sát 1 lớp các tình huống.
Cho phép thử nghiệm theo kiểu thử-sai.
Giúp cho nhà quản lý hiểu rõ hệ thống, vì được xây
dựng theo cách nhìn của nhà quản lý và cấu trúc
quyết định của họ.
Mô phỏng có thể thực hiện với mọi vấn đề, mọi tập
giá trị của các biến,...
TD Khang – ĐHBK Hà Nội
Nhược điểm
Không đảm bảo giải pháp tối ưu.
Quá trình mô phỏng chậm, tốn kém.
Không thể dùng để giải các bài toán khác, khó tổng
quát hóa.
Mô phỏng nhiều khi làm cho nhà quản lý mất trực
quan, phương án tối ưu xuất hiện trước mắt nhưng
không nhận ra
TD Khang – ĐHBK Hà Nội
Thủ tục Monte Carlo 
Dùng thủ tục Monte Carlo qua các bước sau:
1- Xác định độ đo thích hợp với hệ thống.
2- Mô tả hệ thống, xác định hàm phân bố xác suất của các đại
lượng ngẫu nhiên.
3- Xác định phân bố xác suất tích lũy qua các thí nghiệm.
4- Gán cho các đại lượng ngẫu nhiên các phân bố tương ứng.
5- Gán cho mỗi đại lượng ngẫu nhiên một giá trị nào đó.
6- Xác định trung bình và phương sai.
7- Lặp lại các bước 5-6 cho đến khi độ đo hệ thống ổn định.
8- Lặp lại các bước 5-7 với các giải pháp khác nhau, đưa ra các
độ đo đánh giá độ tin cậy. Từ đó chọn giải pháp thích hợp
TD Khang – ĐHBK Hà Nội
Ứng dụng
Mô phỏng mạng lưới giao thông
Mô phỏng quá trình dạy và học trong đào tạo
Mô phỏng các thí nghiệm vật lý, sinh học, các phản
ứng hóa học
Mô phỏng các hoạt động kinh tế, xã hội
TD Khang – ĐHBK Hà Nội
C/ Lập lịch
Phân phối tài nguyên theo thời gian để thực hiện một
tập các tác vụ, thỏa mãn một số ràng buộc
Cho: Một tập các tác vụ cần thực hiện, Một tập các tài
nguyên với sự xác định rõ tài nguyên nào dùng cho
tác vụ nào, Một tập các ràng buộc phải được thỏa
mãn, Một tập các mục tiêu với sự xác định mục tiêu
nào là của tác vụ nào
Cần xác định cách tốt nhất để phân phối tài nguyên cho
các hoạt động tại các thời điểm xác định, mà các ràng
buộc đều được thỏa mãn và đạt mục tiêu tốt nhất
TD Khang – ĐHBK Hà Nội
Các đặc tính
- Mỗi tác vụ được thực hiện theo nhiều cách, phụ thuộc vào
nguồn tài nguyên được phân cho nó
- Quan hệ tác vụ ưu tiên có thể bị chồng chéo
- Một tác vụ có thể bị ngắt theo một tập xác định trước
- Một tác vụ đòi hỏi nhiều nguồn tàinguyên của các loại khác
nhau
- Sự yêu cầu tài nguyên của một tác vụ có thể khác nhau qua thời
gian của tác vụ đó
- Các nguồn tài nguyên có thể tái sử dụng, hoặc không
- Tính sẵn dùng của tài nguyên có thể thay đổi
- Các tài nguyên có thể có những hạn chế tạm thời
- Các mục tiêu có thể thay đổi !
TD Khang – ĐHBK Hà Nội
Phân loại bài toán lập lịch
Phân xưởng xử lý đơn máy: mỗi công việc chỉ có một hoạt động
được thực hiện trên máy đơn, kết quả là một chuỗi công việc
Phân xưởng xử lý máy song song: mỗi công việc chỉ có một hoạt
động đơn, có m máy làm việc song song và chức năng của các
máy là như nhau
Phân xưởng xử lý theo luồng: mỗi công việc gồm một chuỗi (có
thứ tự chặt chẽ) các hoạt động, có m máy được điều khiển
đồng bộ
Bài toán tổng quát: có m máy và j công việc, mỗi công việc có
thứ tự xử lý của nó và không có quan hệ với thứ tự xử lý của
bất kỳ công việc nào khác
TD Khang – ĐHBK Hà Nội
Các kỹ thuật
Tìm kiếm cục bộ tiền định
Các kỹ thuật tính toán mềm
Giải thuật di truyền: mỗi phương án như là một cá
thể, độ thích nghi đo mức độ thỏa mãn các ràng
buộc của cá thể
TD Khang – ĐHBK Hà Nội
D/ Các kỹ thuật tính toán mềm
Mạng nơ ron
Giải thuật di truyền
Hệ mờ
Mạng Bayes
Suy diễn theo trường hợp
...
TD Khang – ĐHBK Hà Nội
Kết hợp mạng nơron và hệ mờ
Mô hình nơ ron - mờ hợp tác
Mô hình nơ ron - mờ lai
Mô hình nơ ron - mờ trên cơ sở hệ mờ
Mờ hóa mạng nơ ron
TD Khang – ĐHBK Hà Nội