Mục lục trang Mở đầu Chương Kiến thức chuẩn bị 1.1 Một số vấn đề lý thuyết xác suất 1.2 Bài toán quy hoạch tuyến tính (QHTT) nguyên ngẫu nhiên 1.3 Phương pháp cắt giải toán QHTT nguyên 13 1.4 Phương pháp nhánh cận giải toán QHTT nguyên 14 Chương Tiếp cận phương pháp nhánh cắt giải toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn 17 2.1 Bài toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn 17 2.2 Cây phân nhánh 19 2.3 Bài toán "chiếc túi" ngẫu nhiên 25 2.4 Về việc phân nhánh cắt 36 Kết luận 40 Tài liệu tham khảo 41 Mở đầu Một phương pháp hiệu giải toán quy hoạch phương pháp cắt Trong toán quy hoạch tuyến tính ngun tất định, người có ý tưởng đề xuất lược đồ cắt, Dangtzig, Fulkerson, Johnson Nhưng Gomory người thành công việc xây dựng lát cắt để đảm bảo thuật toán hữu hạn (mà thường gọi nhát cắt Gomory 1, nhát cắt Gomory 2) Tiếp theo, nhiều nhà khoa học khác đề xuất nhát cắt khác Chẳng hạn [4] kết "thuật toán cắt tọa độ" giải tốn quy hoạch rời rạc có hiệu Bài toán quy hoạch nguyên với tham gia yếu tố ngẫu nhiên gọi toán quy hoạch nguyên ngẫu nhiên Trong toán quy hoạch nguyên ngẫu nhiên, người ta chia ra: lớp quy hoạch nguyên ngẫu nhiên giai đoạn, lớp quy hoạch nguyên ngẫu nhiên hai giai đoạn lớp quy hoạch nguyên ngẫu nhiên nhiều giai đoạn Các hướng tiếp cận nhằm tìm lời giải cho lớp tốn quy hoạch nguyên ngẫu nhiên nhà khoa học giới quan tâm Cũng quy hoạch tuyến tính nguyên, nhà khoa học tìm cách sử dụng lược đồ cắt xây dựng lát cắt có hiệu việc giải toán quy hoạch ngẫu nhiên (chẳng hạn: Yongpei Guan, Shabbir Ahmed, Z.L Chen, F Louveaux, G Infanger, D.P Morton ) Bài toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn có nhiều ứng dụng thực tiễn Vì vậy, việc nghiên cứu nhằm tìm thuật tốn giải toán quy hoạch ngẫu nhiên nhiều giai đoạn có ý nghĩa khoa học ý nghĩa thực tiễn rộng lớn Với lý vậy, lựa chọn đề tài: Một phương pháp tiếp cận giải toán quy hoạch ngẫu nhiên nguyên nhiều giai đoạn" Tài liệu tham khảo báo Cutting planes for multi-stage stochastic integer programs, tác giả Yongpei Guan, Shabbir Ahmed and George L Nemhauser, thuộc trường Đại học Kỹ thuật Atlanta, công bố năm 2006 (xem [5]) Nội dung luận văn bao gồm hai chương: Chương 1: Kiến thức chuẩn bị Trong chương chúng tơi trình bày số khái niệm thuộc lý thuyết xác suất - thống kê; vấn đề lý thuyết quy hoạch tuyến tính ngun tốn quy hoạch tuyến tính nguyên ngẫu nhiên nhiều giai đoạn; Đồng thời để làm công cụ nghiên cứu cho đề tài nêu số vấn đề lược đồ cắt kỹ thuật phân nhánh Chương 2: Tiếp cận phương pháp nhánh cắt giải toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn Đây nội dung luận văn Trong chương này, chúng tơi trình bày lớp toán cần nghiên cứu với kiến thức liên quan Tiếp đó, chúng tơi trình bày mơ hình đặc trưng tốn quy hoạch ngun ngẫu nhiên, tốn "chiếc túi" ngẫu nhiên Cuối phân tích việc phân nhánh cắt mà nội dung trước bàn tới Luận văn thực hoàn thành Trường Đại học Vinh hướng dẫn thầy giáo PGS.TS Trần Xuân Sinh Tác giả xin tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn tận tâm thầy tác giả suốt thời gian học tập nghiên cứu Cũng này, tác giả xin gửi lời cảm ơn thầy giáo, cô giáo Bộ môn Xác suất Thống kê Tốn ứng dụng, thầy giáo Hội đồng chấm luận văn, khoa Toán, khoa Sau Đại học Trường Đại học Vinh Đồng thời, tác giả xin bày tỏ lòng biết ơn giúp đỡ, tạo điều kiện cho học tập, công tác Trường THPT Lê Hồng Phong Cũng này, cho phép tơi nói lời cảm ơn tới gia đình bạn bè, quan tâm, góp ý tạo điều kiện giúp đỡ thực luận văn Mặc dù cố gắng song luận văn không tránh khỏi sai sót Tác giả mong nhận ý kiến đóng góp q thầy giáo bạn để luận văn hoàn thiện Tác giả xin chân thành cảm ơn! Vinh, tháng 12 năm 2011 Tác giả Chương Kiến thức chuẩn bị 1.1 Một số vấn đề lý thuyết xác xuất 1.1.1 Các định nghĩa 1.1.1.1 σ- đại số Giả sử Ω tập tuỳ ý khác rỗng Ký hiệu P(Ω) tập hợp gồm tất tập Ω Lớp A ⊂ P(Ω) gọi đại số nếu: A1) Ω ∈ A, A2) A ∈ A ⇒ A = (Ω \ A) ∈ A, A3) A, B ∈ A ⇒ A ∪ B ∈ A (hoặc A ∩ B ∈ A) Lớp F ⊂ P(Ω) gọi σ -đại số đại số ngồi có A4) Nếu An ∈ F, ∀n = 1, 2, ∞ n=1 An ∈ F (hoặc ∞ n=1 An ∈ F) 1.1.1.2 Không gian đo độ đo xác suất Cặp (Ω, F) gọi không gian đo, Ω tập khác rỗng, F σ - đại số tập Ω Giả sử (Ω, F) không gian đo Một ánh xạ P : F −→ R gọi độ đo xác suất F nếu: A1) P(A) ≥ 0, với A ∈ F A2) P(Ω) = A3) Nếu An ∈ F, ∀n = 1, 2, , Ai ∩ Aj = ∅, i = j ∞ ∞ An = P n=1 P(An ) n=1 1.1.1.3 Không gian xác suất Giả sử Ω tập khác rỗng, F σ - đại số tập Ω, P độ đo xác suất F Khi ba (Ω, F, P) gọi không gian xác suất Tập Ω gọi không gian biến cố sơ cấp σ - đại số F gọi σ - đại số biến cố Mỗi A ∈ F gọi biến cố Không gian xác suất (Ω, F, P) gọi không gian xác suất đầy đủ tập biến cố có xác suất khơng biến cố 1.1.1.4 Đại lượng ngẫu nhiên Giả sử (Ω, F, P) không gian xác suất; G σ- đại số σ- đại số F; B σ- đại số Borel R Khi ánh xạ X : Ω −→ R gọi đại lượng ngẫu nhiên G-đo được, với B ∈ B, ta có X −1 (B) := {ω : X(ω) ∈ B} ∈ G Khi X đại lượng ngẫu nhiên F-đo X gọi đơn giản đại lượng ngẫu nhiên 1.1.1.5 Kỳ vọng đại lượng ngẫu nhiên Giả sử X : (Ω, F, P) → (R, B) đại lượng ngẫu nhiên Khi tích phân Lebesgue X theo độ đo P (nếu tốn tại) gọi kỳ vọng X, ký hiệu EX Vậy EX = XdP Ω 1.1.1.6 Phương sai đại lượng ngẫu nhiên Giả sử X đại lượng ngẫu nhiên Khi số DX = E(X − EX)2 (nếu tồn tại) gọi phương sai X 1.1.2 Các tính chất 1.1.2.1 Tính chất kỳ vọng Giả sử X, Y, ξ đại lượng ngẫu nhiên xác định không gian xác suất (Ω, F, P), a ∈ R, α ∈ E Khi tồn EX, EY, Eξ thì: a) Tồn E(X + Y ) E(X + Y ) = EX + EY b) Tồn E(aX) E(aX) = aEX c) Tồn E(αξ) E(αξ) = αEξ d) Nếu P(X = a) = EX = a e) Nếu ξ X độc lập E(ξX) = Eξ.EX f) Với ánh xạ tuyến tính T : E −→ E (E khơng gian Banach khả li) tồn E[T (X)] E[T (X)] = T [E(X)] 1.1.2.2 Tính chất phương sai Giả sử X phần tử ngẫu nhiên, ξ đại lượng ngẫu nhiên xác định không gian xác suất (Ω, F, P), a ∈ R, α ∈ E Khi a) D(aX) = a2 DX b) D(αξ) = α Dξ c) DX = ⇐⇒ X = EX (h.c.c) 1.2 Bài toán quy hoạch tuyến tính nguyên ngẫu nhiên 1.2.1 Các khái niệm Bài tốn quy hoạch tuyến tính rời rạc có dạng n min(max) f (x) = cj xj (1.1) j=1 với điều kiện       n j=1 aij xj ( , ≥, =) bi , i = 1, 2, , m xj ≥ 0, j = 1, 2, , n      x ∈ D = {dj , dj , , dj }, j ∈ {1, 2, , n}, j j kj dji ∈ R, k phụ thuộc xj Khi Dj tập số ngun ta có tốn quy hoạch tuyến tính nguyên Tập hợp điểm nguyên tập D hữu hạn vô hạn Các tọa độ nằm đoạn thẳng, đường thẳng hay rời rạc dạng liệt kê Bài toán quy hoạch tuyến tính ngun tổng qt có dạng n min(max) f (x) = cj xj (1.2) j=1 với điều kiện       n j=1 aij xj ( , ≥, =) bi , i = 1, 2, , m xj ≥ 0, j = 1, 2, , n      x ∈ Z, j ∈ {1, 2, , n} j Nếu xj ∈ Z, j = 1, 2, , n ta có tốn quy hoạch ngun tồn phần Trong trường hợp ngược lại, ta có tốn quy hoạch ngun hỗn hợp Để đơn giản, xét toán quy hoạch nguyên toàn phần dạng n cj xj f (x) = (1.3) j=1 với điều kiện       n j=1 aij xj = bi , i = 1, 2, , m xj ≥ 0, j = 1, 2, , n      x ∈ Z, j ∈ {1, 2, , n} j Hàm f (x) gọi hàm mục tiêu Các điều kiện toán gọi điều kiện buộc Điểm x = (xj ) ∈ Z thoả mãn điều kiện toán gọi phương án Phương án x đạt cực tiểu hàm mục tiêu gọi phương án tối ưu (hoặc nghiệm) toán 1.2.2 Tính chất tốn Bài tốn quy hoạch tuyến tính có tính chất quan trọng sau: + Nếu tốn quy hoạch tuyến tính có phương án tối ưu tồn phương án cực biên (đỉnh) tối ưu + Tập phương án toán quy hoạch tuyến tính tập lồi đa diện có hữu hạn điểm cực biên + Phương án x = (xj ) cực biên tương ứng với xj > 0, (xj ∈ Z) hệ vectơ cột aj ma trận A = (aij ) độc lập tuyến tính, aj = (a1j , a2j , , amj ) + Mọi tốn quy hoạch tuyến tính rời rạc chuyển tốn quy hoạch tuyến tính ngun Phương pháp chuyển tốn quy hoạch tuyến tính rời rạc tốn quy hoạch tuyến tính nguyên thực sau: * Nếu giá trị dji cách ta cần thay đổi đơn vi đo, đổi biến ta có giá trị nguyên tương ứng * Nếu giá trị dji cách khơng ta thay biến xj biến xij sau kj kj xij dji , xj = i=1 xij = 1, xij ∈ {0, 1} i=1 1.2.3 Bài tốn quy hoạch tuyến tính ngun ngẫu nhiên Bài tốn quy hoạch tuyến tính ngun liệu phụ thuộc biến ngẫu nhiên gọi Bài tốn quy hoạch tuyến tính ngun ngẫu nhiên Để phân loại toán quy hoạch ngẫu nhiên, người ta dựa vào trình thực điều chỉnh phương án có tác động biến ngẫu nhiên vào liệu Cụ thể: + là: Phương án - quan sát - phương án - - quan sát - phương án, + là: Quan sát - phương án - quan sát - - quan sát - phương án Số lần lặp lại điều chỉnh "phương án" trình nêu coi số giai đoạn Từ cho ta lớp tốn quy hoạch tuyến tính ngẫu nhiên "một giai đoạn", "hai giai đoạn (Two-Stage Stochastic Linear 10 Progamming - (2SSLP ))", , "nhiều giai đoạn (Multistage Stochastic Linear Programs)" Chi tiết mơ hình tốn quy hoạch tuyến tính ngẫu nhiên hai giai đoạn xét tới sau: Chúng ta tiếp cận với tốn có điều kiện ràng buộc phụ thuộc vào biến ngẫu nhiên Cụ thể ta xét toán (SLP ) cT x : Ax = b, T x = h, x ≥ , c ma trận cấp n × 1; x ma trận cấp n × 1; b ma trận hệ số cấp m × 1; A ma trận hệ số cấp m × n; h ma trận cấp p × T ma trận cấp p × n, phần tử ma trận h T biến ngẫu nhiên có phân phối xác suất biết Giả sử h hoàn tồn chưa biết, biết hàm phân phối nó, với kỳ vọng hữu hạn Eh Rõ ràng xác định x từ phương trình T x = h Sự khác T x h biến ngẫu nhiên có hàm phân phối phụ thuộc vào x Ta phải "trả giá" cho phụ thuộc Do vậy, toán ta định làm cực tiểu hàm cT x cần có mức phạt cho khác phải trả giá Kỹ thuật hai bước nhằm chuyển tốn (SLP) toán tất định theo giá trị kỳ vọng tương ứng Q trình giải tốn (SLP) gồm hai bước: Bước thứ nhất: Chọn vectơ x không âm thoả mãn điều kiện định biết Bước thứ hai: Chúng ta bổ sung độ lệch T x h ma trận bổ sung W biến phạt y thoả mãn W y = h − T x Do thông tin không đầy đủ, ta đặt d vectơ phạt tìm giá trị nhỏ 27 (i) Vectơ u0 ứng với biến x cho eyr u0 = bQ ex + r∈V\VΩ (ii) Vectơ uj ứng với yj , j ∈ VΩ cho uj = bρ(j)−1 ex + eyr + r∈Λ(j) eyr r∈V\VΩ (iii) Vectơ uj ứng với yj , j ∈ V\VΩ cho uj = us(j) − ej Ta cần {uj }nj=0 thỏa mãn (2.13) với i ∈ V Thật vậy: (i) Ta thấy vectơ u0 thỏa mãn (2.13) với i ∈ VΩ từ vế trái (2.13) bQ ≥ bi , với i ∈ V Với i ∈ V\VΩ , đặt ξ(i) = argmax{bk : k ∈ P(i) ∩ Ω} vế trái (2.13) ak ≥ b i , ak ≥ bξ(i) + bQ + k∈P(i)\P(ξ(i)) k∈P(i)\P(ξ(i)) có bất đẳng thức đầu bQ ≥ bξ(i) nên ξ(i) ∈ Ω bất đẳng thức thứ hai có từ điều kiện (2) Định lý (2.3.2.1.) (ii) Do giá trị vế trái lớn bρ(j)−1 ≥ bi với i ∈ Ψ(j) nên vectơ uj , j ∈ VΩ thỏa mãn (2.13) với i ∈ Ψ(j) Với i ∈ VΩ \Ψ(j) đặt λ(i) = {k : k ∈ P(i) ∩ Λ(j)} theo điều kiện (1) Định lý (2.3.2.1.) vế trái (2.13) bρ(j)−1 + aλ(i) ≥ bi Với i ∈ V\VΩ , tồn λ(i) vế trái bất đẳng thức 28 (2.13) aj yj ≥ bρ(j)−1 + aλ(i) + x+ j∈P(i) ak k∈P(i)\P(ξ(i)) ≥ bξ(i) + ak k∈P(i)\P(ξ(i)) ≥ bi , bất đẳng thức thứ hai có từ điều kiện (1) bất đẳng thức cuối có từ điều kiện (2) Định lý (2.3.2.1.) Lập luận tương tự, ta kết trường hợp không tồn λ(i) (iii) Vectơ uj thỏa mãn (2.13) với i ∈ VΩ s(j) ∈ VΩ j ∈ V\VΩ Mặt khác, uj thỏa (2.13) với i ∈ V\VΩ (do điều kiện (3) định lý (2.3.2.1.)) Vậy {uj }nj=0 thỏa mãn (2.13) với i ∈ V Tiếp theo, cần chứng tỏ {uj }nj=0 thỏa mãn điều kiện (2.15) Thật (i) Trong trường hợp ta kiểm tra u0 thỏa mãn điều kiện (2.15) (ii) Với j ∈ VΩ vectơ uj thỏa mãn điều kiện (2.15) vế trái (2.15) x+ φj (Ω)yj = bρ(j)−1 + j∈VΩ φr (Ω) r∈Λ(j) (bi − bi−1 ) = bρ(j)−1 + r∈Λ(j) i∈Ω(r) = bQ đẳng thức thứ hai suy từ ar ≥ i∈Ω(r) (bi − bi−1 ), với r ∈ Λ(j) Điều r ∈ Λ(j) ⊆ VQ , dựa vào điều kiện (i) ta có ar ≥ max{bi , i ∈ Ω(r)} ≥ i∈Ω(r) (bi − bi−1 ), ∀r ∈ Λ(j) nên ar ≥ 29 i∈Ω(r) (bi − bi−1 ), ∀r ∈ Λ(j) Đẳng thức cuối suy Ω(r1 ) ∩ Ω(r2 ) = ∅ r1 , r2 ∈ Λ(j) k ∈ ∪r∈Λ(j) Ω(r) cho bk ≥ bj với k ∈ Ω (iii) Với j ∈ V\VΩ us(j) thỏa mãn điều kiện (2.15) dựa vào điều kiện (ii) uj = us(j) − ej nên uj thỏa mãn điều kiện (2.15) với j ∈ V\VΩ Cuối ta cần tính độc lập hệ vectơ {uj }nj=0 Để chứng minh n + vectơ {uj }nj=0 độc lập tuyến tính, trước tiên ta thấy thu |V\VΩ | vectơ đơn vị cách đặt eyj = uj − us(j) , ∀j ∈ V\VΩ Hơn nữa, với j ∈ VΩ ∪ {0}, đặt v j = uj − eyr r∈V\VΩ từ ta lập ma trận vectơ |VΩ | dịng ma trận vectơ ứng với i đặt vectơ ứng với j max{bk : k ∈ VΩ (i)} > max{bk : k ∈ VΩ (j)} min{bk : k ∈ VΩ (i)} > min{bk : k ∈ VΩ (j)} max{bk : k ∈ VΩ (i)} = max{bk : k ∈ VΩ (j)} Mỗi cột ứng với đỉnh VΩ Cột thứ i đặt trước cột thứ j max{bk : k ∈ VΩ (i)} > max{bk : k ∈ VΩ (j)} min{bk : k ∈ VΩ (i)} > min{bk : k ∈ VΩ (j)} max{bk : k ∈ VΩ (i)} = max{bk : k ∈ VΩ (j)} Từ xác định Λ(j) trình lập uj , ta thấy vectơ làm thành ma trận tam giác yếu Do vậy, tất n + vectơ độc lập tuyến tính Định lý chứng minh xong 2.3.2.2 Định lý Nếu aj ≥ max{bk , k ∈ V(j)} với j ∈ V họ bất đẳng thức (2.15) ứng với Ω ⊆ V mà 0 yj x bV với j ∈ V mô tả bao lồi tập XSDK Chứng minh Chúng ta ý aj ≥ max{bk , k ∈ V(j)} bất đẳng thức (2.15) xác định có nghĩa dựa vào Định lý (2.3.2.1.) đồng 30 thời φj (Ω) = i∈Ω(j) (bi − bi−1 ) với j ∈ VΩ Chúng ta thấy bất đẳng thức (2.13) mạnh bất đẳng thức (2.15) Như ta cần không tồn mảnh cắt sau thêm vào bất đẳng thức (2.15) để có tập XSDK Từ đó, ta mâu thuẫn giả thiết u0 = {x0 , y10 , , yn0 } điểm vô chứa phần tử phân đoạn Trước tiên, ta giả sử (2.15) không tồn bất đẳng thức mà u0 thỏa mãn điều kiện Khơng tính tổng qt, giả sử thành phần thứ j u0 mảnh cắt, tồn hai điểm u1 = u0 + eyj u2 = u0 − eyj điểm vô tập XSDK Điều mâu thuẫn với giả thiết u0 điểm vô cùng, u0 = (u1 + u2 )/2 Trường hợp có bất đẳng thức mà u0 thỏa mãn điều kiện (2.15), ta định nghĩa Φ tập điểm ứng với vế phải bất đẳng thức Khi Φ = {j ∈ V : x0 + k ∈ VR φk (Ω)yk0 = bj , với Ω ⊆ V} Đặt α∗ = argmin{bj , j ∈ Φ} Ωj tập cho x0 + φk (Ωj )yk0 = bj k∈VΩj với j ∈ Φ Ta chứng minh trường hợp sau: Trường hợp α ∈ Ωj với j ∈ Φ Thật vây, giả sử không tồn đỉnh β ∈ Φ mà Ωβ ∩ Φ = β j ∈ / Φ với j ∈ P(β )\β Khơng tính tổng qt, đặt Ωα = (α1 , α2 , , αk1 , α ) Ωβ = (β , β , , β k2 , β ), ta có x0 + φk (Γ)yk0 > bk2 , k∈VΓ (2.16) 31 Γ = {β , β , , β k2 } x0 + φk (Ωβ )yk0 = bβ (2.17) k∈VΩβ Khi φk (Ωβ )yk0 bβ = x + k∈Vβ φk (Γ)yk0 + (bβ − bk2 ) = x0 + k∈VΓ yk0 k∈P(β ) yk0 , > bk2 + (bβ − bk2 ) k∈P(β ) có đẳng thức đầu từ (2.17) đẳng thức cuối có từ (2.16) Do ta có yk0 < (2.18) k∈P(β ) Xét bất đẳng thức ứng với tập Θ = {α1 , α2 , , αk1 , α , β }, ta có x0 + φk (Θ)yk0 = x0 + k∈VΘ φk (Ωα )yk0 + (bβ − bα ) k∈VΩα yk0 k∈P(β ) yk0 = bα + (bβ − bα ) k∈P(β ) < bβ , có bất đẳng thức từ (2.18) Điều mâu thuẫn với giả thiết x0 + k∈VΘ φk (Θ)yk0 ≥ bβ bất đẳng thức có nghĩa Do vậy, ta có kết α ∈ Ω với j ∈ Φ Trường hợp yk0 = k∈P(j) với j ∈ Φ\{α } (2.19) 32 Thật vậy, với j ∈ V mà bj ≥ bα α ∈ Φ bất đẳng thức ứng với tập Ωj = Ωα ∪ {j} φk (Ωα )yk0 + (bj − bα ) φk (Ωj )yk0 = x0 + x0 + k∈VΩα k∈VΩj yk0 ≥ bj k∈P(j) Do yk0 ≥ (2.20) k∈P(j) với j ∈ V\{α } cho bj ≥ bα Mặt khác, với j ∈ Φ với tập Ωj = {α1 , , αr , j}, ta có bj = x + φk (Ωj )yk0 k∈VΩj = x0 + yk0 φk (Ωj \{j})yk0 + (bj − bαr ) k∈VΩj \{j} k∈P(j) yk0 ≥ bαr + (bj − bαr ) k∈P(j) Khi yk0 ≥ 1, (2.21) k∈P(j) với j ∈ Φ Kết hợp (2.20), (2.21) ta k∈P(j) yk = với j ∈ Φ\{α } Trường hợp Nếu tồn j ∈ Φ mà α ∈ P(j), r ∈ Φ với r ∈ P(j)\P(α ) Thật vậy, từ j ∈ Φ, theo kết (2.19) k∈P(j) yk r ∈ P(j)\P(α ) giả sử Ωr = Ωα ∪ {r}, ta có br = x0 + φk (Ωr )yk0 k∈VΩr = Khi với 33 yk0 = bα + (br − bα ) k∈P(r) yk0 bα + (br − bα ) k∈P(j) = br (có bất đẳng thức từ r ∈ P(j) đẳng thức cuối Bất đẳng thức cho ta k∈P(r) yk = k∈P(j) yk k∈P(j) yk = 1) = với r ∈ P(j)\P(α ) Vì vậy, r ∈ Φ với r ∈ P(j)\P(α ), P(j)∩C(α ) ∈ Φ nên j ∈ Φ từ (2.19) ta có yk0 = với k ∈ P(j)\P(α ) ∪ C(α ) Tương tự, với đôi (i, j) ∈ Φ mà i ∈ P(j) i = α , ta có k∈P(j) yk 1, (2.22) k∈P(i) yk = = 1, từ (2.19) yk0 = với k ∈ P(j)\P(i) (2.23) Từ kết trên, tiếp đến không tồn mảnh cắt điểm dựa vào trường hợp sau: a) x0 = Khi x0 = x0 + d1 y10 = d1 y10 d1 Mặt khác với y10 = α = nên từ (2.19) ta có yk0 = với k ∈ VΦ \{α }, VΦ = ∪j∈Φ P(j) Nếu tồn k ∈ V\VΦ mà < yk0 < có hai điểm u1 = u0 + εeyk u2 = u0 − εeyk điểm vô tập XSDK Điều mâu thuẫn với giả thiết u0 điểm vô cùng, u0 = (u1 + u2 )/2 b) x0 = α = Theo (2.22) ta có yk0 = với k ∈ VΦ \C(1) Nếu có giải pháp phân đoạn < y10 < y10 + yj0 = với j ∈ V(1) ∩ VΦ Vậy yj0 = yk0 với đơi (j, k) ∈ C(1) ∩ VΦ Khi đó, bất đẳng thức có nghĩa 34 (2.15) có giá trị vế phải b , ∈ C(1) ∩ VΦ tương đương với x0 + b y10 + (b − b1 )y = b Thế tồn hai điểm vô phân biệt u1 = u0 +εb1 ex − εey1 + k∈C(1)∩VΦ εeyk u2 = u0 − εb1 ex +εey1 − k∈C(1)∩VΦ εeyk thuộc tập XSDK Điều mâu thuẫn với giả thiết u0 điểm vô cùng, u0 = (u1 + u2 )/2 c) x0 = α = Đặt Φ1 tập đỉnh thuộc Φ\{α } cho đỉnh thuộc Φ khơng thuộc tập VΦ1 {Φ1 ∪ {α }} Khi VΦ1 ∩ Φ = Φ1 ∪ {α } Tương tự, đặt Φ2 tập đỉnh thuộc Φ cho ∪j∈Φ2 V(j) ∩ Φ = Φ2 Từ (2.23) ta có yk0 = với k ∈ VΦ2 \VΦ1 Đặt Φ1 = {j ∈ Φ1 : ∃k ∈ P(j), < yk0 < 1} theo (2.19) ta có k∈P(j) yk = với j ∈ Φ1 Khi tồn đơi (k1 , k2 ) ∈ P(j) với j ∈ Φ1 mà < yk01 , yk02 < Ký hiệu hai tập Π1 = ∅, Π2 = ∅ gán j ∈ Φ1 nghĩa (j) = với j ∈ Φ1 Thế thành phần j ∈ Φ1 bj không giảm Ta tiến hành bước sau: Bước 1: Đặt s(j) = argmin{k ∈ P(j)\Π1 : < yk0 < 1} Bước 2: Nếu (j) = 0, đặt Π1 = Π1 ∪ {s(j)}, chọn (j) = (r) = với r ∈ V(j) ∩ Φ1 Trở lại bước Bước 3: Còn (j) = 1, đặt Π2 = Π2 ∪ {s(j)}, chọn (j) = (r) = với r ∈ V(j) ∩ Φ1 Kết thúc Ta thấy tồn hai điểm u1 = u0 +ε φk (Ωα ) ex −ε k∈Π1 ∩P(α ) φk (Ωα )ex −ε k∈Π2 ∩P(α ) eyk +ε k∈Π1 eyk k∈Π2 u2 = u0 −ε φk (Ωα ) ex +ε k∈Π1 ∩P(α ) φk (Ωα )ex +ε k∈Π2 ∩P(α ) eyk −ε k∈Π1 eyk k∈Π2 35 điểm vô tập XSDK Điều mâu thuẫn u0 điểm vơ cùng, từ ta có u0 = (u1 + u2 )/2 Định lý chứng minh Định lý (2.3.2.2.) tổng quát hóa kết bao lồi trường hợp tất định nghĩa |Ω| = trường hợp có hai giai đoạn tức t(j) với j ∈ V 2.3.2.3 Định lý Nếu aj ≥ max{bk , k ∈ V(j)} với j ∈ V tồn thuật toán phân chia đa thức bất đẳng thức phân (2.15) Khi điều kiện aj ≥ max{bk , k ∈ V(j)} khơng thỏa, ta sử dụng thuật tốn tìm phép phân chia bất đẳng thức phân giả sử aj ≥ max{bk , k ∈ V(j)} với j từ cố định hệ số biến yj để có min{aj , φj (R)} 2.3.2.4 Định lý Một bất đẳng thức có nghĩa sinh dãy tùy ý ghép đôi bất đẳng thức gốc tập tập XSDK mạnh tổ hợp lồi bất đẳng thức phân (2.15) với Ω ⊆ V Chứng minh Trước tiên, xét aj ≥ max{bk , k ∈ V(j)} Trường hợp này, theo Định lý (2.3.2.2), bất đẳng thức phân đủ để mô tả bao lồi tập XSDK Do đó, aj ≥ max{bk , k ∈ V(j)} với j, ta thu bất đẳng thức có nghĩa x + j∈VR φj (R)yj ≥ b(R), b(R) = maxj∈R {bj } sinh dãy tùy ý ghép đôi bất đẳng thức gốc với tập R ⊆ V mạnh tổ hợp lồi bất đẳng thức phân (2.15) x + j∈VΩk φj (Ωk )yj ≥ b(Ωk ), k = 1, , K ứng với tập đỉnh Ω1 , , ΩK Khi đó, tồn tập đối trọng λ1 , , λK với λK ≥ K k=1 λk = với j K K k θj (R) ≥ λk b(Ωk ) λk φj (Ω ) b(R) k=1 k=1 (2.24) 36 Kế đến, ta xét trường hợp hệ số aj Nhận xét bất đẳng thức có nghĩa thu dãy tùy ý ghép đôi với ràng buộc ban đầu XSDK ứng với tập đỉnh R ⊆ V biểu diễn: min{aj , θj (R)}yj ≥ b(R), x+ j∈VR θj (R) hệ số aj ≥ max{bk , k ∈ V(j)}, với j Tương tự, bất đẳng thức phân ứng với Ωk ⊆ V có dạng min{aj , φj (Ωk )}yj ≥ b(Ωk ), x+ j∈VΩk φj (R) hệ số aj ≥ max{bk , k ∈ V(j)}, với j Do K k k=1 λk b(Ω ) b(R) (kết (2.24)), nên ta cần kiểm tra với j ∈ V K K k min{aj , θj , (R)} ≥ λk min{aj , φj (Ω ) với λk ≥ k=1 λk = k=1 Thật vậy, aj ≥ φj (R) ta có K K k min{aj , θj (R)} = θj (R) ≥ k=1 (có min{aj , φj , (R)} = φj (R) ≥ Ngược lại, aj λk min{aj , φj (Ωk )} λk φj (Ω ) ≥ k=1 K k k=1 λk φj (Ω ) từ kết (2.24)) φj (R) K min{aj , θj , (R)} = aj ≥ K min{aj , φj (Ωk )} λ k aj ≥ k=1 k=1 Định lý chứng minh 2.4 Về việc phân nhánh cắt 2.4.1 Một mơ hình tốn học toán quy hoạch ngẫu nhiên nhiều giai đoạn 37 2.4.1.1 Bài toán Bài toán ước lượng ngẫu nhiên đơn hình mơ hình tốn học tốn quy hoạch ngẫu nhiên nhiều giai đoạn định nghĩa phân nhánh T = (V, E) pi (αi si + βi xi + γi yi ) + αa(0) sa(0) i∈V    sa(i) + xi = di + si , i∈V    với điều kiện x i y i , i∈V     s a(0) ≥ 0; si ≥ 0; yi ∈ {0, 1}, i ∈ V, s, x, y biến ngẫu nhiên, tham số α, β, γ a đại lượng biểu thị phụ thuộc vào giá trị biến ngẫu nhiên Loại bỏ dần biến si với i ∈ V dùng s để kiểm chứng lại biến ban đầu sa(0) , mảnh cắt toán ước lượng ngẫu nhiên |V|+1 XSLP = {(s, x, y) ∈ R+ × {0, 1}|V| : s + xj ≥ d0i , xi yi , i ∈ V} j∈P(i) (2.25) d0i = j∈P(i) dj Thay xi yi ta có mở rộng XSLP XRSLP = {(s, y) ∈ R+ × {0, 1}|V| : s + aj yj ≥ bi , i ∈ V}, (2.26) j∈P(i) bi = maxj∈P(i) {d0i } Nhận thấy XRSLP tập túi ngẫu nhiên XSDK , bất đẳng thức có nghĩa mở rộng mục (2.3.) có nghĩa với tập XSLP Bổ đề sau cho ta kết kể biến xj bất đẳng thức có nghĩa với tập XRSLP 2.4.1.2 Bổ đề Nếu bất đẳng thức s + j∈VR πj yj ≥ π0 có nghĩa với tập XSLP với R ⊆ V SR ⊆ VR bất đẳng thức s+ πj yj ≥ π0 , xj + j∈SR j∈S R (2.27) 38 S R = VR \SR có nghĩa với tập XSLP Chứng minh Xét điểm (s∗ , x∗ , y ∗ ) ∈ XSLP Dựng điểm (s, x, y) cho xj = x∗j yj = yj∗ với j ∈ SR , xj = yj = với j ∈ SR s = s∗ + j∈SR x∗j Thế với i ∈ V ta có x i = s∗ + s+ j∈SR j∈P(i) x∗i ≥ d0i x∗i ≥ s∗ + x∗i + j∈P(i) j∈P(i)\SR Do (s, x, y) ∈ XSLP Khi π0 π j y j = s∗ = s+ j∈VR x∗j + j∈SR πj yj∗ j∈VR \SR nên bất đẳng thức (2.27) có nghĩa với tập XSLP Bổ đề chứng minh 2.4.1.3 Định lý Cho tập R = {i1 , , iK } ⊆ V thỏa mãn bi1 biK b1 = maxj∈P(j) {d0i } tập SR ⊆ VR Khi đó, bất đẳng thức s+ φj (R)yj ≥ biK xj + j∈SR (2.28) j∈S R có nghĩa với tập XSLP S R = VR φj (R) = min{aj , ik ∈R(j) (bik − bik−1 )} với bi0 = Chứng minh áp dụng bổ đề (2.4.1.2) vào (2.14) ta điều cần chứng minh nhờ mở rộng tập túi ngẫu nhiên XRSLP 2.4.2 Một trường hợp đặc biệt 2.4.2.1 Đặt vấn đề Giả sử aj ≥ max{bk , k ∈ V(j)} với j ∈ V Xét tập đỉnh Q = {i1 , i2 , , iK }, đặt Q(j) = Q ∩ V(j) với j ∈ Vs, thỏa mãn (i)d0i1 d0i2 d0ik , (ii) Nếu j, im , in ∈ Q(j) {im+1 , im+2 , in−1 } ∈ Q(j) 39 Với i ∈ VQ , ta định nghĩa DQ(i) = DQ(i) = max{d0j : j ∈ Q(i)}    0, {j : j ∈ Q\Q(i) cho d0j   max{d0j : j ∈ Q\Q(i) cho d0j DQ(i) } = ∅ DQ(i) } MQ(i) = max{dij : j ∈ Q(i)}; δQ(i) = min{DQ(i) − DQ(i) MQ(i) } Thế cho SQ ⊆ VQ S Q = VQ \SQ , bất đẳng thức s+ δQ (j)yj ≥ MQ (0) xj + j∈SQ (2.29) j∈S Q có nghĩa với tập XSLP 2.4.2.2 Định lý Bất đẳng thức (2.28) (Q, SQ ) bất đẳng thức phân bất đẳng thức dạng (2.27) ứng với R = Q Chứng minh Kết định lý suy từ xác định tập Q trường hợp δQ (j) = φj (Q) với j ∈ VQ 2.4.3 Phép chia cắt Nhiệm vụ quan trọng khác phương pháp kỹ thuật chia cắt Mục chúng tơi trình bày kỹ thuật Trước tiên, xét trường hợp đặc biệt aj ≥ max{bk , k ∈ V(j)} Phép chia cắt bất đẳng thức phân (2.28) tương đương với việc tìm tập đỉnh R chia tập VR thành hai tập SR S R Điều khó thực nên chúng tơi tìm kết gần Nếu đặt SR = ∅ bất đẳng thức phân ước lượng (2.28) bất đẳng thức túi (2.15), theo định lý (2.3.2.3) chúng tơi có lược đồ dẫn ngắn để phân chia đa thức Trong trường hợp tổng qt, chúng tơi sử dụng lược đồ để tìm bất đẳng thức phân với giả thiết aj ≥ max{bk , k ∈ V(j)} từ cố định hệ số biến yj để có min{aj , φj (R)} 40 Kết luận Kết nghiên cứu, luận văn nêu số nội dung sau: Trình bày đầy đủ, khái niệm kiến thức sở tốn quy hoạch tuyến tính ngun, tốn quy hoạch tuyến tính ngun ngẫu nhiên, số khái niệm sở xác suất số phương pháp cắt giải toán quy hoạch tuyến tính ngun tất định Trình bày khái niệm việc nghiên cứu toán quy hoạch tuyến tính nguyên ngẫu nhiên nhiều giai đoạn Phát biểu chứng minh tính chất tốn Trình bày tốn quy hoạch ngun điển hình tốn "chiếc túi" ngẫu nhiên Phát biểu chứng minh số định lý quan trọng tốn xét Phân tích kỹ thuật nhánh cắt nhằm giải lớp toán quy hoạch tuyến tính nguyên nhiều giai đoạn, dựa phân nhánh cắt phân nhánh Do thời gian trình độ có hạn nên chúng tơi nhận thấy số vấn đề cần tiếp tục nghiên cứu bao gồm: - Xây dựng thuật tốn hồn chỉnh lập trình giải cho hai tốn đề cập luận văn - Khai thác đặc điểm riêng toán nhằm chuyển toán trường hợp đơn giản, dễ sử dụng 41 Tài liệu tham khảo [1] Nguyễn Văn Quảng (2007), Giáo trình xác suất, NXB Đại học Quốc gia, Hà Nội [2] Trần Xuân Sinh (2004), Các phương pháp ngẫu nhiên giải tốn quy hoạch, Giáo trình giành cho Cao học Thạc sĩ, chuyên ngành Xác suất Thống kê Toán học [3] Nguyễn Duy Tiến - Vũ Viết Yên (2001), Lý thuyết xác suất, NXB Giáo dục, Hà Nội [4] Nguyen Ngoc Chu - Tran Xuan Sinh (1989), Integer programming with reverse convex constraints, AMSE Review, AMSE Press, Vol.12, No2 (1989), 1-10 [5] Yongpei Guan, Shabbir Ahmed and George L Nemhauser (2006), Cutting planes for multi-stage stochastic integer programs, University Oklahoma - Institute of Technology, Atlanta [6] T Heinze and R Schultz (2006), A Branch-and-Bound Method for Multistage Stochastic Integer Programs with Risk Objectves, Department of Mathematics University of Duisburg-Essen, Campus Duisburg [7] A Saxena (2007), A Short Note on the Probabilistic Set Covering Problem, Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA [8] S Sen, H.D Sherali (2006), Decomposition with Branch-and-Cut Approaches for Two Stochastic Mixed-Integer Programming, Math Programming, 106(2), 203-223 ... hiệu Bài tốn quy hoạch ngun với tham gia yếu tố ngẫu nhiên gọi toán quy hoạch nguyên ngẫu nhiên Trong toán quy hoạch nguyên ngẫu nhiên, người ta chia ra: lớp quy hoạch nguyên ngẫu nhiên giai đoạn, ... giai đoạn, lớp quy hoạch nguyên ngẫu nhiên hai giai đoạn lớp quy hoạch nguyên ngẫu nhiên nhiều giai đoạn Các hướng tiếp cận nhằm tìm lời giải cho lớp toán quy hoạch nguyên ngẫu nhiên nhà khoa... quát toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn Trong mục này, đưa lớp toán quy hoạch nguyên ngẫu nhiên nhiều giai đoạn tài liệu tham khảo [5] đề cập tới 2.1.1 Bài toán Xét toán quy hoạch nguyên