Báo cáo nghiên cứu khoa học: Về một mô hình bài toán quy hoạch ngẫu nhiên

Tuyển tập những báo cáo nghiên cứu khoa học hay nhất của trường đại học vinh tác giả: 4. Lê Thanh Hoa, Nguyễn Thị Thanh Hiền, Về một mô hình bài toán quy hoạch ngẫu nhiên...Toán học là môn khoa học nghiên cứu về các số, cấu trúc, không gian và các phép biến đổi. Nói một cách khác, người ta cho rằng đó là môn học về "hình và số." Theo quan điểm chính thống, nó là môn học nghiên cứu về các cấu trúc trừu tượng định nghĩa từ các tiên đề, bằng cách sử dụng Luận lý...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: "Về một mô hình bài toán quy hoạch ngẫu nhiên" T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 §¹i häc Vinh 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 l−u 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µ bi. Sè l−îng hµng cÇn x¸c ®Þnh ë kho thø i lµ xi, i = 1, 2, ..., n. Kinh phÝ b¶o qu¶n l−u gi÷ mét ®¬n vÞ hµng ë kho thø i lµ si, i = 1, 2, ..., 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, 2, ..., n; j = 1, 2, ..., 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, (i = 1, 2,..., n; j = 1, 2, ..., n). 1.1.2. §Æt bµi to¸n. 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, 2, …, n) cã ë kho thø i t¹i mét thêi ®iÓm sÏ lµ n n ∑ zij + ∑z ti = xi - , i = 1, 2, ..., n. ki j =1 k =1 Chi phÝ vËn chuyÓn vµ l−u gi÷ ®−îc tÝnh theo c«ng thøc n n n ∑ ∑c ∑ si xi + zij → min. ij i =1 i =1 j =1 VËy ta cã bµi to¸n t×m x = (xi), z = (zij) ≥ 0, sao cho n n n ∑ ∑c ∑ si xi + min { (1.1) zij } ij i =1 i =1 j =1  n n ti + ∑ zij - ∑z = xi, i = 1, 2, ..., n, (1.2)  ki  víi ®iÒu kiÖn  j =1 k =1  xi ≤ bi, i = 1, 2, …, n (1.3)  ti ≥ 0, i = 1, 2, ..., n, (1.4)   xi ≥ 0, zij ≥ 0, i = 1, 2, ..., n; j = 1, 2, ..., n, (1.5)  NhËn bµi ngµy 27/7/2007. Söa ch÷a xong 15/10/2007. 27 T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 §¹i häc Vinh Trong thùc tÕ, bµi to¸n ®· nªu víi biÕn xi, (i = 1, 2, ..., 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. 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 + Ew∈Ω[Q(x, w)]} (1.6) víi ®iÒu kiÖn A(w)x = b(w), x ≥ 0, (1.7) trong ®ã Q(x, w) = min {q(w)y : D(w)y = b(w) – A(w)x, y ≥ 0}, víi c, x ∈ »n; q, y ∈ »m; w = (ω1, ω2, …, ωk) lµ biÕn ngÉu nhiªn thuéc kh«ng gian x¸c suÊt (Ω, , ℘), ⊆ »k; q(w) ®−îc hiÓu nh− mét vect¬ ph¹t khi cã sù chªnh lÖch trong ®iÒu kiÖn buéc cña bµi to¸n víi d÷ liÖu ch−a ch¾c ch¾n; Ew∈Ω[Q(x, w)] lµ kú väng cña Q(x, w) lÊy theo biÕn ngÉu nhiªn w ∈ ; A(w) = (aij(w)) lµ ma trËn hÖ sè cÊp m×n, b(w) lµ ma trËn cÊp m×1; D lµ ma trËn hÖ sè, nãi chung phô thuéc vµo w. II. C¸c kÕt qu¶ chÝnh Nh− ®· nªu trong m« h×nh (1.1)-(1.5), sè 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, nµy 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µ n n ti(w) = xi - x’i(w) - ∑ zij(w) + ∑z (w). ki j =1 k =1 ViÖc gi¶i bµi to¸n (1.1)-(1.5) víi ®¹i l−îng xi x¸c ®Þnh nµo ®ã chØ míi ®−îc xem lµ giai ®o¹n I ...