Bài giảng EE 4108 tối ưu hóa chế độ hệ thống điện Chương 3: ThS. Phạm Năng Văn

EE 4108 TỐI ƯU HÓA CHẾ ĐỘ HỆ THỐNG ĐIỆN

Chương 3 LỰA CHỌN THÀNH PHẦN TỔ MÁY VẬN HÀNH

Th.S Phạm Năng Văn Bộ môn Hệ thống điện – Viện Điện TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

NỘI DUNG

(cid:1) Giới thiệu (cid:1) Dự trữ quay trong hệ thống điện (cid:1) Các ràng buộc của bài toán (cid:1) Mô hình toán học của bài toán UC (cid:1) Phương pháp thứ tự ưu tiên (Priority – list method) (cid:1) Quy hoạch động (Dynamic Programming) nhân (cid:1) Phương

tử Lagrange

pháp

(Lagrange

relaxation method)

(cid:1) Quy hoạch nguyên hỗn hợp (Mixed Integer

Programming)

NỘI DUNG

(cid:1) UC có ràng buộc an toàn (SCUC) (cid:1) Áp dụng bài toán UC trong hoạt động thị trường

điện (Daily aution using a unit commitment)

3.1 GIỚI THIỆU

(cid:1) Economic Dispatch (ED): (cid:1) Biết công suất phụ tải (cid:1) Biết các tổ máy đang vận hành (cid:1) Các tổ máy phát công suất bằng bao nhiêu để tổng chi phí

sản xuất toàn hệ thống nhỏ nhất?

L

3.1 GIỚI THIỆU

(cid:1) Đồ thị phụ tải:

3.1 GIỚI THIỆU

(cid:1) Unit commitment (UC): (cid:1) Biết đồ thị phụ tải (cid:1) Các tổ máy sẵn sàng làm việc (cid:1) Tổ máy nào nên vận hành, tổ máy nào nên dừng và công suất phát của các tổ máy bằng bao nhiêu để cực tiểu chi phí sản xuất trong khoảng thời gian xét?

?

Load Profile

G

3.1 GIỚI THIỆU

(cid:1) Ví dụ 3.1: • Tổ máy 1:

2 ($/h)

• PMin = 250 MW, PMax = 600 MW • C1 = 510 + 7,9 P1 + 0,00172 P1

• Tổ máy 2:

2 ($/h)

• PMin = 200 MW, PMax = 400 MW • C2 = 310 + 7,85 P2 + 0,00194 P2

• Tổ máy 3:

2 ($/h)

• PMin = 150 MW, PMax = 500 MW • C3 = 78 + 9,56 P3 + 0,00694 P3

• What combination of units 1, 2 and 3 will produce 550 MW

at minimum cost?

• How much should each unit in that combination generate?

3.1 GIỚI THIỆU

(cid:1) Ví dụ

3.1 GIỚI THIỆU

(cid:1) Nhận xét từ ví dụ:

(cid:1) Far too few units committed: Can’t meet the demand (cid:1) Not enough units committed: Some units operate above

optimum

(cid:1) Too many units committed: Some units below optimum (cid:1) Far too many units committed: Minimum generation

exceeds demand

(cid:1) No-load cost affects choice of optimal combination

3.1 GIỚI THIỆU

(cid:1) Ví dụ 3.2:

Load

1000

500 Time

0

12

24

6

18 3.1 GIỚI THIỆU

(cid:1) Ví dụ 3.2:

3.1 GIỚI THIỆU

(cid:1) Ví dụ 3.2:

Load

Unit 3

Unit 2

Unit 1

Time

3.1 GIỚI THIỆU

(cid:1) Có bao nhiêu cách kết hợp:

111

110

101

100

- 3 tổ máy: 8 - N tổ máy: 2N - 1 - N tổ máy và đồ thị phụ tải M bậc: (2N – 1)M

011

010

001

000

Bài toán UC trở nên rất phức tạp khi xét hệ thống có nhiều nhà máy, mỗi nhà máy có nhiều tổ máy!!!

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ công suất là một trong các biện pháp quan trọng để nâng cao độ tin cậy vận hành của HTĐ.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ công suất phía nguồn:

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ điều chỉnh (Regulation Reserve):

(cid:2) Được cung cấp nhanh bởi các tổ máy đang vận hành

thông qua điều chỉnh sơ cấp của bộ AGC.

(cid:2) Đáp ứng với sự biến thiên nhỏ của công suất phụ tải. (cid:2) Thời gian đáp ứng tính bằng giây cho đến phút.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ quay (Spinning Reserve):

(cid:2) Được cung cấp bởi các tổ máy đang vận hành. (cid:2) Đáp ứng với sự biến thiên lớn của công suất phụ tải, các

sự cố bất ngờ gây dao động công suất. (cid:2) Thời gian đáp ứng tính trong vài phút.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ bổ sung (Supplemental Reserve):

(cid:2) Cung cấp bởi các tổ máy đang vận hành hoặc các tổ máy đang nghỉ nhưng có khả năng khởi động nhanh (tuabin thủy điện, tuabin khí).

