quy hoạch phát triển hệ thống điện, chương 6

Chia sẻ: Nguyen Van Dau | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

269
lượt xem 106
download

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

một nhà máy điện có thể dùng 4 loại than để sản xuất điện. Biết - lượng điện năng yêu cầu hàng năm của nhà máy :A[MWh] - suất tiêu hao than của loại than thứ i là qi - Giá thành sản xuất điện năng của loại than i là ci [đ/MWh] (i=1,2,3,4) - Lượng than loại i cung cấp hàng năm để sản xuất điện không được vượt quá Qi - Tổng lượng than của cả 4 loại cung cấp hàng năm để sản xuất điện không được vượt quá Q∑ Cần xác định lượng điện năng được...

Chủ đề:

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

Lưu

Nội dung Text: quy hoạch phát triển hệ thống điện, chương 6

Chương 6: Bài toán dạng chính tắc, bài toán dạng mở rộng,Hãy trình bày phương pháp quy hoạch số nguyên I- Quy hoạch tuyến tính: 1. Đặt bài toán: Một nhà máy điện có thể dùng 4 loại than để sản xuất điện. Biết - lượng điện năng yêu cầu hàng năm của nhà máy :A[MWh] - suất tiêu hao than của loại than thứ i là qi - Giá thành sản xuất điện năng của loại than i là ci [đ/MWh] (i=1,2,3,4) - Lượng than loại i cung cấp hàng năm để sản xuất điện không được vượt quá Qi - Tổng lượng than của cả 4 loại cung cấp hàng năm để sản xuất điện không được vượt quá Q∑ Cần xác định lượng điện năng được sản xuất hàng năm từ từng loại than để đạt cực tiểu về chi phí sản xuất điện năng. 2. Lời giải: Nếu gọi lượng điện năng được sản xuất hàng năm từ loại than thứ i là xi [MWh] (i=1,2,3,4) .. bài toán có thể được trình bày như sau: - Xác định X= {x1, x2, x3, x4 } sao cho: f(X) = c1x1 + c2x2 + c3x3 + c4x4  min - Với các ràng buộc:
x1 + x2 + x3 + x4 = A q1x1 + q2x2 + q3x3 + q4x4  Q q1x1  Q1 q 2x 2  Q 2 q3x3  Q3 q4x4  Q4 xi  0 (i=1,2,3,4) 3. Các dạng bài toán quy hoạch tuyến tính: A- Dạng tổng quát j= 1,..n Tìm X={xi } thỏa mãn đồng thời các điều kiện: n 1) f(X)   c j x j  min(max) j 1 n 2) g i ( X )   aij x j (; ; )bi (i  1, m) j 1 Trong đó: - f(X) là hàm mục tiêu - xj là các ẩn - cj , aij , bi là những hằng số tự do B- Dạng chính tắc: Tìm X= {xj }, j=1,..,n thỏa mãn đồng thời các điều kiện sau n 1) f(X) =  c j x j  min(max) j1 n 2) gi(X) =  a ij x j  bi (i  1, m) j1 3) xj ≥ 0 ; bi ≥ 0 trong đó cj , aij , bi là các hằng số tự do
Người ta có thể đưa dạng tổng quát về dạng chính tắc nếu gặp các trường hợp sau: n 1-  a x  b j 1 ij j Thêm vào vế trái phương trình một lượng ẩn i xn+i > 0, ta có: n n  a ij x j  b i   a ij x j  (x n  i )  b i j 1 j 1 n 2-  a x  b j1 ij , bớt vào vế trái của phương trình một lượng j i ẩn xn+i > 0, ta có: n n  a ij x j  b i   a ij x j  (x n i )  b i j 1 j 1 3- Trường hợp xj ≤ 0 th ì đ ặt tj= - xj ≥ 0 4- Trường hợp không biết dấu của ẩn xj thì đặt xj = xj1 - xj2 trong đ ó xj1  0; xj2  0 Bài toán dạng tổng quát sẽ trở thành bài toán dạng chính t ắc C- Dạng chuẩn tắc: là bài toán có dạng sau: T nìm X= {xj }, j= 1,...,n thỏa mãn đồng thời các điều  jx j  kiệncsau: min(max) j1 1- F(X)= n m x i   a i ,m h x m  h  b i ; (i  1, m) 2- Gi(X)= h 1 3- xj≥0; bi ≥0 Ma trận hệ số của hệ phư ng trình ràng buộc có dạng sau: 1 0 0 ... 0 a1,m+1 a1,m+2 ... a1,n
0 1 0 ... 0 a2,m+1 a2,m+2 ... a2,n 0 0 1 ... 0 a3,m+1 a3,m+2 ... a3,n ........................... 0 0 0 ... 1 am,m+1 am,m+2 ... am,n Như vậy có thể suy ra cách nhận biết dạng chuẩn tắc là ma trận hệ số của hệ phương trình ràng buộc kiểu m x n phải có chứa ma trận đơn vị c ấp m. Ví dụ: xét bài toán sau có phải dạng chuẩn không? Cho f(X) = 2x1 + 5x2 + 4x3 + x4 - 5x5  min Với các điều kiện ràng buộc như sau: 1) x1 + 2x2 + 4x3 - 3x5 = 152 2) 4x2 + 2x3 + x4 + 3x5 = 60 3) 3x2+ 4x5 + x6 = 36 Với xj  0 (j=1...6) Ma trận hệ số của hệ phương trình trên như sau: 1 2 4 0 3 0 0 4 2 1 3 0   0  3 0 0 4 1  Cột 1, 4, 5 tạo nên ma trận đơn vị cấp 3 nên bài toán ở dạng chuẩn tắc. Các ẩn tạo nên ma trận cấp 3 l à x1, x4, x6, và ta gọi là các ẩn cơ bản. nếu có một phương án sao cho các ẩn không cơ bản đều bằng 0 tức là nếu g ọi xi=bi (i=1,2..,m) làm ẩn cơ bản v à xi =0 (i=m+1,..,n) là các ẩn không cơ bản thì ta sẽ có một phương án cơ b ản như sau: Xcb = {b1, b2, b3, ..., bm, 0, 0, ...,0} Qui hoạch số nguyên
Nội dung chủ yếu của thuật toán Gamory để giải bài toán quy hoạch tuyến tính sao cho giá trị giá trị lời giải là tối ưu là những số nguyên. Đây cũng là nội dung chủ yếu của QH số nguyên: Gồm những bước tổng quát sau: Bước 1: Xác định lời giải tối ưu của bài tóan chưa quan tâm đến điều kiện số nguyên của lời giải, nếu 1 cách chứa dạt thì chuyển sang bước sau. Bước 2: Xây dựng thêm ràng buộc phụ thuộc nhằm mục đích hạn chế tập giá trị cho phép của lời giải, tuy nhiên không làm mất những giá trị lời giải số nguyên. Bước 3: Giải bài toán đã có thêm ràng buộc phụ đó, là kiểm tra điều kiện số nguyên của lời giải để kết thúc quá trình, hoặc phải lặp lại bước 2. Ta tìm hiểu nội dung của bước 2 và 3 của thuật toán Gamory: 1. Thành lập phương trình ràng buộc phụ: - Giả thiết bài toán QHTT đã được giải bằng thuật toán đơn hình, ở bước cuối cùng đã xác định được giá trị tối ưu của m ẩn cơ bản: x1, x2, …xm nhưng chưa là số nguyên. Khi đó hệ phương trình ràng buộc có dạng sau: a11 x1  a12 x2  ...  a1m xm  ...  a1k xk  ...  a1n xn  b1  a21 x1  a22 x2  ...  a2 m xm  ...  a2 k xk  ...  a2 n xn  b2    ..............................................................................  am1 x1  am 2 x2  ...  amm xm  ...  amk xk  ...  amn xn  bm   những hệ số của x1, x2, ... xm ở hệ trên tạo thành ma trận đơn vị cấp m. Điều kiện số nguyên của lời giải chưa thoả mãn, thể hiện ở chỗ các giá trị b1 ... bm chưa là những số nguyên. Phương trình ràng buộc phụ theo qui tắc sau đây: a. Phân tích: b1  n1  r1  b2  n2  r2    ...  bm  nm  rm   Trong đó ni là phần nguyên (0,1,2 ...) của bi : i = 1,2,... , m nhưng phải đảm bảo: ni  bi; i = 1, 2, ... , m .
ri là phần lẻ của bi ; i = 1, 2, ... , m, nghĩa là: 0  ri < 1 b. Sau khi xác định mọi giá trị ni và ri , i = 1, 2, ... m chọn phương trình ràng buộc ứng với ri cực đại để tạo ràng buộc phụ. c. Phân tích các hệ số ap1, ap2,, ... , apm , ... , apn thành a p1  n p1  rp1  a p 2  n p 2  rp 2  ... a  n  r  pn pn pn Trong đó npj ; j = 1, 2, .... , n là phần nguyên (âm, số 0 và dương) của apj và thoả mãn: npj  apj rpj ; j =1, 2, ... , n là phần lẻ của apj , nghĩa là: 0  rpj < 1 d. Thành lập phương trình ràng buộc phụ với ẩn s1 thêm vào trong dạng : - rp1 x1 - rp2 x2 - ... - rpn xn + s1 = - rp Như vậy bài toán qui hoạch tuyến tính giải theo thuật toán đơn hình ở bước này có (m + 1) ẩn cơ bản là x1 , x2, ... , xm và s1. Bây giờ cần chuyển sang bước tiếp theo, trong đó ẩn cần loại ra chính là s1 và chỉ cần xác định ẩn sẽ đưa vào trong bước mới. 2. Giải bài toán khi có ràng buộc phụ. a. Ghi các giá trị âm của các hệ số -rpj ở hàng ứng với hàng s1 và ứng với j  0. j b. Xác định các tỷ số: ; j  1,2,..., n rpj j c. Lấy cực tiểu của giá trị tuyệt đối: j  1,2,..., n rpj j d. Cột nào ứng với min: j  1,2,..., n thì ẩn đó sẽ được đưa vào rpj hệ ẩn cơ bản ở bước tiếp theo e. Theo thuật toán đơn hình. Giải tiếp cho đến khi mọi lời giải đều là số nguyên. Ví dụ: Xác định  x1, x2 là những giá trị nguyên, không âm, sao cho
f(x) = -x1 - 2x2  min và: - 3x1 + 4x2  6 4x1 + 3x2  12