Về một lớp bài toán tối ưu ngẫu nhiên chi phí vận tải

TAÏP CHÍ ÑAÏI HOÏC SAØI GOØN Soá 10 - Thaùng 6/2012
1
VỀ MỘT LỚP BÀI TOÁN TỐIƯU NGẪU NHIÊN
CHI PHÍ VẬN TẢI
TRẦN XUÂN SINH (*)
DƯƠNG XUÂN GIÁP(**)
NGUYỄN THỊ THANH HIỀN (***)
TÓM TẮT
Trong bài báo này, chúng tôi trình bày mô hình bài toán tối ưu chi phí vận tải trong
điều kiện thông tin về dữ liệu không đầy đủ. Mô hình toán học được thiết lập có mối liên hệ
với khái niệm ma trận hiệu chỉnh nửa đầy đủ và đầy đủ. Trên cơ sở phân tích mô hình,
chúng tôi nghiên cứu cấu trúc của ma trận hiệu chỉnh đầy đủ, ma trận hiệu chỉnh nửa đầy
đủ, tìm mối quan hệ giữa chúng, đư a ra điều kiện cần và đủ để một ma trận hiệu chỉnh nửa
đầy đủ là ma trận hiệu chỉnh đầy đủ.
Từ khoá: bài toán tối ưu ngẫu nhiên, mô hình, ma trận
ABSTRACT
In this paper, we present the problem model of optimal transportation cost in terms of
information on incomplete data. The mathematical model is established to be associated
with the concept of complete recourse matrix and semicomplete recourse matrix. Based on
analysing the model, we study the structure of the complete recourse and semicomplete
recourse matrix, find the relationships between them, provide necessary and sufficient
conditions in order a semicomplete recourse matrix to be a complete recourse matrix.
Keywords: Random optimal problem, Model, Matrix
1. ĐẶT VẤN ĐỀ (*) (**)
Trong lĩnh vực tối ưu hiện nay, nhiều
nhà Toán học quan tâm nghiên cứu bài
toán điều khiển tối ưu, chủ yếu là bài toán
tối ưu ngẫu nhiên. Đặc biệt, nhóm nghiên
cứu của Chen mấy năm gần đây tập trung
nghiên cứu và công bố nhiều bài bá o về
các kết quả thu được cải tiến các phương
pháp xấp xỉ giải bài toán tối ưu ngẫu nhiên
2 giai đoạn và chứng tỏ tầm quan trọng cả
trong lí thuyết và thực tiễn tính toán, ứng
dụng. Trong [1], Chen và các cộng sự chỉ
ra rằng những quy tắc quyết định tuyến
tính có thể dẫn tới những trường hợp
(*) PGS.TS, Trường Đại học Vinh
(**) (***) ThS, Trường Đại học Vinh
không khả thi cho bài toán tối ưu ngẫu
nhiên với sự hiệu chỉnh đầy đủ.
Ma trận W cỡ m×n được gọi là ma trận
hiệu chỉnh đầy đủ, nếu với mỗi ma trận t cỡ
m×1 đều tồn tại ma trận w = [w1 w2 ... wn]T
cỡ n×1 sao cho wj ≥ 0, ∀j = 1, ..., n và
Ww = t [1].
Ma trận W cỡ m×n được gọi là ma trận
hiệu chỉnh nửa đầy đủ, nếu tồn tại ma trận
r = [r1 r2 ... rn]T cỡ n×1 sao cho rj > 0, ∀j =
1, ..., n và Wr = 0.
Trong nhiều bài toán thực tế thường
dẫn tới bài toán tối ưu ngẫu nhiên hiệu
chỉnh đầy đủ hoặc nửa đầy đủ. Trong bài
báo này, chúng tôi muốn trình bày mô hình
bài toán vận tải, với thông tin về dữ liệu có
VỀ MỘT LỚP BÀI TOÁN TỐI ƯU NGẪU NHIÊN CHI PHÍ VẬN TẢI
2
tính ngẫu nhiên, dẫn tới bài toán quy hoạch
ngẫu nhiên có đặc tính như đã nêu.
Chen và các cộng sự chỉ ra rằng ma
trận hiệu chỉnh đầy đủ là ma trận hiệu
chỉnh nửa đầy đủ [1]. Tuy nhiên, điều
ngược lại nói chung không đúng. Câu hỏi
chúng tôi đặt ra là: Với điều kiện nào thì
ma trận hiệu chỉnh nửa đầy đủ là ma trận
hiệu chỉnh đầy đủ? Thiết lập điều kiện cần
và đủ để ma trận hiệu chỉnh nửa đầy đủ là
ma trận hiệu chỉnh đầy đủ. Trả lời triệt để
câu hỏi này chính là nội dung thứ hai của
bài báo.
Kết quả này sẽ đem tới hai ý nghĩa
quan trọng, bởi vì:
Một là định nghĩa ma trận hiệu chỉnh
đầy đủ khó để kiểm tra, cũng như khó để
thiết lập so với định nghĩa ma trận hiệu
chỉnh nửa đầy đủ.
Hai là, bất kỳ bài toán quy hoạch ngẫu
nhiên với hiệu chỉnh đầy đủ là chấp nhận
được đối với những quy tắc quyết định
tuyến tính lệch. Tuy nhiên, quy tắc quyết
định tuyến tính lệch vẫn có thể chấp nhận
được nếu thiếu sự hiệu chỉnh đầy đủ - đó là
các biến hiệu chỉnh nửa đầy đủ nhưng
không hiệu chỉnh đầy đủ, câu hỏi chúng ta
đặt ra ở đây là điều đó xảy ra khi nào? Từ
đó, chúng tôi chỉ ra được điều kiện cần và
đủ để một ma trận hiệu chỉnh nửa đầy đủ
nhưng không là ma trận hiệu chỉnh đầy đủ.
2. BÀI TOÁN TỐI ƯU CHI PHÍ
2.1. Bài toán
Có n kho chứa hàng với sức chứa mỗi
kho là bi, i = 1, ..., n. Số lượng hàng cần
xác định ở kho thứ i là xi, (xi ≥ 0, i = 1, ...,
n). Kinh phí bảo quản lưu giữ một đơn vị
hàng ở kho thứ i là si, i = 1, ..., n. Cước phí
vận tải một đơn vị hàng từ kho thứ i đến
kho thứ j là cij, i = 1, ..., n, j = 1, ..., n. Cần
vận chuyển để điều chỉnh lượng hàng ở các
kho sao cho tổng chi phí lưu kho và vận
chuyển là bé nhất. Biết rằng giữa kho i và
kho j luôn có cung đường vận tải và cij =
cji, với mọi i = 1, ..., n, j = 1, ..., n.
2.2. Mô hình toán học
Kí hiệu zij là số đơn vị hàng được
chuyển từ i tới j, (zij ≥ 0). Khi đó một
phương án vận tải z = (zij) được thực hiện
thì số hàng ti, i = 1, ..., n, có ở kho thứ i tại
một thời điểm sẽ là:
ti = xi - ∑
=
n
j 1
zij + ∑
=
n
k 1
zki, i = 1, ..., n.
Chi phí vận chuyển và lưu trữ được
tính theo công thức
∑
=
n
i 1
sixi + ∑
=
n
i 1
∑
=
n
j 1
cijzij → minx.
Vậy ta có bài toán tìm x = (xi) và
z = (zij), sao cho
min { ∑
=
n
i 1
sixi + ∑
=
n
i 1
∑
=
n
j 1
cijzij} (1)
với điều kiện
ti + ∑
=
n
j 1
zij - ∑
=
n
k 1
zki = xi, i = 1, ..., n, (2)
xi ≤ bi, i = 1, ..., n, (3)
ti ≥ 0, i = 1, ..., n, (4)
xi ≥ 0, zij ≥ 0, i = 1, ..., n, j = 1, ..., n. (5)
Trong thực tế, bài toán đã nêu với biến
xi, i = 1, ..., n, có sự tham gia của yếu tố
ngẫu nhiên w. Khi đó biến z = (zij) và biến
t = (ti) 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 [3].
3. CÁC KẾT QUẢ CHÍNH
3.1. Về bài toán tối ưu chi phí
Như đã nêu trong mô hình (1)-(5), số
TRẦN XUÂN SINH - DƯƠNG XUÂN GIÁP - NGUYỄN THỊ THANH HIỀN
3
lượng hàng có ở kho i là xi 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 là x’i(w). Do
vậy, số lượng hàng có ở kho thứ i là ti(w),
khi thực hiện phương án vận tải z sẽ là
ti(w) = xi – x’i(w) - ∑
=
n
j 1
zij(w) + ∑
=
n
k 1
zki(w).
Thực hiện ở giai đoạn hai, điều chỉnh
kế hoạch với sự tham gia của yếu tố ngẫu
nhiên, ta cần giải bài toán quy hoạch
m