(cid:2) Đáp ứng sự mất cân bằng lớn trong HTĐ như sự cố tổ máy đang phát có công suất lớn, sự cố đường dây liên lạc mang tải nặng.

(cid:2) Thời gian đáp ứng từ vài chục phút đến giờ.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Các thành phần dự trữ

Source: PJM electricity market

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ quay: tổng công suất khả phát của các tổ máy đang vận hành – (tổng công suất phụ tải + tổn thất công suất trong mạng điện).

(cid:1) Dự trữ quay là bắt buộc để tránh hiện tượng tần số giảm quá thấp khi có sự cố 1 hay nhiều máy phát.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ quay phải được phân bố hợp lý giữ các tổ máy có tốc độ thay đổi công suất phát lớn và các tổ máy có tốc độ tăng giảm công suất nhỏ.

Khôi phục tần số và dòng công suất trên các đường dây liên kết một cách nhanh chóng.

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Dự trữ quay cũng phải phân bố hợp lý trên toàn hệ

thống.

Tránh vi phạm giới hạn truyền tải và cho phép các hệ thống điện khu vực làm việc ở chế độ tách đảo “island”.

3.2 DỰ TRỮ CÔNG SUẤT

Đánh giá dự trữ của từng khu vực khi sự cố tổ máy 4?

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Yêu cầu dự trữ công suất:

≥

max u i t P ( , ) Gi

P t ( ) D

P t ( ) R

∑

= 1

t P ( ): Reserve requirement at time R

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Phân loại dự trữ (cid:2)Spinning reserve

– Primary: Quick response for a short time – Secondary: Slower response for a longer time

(cid:2)Tertiary reserve

– Replace primary and secondary reserve to

protect against another outage

– Provided by units that can start quickly (e.g.

open cycle gas turbines)

– Also called scheduled or off-line reserve

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Phân loại dự trữ (cid:2) Positive reserve

– Increase output when generation < load

(cid:2) Negative reserve

– Decrease output when generation > load

(cid:2) Other sources of reserve: – Pumped hydro plants – Demand reduction (e.g. voluntary load shedding)

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Xác định dự trữ công suất: (cid:2)Protect the system against “credible

outages”

(cid:2)Deterministic criteria:

– Capacity of largest unit or interconnection – Percentage of peak load

(cid:2)Probabilistic criteria:

– Takes into account the number and size of the committed units as well as their outage rate

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Deterministic criteria:

Hệ thống

Tiêu chuẩn

Australia & New Zealand

t i

( max u P i

)

1 max 2

Spain

Giữa và

( D3 P

)

( D6 P

)

Manitoba Hydro

t max 80%max u P i i

(

)

∑ max 20% P i

i 1 =

France

UCTES rules, currently at least 500 MW

Yukon Electrical

max 10%P D

( t max max u P i i

)

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Probabilistic criteria: xác suất để tổng công suất khả phát của các tổ máy đang vận hành nhỏ hơn công suất phụ tải ở thời điểm bất kỳ.

p r i i

= ∑

pi – xác suất hệ thống ở trạng thái i ri – xác suất để hệ thống ở trạng thái i có tổng công suất khả phát nhỏ hơn công suất phụ tải

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Xác suất hệ thống ở trạng thái i:

q l

l X ∈

j Y ∈ i

 =   

  ∏ ∏ p      

   

(cid:1) Xi – số phần tử làm việc (cid:1) Yi – số phần tử nghỉ

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Xác suất của một phần tử:

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) λ – cường độ hỏng hóc (xác suất để một phần tử làm việc tốt đến thời điểm t và sẽ hỏng trong khoảng thời gian Δt tiếp theo)

(cid:1) μ – cường độ phục hồi (xác suất để phần tử đã hỏng đến thời điểm t và sẽ trở lại làm việc trong khoảng thời gian Δt tiếp theo)

(cid:1) Biết thời gian làm việc trung bình TLV và thời gian

sửa chữa trung bình τ, dễ dàng tìm được λ và μ

3.2 DỰ TRỮ CÔNG SUẤT

λ =

1 T

µ =

1 τ

LV + τ

µ λ + µ

LV τ + τ

λ λ + µ

LV p q 1 + =

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Ví dụ 3.3:

C 1

23,5P 1

2 .0,77.P 1

26,5P 2

2 .1,6.P 2

1 2 1 2

30P 3

2 .2,00.P 3

32P 4

2 .2,5.P 4

12 MW

≤

1 2 1 2 1 P ,P ,P ,P 2 4

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Ví dụ 3.3:

Đánh giá dự trữ theo tiêu chuẩn xác suất trong khoảng E? Biết: λ = 1/năm μ = 99/năm MTIL = 0,0005

Maximum Tolerable Insecurity Level (MTIL)

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Ví dụ 3.3:

- Vận hành chỉ tổ máy 1:

S = 0,01 > MTIL

- Vận hành 2 tổ máy 1 & 2:

S = 0,0001 (đạt)

3.2 DỰ TRỮ CÔNG SUẤT

(cid:1) Chi phí của dự trữ: • Reserve has a cost even when it is not called • More units scheduled than required

– Units not operated at their maximum efficiency – Extra start up costs

