Trường ðại học Nông nghiệp Hà Nội – Giáo trình Vận trù học
……………………………… 210f
2
(x
3
/z
2
) = C
2
(z
2
) + h
2
x
3
+ f
1
(x
3
+ D
2
- z
2
))
z
2
= 0 1 2 3 4 5 6
Phương án

3 4 3 3 3 4 2 4 3 3
0 z D x
f (x ) C (z ) h x f (x D z )
Min
≤ ≤ +
= + + + − , D
3
= 4, x
4
= 0.
K
ết quả tính toán ñược thể hiện trong bảng VII.7.
Bảng VII.7. Kết quả tính toán giai ñoạn 3
f
3
(x
4
/z
3
) = C
3
(z
3
) + h
3
x
4
+ f
2
(x

0 0 123 116 103 99 106 99 3
Kết quả cuối cùng: giá trị của các biến ñiều khiển là
1
z
∗
= 2,
2
z
∗
= 3,
3
z
∗
= 3. Như
vậy ñể tổng chi phí dự trữ hàng thấp nhất (là 99 USD), trong các giai ñoạn 1, 2 và 3 cần
ñặt các lượng hàng tối ưu theo thứ tự là 2, 3, 3.
Chú ý: Khối lượng tính toán theo quy trình truy toán tiến như trình bày trên ñây có
thể ñược rút gọn rất ñáng kể trong trường hợp hàm chi phí mua hàng/ñơn vị và chi phí
lưu kho/ñơn vị là hằng số hoặc là hàm giảm. Bạn ñọc quan tâm có thể xem thêm trong
các tài liệu tham khảo.
3. MÔ HÌNH LẬP KẾ HOẠCH SẢN XUẤT N CHU KÌ
Xét bài toán lập kế hoạch sản xuất cho N chu kì kế tiếp nhau. Nhu cầu tiêu thụ hàng
trong từng chu kì ñã ñược biết và không nhất thiết phải như nhau. Mô hình ñược xem
xét nhằm giảm tổng chi phí sản xuất và chi phí dự trữ hàng với các giả thiết sau:
− Trường hợp 1: Không cho phép ñể xảy ra tình trạng nợ hàng. Trường hợp 2: Cho
phép nợ hàng và hàng nợ ñược chuyển sang các chu kì sau, nhưng phải trả xong trong
phạm vi thời gian N chu kì.
− Chi phí khởi ñộng lại (dây chuyền sản xuất) ñược coi là bằng 0.
Chúng ta sử dụng các kí hiệu sau cho các chu kì i, i =1, 2, , N:


sản xuất) là hàm lồi.
3.1. Mô hình lập kế hoạch không cho phép nợ hàng
Chúng ta phát biểu lại mô hình với các thuật ngữ của bài toán vận tải (Xem bảng
VII.8): Các lượng cung là a
Ri
và a
Ti
còn các lượng cầu là b
i
. Các chi phí vận chuyển từ
ñiểm cung tới ñiểm cầu là tổng của các chi phí sản xuất và chi phí lưu kho. Cột hàng
thừa ñược dùng ñể cân bằng tổng cung cầu với S =
Ri Ti j
i j
(a a ) b
+ −
∑ ∑
. ðiều này ñược
coi là hợp lí vì chúng ta giả sử rằng khả năng sản xuất của hệ thống luôn ñáp ứng ñược
(lớn hơn) tổng nhu cầu tiêu thụ hàng trong cả N chu kì.
Bảng VII.8. Tổng hợp dữ liệu
(cho bài toán lập kế hoạch sản xuất không cho phép nợ hàng)
1 2 3 … N Cột dư
R
1
c
1
c
1
+h

2
d
1
+h
1
+…+h
N
-
1
0 a
T1
R
2
c
2
c
2
+h
2
c
2
+h
2
+…+h
N
-
1
0 a
R2
T

b
1
b
2
b
3
b
N
S
Do mô hình không cho phép nợ hàng, chúng ta cần có giả thiết:

( )
k k
Ri Ti i
i 1 j 1
a a b
= =
+ ≥
∑ ∑
v
ớ
i k = 1, 2, , N.
Trường ðại học Nông nghiệp Hà Nội – Giáo trình Vận trù học
……………………………… 212Ngoài ra, do nhu c
ầ
u b
i

