Tài liệu Bài toán quy hoạch phi tuyến với kỹ thuật phân rã và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA TOÁN - CƠ - TIN HỌC Phan Ngọc Tú BÀI TOÁN QUY HOẠCH PHI TUYẾN VỚI KỸ THUẬT PHÂN RÃ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ Chuyên ngành: Toán giải tích Mã số: 60.46.01.02 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS NGUYỄN HỮU ĐIỂN Hà Nội - 2014 1 DANH MỤC CÁC KÝ HIỆU VIẾT TẮT QHTT Quy hoạch tuyến tính. QHPT Quy hoạch phi tuyến. Rn Không gian thực n chiều. ∇ f (x) Gradient của hàm f tại điểm x. k.k Chuẩn Euclid. ∇2 f ( x ) ∂ f (x) x Ma trận Hessian của hàm f tại điểm x. Đạo hàm riêng của hàm f theo biến x. Mục lục Lời nói đầu iii 1 Các kiến thức cơ bản 1 1.1 Một số kiến thức về bài toán tối ưu . . . . . . . . . . . . . . . . 1 1.2 Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Phân rã trong quy hoạch tuyến tính 2.1 2.2 Những ràng buộc phức tạp . . . . . . . . . . . . . . . . . . . . 12 2.1.1 Cấu trúc bài toán . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Sự phân rã . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Thuật toán phân rã Dantzig-Wolfe . . . . . . . . . . . . 21 Những biến phức tạp . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.1 Cấu trúc bài toán . . . . . . . . . . . . . . . . . . . . . . 30 2.2.2 Thuật toán phân rã Benders . . . . . . . . . . . . . . . . 31 3 Phân rã trong quy hoạch phi tuyến 3.1 12 44 Phương pháp giảm dư Lagrange . . . . . . . . . . . . . . . . . 45 3.1.1 45 Sự phân rã . . . . . . . . . . . . . . . . . . . . . . . . . . i 3.2 3.1.2 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.3 Đối ngẫu bất khả thi . . . . . . . . . . . . . . . . . . . . 51 3.1.4 Cập nhật hệ số . . . . . . . . . . . . . . . . . . . . . . . 52 Phân rã Lagrange gia tăng . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Sự phân rã . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.2 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.3 Tính tách được . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.4 Cập nhật hệ số . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.5 Cập nhật tham số phạt . . . . . . . . . . . . . . . . . . . 57 Kết luận 61 Tài liệu tham khảo 62 ii Lời nói đầu Tối ưu hóa là một môn toán học ứng dụng đang được nghiên cứu, giảng dạy và học tập ở nhiều trường Đại học - Cao đẳng, góp phần quan trọng trong việc ứng dụng khoa học công nghệ vào cuộc sống và sản xuất. Ngày nay, Quy hoạch tuyến tính (QHTT) vẫn là một phần quan trọng và được phát triển hoàn thiện nhất trong lý thuyết tối ưu hóa. Phần ít được đề cập hơn là tối ưu phi tuyến, còn gọi là quy hoạch phi tuyến (QHPT). Ở cả hai phần này, một số bài toán thực tế trong cuộc sống ta hay gặp các bài toán có kích thước lớn, do đó việc xử lý chúng như thông thường là điều không thể. Vì vậy việc thiết kế những thuật toán theo hướng giải quyết các bài toán lớn là một trong những vấn đề vẫn đang được quan tâm xử lý hiện nay. Trong luận văn xem xét chú ý đến những trường hợp riêng của các bài toán tối ưu hóa, những bài toán có cấu trúc phân rã có thể khai thác thuận lợi. Các bài toán phân rã tối ưu hóa là những bài toán phổ biến trong kỹ thuật và khoa học ứng dụng. Luận văn đề cập đến các bài toán QHTT và QHPT với các trường hợp ràng buộc phức tạp và biến phức tạp. Các kỹ thuật phân rã bao gồm Dantzig - Wolfe, Benders, phương pháp giảm dư Lagrange và những kỹ thuật khác. Bố cục của luận văn bao gồm ba chương Chương 1 trình bày một số khái niệm cơ bản về tối ưu hóa, định lý Karush - Kuhn - Tucker, bài toán đối ngẫu. Chương 2 tập trung vào các bài toán có cấu trúc phân rã trong QHTT, iii trong đó thuật toán phân rã Dantzig - Wolfe được đề cập đến trong trường hợp ràng buộc phức tạp và thuật toán Benders trong trường hợp biến phức tạp. Ở đó có các ví dụ minh họa rõ hơn. Chương 3 tập trung vào một số bài toán có cấu trúc phân rã trong QHPT, trong đó với trường hợp ràng buộc phức tạp được xem xét qua các ví dụ sử dụng phương pháp giảm dư Lagrange và phương pháp Lagrange gia tăng. Trong luận văn chắc chắn không thể tránh khỏi những hạn chế và sai sót, tôi mong nhận được sự góp ý và những ý kiến đóng góp của Thầy Cô và bạn đọc. Qua đây em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS.TS Nguyễn Hữu Điển, người đã giúp đỡ em trong quá trình thực hiện luận văn. Hà Nội, tháng 09 năm 2014 Học viên Phan Ngọc Tú iv Chương 1 Các kiến thức cơ bản 1.1 Một số kiến thức về bài toán tối ưu Trong không gian vectơ R n , cho D ⊆ R n là một tập khác rỗng và hàm số thực f : D → R tùy ý. Bài toán tối ưu có dạng (P) min{ f ( x) : x ∈ D } là bài toán tìm vectơ (điểm) x∗ ∈ D sao cho f ( x∗ ) ≤ f ( x) với mọi x ∈ D. Trường hợp D = R n ta có bài toán tối ưu không ràng buộc min{ f ( x) : x ∈ R n } hay minn f ( x) x ∈R Trái lại, (P) là bài toán tối ưu có ràng buộc. Khi ấy tập D thường được cho bởi (1.1)  D = x ∈ R n : gi ( x) 6 0, i = 1, . . . , m; h j ( x) = 0, j = 1, . . . , p với gi , h j : R n → R là các hàm số cho trước, gọi là các hàm ràng buộc. Các hệ thức gi ( x) ≥ 0 gọi là các ràng buộc bất đẳng thức, các hệ thức h j ( x) = 0 gọi là các ràng buộc đẳng thức. Bài toán (P) với f (x) không tuyến tính hoặc tập D cho bởi (1.1) trong đó có ít nhất một trong các hàm gi , h j là phi tuyến. Các bài toán tối ưu phi tuyến thuộc loại bài toán tối ưu liên tục (không ràng buộc khi D = R n hay có ràng buộc khi D cho bởi các đẳng thức và bất đẳng thức). 1 Định nghĩa 1.1. (Hàm nửa liên tục) + Hàm f : D → R gọi là hàm nửa liên tục dưới tại điểm x ∈ D nếu với mỗi ε > 0 có một δ > 0 sao cho f ( x ) − ε 6 f ( x) với mọi x thuộc D, k x − xk < δ. Hàm f gọi là nửa liên tục dưới trên D nếu f liên tục dưới tại mọi điểm x ∈ D. Định nghĩa trên tương đương với limx ∈ D,x →x f ( x) > f ( x ). + Hàm f : D → R gọi là hàm nửa liên tục dưới tại điểm x ∈ D nếu với mỗi ǫ > 0 có một δ > 0 sao cho f ( x) 6 f ( x ) + ε với mọi x thuộc D, k x − xk < δ. Hàm f gọi là nửa liên tục trên trên D nếu f liên tục trên tại mọi điểm x ∈ D. Định lí 1.1. Một hàm f(x) nửa liên tục dưới trên một tập compact D khác rỗng phải đạt cực tiểu trên D. Tương tự, một hàm f(x) nửa liên tục trên trên một tập compact D khác rỗng phải đạt cực đại trên D. Định lí 1.2. a) Một hàm f : D → R nửa liên tục dưới trên một tập đóng D khác rỗng mà bức (coercive) trên D, nghĩa là f ( x) → +∞ khi x ∈ D, k xk → +∞, thì f phải có cực tiểu trên D. b) Một hàm f : D → R nửa liên tục trên trên một tập đóng D khác rỗng mà - f bức trên D, nghĩa là f ( x) → −∞ khi x ∈ D, k xk → +∞, thì f phải có cực đại trên D. Định lí 1.3. (Định lý Karush - Kuhn - Tucker). Giả sử các hàm f, gi , h j (i = 1, . . . , m; j = 1, . . . , p) khả vi trên một tập mở chứa D, x∗ ∈ D là một điểm cực tiểu địa phương của bài toán ở trên và x∗ là điểm chính qui. Khi đó, tồn tại vectơ λ∗ = (λ1∗ , . . . , λ∗m )T , µ∗ = (µ1∗ , . . . , µ∗p )T thỏa mãn  p m  ∗ ∗ ∗   (1.1) ∇ f ( x ) + ∑ λi ∇ gi ( x ) + ∑ µ∗j ∇h j ( x∗ )   i =1 j =1  λi∗ gi ( x∗ ) = 0 và λi∗ > 0, i = 1, . . . , m (1.2)     gi ( x∗ ) 6 0, i = 1, . . . , m; h j ( x∗ ) = 0, j = 1, . . . , p (1.3) Chứng minh. Do x∗ là điểm cực tiểu địa phương nên theo điều kiện cần tối ưu cấp 1 ta có < ∇ f ( x∗ ), d > > 0 với mọi d ∈ TD ( x∗ ). Do x∗ là điểm chính qui (tức là TD ( x∗ ) = S( x∗ )) nên bất đẳng thức này đúng với mọi d ∈ S( x∗ ), nghĩa là với mọi d ∈ R n nghiệm đúng hệ phương trình trên với x∗ thay cho x0 . Áp dụng bổ đề Farkas cho ma trận A với ma trận chuyển vị AT có các cột là −∇ gi ( x∗ ), i ∈ I ( x∗ ), ∇h j ( x∗ ), −∇h j ( x∗ ) ( j = 1, . . . , p). 2 Ta tìm được các số thực λi∗ > 0(i ∈ I ( x∗ )), α j > 0, β j > 0( j = 1, . . . , p). sao cho ∗ ∇ f (x ) = − ∑ i∈T (x∗ ) λi∗ ∇ gi ( x∗ ) + p ∑ (α j − β j )∇h j (x∗ ). j =1 Bằng cách đặt λi∗ = 0 với mọi i ∈ / I ( x∗ ), µ∗j = β j − α j với mọi j = 1, . . . , p ta nhận được hai điều đầu tiên. Do x∗ ∈ D nên ta có điều cuối cùng. Nhận xét 1.1. a) Đối với bài toán (P) ta lập hàm số sau đây, gọi là hàm Lagrange tương ứng với (P) p m L( x, λ, µ) = f ( x) + ∑ λi gi ( x) + i =1 ∑ µ j h j ( x). j =1 (x ∈ R n , λi > 0 với mọi i và µ j tùy ý với mọi j). Khi đó điều kiện KKT được viết lại thành ∇x L( x, λ, µ) = 0, λT ∇λ L( x, λ, µ) = 0, ∇λ L( x, λ, µ) 6 0, ∇µ L( x, λ, µ) = 0, điều kiện (1.1) gọi là điều kiện dừng, bởi vì ∇x L( x, λ, µ) = 0; (1.2) là điều kiện bù và (1.3) là điều kiện chấp nhận được. b) Trường hợp tập D có thêm ràng buộc xk > 0 với k ∈ K ⊂ {1, . . . , n}, tức là D = { x ∈ R n : gi ( x) 6 0, i = 1, . . . , m; h j ( x) = 0, j = 1, . . . , p; xk > 0, k ∈ K}, thì điều kiện (1.1) đổi thành (các điều kiện (1.2), (1.3) không thay đổi) (1.1a) (1.1b) (1.1c) p m ∂h j ( x∗ ) ∂gi ( x∗ ) ∂ f (x∗ ) + ∑ λi + ∑ µj = 0 ∀k ∈ / K, ∂xk ∂xk ∂xk i =1 j =1 m ∂h j ( x∗ ) ∂gi ( x∗ ) ∂ f (x∗ ) + ∑ λi + ∑ µj > 0, xk∗ > 0 ∀k ∈ K, ∂xk ∂x ∂x k k i =1 j =1 p xk∗ [ p m ∂h j ( x∗ ) ∂g ( x∗ ) ∂ f (x∗ ) + ∑ λi i + ∑ µj ] = 0, ∀k ∈ K. ∂xk ∂x ∂x k k i =1 j =1 Ví dụ 1.1. a) Tìm điều kiện KKT cho bài toán sau (P) min{ f ( x) = − log x1 − log x2 : x1 + x2 − 2 6 0, x1 > 0, x2 > 0}. 3 tại điểm cực tiểu địa phương x∗ = ( x1∗ , x2∗ ) của (P). Trong ví dụ này g(x) = x1 + x2 − 2. Hàm Lagrange có dạng L( x, λ) = f ( x) + λg( x) = − log x1 − log x2 + λ( x1 + x2 − 2). Điều kiện KKT tại x∗ là   − 1 + λ > 0, − 1 + λ > 0, x (λ − 1 ) = 0, x2 (λ − 1 ) = 0 1 x1 x2 x1 x2  λ( x1 + x2 − 2) = 0, x1 + x2 − 2 6 0, x1 > 0, x2 > 0, λ > 0 Giải hệ trên ta được điểm KKT duy nhất là x∗ = (1, 1)T với λ∗ = 1. Đó chính là nghiệm cực tiểu của bài toán trên (Chú ý (P) là bài toán lồi). b) Một ví dụ khác. Kiểm tra điều kiện KKT đối với bài toán sau 3 1 min ( x1 − )2 + ( x2 − )4 , với các điều kiện x 2 2 g1 ( x) = x1 + x2 − 1 6 0, g2 ( x) = x1 − x2 − 1 6 0, g3 ( x) = − x1 + x2 − 1 6 0, g4 ( x) = − x1 − x2 − 1 6 0. Có thể thấy x∗ = (1, 0)T là điểm cực tiểu, I ( x∗ ) = {1, 2}. Ta có   " # " # −1 1 1 , ∇ g2 ( x ∗ ) = . ∇ f ( x ∗ ) =  1  , ∇ g1 ( x ∗ ) = 1 −1 − 2 Vì thế điều kiện KKT được thỏa mãn nếu đặt λ∗ = ( 43 , 41 , 0, 0)T . 1.2 Bài toán đối ngẫu Những kết quả thu được cho bài toán quy hoạch tuyến tính được khái quát cho bài toán quy hoạch phi tuyến. Xét bài toán gốc phi tuyến tổng quát min f ( x), với x (1) h( x) = 0, g( x) 6 0. 4 trong đó f : R n → R, h : R n → R l , g : R n → R m . Bài toán đối ngẫu đòi hỏi về hàm đối ngẫu được định nghĩa như sau Φ(λ, µ) = inf { f ( x) + λT h( x) + µT g( x)} . x trong đó λ∗ , µ∗ là những hệ số liên hợp với những ràng buộc (1) về nghiệm tối ưu x∗ của bài toán trên. Bài toán đối ngẫu của bài toán gốc trên được định nghĩa như sau max z D = Φ(λ, µ), µ > 0. λ,µ Sử dụng hàm Lagrange: L( x, λ, µ) = f ( x) + λT h( x) + µT g( x). Chúng ta có thể viết lại bài toán đối ngẫu như sau h i max inf L( x, λ, µ) . x λ,µ;µ>0 Định nghĩa 1.2. (Điều kiện đủ thứ hai). Giả sử f , h.g ∈ C2 . Những điều kiện sau là đủ để điểm x∗ thỏa mãn (1) trở thành cực tiểu tương đối ngặt của bài toán trên (a) Những ràng buộc ở định lý Karush - Kuhn - Tucker đáp ứng. (b) Ma trận Hessian L( x∗ ) = F( x∗ ) + λT H ( x∗ ) + µT G( x∗ ) là xác định dương trên không gian con n o y : ∇ H ( x∗ ) T y = 0, ∇ g j ( x∗ ) T y = 0; ∀ j ∈ J , trong đó J = { j: g j ( x∗ ) = 0, µ j > 0} . Định nghĩa 1.3. (Điều kiện cần thứ hai). Giả sử f , h.g ∈ C2 . Nếu x∗ là một điểm chính quy cực tiểu tương đối của bài toán trên, khi đó tồn tại những vectơ λ và µ ≥ 0 mà điều kiện (1.1) và µ j > 0 được đáp ứng và ma trận Hessian L( x∗ ) = F( x∗ ) + λT H ( x∗ ) + µT G( x∗ ) là xác định dương trên không gian tiếp xúc của những ràng buộc tại x∗ . Ví dụ 1.2. (Hàm đối ngẫu). Xét bài toán min z = x12 + x2 , với x1 ,x2 − x1 + 2x2 = 0, x1 x2 > 2. 5 Giải: Hàm Lagrange là L( x1 , x2 , λ, µ) = x12 + x2 + λ(− x1 + 2x2 ) + µ(− x1 x2 + 2), và điều kiện KKT trở thành ∂L( x1 , x2 , λ, µ) = 2x1 − λ − µx2 = 0, ∂x1 ∂L( x1 , x2 , λ, µ) = 1 + 2λ − µx1 = 0, ∂x2 − x1 + 2x2 = 0, − x1 x2 + 2 6 0, µ(− x1 x2 + 2) = 0, µ > 0. dẫn đến những nghiệm gốc và đối ngẫu là 9 7 z∗ = 5, x1∗ = 2, x2∗ = 1, λ∗ = , µ∗ = . 4 4 Để thu được bài toán đối ngẫu đầu tiên chúng ta tính toán hàm đối ngẫu h i Φ(λ, µ) = inf L( x, y, λ, µ) = inf x12 + x2 + λ(− x1 + 2x2 ) + µ(− x1 x2 + 2) . x1 ,x2 x1 ,x2 Và khi ∂L( x1 , x2 , λ, µ) = 2x1 − λ − µx2 = 0, ∂x1 ∂L( x1 , x2 , λ, µ) = 1 + 2λ − µx1 = 0. ∂x2 Dẫn đến x= 1 + 2λ 2 + 4λ − λµ ,y = . µ µ2 Hàm đối ngẫu trở thành (1 + 2λ)2 − λµ(1 + 2λ) + 2µ3 . Φ(λ, µ) = µ2 Và do đó bài toán đối ngẫu là (1 + 2λ)2 − λµ(1 + 2λ) + 2µ3 max Φ(λ, µ) = , với µ > 0. µ2 λ,µ 6 Cuối cùng, do 4λ(2 − µ) − µ + 4 ∂Φ(λ, µ) = = 0, ∂λ µ2 (1 + 2λ) [ λ(µ − 4) − 2] ∂Φ(λ, µ) =2+ = 0, ∂µ µ3 dẫn đến λ∗ = 74 , µ∗ = 49 , là nghiệm của bài toán đối ngẫu, và rõ ràng trùng khớp với nghiệm thu được từ điều kiện KKT ở trên. Định nghĩa 1.4. (Dưới gradient và dưới vi phân). Cho C là một tập lồi không âm trong R n và cho Φ : C → R là lồi. Khi đó, α được gọi là một dưới gradient của Φ(λ) tại e λ ∈ C nếu Φ(λ) > Φ(e λ ) + α T (λ − e λ ); ∀λ ∈ C. Tương tự vậy, cho Φ : C → R là lõm. Khi đó, α được gọi là một dưới gradient của e λ ∈ C nếu Φ(λ) 6 Φ(e λ ) + α T (λ − e λ ); ∀λ ∈ C. Tập tất cả các dưới gradient của Φ(λ) trong e λ là một tập lồi được biết như dưới vi phân của Φ(λ) tại e λ. Định lí 1.4. (Đối ngẫu yếu). Đối với bất kỳ nghiệm khả thi x của bài toán gốc và bất kỳ nghiệm khả thi λ, µ của bài toán đối ngẫu, ta luôn có f ( x) > φ(λ, µ). Định nghĩa 1.5. (Độ lệch đối ngẫu). Hiệu số giữa sup{Φ(λ, µ)| µ > 0} − inf{ f ( x)| h( x) = 0, g( x) 6 0}, được gọi là độ lệch đối ngẫu của bài toán đối ngẫu và bài toán gốc. Ví dụ 1.3. Xét bài toán sau đây min −2x1 + x2 , với x1 ,x2 5 x1 + x2 = , ( x1 , x2 ) ∈ X. 2 Trong đó X = { (0,0), (0,2), (2,0), (2,2), ( 45 , 45 )} . 7 Hàm đối ngẫu của nó được cho bởi  3λ   −2 + nếu λ 6 1,   2   λ Φ(λ) = −4 − nếu − 1 6 λ 6 2,  2    5λ  − nếu λ > 2, 2 biểu diễn trong hình vẽ. Nghiệm tối ưu của bài toán đối ngẫu là λ∗ = −1 với giá trị hàm mục tiêu Φ(λ∗ ) = − 72 . Dễ dàng để thấy rằng x1∗ = 45 và x2∗ = 45 là nghiệm tối ưu của bài toán gốc với một giá trị hàm mục tiêu bằng f ( x∗ ) = − 45 . Do đó, hiệu số f ( x∗ ) − Φ(λ∗ ) = − 54 + 27 = 49 là độ lệch đối ngẫu được biểu diễn trong hình vẽ. Hình 1.1: Đồ thị minh họa độ lệch đối ngẫu trong ví dụ minh họa 1.3. Bây giờ để hiểu được về sự phân rã trong bài toán tối ưu ta xét ví dụ sau Ví dụ 1.4. (Tính toán lưu vực sông). Xét một lưu vực sông bao gồm hai hồ chứa như minh họa trong hình vẽ. Mỗi hồ chứa đã kết hợp một nhà máy thủy điện sản xuất điện. Các dòng vào tự nhiên tới hồ 1 và 2 trong suốt khoảng 8 Hình 1.2: minh họa của ví dụ tính toán lưu vực sông. thời gian t được định nghĩa tương ứng bằng wt1 và wt2 . Dung lượng nước của hồ 1 và 2 tại thời điểm cuối của chu kỳ t được định nghĩa tương ứng bởi rt1 và rt2 . Nước xả ra trong suốt khoảng thời gian t bởi hồ 1 và 2 tương ứng là dt1 và dt2 . Các dung lượng được giới hạn trên và dưới tương ứng bởi những hằng số r1max, r1min , r2max , r2min . Tương tự, thể tích nước xả được giới hạn trên max bởi dmax 1 , d2 . Giả sử rằng nước tháo ra trong hồ 1 đến ngay lập tức hồ 2, đó là giả định hợp lý nếu các hồ không quá xa nhau. Tổng số năng lượng sản xuất bởi nhà máy điện 1 và 2 trong suốt khoảng thời gian t là tỷ lệ thuận tương ứng với sự xả nước trong khoảng thời gian t đó. Hằng số tỷ lệ cho nhà máy 1 và 2 là k 1 và k 2 . Hệ thống sông được vận hành để cung cấp cho nhu cầu điện năng của địa phương trong mỗi khoảng thời gian, et . Nếu năng lượng bổ sung có thể được sản xuất trong suốt thời gian t, nó được bán với giá thị trường λt , với mục tiêu tối đa hóa lợi nhuận. Xét một thời gian là 2h và giả sử rằng dung lượng hồ tại lúc bắt đầu của tầng thời gian là r01 và r02 , tương ứng cho hồ 1 và 2. Bài toán tối đa hóa lợi nhuận là max r11 ,r12 ,r21 ,r22 ,d11 ,d12 ,d21 ,d22 λ1 (k 1 d11 + k 2 d12 − e1 ) + λ2 (k 1 d21 + k 2 d22 − e2 ). 9 Với những ràng buộc cân bằng nước r11 = r01 + w11 − d11 , r21 = r11 + w21 − d21 , r12 = r02 + w12 − d12 + d11 , r22 = r12 + w22 − d22 + d21 , r21 + r22 = r01 + r02 + w11 + w21 + w12 + w22 − d12 − d22 . Trong đó ràng buộc cuối cùng là ràng buộc rườm rà mà nó thuận tiện để kết hợp bởi vì nó diển tả một dạng ma trận thích hợp của bài toán; những ràng buộc yêu cầu k 1 d11 + k 2 d12 > e1 , k 1 d21 + k 2 d22 > e2 . Những giới hạn cấp độ hồ r1min 6 r11 , r21 6 r1max ; r2min 6 r12 , r22 6 r2max. Và những giới hạn cho phép xả max 0 6 d11 , d21 6 dmax 1 ; 0 6 d12 , d22 6 d2 . Phân loại những biến theo thứ tự r11 , r21 , r12 , r22 , d11 , d21 , d12 , d22 , ma trận tương ứng với các ràng buộc mà không phải giới hạn là: Cấu trúc của ma trận này cho thấy một cấu trúc có thể khai thác. Nếu hai ràng buộc cuối cùng được giảm đi, ma trận còn lại có một cấu trúc mạng cho phép sử dụng các thuật toán giải hiệu quả cao. Ma trận này bao gồm trong mỗi cột chỉ có một 1 và -1. Tuy nhiên, hai ràng buộc cuối cùng ngăn chặn việc sử dụng một thuật toán hiệu quả trừ khi một cơ chế phân rã thích hợp được sử dụng như thuật toán phân rã Dantzig-Wolfe. Kỹ thuật phân rã được giải thích trong chương tiếp theo. 10 Trong thực tế, số lượng thiết bị sản xuất có thể cao như 100, và việc xây dựng khía cạnh của bài toán chi phí sản xuất năng lượng tối thiểu, không có ràng buộc tuyến tính bổ sung, yêu cầu 2100 − 1 ràng buộc, một con số có thể ngăn chặn thậm chí viết ra bài toán. Tuy nhiên, nghiệm của nó là tầm thường bằng cách sử dụng quy tắc trật tự. Tuy nhiên, nếu ràng buộc tuyến tính thêm được bao gồm, kết quả bài toán sẽ trở nên không viết được và nan giải, trừ khi một kỹ thuật phân rã được sử dụng để giảm bớt những ràng buộc phức tạp. Kỹ thuật phân rã được giải thích trong chương tiếp theo. 11 Chương 2 Phân rã trong quy hoạch tuyến tính 2.1 Những ràng buộc phức tạp Kích thước của một bài toán quy hoạch tuyến tính có thể rất lớn. Người ta có thể gặp phải trong thực tế những bài toán với hàng trăm hàng ngàn phương trình hoặc ẩn số. Để giải quyết những bài toán này phải sử dụng một số kỹ thuật đặc biệt cho thuận tiện và cần thiết. Ngoài ra, một giải pháp phân phối của các bài toán lớn có thể được mong muốn vì lý do kỹ thuật hoặc thực tế. Kỹ thuật phân rã cho phép loại nhất định của các bài toán được giải quyết một cách phân cấp hoặc phân phối. Ngoài ra, chúng dẫn đến sự đơn giản hóa thủ tục nghiệm của bài toán được nghiên cứu. Đối với một kỹ thuật phân rã có ích , bài toán ở đây phải có cấu trúc thích hợp. Hai trường hợp như vậy xảy ra trong thực tế: các ràng buộc phức tạp và cấu trúc biến phức tạp. Hai trường hợp này được xem xét trong chương này. Trong một bài toán quy hoạch tuyến tính, các ràng buộc phức tạp liên quan đến các biến từ các khối khác nhau rõ ràng, ràng buộc phức tạp cản trở một nghiệm của bài toán bằng các khối. 12 2.1.1 Cấu trúc bài toán Xét bài toán quy hoạch tuyến tính n (2.1) min x1 ,x2 ,...,xn ∑ c j x j , với j =1 n (2.2) ∑ eij x j = fi ; i = 1, . . . , q, j =1 n (2.3) ∑ aij x j = bi ; i = 1, . . . , m, j =1 up (2.4) 0 6 x j 6 x j ; j = 1, . . . , n. Trong đó những ràng buộc (2.2) có một cấu trúc phân rã trong r khối, mỗi khối có kích cỡ là nk (k = 1, . . . , r ), tức là chúng có thể được viết như sau nk ∑ j = n k − 1 +1 eij x j = f i ; i = qk−1 + 1, . . . , qk . Chú ý rằng n0 = q0 = 0, qr = q và nr = n. Mặt khác, khi những ràng buộc (2.3) không có cấu trúc phân rã, chúng là những ràng buộc phức tạp. up Chú ý rằng những cận trên x j ( j = 1, . . . , n) được xem xét cho tất cả các biến tối ưu x j ( j = 1, . . . , n). Giả định này cho phép làm việc với một miền khả thi compact (hữu hạn), dẫn đến một phân tích lý thuyết đơn giản của bài toán (2.1) - (2.4). Giả định này là hợp lý bởi tính chất bị chặn của hầu hết biến kỹ thuật. Hình 2.1 cho thấy cấu trúc của bài toán nêu trên đối với trường hợp r = 3. 13 Cụ thể bài toán này có thể được viết như sau min x [1] ,x [2] ,x [3]   [1 ]  x  T  T  T    [2 ]  [1 ] [ 2] [3 ] c | c | c x .   [3 ] x Trong đó những chỉ số trong ngoặc đề cập đến những phân vùng, với     [ 1] f E [1 ] | |  −−−−−−−−−−−−−   [1]   −−   x      −−   [2]   [ 2] f | E |       −−−−−−−−−−−−−    [ 2]  =  −−   .   x−−     3 [ ] [ 3 ]  f     | | E  −−−−−−−−−−−−−  x[3]  −−      A [ 1] | A [ 2] | A [ 3] b Trong trường hợp tổng quát bài toán ban đầu có thể được viết như sau Hình 2.1: ma trận phân rã với những ràng buộc phức tạp r min x [1] ,x [2] ,...,x [r ] ∑ k =1  c 14 [ k] T x[k] , với