• Must build units capable of rapid response • Cost of reserve proportionally larger in small

systems

• Important driver for the creation of interconnections

between systems

3.3 CÁC RÀNG BUỘC

(cid:1) Ràng buộc tổ máy (cid:1) Ràng buộc hệ thống (cid:1) Chi phí khởi động

3.3.1 Ràng buộc tổ máy

(cid:1) Công suất phát tối đa (cid:1) Công suất phát tối thiểu (cid:1) Thời gian dừng máy tối thiểu (cid:1) Thời gian làm việc tối thiểu (cid:1) Tốc độ thay đổi công suất phát

3.3.1 Ràng buộc tổ máy

u(i,t) :

Status of unit i at period t

u(i,t) = 1 :

Unit i is on during period t

u(i,t) = 0 :

Unit i is off during period t

G i t P ( , ) :

Power produced by unit i during period t

3.3.1 Ràng buộc tổ máy

• Minimum up time

– Once a unit is running it may not be shut down

immediately:

up,min then u(i,t + 1) = 1

If u(i,t) = 1 and ti

up < ti • Minimum down time

– Once a unit is shut down, it may not be started

immediately

down,min then u(i,t +1) = 0

If u(i,t) = 0 and ti

down < ti

3.3.1 Ràng buộc tổ máy

• Maximum ramp rates

– To avoid damaging the turbine, the electrical output of a unit cannot change by more than a certain amount over a period of time:

,max

i t ,

(

)

Maximum ramp up rate constraint: ) + − 1 P G