ậ
t toán
ñể
gi
ả
i bài toán l
ậ
p k
ế
ho
ạ
ch
ñượ
c phát bi
ể
u v
ắ
n t
ắ
t
nh
ư
sau (theo thu
ậ
t ng
ữ
c
ủ
a bài toán v
ậ

ấ
t.
−
C
ậ
p nh
ậ
t l
ạ
i b
ả
ng v
ậ
n t
ả
i (v
ớ
i các kh
ả
n
ă
ng còn d
ư
)
ñể

ñ
áp
ứ
ng nhu c

i khi nhu c
ầ
u tiêu th
ụ
hàng c
ủ
a chu kì N
ñượ
c
th
ỏ
a mãn.
Ví dụ 1: Xét bài toán lập kế hoạch sản xuất với 4 chu kì và các dữ liệu ñược tổng
hợp trong bảng VII.9. Còn kế hoạch sản xuất tối ưu ñược cho trong bảng VII.10.
Bảng VII.9. Tổng hợp dữ liệu
Khả năng sản xuất
(ñơn vị hàng)
Chu kì
i
a
Ri
a
Ti
Nhu cầu tiêu
thụ hàng b
i
1 100 50 120
2 150 80 200
3 100 100 250
4 200 50 200

3.30
10

50 30 10

R
2

2
150

2.1 2.2

0

150

T
2

3
50

3.1
30

3.2

200

0

200T
4

3

0
50

50

120
20

200
50

250
150
50
20

200


một cách tương ứng. Tuy nhiên ñể ñưa ra phương án lập kế hoạch tối ưu lúc này cần áp
dụng một trong các thuật toán giải bài toán vận tải ñã biết ở chương II (thuật toán ñược
ñưa ra ở mục A không dùng ñược).
Ví dụ 2: Xét bài toán lập kế hoạch sản xuất với 3 chu kì và các dữ liệu ñược tổng
hợp trong bảng VII.11. Ngoài ra, cũng biết chi phí sản xuất trong giờ làm việc là 5/ñơn
vị và ngoài giờ làm việc là 10/ñơn vị (trong cả ba chu kì). Các chi phí lưu kho và chi phí
phát sinh do nợ hàng là 1 và 2 cho một ñơn vị hàng (trong cả ba chu kì). Còn kế hoạch
sản xuất tối ưu ñược cho trong bảng VII.12.
Bảng VII.11. Tổng hợp dữ liệu
Khả năng sản xuất
(ñơn vị hàng)
Chu kì
i
a
Ri
a
Ti
Nhu cầu tiêu
thụ hàng b
i
1 15 10 20
2 15 0 35
3 20 15 15
Bảng VII.12. Kế hoạch sản xuất tối ưu
1 2 3 Cột dư
R
1
5
15


9 7
5
5
15

0
20
T
3
14 12
10
10

0
5

15
20

35

15

5
4. MỘT SỐ MÔ HÌNH XÁC SUẤT TRONG QUẢN LÍ HÀNG DỰ TRỮ
Trường ðại học Nông nghiệp Hà Nội – Giáo trình Vận trù học
……………………………… 2144.1. Mô hình xác suất với chế ñộ báo cáo theo dõi thường xuyên

sinh do nợ hàng/năm), trong ñó:
− Kì vọng chi phí ñặt hàng/năm = DK/y.
− Kì vọng chi phí lưu kho/năm: ðặt
H
=
(y E{R-X})+E{R-X} y
E{R-X}
2 2
+
= +
là
mức hàng trung bình trong kho/năm. Do kì vọng hàng tồn kho cuối mỗi chu kì là

0
E{R - X} = (R-x)f(x)dx = R - E{X}
∞
∫
nên kì vọng chi phí lưu kho/năm là h
H
=
y
h R E{X}
2
 
+ −
 
 
.
− Kì v
ọ

ế
u/chu kì hàng là
S
=
0 R
S(x)f (x)dx (x R)f (x)dx
∞ ∞
= −
∫ ∫
. Do hàng n
ă
m có
trung bình (D/y) l
ầ
n
ñặ
t hàng nên kì v
ọ
ng chi phí phát sinh do n
ợ
hàng/n
ă
m là p(D
S
/y).
V
ậ
y t
ổ
ng chi phí d

ng hàng
thi
ế
u, mà không ph
ụ
thu
ộ
c vào th
ờ
i gian thi
ế
u hàng nh
ằ
m m
ụ
c
ñ
ích
ñơ
n gi
ả
n hóa mô
hình.
ð
i
ề
u ki
ệ
n c
ầ

∂

∫

T
ừ
ph
ươ
ng trình
ñầ
u s
ẽ
có: y* =
2D(K pS) / h
+
(*).
Còn t
ừ
ph
ươ
ng trình th
ứ
hai s
ẽ
có:
R
hy
f (x)dx
pD
∗

ộ
t s
ố
h
ữ
u h
ạ
n b
ướ
c n
ế
u h
ệ
có nghi
ệ
m)
theo các b
ướ
c sau:
− Trong (*) cho
S
= 0 (ho
ặ
c cho R = ∞) thì có y* =
2DK / h
.
− Cho R = 0 thì t
ừ
(*) có y* =
ˆ

ồ
n
t
ạ
i duy nh
ấ
t.
−
ðặ
t y* = y
1
=
2DK / h
và thay vào (**)
ñể
tìm
ñượ
c R* = R
1
.
− D
ự
a vào giá tr
ị
R* = R
1
, thay vào (*)
ñể
tìm
ñượ

ị
liên ti
ế
p tìm
ñượ
c c
ủ
a R
là g
ầ
n b
ằ
ng nhau. L
ấ
y giá tr
ị
trung bình c
ủ
a hai giá tr
ị
này là giá tr
ị
cu
ố
i cùng c
ủ
a R*,
sau
ñ
ó tính ti

