Áp dụng phương pháp Nhánh và cận để quy hoạch mở rộng lưới điện huyện Phú Xuyên khi xét đến mạng điện có sẵn ở địa phương

- Mô hình l-ới điện Hình 4.4.
- Cây ph-ơng án của bài toán Hình 4.5.
- Sơ đồ khối của thuật toán nhánh và cận.
- Hình 4.7 : Sơ đồ khối sử dụng kỹ thuật đệ quy khi rẽ nhánh và quay lui khi tìm kiếm ph-ơng án tối -u Hình 4.6.
- Mô hình l-ới điện Hình 4.7.
- Cây ph-ơng án của bài toán Hình 4.8.
- Sơ đồ thuật toán ph-ơng pháp nhánh cận cải biên Hình 4.9: Giao diện chính của ch-ơng trình nhánh cận cải biên Hình 4.10: Giao diện các thông số nhập dữ liệu của ch-ơng trình nhánh cận cải biên Hình 4.11: Sơ đồ graph ví dụ với 1 nút nguồn và 04 nút tải.
- Hình 4.12 Cây ph-ơng án của ph-ơng án nhánh cận cải biên Hình 4.13: Số liệu nguuồn và tải, chiều dài các nhánh tải theo VD Hình 4.14: Kết quả tổng hợp với cây có thành phần Z1 và Z2 là nhỏ nhất Hình 4.15: Kết quả tổng hợp ph-ơng án tối -u của l-ới điện theo VD Hỡnh 5.1: B.
- Tuy ta p quy là phương phỏp Nhỏnh và cận.
- Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Bài toán quy hoạch phát triển mở rộng hệ thống điện th-ờng đ-ợc đặt ra nh- sau: Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Yêu cầu tìm ph-ơng án kết cấu l-ới tối -u để xây dựng và đ-a các đối t-ợng mới vào vận hành, đảm bảo đạt đ-ợc yêu cầu hàm chi phí tính toán là cực tiểu trong giai đoạn thời gian nào đó, đồng thời thoả mãn các ràng buộc về kinh tế kỹ thuật.
- Nhìn chung, bài toán quy hoạch phát triển mở rộng l-ới điện là một bài toán tối -u đa mục tiêu, nhiều cực trị với các biến số liên tục và rời rạc, các ràng buộc của bài toán có dạng đẳng thức hoặc bất đẳng thức.
- Tuỳ theo l-ợng thông tin ban đầu có đ-ợc, ng-ời ta th-ờng chia bài toán quy hoạch ra thành các loại: tất định, ngẫu nghiên xác định và bất định.
- Đối với mỗi loại bài toán ng-ời ta có các mô hình toán học và các ph-ơng pháp giải khác nhau.
- Đối với bài toán tất định, thông tin ban đầu đã đ-ợc xác định và nó là duy nhất.
- Thông th-ờng, bài toán đ-ợc chia ra thành 2 dạng: mô hình tĩnh và mô hình động.
- Hàm mục tiêu của bài toán đ-ợc biểu diễn nh- sau: Z= kjn1kn1jkjjim1in1jjixCxC.
- m: số nút nguồn cung cấp Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- xijt  fijt - xij(t-1) Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 8920 34 AC Hoàng Long Hoàng, Phỳ Tỳc Bảng 2.2: Phạm vi cấp điện của cỏc xuất tuyến sau trạm 110kV và sau trạm TG Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 35/6 2x Bảng 2.4: Tỡnh trạng mang tải trạm trung gian Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 2011 Pmax (kW kWh Pmax (kW kWh Bảng 3.1: Kết quả dự bỏo nhu cầu điện ngành Cụng nghiệp – xõy dựng Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 6,08% Bảng 3.2: Kết quả dự bỏo nhu cầu điện ngành nụng – lõm – thủy sản Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 539 836 Bảng 3.7: Nhu cầu cụng suất huyện Phỳ Xuyờn giai đoạn Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 43 Ch-ơng IV: áp dụng ph- ơng pháp nhánh và cận TronG tr- ờng hợp đã tồn tại một mạng điện có sẵn 4.1.
- Đặt bài toán nhánh và cận xác định cấu trúc tối -u của l-ới điện Quy hoạch l- ới điện là một phần rất quan trọng của quy hoạch hệ thống năng l- ợng.
- Nhiệm vụ của nó là xác định một cấu trúc tối - u của l- ới điện theo sự tăng tr- ởng của phụ tải và một sơ đồ quy hoạch nguồn đối với thời gian quy hoạch ứng với yêu cầu phân phối điện năng một cách an toàn và kinh tế.
- Nói chung việc quy hoạch l- ới điện sẽ đ- a ra đ- ợc ph- ơng án về vị trí đặt đ- ờng dây ti in, thời điểm xây dựng chúng và kết cấu xây dựng của chúng.
- Sau khi đã chọn đ- ợc cấp điện áp tối - u, ng- ời ta phải giải quyết bài toán xác định cấu trúc tối - u của l- ới điện.
- Để đáp ứng đ- ợc yêu cầu này, việc tr- ớc tiên ta sẽ căn cứ vào nhu cầu phụ tải đã đ- ợc dự báo, đặt ra bài toán để áp dụng ph- ơng pháp tối - u toán học chặt chẽ giải tìm kết quả.
- Bài toán này có thể phát biểu nh- sau: Cho biết công suất và vị trí địa lí của các nguồn điện và phụ tải điện, cần xác định sơ đồ nối dây tối - u của l- ới điện thiết kế nhằm thoả mãn cực tiểu hàm chi phí tính toán Z.
- Ph- ơng pháp đơn giản nhất là liệt kê tất cả các ph- ơng án sơ đồ nối dây theo chỉ tiêu hàm chi phí cực tiểu, sau đó chọn ra ph- ơng án ứng với giá trị cực tiểu của hàm chi phí Z.
- Tuy nhiên khi xét đến mọi ph- ơng án nối dây thì khối l- ợng tính toán sẽ rất lớn và khó có thể thực hiện đ- ợc.
- Để khắc phục nh- ợc điểm đó ng- ời ta đã cố gắng áp dụng các ph- ơng pháp quy hoạch toán học để tìm ph- ơng án tối - u theo h- ớng nhanh nhất và áp dụng đ- ợc các thuật toán có thể lập trình để chạy trên máy tính.
- Trong luận văn này, chúng tôi áp dụng ph- ơng pháp đã đ- ợc nhiều nhà khoa học nghiên cứu, đó là ph- ơng pháp nhánh và cận.
- Đây là một ph- ơng pháp quy hoạch tối - u có thuật toán rõ ràng, các b- ớc chặt chẽ, có thể lập trình để tạo ra phần mềm chuyên dụng.
- Ph-ơng pháp giải bài toán bằng thuật toán nhánh cận 4.2.1.
- Xây dựng hàm mục tiêu Để lập hàm mục tiêu của bài toán ta xác định công thức của hàm chi phí tính toán nh- sau: Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Nh- vậy biểu thức hàm chi phí tính toán hàng năm Z của ph- ơng án phụ thuộc vào các giá trị Iij theo dạng: Khi đó bài toán xác định cấu trúc tối - u của l- ới điện trở thành bài toán xác định tập Iij sao cho hàm chi phí tính toán Z(Iij) đạt giá trị cực tiểu.
- Khi đó bài toán đ- ợc mô tả d- ới dạng toán học sau.
- n1j,in1j,iijijijijijij;0IkhiminI.L.L.A;0Ikhi0Z Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Từ đó suy ra điều kiện của bài toán là Xác định tập  Iij  sao cho : min Z(Iij.
- Trong công thức trên thì W gọi là giá trị cận d- ới của hàm mục tiêu Z của một ph- ơng án bất kì và ta không thể tìm đ- ợc ph- ơng án nào có hàm chi phí tính toán nhỏ hơn W.
- Giá trị của hàm chi phí tính toán chỉ bằng W khi ph- ơng án đ- ợc chọn vừa là ph- ơng án có vốn đầu t- cực tiểu, vừa là ph- ơng án có tổn thất điện năng nhỏ nhất.
- Tuy nhiên điều này rất khó có thể xảy ra trong thực tế vì một ph- ơng án có vốn đầu t- bé rất khó có thể đảm bảo rằng tổn thất điện năng là nhỏ nhất.
- Để có thể tìm đ- ợc lời giải tối - u cho bài toán trên chúng tôi áp dụng ph- ơng pháp cận và nhánh và tiến hành theo các b- ớc sau đây: Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 48 4.2.2 Thuật toán tìm cấu trúc tối -u của l-ới điện bằng ph-ơng pháp nhánh và cận B-ớc 1: Tìm ph-ơng án cây bao trùm nhỏ nhất Để tìm ph- ơng án có cây bao trùm nhỏ nhất ta có thể sử dụng lý thuyết graph để xác định, và đó chính là ph- ơng án có tổng chiều dài đ- ờng dây nhỏ nhất.
- Sơ đồ thuật toán tìm cây bao trùm nhỏ nhất đ- ợc biểu diễn nh- sau: Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 49 Hình 4.1: Sơ đồ thuật toán Prim tìm cây bao trùm nhỏ nhất B-ớc 2: Tìm ph-ơng án có chi phí tổn thất điện năng Z2 là nhỏ nhất Ph- ơng án ứng với minZ2 là ph- ơng án có cực tiểu của tổng các tích giữa chiều dài các cạnh và dòng điện t- ơng ứng đi trên đó.
- Đó cũng chính là ph- ơng án có tổng mômen phụ tải Pij.Lij nhỏ nhất hoặc tổng tổn thất điện năng trong l- ới điện là nhỏ nhất.
- Bài toán có thể mô tả d- ới dạng toán học nh- sau: Xác định Iij sao cho Z2 = min..1,ijnjiijIL Ak=0;C=0.
- Sc:=Sc+1 C chứa các cạnh của cây bao trùm nhỏ nhất của graph In kết quả Sc=n-1 Nhập số liệu về graph đầy đủ của mạng điện Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Iji = 0 Để giải quyết bài toán này ta có thể áp dụng ph- ơng pháp đơn hình.
- Thuật toán đơn hình là ph- ơng pháp hoàn thiện lời giải, nghĩa là từ một lời giải cơ bản, bài toán này cho phép đi nhanh nhất đến lời giải tối - u.
- Ta cần xác định số ẩn cơ bản, đó chính là m ẩn độc lập trong hệ ph- ơng trình ràng buộc, đồng thời thoả mãn hàm mục tiêu.
- Sau đó ta chuyển sang ph- ơng án mới và tiếp tục kiểm tra điều kiện tối - u.
- Đến khi điều kiện tối - u thoả mãn, ph- ơng án ta tìm đ- ợc chính là ph- ơng án có chi phí tổn thất điện năng cực tiểu.
- Giả thiết bài toán đã thực hiện đến b- ớc s, bảng đơn hình có dạng: B- ớc tính Hệ số ẩn cơ bản Tên ẩn CB Lời giải x1 x2 xk xn c1 c2 cn s cj x1(s) b1(s) a11(1s) a12(2s) a1k(ks) a1n(ns) x2(s) b2(s) a21(1s) a22(2s) a2k(ks) a2n(ns) xl(s) bl(s) al1(1s) al2(2s) alk(ks) aln(ns) xn(s) bm(s) am1(1s) am2(2s) amk(ks) amn(ns) f(x) f1(s)(x) 1(s) 2(s) k(s) m(s) Bảng 4.1: Bảng đơn hình ở b-ớc giải thứ s Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- ở hàng i  l: Sơ đồ khối giải bài toán đơn hình đ- ợc trình bày trong hình 4.2.
- In kết quả Kết thúc Đ S Đ S Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 53 Để giải quyết bài toán tìm chi phí tổn thất điện năng nhỏ nhất, trong luận văn này chúng tôi xây dựng hệ ph- ơng trình ràng buộc phụ từ hệ ph- ơng trình : a11x1 + a12x2.
- aij : là khoảng cách giữa 2 đỉnh i và j Sau đó cần lập hệ ph- ơng trình ràng buộc theo quy tắc sau đây : a11x1 + a12x2.
- Nh- vậy để tìm các giá trị nguyên của các ẩn cơ bản, ta đ- a thêm ẩn phụ và x1p, x2p , xmp và chuyển sang phần giải bài toán đơn hình mở rộng.
- Bắt đầu từ nó ta có thể tiến hành thuật toán đơn hình để giải bài toán gốc.
- B-ớc 3: Thực hiện ph-ơng pháp nhánh và cận để tìm ph-ơng án tối -u Dựa trên cơ sở vừa tìm đ- ợc là ph- ơng án có Z1min và ph- ơng án có Z2min, thực hiện tối - u hoá theo nguyên tắc của kỹ thuật nhánh cận để tìm cấu trúc tối - u của l- ới điện thiết kế.
- Ta có W =W1+W2 là giá trị cận d- ới của hàm mục tiêu Z của một ph- ơng án bất kì .
- 54 Với tinh thần đó, ta sẽ đi tìm thuật toán để phối hợp các ph- ơng án có minZ1 và minZ2 đồng thời luôn luôn để ý tới giá trị của cận W.
- Do số ph- ơng án nối dây của l- ới điện là rất lớn.
- Nếu chỉ xét mạng hở thì đã có tới nn-2 ph- ơng án.
- Vì vậy để giảm bớt khối l- ợng tính toán ta có thể bỏ qua những tập ph- ơng án mà biết chắc chắn trong tập đó không chứa ph- ơng án tối - u.
- Để làm đ- ợc việc đó ta tiến hành phân nhánh, tức là chia các ph- ơng án thành những tập có chứa nhánh ij và tập không chứa nhánh ij, ở mỗi tập tr- ớc hết chỉ cần tìm giá trị cận W.
- Khi đó, các b- ớc tiến hành của ph- ơng pháp nhánh và cận nh- sau: B-ớc 3.1: Lập cây ph-ơng án Từ đỉnh O ban đầu của cây ph- ơng án, vẽ các nhánh liên tiếp về phía tay phải theo thứ tự tăng dần: cạnh a ngắn hơn cạnh b, cạnh b ngắn hơn cạnh c, cạnh c ngắn hơn cạnh d (hình 2.4).
- Cây ph-ơng án của bài toán Các đỉnh O, A, B, C, D mô tả tập hợp các cây của graph l- ới điện.
- So sánh WE với ZD: Nếu WE > ZD thì suy ra trong tập các ph- ơng án ứng với E không có ph- ơng án tối - u, do đó, ta quay lại C và đi lên B Nếu WE < ZD thì ta phải phân nhánh tiếp B-ớc 3.3: Với giả thiết WE > ZD thì ta quay lại C, đi lên B rồi rẽ nhánh đến F.
- N là đỉnh có các ph- ơng án chứa a, b, d nh- ng không chứa c và k.
- B-ớc 3.6: Giả sử WN > ZK thì suy ra trong tập các ph- ơng án ứng với N không có ph- ơng án tối - u, do đó ta quay lại I và đi lên F.
- P là đỉnh có các ph- ơng án chứa a, b nh- ng không chứa c và d.
- L là tập hợp các ph- ơng án có chứa cạnh a song không chứa b.
- M là tập hợp các ph- ơng án không chứa cạnh a song có thể chứa b, c.
- Nếu WM > ZK thì thuật toán dừng vì không thể tìm đ- ợc ph- ơng án nào có hàm chi phí nhỏ hơn ZK.
- Kết luận: Với các giả thuyết nh- trên thì ph- ơng án tối - u là ph- ơng án ứng với đỉnh K (K là ph- ơng án chứa các cạnh a, b, c, k).
- Sơ đồ khối của thuật toán nhánh cận đ- ợc trình bày trong hình 4.5 Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Z1+W2 Zm thì bỏ qua tập ph- ơng án đó, nếu Z'1+W2 < Zm thì tính Z'2 của cây bao trùm mới.
- Nếu Z'1+Z'2 > Zm thì bỏ qua và quay lại b- ớc 1, ng- ợc lại sẽ lấy giá trị Z'1+Z'2 của ph- ơng án mới làm giá trị để so sánh tiếp.
- Quá trình cứ tiếp tục cho đến khi đến nút của cạnh thuộc tập T1 (k=v) thì dừng lại, ph- ơng án có giá trị min nhất chính là ph- ơng án cần tìm.
- ở đây, khi tính so sánh giá trị hàm mục tiêu khi tìm theo ph- ơng pháp nhánh cận và ph- ơng pháp nhánh cận cải biên ta cần phải phân biệt nh- sau.
- Trong ph- ơng pháp nhánh cận đơn thuần, hàm Z1 đ- ợc tính cho tất cả các cạnh có mặt trong ph- ơng án, mặc dù có thể có một số cạnh đã có và không phải tốn chi phí xây dựng nữa.
- Còn trong ph- ơng pháp nhánh cận cải biên, sau khi đã phân biệt ra 2 tập cạnh T1, T2 ta sẽ không tính chi phí Z1 của tập T1 là tập các cạnh đã có trong mạng điện cũ mà chỉ tính chi phí Z1 của các cạnh có mặt trong tập T2 các cạnh mới phát sinh.
- Khi đó, các b- ớc tiến hành của ph- ơng pháp nhánh và cận cải biên đ- ợc thực hiện nh- sau: Các b- ớc làm b- ớc 1, 2 đều làm giống nh- phần b- ớc 1, 2 của nhánh cận B-ớc 3’: Thực hiện ph-ơng pháp nhánh và cận cải biên để tìm ph-ơng án tối -u B-ớc 3.1': Lập cây ph- ơng án Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- 64 Từ đỉnh H đến đỉnh O ban đầu là cây ph- ơng án của mạng điện cũ đã đ- ợc bố trí là 2 cạnh h và g, vẽ các nhánh liên tiếp về phía tay phải theo thứ tự tăng dần: cạnh a ngắn hơn cạnh b, cạnh b ngắn hơn cạnh c, cạnh c ngắn hơn cạnh d của mạng điện mới (hình 4.7).
- Hoàn toàn đi tìm cây bao trùm nhỏ nhất nh- trong ph- ơng án nhánh cận đã trình bày ở trên.
- Cây ph-ơng án của bài toán Các đỉnh O, A, B, C, D mô tả tập hợp các cây của graph l- ới điện hoàn toàn mới.
- Z2D*: Có xét đến mạng điện cũ Vì đây là cây bao trùm nhỏ nhất nên Z1D = W1D = W1.
- 65 So sánh WE với ZD: Nếu WE > ZD thì suy ra trong tập các ph- ơng án ứng với E không có ph- ơng án tối - u, do đó, ta quay lại C và đi lên B Nếu WE < ZD thì ta phải phân nhánh tiếp B-ớc 3.3': Với giả thiết WE > ZD thì ta quay lại C, đi lên B rồi rẽ nhánh đến F.
- B-ớc 3.6': Giả sử WN > ZK thì suy ra trong tập các ph- ơng án ứng với N không có ph- ơng án tối - u, do đó ta quay lại I và đi lên F.
- 66 Kết luận: Với các giả thuyết nh- trên thì ph- ơng án tối - u là ph- ơng án ứng với đỉnh K (K là ph- ơng án chứa các cạnh a, b, c, k, g, h).
- Sơ đồ khối của thuật toán nhánh cận đ- ợc trình bày trong hình 4.8 Áp dụng phương phỏp nhỏnh và cận trong quy hoạch mạng điện địa phương.
- Sơ đồ thuật toán ph-ơng pháp nhánh cận cải biên Phng ỏn D cú min Z = W

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt