Chương 5: Phương pháp qui hoạch
xấp xỉ giải qui hoạch phi tuyến
Bài toán qui hoạch tổng quát thường là bài toán qui hoạch phi
tuyến. Chỉ cần một trong các hàm { f(X) → min (max) } hoặc {
g
i
(X) (≤,=,≥) b
i
(i = 1,2,…,m) } là các hàm phi tuyến thì bài toán
qui ho
ạch tổng quát sẽ là bài toán qui hoạch phi tuyến. Để giải bài
toán qui ho
ạch phi tuyến người ta thường áp dụng một trong các
phương pháp là: tuyến tính hóa, đưa về b
ài toán qui hoạch phi
tuyến không ràng buộc, giải trực tiếp, qui hoạch động v.v…
Phương pháp tuyến tính hoá ( qui hoạch xấp xỉ )
Xác định tập giá trị các biến: X = {x
1
, x
2
,… x
n
}
Sao cho hàm
f(x
j
) → max (min)
j = 1,2,…,n
Đồng thời thỏa mãn các điều kiện:
h

( ) ( ) '( )( ) min
( ) ( ) ' ( )( ) 0
( ) ( ) ' ( )( ) 0
k k k
i
i
k k k
i i xi i
i
k k k
i i xi i
i
f X f X f X x x
h X h X h X x x
g X g X g X x x

   


   


   





(1)
trong đó x

ấy các đạo hàm f’(X), h
i
’(X), g
i
’(X) và tính giá trị của
chúng theo X
(0)
:
f’(X
(0)
), h
i
’(X
(0)
), g
i
’(X
(0)
).
+ L
ập bài toán qui hoạch tuyến tính (1).
Bước 2:
+ Giải bài toán qui hoạch tuyến tính (1) được X
(1)
.
+ Ch
ọn vectơ δ tùy ý
+ so sánh gi
ữa các thành phần thứ i của hai vectơ (X
(0)

= x
i
(0)
- δ
(1)
.
Trong đó δ
(1)
là độ dài bước lặp thứ 1 (0 < δ
(1)
< 1)
Ở những bước lặp khác ta có: δ
(k+1)
= μ δ
(k)
(0 < μ < 1)
Điều kiện tối ưu là khi nào δ ≤ ε th
ì coi như bài toán hội tụ theo
tiêu chuẩn đã đề ra.
(lý thuyết thế này là đủ nhưng có thể tham khảo thêm ví dụ trang
112 sách Quy Hoạch Phát Triển HTĐ của thầy Tráng)
Sơ đồ khối:
Ưu điểm:
- Thuật toán đơn giản, giải đơn giản (vì có chương trình mẫu)
- Nói chung là hội tụ
Nhược điểm:
- Tốc độ tính toán chậm, không dùng cho hệ thống điện lớn
Vào f(X), h(X), g(X)
Chọn X
(0)

i
(k+1)
> x
i
(k)
i = 1,2,…n
x
i
(k+1)
= x
i
(k)
+ δ
(
k+
1)
x
i
(k+1)
= x
i
(k)
-
δ
(
k+
1)
δ ≤ ε
In gtrị của X; STOP
δ = μδ

ngẫu) sao cho giữa các bài toán này có liên quan chặt chẽ (VD:từ
nghiệm của bài toán này có thể suy ra nghiệm của bài toán kia). Cụ
thể:
Xác định
1 2 n
X {x ,x , ,x }

sao cho:
m
1 2 n 1 1 m 1 2 n 1 i 1 2 n
i 1
L(x ,x , ,x ; , , , ) f(x ,x , ,x ) .h (x ,x ,
.,x ) min

      

Trong đó: L – hàm Lagrange.

- nhân tử Lagrange.
Lấy đạo hàm riêng của L theo xj và
i

rồi cho bằng 0 ta được hệ
phươn
g trình Lagrange:




m

i 1,2, ,m

 xác định hệ (1)
Nếu ở điểm
* * * *
1 2 n
X {x ,x , ,x }

hàm
* * *
1 2 n
f{x ,x , ,x }
đạt cực trị thì tồn tại
vectơ
* * * *
1 2 m
{ , , , }
    
sao cho điểm
* * * * * *
1 2 n 1 2 m
{x ,x , ,x ; , , , }
  
là lời
giải của hệ trên. Hệ có (n+m) phương trình, giải ra được n ẩn xj và
m
ẩn
i

.

g (X) 0

thì nhân
i
g (X)
với ( -1)
để có ràng buộc
i
g (X) 0

Hàm Lagrange có dạng:
 
1
1
m m
1 2 n i i 1 2 n i i 1 2 n
i 1 i m 1
L X, f(x ,x , ,x ) .h (x ,x , ,x ) .g (x ,x , ,x
) min
  
      
 
Vì
i
g (X)
không đồng nhất bằng không nên không thể lấy đạo
hàm hàm


L X,




x
L
Định lý: Vectơ
*
X
chỉ là lời giải tối ưu của bài toán (2) khi tồn tại
véctơ
*

sao cho:
Giá tr
ị của điểm






* * * *
L X , L X , L X ,
    



* *
L X ,
