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<br /> <br /> <br /> VỀ MỘT LỚP BÀI TOÁN TỐI ƯU NGẪU NHIÊN<br /> CHI PHÍ VẬN TẢI<br /> <br /> TRẦN XUÂN SINH (*)<br /> DƯƠNG XUÂN GIÁP(**)<br /> NGUYỄN THỊ THANH HIỀN (***)<br /> <br /> TÓM TẮT<br /> 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<br /> đ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ệ<br /> 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,<br /> 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<br /> đủ, 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<br /> đầy đủ là ma trận hiệu chỉnh đầy đủ.<br /> Từ khoá: bài toán tối ưu ngẫu nhiên, mô hình, ma trận<br /> <br /> ABSTRACT<br /> In this paper, we present the problem model of optimal transportation cost in terms of<br /> information on incomplete data. The mathematical model is established to be associated<br /> with the concept of complete recourse matrix and semicomplete recourse matrix. Based on<br /> analysing the model, we study the structure of the complete recourse and semicomplete<br /> recourse matrix, find the relationships between them, provide necessary and sufficient<br /> conditions in order a semicomplete recourse matrix to be a complete recourse matrix.<br /> Keywords: Random optimal problem, Model, Matrix<br /> <br /> 1. ĐẶT VẤN ĐỀ (*) (**) không khả thi cho bài toán tối ưu ngẫu<br /> Trong lĩnh vực tối ưu hiện nay, nhiều nhiên với sự hiệu chỉnh đầy đủ.<br /> nhà Toán học quan tâm nghiên cứu bài Ma trận W cỡ m×n được gọi là ma trận<br /> toán điều khiển tối ưu, chủ yếu là bài toán hiệu chỉnh đầy đủ, nếu với mỗi ma trận t cỡ<br /> tối ưu ngẫu nhiên. Đặc biệt, nhóm nghiên m×1 đều tồn tại ma trận w = [w1 w2 ... wn]T<br /> cứu của Chen mấy năm gần đây tập trung cỡ n×1 sao cho wj ≥ 0, ∀j = 1, ..., n và<br /> nghiên cứu và công bố nhiều bài bá o về Ww = t [1].<br /> các kết quả thu được cải tiến các phương Ma trận W cỡ m×n được gọi là ma trận<br /> pháp xấp xỉ giải bài toán tối ưu ngẫu nhiên hiệu chỉnh nửa đầy đủ , nếu tồn tại ma trận<br /> 2 giai đoạn và chứng tỏ tầm quan trọng cả r = [r1 r2 ... rn]T cỡ n×1 sao cho rj > 0, ∀j =<br /> trong lí thuyết và thực tiễn tính toán, ứng 1, ..., n và Wr = 0.<br /> dụng. Trong [1], Chen và các cộng sự chỉ Trong nhiều bài toán thực tế thường<br /> ra rằng những quy tắc quyết định tuyến dẫn tới bài toán tối ưu ngẫu nhiên hiệu<br /> tính có thể dẫn tới những trường hợp chỉnh đầy đủ hoặc nửa đầy đủ. Trong bài<br /> báo này, chúng tôi muốn trình bày mô hình<br /> (*)<br /> PGS.TS, Trường Đại học Vinh bài toán vận tải, với thông tin về dữ liệu có<br /> (**) (***)<br /> ThS, Trường Đại học Vinh<br /> <br /> 1<br /> VỀ MỘT LỚP BÀI TOÁN TỐI ƯU NGẪU NHIÊN CHI PHÍ VẬN TẢI<br /> <br /> <br /> tính ngẫu nhiên, dẫn tới bài toán quy hoạch chuyển là bé nhất. Biết rằng giữa kho i và<br /> ngẫu nhiên có đặc tính như đã nêu. kho j luôn có cung đường vận tải và cij =<br /> Chen và các cộng sự chỉ ra rằng ma cji, với mọi i = 1, ..., n, j = 1, ..., n.<br /> trận hiệu chỉnh đầy đủ là ma trận hiệu 2.2. Mô hình toán học<br /> chỉnh nửa đầy đủ [1]. Tuy nhiên, điều Kí hiệu zij là số đơn vị hàng được<br /> ngược lại nói chung không đúng. Câu hỏi chuyển từ i tới j, (zij ≥ 0). Khi đó một<br /> chúng tôi đặt ra là: Với điều kiện nào thì phương án vận tải z = (zij) được thực hiện<br /> ma trận hiệu chỉnh nửa đầy đủ là ma trận thì số hàng ti, i = 1, ..., n, có ở kho thứ i tại<br /> hiệu chỉnh đầy đủ? Thiết lập điều kiện cần một thời điểm sẽ là:<br /> và đủ để ma trận hiệu chỉn h nửa đầy đủ là n n<br /> ma trận hiệu chỉnh đầy đủ. Trả lời triệt để ti = xi - ∑ zij + ∑ zki, i = 1, ..., n.<br /> câu hỏi này chính là nội dung thứ hai của j =1 k =1<br /> bài báo. Chi phí vận chuyển và lưu trữ được<br /> Kết quả này sẽ đem tới hai ý nghĩa tính theo công thức<br /> quan trọng, bởi vì:<br /> n n n<br /> Một là định nghĩa ma trận hiệu chỉnh<br /> đầy đủ khó để kiểm tra, cũng như khó để ∑ sixi + ∑ ∑ cijzij → minx.<br /> i =1 i =1 j =1<br /> thiết lập so với định nghĩa ma trận hiệu<br /> chỉnh nửa đầy đủ. Vậy ta có bài toán tìm x = (xi) và<br /> Hai là, bất kỳ bài toán quy hoạch ngẫu z = (zij), sao cho<br /> nhiên với hiệu chỉnh đầy đủ là chấp nhận n n n<br /> được đối với những quy tắc quyết định min { ∑ sixi + ∑ ∑ cijzij} (1)<br /> i =1 i =1 j =1<br /> tuyến tính lệch. Tuy nhiên, quy tắc quyết<br /> định tuyến tính lệch vẫn có thể chấp nhận với điều kiện<br /> được nếu thiếu sự hiệu chỉnh đầy đủ - đó là n n<br /> các biến hiệu chỉnh nửa đầy đủ nhưng ti + ∑ zij - ∑ zki = xi, i = 1, ..., n, (2)<br /> không hiệu chỉnh đầy đủ, câu hỏi chúng ta j =1 k =1<br /> đặt ra ở đây là điều đó xảy ra khi nào? Từ xi ≤ bi, i = 1, ..., n, (3)<br /> đó, chúng tôi chỉ ra được điều kiện cần và<br /> đủ để một ma trận hiệu chỉnh nửa đầy đủ ti ≥ 0, i = 1, ..., n, (4)<br /> nhưng không là ma trận hiệu chỉnh đầy đủ. xi ≥ 0, zij ≥ 0, i = 1, ..., n, j = 1, ..., n. (5)<br /> 2. BÀI TOÁN TỐI ƯU CHI PHÍ Trong thực tế, bài toán đã nêu với biến<br /> 2.1. Bài toán xi, i = 1, ..., n, có sự tham gia của yếu tố<br /> Có n kho chứa hàng với sức chứa mỗi ngẫu nhiên w. Khi đó biến z = (zij) và biến<br /> kho là bi, i = 1, ..., n. Số lượng hàng cần t = (ti) sẽ phụ thuộc vào yếu tố ngẫu nhiên<br /> xác định ở kho thứ i là xi, (xi ≥ 0, i = 1, ..., đã nêu. Để giải quyết bài toán này, ta cần<br /> n). Kinh phí bảo quản lưu giữ một đơn vị tới sự điều chỉnh trong lớp các bài toán quy<br /> hàng ở kho thứ i là si, i = 1, ..., n. Cước phí hoạch ngẫu nhiên hai giai đoạn [3].<br /> vận tải một đơn vị hàng từ kho thứ i đến 3. CÁC KẾT QUẢ CHÍNH<br /> kho thứ j là cij, i = 1, ..., n, j = 1, ..., n. Cần 3.1. Về bài toán tối ưu chi phí<br /> vận chuyển để điều chỉnh lượng hàng ở các Như đã nêu trong mô hình (1)-(5), số<br /> kho sao cho tổng chi phí lưu kho và vận<br /> <br /> 2<br />  TRẦN XUÂN SINH - DƯƠNG XUÂN GIÁP - NGUYỄN THỊ THANH HIỀN<br /> <br /> <br /> lượng hàng có ở kho i là xi có thể phụ thuộc Định lí 3.1.1. Ma trận A của bài toán<br /> đại lượng ngẫu nhiên w. Ta kí hiệu giá trị (6) - (9) có n hàng, n(n-1) cột, nhưng có<br /> thay đổi, do tác động của w là x’i(w). Do hạng n -1. Đặc biệt, tổng các vectơ cột là<br /> vậy, số lượng hàng có ở kho thứ i là ti(w), vectơ 0.<br /> khi thực hiện phương án vận tải z sẽ là Chứng minh. Viết tường minh bài toán<br /> n n (6) - (9) ta thấy ma trận A gồm các phần tử<br /> ti(w) = xi – x’i(w) - ∑ zij(w) + ∑ zki(w). 1, -1 và 0, trong đó trên mỗi hàng gồm n-1<br /> j =1 k =1 số 1 và -1, còn lại là số 0 . Cũng như vậy,<br /> Thực hiện ở giai đoạn hai, điều chỉnh trên mỗi cột chỉ gồm một số 1 và một số -<br /> kế hoạch với sự tham gia của yếu tố ngẫu 1, còn lại là số 0. Khi đó, nếu cộng n hàng<br /> nhiên, ta cần giải bài toán quy hoạch lại với nhau thì được hàng toàn số 0, tứ c là<br /> n hàng của A phụ thuộc tuyến tính. Nhưng<br /> n n n<br /> có thể thấy tồn tại định thức cấp n-1 khác<br /> min{(x, z) = ∑ sixi + ∑ ∑ cijE(zij(w))} 0. Vậy điều đó chứng tỏ hạng của ma trận<br /> i =1 i =1 j =1<br /> A bằng n-1. Mặt khác, với bản đồ giao<br /> với điều kiện thông là đồ thị đối xứng đầy đủ G(U, V),<br /> n n n(n − 1)<br /> ti(w) = xi – x’i(w) - ∑ zij(w) + ∑ zki(w), tập đỉnh U có n đỉnh sẽ có<br /> 2<br /> cạnh.<br /> j =1 k =1<br /> Mỗi cạnh (i, j) có 2 ẩn zij và zji, vì vậy số ẩn<br /> i = 1, ..., n, phải là n(n-1). Từ đó cho thấy số cột là<br /> xi ≤ bi, i = 1, ..., n, n(n-1).<br /> Tương tự, tổng các vectơ cột sẽ là<br /> ti ≥ 0, i = 1, ..., n,<br /> vectơ 0.<br /> xi ≥ 0, x’i(w), zij(w) ≥ 0, i = 1, ..., n, j = 1, Định nghĩa. Bài toán (6) - (9) có ma<br /> ..., n.<br /> trận A là ma trận hiệu chỉnh nửa đầy đủ thì<br /> trong đó E(w) là kỳ vọng của đại lượng ta nói đó là bài toán nửa đầy đủ. Tương tự<br /> ngẫu nhiên w. nếu ma trận A là ma trận hiệu chỉnh đầy đủ<br /> Bài toán nêu trên có thể viết gọn lại thì ta nói đó là bài toán đầy đủ.<br /> như sau Định lí 3.1.2. Bài toán (6) - (9) thuộc<br /> min{(x, z) = sTx + cTE(z(w))} (6) lớp bài toán hiệu chỉnh nửa đầy đủ.<br /> Chứng minh. Trước hết, như chứng<br /> với điều kiện minh Định lí 3.1.1, ta nhận thấy rằng ma<br /> x – t(w) + Az(w) = x’(w) , (7) trận A gồm các phần tử 1, -1 và 0, trong đó<br /> x ≤ b, (8) trên mỗi hàng, số phần tử 1 bằng số phần<br /> tử -1. Khi đó ta chọn vectơ u = (ui), với ui<br /> x ≥ 0, t(w), x’(w), z(w) ≥ 0, (9)<br /> = 1, cho mọi i = 1, 2, ..., n(n-1), thì thoả<br /> trong đó x = (xi), t(w) = (ti(w)), x’(w) = mãn điều kiện bài toán hiệu chỉnh nửa<br /> (x’i(w)), b = (bi) và sT, cT tương ứng là ma đầy đủ.<br /> trận chuyển vị của ma trận s = (si), c = (cij), Bài toán (6) - (9), theo như Định lí<br /> A là ma trận gồm các phần tử tương ứng là 3.1.2, nó là hiệu chỉnh nửa đầy đủ. Tuy<br /> các hệ số của z = ( zij ) . nhiên, có thể kiểm tra thấy rằng bài toán đó<br /> <br /> <br /> 3<br /> VỀ MỘT LỚP BÀI TOÁN TỐI ƯU NGẪU NHIÊN CHI PHÍ VẬN TẢI<br /> <br /> <br /> chưa là hiệu chỉnh đầy đủ. Chúng ta hãy trong đó B, T là các ma trận hệ số, D và các<br /> xét riêng một mô hình thường gặp trong kí hiệu khác như đã nêu trên, H(w) và h(w)<br /> bài toán vận tải đã nêu như sau: Ta giả thiết là các hàm affine đối với wi , nghĩa là<br /> rằng số lượng hàng đang có ở kho i là bi.<br /> k k<br /> Đặt xi là số hàng được vận chuyển đến kho<br /> H(w) = H0 + ∑ Hiwi; h(w) = h0 + ∑ hi w i .<br /> ∑ j =1 zij. Khi đó ta có bài toán<br /> n<br /> i , tức là xi = i =1 i =1<br /> <br /> Định lí 3.1.3. Bài toán (10)-(13) với ma<br /> n n n<br /> trận D như đã nêu là hiệu chỉnh đầy đủ.<br /> min{f(x, z) = ∑ sixi + ∑ ∑ cijE(zij(w))} Chứng minh. Như đã thấy D(I, A*), nên<br /> i =1 i =1 j =1<br /> với vectơ t = (ti) bất kỳ thuộc ℝn, phương<br /> với điều kiện ti(w) = bi + xi – x’i(w) - trình Du = t, ứng với mỗi ti có dạng<br /> ∑ zji(w), i = 1, ..., n, ui – vj = ti, (*)<br /> j:( i , j )∈V<br /> <br /> xi ≤ bi, i = 1, ..., n,<br /> trong đó vj = ∑ j∈J uj, với J là tập hợp gồm<br /> xi ≥ 0, ti(w), zij(w) ≥ 0, i = 1, n-1 chỉ số tương ứng các phần tử -1 trong D.<br /> ..., n, j = 1, ..., n. Rõ ràng phương trình (*) luôn tồn tại<br /> nghiệm ui, vj ≥ 0 với mọi ti. Từ vj ta có thể<br /> Kí hiệu D = (I A*), trong đó I là ma phân tích để có được vectơ u = (ui) ≥ 0, thoả<br /> trận đơn vị, tư ơng ứng với hệ số của xi, i = mãn Du = t, với mọi cách chọn vectơ t.<br /> 1, ..., n, A* là ma trận hệ số của zij trong bài<br /> Đó là điều cần chứng minh.<br /> toán nêu trên (chú ý rằng ma trận A* trong<br /> Từ đây trở đi, ta xét bài toán vận tải<br /> trường hợp này chỉ khác với ma trận A<br /> dạng tổng quát (10) - (13).<br /> trong Định lí 3.1.1, bởi xóa đi các phần tử<br /> Ta giả thiết thêm rằng t(w), z(w) cũng<br /> 1, còn lại các phần tử -1 và 0). Như vậy,<br /> là hàm affine đối với wi, nghĩa là<br /> ma trận D có n hàng và 2n cột.<br /> Lúc này bài toán nêu trên có thể viết lại k k<br /> <br /> T T<br /> t(w) = t0 + ∑ tiwi; z(w) = z0 + ∑ zi w i .<br /> min{f(x, z) = s x + c E(z(w))} i =1 i =1<br /> <br /> (Chú ý rằng trong mô hình (10) -(13),<br /> với điều kiện t(w) – D(x, z(w)) = b,<br /> sự biểu diễn dạng affine của U(w), h(w) và<br /> x ≤ b, t(w) là rất thực tế). Khi đó ta xấp xỉ bài<br /> x ≥ 0, t(w), z(w) ≥ 0. toán (10)-(13) bởi bài toán sau đây<br /> Bài toán vừa nêu có thể viết khái quát min{F(x, z) = sTx + dTt0 + gTz0} (14)<br /> hơn như sau: Tìm x ∈ ℝn và z ∈ ℝ2n sao cho<br /> với Bx = b, (15)<br /> T T T<br /> min{f(x, z) = s x + E(d t(w)) + E(g E(z(w))} (10) điều Hix +Tti + Dzi = hi, i = 0, 1, ..., k (16)<br /> kiện<br /> với Bx = b, (11) x, t(w), z(w) ≥ 0. (17)<br /> điều H(w)x +Tt(w) + D[x, z(w)] = h(w), (12) Định lí 3.1.4. Mỗi phương án của bài<br /> kiện<br /> x ≥ 0, t(w), z(w) ≥ 0. (13) toán (14)-(17) cũng là phương án của bài<br /> toán (10)-(13). Đồng thời minf ≤ minF.<br /> <br /> 4<br />  TRẦN XUÂN SINH - DƯƠNG XUÂN GIÁP - NGUYỄN THỊ THANH HIỀN<br /> <br /> <br /> Chứng minh. Xem [2]. chỉnh đầy đủ, ta suy ra W là ma trận hiệu<br /> 3.2. Về mối quan hệ giữa tính đầy đủ chỉnh nửa đầy đủ, nghĩa là tồn tại vectơ cột<br /> và nửa đầy đủ r = [r1 r2 ... rn]T cấp n×1 sao cho rj > 0, ∀j<br /> Như đã nêu trong mục 1, bây giờ = 1, ..., n và Wr = 0 hay<br /> chúng ta bàn tới mối quan hệ giữa hai khái r1W1 + r2W2 + ... + rnWn = 0.<br /> niệm "hiệu chỉnh đầy đủ" và "hiệu chỉnh<br /> nửa đầy đủ". Điều này mâu thuẫn với hệ {W1, W2,<br /> Trong mục 1, chúng ta đã có xét: "ma ..., Wn} là cơ sở.<br /> trận hiệu chỉnh đầy đủ là ma trận hiệu Bây giờ ta chứng minh W có hạng<br /> chỉnh nửa đầy đủ. Để kiểm tra ma trận W bằng m. Giả sử ngược lại, ma trận W có<br /> có phải là ma trận hiệu chỉnh đầy đủ hay hạng bé hơn m, nghĩa là rank {W1, W2, ...,<br /> không, hoặc thiết lập ma tr ận hiệu chỉnh Wn} < m. Lập luận giống như trường hợp<br /> đầy đủ là rất khó. Những kết quả chúng tôi 1, ta dẫn đến mâu thuẫn. Điều đó chứng tỏ<br /> thu được sau đây đã giải quyết những khó hạng của W bằng m.<br /> khăn này. Định lí chứng minh xong.<br /> Định lí 3.2.1. Nếu ma trận W cấp mn Định lí 3.2.2. Cho trước hai số tự<br /> là ma trận hiệu chỉnh đầy đủ thì m < n và nhiên m, n. Khi đó, luôn tồn tại ma trận<br /> ma trận W có hạng bằng m. hiệu chỉnh nửa đầy đủ W có cấp m×n. Hơn<br /> Chứng minh. Gọi W1, W2, ..., Wn là các nữa, nếu n > 1 thì với số tự nhiên k bất kì<br /> vectơ cột của ma trận W, đây chính là các sao cho k ≤ min{m, n-1}, luôn tồn tại ma<br /> vectơ trong không gian vectơ ℝm. Trước trận hiệu chỉnh nửa đầy đủ W có cấp m ×n<br /> tiên, ta chứng minh m < n. Thật vậy, giả sử và có rank{W} = k.<br /> ngược lại, ta xét 3 trường hợp: Chứng minh. Nếu n = 1 thì ta chọn ma<br /> Trường hợp 1: m > n. Khi đó, trận W là ma trận cột không (chính là vectơ<br /> rank{W1, W2, ..., Wn} < m. Theo đại số không trong không gian vectơ ℝm). Khi đó,<br /> tuyến tính, tồn tại vectơ cột t ∈ ℝm để ma trận W thoả mãn điều kiện là ma trận<br /> hiệu chỉnh nửa đầy đủ.<br /> rank{W1, W2, ..., Wn, t} = rank{W1, W2, ..., Nếu n > 1 thì ta chọn tuỳ ý các vectơ<br /> Wn} + 1,<br /> cột W1, W2, ..., Wn-1 ∈ ℝm có hạng bằng k<br /> nghĩa là t không thuộc không gian vectơ<br /> và các số thực dương tuỳ ý rj, ∀j = 1, ..., n.<br /> 〈W1, W2, ..., Wn〉 sinh bởi hệ {W1, W2, ...,<br /> Ta đặt<br /> Wn}. Từ đó suy ra không tồn tại vectơ cột w<br /> để Ww = t. Nói riêng, W không là ma trận r1 r r<br /> Wn = − W1 − 2 W2 − ... − n −1 Wn −1 ∈ ℝm. (18)<br /> hiệu chỉnh đầy đủ, ta gặp một mâu thuẫn. rn rn rn<br /> Trường hợp 2: m = n và rank(W) < m. Từ đó suy ra<br /> Lập luận tương tự trường hợp 1.<br /> Trường hợp 3: m = n và rank(W) = m. r1W1 + r2 W2 + ... + rnWn = 0. (19)<br /> Khi đó, ma trận W khả nghịch, suy ra hệ Gọi W là ma trận gồm các cột W1, W2,<br /> {W1, W2, ..., Wn} là cơ sở của không gian ..., Wn. Khi đó, công thức (19) cho ta Wr =<br /> vectơ ℝm. Theo giả thiết, W là ma trận hiệu 0. Rõ ràng ma trận W có cấp m×n. Do hệ<br /> <br /> <br /> 5<br /> VỀ MỘT LỚP BÀI TOÁN TỐI ƯU NGẪU NHIÊN CHI PHÍ VẬN TẢI<br /> <br /> <br /> vectơ cột W1, W2, ..., Wn-1∈ ℝm có hạng<br /> bằng k và vectơ cột Wn biểu thị tuyến tính Định lí 3.2.4. Ma trận W cấp m×n là ma<br /> qua hệ các vectơ W1, W2, ..., Wn-1 nên suy trận hiệu chỉnh đầy đủ khi và chỉ khi với số<br /> ra rank(W) = k. Như vậy, ma trận W xây thực  bất kỳ và mỗi vectơ cột t cấp m ×1 đều<br /> dựng như trên là ma trận hiệu chỉnh nửa tồn tại vectơ cột w = [w1 ... wn]T với các biến<br /> đầy đủ có cấp m×n và có hạng bằng k. bị chặn dưới bởi , tức là j ≥ ,<br /> Định lí 3.2.3. Giả sử ma trận W có cấp j = 1, ..., n, thoả mãn Wr = t.<br /> m×n, (m < n), có hạng bằng m, thoả mãn Chứng minh. Giả sử W là ma trận hiệu<br /> điều kiện tồn tại vectơ cột r = [r1r2...rn]T chỉnh đầy đủ. Khi đó, với mỗi số thực  và<br /> cấp n×1, với r j ≥ 0, j = 1, ..., n, sao cho Wr với mỗi vectơ cột t cấp m×1, ta đặt t* = t -<br /> = 0 và tập các vectơ cột tương ứng với các W*, trong đó  ∗ = [  ... ]T là vectơ cột<br /> hệ số r j > 0 của ma trận W tồn tại một hệ cấp m×1 gồm các phần tử đều bằng  . Theo<br /> các vectơ cột tạo thành cơ sở của không định nghĩ a ma trận hiệu chỉnh đầy đủ, tồn<br /> gian vectơ ℝm. Khi đó W là ma trận hiệu tại vectơ cột y = [y1 ... yn]T sao cho yj ≥ 0, j<br /> chỉnh đầy đủ. = 1, ..., n, thoả mãn Wy = t*, hay Wy = t -<br /> Chứng minh. Xem [4]. W*, điều này tương đương với W(y + *)<br /> Hệ quả 1. Ma trận W cấp m×n, (m < = t. Đặt w = y + * = [w1 ... wn]T, với wj = yj<br /> n), có hạng bằng m. Khi đó W là ma trận +  ≥  thì ta có Ww = t thoả mãn các bi ến<br /> hiệu chỉnh đầy đủ khi và chỉ khi W là ma bị chặn dưới bởi  .<br /> trận hiệu chỉnh nửa đầy đủ. Ngược lại, ta dễ dàng có điều phải<br /> Chứng mi nh. Suy trực tiếp từ nhận xét chứng minh với việc chọn  = 0 .<br /> ở phần I và Định lí 3.2.3. Đó là điều phải chứng minh.<br /> Hệ quả 2. Cho ma trận W cấp m×n là Định lí 3.2.5. Ma trận W cấp m×n là ma<br /> ma trận hiệu chỉnh nửa đầy đủ. Khi đó, ma trận hiệu chỉnh đầy đủ khi và chỉ khi với số<br /> trận W là ma trận hiệu chỉnh đầy đủ khi và thực  bất kỳ, với mỗi vectơ cột t cấp m ×1 đều<br /> chỉ khi m < n và ma trận W có hạ ng bằng m. tồn tại vectơ cột w = [w1 ... wn]T, với các<br /> Chứng minh. Suy ra trực tiếp từ Hệ quả biến bị chặn trên bởi , tức là w j ≤ , j =<br /> 1 và Định lí 3.2.1. 1, ..., n, thoả mãn Ww = t.<br /> Nhận xét. Từ Hệ quả 2, ta có thể thiết Chứng minh. Việc chứng minh hoàn<br /> lập ma trận hiệu chỉnh đầy đủ qua việc toàn tương tự như chứng minh Định lí<br /> thiết lập ma trận hiệu chỉnh nửa đầy đủ 3.2.4, chỉ khác ở chỗ để có w bị chặn trên<br /> bằng cách sử dụng Định lí 3.2.2 với việc thì ta đặt t* = - t + W*, trong đó * = [ ...<br /> chọn k = m. ]T là vectơ cột cấp n×1.<br /> <br /> <br /> <br /> <br /> 6<br />  TÀI LIỆU THAM KHẢO<br /> <br /> 1. Xin Chen, Melvyn Sim, Peng Sun and Jiawei Zhang (2008), A Linear Decision-Based<br /> Approximation - Approach to Stochastic Programming, Operations Research, Vol. 56,<br /> No. 2, March-April 2008, pp. 344-357.<br /> 2. Xin Chen, Melvyn Sim and Peng Sun (2005), A robust optimization perspective of<br /> stochastic programming, Working paper, National University of Singapore.<br /> 3. Shapiro, D. Dentcheva and A. Ruszczyński (2010), Lectures on Stochastic<br /> Programming Modeling and Theory, Mathematical Programming, Society<br /> Philadelphia.<br /> 4. Dương Xuân Giáp (2009), Một số kết quả về sự hiệu chỉnh đầy đủ và hiệu chỉnh nửa<br /> đầy đủ trong các phương pháp xấp xỉ giải bài toán quy hoạ ch ngẫu nhiên, Tạp chí<br /> Khoa học, Trường Đại học Vinh, Tập 38, Số 3A(2009), ISSN 1859-2228, 26-34.<br /> <br /> * Nhận bài ngày 1/12/2011. Sữa chữa xong 10/6/2012. Duyệt đăng 15/6/2012.<br /> <br /> <br /> <br /> <br /> 7<br />