Xem mẫu
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM
Chương 11: Quy hoaïch ñoäng
Khoa KTXD - Bộ môn KTTNN
Giảng viên: PGS. TS. NGUYỄN THỐNG
E-mail: nthong56@yahoo.fr or nguyenthong@hcmut.edu.vn
Web: http://www4.hcmut.edu.vn/~nguyenthong/index
Tél. (08) 38 691 592 - 098 99 66 719
1
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
NỘI DUNG MÔN HỌC
CHƯƠNG 1: Giôùi thieäu Phöông phaùp ñònh
löôïng trong Quaûn lyù.
CHƯƠNG 2: Quy hoaïch tuyeán tính.
CHƯƠNG 3: Cô sôû lyù thuyeát ra quyeát ñònh.
CHƯƠNG 4: Baøi toaùn vaän taûi.
CHƯƠNG 5: Quaûn lyù kho.
CHƯƠNG 6: Ra quyeát ñònh ña muïc tieâu.
CHƯƠNG 7: Lyù thuyeát saép haøng.
2
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
NỘI DUNG MÔN HỌC (tt)
Qui Hoạch Động được Richard Bellman đã
đề ra phương pháp (QHĐ) năm 1957.
QHĐ là phương pháp thích hợp tìm
nghiệm cho các quá trình dạng một chuỗi
các quyết định tuần tự theo không gian
hoặc thời gian.
Chương 8: Phân tích thành phần chính (PCA).
Chương 9: Kiểm định Cronbach’s Alpha &
KMO
Chương 10: Phương pháp AHP
Chương 11: Qui hoạch động
Chương 12: Hoạch định dự án
Chương 13: Xích Markov
Chương 14: Lý thuyết trò chơi.
Chương 15: Mô phỏng Monte Carlo.
1/6/2016
3
4
PGS. TS. Nguyễn Thống
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Nguyên lý tối ưu của Bellman
Nguyên lý tối ưu của Bellman được phát
biểu như sau: “Một sách lược tối ưu có đặc
tính là dù cho các trạng thái và các quyết
định trước đây như thế nào thì các quyết
định ở những bước tiếp theo phải tạo thành
một sách lược tối ưu đối với các trạng thái
được hình thành từ những quyết định trước
đây”.
VÍ DỤ: Xét một mạng lưới giao thông sau. Xác
định đường đi ngắn nhất từ LakeCity đến
Dixiville.
4km
12km Athène
LakeCity
Brow
5km
2km
5
PGS. TS. Nguyễn Thống
Virgine 10km
6km
4km
Hope
14km
Dixiville
Georgtow 2km
10km
6
PGS. TS. Nguyễn Thống
1
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Giải ngược dòng
BƯỚC 3
TUYẾN
KHOẢNG CÁCH
1
BƯỚC 2
BƯỚC
5-7
6-7
4-5
3-5
3-6
2-5
2-6
1-4
1-3
1-2
14
2
10
12
6
4
10
4
5
2
BƯỚC 1
2
10km
4
4km
12km
3
1
5km
2
14km
6
2km
7
6km
4km
2km
5
3
10km
Giaûi ngöôïc doøng
PGS. TS. Nguyễn Thống
7
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
• BẮT ĐẦU NGƯỢC DÒNG
Nút bắt đầu Khoảng cách
min đến 7
Bước 1
5
14
6
2
Nút bắt đầu Khoảng cách
min đến 7
Bước 2
4
24
3
8
2
12
PGS. TS. Nguyễn Thống
Tuyến tương
ứng
5-7
6-7
Tuyến tương
ứng
4-5
5-7
3-6
6-7
2-6
6-7
1
1-3
3-6
6-7
10
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Từ nút đến Khoảng cách
nút
(10 km)
1-2
5
1-3
4
Từ nút đến
nút
Khoảng cách
(10 km)
4-7
2
5
9
2-4
2-5
4
3-5
3-6
8
10
11
6
Soá lieäu xem baûng sau
Ñaùp soá: 1-2-5-8-9 19km
11
PGS. TS. Nguyễn Thống
4-8
4
5-7
7
6
PGS. TS. Nguyễn Thống
Tuyến tương ứng
9
4
3
Khoảng cách
min đến 7
13
Lời giải cho đường đi tối ưu (ngắn nhất)
Baøi taäp 1: Xeùt maïng löôùi giao thoâng sau. Duøng
p/phaùp QHÑ, xaùc ñònh ñöôøng ñi ngaén nhaát töø 1
ñeán 9.
1
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bước 3
Nút bắt đầu
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
2
8
PGS. TS. Nguyễn Thống
12
5-8
6-7
6
6
6-8
10
7-9
6
8-9
4
12
2
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Baøi taäp 2: Xeùt maïng löôùi giao thoâng sau. Duøng
p/phaùp QHÑ, xaùc ñònh ñöôøng ñi ngaén nhaát töø 1
ñeán 10.
12
5
16
2
13
12
10
18
9 18
10
10
15
6
9
25
1 8 3
12
8
20
12 4
14
14
8
7
ÁP DỤNG QUY HOẠCH ĐỘNG XÁC
ĐỊNH TIA ĐIỀU TIÊT CỦA
P/P ĐƯỜNG CHỈ THẰNG
Tìm đường thẳng ngắn nhất từ ĐẦU đến
CUỐI của tia lưu lượng.
13
PGS. TS. Nguyễn Thống
14
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bài tập 3: Xaùc ñònh tia ñieàu tieát baèng p/p Ñöôøng
chæ thaúng trong tính toaùn thuûy naêng.
Trong tính toán thủy năng hồ chứa thủy điện, xác
định lưu lượng điều tiết có thể dùng phương
pháp đường chỉ thẳng. Thực chất phương pháp
này là tìm đưòng đi ngắn nhất từ đầu đến cuối
chuỗi lưu lượng trong toạ độ xiên (dạng đường
gãy khúc, tựa trên các đáy hoặc đỉnh các đường
lũy tích hoặc đường bổ trợ). Phương pháp có thể
minh họa bởi đồ thị sau:
15
PGS. TS. Nguyễn Thống
W (tr. m3)
§-êng lòy tÝch dßng ch¶y
®Õn trong täa ®é xiªn
Whi
T (th)
0
1
13
A
25
37
49
61
-200
B
-400
Tia ®iÒu tiÕt
theo §CT
-600
Đường bổ trợ
-800
16
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bài tập 4: Chiến lược sản xuất kinh doanh
Một nhà sản xuất máy gia dụng lọai A, B, C:
- Khả năng sản xuất: 500000 đ/v (bất kỳ lọai)
- Kết quả nghiên cứu thị trường:
* A
nguon tai.lieu . vn
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM
Chương 11: Quy hoaïch ñoäng
Khoa KTXD - Bộ môn KTTNN
Giảng viên: PGS. TS. NGUYỄN THỐNG
E-mail: nthong56@yahoo.fr or nguyenthong@hcmut.edu.vn
Web: http://www4.hcmut.edu.vn/~nguyenthong/index
Tél. (08) 38 691 592 - 098 99 66 719
1
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
NỘI DUNG MÔN HỌC
CHƯƠNG 1: Giôùi thieäu Phöông phaùp ñònh
löôïng trong Quaûn lyù.
CHƯƠNG 2: Quy hoaïch tuyeán tính.
CHƯƠNG 3: Cô sôû lyù thuyeát ra quyeát ñònh.
CHƯƠNG 4: Baøi toaùn vaän taûi.
CHƯƠNG 5: Quaûn lyù kho.
CHƯƠNG 6: Ra quyeát ñònh ña muïc tieâu.
CHƯƠNG 7: Lyù thuyeát saép haøng.
2
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
NỘI DUNG MÔN HỌC (tt)
Qui Hoạch Động được Richard Bellman đã
đề ra phương pháp (QHĐ) năm 1957.
QHĐ là phương pháp thích hợp tìm
nghiệm cho các quá trình dạng một chuỗi
các quyết định tuần tự theo không gian
hoặc thời gian.
Chương 8: Phân tích thành phần chính (PCA).
Chương 9: Kiểm định Cronbach’s Alpha &
KMO
Chương 10: Phương pháp AHP
Chương 11: Qui hoạch động
Chương 12: Hoạch định dự án
Chương 13: Xích Markov
Chương 14: Lý thuyết trò chơi.
Chương 15: Mô phỏng Monte Carlo.
1/6/2016
3
4
PGS. TS. Nguyễn Thống
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Nguyên lý tối ưu của Bellman
Nguyên lý tối ưu của Bellman được phát
biểu như sau: “Một sách lược tối ưu có đặc
tính là dù cho các trạng thái và các quyết
định trước đây như thế nào thì các quyết
định ở những bước tiếp theo phải tạo thành
một sách lược tối ưu đối với các trạng thái
được hình thành từ những quyết định trước
đây”.
VÍ DỤ: Xét một mạng lưới giao thông sau. Xác
định đường đi ngắn nhất từ LakeCity đến
Dixiville.
4km
12km Athène
LakeCity
Brow
5km
2km
5
PGS. TS. Nguyễn Thống
Virgine 10km
6km
4km
Hope
14km
Dixiville
Georgtow 2km
10km
6
PGS. TS. Nguyễn Thống
1
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Giải ngược dòng
BƯỚC 3
TUYẾN
KHOẢNG CÁCH
1
BƯỚC 2
BƯỚC
5-7
6-7
4-5
3-5
3-6
2-5
2-6
1-4
1-3
1-2
14
2
10
12
6
4
10
4
5
2
BƯỚC 1
2
10km
4
4km
12km
3
1
5km
2
14km
6
2km
7
6km
4km
2km
5
3
10km
Giaûi ngöôïc doøng
PGS. TS. Nguyễn Thống
7
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
• BẮT ĐẦU NGƯỢC DÒNG
Nút bắt đầu Khoảng cách
min đến 7
Bước 1
5
14
6
2
Nút bắt đầu Khoảng cách
min đến 7
Bước 2
4
24
3
8
2
12
PGS. TS. Nguyễn Thống
Tuyến tương
ứng
5-7
6-7
Tuyến tương
ứng
4-5
5-7
3-6
6-7
2-6
6-7
1
1-3
3-6
6-7
10
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Từ nút đến Khoảng cách
nút
(10 km)
1-2
5
1-3
4
Từ nút đến
nút
Khoảng cách
(10 km)
4-7
2
5
9
2-4
2-5
4
3-5
3-6
8
10
11
6
Soá lieäu xem baûng sau
Ñaùp soá: 1-2-5-8-9 19km
11
PGS. TS. Nguyễn Thống
4-8
4
5-7
7
6
PGS. TS. Nguyễn Thống
Tuyến tương ứng
9
4
3
Khoảng cách
min đến 7
13
Lời giải cho đường đi tối ưu (ngắn nhất)
Baøi taäp 1: Xeùt maïng löôùi giao thoâng sau. Duøng
p/phaùp QHÑ, xaùc ñònh ñöôøng ñi ngaén nhaát töø 1
ñeán 9.
1
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bước 3
Nút bắt đầu
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
2
8
PGS. TS. Nguyễn Thống
12
5-8
6-7
6
6
6-8
10
7-9
6
8-9
4
12
2
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Baøi taäp 2: Xeùt maïng löôùi giao thoâng sau. Duøng
p/phaùp QHÑ, xaùc ñònh ñöôøng ñi ngaén nhaát töø 1
ñeán 10.
12
5
16
2
13
12
10
18
9 18
10
10
15
6
9
25
1 8 3
12
8
20
12 4
14
14
8
7
ÁP DỤNG QUY HOẠCH ĐỘNG XÁC
ĐỊNH TIA ĐIỀU TIÊT CỦA
P/P ĐƯỜNG CHỈ THẰNG
Tìm đường thẳng ngắn nhất từ ĐẦU đến
CUỐI của tia lưu lượng.
13
PGS. TS. Nguyễn Thống
14
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bài tập 3: Xaùc ñònh tia ñieàu tieát baèng p/p Ñöôøng
chæ thaúng trong tính toaùn thuûy naêng.
Trong tính toán thủy năng hồ chứa thủy điện, xác
định lưu lượng điều tiết có thể dùng phương
pháp đường chỉ thẳng. Thực chất phương pháp
này là tìm đưòng đi ngắn nhất từ đầu đến cuối
chuỗi lưu lượng trong toạ độ xiên (dạng đường
gãy khúc, tựa trên các đáy hoặc đỉnh các đường
lũy tích hoặc đường bổ trợ). Phương pháp có thể
minh họa bởi đồ thị sau:
15
PGS. TS. Nguyễn Thống
W (tr. m3)
§-êng lòy tÝch dßng ch¶y
®Õn trong täa ®é xiªn
Whi
T (th)
0
1
13
A
25
37
49
61
-200
B
-400
Tia ®iÒu tiÕt
theo §CT
-600
Đường bổ trợ
-800
16
PGS. TS. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 11: Quy hoaïch ñoäng
Bài tập 4: Chiến lược sản xuất kinh doanh
Một nhà sản xuất máy gia dụng lọai A, B, C:
- Khả năng sản xuất: 500000 đ/v (bất kỳ lọai)
- Kết quả nghiên cứu thị trường:
* A