Báo cáo nghiên cứu khoa học: "Về một bài toán phân phối điện được giải bằng phương pháp Monte - Carlo"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

97
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo luận văn - đề án 'báo cáo nghiên cứu khoa học: "về một bài toán phân phối điện được giải bằng phương pháp monte - carlo"', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Về một bài toán phân phối điện được giải bằng phương pháp Monte - Carlo"

Trêng §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVII, sè 2A-2008 VÒ mét bµi to¸n ph©n phèi ®iÖn ®îc gi¶i b»ng ph¬ng ph¸p Monte - Carlo (a) (b) TrÇn Xu©n Sinh , Th¸i Do·n ¢n Tãm t¾t. §Ó gi¶i quyÕt bµi to¸n ph©n phèi ®iÖn, chóng t«i ®a ra m« h×nh to¸n häc lµ bµi to¸n quy ho¹ch låi ngÉu nhiªn, víi hµm môc tiªu phô thuéc ®¹i lîng ngÉu nhiªn t¬ng øng. Tõ ®ã, chóng t«i x©y dùng thuËt to¸n Monte - Carlo, kÕt hîp víi thuËt to¸n gi¶i bµi to¸n quy ho¹ch låi nh»m t×m ra ph¬ng ¸n tèi u. I. Bµi to¸n Bµi to¸n mµ chóng t«i ®Ò cËp tíi ë ®©y, xuÊt ph¸t tõ thùc tÕ nh sau: Gi¶ sö t¹i 1.1. A (KW) tõ m nhµ thêi ®iÓm x¸c ®Þnh nµo ®ã, C«ng ty ®iÖn lùc cÇn ph©n bè lîng ®iÖn n ®Þa ph¬ng (n¬i tiªu thô). Nhµ m¸y ®iÖn thø m¸y ®iÖn kh¸c nhau, dïng ®Ó phôc vô i ai i truyÒn t¶i ®iÖn trªn tuyÕn vÒ n¬i cã s¶n lîng lµ (KW). NÕu nhµ m¸y ®iÖn thø tiªu thô thø j th× tû lÖ h÷u Ých chØ cã thÓ ®¹t dij (trªn 1KW) trong mét thêi gian x¸c ®Þnh. Chi phÝ truyÒn t¶i 1 (KW) ®iÖn tõ nhµ m¸y ®iÖn thø i trªn tuyÕn vËn t¶i vÒ n¬i tiªu thô thø j lµ cij . Tuy nhiªn, nhu cÇu ®iÖn wj ë n¬i sö dông ®iÖn thø j kh«ng thÓ biÕt tríc ®îc vµ ph¶i coi nã nh mét ®¹i lîng ngÉu nhiªn, ph©n bè liªn tôc víi mËt pj (wj ), j = 1, 2, ..., n. H·y t×m c¸ch ph©n phèi ®iÖn sao cho tæng chi phÝ ®é x¸c suÊt lµ vµ møc thiÖt h¹i thÊp nhÊt, mµ b¶o ®¶m kh¶ n¨ng cung cÊp, phôc vô nhu cÇu sö dông ®iÖn ë mçi n¬i. 1.2. ThiÕt lËp bµi to¸n. Ký hiÖu xij lµ sè lîng KW ®iÖn chuyÓn tõ nhµ m¸y ®iÖn thø i, (i = 1, 2, ..., m), tíi n¬i tiªu thô thø j, (j = 1, 2, ..., n), trong mét thêi gian x¸c ®Þnh. Khi ®ã tæng chi phÝ vËn t¶i ®iÖn cña C«ng ty ®iÖn tíi n¬i tiªu thô thø j lµ m cij xij . i=1 j §ång thêi sè lîng ®iÖn ®îc t¶i vÒ sÏ lµ m zj = dij xij , j = 1, 2, ..., n. i=1 Lóc nµy, cã thÓ x¶y ra: zj wj , cã nghÜa lµ nhu cÇu kh«ng bÐ h¬n kh¶ n¨ng. Trong trêng hîp nµy + NÕu wj − zj nhu cÇu kh«ng ®îc thùc hiÖn. Ký hiÖu vj lµ gi¸ trÞ thiÖt h¹i do kh«ng ®ñ cã ®iÖn b¸n mçi KW ®iÖn t¹i n¬i tiªu thô thø j . Lóc nµy gi¸ trÞ thiÖt h¹i cña C«ng ty t¹i 1 - NhËn bµi ngµy 03/5/2008. Söa ch÷a xong ngµy 22/7/2008.
vj (wj − zj ). j sÏ lµ Sù thiÖt h¹i trung b×nh do yªu cÇu kh«ng ®îc ®¸p øng ë n¬i tiªu vj (wj − zj ). Khi ®ã j Ej thô ®îc x¸c ®Þnh bëi kú väng to¸n cña ®¹i lîng ngÉu nhiªn ta cã ∞ vj (wj − zj )pj (wj )dwj , zj ∞. Ej = wj zj zj ≥ wj , cã nghÜa lµ nhu cÇu kh«ng cao h¬n kh¶ n¨ng. Trong trêng hîp nµy + NÕu zj − wj lµ ®é lÖch sè KW ®iÖn cßn thõa kh«ng b¸n ®îc t¹i n¬i tiªu thô thø j . Ký hiÖu uj lµ gi¸ trÞ thiÖt h¹i do mçi KW ®iÖn thõa, kh«ng b¸n ®îc t¹i j . Lóc nµy thiÖt h¹i ë tuyÕn t¶i ®iÖn thø j sÏ lµ uj (zj − wj ). Sù thiÖt h¹i trung b×nh do thõa ®iÖn ë tuyÕn j ®îc x¸c ®Þnh bëi kú väng to¸n Ej cña ®¹i lîng ngÉu nhiªn uj (zj − wj ). zj uj (zj − wj )pj (wj )dwj , 0 Ej = wj zj . 0 VËy tæng chi phÝ vËn t¶i céng thiÖt h¹i trung b×nh cho ho¹t ®éng cña C«ng ty ®iÖn do thiÕu ®iÖn còng nh thõa ®iÖn ®îc m« t¶ bëi hµm môc tiªu n m ∞ zj vj (wj − zj )pj (wj )dwj + uj (zj − wj )pj (wj )dwj → min f= cij xij + zj 0 j =1 i=1 víi ®iÒu kiÖn: i a) H¹n chÕ vÒ lîng ®iÖn cña nhµ m¸y thø n xij ai , i = 1, 2, ..., m; j =1 j b) VÒ sè lîng ®iÖn ®îc t¶i vÒ n¬i tiªu thô thø m dij xij = zj , j = 1, 2, ..., n; i=1 c) Rµng buéc dÊu cña Èn xij ≥ 0, i = 1, 2, ..., m; j = 1, 2, ..., n, zj ≥ 0, j = 1, 2, ..., n. Tõ ®©y ta cã bµi to¸n quy ho¹ch ngÉu nhiªn n m ∞ zj vj (wj − zj )pj (wj )dwj + uj (zj − wj )pj (wj )dwj min f = cij xij + zj 0 j =1 i=1 (1.1) víi ®iÒu kiÖn n xij ai , i = 1, 2, ..., m; (1.2) j =1
m dij xij − zj = 0, j = 1, 2, ..., n; (1.3) i=1 xij ≥ 0, i = 1, 2, ..., m; j = 1, 2, ..., n; zj ≥ 0, j = 1, 2, ..., n. (1.4) Bµi to¸n (1.1)-(1.4) lµ bµi to¸n quy ho¹ch ngÉu nhiªn, cã hµm môc tiªu phô thuéc wj . ®¹i lîng ngÉu nhiªn II. KÕt qu¶ (1.1) − (1.4) lµ bµi to¸n quy ho¹ch låi ngÉu nhiªn víi miÒn 2.1. §Þnh lý. Bµi to¸n rµng buéc lµ tËp låi, compact. Chøng minh. XÐt hµm môc tiªu n m ∞ zj vj (wj − zj )pj (wj )dwj + uj (zj − wj )pj (wj )dwj f= cij xij + zj 0 j =1 i=1 n m n n ∞ zj vj (wj − zj )pj (wj )dwj + uj (zj − wj )pj (wj )dwj = cij xij + zj 0 j =1 i=1 j =1 j =1 = f1 + f2 + f3 , trong ®ã n m f1 = cij xij , j =1 i=1 n ∞ vj (wj − zj )pj (wj )dwj , f2 = zj j =1 n zj uj (zj − wj )pj (wj )dwj . f3 = 0 j =1 f1 lµ hµm tuyÕn tÝnh, f2 vµ f3 lµ hµm tæng cña c¸c kú väng to¸n, do ®ã Ta thÊy hµm nã còng c¸c hµm låi. VËy f lµ hµm låi. MÆt kh¸c, ta thÊy miÒn chÊp nhËn M lµ giao cña c¸c nöa kh«ng gian ®ãng, nªn nã lµ tËp låi ®a diÖn ®ãng. §ång thêi cã thÓ chØ ra r»ng M kh¸c rçng vµ bÞ chÆn, do ®ã nã lµ ®a diÖn låi, ®ãng. 2 Tõ ®ã suy ra ®iÒu ph¶i chøng minh. x = (xij ) ∈ Rm×n , z = (zj ) ∈ Rn . Ký hiÖu §Þnh lý 2.1 lµ c¬ së cho viÖc x©y dùng thuËt to¸n gi¶i bµi to¸n (1.1)-(1.4). 2.2. ThuËt to¸n (0) (0) wj , j = 1, 2, ..., n. T¹i w(0) = (wj ) Bíc chuÈn bÞ. Chän ngÉu nhiªn c¸c gi¸ trÞ (0) (0) , z , w(0) ). ®· chän, gi¶i bµi to¸n phô (1.1)-(1.4), ®îc nghiÖm (x
f (x(0) , z (0) , w(0) ) = β0 lµ gi¸ trÞ kû lôc hiÖn t¹i. Ký hiÖu (k ) Bíc k, (k = 0, 1, ...). §· biÕt gi¸ trÞ kû lôc βk t¹i w . Chän ngÉu nhiªn c¸c gi¸ (k+1) (k ) (k+1) (k+1) trÞ wj = wj , j = 1, 2, ..., n. T¹i w = (wj ) ®· chän, gi¶i bµi to¸n phô (k+1) (k+1) (k+1) (1.1)-(1.4), ®îc nghiÖm (x ,z ,w ). (k+1) (k+1) (k+1) Ký hiÖu f (x ,z ,w ) = βk+1 . + NÕu βk+1 < βk th× gi¸ trÞ kû lôc hiÖn t¹i lµ βk+1 . G¸n k := k + 1, trë l¹i bíc k. (k+1) + NÕu ngîc l¹i, ta lo¹i bá w , trë l¹i bíc k . Bíc kÕt thóc. Víi k ®ñ lín, tÝnh trung b×nh mÉu k 1 k f (x(k) , z (k) , w(k) ). F= k i=1 Tõ ®iÒu kiÖn (1.2), (1.3) vµ (1.4) cho thÊy tËp ph¬ng ¸n cña bµi to¸n lµ kh¸c Chó ý. xij = 0, vµ zj = 0, víi mäi i, j , lµ mét ph¬ng ¸n). MÆt kh¸c, còng rçng (®iÓm cã to¹ ®é tõ ®iÒu kiÖn ®· nªu cho thÊy tËp ph¬ng ¸n bÞ chÆn. Do vËy viÖc gi¶i c¸c bµi to¸n phô ë mçi bíc lu«n cã nghiÖm. §Ó chøng minh sù héi tô cña thuËt to¸n, ta nh¾c l¹i mét kÕt qu¶ quan träng trong [4]. Cho bµi to¸n f (x, w)p(w)dw → min F (x) = (2.1), x ∈ M ⊂ Rn ; p(w) lµ hµm mËt ®é cña ®¹i lîng ngÉu nhiªn w. trong ®ã (k ) Gi¶ sö øng víi c¸c gi¸ trÞ mÉu w , b»ng ph¬ng ph¸p Monte Carlo, cho ta d·y (k ) ph¬ng ¸n x tèt dÇn. Víi k ®ñ lín, ta cã k 1 (k ) f (x(k) , w(k) ). F = k i=1 (x , w ) lµ ph¬ng ¸n tèi u, t¬ng øng víi gi¸ trÞ hµm môc tiªu F ∗ cña bµi ∗ ∗ Ký hiÖu to¸n (2.1). f (∗, w) lµ hµm låi; (Ω, Σ, P ). §Þnh lý [4]. 2.3. Cho kh«ng gian x¸c suÊt Gi¶ sö (k ) (k ) {x } lµ d·y ®éc lËp w M lµ tËp låi, compact; tèt dÇn t¬ng øng c¸c mÉu . Khi ®ã F (k ) → F ∗ (h.c.c). hÇu ch¾c ch¾n 2.4. §Þnh lý. Ta cã P { lim (F (k) − F ∗ ) = 0} = 1. k→∞ Chøng minh. Nh chóng ta ®· thÊy trong ®Þnh lý 2.1, bµi to¸n (1.1)-(1.4) lµ bµi to¸n f quy ho¹ch låi (hµm môc tiªu låi) víi tËp ph¬ng ¸n låi ®a diÖn, kh¸c rçng vµ bÞ chÆn {x(k) } vµ chän mÉu (tËp ph¬ng ¸n låi vµ compact). §ång thêi víi c¸ch x©y dùng d·y (k ) (k ) {x } lµ tèt dÇn. w ®éc lËp ®· nªu trong thuËt to¸n cho ta d·y
Nh vËy c¸c ®iÒu kiÖn cña ®Þnh lý 2.3 ®îc tho¶ m·n. Tõ ®ã suy ra ®iÒu ph¶i chøng 2 minh. III. Th¶o luËn. Bµi to¸n ph©n phèi ®iÖn lµ mét trong nh÷ng bµi to¸n cÇn sím cã ®îc nh÷ng c«ng tr×nh nghiªn cøu hiÖu qu¶. Song song víi bµi to¸n ph©n phèi ®iÖn lµ bµi to¸n dù tr÷ níc cho c¸c hå thuû ®iÖn. Chóng t«i hy väng r»ng, víi thuËt to¸n ®· nªu, trªn mçi m« h×nh cô thÓ, sÏ gãp phÇn tÝch cùc vµo viÖc æn ®Þnh ®iÖn hiÖn nay cña ViÖt Nam. Tµi liÖu tham kh¶o [1] NguyÔn Quý Hû, Ph¬ng ph¸p m« pháng sè Monte Carlo, NXB §¹i häc Quèc gia Hµ Néi, Hµ Néi, 2004. [2] TrÇn Xu©n Sinh, C¸c ph¬ng ph¸p ngÉu nhiªn gi¶i bµi to¸n quy ho¹ch, Bµi gi¶ng dïng cho Sau §¹i häc, chuyªn ngµnh X¸c suÊt thèng kª to¸n häc, §¹i häc Vinh, 2006. [3] NguyÔn Duy TiÕn vµ Vò ViÕt Yªn, Lý thuyÕt x¸c suÊt, NXB Gi¸o dôc, Hµ Néi, 2001. [4] Yuri M. Ermoliev and Vladimir I. Norkin, Monte Carlo optimization and path dependent nonstationary laws of Large numbers, IIASA, International Institute for applied systems analysis, 1998, Web: www.iiasa.ac.at. Summary On the problem of mange a electric solved by method of Monte-Carlo In order to study the problem about supplying electricity, we set up a mathematical model, which is a stochastic convex programming with objective function depending on a stochastic variable. Then, we construct a Monte-Carlo algorithm combining with a algorithm for solving convex programming problems to find an optimization plan. (a) Khoa To¸n, Trêng §¹i häc Vinh (b) Cao häc 14, X¸c suÊt thèng kª, Trêng §¹i häc Vinh.