( P i t , G

≤ ∆ up P i

Maximum ramp down rate constraint:

,max

i t

+ ≤ ∆ down

i t P ( , ) P ( , − G

P i

3.3.1 Ràng buộc tổ máy

(cid:1) Ràng buộc nhiên liệu (cid:1) Ràng buộc nhân công

3.3.2 Ràng buộc hệ thống

(cid:1) Cân bằng công suất trong hệ thống điện (cid:1) Dự trữ công suất trong hệ thống điện (cid:1) Phát thải ô nhiễm môi trường (cid:1) Ràng buộc của mạng điện

3.3.2 Ràng buộc hệ thống

(cid:1) Cân bằng công suất trong hệ thống điện (cid:1) Bỏ qua tổn thất, dạng đơn giản nhất:

u i t

i t ( , ).P ( , ) G

( ) P t D

∑

= 1

(cid:1) Phương pháp dòng điện một chiều:

−

(

)

) P u i t P i t , , i

( P i t , D

( B δ δ j i

)

∑

= 1

3.3.2 Ràng buộc hệ thống

(cid:1) Cân bằng công suất trong hệ thống điện

(cid:1) Phương pháp dòng điện xoay chiều:

−

)

(

( P i t , D

) P u i t P i t , , i n

ɺ U

cos

sin

δ + ij

B ij

ɺ ( U G j ij

)

∑

−

k ,

(

)

( Q u i t Q i t Q i t , G

= 1 ) n

ɺ U

sin

cos

δ − ij

B ij

ɺ ( U G ij j

)

∑

= 1

3.3.2 Ràng buộc hệ thống

(cid:1) Phát thải ô nhiễm môi trường • Constraints on pollutants such SO2, NOx

– Various forms:

• Limit on each plant at each hour • Limit on plant over a year • Limit on a group of plants over a year

• Constraints on hydro generation

– Protection of wildlife – Navigation, recreation

3.3.2 Ràng buộc hệ thống

(cid:1) Ràng buộc của mạng điện:

– Some units must run to provide voltage support – The output of some units may be limited because their output would exceed the transmission capacity of the network

Cheap generators May be “constrained off”

More expensive generator May be “constrained on”

3.3.2 Ràng buộc hệ thống

(cid:1) Ràng buộc của mạng điện:

≤

min P ij

B ij

P ij

max P ij

(cid:1) Phương pháp dòng điện một chiều: )

( − δ δ j

(cid:1) Phương pháp dòng điện xoay chiều:

0 ≤

≤

2 2 P Q + ij ij

max ij

3.3.3 Chi phí khởi động

(cid:1) Nhiệt độ và áp suất của tổ máy nhiệt điện phải tăng

từ từ nên cần chi phí để tổ máy “commit”.

(cid:1) Có 2 cách tiếp cận khi dừng tổ máy nhiệt điện:

(cid:1) Cooling (The boiler is cooled down and then heated back up to operating temperature in time for a scheduled turn on)

(cid:1) Banking (maintain boiler at operating temperature)

3.3.3 Chi phí khởi động

(cid:1) Sự phụ thuộc chi phí khởi động (cooling) vào thời

gian dừng máy:

−

OFF ti τi

)

SCi (t i

OFF ) =αi + βi (1 − e

αi + βi

αi

OFF ti

3.3.3 Chi phí khởi động

(cid:1) So sánh chi phí khởi động theo thời gian dừng máy:

3.3.3 Chi phí khởi động

(cid:1) Tổ máy diesel: chi phí khởi động thấp, chi phí sản

xuất cao.

(cid:1) Tổ máy nhiệt điện than: chi phí khởi động lớn, chi

phí sản xuất nhỏ.

(cid:1) Cần có sự cân bằng giữa chi phí khởi động và chi

phí sản xuất.

3.3.4 Nhận xét

(cid:1) Một vài ràng buộc liên kết các khoảng thời gian với

nhau.

(cid:1) Cực tiểu tổng chi phí (chi phí khởi động + chi phí sản xuất) phải được giải trên toàn bộ khoảng thời gian xét.

(cid:1) UC là bài toán tổng quát hơn bài toán ED. (cid:1) ED là bài toán con của UC.

3.3.4 Nhận xét

(cid:1) Một vài nhà máy có công suất phát không thể thay đổi vì lý do kỹ thuật hoặc thương mại (Inflexible Plants).

(cid:1) Công suất phát của các nhà máy “Inflexible” được

cho trước khi giải bài toán tối ưu.

(cid:1) Ví dụ: Nhà máy điện hạt nhân, thủy điện kênh dẫn,

năng lượng tái tạo (gió, mặt trời, …)

3.4 MÔ HÌNH BÀI TOÁN UC

(cid:1) Static UC:

3.4 MÔ HÌNH BÀI TOÁN UC

(cid:1) Dynamic UC:

3.4 MÔ HÌNH BÀI TOÁN UC

(cid:1) Dynamic UC:

3.4 MÔ HÌNH BÀI TOÁN UC

(cid:1) Kết hợp của biến nguyên và biến liên tục. (cid:1) Biến liên tục:

(cid:1) Có thể sử dụng gradients hoặc LP. (cid:1) Bất kỳ giá trị thuộc tập kết hợp khả thi đều OK.

(cid:1) Biến rời rạc:

(cid:1) Không có gradient. (cid:1) Chỉ có thể lấy một số hữu hạn các giá trị. (cid:1) Phải thử cách kết hợp của các biến rời rạc. (cid:1) Bài toán không lồi (Problem is not convex)

3.4 MÔ HÌNH BÀI TOÁN UC

(cid:1) Đặc điểm kỹ thuật giải tốt:

(cid:1) Lời giải gần với nghiệm tối ưu. (cid:1) Thời gian tính toán chấp nhận được. (cid:1) Có khả năng mô hình các ràng buộc.

(cid:1) Các phương pháp giải:

– Priority list / heuristic approach (Thứ tự ưu tiên) – Dynamic programming (Quy hoạch động) – Lagrangian relaxation (Nới lỏng Lagrange) – Mixed Integer Programming (Quy hoạch tuyến tính

nguyên thực hỗn hợp – MILP)

State of the art

3.5 PRIORITY – LIST METHOD

(cid:1) Đưa ra thứ tự khởi động và dừng các tổ máy. (cid:1) Chỉ xét được một vài ràng buộc. (cid:1) Tiếp cận điển hình là dựa trên chi phí sản xuất điện năng trung bình khi tổ máy phát công suất tối đa (the average full – load production cost – AFLC):

(cid:1) Thứ tự khởi động các tổ máy: AFLC1 ≤ AFLC2 ≤ … AFLCn

3.5 PRIORITY – LIST METHOD

(cid:1) Ví dụ 3.4:

3.5 PRIORITY – LIST METHOD

(cid:1) Ví dụ 3.4:

3.5 PRIORITY – LIST METHOD

(cid:1) Trong thị trường điện cạnh tranh, chi phí là thông tin cá nhân và phương pháp này sẽ phải dựa trên giá (prices).

(cid:1) Thứ tự khởi động tổ máy là tăng dần giá điện năng tối đa

tổ máy phát công suất

trung bình khi (average full load prices).

3.5 PRIORITY – LIST METHOD

(cid:1) Có thể sử dụng thuật toán sau:

(cid:1) Tại mỗi giờ, khi phụ tải giảm, xác định xem có thể ngừng tổ máy tiếp theo trên danh sách thứ tự ưu tiên. Kiểm tra ràng buộc dự trữ công suất. Nếu thỏa mãn thì chuyển sang bước tiếp theo.

(cid:1) Xác định số giờ H trước khi tổ máy được làm việc trở lại. Kiểm tra ràng buộc thời gian dừng máy tối thiểu. Nếu thỏa mãn thì chuyển sang bước tiếp theo.

3.5 PRIORITY – LIST METHOD

(cid:1) Tính toán 2 chi phí.

(cid:1) Chi phí sản xuất toàn hệ thống khi tổ máy làm việc trong

H giờ tiếp theo.

(cid:1) Chi phí sản xuất của hệ thống khi tổ máy dừng và khởi

động tổ lại (cooling hoặc banking).

(cid:1) So sánh 2 chi phí trên. Nếu chi phí thứ 2 nhỏ hơn

chi phí thứ nhất thì tổ máy đó sẽ nghỉ.

(cid:1) Lặp lại quá trình trên đối với tổ máy tiếp theo trên

thứ tự ưu tiên.

3.5 PRIORITY – LIST METHOD

(cid:1) Ưu điểm:

(cid:1) Tính toán nhanh (cid:1) Xét được ràng buộc thời gian làm việc tối thiểu và dừng

tối thiểu.

(cid:1) Đòi hỏi ít tính toán, vì vậy kích cỡ lớn của bài toán UC

không là vấn đề.

(cid:1) Nhược điểm:

(cid:1) Không tìm được lời giải tối ưu. (cid:1) Không có thông tin độ nhạy. (cid:1) Không xét được nhiều ràng buộc quan trọng.

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Ví dụ 3.5:

(cid:1) Dữ liệu của các tổ máy:

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Ví dụ 3.5:

Hourly Demand

Load

350 300 250 200 150 100 50 0

1

3

2 Hours

Không xét ràng buộc dự trữ công suất

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Các cách kết hợp khả thi:

150

300

200

3.6 DYNAMIC PROGRAMMING (DP)

A B C

1 1 1

1 1 0

1 0 1

Initial State

1 0 0

0 1 1

Chuyển trạng thái giữa các kết hợp khả thi.

3.6 DYNAMIC PROGRAMMING (DP)

A B C

1 1 1

1 1 0

1 0 1

Initial State

1 0 0

0 1 1

TD TU 3 3

Ràng buộc thời gian dừng máy tối thiểu của tổ máy A.

3.6 DYNAMIC PROGRAMMING (DP)

A B C

1 1 1

1 1 0

1 0 1

Initial State

1 0 0

0 1 1

TD TU 3 3

Ràng buộc thời gian làm việc tối thiểu của tổ máy B.

3.6 DYNAMIC PROGRAMMING (DP)

A B C

1 1 1

1 1 0

1 0 1

Initial State

1 0 0

0 1 1

Sự chuyển trạng thái khả thi.

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

1 1 0

1 0 1

1 0 0

Xét chi phí sản xuất

3.6 DYNAMIC PROGRAMMING (DP)

State

Load

Cost

150

PA 150

PC 0

PB 0

1500

300

250

3500

300

250

3100

300

240

3200

200

2000

200

190

2100

h c t a p s i D c i m o n o c E

200

150

2100

Unit

No-load cost

Marginal cost

Pmin 150

Pmax 250

100

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

4 $3200

1 1 0

3 $3100

7 $2100

1 0 1

6 $2100

2 $3500

1 0 0

1 $1500

5 $2000

Chi phí sản xuất từng trạng thái

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

4 $3200

1 1 0

$700

3 $3100

7 $2100

$600

1 0 1

6 $2100

2 $3500

$100

1 0 0

1 $1500

5 $2000

Start-up cost

Unit

1000

600

Xét chi phí khởi động

100

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

$5400 4 $3200

$7300

1 1 0

$700

$600

7 $2100 $7200

$600

1 0 1

$5200 3 $3100 $5100 2 $3500

6 $2100

$100

$1500

$7100

1 0 0

1 $1500

5 $2000

Xét chi phí tích lũy (accumulated costs)

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

$7300

1 1 0

$7200

1 0 1

$7100

1 0 0

Lowest total cost

Tổng chi phí (total costs)

3.6 DYNAMIC PROGRAMMING (DP)

1 1 1

1 1 0

1 0 1

$7100

1 0 0

Lời giải tối ưu

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Ví dụ 3.5 minh họa phương pháp quy hoạch động

giải bài toán UC.

(cid:1) Một vài ràng buộc đã bị bỏ qua nên đã không xét

được tính phức tạp của bài toán UC.

(cid:1) Phương pháp này không còn được sử dụng do DP chỉ phù hợp với các hệ thống nhỏ (dưới 20 tổ máy). Thời gian tính toán tăng theo hàm mũ với số tổ máy.

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) DP thích hợp khi giải bài toán tối ưu có các biến rời rạc, hàm chi phí có dạng phi tuyến và có các ràng buộc phức tạp.

(cid:1) Không cung cấp thông tin độ nhạy.

(cid:1) Nguyên lý cơ bản của DP: Một bộ phận của sách

lược tối ưu cũng là một sách lược tối ưu.

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Phương trình đệ quy:

− ⇒ +

t I ,

−

1, L

)

