Một trong những giải pháp nâng cao độ tin cậy cung cấp điện của lưới điện phân phối là lắp đặt dao cách ly phân đoạn trên các nhánh của lưới điện. Nhờ giảm phạm vi và thời gian mất điện khi cô lập sự cố nên sẽ giảm được thiệt hại hằng năm do mất điện. Tuy nhiên cần phải đầu tư kinh phí để lắp đặt và vận hành bảo dưỡng. Vì vậy, cần phải tính toán tìm phương án tối ưu lắp đặt các thiết bị phân đoạn. Trong bài báo này, trình bày việc giải bài toán tối ưu hóa việc lắp đặt dao cách ly phân đoạn trên lưới điện phân phối hình tia bằng phương pháp quy hoạch động. Bài toán tối ưu được chia thành nhiều bước tính, các điều khiển tối ưu ở từng bước tìm được dựa vào phương trình truy toán quy hoạch động Bellman. Trên cơ sở thuật toán và chương trình được xây dựng, bài báo trình bày ví dụ áp dụng để minh họa cho phương pháp.
Tài liệu tham khảo
[1] Trần Bách, Lưới điện và Hệ thống điện, tập II, NXB Khoa học và Kỹ thuật, 2000. [2] Đặng Ngọc Dinh và các cộng sự; Hệ thống điện, NXB Khoa học và Kỹ thuật, 1980. [3] J. Endrenyi, Reliability Modelling in Electric Power Systems, John Wiley & Sons, 1978. [4] Allen J. Wood, Power Generation, Operation, and Control, John Wiley & Sons, 1996. [5] Trần Tấn Vinh, “Tính toán các chỉ tiêu độ tin cậy hệ thống điện phân phối dựa trên trạng thái các phần tử”, Tạp chí Khoa học và Công nghệ ĐHĐN, Số 05[90], 2015. [6] Hô Quang Vĩnh, “Tối ưu hóa số lượng và vị trí đặt thiết bị phân đoạn trên lưới điện phân phối bằng phương pháp quy hoạch động”, Luận văn thạc sĩ kỹ thuật, ĐHĐN, 2009.
Xem thêm
plugins.themes.academic_pro.article.sidebar##
Cách trích dẫn
Tran Tan Vinh. “Tính toán lắp đặt tối ưu Dao cách Ly phân đoạn Trên lưới điện phân phối bằng phương pháp Quy hoạch động”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 5, số p.h 114, Tháng Năm 2017, tr 11-15, //jst-ud.vn/jst-ud/article/view/3171.
Cuốn sách này được hoàn thành trên cơ sở Bài giảng của cùng tác giả được sử dụng cho học phần "Tối ưu hóa chế độ hệ thống điện" thuộc chương trình đào tạo Kỹ sư Kỹ thuật điện, Khoa Điện, Trường Điện ‒ Điện tử, Đại học Bách khoa Hà Nội. Các tác giả hy vọng cuốn sách này cũng là tài liệu tham khảo hữu ích cho việc giảng dạy, học tập và nghiên cứu về ứng dụng lý thuyết tối ưu hóa trong vận hành hệ thống điện ở các trường đại học kỹ thuật khác.
Nội dung của cuốn sách gồm bốn chương và phần phụ lục, trong đó các tác giả trình bày một số bài toán từ cơ bản đến nâng cao và có ý nghĩa quan trọng về vận hành hệ thống điện theo cơ chế thị trường, bao gồm nguyên lý điều chỉnh công suất để đảm bảo yêu cầu chất lượng điện năng, phân bố tối ưu công suất và lựa chọn tổ máy vận hành. Phần phụ lục giới thiệu về phương pháp giải bài toán tối ưu sử dụng quy hoạch tuyến tính [LP].
Quy hoạch động [QHĐ] là một lớp thuật toán rất quan trọng và có nhiều ứng dụng trong ngành khoa học máy tính. Trong các cuộc thi Olympic tin học hiện đại, QHĐ luôn là một trong những chủ đề chính. Tuy vậy, theo tôi thấy, tài liệu nâng cao về QHĐ bằng tiếng Việt hiện còn cực kỳ khan hiếm, dẫn đến học sinh/sinh viên Việt Nam bị hạn chế khả năng tiếp cận với những kỹ thuật hiện đại. Trong bài viết này, tôi sẽ trình bày một vài kỹ thuật để tối ưu hóa độ phức tạp của một số thuật toán QHĐ.
Table of Contents
1. Đổi biến
Nhiều khi trong trạng thái QHĐ có một thành phần nào đấy với khoảng giá trị quá lớn, trong khi kết quả của hàm lại có khoảng giá trị nhỏ. Trong một vài trường hợp, ta có thể đảo nhãn để giảm số trạng thái.
Bài tập ví dụ
Longest Common Subsequence [LCS]
Đề bài
Cho xâu A độ dài m, xâu B độ dài n. Hãy tìm độ dài xâu con chung dài nhất của hai xâu, chú ý là xâu con chung có thể không liên tiếp.
Giới hạn
- $m \le 10^6$
- $n \le 5000$
- Các kí tự trong cả hai xâu là các chữ cái tiếng Anh in hoa 'A'..'Z'
Ví dụ
A = ADBCC
B = ABCD
LCS = ABC
Kết quả = 3Lời giải
Thuật toán đơn giản
Gọi $F[i, j]$ là LCS của hai tiền tố $A_{1..i}$ và $B_{1..j}$.
Khi đó ta có thể maximize $F[i, j]$ theo $F[i-1, j]$ và $F[i, j-1]$.
Nếu $A_i = B_j$ thì ta có thể cập nhật $F[i, j]$ theo $F[i-1, j-1] + 1$.
Kết quả bài toán là $F[m, n]$.
Độ phức tạp của thuật toán này là $O[m*n]$, không khả thi với giới hạn của đề bài.
Đổi biến
Đặt $L = min[m, n]$
Để ý rằng trong hàm QHĐ trên, các giá trị của $F[i, j]$ sẽ không vượt quá $L$, trong khi đó chiều thứ hai của trạng thái có thể khá lớn [lên tới $MAXM = 10^6$].
Để tối ưu hóa, ta sẽ đổi biến. Gọi $dp[i, j]$ là vị trí $k$ nhỏ nhất sao cho $LCS[A_{1..i}, B_{1..k}] = j$.
Để tính các giá trị của $dp$, ta sẽ QHĐ theo kiểu cập nhật đi, thay vì đi tìm công thức trực tiếp cho các $dp[i, j]$.
Gọi $nextPos[i, c] = j > i$ nhỏ nhất mà $A_j = c$ [với $c$ là một ký tự từ 'A' đến 'Z'].
Mảng $nextPos$ có thể tính trong $T[M*26]$.
Như vậy ta có thể tính các giá trị QHĐ như sau:
- Ban đầu khởi tạo các giá trị $dp[i, j] = \infty$, $dp[0, 0] = 0$.
- For $i$ và $j$ tăng dần, với mỗi giá trị $dp[i, j]$ khác vô cùng:
- Cập nhật $dp[i+1, j]$ theo $dp[i, j]$.
- Gọi $k$ là vị trí xuất hiện tiếp theo của $B_{i+1}$ trong xâu $A$ bắt đầu từ vị trí $dp[i, j]$, tức là $k = nextPos[dp[i, j], B_{i+1}]$.
- Nếu tồn tại $k$, cập nhật $dp[i+1, j+1]$ theo $k$.
Để tính kết quả, ta sẽ chỉ cần tìm $j$ lớn nhất mà tồn tại $dp[i, j]$ khác vô cùng.
# include
using namespace std;
const int M = 1e6 + 6;
const int N = 5005;
int dp[N][N];
char a[M], b[N];
int nextPos[M][26];
int m, n;
void minimize[int &a, int b] {
if [a == -1 || a > b] a = b;
}
int main[] {
cin >> a + 1 >> b + 1;
m = strlen[a + 1]; n = strlen[b + 1];
for [int c = 0; c < 26; ++c]
for [int i = m - 1; i >= 0; --i]
nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c];
int maxLength = min[m, n];
memset[dp, -1, sizeof dp];
dp[0][0] = 0;
for [int i = 0; i < n; ++i] {
for [int j = 0; j = 0] {
minimize[dp[i + 1][j], dp[i][j]];
int new_value = nextPos[dp[i][j]][b[i + 1] - 'A'];
if [new_value > 0]
minimize[dp[i + 1][j + 1], new_value];
}
}
int ans = 0;
for [int j = maxLength; j > 0; --j] {
for [int i = j; i = 0] ans = j;
if [ans != 0] break;
}
cout y >> b >> n;
cout x >> a >> y >> b >> n;
cout R] return;
int mid = L + R >> 1;
best[mid] = from;
for [int i = from + 1; i eval[mid + 1, i]]
best[mid] = i;
solve[L, mid - 1, from, best[mid]];
solve[mid + 1, R, best[mid], to];
}Đánh giá độ phức tạp thuật toán: vì mỗi lần gọi để quy khoảng $[L,R]$ được chia đôi, nên sẽ có $O[logN]$ tầng, mỗi tầng vòng for chỉ chạy qua $O[N]$ phần tử, vì vậy độ phức tạp của thuật toán là $O[NlogN]$.
SEQPART - Hackerrank
Đề bài
Cho dãy $L$ số $C[1..L]$, cần chia dãy này thành $G$ đoạn liên tiếp. Với phần tử thứ $i$, ta định nghĩa chi phí của nó là tích của $C[i]$ và số lượng số nằm cùng đoạn liên tiếp với nó. Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử.
Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.
Input
- Dòng đầu tiên chứa 2 số $L$ và $G$.
- $L$ dòng tiếp theo, chứa giá trị của dãy $C$.
Output
- Một dòng duy nhất chứa chi phí nhỏ nhất.
Giới hạn
- $1 \le L \le 8000$.
- $1 \le G \le 800$.
- $1 \le C[i] \le 10^9$.
Ví dụ
Input
6 3
11
11
11
24
26
100
Output
299Giải thích: cách tối ưu là $C[] = [11, 11, 11], [24, 26], [100]$.
Chi phí là $11 * 3 + 11 * 3 + 11 * 3 + 24 * 2 + 26 * 2 + 100 * 1 = 299$.
Lời giải
Đây là dạng bài toán phân hoạch dãy số có thể dễ dàng giải bài QHĐ. Gọi $F[g, i]$ là chi phí nhỏ nhất nếu ta phân hoạch $i$ phần tử đầu tiên thành $g$ nhóm, khi đó kết quả bài toán sẽ là $F[G, L]$.
Để tìm công thức truy hồi cho hàm $F[g, i]$, ta sẽ quan tâm đến nhóm cuối cùng. Coi phần tử 0 là phần tử cầm canh ở trước phần tử thứ nhất, thì người cuối cùng không thuộc nhóm cuối có chỉ số trong đoạn $[0, i]$. Giả sử đó là người với chỉ số k, thì chi phí của cách phân hoạch sẽ là $F[g-1, k] + Cost[k+1, i]$, với $Cost[i, j]$ là chi phí nếu phân $j-i+1$ người có chỉ số $[i, j]$ vào một nhóm. Như vậy:
$F[g, i] = min[F[g-1, k] + Cost[k+1, l]]$ với $0 > L >> G; for [int i = 1; i > C[i]; sum[i] = sum[i - 1] + C[i]; } for [int g = 1; g > L >> G; for [int i = 1; i > C[i]; sum[i] = sum[i - 1] + C[i]; } for [int i = 1; i > b + 1; m = strlen[a + 1]; n = strlen[b + 1]; for [int c = 0; c < 26; ++c] for [int i = m - 1; i >= 0; --i] nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c]; int maxLength = min[m, n]; memset[dp, -1, sizeof dp]; dp[0][0] = 0; for [int i = 0; i < n; ++i] { for [int j = 0; j = 0] { minimize[dp[i + 1][j], dp[i][j]]; int new_value = nextPos[dp[i][j]][b[i + 1] - 'A']; if [new_value > 0] minimize[dp[i + 1][j + 1], new_value]; } } int ans = 0; for [int j = maxLength; j > 0; --j] { for [int i = j; i = 0] ans = j; if [ans != 0] break; } cout > a + 1 >> b + 1; m = strlen[a + 1]; n = strlen[b + 1]; for [int c = 0; c < 26; ++c] for [int i = m - 1; i >= 0; --i] nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c]; int maxLength = min[m, n]; memset[dp, -1, sizeof dp]; dp[0][0] = 0; for [int i = 0; i < n; ++i] { for [int j = 0; j = 0] { minimize[dp[i + 1][j], dp[i][j]]; int new_value = nextPos[dp[i][j]][b[i + 1] - 'A']; if [new_value > 0] minimize[dp[i + 1][j + 1], new_value]; } } int ans = 0; for [int j = maxLength; j > 0; --j] { for [int i = j; i = 0] ans = j; if [ans != 0] break; } cout > a + 1 >> b + 1; m = strlen[a + 1]; n = strlen[b + 1]; for [int c = 0; c < 26; ++c] for [int i = m - 1; i >= 0; --i] nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c]; int maxLength = min[m, n]; memset[dp, -1, sizeof dp]; dp[0][0] = 0; for [int i = 0; i < n; ++i] { for [int j = 0; j = 0] { minimize[dp[i + 1][j], dp[i][j]]; int new_value = nextPos[dp[i][j]][b[i + 1] - 'A']; if [new_value > 0] minimize[dp[i + 1][j + 1], new_value]; } } int ans = 0; for [int j = maxLength; j > 0; --j] { for [int i = j; i = 0] ans = j; if [ans != 0] break; } cout > a + 1 >> b + 1; m = strlen[a + 1]; n = strlen[b + 1]; for [int c = 0; c < 26; ++c] for [int i = m - 1; i >= 0; --i] nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c]; int maxLength = min[m, n]; memset[dp, -1, sizeof dp]; dp[0][0] = 0; for [int i = 0; i < n; ++i] { for [int j = 0; j = 0] { minimize[dp[i + 1][j], dp[i][j]]; int new_value = nextPos[dp[i][j]][b[i + 1] - 'A']; if [new_value > 0] minimize[dp[i + 1][j + 1], new_value]; } } int ans = 0; for [int j = maxLength; j > 0; --j] { for [int i = j; i = 0] ans = j; if [ans != 0] break; } cout a[i]$: Trường hợp này ta cần đẩy $a[i]$ vào tập hợp $S$ hai lần. Bởi phần hàm số bên trái $a[i]$ sẽ có độ dốc giảm đi $1$, trong khi phần từ $a[i]$ đến $Opt[i-1]$ có độ dốc tăng thêm $1$. Để ý là $Opt[i-1]$ không còn là điểm đầu tiên mà từ đó hàm $F$ đạt cực tiểu nữa, ta xóa $Opt[i-1]$ khỏi tập hợp $S$.
Các thao tác chèn xóa và lấy $max$ của tập hợp có thể dễ dàng cài đặt bằng std::multiset trong C++, hay sử dụng Binary Heap nếu code Pascal.
Như vậy độ phức tạp của lời giải trên là $O[NlogN]$.
# include
using namespace std;
const int M = 1e6 + 6;
const int N = 5005;
int dp[N][N];
char a[M], b[N];
int nextPos[M][26];
int m, n;
void minimize[int &a, int b] {
if [a == -1 || a > b] a = b;
}
int main[] {
cin >> a + 1 >> b + 1;
m = strlen[a + 1]; n = strlen[b + 1];
for [int c = 0; c < 26; ++c]
for [int i = m - 1; i >= 0; --i]
nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c];
int maxLength = min[m, n];
memset[dp, -1, sizeof dp];
dp[0][0] = 0;
for [int i = 0; i < n; ++i] {
for [int j = 0; j = 0] {
minimize[dp[i + 1][j], dp[i][j]];
int new_value = nextPos[dp[i][j]][b[i + 1] - 'A'];
if [new_value > 0]
minimize[dp[i + 1][j + 1], new_value];
}
}
int ans = 0;
for [int j = maxLength; j > 0; --j] {
for [int i = j; i = 0] ans = j;
if [ans != 0] break;
}
cout b] a = b;
}
int main[] {
cin >> a + 1 >> b + 1;
m = strlen[a + 1]; n = strlen[b + 1];
for [int c = 0; c < 26; ++c]
for [int i = m - 1; i >= 0; --i]
nextPos[i][c] = [a[i + 1] - 'A' == c] ? i + 1 : nextPos[i + 1][c];
int maxLength = min[m, n];
memset[dp, -1, sizeof dp];
dp[0][0] = 0;
for [int i = 0; i < n; ++i] {
for [int j = 0; j = 0] {
minimize[dp[i + 1][j], dp[i][j]];
int new_value = nextPos[dp[i][j]][b[i + 1] - 'A'];
if [new_value > 0]
minimize[dp[i + 1][j + 1], new_value];
}
}
int ans = 0;
for [int j = maxLength; j > 0; --j] {
for [int i = j; i = 0] ans = j;
if [ans != 0] break;
}
cout