Một lớp bài toán đầu t tài chính
Trần Xuân Sinh
(a)
, Nguyễn Thị Thanh Hiền
(a)
Nguyễn Văn Hng
(b)
Tóm tắt. Trong bài báo này, chúng tôi giới thiệu một mô hình bài toán đầu t tài chính
mà việc giải nó đợc quy về bài toán chiếc túi với ràng buộc ngẫu nhiên. Từ đó chúng
tôi xây dựng thuật toán nhằm tìm ra phơng án tối u.
I. Bài toán
Một nhà đầu t có b đơn vị đồng vốn, dự định tham gia đầu t vào n công ty kinh
doanh (ta gọi công ty thứ i là Công ty i, i = 1, , n). Nếu đầu t 1 đơn vị đồng vốn vào
Công ty i thì cho lãi suất là c
i
và chi phí phải trả là a
i
. Hỏi nên đầu t vốn nh thế
nào để có tổng số lãi lớn nhất.
Để thiết lập mô hình toán học, ta ký hiệu I = {1, 2, , n} và x
i
, i I, là sự lựa chọn
của Nhà đầu t vào Công ty i (x
i
= 1 nếu Công ty i đợc lựa chọn đầu t, còn x
i
= 0
là Công ty i không đợc lựa chọn đầu t). Khi đó ta có bài toán
max{f = c.x} (1)
với điều kiện



i=1
c
i
x
i
:
k

i=1
a
i
x
i
h; x
i
{0; 1}, i = 1, k

().
Điều đó có nghĩa rằng F
k
(h) là giá trị lớn nhất của hàm f khi các đồ vật đợc chọn
từ k lần đầu tiên và trọng lợng của cái túi là h.
Với k = 1, ta có
F
1
(h) = max
x
1
{0;1}

i
h a
k
x
k
; x
i
{0; 1}, i = 1, k

.
Khi đó ta có
F
k
(h) = max
x
k
{0;1}

c
k
x
k
+ max
x
i
{0;1}

k1

i=1

