Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
27

Về Một mô hình bài toán quy hoạch ngẫu nhiên

Lê Thanh Hoa
(a)

Nguyễn Thị Thanh Hiền
(b)Tóm tắt. Trong bài báo này, chúng tôi đã thiết lập một mô hình quy hoạch
ngẫu nhiên, chứng minh các tính chất riêng biệt của nó. Trên cơ sở đó, chúng tôi xấp
xỉ bài toán vận tải với dữ liệu ngẫu nhiên bởi bài toán quy hoạch tuyến tính.
I. Mở đầu
1.1. Bài toán lu chuyển hàng
1.1.1. Bài toán. Có n kho chứa hàng với sức chứa mỗi kho là b
i
. Số lợng hàng cần
xác định ở kho thứ i là x
i
, i = 1, 2, , n. Kinh phí bảo quản lu giữ một đơn vị hàng ở
kho thứ i là s
i

z
ij
+

=
n
k 1
z
ki
, i

= 1, 2, , n.

Chi phí vận chuyển và lu giữ đợc tính theo công thức

=
n
i 1
s
i
x
i
+

=
n
i 1

=
n

c
ij
z
ij
} (1.1)
với điều kiện










t
i
+

=
n
j 1
z
ij
-

=
n
k 1

Nhận bài ngày 27/7/2007. Sửa chữa xong 15/10/2007.

Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
28
Trong thực tế, bài toán đã nêu với biến x
i
, (i = 1, 2, , n), có sự tham gia của yếu
tố ngẫu nhiên w. Khi đó biến z = (z
ij
) và biến t = (t
i
) sẽ phụ thuộc vào yếu tố ngẫu
nhiên đã nêu. Để giải quyết bài toán này, ta cần tới sự điều chỉnh trong lớp các bài
toán quy hoạch ngẫu nhiên hai giai đoạn.
1.2. Bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn ([2])
Nh chúng ta đã biết bài toán quy hoạch tuyến tính ngẫu nhiên 2 giai đoạn (two-
stage stochastic linear programming), với giai đoạn I: xác định sơ bộ nghiệm trên cở
sở các thông tin có đợc trớc đó, giai đoạn II: chỉnh lý nghiệm theo thực tế, có chú ý
đến các yếu tố ngẫu nhiên. Cụ thể, chúng ta cần giải bài toán (2SSLP) sau
min {g(x) = cx + E
w

[Q(x, w)]} (1.6)
với điều kiện

có thể phụ
thuộc đại lợng ngẫu nhiên w. Ta ký hiệu giá trị thay đổi, do tác động của w, này là
x
i
(w). Do vậy, số lợng hàng có ở kho thứ i là t
i
(w), khi thực hiện phơng án vận tải z
sẽ là
t
i
(w) = x
i
- x
i
(w) -

=
n
j 1
z
ij
(w) +

=
n
k 1
z
ki
(w).
Việc giải bài toán (1.1)-(1.5) với đại lợng x

(w))}
với điều kiện
Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
29







t
i
(w) = x
i
- x
i
(w) -

=
n
j 1
z
ij

với điều kiện






x - t(w) + Az(w) = x(w) (2.2)

x b (2.3)

x, t(w), x'(w) 0, z(w) 0,

(2.4)

