Bài giảng Kỹ thuật ra quyết định kỹ sư - Chương 8: Quy hoạch động

 Lan , GVC. Ths.
Ba bước để giải bài toán 
h h độquy oạc ng:
• Chia bài toán ban đầu thành những bài 
ỗtoán nhỏ hơn, m i bài toán tương 
đương với một giai đoạn
• Xem xét tất cả các điều kiện và các 
trạng thái ở giai đoạn cuối  tìm lời giải 
tối ưu bắt đầu từ giai đoạn cuối
Giải bài t á bằ h há• o n ng p ương p p ngược 
dòng đi từ giai đoạn cuối trở về giai 
đoạn đầu tiên. Giai đoạn cuối cùng ký 
hiệ là 1 Xá đị h lời iải ối ở i iu . c n g t ưu g a 
đoạn n dựa vào lời giải tối ưu ở giai 
đoạn tiếp theo (n-1). Lời giải của bài 
ầ
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
toán được xác định khi giai đoạn đ u 
tiên đã được giải xong. 
Bài toán đường đi ngắn 
hấn t
Ví dụ 8.1
Mỗi ngày công ty xây dựng Kiến An cần 
phải vận chuyển vữa bê tông tươi từ 
hà á ả ấ ữ bê ô hn m y s n xu t v a t ng t ương 
phẩm Cửu Long đến công trường xây 
dựng nhà thi đấu Hoàn Hảo Hãy tìm . 
đường đi ngắn nhất từ nhà máy sản 
xuất vữa bê tông Cửu Long (nút 1) đến 
ô t ờ ( út 7) S đồ l ớic ng rư ng n . ơ mạng ư 
đường với chiều dài các nhánh đường 
như trong hình 
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán đường đi ngắn 
hấn t
10  2 5
 4 km
12 14
1 3 75
2 64 2
4 6
10
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán đường đi ngắn 
hấn t
Gọi 
• f(n,s): khoảng cách ngắn nhất hay chi phí 
vận chuyển thấp nhất khi di chuyển từ nút 
s đến nút cuối cùng ở giai đoạn n
• c(s,j): khoảng cách hay chi phí vận chuyển 
từ nút s đến nút j
• d(n s): các quyết định ở giai đoạn n (các, 
nút sẽ đi qua tư nút xuất phát s) 
• s: trạng thái, tương ứng với nút xuất phát 
trong giai đoạn n 
f(n,s) = min [C(s,j) + f(n-1,j)]
xét tất cả các nhánh đường xuất phát từ nút s
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán đường đi ngắn 
hấn t
10  2 5
 4 km
12 14
1 3 7 5
2 64 2
4 6
10 
giai đoạn 3 giai đoạn 2 giai đoạn 1
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán này có 3 giai đoạn
Bài toán đường đi ngắn 
hấn t
Bài toán này có 3 giai đoạn: 
• Giai đoạn 3 có một trạng thái (nút xuất 
phát là nút 1)
• Giai đoạn 2 có ba trạng thái (nút xuất 
phát là nút 2,3,4)
• Giai đoạn 1 có hai trạng thái (nút xuất 
phát là nút 5,6).
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán đường đi ngắn 
hấn t
Lời giải bài toán tìm đường đi ngắn nhất – 
giai đoạn 1
Trạng thái f(1,s) d(1,s)
5 14 7
6 2 7
 2 5
4 km
12 14
10
1 3 7 5
 2 6 4
10
 2
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
4 6
Bài toán đường đi ngắn nhất
Lời giải bài toán tìm đường đi ngắn nhất – 
giai đoạn 2
Trạng Quyết định f(2,s) d(2,s)
thái D(2,s)
nút 5 nút 6
4
3
4
12
10
6
+14
+14
+2
+2
12
8
6
6
2
2 510
10 +14 24 5
1 
 3
7
 4 km
 5
12 14
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.4 6 
 2 6 4
10
 2
Bài toán đường đi ngắn nhất
Lời giải bài toán tìm đường đi ngắn nhất –
giai đoạn 3
Trạng thái Quyết định D(3 s) f(3 s) d(3 s) , , ,
nút 4 nút 3 nút 2
1 2 5 4
Vậy lộ trình ngắn nhất đi từ nút 1 đến nút 7 là 1-3-6-7 
+12 +8 +24 13 3
2 510
với chiều dài là 13 km.
1 
 3
7
 4 km
 5
12 14
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.4 6 
 2 6 4
10
 2