x
k
+ F
k1
(h a
k
x
k
)}.
Ký hiệu
F
0
(h) = 0; h =
0, b,
ta có công thức đệ quy nh sau:
F
k
(h) = max
x
k
{0;1}
{c
k
x
k
+ F
k1
(h a
k
x

thờng biến
động ngẫu nhiên. Để giữ cho c
i
cố định, Công ty i, i I có thể điều chỉnh cho a
i
biến
động theo "giá tham chiếu" ngẫu nhiên w
i
với biên độ dao động là w
i
[w
i
, w
i
].
Trong bài viết này, chúng tôi nêu ra một hớng giải quyết bài toán khi có sự biến
động ngẫu nhiên về chi phí nh đã nêu.
II. Các kết quả chính
2.1. Bài toán đầu t tài chính có ràng buộc ngẫu nhiên
Giả sử a
i
, i = 1, , n phụ thuộc đại lợng ngẫu nhiên w
i
, i = 1, , n. Ký hiệu w = (w
i
)
lấy giá trị trong W R
n
+
; độ đo xác suất P trên W là P (w W ) = P (W ) = 1. Khi đó

Nh vậy bài toán lúc này đặt ra là: Tìm một điểm x

{0; 1}
n
với xác suất
P

n

i=1
w
i
x
i
b

1 sao cho đạt max f.
Do không phải dễ dàng duyệt hết các phơng án của bài toán đặt ra khi n khá
lớn, cho nên chúng ta cần khai thác các tính chất của nó.
2.2. Các giả thiết ban đầu. Để nghiên cứu bài toán (1)(2)(3), trong bài viết này,
chúng tôi đa ra một số giả thiết ban đầu nh sau:
(i) Các đại lợng c
i
, a
i
, i = 1, , n và b nguyên.
(ii) Các đại lợng ngẫu nhiên w
i
[w
i

I, {0, , |I

|}, S I

có bản số , nghĩa là |S| = .
Ta xét bài toán
max{f = c.x} (7)
với điều kiện

iS
w
i
x
i
+

iI

\S
w
i
x
i
+

i /I

w
i
x

Chứng minh. Trớc hết chúng ta nhận xét rằng mỗi phơng án tối u của bài toán
(7) (9) làm cực đại

iI
x
i
, với x
i
{0; 1}. Giả sử rằng (w + ) b. Điều này có nghĩa
là phơng án tối u x

của (7) (9) có ít nhất phần tử khác 0, tức là

iI
x

i
. Vì
vậy, x

trong thực tế là phơng án tối u của bài toán max


iI
x
i

, với ràng buộc

iI

{f = cx}) (10)
với điều kiện
V W : P (V ) 1 , (11)
w V : w.x b,
x {0; 1}
n
. (12)
Định lý 2.3.2. Phơng án x

của bài toán (4) (6) là tối u khi và chỉ khi tồn tại
V W với P (V ) 1 sao cho (V, x

) là phơng án tối u của bài toán (10) (12).
Chứng minh. Rõ ràng x

là phơng án của bài toán (4) (6), khi và chỉ khi tồn tại
V W : P (V ) 1 sao cho (V, x

) là phơng án của bài toán (10)-(12). Chú ý rằng
nếu V có dạng V = {w W : wx b} thì P(wx b) P (V ). Khi đó (V, x

) là phơng án
tối u của bài toán (10)-(12) khi và chỉ khi x

là phơng án tối u của (4) (6). Đó là
điều phải chứng minh.
Với mỗi i I, ta ký hiệu

i
=

iS
w
i
x
i
b, S I, |S| = , (14)
x {0; 1}
n
. (15)
Với mỗi x {0; 1}
n
, ta ký hiệu
I(x) = {i I : x
i
= 1}.
Định lý 2.3.3.[5]. Ta có bất đẳng thức
P (w.x b) P


iI

i


,
với mọi phơng án x của bài toán (13) (15)
Lấy I

I và {0, , |I


lấy với mọi S I

, |S| = .
Bài toán (16)-(18) đợc ký hiệu là (RKP (I

, )).
Bài toán (13)-(15) là trờng hợp riêng của (RKP (I

, )) khi I

= I, = n.
Định lý 2.3.4. [5]. Lấy {0, , n}. Giả sử x

là phơng án tối u của (RKP (I, )).
Khi đó
(i) nếu |I(x

)| thì x

là phơng án tối u của (RKP(I(x

), )),
(ii) nếu |I(x

)| thì x

là phơng án tối u của (RKP (I, n)), tức là phơng án tối
u của bài toán (7) (9).
Định lý 2.3.5 [5]. Giả sử rằng i I, w
i

= I(x
(k)
). Xác định

là giá trị lớn nhất của {0, , |I

|} sao cho
x
(k)
là phơng án của bài toán (RKP(I

,

)).
Bớc 4. Tính cận dới U P


iI

w
i
b

Nếu U 1 , thì x
(k)
là phơng án của (4) (6). Dừng lại.
Ngợc lại, sang bớc 5.
Bớc 5. Gán k :=

+ 1, trở lại bớc 2.

)) và
nhờ Định lý 2.3.5 ta đợc phơng án tối u của bài toán (4)-(6).
+ Để tính cận dới U tại bớc 4, chúng ta có thể tham khảo các ví dụ về cận xác
suất trong [4]. Chất lợng của cận sẽ có ảnh hởng trực tiếp lên số lần lặp của thuật
toán.
Ví dụ. Nhà đầu t tài chính có 82 đơn vị vốn, có thể đầu t vào 9 Công ty, với
mức lãi suất tại Công ty i là c
i
= 10 i, i = 1, , 9. Biên độ giao động về giá đầu t ở
các Công ty nh nhau với mức tối thiểu là w = 8, tối đa là w = 12 đơn vị vốn. Khi đó
ta có mô hình toán học
max

f =
9

i=1
(10 i)x
i

với điều kiện

9
i=1
w
i
x
i
82,
x {0; 1}

(i)
i
= 1 và e
(i)
j
= 0, i = j. Ta sử dụng Định lý 2.1, tơng ứng với các giá trị của
k, lần lợt thực hiện thuật toán:
k = 0: Chúng ta có

= 0,

iI
x
(0)
i
= [b/w] = [82/8] = 10, và do vậy x
(0)
=

9
i=1
e
(i)
.
Tiếp tục, tính cận dới (xem [4]) P


9
i=1
w


9
i=2
e
(i)
. Chúng ta có

=
min{|I

|; (b

iI

w
i
x
i
)/} = [(82 9 8)/4] = 2, tính cận dới P


9
i=2
w
i
82

U =
0, 001 < 0, 9. Gán k :=


iI
x
(5)
i
= [(82 20)/8] = 7, và do vậy x
(5)
=

9
i=4
e
(i)
. Tính đợc cận dới
P


9
i=4
w
i
82

U = 0, 99 > 0, 9. Dừng lại. Trả lời x
(5)
là phơng án của (RKP (I, )),
do vậy nó là phơng án tối u của (SKP ).
Từ đó, để tìm x
(5)
= (x
(5)

o
1(2004),
35-53.
[5] O. Klopfenstein and D. Nace, A Robust Approach to the Chance-constrained Knap-
sack Problem, 60205 Compiègne Cedex, France, 2006.
Summary
A class problem of financial investment
In this paper, we introduced a model for problems of financial investment, the
way of its solving reduced to the knapsack problem with stochastic constrain. Then
we give an algorithm to find an optimal plan.
(a) Khoa Toán, Trờng Đại học Vinh
(b) Khoa Toán, Trờng Đại học Đồng Tháp.