PHƯƠNG PHÁ
ĐỊNH BÁCH
LƯNGKHOA
TRONGTP.
QUẢ
N LÝ
TRƯỜNG
ĐẠIP HỌC
HCM
Chương 11: Quy hoạch động
Khoa KTXD - Bộ mơn KTTNN

Giảng viên: PGS. TS. NGUYỄN THỐNG
E-mail: or
Web: />Tél. (08) 38 691 592 - 098 99 66 719

1

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

NỘI DUNG MƠN HỌC
CHƯƠNG 1: Giới thiệu Phương pháp đònh
lượng trong Quản lý.
CHƯƠNG 2: Quy hoạch tuyến tính.
CHƯƠNG 3: Cơ sở lý thuyết ra quyết đònh.
CHƯƠNG 4: Bài toán vận tải.
CHƯƠNG 5: Quản lý kho.
CHƯƠNG 6: Ra quyết đònh đa mục tiêu.

CHƯƠNG 7: Lý thuyết sắp hàng.

2

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch độ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 q 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 PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Ngun lý tối ưu của Bellman
Ngun 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 PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Giải ngược dòng
BƯỚC 3

BƯỚC 2

BƯỚC

TUYẾN

KHOẢNG CÁCH

1

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

Giải ngược dòng

PGS. TS. Nguyễn Thống

7


PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch độ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

10

9
8

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động
Từ nút đến Khoảng cách
nút
(10 km)
1-2

5

1-3

4

2-4


10

2-5

4

3-5
3-6

11
6

6

Số liệu xem bảng sau
PGS. TS. Nguyễn Thống

Đáp số: 1-2-5-8-9  19km

1-3
3-6
6-7

PGS. TS. Nguyễn Thống

7

3

Tuyến tương ứng


9

4

5

Khoảng cách
min đến 7
13

Lời giải cho đường đi tối ưu (ngắn nhất)

Bài tập 1: Xét mạng lưới giao thông sau. Dùng
p/pháp QHĐ, xác đònh đường đi ngắn nhất từ 1
đến 9.

1

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động
Bước 3
Nút bắt đầu

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

2

8


PGS. TS. Nguyễn Thống

11

PGS. TS. Nguyễn Thống

Từ nút đến
nút

Khoảng cách
(10 km)

4-7

2

4-8

4

5-7

12

5-8
6-7

6
6


6-8

10

7-9

6

8-9

4

12

2


PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Bài tập 2: Xét mạng lưới giao thông sau. Dùng
p/pháp QHĐ, xác đònh đường đi ngắn nhất từ 1
đế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 PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Bài tập 3: Xác đònh tia điều tiết bằng p/p Đường
chỉ thẳng trong tính toán thủy năng.
Trong tính tố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 PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch độ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 <= 300000 s.phẩm/năm
* B <= 500000 s.phẩm/năm
* C <= 200000 s.phẩm/năm
Do u cầu sản xuất theo dây chuyền, chỉ
sản xuất từng lơ hàng 100000 sản phẩm.
Lợi nhuận mang lại cho từng loại sản phẩm
xem bảng sau:
17

PGS. TS. Nguyễn Thống

200

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động
Lợi nhuận hiện tại ròng (NPV)

Sản phẩm
tiêu thụ

(100000 đv)
0
1
2
3
4
5

A
-500
500
1300
2200

B
-300
650
1450
2200
2800
3300

C
-100
350
1650

Xác định phương án sản xuất mang về
lợi nhuận lớn nhất ?
18

PGS. TS. Nguyễn Thống

3


PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Lời giải: Xét trường hợp chỉ sản xuất A&B
SẢN XUẤT TỔNG
0

SẢN 1
XUẤT
2
B
3

0
-500
-300

1
500
-300
-500
650


Max !

2
1300
-300
500
650
-500
1450

3
2200
-300
1300
650
500
1450
-500
2200

4

2200
650
1300
1450
500
2200
-500

2800

4
5

Profits

-800

200

1150

1950

SẢN XUẤT TỔNG  C+[A+B]

5

2850

2200
1450
1300
2200
500
2800
-500
3300
3650 19


PGS. TS. Nguyễn Thống

SẢN
XUẤT
C

0

0

1

2

3

4

5

-800

200

1150

1950

2850


3650

-100

-100

-100

-100

-100

-100

-800

200

1150

1950

2850

1

350

2

Profit -900
total

100

350

350

350

350

-800

200

1150