Bài toán tận dụng sức chứa
Ví dụ 8.2 Công ty xây lắp Xalaco dùng 
một xe tải có trọng tải 7 tấn để chở 3 
loại cấu kiện nặng 1 tấn, 2 tấn, và 3 tấn. 
Tiền lời chở cấu kiện nặng 1 tấn là 
200.000 đồng, 2 tấn là 500.000 đồng và 
3 tấ là 800 000 đồ Nê hở b n . ng. n c ao 
nhiêu chiếc mỗi loại để được tiền lời 
nhiều nhất? 
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán tận dụng sức chứa
Gọi:
• n là số loại cấu kiện
• j: cấu kiện thứ j (j =1÷n) 
• w(j) là trọng lượng một cấu kiện loại j
• x(j) là số lượng cấu kiện loại j nên chở 
• R(j,x(j)) là tiền lời chở x(j) cấu kiện loại j
• g(j w) là tiền lời tích luỹ lớn nhất khi chở, 
cấu kiện loại j, j-1, , 1 khi trọng tải của 
xe còn w
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
 .
Bài toán tận dụng sức chứa
• Không có trình tự về thời gian ra quyết 
định nhưng có thể xem quyết định chở 
bao nhiêu cấu kiện loại j là một giai 
đoạn Lời giải tối ưu tương ứng với giá. 
trị tiền lời lớn nhất trong điều kiện trọng 
tải của xe dành để chở cấu kiện j, j-
1,,1 là w. Khi đã quyết định chở x(j) 
cấu kiện loại j thì trọng tải xe dành để 
chở cấu kiện j 1 1 chỉ còn là w - ,, -
w(j)x(j). 
g(j,w) = max [R(j,x(j)) + g(j-1,w-w(j)x(j))] 
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán tận dụng sức chứa
Giai đoạn 1: quyết định chở bao nhiêu 
ấ kiệ 1 tấc u n n
Trạng thái g(j,w)) x(j)
0 0 0
1 2 1
2 4 2
3 6 3
4 8 4
5 10 5
6 12 6
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.7 14 7
Giai đoạn 2: quyết định chở bao nhiêu
Bài toán tận dụng sức chứa
Trạng Quyết định (số lượng cấu g(j,w) x(j)
cấu kiện 2 tấn
thái
kiện)
0 1 2 3
0
1
0
20
0
+2
0
0
2
3
5
7
0
0
5
5
+4
+6 +2
1
1
4
5
10
12
0
0
5
5
10
10
+8
+10
+4
+6 +2
2
2
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
6
7
15
17
0
0
5
5
10
10
+12
+14
+8
+10
+4
+6
15
15+2
3
3
Bài toán tận dụng sức chứa
• Giai đoạn 3: quyết định chở bao nhiêu 
cấu kiện 3 tấn
Trạng 
thái
Quyết định (số lượng
cấu kiện)
g(j,w) x(j)
0 1 2
7 0 +17 8 16+10 +2 18 1 hay 2
Vậy nên chở một cấu kiện 3 tấn và hai cấu 
kiệ 2 tấ h hở h i ấ kiệ 3 tấ à ộtn n ay c a c u n n v m 
cấu kiện 1 tấn để được tiền lời nhiều nhất 
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài toán kế hoạch sản xuất 
à ồ ữv t n tr
• P(n): số lượng hàng được mua hay sản 
xuất trong thời đoạn n
• D(n): Nhu cầu tiêu thụ hàng trong thời 
đoạn n
• I(n-1): lượng hàng tồn trữ vào đầu thời 
đoạn (n-1) khi lượng hàng tồn trữ đầu 
thời đoạn n là I(n), I(n-1) = I(n) + P(n) – D 
(n) 
• S(n): chi phí chuẩn bị cho một đợt sản 
ấ ầ
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
xu t/chi phí đặt hàng cho một l n nhập 
hàng
Bài toán kế hoạch sản xuất 
à ồ ữv t n tr
• V(P(n),I(n)): chi phí sản xuất/mua sắm và tồn 
trữ hàng chi phí này là hàm số của lượng , 
hàng hoá tồn trữ và sản xuất/mua sắm trong 
thời đoạn n
ổ• C(n,P(n),I(n)): chi phí t ng cộng của thời 
đoạn n 
= S(n) + V(P(n) I(n)) nếu P(n)>0 , 
= V(P(n),I(n)) nếu P(n)=0 
• f(n,i): tổng chi phí mua sắm/sản xuất và tồn 
trữ từ thời đoạn 1 đến thời đoạn thứ n với 
mức tồn trữ đầu thời đoạn n là i 
f(n i)=min{C(n P(n) i+P(n) D(n))+f(n 1 i+P(n)
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
, , , - - , -
D(n))}
Bài toán kế hoạch sản xuất 
à ồ ữv t n tr
Ví dụ 8.3 Công ty xây dựng AMC có nhu cầu sử 
d ỗi thá ột bộ á l h t tâụng m ng m m y ạn rung m 
trong vòng 3 tháng tới. Mỗi đầu tháng cửa 
hàng điện lạnh Dilaco đều đến công ty AMC để 
chào hàng Công ty AMC có thể đặt mua số . 
lượng máy lạnh theo yêu cầu của tháng đó. Do 
chi phí vận chuyển, Dilaco đề nghị sẽ giảm giá 
bán tùy theo số lượng máy đặt mua. Nhưng 
nếu số máy đặt mua lớn hơn yêu cầu sử dụng 
trong tháng đó thì lại tốn kém chi phí bảo quản 
số máy dư chưa dùng đến. Biết rằng giá mua 
ột bộ á là 7 200$ từ h i bộ t ở lê thì hỉm m y . , a r n c 
phải trả thêm 7.000$ cho mỗi bộ mua thêm (vì 
chi phí cho một lần chuyên chở xem như là 
200$) chi phí tồn trữ một bộ máy trong vòng
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
, 
một tháng là 150$. Vậy công ty nên đặt mua 
máy như thế nào để giảm tối đa chi phí. 
Bài toán kế hoạch sản xuất 
à ồ ữv t n tr
• Bài toán chia làm ba thời đoạn (mỗi thời 
đoạn tương ứng 1 bài toán nhỏ ):
- Thời đoạn 1(n=1)  tháng thứ 3 
- Thời đoạn 2(n=2)  tháng thứ 2
- Thời đoạn 3(n=3)  tháng thứ 1 
 Lời giải cho bài toán là lời giải bài toán 
