Bài toán quy hoạch tuyến tính với hàm mục tiêu phụ thuộc tham số

  • Số trang: 48 |
  • Loại file: PDF |
  • Lượt xem: 190 |
  • Lượt tải: 0
quocphongnguyen

Đã đăng 3535 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH KIÊN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VỚI HÀM MỤC TIÊU PHỤ THUỘC THAM SỐ LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÀNH KIÊN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VỚI HÀM MỤC TIÊU PHỤ THUỘC THAM SỐ Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS TRẦN VŨ THIỆU THÁI NGUYÊN – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Líi cam oan Tæi xin cam oan ¥y l  cæng tr¼nh nghi¶n cùu cõa ri¶ng tæi. C¡c sè li»u v  k¸t qu£ nghi¶n cùu n¶u trong luận v«n l  trung thüc, ch÷a tøng ÷ñc cæng bè trong b§t ký mët cæng tr¼nh n o kh¡c. T¡c gi£ Nguyễn Thành Kiên LỜI NÓI ĐẦU Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) một hàm tuyến tính với các biến số thỏa mãn các ràng buộc đẳng thức (hay bất đẳng thức) tuyến tính. Ở dạng chung nhất, qui hoạch tuyến tính có thể hiểu là bài toán min{cT x : x ∈ D}, trong đó c ∈ Rn , D ⊂ Rn là một tập lồi đa diện, nghĩa là tập các nghiệm của một hệ đẳng thức (hay bất đẳng thức) tuyến tính và x ∈ Rn là véctơ biến cần tìm. Qui hoạch tuyến tính là bài toán tối ưu đơn giản nhất và được ứng dụng rộng rãi trong thực tiễn. Đôi khi các hệ số trong bài toán, nói riêng là các hệ số mục tiêu (như giá cả, lợi nhuận, ...), không hoàn toàn được xác định trước mà có thể biến động. Cũng vậy, trong nhiều bài toán qui hoạch toán học, các dữ liệu ban đầu thường phụ thuộc một tham số nào đó. Các bài toán như thế gọi là bài toán qui hoạch tham số (parametric programming). Vì thế, để tìm lời giải cho các bài toán loại này ta cần nghiên cứu qui hoạch tham số. Có nhiều dạng bài toán phụ thuộc tham số. Chẳng hạn, với bài toán qui hoạch tuyến tính, có thể các hệ số mục tiêu hay các hệ số ở vế phải hệ ràng buộc hoặc cả hai phụ thuộc tham số. Cũng có thể hệ số của các biến trong bài toán phụ thuộc tham số ... Luận văn này đề cập tới một lớp bài toán qui hoạch tham số điển hình, thường gặp. Đó là bài toán qui hoạch tuyến tính với hệ số mục tiêu phụ thuộc tuyến tính vào một tham số, gọi tắt là qui hoạch tuyến tính tham số. Qui hoạch tuyến tính tham số nghiên cứu tính chất của nghiệm tối ưu phụ thuộc tham số và đề xuất các phương pháp tìm nghiệm tối ưu theo tham số. Các nghiên cứu này bắt đầu từ những năm 1950, gần như cùng thời với sự ra đời của qui hoạch tuyến tính. 1 Mục tiêu của luận văn này là tìm hiểu và trình bày nội dung bài toán qui hoạch tuyến tính và bài toán vận tải với hàm mục tiêu phụ thuộc tuyến tính vào một tham số, tính chất hàm giá trị tối ưu của bài toán, phương pháp giải bài toán với các khoảng giá trị khác nhau của tham số, tìm ví dụ số minh hoạ cho thuật toán giải qui hoạch tuyến tính tham số và bài toán vận tải tham số và ứng dụng phương pháp qui hoạch tuyến tính tham số tìm các nghiệm tối ưu Pareto (các điểm hữu hiệu) của bài toán qui hoạch tuyến tính hai mục tiêu. Nội dung luận văn được viết thành ba chương: Chương 1 "Bài toán qui hoạch tuyến tính tham số" giới thiệu tóm tắt về bài toán qui hoạch tuyến tính và phương pháp đơn hình giải qui hoạch tuyến tính. Sau đó tập trung giới thiệu bài toán qui hoạch tuyến tính tham số với các hệ số mục tiêu phụ thuộc tuyến tính vào một tham số và trình bày thuật toán đơn hình tham số tìm lời giải tối ưu   cho bài toán với mọi tham số λ ∈ R hoặc λ ∈ t, t , trong đó t và t cho trước. Hàm giá trị tối ưu ϕ(λ) là một hàm lõm liên tục, tuyến tính từng khúc (đối với bài toán min) và là hàm lồi liên tục, tuyến tính từng khúc (đối với bài toán max). Chương 2 "Bài toán qui hoạch tuyến tính hai mục tiêu" giới thiệu vắn tắt về khái niệm tối ưu Pareto trong các bài toán qui hoạch tuyến tính với nhiều hàm mục tiêu và trình bày ứng dụng thuật toán đơn hình tham số vào tìm tập điểm hữu hiệu (tức lời giải tối ưu Pareto) của bài toán tuyến tính hai mục tiêu. Thuật toán tham số cho phép tìm được tất cả các điểm hữu hiệu, tập này tạo nên đường tối ưu Pareto của bài toán. Chương 3 "Bài toán vận tải tham số" trình bày kết quả về bài toán vận tải tham số, với tham số có mặt ở hàm mục tiêu của bài toán. Nêu thuật toán thế vị tìm lời giải cơ sở tối ưu trong các khoảng tham số khác nhau và nêu ví dụ số cho thấy hàm giá trị tối ưu của hai bài toán là hàm lõm liên tục, tuyến tính từng khúc. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này 2 còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này tác giả xin trân trọng cảm ơn các thầy cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên, Viện Toán học -Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Đặc biệt tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn GS -TS Trần Vũ Thiệu đã tận tình giúp đỡ để tác giả hoàn thành luận văn này. Thái Nguyên, tháng 09 năm 2014. Người thực hiện Nguyễn Thành Kiên 3 Chương 1 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH Chương này đề cập tới bài toán qui hoạch tuyến tính với hàm mục tiêu phụ thuộc tham số. Phần đầu nhắc lại các kiến thức cơ sở về qui hoạch tuyến tính và phương pháp đơn hình. Tiếp đó trình bày nội dung bài toán qui hoạch tham số và giới thiệu thuật toán giải bài toán, dựa trên các kỹ thuật tính toán của phương pháp đơn hình. Cuối chương nêu các ví dụ số minh họa cho thuật toán giải qui hoạch tham số. Nội dung của chương dựa chủ yếu vào các tài liệu [1] - [4]. 1.1 1.1.1 QUI HOẠCH TUYẾN TÍNH VÀ PHƯƠNG PHÁP ĐƠN HÌNH Bài toán qui hoạch tuyến tính chính tắc Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) một hàm tuyến tính với các biến số thỏa mãn các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Bài toán qui hoạch tuyến tính bất kỳ có thể đưa về dạng chính tắc sau:  min cT x : Ax = b, x ≥ 0 , (1.1) trong đó A ∈ Rm×n , b ∈ Rm , c ∈ Rn và x ≥ 0 có nghĩa là x ∈ Rn+ . Ta giả thiết m 6 n và rank (A) = m, nghĩa là không có ràng buộc thừa trong số các đẳng thức. 4 Ta nhắc lại một số định nghĩa: Hàm f (x) = cT x gọi là hàm mục tiêu (objective function). Tập D = {x ∈ Rn : Ax = b, x > 0} gọi là miền ràng buộc (constraint set) của bài toán. Như đã biết trong giải tích lồi, D xác định như trên là một tập lồi đa diện (polyhedron) và D có đỉnh. Véctơ x ∈ D, tức là Ax = b, x ≥ 0, gọi là một lời giải chấp nhận được (feasible solution). Lời giải chấp nhận được đạt giá trị nhỏ nhất của hàm mục tiêu cT x gọi là một lời giải tối ưu (optimal solution). Một điểm x0 ∈ D gọi là điểm cực biên (extreme point) hay đỉnh (vertex)   của tập lồi đa diện D nếu không có đoạn thẳng nào x1 , x2 ⊂ D mà x1 6= x2 và x0 = λx1 + (1 − λ)x2 với 0 < λ < 1. Một lời giải của bài toán (1.1) mà là điểm cực biên của D gọi là một lời giải cơ sở (basic solution). Định lý sau nêu một đặc trưng cho lời giải cơ sở của bài toán chính tắc. Định lý 1.1([2], Định lý 3.4). Ký hiệu A1 , A2 , ..., An là các cột của ma trận A. Một lời giải chấp nhận được x̄ ∈ D của bài toán (1.1) là lời giải cơ sở khi và chỉ khi tập véctơ {Aj : x̄j > 0} độc lập tuyến tính. Định lý sau cho biết khi nào bài toán qui hoạch tuyến tính có lời giải tối ưu. Định lý 1.2([2], Định lý 3.2). D 6= ∅ và nếu hàm mục tiêu cT x bị chặn dưới trên D thì bài toán (1.1) chắc chắn có lời giải tối ưu. Định lý sau khẳng định lời giải tối ưu đạt được tại một đỉnh của D. Định lý 1.3([2], Định lý 3.6). Qui hoạch tuyến tính chính tắc có lời giải tối ưu thì cũng có lời giải cơ sở tối ưu. 1.1.2 Phương pháp đơn hình Phương pháp đơn hình do G. B. Dantzig đề xuất năm 1947 là phương pháp quen thuộc và hiệu quả để giải các dạng bài toán qui hoạch tuyến tính. Hơn nữa, phương pháp đơn hình còn được cải biên, mở rộng để giải nhiều bài toán khác như: qui hoạch toàn phương, qui hoạch phân tuyến tính, bài toán bù tuyến tính, qui hoạch tuyến tính đa mục tiêu, ... 5 Phương pháp đơn hình cũng có nhiều biến thể khác nhau tùy theo đặc điểm bài toán cần giải: đơn hình gốc, đơn hình đối ngẫu, đơn hình gốc - đối ngẫu, đơn hình cải biên, ... Trong mục này ta sẽ trình bày phương pháp đơn hình dạng gốc giải qui hoạch tuyến tính chính tắc. Xét bài toán qui hoạch tuyến tính (1.1). Hàm mục tiêu f (x) = cT x tuyến tính nên nếu f(x) bị chặn dưới trên miền ràng buộc D = {x ∈ Rn : Ax = b, x > 0} thì theo các Định lý 1.2 và 1.3, f (x) = cT x đạt cực tiểu tại ít nhất một điểm cực biên của D. Vậy chỉ cần tìm điểm cực tiểu trong tập các điểm cực biên của miền ràng buộc D, tức là trong tập các lời giải cơ sở. Ta bắt đầu từ một lời giải cơ sở. Cho x̄ là một lời giải cơ sở (cách tìm sẽ mô tả sau), ứng với cơ sở B. Ở đây cơ sở B được hiểu là một tập chỉ số với các tính chất: a) B ⊂ {1, ..., n} , |B| = m (B gồm m chỉ số); b) B ⊇ {j : x̄j > 0}, tức là x̄j = 0 với mọi j ∈ / B; c) Hệ véctơ {Aj : j ∈ B} độc lập tuyến tính. Đặt N = {1, ..., n} \B . Biến xj , j ∈ B , gọi là biến cơ sở (basic variable), biến xj , j ∈ N , gọi là biến ngoài cơ sở hay biến phi cơ sở (nonbasic variable). Ta phân hoạch A = (AB , AN ), trong đó AB = {Aj : j ∈ B} là ma trận vuông không thoái hóa, lập nên bới m véctơ cột Aj của A với chỉ số j ∈ B và AN = {Aj : j ∈ N } là ma trận lập nên bởi n - m véctơ Aj còn lại của A với chỉ số j ∈ N . Tương tự, ta viết c = (cB , cN ) với cB và cN là véctơ gồm các thành phần cj của c với j ∈ B và j ∈ N tương ứng. Cách viết x = (xB , xN ) có ý nghĩa tương tự. Để cho tiện, ta cũng gọi AB là cơ sở và Aj , j ∈ B , là véctơ cơ sở, còn Aj , j ∈ N , là véctơ ngoài cơ sở hay véctơ phi cơ sở. Tương ứng với cơ sở B, phương trình Ax = b trở thành AB xB + −1 AN xN = b. Từ đó xB = A−1 B (b − AN xN ) (nói riêng x̄B = AB b ), suy ra công thức biểu diễn các biến cơ sở theo các biến ngoài cơ sở xB = x̄B − A−1 B AN xN . 6 Do đó T cT x = cTB xB + cTN xN = cTB x̄B − cTB A−1 B AN xN + cN xN hay T cT x = cTB x̄B − (cTB A−1 B AN − cN )xN (1.2) T Vì thế, nếu ∆N = cTB A−1 B AN − cN ) 6 0 thì x̄ tối ưu. Còn nếu ∆N có một thành phần dương, chẳng hạn ∆k > 0 với một chỉ số k ∈ N nào đó, thì công thức (1.2) cho thấy rằng khi tăng xk có thể làm giảm cT x, nghĩa là đưa k vào B thay thế cho một phần tử thích hợp trong B ta sẽ có một cơ sở mới B’ chấp nhận được tốt hơn (hay ít nhất không kém). Đó là ý tưởng chính của phương pháp đơn hình để giải qui hoạch tuyến tính chính tắc. Để đơn giản, giả sử rằng B = 1, ... , m. Nếu ma trận A−1 B AN = P [Zik , i ∈ B, k ∈ N ] thì ∆k = ci zik − ck và công thức (1.2) có thể viết i∈B lại thành cT x = cT x̄ − X X X ci zik − ck )xk = cT x̄ − ∆k xk . ( k∈N i∈B k∈N Công thức này cho thấy (với bài toán tìm cực tiểu) Tiêu chuẩn tối ưu: x̄ là lời giải tối ưu nếu X ∆k = ci zik − ck 6 0 ∀k ∈ N. i∈B • Dấu hiệu nhận biết bài toán có trị tối ưu vô cực (−∞ với bài toán min, +∞ với bài toán max): ∃k ∈ N với ∆k > 0 (bài toán min) hay ∆k < 0 (bài toán max), zik 6 0 ∀i ∈ B . • Qui tắc "Hình chữ nhật" tính truy hồi các hệ số zik trong bảng đơn hình: Giả sử biến xs , s ∈ N , được đưa vào cơ sở thay cho biến thứ r trong B. Khi đó z 0 ik =  zik, − (zrk /zrs )zis , i 6= r zrk /zrs , i = r , i = 1, ..., m, k = 0, 1, ..., n 7 với zi0 là giá trị biến cơ sở thứ i trong x̄B và A−1 B Ak = (zik )i ∈B , k = 1, ... , n.. Giá trị hàm mục tiêu ∆0 = cT x và ∆k , k ∈ N 0 , được tính theo công thức: ∆0 k = ∆k − (zrk /zrs ) ∆s , k ∈ {0} ∪ N 0 . • Tìm lời giải cơ sở ban đầu: Lập và giải qui hoạch tuyến tính phụ (b > 0):  min eT z : Ax + Iz = b, x > 0, z > 0 , trong đó e ∈ Rm là véctơ với mọi thành phần bằng 1 và I là ma trận đơn vị cấp m. Lời giải cơ sở ban đầu là (0, b). 1.1.3 Ví dụ minh họa Ví dụ 1.1. Giải qui hoạch tuyến tính f (x) = 9x1 + 2x2 − 15x3 → min với điều kiện  x1 + 2x2 + x3 + x4       3x1 + 2x3 + x5 = 40 = 60  x1 + 4x2 + x6 = 30      x1 > 0, x2 > 0, x3 > 0 Bài toán có lời giải cơ sở ban đầu x1 = (0, 0, 0, 40, 60, 30)T với  f x1 = 0. Cơ sở B = {4, 5, 6} , N = {1, 2, 3}. Lập bảng đơn hình ban đầu (xem [2], tr. 54). 8 Do ∆3 = 15 > 0 nên x1 chưa tối ưu. Đưa x3 vào cơ sở thay x5 . Lập Bảng 2.  Lời gỉải cơ sở mới x2 = (0, 0, 30, 10, 0, 30)T với f x2 = −450 <  f x1 = 0. Cơ sở mới B 0 = {4, 3, 6} , N 0 = {1, 2, 5}. Mọi ∆k 6 0 nên x2 tối ưu: Dừng quá trình giải. Xuất xopt = x2 = (0, 0, 30, 10, 0, 30)T và fmin = −450. 1.2 QUI HOẠCH TUYẾN TÍNH VỚI MỤC TIÊU THAM SỐ 1.2.1 Nội dung bài toán Có nhiều dạng bài toán phụ thuộc tham số. Chẳng hạn với bài toán qui hoạch tuyến tính, có thể các hệ số mục tiêu hay các hệ số ở vế phải hệ ràng buộc hoặc cả hai phụ thuộc tham số. Cũng có thể hệ số của các biến trong bài toán phụ thuộc tham số ... Chương này xét một trường hợp đơn giản, thường gặp. Đó là bài toán qui hoạch tuyến tính với các hệ số mục tiêu phụ thuộc tuyến tính vào một tham số. Bài toán có dạng như sau: P (λ) min{(c + λd)T x : Ax = b, x > 0}, (1.3) trong đó A là ma trận cấp m × n, b, c và d lần lượt là các véctơ (cột) với m, n và n thành phần. Giả thiêt m 6 n, rank (A) = m. Ký hiệu D = {x ∈ Rn : Ax = b, x > 0} và gọi D là miền ràng buộc của bài toán. Ta cũng giả thiết D 6= ∅. P (λ) xác định theo (1.3) gọi tắt là bài toán qui hoạch tuyến tính tham số (Parametric Linear Programming). Tương tự như trong qui 9 hoạch tuyến tính, véctơ x ∈ D, tức Ax = b, x > 0, gọi là một lời giải chấp nhận được. Lời giải chấp nhận được mà là đỉnh của D gọi là một lời giải cơ sở, mỗi lời giải cơ sở có một cơ sở tương ứng gồm chỉ số của m biến cơ sở. Lời giải chấp nhận được đạt giá trị nhỏ nhất của hàm mục tiêu (c + λd)T x gọi là một lời giải tối ưu của P (λ). Nếu lời giải tối ưu mà là đỉnh của D thì nó được gọi là giải cơ sở tối ưu. Cơ sở tương ứng với lời giải này cũng được gọi là cơ sở tối ưu. Tập các giá trị tham số λ làm cho một cơ sở tối ưu gọi là khoảng tham số tối ưu của cơ sở đó. Mục đích của qui hoạch tham số là tìm nghiệm tối ưu cho P (λ)với mọi tham số λ ∈ R hay với mọi λ thuộc một khoảng cho trước nào đó. Ký hiệu ϕ(λ) là giá trị tối ưu của P (λ). Có thể thấy ϕ : λ ∈ R → ϕ(λ) = min {(c + λd)T x} Ax=b, x>0 là một hàm lõm (concave function) liên tục, tuyến tính từng khúc, vì   ϕ(λ) là bao dưới của một họ hàm afin f (x, λ) = cT x + dT x λ theo  λ. Chú ý, ψ(λ) = max cT x : Ax = b, x > 0 là một hàm lồi (convex function) liên tục, tuyến tính từng khúc, vì lúc đó ψ(λ) là bao trên của một họ hàm afin theo λ. Theo lý thuyết qui hoạch tuyến tính tham số, có tồn tại một số hữu hạn giá trị tham số  −∞ < t−p < ... < t−1 < t1 < ... < tq < +∞ p, q > 0, nguyên sao cho ϕ(λ) là tuyến tính với mọi λ ∈ [tk , tk+1 ] (−p 6 k < q) hoặc với mọi λ 6 t−p hoặc với mọi λ > tp . Ở đây các giá trị tk được đánh số sao cho t−1 < 0 6 t1 . Đồng thời với mỗi k ∈ [−p, q − 1] tồn tại cơ sở Bk là tối ưu của bài toán P (λ) với mọi λ ∈ [tk , tk+1 ]. Các giá trị tk gọi là các điểm gẫy (breakpoints) của hàm ϕ(λ). Do tính chất nêu trên nên vấn đề đặt ra là tìm các điểm gẫy tk của ϕ(λ) và các cơ sở tối ưu Bk tương ứng với các điểm gẫy này. Như vậy, ta chỉ cần giải một số hữu hạn bài toán P (λ) với λ là các điểm gẫy. 10 1.2.2 Thuật toán qui hoạch tham số Sơ đồ thuật toán giải trình bày dưới đây là một biến thể của phương pháp đơn hình quen biết trong qui hoạch tuyến tính, đã được nhắc lại ở Mục 1.1.2. Ý tưởng chung của thuật toán tham số là bắt đầu từ một giá trị tùy ý λ ∈ R hoặc λ thuộc khoảng cho trước, chẳng hạn λ0 = t0 . Dùng phương pháp đơn hình giải bài toán qui hoạch tuyến tính P (t0 ). Do giả thiêt D 6= ∅ nên sau một số hữu hạn bước lặp ta thu được lời giải cơ sở tối ưu của bài toán P (t0 ) hoặc khẳng định hàm mục tiêu của bài toán P (t0 ) không bị chặn dưới trên miền D. Xét hai trường hợp. • Trường hợp 1. Giả sử ta thu được lời giải cơ sở tối ưu của P (t0 ) là x0 = (x01 , ...x0n , )T với cơ sở tối ưu B0 , nghĩa là: a) B0 ⊂ {1, ... , n} , |B0 | = m; / B0 ; b) B0 ⊇ {j : x0j > 0}, tức x0k = 0 ∀k ∈ c) {Aj : j ∈ B0 } độc lập tuyến tính. Véctơ x0 không chỉ là lời giải cơ sở tối ưu của bài toán P(λ) với tham số λ = t0 đã chọn, mà nó còn là lời giải cơ sở tối ưu của P(λ) với mọi tham số λ trong khoảng [t−1 , t1 ]. Sử dụng các điều kiện tối ưu trong phương pháp đơn hình, ta xác định khoảng tham số tối ưu [t−1 , t1 ] của cơ sở B0 như sau. Theo thuật toán đơn hình, ước lượng của véctơ biến xk với k ∈ / B0 có thể biểu diễn dưới dạng một hàm tuyến tính phụ thuộc tham số λ như sau: ∆k (λ) = [ X ci zik − ck ] + λ[ i∈B0 X di zik − dk ], i∈B0 trong đó zik , i ∈ B0 là các hệ số khai triển theo cơ sở B0 của véctơ Ak (nghĩa là Ak = [zik , i ∈ B0 ]). Ký hiệu X X 1 2 ∆k = ci zik − ck , ∆k = di zik dk − ck ⇒ ∆k (λ) = ∆1k + λ∆2k i∈B0 i∈B0 Do x0 là lời giải tối ưu của bài toán P (t0 ) nên ta có ∆k (t0 ) = ∆1k + t0 ∆2k 6 0 ∀k ∈ / B0 11 Khi đó x0 vẫn còn là lời giải tối ưu của bài toán P (λ) với mọi λ thỏa mãn: ∆k (λ) = ∆1k + λ∆2k 6 0 ∀k ∈ / B0 (1.4) Hệ bất phương trình (1.4) tương thích vì nó có nghiệm λ = t0 . Với ∆2k > 0 từ (1.4) suy ra λ 6 −∆1k /∆2k , còn với ∆2k < 0 suy ra λ > −∆1k /∆2k . Nếu ký hiệu ( t−1 = ( t1 = ∆1 max{ - ∆2k : ∆2k < 0} k −∞, khi ∀∆2k > 0 (1.5) ∆1 min{ - ∆2k : ∆2k > 0} k +∞, khi ∀∆2k 6 0 (1.6) thì tập nghiệm của hệ (1.4) là t−1 6 λ 6 t1 . Như vậy, với λ ∈ [t−1 , t1 ] ta có ∆k (λ) 6 0 với mọi k ∈ / B0 và vì thế x0 là lời giải tối ưu của P (λ). Nói riêng ta có ∆k (t1 ) 6 0 ∀k = 1, ..., n. (1.7) / B0 thì t−1 không bị chặn dưới, Chú ý rằng nếu ∆2k > 0 với mọi k ∈ / B0 thì t1 không bị chặn ta đặt t−1 = −∞ còn nếu ∆2k 6 0 với mọi k ∈ trên, ta đặt t1 = +∞. Vậy nếu ký hiệu E(B) là khoảng tham số tối ưu của cơ sở tối ưu B, ta có E (B0 ) = [t−1 , t1 ]. Vì E(B) là miền nghiệm của một hệ bất phương trình tuyến tính nên khoảng tham số tối ưu của cơ sở B có thể là một điểm (khi t−1 = t1 ), một đoạn (khi t−1 < t1 ), một tia (khi t−1 = −∞ hay t1 = +∞) hoặc toàn bộ đường thẳng. Tuy nhiên, với một cơ sở B bất kỳ có thể E(B) = ∅. Tiếp theo, ta xét các giá trị tham số λ ở bên phải (λ > t1 ) và bên trái (λ 6 t−1 ) khoảng E(B) = [t−1 , t1 ]. Ta tiến hành như sau. Xét bài toán P (λ) với λ > t1 . Giả sử s là chỉ số sao cho t1 = −∆1s /∆2s = min{−∆1k /∆2k : ∆2k > 0}. Khi đó ∆s (t1 ) = ∆1s + t1 ∆2s = 0 12 (1.8) Có hai khả năng xảy ra: a. Nếu zis 6 0 ∀i ∈ B0 thì do ∆2k > 0 nên với mọi λ > t1 ta có ∆s (λ) = ∆1s + λ∆2s > 0 (1.9) Theo thuật toán đơn hình thì f (x) = cT x → −∞ khi t1 < λ → +∞. b. Còn nếu ∃i ∈ B0 , zis > 0 thì với λ > t1 khi đưa biến xs vào cơ sở sẽ nhận được lời giải cơ sở mới tốt hơn (với giá trị hàm mục tiêu nhỏ hơn). Lời giải cơ sở x0 ứng với cơ sở B0 không còn tối ưu nữa vì ít nhất đã có ∆s (λ) > 0 với λ > t1 (do có (1.9)). Giả sử theo thủ tục đơn hình, biến với chỉ số ir ở vị trí r trong B0 bị loại khỏi cơ sở. Khi đó ta nhận được cơ sở mới B1 = (B0 \{ir }) ∪ {s}. Ta có Định lý 1.4. B1 là cơ sở tối ưu của bài toán P (t1 ). Chứng minh. Theo công thức biến đổi cơ sở thì ∆0 k (λ) = ∆k (λ) − zrk ∆s (λ), k = 1, ..., n zrs Do ∆s (t1 ) = 0 (xem (1.8)) nên theo qui tắc hình chữ nhật và (1.7) suy ra ∆0 k (t1 ) = ∆k (t1 ) 6 0 với mọi k = 1, ..., n. Như vậy cơ sở mới B1 tối ưu với λ = t1 . Định lý 1.5. Khoảng tham số tối ưu của cơ sở B1 có mút trái là t1 . Chứng minh. Xét hệ phương trình tuyến tính ∆0 k (λ) = ∆1k + λ(∆2k )0 6 0, k = 1, ..., n (1.10) Hệ (1.10) tương thích vì nó có nghiệm λ = t1 . Xét khoảng nghiệm của hệ này. Vì (∆1k )0 và (∆2k )0 cũng nghiệm đúng công thức biến đổi cơ sở nên (∆1k )0 = ∆1k − (zrk /zrs )∆1s , k = 1, ...., n, (∆2k )0 = ∆2k − (zrk /zrs )∆2s , k = 1, ...., n. Do ir ∈ B0 nên ∆1ir = ∆2ir = 0, zri = 1, vì vậy (∆1ir )0 = −∆1s /zrs , (∆2ir )0 = −∆2s /rs . 13 Nếu λ là nghiệm của (1.10) thì nói riêng nó phải thỏa mãn ∆0 ir (λ) 6 0, tức ∆1s ∆2s − −λ 60 zrs zrs (1.11) Vì zrs > 0, ∆2s > 0 nên (1.11) tương đương với ∆1s + λ∆2s > 0 hay ∆1s λ > − 2 = t1 . ∆s Điều này chứng tỏ rằng nghiệm của hệ (1.10) phải thỏa mãn λ > t1 . Vậy cơ sở B1 có khoảng tham số tối ưu nhận t1 làm mút trái. Mút bên phải của khoảng tham số tối ưu đối với cơ sở B1 được xác định theo công thức tương tự như (1.6). Quá trình trên tiếp tục cho tới khi tìm được một tia mà nó hoặc là khoảng tối ưu của cơ sở cuối cùng hoặc là hàm mục tiêu không bị chặn dưới trên tia này. Xét bài toán P (λ) với λ 6 t−1 . Ta làm hoàn toàn tương tự như trên. Giả sử h là chỉ số sao cho  t−1 = −∆1h /∆2h = max −∆1k /∆2k : ∆2k < 0 . Từ đó ∆k (t−1 ) = ∆1k + t−1 ∆2k 6 0 ∀k ∈ / B0 . ∆h (t−1 ) = ∆1h + t−1 ∆2h = 0, ∆h (λ) = ∆1h + λ∆2h > 0 với λ < t−1 . Biến xh được đưa vào cơ sở thay cho biến có chỉ số ir ∈ B0 bị loại khỏi cơ sở. Cơ sở mới B2 = (B0 \ir }) ∪ {h}. Giả sử x2 là lời giải cơ sở ứng với cơ sở B2 . x2 là lời giải tối ưu của bài toán P (λ) với tham số λ thuộc một khoảng có mút phải là t−1 . Mút trái của khoảng này được xác định theo công thức tương tự như (1.5). Bằng cách như vậy, ta sẽ thu được mọi lời giải tối ưu của bài toán qui hoạch tham số P (λ) ứng với các khoảng tham số nằm về phía trái t−1 . 14 Nếu trong quá trình giải các bài toán P (λ) với λ > tk hoặc λ < t−k ta sử dụng "qui tắc tự vựng" để chọn biến loại ra khỏi cơ sở như trong phương pháp đơn hình khắc phục hiện tượng xoay vòng thì bao giờ ta cũng di chuyển theo những cơ sở khác nhau. Do đó quá trình giải bài toán như đã trình bày ở trên sẽ kết thúc sau một số hữu hạn bước. • Trường hợp 2. Giả sử bài toán P (t0 ) có hàm mục tiêu không bị chặn dưới, tức là tồn tại cơ sở B0 và chỉ số k ∈ / B0 sao cho ∆k (t0 ) = ∆1k + t0 ∆2k > 0 (1.12) và zik 6 0 ∀i ∈ B0 . Xét hai khả năng. a. Nếu ∆2k = 0 thì từ (1.12) cho thấy ∆k (λ) = ∆1k > 0 với mọi λ0 , do đó (c + λd)T x không bị chặn dưới với mọi λ ∈ R, tức P (λ) có trị tối ưu vô cực với mọi λ: Dừng quá trình giải. b. Nếu ∆2k 6= 0, đặt t1 = −∆1k /∆2k và xét bất đẳng thức ∆1k +λ∆2k > 0. Nếu ∆2k < 0 thì bất đẳng thức thỏa mãn với mọi giá trị λ < t1 . Còn nếu ∆2k > 0 thì bất đẳng thức thỏa mãn với mọi giá trị λ > t1 . Giả sử ∆2k < 0 (trường hợp ∆2k > 0 xét tương tự). Khi đó bài toán P (λ) không giải được với mọi λ < t1 , ta xét tiếp với λ > t1 . Trước hết ta giải bài toán P (t1 ). Có hai khả năng xảy ra: b1. Nếu tìm được cơ sở tối ưu cho P (t1 ) thì quá trình tính toán tiếp tục theo trường hợp 1 đã xét ở trên. b2. Nếu P (t1 ) lại không giải được, tức là tồn tại cơ sở B1 và chỉ số s∈ / B1 sao cho ∆s (t1 ) = ∆1k + t1 ∆2k > 0 và zis 6 0 ∀i ∈ B1 . (1.13) Xảy ra các khả năng sau: * Nếu ∆2s = 0 thì ∆s (λ) = ∆1s > 0 với mọi λ, do đó bài toán P (λ) không giải được trên toàn trục số thực R. * Nếu ∆2s > 0 thì ∆s (λ) = ∆1s + λ∆2s > 0 với mọi λ > t2 = −∆1s /∆2s . Mặt khác, từ (1.13) suy ra t1 > −∆1s /∆2s = t2 . Như vậy bài toán P (λ) không giải được với mọi λ > t2 , nhưng đồng thời nó lại không giải được với mọi λ < t1 , do đó P (λ) không giải được với mọi λ ∈ R. 15 * Nếu ∆2s < 0 thì ∆s (λ) = ∆1s + λ∆2s > 0 với mọi λ < t2 . Từ (1.13) suy ra t1 ∆2s > −∆1s , do đó t1 < t2 = −∆1s /∆2s . Tiếp tục xét bài toán P (λ) với λ > t2 bằng cách giải P (t2 ). Sau một số hữu hạn bước hoặc sẽ khẳng định bài toán P (λ) không giải được đối với mọi λ > t2 hoặc tìm được lời giải cơ sở tối ưu cho bài toán P (λ) với λ = t3 nào đó, v.v ... 1.2.3 Ví dụ minh họa Ví dụ 1.2 ([1], tr. 150). Giải bài toán qui hoạch tuyến tính tham số (λ ∈ R ): −(2 + 3λ)x1 + (1 − 2λ)x2 − 3λx3 − 4x4 → min với các ràng buộc  x1 + 2x2 + x3 + 3x4 6 7       −3x1 + 4x2 + 3x3 − x4 6 15  2x1 − 5x2 + 2x3 + 2x4 6 2      x1 > 0, x2 > 0, x3 > 0, x4 > 0 Dữ liệu bài toán gồm ! 1 2 1 3 A = −3 4 3 −1 , b = 2 −5 2 2 7 15 2 !   −2   1  , c =  0 , d =  −4   −3 −2  −3  . 0 Chọn tham số ban đầu λ = t0 = 0. Ta thêm vào 3 biến bù x5 , x6 , x7 > 0 đưa các ràng buộc về dạng đẳng thức. Giải qui hoạch tuyến tính chính tắc P (t0 ) với t0 = 0. Cơ sở ban đầu B0 = {5, 6, 7}. Quá trình giải P (t0 ) được ghi ở các Bảng 1 - 3. 16 ∆4 = 4 > 0. Đưa x4 vào cơ sở thay cho x7 ta nhận được Bảng 2 ∆2 = 9 > 0. Đưa x2 vào cơ sở thay cho x5 ta nhận được Bảng 3 Cơ sở tối ưu cho P (t0 ) là B0 = {2, 4, 6}. Để tìm khoảng tham số tối ưu của cơ sở này, trong Bảng 3 ngoài dòng ∆1k , ta tính thêm hai dòng ∆2k và −∆1k /∆2k . Theo (1.5) - (1.6) ta có E (B0 ) = [−9/2, 2/65]. Giá trị tối ưu ϕ(λ) = −(148 + 16λ)/19 với mọi −9/2 6 λ 6 2/65. Tiếp theo, ta tìm lời giải của P (λ) với λ ở bên trái khoảng E (B0 ) = [−9/2, 2/65]. Từ Bảng 3, ta đưa biến x5 (do t−1 = −∆15 /∆25 ) vào cơ sở thay cho x2 ta được cơ sở mới B−1 = {5, 6, 4} (xem Bảng 4). Trong bảng này dòng ∆2k không có phần tử âm nên theo (1.5), B−1 là cơ sở tối ưu của P (λ) với mọi λ ∈ (−∞; −9/2]. Giá trị tối ưu ϕ(λ) = −4 + 0.λ với mọi λ 6 −9/2. 17
- Xem thêm -