( C t I ,

)

(

)

( C t I , tc

( C t tc

 

 

min { } L

(cid:1) Ctc(t, I) – tổng chi phí nhỏ nhất từ trạng thái ban

đầu tới trạng thái I giờ t

(cid:1) C(t, I) – chi phí sản xuất ở trạng thái (t, I) (cid:1)

- chi phí chuyển từ trạng thái

(t-1, L) sang trạng thái (t, I)

(cid:1) {L} – tập các trạng thái khả thi ở thời điểm t-1

3.6 DYNAMIC PROGRAMMING (DP)

t=1

(cid:1) Lưu đồ thuật toán:

L − ⇒

t I ,

)

( C t I ,

)

(

)

( C t I , tc

Tính toán tất cả các trạng thái I ở thời gian t

 

 

min { } L

t= t+1

{L}=”N” - tập các trạng thái khả thi ở thời điểm t-1

− ⇒ +

t I ,

−

1, L

)

( C t I ,

)

(

)

( C t I , tc

( C t tc

Tính toán tất cả các trạng thái I ở thời gian t

 

 

min { } L

Lưu đường có chi phí nhỏ nhất

t = M, giờ cuối cùng

Lời giải tối ưu

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Kết hợp với phương pháp thứ tự ưu tiên để giảm kích cỡ của bài toán UC và xác định các cách kết hợp khả thi.

(cid:1) Ví dụ 5: Dữ liệu các tổ máy

- 6: tổ máy đã nghỉ trong 6 giờ 8: tổ máy đã làm việc trong 8 giờ

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Ví dụ 3.6: Đồ thị phụ tải

Thứ tự ưu tiên: tổ máy 3 – 2 – 1 – 4

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Ví dụ 3.6: Thứ tự kết hợp của các tổ máy (xếp theo

thứ tự công suất khả phát)

Trạng thái ban đầu: 12

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Bước 1: Áp dụng phương pháp thứ tự ưu tiên (không xét ràng buộc thời gian dừng máy tối thiểu và làm việc tối thiểu) (cid:1) Giờ thứ nhất: PD = 450 MW

Các trạng thái 12, 13, 14, 15 khả thi. Tuy nhiên, trạng thái 13 không thỏa mãn thứ tự ưu tiên.

(cid:1) Kết quả

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Bước 2: Giải bài toán UC sử dụng DP (không xét ràng buộc thời gian dừng máy tối thiểu và làm việc tối thiểu) (cid:1) 4 giờ đầu: các trạng thái khả thi là 12, 14, 15 (cid:1) 4 giờ sau: các trạng thái khả thi là 5, 12, 14, 15 (cid:1) Tổng số trạng thái khả thi là 5, 12, 14, 15

(cid:1) Giờ thứ nhất t = 1: {L} = {12}, {I} = {12, 14, 15} Ctc(1, 12) = C(1, 12) + CSU(0,12→ 1,12) + Ctc(0,12) = 9208 + 0 + 0 = 9208 Ctc(1, 14) = C(1, 14) + CSU(0,12→ 1,14) + Ctc(0,14) = 9493 + 350 + 0 =

9843

Ctc(1, 15) = C(1, 15) + CSU(0,12→ 1,15) + Ctc(0,15) = 9861 + 350 + 0 =

10211

3.6 DYNAMIC PROGRAMMING (DP)

(cid:1) Giờ thứ hai t = 2: {L} = {12, 14, 15}, {I} = {12, 14, 15} Ctc(2, 15) = min[C(2, 15) + CSU(1,12→ 2,15) + Ctc(1,12); C(2, 15) + CSU(1,14→ 2,15) + Ctc(1,14); C(2, 15) + CSU(1,15→ 2,15) + Ctc(1,15)] = 11301 + min[350 + 9208; 0 + 9843; 0 + 10211] = 11301 + 9843 = 20859

Thực hiện hoàn toàn tương tự: Ctc(2,12), Ctc(2,14)

(cid:1) Giờ thứ ba t = 3: {L} = {12, 14, 15}, {I} = {14, 15}

3.6 DYNAMIC PROGRAMMING (DP)

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Được áp dụng để giải các bài toán UC từ những

năm 1970s.

(cid:1) Phương pháp này sử dụng lý thuyết đối ngẫu

(duality theory) trong quy hoạch phi tuyến.

(cid:1) Được sử dụng trong rất nhiều phần mềm thương

mại để áp dụng cho các hệ thống lớn.

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Bài toán: (cid:1) Hàm mục tiêu:

C P i t u i t , ,

(

)

(

)

(

)

(

)

C P i t , G

∑∑

 

 

 

 

 

 i t u i t , , 

= 1

(cid:1) Các ràng buộc:

≤

)

) ( min u i t P , Gi

( P i t , G

) ( max u i t P , Gi

−

( i t (i, t).u ,

)

P t ( ) D

P G

∑

= 1

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Hàm Lagrange:

t λ

−

)

( L C P u it

Git

t P D

P u Git it

∑

= 1

  

  

(cid:1) Hàm mục tiêu, giới hạn công suất phát, ràng buộc tốc độ tăng giảm công suất phát độc lập giữa các tổ máy (Tổ máy này không ảnh hưởng đến chi phí của tổ máy khác).

(cid:1) Ràng buộc cân bằng công suất (coupling constraints) có liên kết giữa các tổ máy (tác động đến tổ máy này sẽ ảnh hưởng đến các tổ máy khác).

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Lagrange Relaxation method tạm thời bỏ qua ra ràng buộc móc nối (coupling constraints) và giải bài toán khi không xét ràng buộc này.

(cid:1) Thủ tục tối ưu đối ngẫu:

( ) λ

max t λ

t λ

( ) λ

q ( L P u Git it

)

min P u , Git it

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Quá trình giải gồm 2 bước:

1. Tìm giá trị λt để q(λ) tiến tới giá trị lớn hơn.

2. Cố định λt ở bước 1, tìm Pgit và uit để cực tiểu hàm

Lagrange L

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Khi λt cố định, hàm Lagrange được viết lại:

t λ

−

)

( C P i

Git

SU C it

t P D

P u Git it

∑∑

∑

 

 u .  it

= 1

  

  

−

t λ

)

( C P i

Git

SU C it

t P D

P u Git it

∑∑

∑

 

 u .  it

= 1

−

)

( C P i

Git

SU C it

P uλ Git it

∑∑

∑

 

 u .  it

= 1

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Như vậy, có thể xét riêng từng tổ máy độc lập

−

)

( C P i

Git

SU C it

u . it

P uλ Git it

∑

{

}

 

 

= 1

(cid:1) Cực tiểu hàm Lagrange tìm được bằng cách giải cực

min

−

t λ

( ) λ

)

( C P i

SU C it

u . it

Git

P u Git it

∑ ∑ min

tiểu hàm Lagrange của từng tổ máy độc lập. {

}

 

 

= 1

min

max

(cid:1) Ràng buộc:

≤

u P it Gi

P Git

u P it Gi

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Bài toán này có thể dễ dàng giải bằng phương pháp

quy hoạch động với 1 biến:

(cid:1) Si – chi phí khởi động

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Khi ui = 1, ta có:

−

t Pλ

)

( C P i

Git

min  

 

(cid:1) Lấy đạo hàm bậc nhất, ta có lời giải tối ưu:

t λ

opt P Git

(

) =

dC i dP

Git

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Xét ràng buộc giới hạn công suất phát:

1) P

−

t λ

)

opt Git

min P Gi

( C P i

Git

P Git

min P Gi

( min C P i Gi

)

: min  

 

≤

min 2) P Gi

opt P Git

min

−

t λ

max P Gi )