ở thời đoạn 3 (tháng thứ 1).
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
 Xét bài toán ở thời đoạn 1(n=1) (tháng 
thứ 3):
Gọi:
ồ ầ- i: là mức t n trữ ở đ u tháng thứ 3.(thời 
đoạn này i=0,1)
f(1 i): là tổng chi phí mua sắm và bảo- , 
quản hàng từ giai đoạn cuối cùng đến giai 
đoạn thứ n với mức tồn trữ đầu giai đoạn n 
là i ũ là tổ hi hí ắ à bả c ng ng c p mua s m v o 
quản ở tháng thứ 3 
- P(1): số máy được mua trong tháng 3
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
(giai đoạn 1)
Bài toán kế hoạch sản xuất 
à ồ ữv t n tr
• Giai đoạn 1: xét số lượng máy còn tồn 
trữ đầu tháng thứ 3
Trạng thái Quyết định f(1 i) P(1) ,
0
0 1
- 7,2 7 2 1
1 0 -
,
0 0
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
 Xét bài toán ở Thời đoạn 2 (n=1) (tháng 
thứ 2):
Gọi:
ồ ầ- i: là mức t n trữ ở đ u tháng thứ 2 (thời 
đoạn này i=0,1, 2)
f(2 i): là tổng chi phí mua sắm và bảo- , 
quản hàng từ thời đoạn cuối cùng đến thời 
đoạn thứ n với mức tồn trữ đầu thời đoạn n 
là i ũ là tổ hi hí ắ à bả c ng ng c p mua s m v o 
quản hàng ở tháng thứ 3 và tháng thứ 2
- P(2): số máy được mua trong tháng 2
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
(thời đoạn 2)
Bài toán kế hoạch sản xuất 
và tồn trữ 
• Giai đoạn 2: xét số lượng máy còn tồn 
trữ đầu tháng thứ 2 
Trạng 
thái
Quyết định f(2,i) P(2)
0 1 2
0
1
-
-(0+0)
(7,2+0)
(7,2+0,15)
(14,2+0,15)
+7,2 + 0
+7,2 + 0 14,35
7,2
2
0
2 - -(0+0,15) + 0 0,15 0
Trạng thái Quyết định f(1,i) P(1)
0 1
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
0
1
- 7,2
0 -
7,2
0 0
1
 Xét bài toán ở Thời đoạn 3 (n=3) (tháng 
thứ 1):
Gọi:
i: là mức tồn trữ ở đầu tháng thứ 1 (thời- . 
đoạn này i=0)
- f(3,i): là tổng chi phí mua sắm và bảo 
ả hà từ thời đ ối ù đế thờiqu n ng oạn cu c ng n 
đoạn thứ n với mức tồn trữ đầu thời đoạn n 
là i, là tổng chi phí mua sắm và bảo quản ở 
tháng thứ 3 tháng thứ 2 à tháng thứ 1  , v 
hàm mục tiêu của bài toán
- P(3): số máy được mua trong tháng 1 
(thời đ 3)
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
 oạn 
Bài toán kế hoạch sản xuất 
và tồn trữ 
• Giai đoạn 3: xét số lượng máy tồn trữ 
đầu tháng thứ 1 
Trạng 
thái
Quyết định f(3,i) P(3)
1 2 3
Trạng Quyết định f(2,i) P(2)
0 7,2 (14,2+0,15) (21,2+2x0,15)+14,35 +7,2 +0,15 21,55 1,2
thái 0
0
1 2
- (7,2+0) (14,2+0,15)+7,2 + 0 14,35 2
0
1
2 -
-
-
(0+0)
(0+0,15)
(7,2+0,15)+7,2 + 0
+ 0
7,2
0,15
0
©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Vậy: Mua một máy vào tháng thứ 1 và 2 máy vào tháng thứ 2 
hay mua 2 máy vào tháng thứ 1 và một máy vào tháng thứ 3