trong đó t(w) = (t
i
(w)), x(w) = (x'
i
(w)), x = (x
i
), b = (b
i
); s
T
, c
T
tơng ứng là ma trận
chuyển vị của ma trận s = (s
i

A =













111100
110011
001111
,
Khi đó, nếu cộng n hàng lại với nhau thì đợc hàng toàn số 0, tức là n hàng của A
phụ thuộc tuyến tính. Nhng có thể thấy tồn tại định thức cấp n-1 khác 0. Vậy điều
đó chứng tỏ hạng của ma trận A bằng n-1.
Mặt khác, với n đỉnh sẽ có n(n-1)/2 cạnh. Mỗi cạnh (i, j) có 2 ẩn z
ij
và z
ji
, vì vậy số
ẩn phải là n(n-1). Từ đó cho thấy số cột là n(n-1).
Cũng tơng tự, tổng các vectơ cột sẽ là vectơ 0.



i
=

=
n
j 1
z
ij
.
Khi đó ta có bài toán
min { f(x, z) =

=
n
i 1
s
i
x
i
+

=
n
i 1

=
n
j 1
c
ij

i
(w), z
ij
(w) 0, i = 1, 2, , n; j = 1, 2, , n.
Ký hiệu
D = ( I A
*
),
trong đó I là ma trận đơn vị, tơng ứng với hệ số của x
i
(i = 1, 2, , n), A
*
là ma trận
hệ số của z
ij
trong bài toán nêu trên (chú ý rằng ma trận A
*
chỉ khác với ma trận A
trong mệnh đề 1, bởi xóa đi các phần tử 1, còn lại các phần tử - 1 và 0). Nh vậy, ma
trận D có n hàng và n
2
cột.
Lúc này bài toán nêu trên có thể viết lại
min { f(x, z) = s
T
x + c
T
E(z(w))}
với điều kiện

Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
31
với điều kiện






Bx = b

(2.6)

U(w)x + Vt(w) + D(x, z(w)) = h(w),

(2.7)

x, t(w), z(w) 0, (2.8)

trong đó B, V là các ma trận hệ số, D và các ký hiệu khác nh đã nêu trên. U(w) và
h(w) là các hàm affine đối với

i
, nghĩa là
U(w) = U

n
,
phơng trình Du = t, ứng với mỗi t
i
có dạng
u
i
- v
j
= t
i
, (*)
trong đó v
j
=

Jj
j
u
, với J là tập hợp gồm n-1 chỉ số tơng ứng vơi các số -1 trong
D. Rõ ràng phơng trình (*) luôn tồn tại nghiệm u
i
, v
j
0 với mọi t
i
. Từ v
j
ta có thể
phân tích để có đợc vectơ u = (u

=
k
i
1
z
i

i
.
(Chú ý rằng trong mô hình (2.5)-(2.8), sự biểu diễn dạng affine của U(

), h(

) và
t(

) là rất thực tế).
Khi đó ta xấp xỉ bài toán (2.5)-(2.8) bởi bài toán sau đây
min { F(x, z) = s
T
x + d
T
t
0
+ g
T
z
0
} (2.9)
với điều kiện


) có thỏa mãn điều kiện (2.7) hay không. Rõ ràng từ điều kiện
U
i
x + Vt
i
+ Dz
i
= h
i
, i = 0, 1, , k (2.11)
cộng k+1 đẳng thức lại ta đợc điều kiện (2.7). Vậy mỗi phơng án của bài toán (2.9)-
(2.12) cũng là phơng án của bài toán (2.5)-(2.8).
Trong biểu thức
min { f(x, z) = s
T
x + E(d
T
t(w)) + E(g
T
(z(w))}
Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
32
ta thay

t(w)) + E(g
T
(z(w))} min{F(x, z) = s
T
x + d
T
t
0
+ g
T
z
0
}.
Đó là điều phải chứng minh.


Ký hiệu q = (q
1
, q
2
, , q
2
n
). Khi đó với mỗi i (i = 1, 2, , n
2
), xét bài toán quy
hoạch tuyến tính
g
i
= min g

)x + Vt(

) + Dr(

) = h(

), (2.14)
ta xét
z(

) = r(

) +

=
n
i
1
(r
i
(

)
_
)
q
i
, (2.15)
trong đó ký hiệu a
_

)D
q
i
.
Vì
q
i
là nghiệm của (2.13) nên D
q
i
= 0. Từ đó suy ra Dz(

) = Dr(

).
Mặt khác, do q 0 và q
i
= 1, nên từ (2.15) suy ra z(

) 0.
Bởi vậy, với mỗi x cho trớc nào đó thì tồn tại r(

) và t(

) thỏa mãn (2.14).
Mệnh đề 5. Bài toán (2.5)-(2.8) với mọi x và t(

) đã cho, tồn tại r(

) sao cho

33
Theo mệnh đề 3, bài toán đã cho là hợp lý, nên tồn tại r
0
, r
1
, , r
k
, sao cho
U
i
x + Vt
i
+ Dr
i
= h
i
, i = 0, 1, , k.
Thực hiện với

và cộng k+1 đẳng thức trên ta đợc
r(

) = r
0
+

=
k
i
1

z(

) = g
T
r(

) +
g
T
(r(

)
_
).
Xét bài toán
min{

= s
T
x + d
T
t
0
+ g
T
r
0
+ E[
g
T


)),
trong đó
z(

) = r(

) +

=
n
i
1
(r
i
(

)
_
)
q
i

là thỏa mãn điều kiện của bài toán (2.5)-(2.8). Lúc này chúng ta có
minf min

.
Ngoài ra, với mọi phơng án dạng (x, t(

), z(


), ta có thể xấp xỉ bài toán
(2.5) -(2.8) bởi bài toán (2.16).
Đại học Vinh Tạp chí khoa học, tập XXXVI, số 3A-2007
34
Trong trờng hợp này, chúng ta rút bớt đợc cận trên của bài toán cần giải.
Nh vậy, để giải bài toán (2.5)-(2.8), ta giải bài toán xấp xỉ (2.16). Việc giải bài
toán (2.16) có thể sử dụng phơng pháp xấp xỉ Monte - Carlo.

tài liệu tham khảo[1] X. Chen, M. Sim, P. Sun, A robust optimization perspective of stochastic
programming, Working paper, National University of Singapore, 2005.
[2] Dinh The Luc, Introduction a la optimizacion no lineal, (Chapter 10: Stochastic
Programming, pp. 77-82, VI Coloquio del departamento de matematicas centro
de investigacion y de estudios avanzados del IPN 31 de Julio al 18 de Agosto de
1989.
[3] Bùi Thế Tâm, Trần Vũ Thiệu, Các phơng pháp tối u hoá, NXB Giao thông vận
tải, Hà Nội, 1998.
[4] Bùi Minh Trí, Quy hoạch toán học, Tập 2, NXB Khoa học Kỹ thuật, Hà Nội, 2005. Summary