( C P i

Git

P Git

opt Git

( C P i

)

 

 

3) P

−

t λ

)

opt Git

max P Gi

( C P i

Git

P Git

max P Gi

opt P Git ( max C P i Gi

)

: min  

 

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Tại mỗi bước thời gian:

−

Cho u

−

t λ

Git

P Git

−

Cho u

−

≥

t λ

( (

) )

Git

P Git

 khi C P   khi C P 

   

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Hiệu chỉnh λ

3.7 LAGRANGE RELAXATION METHOD

Thuật toán giải

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

(cid:1) Không xét chi phí khởi động, thời gian làm việc tối

thiểu và nghỉ tối thiểu.

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

(cid:1) Ví dụ 3.7

3.7 LAGRANGE RELAXATION METHOD

Ưu điểm: (cid:1) Biểu diễn chi tiết các đặc tính phức tạp của các tổ

máy.

(cid:1) Linh hoạt cao (modun hóa và mở rộng). (cid:1) Thuận lợi khi đánh giá chi phí biên

3.7 LAGRANGE RELAXATION METHOD

Nhược điểm: (cid:1) Chỉ đưa ra lời giải gần tối ưu (suboptimal). (cid:1) Tính toán nhiều. (cid:1) Trong hoạt động thị trường điện, kết quả của bài toán UC có được bằng phương pháp LR có thể dẫn đến vấn đề không công bằng bởi vì các tổ máy thuộc quyền sở hữu của các thành phần khác nhau. (cid:1) Lời giải gần tối ưu và cũng có nhiều lời giải gần tối ưu, vấn đề phân biệt đối xử có thể tăng vì sự sở hữu thuộc các thành phần khác nhau.

3.7 LAGRANGE RELAXATION METHOD

Nhược điểm: (cid:1) Hai lời giải có giá trị hàm mục tiêu xấp xỉ nhau nhưng lại có sự khác nhau đáng kể về phương thức vận hành của các nguồn riêng lẻ, điều này dẫn đến sự thay đổi đáng kể chi phí và lợi nhuận.

(cid:1) LR là một trong các phương pháp tối ưu quan trọng nhất. Theo LR, bài toán tối ưu ban đầu sẽ được tách thành dãy các bài toán con độc lập đơn giản hơn.

3.7 LAGRANGE RELAXATION METHOD

Nhược điểm: (cid:1) Hiện tại, LR là phương pháp quan trọng nhất nhưng sự công bằng và tính hiệu quả đã bị cản trở trong môi trường cạnh tranh.

(cid:1) Đồng thời, phương pháp MIP (Mixed Integer Programming) đang được phát triển mạnh để giải bài toán UC.

(cid:1) MIP có nhiều khó khăn, đòi hỏi phải áp dụng một cách hiệu quả phương pháp tìm kiếm (heuristic) cho các bài toán kích cỡ lớn.

3.7 LAGRANGE RELAXATION METHOD

Nhược điểm: (cid:1) Nếu MIP không thể tìm lời giải chính xác thì vấn đề

công bằng vẫn tồn tại.

3.8 MIXED INTEGER PROGRAMMING (MIP)

(cid:1) MIP đạt được lời giải tối ưu tốt hơn phương pháp

LR.

(cid:1) Nhiều thị trường điện ở Mỹ sử dụng MIP để giải bài

toán UC.

(cid:1) MILP (Mixed Integer Linear Programming) sẽ

được trình bày.

3.8 – MIP - LP formulation of ED

C1 = a1 + c1x1

L 2 Minimize CT = a1 + a2 + a3 +

MAX

MIN

c1 x1 + c2 x2 + c3 x3

MAX

C2 = a2 + c2x2

MAX

MIN

Subject to: x1 + x2 + x3 = L MIN ≤ x1 ≤ P1 P1 MIN ≤ x2 ≤ P2 P2 MIN ≤ x3 ≤ P3 P3

C3 = a3 + c3x3

• Objective function is linear • All constraints are linear • All variables are real •

Problem can be solved using standard linear programming

MAX

MIN

3.8 MIP - Can we use LP for UC?

MAX

x1 = 0 or P1

MIN ≤ x1 ≤ P2

MAX

MIN

x2 = 0 or P2

MIN ≤ x2 ≤ P2

MAX

MIN

MIN ≤ x3 ≤ P3 x3 = 0 or P3 The variables no longer have a contiguous domain (Non-convex set) Standard linear programming is no longer applicable

MAX

MIN

3.8 MIXED INTEGER PROGRAMMING

(cid:3) Some decision variables are integers – Special case: binary variables {0,1}

(cid:3) Other variables are real (cid:3) Objective function and constraints are linear

3.8 MIP - Example

Except for the fact that the variables are integer, this looks very much like a linear programming problem.

3.8 MIP - Example

4x1 + 2x2 = 15

x1 + 2x2 = 8

x1 + x2 = 5

3.8 MIP - LP relaxation

Let us relax the constraint that the variables must be integer.

4x1 + 2x2 = 15

The problem is then a regular LP

Solution of the relaxed LP x1 = 2.5; x2 = 2.5; Objective = 12.5

x1 + 2x2 = 8

x1 + x2 = 5

4 Objective: 3x1 + 2x2

3.8 MIP - LP relaxation

4x1 + 2x2 = 15

The solution of the relaxed problem is always better than the solution of original problem! (Lower objective for minimization problem, higher for maximization)

Solution of the relaxed LP x1 = 2.5; x2 = 2.5; Objective = 12.5

x1 + 2x2 = 8

x1 + x2 = 5

3.8 MIP- Solution of the integer problem

4x1 + 2x2 = 15

Solution of the relaxed LP x1 = 2.5; x2 = 2.5; Objective = 12.5

x1 + 2x2 = 8

x1 + x2 = 5

3.8 MIP - Solution of the integer problem

4x1 + 2x2 = 15

Solution of the original problem x1 = 2; x2 = 3; Objective = 12.0

Solution of the relaxed LP x1 = 2.5; x2 = 2.5; Objective = 12.5

x1 + 2x2 = 8

x1 + x2 = 5

3.8 MIP - Naïve rounding off

LP solution

IP solution

The optimal integer solution can be far away from the LP solution “Far away” can be difficult to find when there are many dimensions

3.8 MIP - Finding the integer solution

(cid:3) Large number of integer variables (cid:3) Vast number of possible integer solutions (cid:3) Need a systematic procedure to search this solution

space

(cid:3) Fix the variables to the nearest integer one at a time (cid:3) “Branch and Bound” algorithm

3.8 MIP - Another example

Relaxed LP solution: (1.75, 0.75)

3.8 MIP - Branch on x1

Problem 0

x1 ≥ 0; x2 ≥ 0 x1 ≤ 1

x1 ≥ 0 ; x2 ≥ 0 x1 ≥ 2

Problem 1

Problem 2

3.8 MIP - Branch on x1

Problem 2

Problem 1

Solution of Problem 2

Solution of Problem 1

3.8 MIP - Search Tree: first layer

Solution of Problem 1: • x1 integer • x2 real • Not a feasible solution yet • Can still branch on x2

Solution of Problem 2: • x1 & x2 integer • Feasible solution of the original problem • Bound on the optimum • Best solution so far

3.8 MIP - Branch on x2

Problem 1

x1 ≤ 1; x2 ≥ 0

x1 ≥ 0; x2 ≥ 0 x1 ≤ 1; x2 ≤ 1

Problem 3

x1 ≥ 0; x2 ≥ 0 x1 ≤ 1; x2 ≥ 2 Problem 4

3.8 MIP - Search Tree: second layer

No integer solution yet

No solution

3.8 MIP- Branch and Bound: what next?

Optimal solution

Solution of relaxed problem 4 is bounded by solution of problem 2. No point in going further

Can’t go any further in this No solution direction

3.8 MIP - Comments on Branch and Bound

(cid:3) Search tree gets very big if there are more than a few

integer or binary variables

(cid:3) Even with the bounds provided by the relaxed solutions, exploring the tree usually takes a ridiculous amount of time

(cid:3) Clever mathematicians have developed techniques to

identify “cuts” (cid:3) Constraints based on the structure of the problem that

eliminate part of the search tree

(cid:3) “Branch and Cut” algorithm

3.8 MIP - Duality Gap

(cid:3) Finding the optimal solution for a large problem can take too much time even with branch and cut (cid:3) Best solution of relaxed problem provides a bound

on the solution

(cid:3) Duality gap: Difference between best solutions of

relaxed problem and actual problem

(cid:3) Stop searching the tree if duality gap is sufficiently

small