Phương pháp nhánh và cận giải bài toán quy hoạch nguyên
Phân nhánh
Việc phân nhánh được thực hiện bằng cách chia tập M thành các tập con
Tính cận
Xét hàm số γ(A) xác định trên 2 M \∅, với γ : 2 M \∅ → R thoả mãn
Hàm số γ(A) trên tập A ⊂ M gọi là cận dưới của A.
Từ đó ta có γ(M i ) ≥ γ(M),∀i = 1, , k Đồng thời f(x ∗ ) = min{f(x) : x ∈ M} ≥ minγ(Mi) =γ(Ms).
Dó đó nếu f(x ∗ ) = γ(M s ) thì x ∗ là phương án tối ưu cần tìm.
Lựa chọn và loại bỏ
+ Lựa chọn: Giả sử cho M k
Khi đó γ(M s ) = minγ(M i ), i= 1, , k, tức là γ(M s ) ≤γ(M i ),∀i = 1, , k, nên γ(Ms) ≤ min{f(x) : x ∈ M}.
Ta hy vọng M s chứa phương án tối ưu Vì vậy có thể chọn M s để phân nhánh.
Loại bỏ là quá trình nhằm thu gọn bài toán và tiết kiệm bộ nhớ Tiêu chí để thực hiện việc loại bỏ là khi tại bước k, nếu phương án x thỏa mãn điều kiện f(x) ≤ f(x) với mọi phương án đã biết, thì x được coi là phương án kỷ lục và f(x) là giá trị kỷ lục.
Nếu có M j mà γ(M j ) ≥ f(x) thì M j bị loại bỏ Chú ý rằng nếu M j = ∅ thì M j cũng bị loại bỏ.
Một số khái niệm cơ bản của lý thuyết xác suất
Các khái niệm
1.2.1.1 σ-đại số Giả sử Ω là một tập tuỳ ý khác rỗng Ký hiệu P(Ω) là tập hợp gồm tất cả các tập con của Ω.
Lớp A ⊂ P(Ω) được gọi là một đại số nếu:
A3) A, B ∈ A ⇒ A∪B ∈ A (hoặc A∩B ∈ A) Lớp F ⊂ P(Ω) được gọi là σ-đại số nếu nó là đại số và ngoài ra có
A4) Nếu A n ∈ F, ∀n= 1,2, thì S∞ n=1A n ∈ F (hoặc là T∞ n=1An ∈ F).
1.2.1.2 Không gian đo.Cặp(Ω,F)được gọi làmột không gian đo, trong đó Ω 6= ∅ bất kỳ, F là một σ-đại số các tập con của Ω Toàn bộ Ω được gọi là biến cố chắc chắn, tập ∅ gọi là biến cố không, A gọi là biến cố đối của biến cố A Nếu A∩B = ∅, thì ta nói A và B là các biến cố xung khắc. 1.2.1.3 Độ đo xác suất Hàm tập P xác định trên đại số A được gọi là độ đo xác suất σ-cộng tính nếu:
Không gian xác suất (Ω,F,P) được coi là không gian xác suất đầy đủ khi mọi tập con của biến cố có xác suất không đều đều là biến cố Từ bây giờ, chúng ta sẽ luôn hiểu rằng khi nhắc đến không gian xác suất (Ω,F,P), đó là không gian xác suất đầy đủ.
Trong định nghĩa trên, điều kiện (P2) xác định rằng biến cố chắc chắn có xác suất bằng 1 Tuy nhiên, có những biến cố khác cũng có xác suất bằng 1 nhưng không nhất thiết là biến cố chắc chắn Những biến cố này được gọi là biến cố hầu chắc chắn.
1.2.1.4 Biến ngẫu nhiên Giả sử (Ω,F) là một không gian đo, R [−∞,+∞] Hàm thực
X = X(ω) xác định trên Ω lấy giá trị trên R gọi là hàm F-đo được hoặc biến ngẫu nhiên suy rộng nếu
{ω : X(ω) ∈ B} = X −1 (B) ∈ F với mỗi B ∈ B(R) (với B(R) là σ - đại số các tập Borel của R).
X : Ω −→ R = (−∞; +∞) thì X được gọi là biến ngẫu nhiên.
1.2.1.5 Hàm Borel Hàm ϕ : (R n ,B(R n )) −→ (R,B(R)) được gọi là hàm Borel, nếu nó là B(R n )-đo được, nghĩa là ϕ −1 (B) ∈ B(R n ), với mỗi B ∈ B(R).
1.2.1.6 Hàm phân phối của biến ngẫu nhiên Giả sử (Ω,F,P) là một không gian xác suất, X : Ω → R là biến nhẫu nhiên Khi đó, hàm số
F X (x) =P(X < x) =P(ω : X(ω) < x) được gọi là hàm phân phối của X. Nhận xét F X (x) = P[X −1 (−∞, x)] = P X [(−∞, x)].
1.2.1.7 Kỳ vọng của biến ngẫu nhiên Định nghĩa Giả sử X : (Ω,F,P) → (R,B(R)) là biến ngẫu nhiên Khi đó tích phân Lebesgue của X theo độ đo P (nếu tồn tại) được gọi là kỳ vọng của X và ký hiệu là EX.
Nếu tồn tại E | X | p < ∞ (p > 0), thì ta nói X khả tích bậc p Đặc biệt, nếu E | X |< ∞, thì X được gọi là biến ngẫu nhiên khả tích.
Lược đồ xây dựng kỳ vọng Lược đồ xây dựng kỳ vọng chính là lược đồ xây dựng tích phân Lebesgue.
Nếu X là biến ngẫu nhiên đơn giản X = P n i=1 a i I A i thì
Nếu X là biến ngẫu nhiên không âm thì X là giới hạn của một dãy tăng các biến ngẫu nhiên đơn giản (Xn, n ≥1)
EX := lim n→∞EXn. Nếu X là biến ngẫu nhiên bất kỳ thì X = X + −X − ; với
Khi đó EX := EX + −EX − (nếu có nghĩa).
Tính chất của biến ngẫu nhiên
Khi đó các mệnh đề sau là tương đương. a) X là biến ngẫu nhiên. b) {ω :X(ω) < x} ∈ F với mỗi x ∈ R. c) {ω :X(ω) ≤ x} ∈ F với mỗi x ∈ R. d) {ω : a ≤X(ω) < b} ∈ F với a < b bất kỳ.
2) Giả sử X 1 , X 2 , , X n là các biến ngẫu nhiên cùng xác định trên (Ω,F) và ϕ(t1, , tn) là hàm Borel giá trị thực Khi đó
Y = ϕ(X 1 , X 2 , , X n ) cũng là biến ngẫu nhiên.
3) Giả sử X, Y là các biến ngẫu nhiên Khi đó
X + = max(X,0), X − = max(−X,0),|X| = X + +X − cũng là các biến ngẫu nhiên Đặc biệt, nếu Y không triệt tiêu thì X/Y là biến ngẫu nhiên.
4) Giả sử (X n , n ≥ 1) là dãy biến ngẫu nhiên và sup n
X n ,inf n X n hữu hạn trên Ω Khi đó sup n
X n ,lim inf n X n là các biến ngẫu nhiên Đặc biệt nếu tồn tại n→∞lim X n = X thì X cũng là biến ngẫu nhiên.
Tính chất của kỳ vọng
3) Nếu tồn tại EX thì với mọi C ∈ R, ta có E(CX) = CEX.
4) Nếu tồn tại EX và EY thì E(X ±Y) = EX ±EY.
P ix i p i nếu X rời rạc nhận các giá trị x 1 , x 2 , , với P(X = x i ) = p i
−∞ xp(x)dx nếu Xliên tục có hàm mật độ p(x).
Tổng quát: Nếu f : R → R là hàm đo được và Y = f(X) thì
P if(x i )p i nếu X rời rạc nhận các giá trị x 1 , x 2 , với P(X = x i ) =p i
−∞ f(x)p(x)dx nếu Xliên tục có hàm mật độ p(x).
6) (Định lý P Levi về hội tụ đơn điệu) Nếu X n ↑X (tương ứng X n ↓ X) và tồn tại n để EX n − < ∞(tương ứng EX n + < ∞) thì EXn ↑ EX(tương ứng EX n ↓ EX).
7) (Bổ đề Fatou) Nếu X n ≥ Y với mọi n ≥ 1 và EY > −∞ thì
Nếu X n ≤ Y với mọi n ≥1 và EY < +∞ thì
ElimXn ≥ limEXn. Nếu | X n |≤ Yvới mọi n≥ 1 và EY < ∞ thì
8) (Định lý Lebesgue về hội tụ bị chặn) Nếu |X n | ≤ Y, với mọi n ≥
1,EY < ∞và Xn → X thìX khả tích, E|X n −X| → 0và EXn →EX(khi n→ ∞).
9) (Bất đẳng thức Markov) Giả sử X là biến ngẫu nhiên không âm Khi đó nếu tồn tại EX thì với mọi ε > 0 ta có
Các tính chất 1 - 8 suy ra từ các tính chất tương ứng của tích phân Lebesgue với độ đo chuẩn hóa Chúng ta chứng minh tính chất 9 Ta có
P(X ≥ ε) ≤ EX ε Qua các tính chất và ví dụ trên, ta thấy rằng kỳ vọng của biến ngẫu nhiên
Giá trị kỳ vọng X của một biến ngẫu nhiên là giá trị trung bình theo xác suất Nếu X nhận các giá trị với xác suất đồng đều, kỳ vọng sẽ tương đương với trung bình cộng của các giá trị đó.
Các loại hội tụ và tính chất
1.2.4.1 Định nghĩa Ta nói dãy biến ngẫu nhiên (X n , n ≥ 1) hội tụ đến biến ngẫu nhiên X (khi n → ∞)
• Theo xác suất nếu với mọi ε > 0 thì n→∞lim P(|X n −X| > ε) = 0.
• Đầy đủ nếu với mọi ε > 0 thì
• Theo trung bình cấp p,(p > 0) nếu lim n→∞E|X n −X| p = 0.
Trong lý thuyết xác suất, một chuỗi biến ngẫu nhiên \(X_n\) được coi là yếu nếu khi \(n\) tiến tới vô cùng, giới hạn phân phối \(F_n(x)\) hội tụ về \(F(x)\) với mọi \(x\) thuộc tập hợp liên tục \(C(F)\), trong đó \(F_n(x)\) và \(F(x)\) lần lượt là hàm phân phối của các biến ngẫu nhiên \(X_n\) và \(X\).
• Hội tụ theo điểm Trong định nghĩa của hội tụ theo phân phối chúng ta nói rằng hàm phân phối F(x) hội tụ theo từng điểm Nếu F(x) liên tục và
F n −→ L F nghĩa là với mỗi x, F n (x) −→F(x) Hay nói cách khác, với mỗi x và ∀ε > 0,∃n sao cho |F n (x)−F(x)| < ε,∀n ≥ N.
• Hội tụ đều của hàm phân phối Dãy hàm F n (x)hội tụ đều đến hàm F(x) nếu ∀ε > 0,∃N sao cho ∀n > N và ∀x ta có
Hay có thể nói cách khác: Dãy hàm F n (x) hội tụ đều đến hàm F(x) khi và chỉ khi sup x
|F n (x)−F(x)| → 0, trong đó F n (x), F(x) tương ứng hàm phân phối của biến ngẫu nhiên X n và X.
Hội tụ hầu chắc chắn, hay còn gọi là hội tụ với xác suất 1, là một khái niệm quan trọng trong lý thuyết xác suất Hội tụ theo trung bình cấp p, được biết đến với tên gọi hội tụ trong L p, thể hiện sự hội tụ của chuỗi số liệu trong không gian L p Bên cạnh đó, hội tụ đều theo phân phối, hay còn gọi là hội tụ Kolmogrov - Smirnov, là một hình thức hội tụ khác có ý nghĩa trong việc đánh giá sự phân phối của các biến ngẫu nhiên.
1) X n −→ h.c.c X khi và chỉ khi với mọi ε > 0 lim n→∞ P(sup m≥n |X m −X| > ε) = 0.
3) Nếu (X n , n ≥ 1) là dãy biến ngẫu nhiên độc lập và X n −→ h.c.c C thì
Theo tính chất 5, hội tụ theo phân phối nói chung yếu hơn hội tụ theo xác suất Tuy nhiên, trong trường hợp biến ngẫu nhiên giới hạn là hằng số, chúng ta có một tính chất đặc biệt.
Bài toán quy hoạch tuyến tính ngẫu nhiên
Bài toán quy hoạch ngẫu nhiên
Bài toán quy hoạch tuyến tính tổng quát có thể đưa về dạng min{f(x) =c T x} (LP) với điều kiện
Ax = b x ≥ 0, trong đó x = (x1 x2 xn) T là ma trận cỡ n×1, c = (c1 c2 cn) là ma trận cỡ 1×n, b = (b 1 b 2 b m ) T là ma trận cỡ m×1,A = (a ij ) là ma trận cấp m×n.
Bài toán quy hoạch tuyến tính ngẫu nhiên xuất hiện khi các thành phần của ma trận A, b, c phụ thuộc vào đại lượng ngẫu nhiên Để nghiên cứu loại bài toán này, có nhiều phương pháp tiếp cận khác nhau tùy thuộc vào yêu cầu thực tế Thông thường, các lớp bài toán được xem xét sẽ giúp định hướng cho việc giải quyết vấn đề hiệu quả hơn.
1.3.1.1 Quy hoạch tuyến tính ngẫu nhiên một giai đoạn
Quy hoạch tuyến tính ngẫu nhiên một giai đoạn là một loại bài toán được giải dựa trên dữ liệu ban đầu xác định Sau khi tìm ra phương án tối ưu, các phương pháp trực tiếp như quy hoạch tham số và tái tối ưu được áp dụng để điều chỉnh phương án này, nhằm thích ứng với sự biến đổi của các đại lượng ngẫu nhiên trong thực tế.
1.3.1.2 Quy hoạch ngẫu nhiên tuyến tính hai giai đoạn
Quy hoạch ngẫu nhiên tuyến tính hai giai đoạn là lớp bài toán phương án được xem xét 2 lần.
Trong giai đoạn đầu tiên, người ta sử dụng thông tin xác định để xây dựng phương án thông qua việc giải bài toán lập kế hoạch (LP) Kết quả của giai đoạn này là tìm ra phương án tối ưu.
Trong giai đoạn hai, dựa trên phương án tối ưu đã được giải, người ta điều chỉnh lại để phù hợp với thực tế khi chịu ảnh hưởng của đại lượng ngẫu nhiên Mục tiêu là tìm ra mức "phạt" tối thiểu do độ lệch từ giai đoạn một, thông qua việc xử lý dữ liệu bằng khái niệm kỳ vọng toán.
Bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn có dạng min{c T x+E(Q(x,z))}˜ (1.1) với điều kiện
Hàm Q(x,z)˜ được gọi là hàm hiệu chỉnh, với z˜∈ R n là vectơ ngẫu nhiên,
Kỳ vọng của biến ngẫu nhiên Q(x,z) được biểu diễn bởi E(Q(x,z)), trong đó vectơ x và y tương ứng đại diện cho biến của giai đoạn thứ nhất và giai đoạn thứ hai Ma trận D có kích thước m × m, thường có thể được lấy là ma trận đơn vị, với y = (y1 ym).
Dy thể hiện độ lệch giữa Ax với b và q = (q 1 , , q m ) thường gọi là vectơ phạt bởi tác động của z˜.
Giai đoạn thứ nhất biến x là nghiệm thu được trên cơ sở thông tin có được từ thực nghiệm.
Giai đoạn thứ hai xác định y là nghiệm thu bằng cách điều chỉnh nghiệm sơ bộ x từ giai đoạn 1 với thông tin chính xác, trong đó z˜ nhận giá trị thực.
Từ đó cho thấy bài toán (1.1) tương đương với bài toán min{c T x+E(qy(˜z))} với điều kiện
T(˜z)x+Dy(˜z) = h(˜z) x ≥ 0 y(˜z) ≥ 0 y(.) ∈ Y − Không gian các hàm đo được.
1.3.1.3 Quy hoạch ngẫu nhiên tuyến tính nhiều giai đoạn
Quy hoạch tuyến tính ngẫu nhiên nhiều giai đoạn là một bài toán phức tạp, trong đó phương án tối ưu được điều chỉnh qua các giai đoạn dựa trên thông tin dữ liệu ban đầu và ảnh hưởng của các đại lượng ngẫu nhiên Để giải quyết bài toán này, cần quan sát và phân tích từng giai đoạn, tương tự như việc xem xét các yếu tố trong hai giai đoạn khác nhau.
(LP1) Q 1 = min x (1) n c T 1 x (1) +E ω∈Ω [Q(x (1) , ω)]o, với điều kiện
X i=1 ptiE ω ti ∈Ω t[Qt(x (t−1) ), ωti)], ở đâyptilà xác suất của biến cốwti ∈ Ωt, i= 1,2, , qt,còn[Qt(x (t−1) ), ωti)] được xác định từ bài toán
(LP t) [Q t (x (t−1) ), ω t )] = min x (t) n c T t x (t) +E ω∈Ω [Q t−1 (x (t) , ω)] o , với điều kiện
Tính lồi của bài toán hai giai đoạn
Với mỗi A, b cố định, hàm Q(x,ez) là lồi theo x Do đó c T x+E[Q(x,z)]e là hàm lồi theo x và (1.1) là bài toán quy hoạch lồi.
Để chứng minh rằng hàm Q(x,z)e là hàm lồi, với b 0 và A 0 là các giá trị cố định, và x 1, x 2 là các vectơ không âm cố định, ta xem xét các phương án tối ưu y 1 và y 2 tương ứng với các giá trị b 0 và A 0 Giả sử λ thuộc khoảng [0,1], nhiệm vụ của chúng ta là chứng minh rằng Q(λy 1 + (1-λ)y 2, z) ≤ λQ(y 1, z) + (1-λ)Q(y 2, z).
Thật vậy, từ y 1 , y 2 ≥ 0 và 0 ≤ λ ≤ 1, ta có y 0 = λy 1 + (1 −λ)y 2 ≥ 0. Ngoài ra
= A 0 (λx 1 + (1−λ)x 2 )−b 0 Điều đó chỉ ra rằng y 0 là một phương án của (1.1) tương ứng với (λx 1 +
Từ đó suy ra Q(x,z)e là hàm lồi.
Tính lồi của c x +E[Q(x,ez)] là hiển nhiên vì phép toán đối với kỳ vọng là tuyến tính.
Dĩ nhiên tập phương án là tập lồi Do vậy bài toán (1.1) là bài toán quy hoạch lồi. Đó là điều phải chứng minh.
Bài toán quy hoạch ngẫu nhiên nhiều giai đoạn có thể được xác định thông qua bài toán quy hoạch ngẫu nhiên hai giai đoạn, cho thấy rằng bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn (cũng như nhiều giai đoạn) có thể được chuyển đổi thành bài toán quy hoạch lồi xác định Kết quả này đóng vai trò quan trọng trong việc tiếp cận và giải quyết bài toán quy hoạch tuyến tính ngẫu nhiên.
Một số yếu tố giải tích
Hàm nửa liên tục
• Một hàm f : X −→ R(Xđóng, X ⊂ R n ), f được gọi là nửa liên tục dưới tại x 0 ∈ X nếu lim x∈X,x→x 0 f(x) ≥ f(x 0 ).
Nếuf(x 0 ) hữu hạn thì điều kiện này có thể viết lại một cách tương đương,
∀ε > 0 tồn tại một lân cận V ⊂ X của x 0 sao cho f(x) > f(x 0 )−ε, ∀x ∈ x 0 +V.
•Hàm f được gọi là nửa liên tục dưới trên X nếu nó liên tục tại mọi điểm x ∈ X.
• Hàm f được gọi là nửa liên tục trên tại x 0 ∈ X nếu lim x∈X,x→x 0 f(x) ≤ f(x 0 ).
Nếuf(x 0 ) hữu hạn thì điều kiện này có thể viết lại một cách tương đương,
∀ε > 0 tồn tại một lân cận V ⊂ X của x 0 sao cho f(x) < f(x 0 )−ε, ∀x ∈ x 0 +V.
1 Một hàm f : X −→ R là nửa liên tục dưới trên toàn tập đóng
Tập X ⊂ R n được coi là nửa liên tục nếu và chỉ nếu với mọi giá trị α ∈ R, tập mức dưới {x ∈ X : f(x) ≤ α} là tập đóng Đồng thời, nó cũng nửa liên tục trên khi và chỉ khi với mọi α ∈ R, tập mức trên {x ∈ X | f(x) ≥ α} là tập đóng.
Để chứng minh định lý, chỉ cần tập trung vào phần đầu Nếu hàm f(x) nửa liên tục dưới trên tập X, thì với mọi dãy x_k hội tụ về x_0, trong đó x_k thuộc X và f(x_k) ≤ α, ta có f(x_0) ≤ lim (x_k → x_0) f(x_k) ≤ α Điều này chứng tỏ rằng x_0 thuộc X và f(x_0) ≤ α, từ đó khẳng định rằng mức dưới của hàm f(x) là đóng.
Ngược lại nếu với mọi α ∈ R tập {x ∈ X | f(x) ≤ α} đóng thì với mọi dãy x k ∈ X, x k →x 0 ∈ X, mà limf(x k ) < f(x 0 ) phải có ε > 0 để với mọi k đủ lớn f(x k ) ≤ f(x 0 )−ε, do đó f(x k ) ≤f(x 0 )−ε, mâu thuẫn.
• Hàm f được gọi là nửa liên tục trên trên X nếu nó liên tục tại mọi điểm x ∈ X
2 Một hàm f(x) nửa liên tục dưới trên một tập compact X phải đạt cực tiểu trên tập ấy Một hàm f(x) nửa liên tục trên trên một tập compact
X phải đạt cực đại trên tập ấy.
3 Một hàm tuyến tính bị chặn trên (hay dưới) trên một tập afin thì chỉ có thể đồng nhất hằng.
4 Một hàm f : X −→ R nửa liên tục dưới trên một tập đóng X 6= ∅ mà bức (coercive) trên X, nghĩa là f(x) → +∞ khi x ∈ X, k x k→ +∞, thì f phải có cực tiểu trên X.
5 Một hàm f : X −→ R nửa liên tục trên trên một tập đóng X mà −f bức trên X, nghĩa là f(x) → −∞, với x ∈ X, khi kx k→ +∞,thì f phải có cực đại trên X.
Hàm phân phối tích lũy
Hàm phân phối tích lũy F(x) được định nghĩa là P(X ≤ x), thể hiện xác suất mà biến ngẫu nhiên X nhận giá trị nhỏ hơn hoặc bằng x Để tính xác suất X nằm trong khoảng (a; b], với điều kiện a < b, ta sử dụng công thức F(b) − F(a) Theo quy ước, chữ F hoa được sử dụng để chỉ hàm phân phối tích lũy.
Hàm đóng
Hàm sốC : P(R s ) −→ 2 R s gọi là hàm đúng trờnP(R s ), nếu vớià ∈ P(R s ) tựy ý và dóy à n ∈ P(R s ), x n ∈ C(à n ) với à n −→ w à và x n −→ x thỡ x ∈ C(à) Trong đú P(R s ),P(R) lần lượt là cỏc tập độ đo xỏc suất Borel trờn
Hàm Lagrange
Cho bài toán quy hoạch min{f(x) : f i (x) ≤ 0, x ∈ M ⊂R n }.
Khi đó hàm L(x, λ) cho sau đây được gọi là hàm Lagrange
X i=1 λifi(x), trong đó λ = (λ i ) ∈ R m + Các giá trị λ i gọi là nhân tử Lagrange. Khi đó bài toán
L(x) := min x∈M L(x, λ) có bài toán đối ngẫu Lagrange là
CHƯƠNG 2 THUẬT TOÁN NHÁNH-CẬN GIẢI BÀI TOÁN (SL−M ILC)
2.1 Bài toán đầu tư tài chính sản xuất điện
Bài toán thực tế
Một công ty điện lực có thể đầu tư vào nhiều loại nhà máy điện như nhiệt điện, thủy điện, điện gió, điện mặt trời và điện hạt nhân Để sản xuất điện, công ty cần sử dụng nhiều loại nguyên liệu khác nhau, mỗi loại nguyên liệu có chi phí sản xuất riêng cho từng nhà máy Mục tiêu là tối ưu hóa việc đầu tư để giảm thiểu tổng chi phí, đồng thời đảm bảo khả năng cung cấp nguyên liệu không vượt quá giới hạn cho phép.
Thiết lập mô hình toán học
Để thiết lập mô hình toán học cho việc sản xuất điện, ta ký hiệu I = {1,2, , n}, trong đó xj (j ∈ I) đại diện cho số đơn vị sản phẩm điện được sản xuất tại nhà máy điện thứ j (với xj ≥ 0) Bài toán được đặt ra dưới dạng tối thiểu hóa, cụ thể là min{f = c T x} với các điều kiện đi kèm.
Qx = z, x ≥0, trong đó c = (c j ), x = (x j ), z = (b i ), c T x = P j∈I c j x j , Q = (a ij ) và x = (x j ) ≥ 0 khi và chỉ khi x j ≥ 0, j = 1, n.
Trong sản xuất, các giá trị lãi suất, chi phí và khả năng nguyên liệu thường biến động ngẫu nhiên, dẫn đến sai lệch trong điều kiện Qx = z và ảnh hưởng đến giá trị hàm mục tiêu Để cân bằng những sai lệch này, vectơ phạt q và biến phạt y được đưa vào sử dụng, trong đó ý nghĩa "phạt" thể hiện rằng nếu điều kiện nào bị ảnh hưởng bởi biến ngẫu nhiên, sẽ phải nhận phạt theo trọng số tương ứng Ngược lại, những điều kiện không bị ảnh hưởng sẽ không phải chịu phạt Mục tiêu là sản xuất với lượng phạt tối thiểu khi có tác động từ các yếu tố ngẫu nhiên.
Từ đó dẫn tới bài toán quy hoạch ngẫu nhiên minx n c T x+ min y q T y : W y = z(ω)−Qx, y ≥ 0 :x ≥ 0 o , trong đó W là một ma trận cấp m ×m nào đó, thông thường có thể lấy
W là ma trận đơn vị.
Trong trường hợp biến phạt y liên tục, chúng ta đối mặt với bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn thông thường Luận văn này tập trung vào việc nghiên cứu biến phạt y, với giá trị thuộc tập Z m +.
Bài toán tổng quát (SP − M ILC)
Bài toán
Bài viết này đề cập đến mô hình quy hoạch ngẫu nhiên trong bài toán đầu tư tài chính cho sản xuất điện, như đã nêu trong mục 2.1 Chúng tôi bắt đầu với bài toán quy hoạch tuyến tính ngẫu nhiên nguyên hỗn hợp tổng quát, được biểu diễn bằng phương trình tối thiểu hóa: minx {c T x + q T y} (2.1), với các điều kiện đi kèm.
Qx+W y = z(ω) x ∈ X, y ∈ Z m + ×R m + 0 , trong đó c = (c j ), j = 1, m 0 ; q = (q i ), i= 1, m+m 0 ; z(ω) là phần tử ngẫu nhiên;Q, W là các ma trận hữu tỉ Nói chungx, y phụ thuộc z(ω);X ⊆ R m là đa diện khác rỗng.
Theo lý thuyết quy hoạch ngẫu nhiên hai giai đoạn ta có thể chuyển bài toán (2.1) về bài toán sau minx n c T x+ min y {q T y : W y = z(ω)−Qx, y ∈ Z m + ×R m + 0 } : x ∈ X o
Hàm Φ(t) được định nghĩa là giá trị tối thiểu của hàm mục tiêu q^T y dưới điều kiện W y = t và y thuộc Z^m_+ × R^m_+^0 Đây là hàm giá trị của bài toán quy hoạch tuyến tính nguyên hỗn hợp min{q^T y : W y = t, y ∈ Z^m_+ × R^m_+^0}, đã được nghiên cứu trong lĩnh vực tối ưu hóa tham số Để đảm bảo tính đầy đủ cho bài toán, ngoài các giả thiết đã nêu, ta còn giả thiết thêm rằng W(Z^m_+ × R^m_+^0) = R^s.
Có thể thấy rằng Φ nhận giá trị thực và nửa liên tục dưới trên R s , vì tlimn →tinf Φ(t n ) ≥ Φ(t), ∀t ∈ R s
Bài toán (2.2) chỉ ra rằng bài toán tối ưu ngẫu nhiên (2.1) cho ta một họ các biến ngẫu nhiên dạng
Mỗi kết quả của giai đoạn thứ nhất x ∈ X tạo ra một biến ngẫu nhiên f(x, ω) := c T x + Φ(z(ω) − Qx) Trong bài toán quy hoạch ngẫu nhiên hai giai đoạn, mục tiêu là tối ưu hóa các quyết định chưa biết Điều này có nghĩa là chúng ta chỉ có thể xác định một đại lượng x "tốt nhất" hoặc một phần tử x "tốt nhất" khác trong tập biến ngẫu nhiên.
Từ những cách tiếp cận trước đây sử dụng kỳ vọng dẫn đến bài toán tối ưu hóa minx {E[f(x, ω)] : x ∈ X} (2.5)
Sử dụng các tổng có trọng lượng trong E và một vài độ rủi ro R dẫn đến những mô hình rủi ro trung bình. minx {E[f(x, ω)] +ρ.R[f(x, ω)] : x ∈ X}, (ρ > 0, cố định ) (2.6)
Ký hiệu
Biến ngẫu nhiên X được coi là cực tiểu cấp 1 của hàm h nếu nó tốt hơn biến ngẫu nhiên Y khi điều kiện Eh(X) ≤ Eh(Y) được thỏa mãn với mọi hàm không giảm h, và cả hai kỳ vọng đều tồn tại.
Người ta chứng minh được một kết quả tương đương như sau.
Cho P(R^s) và P(R) là các tập độ đo xác suất Borel trên R^s và R tương ứng Nếu a ∈ P(R^s) và ν ∈ P(R), chúng ta ký hiệu các độ đo xác suất sinh ra từ biến ngẫu nhiên z(ω) và d(ω).
• Chúng ta cố định ν, hàm đa trị C : P(R s ) −→2 R m với
Quy hoạch ngẫu nhiên hai giai đoạn (2.1) và tập hợp (2.4) giả định rằng chi phí chuẩn ngẫu nhiên d(ω) đã được xác định Đối với x ∈ X "chấp nhận được", hàm tối ưu f(x, ω) không vượt quá chi phí chuẩn d(ω) Từ đó, chúng ta tối ưu hóa hàm g: R^m → R cho mọi x ∈ X chấp nhận được, dẫn đến bài toán quy hoạch ngẫu nhiên với ràng buộc cảm sinh theo dạng tuyến tính nguyên hỗn hợp Bài toán này được ký hiệu là (SP −M ILC), tức là Stochastic Program with first-order dominance induced by Mixed-Integer Linear Constraint, với mục tiêu tối thiểu hóa g(x) dưới ràng buộc f(x, ω) ≤ d(ω).
Các tính chất cơ bản của bài toán
Định nghĩa
Một dóy {à n } trong P(R s ) được gọi là hội tụ yếu tới à ∈ P(R s ), nếu với mọi hàm liên tục bị chặn h : R s −→ R thỏa mãn
Định lý
Giả sử (A 1 ) và (A 2 ) được thoả mãn Khi đó C là hàm đóng, đa trị trên P(R s ) Điều này cú nghĩa là với à ∈ P(R s ) tựy ý và dóy à n ∈ P(R s ), x n ∈ C(à n ), với à n −→ w à và x n → x thỡ x ∈ C(à).
Chứng minh Giả sử x n ∈ C(à), với mọi n và theo (2.7) ta cú ν[d ≤ η] ≤à n [f(x n , z) ≤η], ∀η ∈ R, (2.9) trong đó ta ký hiệu d ≤η và f(x n , z) ≤ η lần lượt là các tập {d ∈ R : d ≤ η} và {z ∈ R s : f(x n , z) ≤ η}, tương ứng.
Ký hiệu M η (x) được định nghĩa là tập hợp {z ∈ R s : f(x, z) > η} Dựa trên giả thiết (A 1) và (A 2), hàm Φ và f(x, •) đều là nửa liên tục dưới, dẫn đến M η (x) là tập mở với η ∈ R cho mọi x ∈ R m Ký hiệu mới (2.9) cho thấy rằng với mọi n ν[d ≤ η] và n [M η (x n )] ≤ 1, điều này áp dụng cho tất cả η ∈ R.
Từ M η (x) mở, và các kết quả đã có ta suy ra à[M η (x)] ≤ lim inf n à n [M η (x)], ∀η ∈ R (2.11) Tính nửa liên tục dưới của hàm Φ cho thấy
Mη(x) ⊆ lim inf n Mη(xn), ∀η ∈ R, với "lim inf n" là giới hạn dưới của Mη Đặt tập hợp tất cả các điểm thuộc một số hữu hạn của Mη(xn), từ đó suy ra rằng à n [Mη(x)] ≤ à n [lim inf k Mη(xk)] ≤ lim inf k à n [Mη(xk)] ∀η ∈ R Khi lấy giới hạn dưới cho ba vế theo n, ta có lim inf n à n [Mη(x)] ≤ lim inf n lim inf k à n [Mη(xk)] ≤ lim inf n à n [Mη(xn)] ∀η ∈ R.
(2.13) Đối với bất đẳng thức cuối cùng chúng ta chọn dãy con đường chéo với n= k Từ (2.11) và (2.13) ta có à[M η (x)] ≤ lim inf n à n [M η (x n )], ∀η ∈ R (2.14)
Lấy giới hạn theo n trong (2.10) và từ (2.14) ta có ν[d ≤ η] +à[Mη(x)] ≤ν[d ≤ η] + lim inf n àn[Mη(xn)] ≤1, ∀η ∈ R.
Từ (2.10), (2.9) và (2.7), suy raf(x, z) 1 d.Do tính đóng củaX, x n →x, và x n ∈ X với mọi n chỳng ta suy ra x ∈ X Từ đú suy ra x ∈ C(à). Đó là điều phải chứng minh.
Chú ý
Chú ý 1 (Về biến ν): Trong bối cảnh P(R) có sự hội tụ đều của hàm phân phối theo Kolmogrov - Smirnov, theo định lý 2.3.2, hàm đa trị C : P(R s) × P(R) −→ 2 R m được thể hiện một cách rõ ràng.
Nếu ν n hội tụ về ν theo Kolmogorov - Smirnov, thì νn[d ≤ η] →ν[d ≤η], ∀η ∈ R.
Chú ý 2 (Về hội tụ yếu trong P(R s )) đề cập đến một lớp các biến ngẫu nhiên khác nhau, nơi đã xây dựng một kết quả chính xác liên quan đến điều kiện ràng buộc tối ưu bậc nhất và sự hội tụ trong không gian P(R s ) Kết quả này được xác định bởi một chuỗi phân kỳ và so với các kết quả trước đó, Định lý 2.3.2 cung cấp một biến ngẫu nhiên tập trung hơn, liên quan đến khái niệm hội tụ yếu trong P(R s ).
Sự hội tụ yếu của độ đo xác suất không phải là kết quả của tính phân kỳ trong các kết quả đã có, mà là một hiện tượng độc lập.
Chú ý 3 đề cập đến sự hội tụ yếu trên P(R) Định lý 2.3.2 phân nhỏ biến ν và áp dụng cho P(R) với sự hội tụ yếu Để thực hiện điều này, cần đặt η = 0 và chọn à, x, Φ sao cho 1−à[M 0 (x)] = 1/2 Giả sử ν n và ν là các độ đo xác suất riêng biệt, với ν n từ 1 đến n và ν bằng 0 Khi đó, ν n sẽ hội tụ yếu về ν.
2.Định lý 2.3.2 suy ra rằng C(à) là một tập đúng với mọi à ∈ P(R s ).
Hệ quả
Giả sử (A 1 ) và (A 2 ) được thoả món Khi đú C(à) là tập con đúng của R m , đối với mỗi à ∈ P(R s ).
Bài toán tối ưu hóa (2.8) có tính khả thi, đặc biệt khi hàm nửa liên tục dưới g, X bị chặn và tập C(à) không rỗng Giá trị tối ưu có thể đạt được và hữu hạn, điều này được chứng minh qua tính chất nửa liên tục của các ánh xạ như đã đề cập trong chương 1 Kết luận rằng (2.8) có thể được xem như một bài toán quy hoạch tham số với phân bố xác suất của biến ngẫu nhiên z(ω) được đưa vào tham số.
Định lý
Giả sử (A1) và (A2) được thỏa mãn, với X là tập không rỗng và compact, và g là hàm nửa liên tục dưới Lấy à ∈ P(Rs) sao cho P(à) có một phương án tối ưu Khi đó, hàm giá trị tối ưu ϕ(à) được định nghĩa là inf{g(x) : x ∈ C(à)} là nửa liên tục dưới tại à.
Giả sử rằng C(à n) không rỗng với mọi n, ta có ϕ(à n) = +∞ không ảnh hưởng đến kết quả của lim inf n ϕ(à n) ≥ ϕ(à) Với ε > 0 cố định, tồn tại x n ∈ C(à n) sao cho g(x n) ≤ ϕ(à n) + ε Nhờ tính compact của X, tồn tại điểm tụ x n Do tính đúng của C(à), x thuộc C(à) Kết hợp với tính nửa liên tục dưới của g, ta có ϕ(à) ≤ g(x) ≤ lim inf n g(x n) ≤ lim inf n ϕ(à n) + ε.
Do ε > 0 lấy tùy ý, nên từ đây suy ra điều kết luận của định lý. Định lý chứng minh xong.
Định lý
Trong bài viết này, z(ω) và d(ω) được xác định với các phân phối riêng biệt là z l và d k, với xác suất tương ứng π l và p k Định nghĩa g(x) là hàm tuyến tính g T x, với X bị giới hạn Dưới giả định (A 1) và (A 2), tồn tại một hằng số M, cho phép bài toán (SP −M ILC) tương đương với bài toán quy hoạch tuyến tính nguyên hỗn hợp min{g(x) = g T x} với các điều kiện đã nêu.
P l=1 π l θ lk ≤d k , ∀k x ∈ X, y lk ∈ Z m + ×R m + 0 , θ lk ∈ {0,1}, ∀l,∀k trong đó d k := 1−ν[d ≤d k ], k = 1, K.
Chứng minh Do (2.7) nên điều kiện buộc f(x, z) 1 d tương đương với ν[d ≤η]≤ à[f(x, z) ≤ η], ∀η ∈ R (2.16)
Ta suy ra rằng điều này tương đương với ν[d ≤ dk]≤ à[f(x, z) ≤ dk] với k = 1,2, , K (2.17)
Sự cần thiết của (2.17) là hiển nhiên Đối với giả thiết đầy đủ rằngd k được sắp thứ tự tăng dần và xét η thỏa mãn d k ≤ η ≤d k+1 Khi đó ta có ν[d≤ η] = ν[d ≤ d k ] ≤à[f(x, z) ≤ d k ] ≤à[f(x, z) ≤ η].
Đẳng thức đầu tiên đúng khi d riêng biệt và có nhiều điểm giữa d k và d k+1 Bất đẳng thức hai được xác định từ (2.17), trong khi bất đẳng thức cuối đúng nhờ tính đơn điệu của hàm phân phối tích lũy Khi η < dl, vế trái của (2.16) bằng 0, do đó (2.16) đúng Nếu η > d k, thì (2.17) đúng khi k = K, và tính đơn điệu của hàm phân phối tích lũy dẫn đến vế phải của (2.16) cũng đúng, khẳng định tính tương đương Tiếp theo, chúng ta sẽ xây dựng số M như đã nêu trong định lý.
Doϕ là hàm đơn điệu tăng nên vế phải của bất đẳng thức trên là hữu hạn.
Do (A 1 ),(A 2 ), nên tồn tại các hằng số bất biến α > 0, β > 0 sao cho bất đẳng thức sau đây thỏa mãn với mọi t 1 , t 2 ∈ R s
Ngoài ra,(A 2 ) kéo theo Φ(0) = 0 Điều này có thể ước lượng như sau
≤ kck.kxk+αkz l k+αkQk.kxk+β +|d k |.
Từ X bị chặn, suy ra tính hữu hạn của cận trên Bằng cách xét biến cố đối ở vế phải, ta viết lại (2.16) như sau: à[f(x, z) > d k ] ≤1−ν[d ≤ d k ] =: d k , với k = 1,2, K (2.18) Với mỗi k ∈ {1,2, , K}, ta xét hai tập hợp sau
S 2 :={x ∈ X : ∃θ l ∈ {0,1},∃y l ∈ Z m + ×R m + 0 , l = 1, L}, trong đó θl và yl thỏa mãn thêm các điều kiện
P l=1 π l θ l ≤d k , với M được chọn như trên.
Chúng ta có thể chứng minh bằng cách chỉ ra S 1 = S 2
Thật vậy, bắt đầu ta chứng minh bao hàm thức S 1 ⊆ S 2 Lấy x ∈ S 1 và xét
Khi đó, do định nghĩa của S 1 ta có P l∈I π l ≤ d k Đặt θ l := 1 với l ∈ I và θ l = 0 với l /∈ I Điều này cho ta
Với l /∈ I ta có: c T x+ Φ(z l −Qx) ≤ d k Do đó tồn tại y l ∈ Z m + ×R m + 0 kéo theo c T x+q T y l −d k ≤ 0 = M θ l và Qx+W y l = z l
Vớil ∈ I ta lấy yl ∈ Z m + ×R m + 0 sao choQx+W yl = zl và q T yl = Φ(zl−Qx).
Từ cách chọn M chúng ta có: c T x+q T y l −d k ≤M = M θ l Điều này chứng tỏ x ∈ S 2
Bây giờ ta chứng minhS 2 ⊆S 1 Lấyx ∈ S 2 và xétI := {l ∈ {1, , L} : θl = 0} Với mỗi l ∈ I khi đó tồn tại yl ∈ Z m + ×R m + 0 sao cho c T x+q T y l −d k ≤0 và Qx+W y l = z l
Do đó c T x+ Φ(z l −Qx) ≤ d k với mỗi l ∈ I
{l ∈ {1, L} : c T x+ Φ(z l −Qx) > d k } ⊆ {l ∈ {1, , L} :θ l = 1}. Điều này cho thấy à[c T x+ Φ(z −Qx) > d k ] ≤ X l / ∈I π l θ l L
Từ đó ta suy ra điều phải chứng minh.
Thuật toán nhánh và cận giải bài toán (SP − M ILC )
Nhận xét
Chứng minh của định lý 2.3.6 chỉ ra rằng trong không gian xác suất hữu hạn, bài toán quy hoạch ngẫu nhiên với điều kiện ràng buộc tối ưu (2.8) tương đương với bài toán tối ưu hóa có điều kiện ràng buộc xác suất hữu hạn, cụ thể là min{g T x : x ∈ X, à[f(x, z) ≤ d k ]≥ ν[d ≤ d k ], k = 1, 2, , K}.
So với bài toán quy hoạch ngẫu nhiên có điều kiện ràng buộc truyền thống, một thách thức mới xuất hiện là hàm f(x, z) được xác định bởi hàm giá trị của bài toán cực trị khác và có tính giải tích kém hơn.
Trong không gian xác suất hữu hạn, tính tối ưu ngẫu nhiên sẽ giảm xuống khi số lượng điều kiện ràng buộc xác suất trở nên hữu hạn Nhiều tác giả cũng đã nghiên cứu các biến ngẫu nhiên khác trong bối cảnh này.
Bài toán quy hoạch tuyến tính nguyên hỗn hợp, theo định lý 2.3.6, có thể được giải quyết bằng phần mềm chuyên dụng Khi dữ liệu L và K tăng và phân phối chuẩn, phương pháp này giúp tiếp cận giới hạn của bài toán Lưu ý rằng giá trị L trong điều kiện ràng buộc xuất hiện trong không gian xác suất riêng biệt của quy hoạch ngẫu nhiên truyền thống, dẫn đến các điều kiện ràng buộc như c T x + q T y lk - d k ≤ M θ lk, ∀l, ∀k.
Khi cố định K, không có sự ràng buộc rõ ràng giữa các biến y lk và θ lk, mà phụ thuộc vào chỉ số l trong tập hợp {1,2, , L} Sự liên kết chỉ được thiết lập thông qua biến x, xuất hiện đồng nhất trong toàn bộ Các biến này cần phải độc lập với l và k, dẫn đến việc với K đã cho sẽ tạo ra một phân tử của L, từ đó hình thành điều kiện ràng buộc.
Công thức X l=1 π l θ lk ≤ d k ∀k (2.19) thể hiện sự liên kết giữa nhiều biến dựa trên các giá trị khác nhau của l ∈ {1,2, L} Điều này cho thấy các mô hình đầy đủ không tuân theo cấu trúc của tập I.
Xác định cận
Ý tưởng cơ bản của thuật toán tìm cận dưới là sử dụng một sự nới lỏng phù hợp để xác định cận trên, thông qua việc áp dụng kỹ thuật riêng, bao gồm hai công việc chính là "phân nhánh" và "tính cận" trong bài toán tối ưu toàn cục Đối với cận dưới, sự nới lỏng được thực hiện theo phương pháp "gấp đôi", trong đó biến x trở nên nhẹ hơn nhờ vào sự xuất hiện của x l (với l = 1, 2, , L) Điều kiện ràng buộc (2.19) được nới lỏng bằng phương pháp Lagrange, trong đó ta đặt x = P L l=1 π l θ l và sử dụng các nhân tử Lagrange λk ≥ 0 cho k = 1, 2, , K Hàm Lagrange được định nghĩa để phục vụ cho quá trình này.
X k=1 λk(θlk −dk). Điều này dẫn đến bài toán Lagrange đối ngẫu max{D(λ) : λ ∈ R K + }, trong đó
Bây giờ, bài toán tối ưu D(λ), được chia theo l và ta được
Đối ngẫu Lagrange là bài toán cực đại của hàm lõm không trơn, với giá trị tối ưu là cận dưới của quy hoạch tuyến tính nguyên hỗn hợp Để giải bài toán này, thường sử dụng thuật toán "bó" trong tối ưu hóa lồi không trơn, như phương pháp bó cônic của C Helmberg và K C Kiwiel Quá trình lặp lại yêu cầu hàm giá trị D(λ) và sự cân bằng từ ∂D(λ), trong đó tính tách là yếu tố cốt yếu, dẫn đến phân hoạch bài toán tối ưu hóa D(λ) thành các bài toán con tương ứng z l.
Theo nguyên tắc, phương pháp xây dựng cận dưới có thể được cải thiện thông qua sự nới lỏng Lagrange, không chỉ với (2.19) mà còn đối với ẩn x, được biểu thị bởi đồng nhất thức x 1 = x 2 = = x L Tuy nhiên, điều này dẫn đến sự gia tăng đáng kể về số chiều trong đối ngẫu Lagrange, từ K đến K + m.(L−1) L là số hàm phân phối z l, trong khi K là số hàm phân phối chuẩn d k Quan sát cho thấy L luôn lớn hơn K; ví dụ, L có thể đạt hàng trăm hoặc hàng nghìn, trong khi K thường chỉ khoảng 20 hoặc thấp hơn.
2.4.2.2 Cận trên.Một cận trên của giá trị tối ưu của (2.15) được xác định bởi sự tìm kiếm sau nhằm mục đích tìm kiếm một phương pháp khả thi cho (2.15) Nguồn vào tìm kiếm bao gồm x l là những phần xe l của phương án tối ưu và những bài toán con trong (2.20) cho ta λ tối ưu hoặc gần tối ưu.
Thuật toán tìm cận trên
Bước đầu tiên là xác định xe l, với l = 1, 2, , L, làm điểm xuất phát cho x và chọn một "ứng cử viên hợp lý" x Có thể chọn phương án phát sinh thường xuyên nhất hoặc sử dụng hàm minL l (xl, θl, λ) để tìm giá trị tối thiểu, hoặc tính giá trị trung bình xel cho l = 1, 2, , L, và làm tròn đến số nguyên nếu cần.
Bước 2: Kiểm tra những bài toán sau có khả thi không l = 1,2, L min{g T x} (2.21) với điều kiện
+ Nếu x không thỏa mãn (2.15) thì quá trình tìm kiếm dừng lại, với cận trên là +∞.
Bước 3: Kiểm tra θ lk , đã tìm thấy trong (2.21) bằng cách kiểm tra bất đẳng thức
+ Nếu đúng, vậy thì phương án của( 2.15) được tìm thấy Quá trình tìm kiếm dừng lại với cận trên g T x.
+ Ngược lại, chuyển sang bước 4.
Bước 4: Giải các bài toán (với mỗi l = 1,2, , L) sau: min
Bước 5: Trở lại bước 3 với θ lk được tìm thấy ở bước 4.
+ Nếu phần kiểm tra là đúng, khi đó việc tìm kiếm dừng lại, với cận trên là g T x.
+ Ngược lại, quá trình tìm kiếm dừng lại, với cận trên là +∞.
Bước 4 nhằm mục đích "loại bỏ" θ lk để thực hiện (2.19) và tiếp tục với phương án tìm thấy trong bước 2 Tác động của bước 4 trở nên đặc biệt quan trọng khi một lựa chọn θ lk "tồi" trong bước 2 dẫn đến việc kiểm tra ở bước 3 thất bại, mặc dù x vẫn thỏa mãn (2.15) với các giá trị θ lk khác.
Phân nhánh
Phương pháp tính cận được tổ chức theo sơ đồ nhánh và cận, trong đó nhánh được thực hiện thông qua phân tích tập X với độ mịn ngày càng tăng Điều này có nghĩa là tập X trở nên chi tiết hơn theo thời gian Để đảm bảo tính chính xác trong việc mô tả bài toán quy hoạch tuyến tính nguyên hỗn hợp, bất đẳng thức tuyến tính được sử dụng để phân nhánh.
Trong bài toán tối ưu, ký hiệu P đại diện cho tập hợp các bài toán đang được xem xét, trong khi ϕ LB (P) là cận dưới cho giá trị tối ưu của mỗi bài toán thuộc P Hơn nữa, ϕ thể hiện cận trên tốt nhất hiện tại đối với giá trị tối ưu của bài toán (2.15), và X(P) là một phần tử trong phân chia của X tùy thuộc vào P.
Như kết quả định lý 2.3.6 đã cho thấy, để giải bài toán (SP −M ILC), ta chỉ cần giải bài toán tương đương (2.15) min{g(x) =g T x} (2.15) với điều kiện
P l=1 πlθlk ≤ dk, ∀k, x ∈ X, ylk ∈ Z m + ×R m + 0 , θlk ∈ {0,1}, ∀l,∀k trong đó dk := 1−ν[d ≤ dk], k = 1, K.
Thuật toán nhánh và cận
Bước 1: (Khởi đầu) Đặt P = {(2.16)} và ϕ := +∞.
Bước 2: (Kết thúc) Nếu P = ∅ thì x, với ϕ = g T x, là phương án tối ưu cần tìm.
Bước 3: Lựa chọn và loại bỏ một bài toán P trong P Sử dụng phương pháp tìm cận để xác định một cận dưới ϕ LP (P) và áp dụng thuật toán 2.4.2.2 nhằm tìm một phương án chấp nhận được x ∈ P.
+ Nếuϕ LP (P) = +∞ (không gặp ở các bài toán con trong (2.20)) hoặc ϕ LP (P) > ϕ(kém P), thì trở lại bước 2.
+ Nếu ϕ LP (P) = g T x (tối ưu đối với P) thì kiểm tra g T x < ϕ có thỏa mãn không.
- Nếu thỏa mãn thì ϕ := g T x Trở lại bước 2.
- Nếu ngược lại thì ϕ := g T x Sang bước 5.
Bước 5 trong quy trình là tạo hai bài toán con P1 và P2 thông qua việc phân chia tập X(P), sau đó cập nhật P bằng cách thêm P1 và P2 vào tập hợp Để đánh giá hiệu quả của thuật toán, một nghiên cứu của các tác giả R Gollmer, F Neuce, và R Schultz vào năm 1999 đã thực hiện thử nghiệm trên một mô hình thực tế với 17,500 biến, bao gồm 9,000 biến Boolean và 8,500 biến liên tục, cùng với 22,000 điều kiện ràng buộc.
I Luận văn đã trình bày được các kết quả chính sau đây:
1.1 Trình bày được một cách có hệ thống những kiến thức cơ bản, cần thiết cho việc nghiên cứu các nội dung chính của luận văn.
1.2 Tìm được mô hình thực tế về bài toán đầu tư tài chính sản xuất điện nhằm dẫn đến bài toán tổng quát cần nghiên cứu.
1.3 Nêu được bài toán quy hoạch tuyến tính ngẫu nhiên, với ràng buộc cảm sinh bởi dạng tuyến tính nguyên hỗn hợp, cần được nghiên trong đề tài.
1.4 Trình bày được những tính chất cơ bản của bài toán Trong đó đáng chú ý là Định lý 2.3.6 cho phép ta chuyển việc giải bài toán quy hoạch ngẫu nhiên về giải bài toán quy hoạch tất định.
1.5 Trên cơ sở kết quả đã nêu, chúng tôi đã trình bày được thuật nhánh- và-cận giải bài toán đã đặt ra.
Về chủ đề "Bài toán đầu tư tài chính sản xuất điện", chúng tôi đã trình bày chi tiết trong mục 2.1 của bài viết gửi đăng tại "Kỷ yếu Hội thảo khoa học Toán - Tin ứng dụng" diễn ra tại Đại học Vinh vào ngày 26 tháng 11 năm 2011.
II Sau khi hoàn thành luận văn, chúng tôi nhận thấy còn một số nội dung cần được tiếp tục nghiên cứu bao gồm:
- Thuật toán cần được chi tiết hơn, trình bày ví dụ về thuật toán cụ thể bằng số.
- ứng dụng thuật toán 2.4.4 vào việc giải các bài toán thực tế.