y y
≥
%
nên các giá trị tối ưu y* và R* là tồn tại duy
nhất.
Tính
S
=
R
(x R)f (x)dx
∞
−
∫
=
R
1
(x R) dx
100
∞
−
∫
=
2
R
R 50
200
− +
.
T
ừ

∗
− (****).
Áp d
ụ
ng ph
ươ
ng trình (****)
ñể
tính R
i
khi
ñ
ã bi
ế
t y
i
và ph
ươ
ng trình

(***)
ñể
tính
y
i+1
khi
ñ
ã bi
ế
t R

R 50
200
− +
= 0,199971
y
2
=
100000 10000 0,199971
+ ×
= 319,37
R
2
= 100 -
319,37
50
= 93,612.
B
ướ
c l
ặ
p 3:
S
=
2
2
2
R
R 50
200
− +

H(y)
0,
−

=



khi D y
khi D y,
<
≥

còn lượng hàng thiếu là

0
G(y)
D y,

=

−


khi D y
khi D y.
<
≥

Gọi x là lượng hàng tồn kho trước khi ñặt hàng, f(D) là hàm mật ñộ xác suất của D,

 
+ −
 
 
 
∫

= c(y-x) + h
y
0
(y D)f (D)dD
−
∫
+ p
y
(D y)f (D)dD
∞
−
∫
.
Giá tr
ị
t
ố
i
ư
u y* ph
ả
i th
ỏ

y
y 0
f(D)dD = 1- f(D)dD
∞
∫ ∫
nên t
ừ
(*) s
ẽ
có:
y
0
p c
f (D)dD
p h
∗
−
=
+
∫
(**). V
ậ
y y*
ñượ
c
xác
ñị
nh n
ế
u p ≥ c, còn n

(**)
ñ
úng là
ñ
i
ể
m c
ự
c ti
ể
u do
ñ
i
ề
u ki
ệ
n
ñủ
(
ñạ
o hàm b
ậ
c hai
d
ươ
ng)
ñượ
c th
ỏ
a mãn:

q = (p-c)/(p+c), t
ứ
c là P{D ≤ y*} = (p-c)/(p+c). V
ớ
i x là l
ượ
ng hàng t
ồ
n
kho tr
ướ
c khi
ñặ
t hàng, chính sách
ñặ
t hàng t
ố
i
ư
u là:
− N
ế
u y* > x thì
ñặ
t l
ượ
ng hàng y* - x.
− N
ế
u y* ≤ x thì không c

−
∑
.
ð
i
ề
u ki
ệ
n
ñể
E{C(y)}
ñạ
t c
ự
c ti
ể
u là:

E{C(y 1)} E{C(y)}
E{C(y 1)} E{C(y)}.
− ≥


+ ≥


Do E{C(y-1)} = E{C(y)} + p - c - (h+p)
y 1
D 0
f (D)

⇔
P{D
≤
y}
≥
(p-c)/(p+h).
V
ậ
y
quy tắc tìm y*
là: y* ph
ả
i th
ỏ
a mãn: P{D
≤
y*-1}
≤
(p-c)/(p+h)
≤
P{D
≤
y*}.
Ví dụ 3: Xét mô hình một chu kì với h = 1,0 USD, p = 4,0 USD và c = 2,0 USD.
Phân phối xác suất của D như sau:
D 0 1 2 3 4 5
f(D) 0,10 0,20 0,25 0,20 0,15 0,10
Lúc ñó: q = (p-c)/(p+h) = 0,4. Lượng ñặt hàng tối ưu ñược dò tìm từ bảng sau:
y 0 1 2 3 4 5
P(D ≤ y)

y
f (D)dD
2D
∞
 
 
 
 
 
∫
.
B
ạ
n
ñọ
c có th
ể
t
ự
gi
ả
i thích công th
ứ
c này d
ự
a trên các nh
ậ
n xét sau:
−
N


y-D
D

y

y/2

D-y

D

x
2

x
1Hình VII.6a. ðồ thị mức hàng khi D < y Hình VII.6b. ðồ thị mức hàng khi D > y
ð
i
ề
u ki
ệ
n c
ầ
n
ñể
E{C(y)}

D y
f (D)dD
D
∞
 
−
 
 
∫
= 0,
hay
y
0
y
f (D)
f (D)dD y dD
D
∗
∗
∞
∗
+
∫ ∫
=
p c
p h
−
+
= q.
Ví dụ 4: Xét mô hình một chu kì với h = 0,5 USD, p = 4,5 USD và c = 0,5 USD.

ng t
ổ
ng chi phí d
ự
tr
ữ
hàng bao g
ồ
m c
ả
chi phí kh
ở
i
ñộ
ng l
ạ
i, ta có:
E{
C
(y)} = K + c(y-x) + h
y
0
(y D)f (D)dD
−
∫
+ p
y
(D y)f (D)dD
∞
−

ñạ
t c
ự
c ti
ể
u):

y
0
p c
f (D)dD
p h
∗
−
=
+
∫
.
ðồ
th
ị
các hàm s
ố
E{C(y)} và E{
C
(y)}
ñượ
c minh h
ọ
a trên hình VII.7, v