1950

1650

1650

1650

1650

1050


1850

2800

3600
20

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động
Có 2 lời giải cho cùng kết quả kinh doanh lớn nhất
là 3600$:
- Lời giải 1:
A 100000 đ/v

B 200000 đ/v
C 200000 đ/v
- Lời giải 2:

A 200000 đ/v
B 100000 đ/v
C 200000 đ/v

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Bài tập: Hãy thiết lập bài
tóan trên dưới dạng bài

tốn quy tuyến tính (quy
hoạch nhị ngun). Dùng
Solver trong Excel để giải.

21

PGS. TS. Nguyễn Thống

22

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Hướng dẫn:

Bài tập 6: Bài tốn đầu tư.

Gọi Xi{0,1} là các biến quyết
định với i=1,13 (=0: khơng chọn, =1: chọn).
Hàm mục tiêu: F 
X



i


i

i

Ràng buộc:
4

 Xi 1
i 1

10

X
i 5

i

1

13

X
i 11

1

i

13


 X
i 1

i

i

5

Một nghiên cứu thị trường được thực hiện cho 4
ngành khác nhau A, B, C, D. Lợi nhuận dự kiến
theo giá trị đầu tư được tính và cho kết quả
trong bảng sau. Giả thiết rằng chủ đầu tư chỉ
chấp nhận cho phương án đầu tư có suất thu lợi
năm ít nhất là 20%.
Xác định các phương án đấu tư có thể theo thứ tự
hiệu quả cao nhất đến thấp nhất.
(Xem Excel: Solver_QHDong)

23

PGS. TS. Nguyễn Thống

24

PGS. TS. Nguyễn Thống

4



PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động
Đầu tư
(triệu $)
0
1
2
3
4
5
6
7
8
9
10

A
f1

B
f2

C
f3

D
f4

0

0.28
0.45
0.65
0.78
0.9
1.02
1.13
1.23
1.32
1.38

0
0.25
0.41
0.55
0.65
0.75
0.8
0.85
0.88
0.9
0.9

0
0.15
0.25
0.4
0.5
0.62
0.73

0.82
0.9
0.96
1

0
0.2
0.33
0.42
0.48
0.53
0.56
0.58
0.6
0.6
0.6

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

HƯỚNG DẪN
PHƯƠNG TRÌNH XÁC ĐỊNH TỐI ƯU
KHI CHỈ CÓ A & B

Bước 1  F1,2(T)=Max[f1(x)+f2(T-x)]
T : Tổng đầu tư
Hàm lợi nhuận
x  đầu tư vào lĩnh vực A
Hàm lợi nhuận
của A


của B

25

PGS. TS. Nguyễn Thống

26

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

HƯỚNG DẪN

HƯỚNG DẪN

PHƯƠNG TRÌNH XÁC ĐỊNH TỐI ƯU
KHI CHỈ CÓ C & [A+B]

PHƯƠNG TRÌNH XÁC ĐỊNH TỐI ƯU
KHI CÓ D+[C+A+B]

Bước 2  F1,2,3(T)=Max[F1,2(x)+f3(T-x)]
Kết quả bước 1
T : Tổng đầu tư

x  đầu tư vào lĩnh vực [A+B]

Bước 3  F1,2,3,4(T)=Max[F1,2,3(x)+f4(T-x)]
T : Tổng đầu tư
Kết quả bước 2
x  đầu tư vào lĩnh vực [A+B+C]

Hàm lợi nhuận
của C

27

PGS. TS. Nguyễn Thống

PGS. TS. Nguyễn Thống

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

Ví dụ: Điều tiết tối ưu hồ chứa thủy điện:
- Max điện năng trung bình.
- Max doanh thu (hồ chứa phục vụ nhiều mục
tiêu: phát điện, cấp nước, nông nghiệp,…).
Mực nước hồ BT

Mực nước hồ BT

Mực nước hồ j

Mực nước hồ j


Mực nước hồ j-1

Mực nước hồ j-1

Hàm lợi nhuận
của D

28

PHƯƠNG PHÁP ĐỊNH LƯNG TRONG QUẢN LÝ
Chương 11: Quy hoạch động

HẾT CHƯƠNG
QUY HOẠCH ĐỘNG

Mực nước hồ MNC Mực nước hồ MNC
0

t-2

PGS. TS. Nguyễn Thống

t-1

t

Bài toán truy ngược

t=T


29

30

PGS. TS. Nguyễn Thống

5