Giải một lớp bài toán qui hoạch phân thức phi tuyến

Chia sẻ: Bautroibinhyen17 Bautroibinhyen17 | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

57
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày phương pháp giải một lớp bài toán qui hoạch phân thức phi tuyến. Dùng biến đổi Charnes-Cooper, bài toán được đưa về một qui hoạch phi tuyến tương đương và sau đó qui hoạch này lại được biến đổi thành một bài toán qui hoạch tuyến tính, với một biến số và hai ràng buộc nhiều hơn so với bài toán ban đầu. Cuối bài nêu ra các ví dụ số minh họa cho phương pháp giải.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giải một lớp bài toán qui hoạch phân thức phi tuyến

. • \ W X F { Q J W U u Q K N K R D K e F GIẢI MỘT LỚP BÀI TOÁN QUI HOẠCH PHÂN THỨC PHI TUYẾN GS.TS. Trần Vũ Thiệu Khoa Toán - Tin Tóm tắt. Bài này trình bày phương pháp giải một lớp bài toán qui hoạch phân thức phi tuyến. Dùng biến đổi Charnes-Cooper ([2], tr. 54), bài toán được đưa về một qui hoạch phi tuyến tương đương và sau đó qui hoạch này lại được biến đổi thành một bài toán qui hoạch tuyến tính, với một biến số và hai ràng buộc nhiều hơn so với bài toán ban đâu. Cuối bài nêu ra các ví dụ số minh hoạ cho phương pháp giải. 1. NỘI DUNG BÀI TOÁN Xét bài toán qui hoạch phân thức phi tuyến có dạng: p 0 (t 0 )  p1 ( t 1 ) x 1    p n ( t n ) x n (P) , min xk , tk , qk q 0  q1 x 1    q n x n với các điều kiện A1x1 + ... + Anxn ≤ b, x1 ≥ 0, ... , xn ≥ 0. ak ≤ tk ≤ b k, ck ≤ qk ≤ dk, k = 0, 1, ... , n, trong đó ak, bk, ck, dk ∈ ℝ, Ak ∈ ℝm (k = 1, ... , n) và b ∈ ℝm cho trước, pk(t) là hàm liên tục theo t ∈ [ak, bk] ⊂ ℝ. Các biến cần tìm của (P) là xk. tk, qk, k = 1, ... , n. Ta giả thiêt: a) Tập X = {x ∈ ℝn : A1x1 + ... + Anxn ≤ b, x ≥ 0} ≠ ∅ và bị chặn; b) q 0 + q1x1+ ... + qnxn > 0 ∀x = (x1, ... , xn)T ∈ X, ∀qk ∈ [ck, d k]. Khi ak = bk, ck = dk với mọi k = 0, 1, ... , n (tức mọi pk, qk cho trước), (P) trở thành bài toán qui hoạch phân tuyến tính ([2], tr. 41 và [3], tr. 703) thông thường, ký hiệu (LFP). Khi xem mọi tk, qk như các biến số thì (P) là một bài toán qui hoạch phân thức phi tuyến. Để cho tiện về sau, ta ký hiệu A = (A1, A2, ... , An). Trường hợp mọi pk(tk) tuyến tính đã xét ở [4]. Có thể giải thích ý nghĩa của bài toán (P) như sau: Giả sử một xí nghiệp có thể dùng m loại vật tư hiện có để sản xuất ra n loại sản phẩm. Gọi bi là lượng vật tư i (i = 1, ... , m) mà xí nghiệp có và aik là định mức tiêu hao vật tư i để sản xuất một đơn vị sản phẩm k (k = 1, ... , n). Mỗi đơn vị sản phẩm k sản xuất ra sẽ cho lợi nhuận là pk(tk) phụ thuộc tham số tk ∈ [ak, bk] và tốn chi phí sản xuất là qk∈ [ck, dk], p0(t0) là lợi nhuận cố định thu được và q0 là chi phí cố định cần bỏ ra (p0, q0 không phụ thuộc số lượng sản phẩm sản xuất). Hỏi với số vật tư đã có xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm mỗi loại sao cho hiệu qủa sản xuất của xí nghiệp (đo bằng tỉ số giữa tổng lợi nhuận thu được trên tổng chi phi sản xuất) là lớn nhất? Bài toán này dẫn đến mô hình qui hoạch phân thức có dạng bài toán (P). Dùng phép đổi biến số Charnes - Cooper ([2], tr. 54), ta đưa bài toán (P) về một bài toán tối ưu phi tuyến tương đương: Thêm vào một biến mới 1 y0 = > 0, q 0  q1x 1    q n x n 7 U u Q J 9 L K e F 7 K Q J / R Q J 72 . • \ W X F { Q J W U u Q K N K R D K e F (P) được viết lại thành bài toán: p0(t0)y0 + p1(t1)y0x1 + ... + pn(tn)y0 xn → min, q0 y0 + q1 y0 x1 + ... + q ny0 xn = 1, A1 y0x1 + ... + Any0 xn ≤ by0, x1 ≥ 0, ... , xn ≥ 0, y0 ≥ 0. ak ≤ tk ≤ b k, ck ≤ qk ≤ d k, k = 0, 1, ... , n. Bằng cách thay các biến xk bởi yk = y0 xk với mọi k = 1, ... , n, ta đưa bài toán trên về dạng tương đương: (Q) p0(t0)y0 + p1(t1)y1 + ... + p n(tn)yn → min, q0 y0 + q1 y1 + ... + qnyn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. ak ≤ tk ≤ b k, ck ≤ qk ≤ d k, k = 0, 1, ... , n. Định lý sau cho thấy có thể giải (Q) thay cho bài toán (P).  Định lý 1. Với các giả thiết đã nêu, nếu y* = ( y , y1 , ... , y  )T là một nghiệm tối ưu 0 n  của bài toán (Q) thì y > 0 và x* = ( x1 , x  , ... , x  )T với x  = y / y sẽ là một nghiệm tối 0 2 n k k 0 ưu của bài toán (P) ban đầu. Chứng minh. Trước tiên ta chứng minh y > 0. Thật vậy, nếu y = 0 thì do q Ty* = 1 0 0  nên đặt z = ( y1 , ... , y  ) ta có z ≠ 0 và z thỏa mãn Az ≤ 0, z ≥ 0. Khi đó z là một hướng lùi xa n của tập lồi X, bởi vì với bất kỳ x ∈ X (tức Ax ≤ b, x ≥ 0) ta có A(x + z) = Ax + Az ≤ b và x + z ≥ 0 với mọi  ≥ 0. Chứng tỏ x + z ∈ X với mọi  ≥ 0, điều này trái với giả thiêt tập X bị chặn. Vậy phải có y ≠ 0. Do y  ≥ 0 nên y > 0. 0 0 0 Bây giờ ta chứng minh x* là nghiệm tối ưu của (P). Thật vậy, do y* là nghiệm của (Q), > 0 nên x* nghiệm đúng Ax* ≤ b, x* ≥ 0, tức x* ∈ X. Lấy bất kỳ x ∈ X (Ax ≤ b, x ≥ 0). Do giả thiêt q0 + q1x1 + ... + qnxn > 0 nên y = (y0, y1, ... , yn) với y0 = 1/(q 0 + q1x1 + ... + q nxn) > 0, yk = y0 xk ≥ 0, k = 1, ... , n, sẽ thoả mãn mọi ràng buộc của bài toán (Q). Mặt khác, y* là nghiệm tối ưu của (Q) nên phải có  p 0(t0) y  + p1(t1) y1 + ... + p n(tn) y  ≤ p0(t0)y0 + p1(t1)y1 + ... + p n(tn)yn. 0 n y 0 Bằng cách thay y  = y . x  , yk = xk/(q0 + q 1x1 + ... + q nxn), k = 1, ... , n và y0 = 1/(q 0 + k 0 k q1x1 + ... + q nxn) ta thấy  y (p0(t0) + p 1(t1) x1 + ... + pn(tn) x  ) ≤ 0 n ≤ (p0(t0) + p 1(t1)x1 + ... + pn(tn)xn)/(q 0 + q1x1 + ... + qnxn).  Chia vế trái bất đẳng thức trên cho q Ty* = y (q0 + q1 x1 + ... + q n x  ) = 1 ta nhận được 0 n  p 0 ( t 0 )  p1 ( t 1 ) x 1    p n ( t n ) x  n  q 0  q1 x 1    qnx n ≤ p 0 ( t 0 )  p1 ( t 1 ) x 1    p n ( t n ) x n . q 0  q1x n    q n x n ∎ Đó là điều cần chứng minh. 2. BÀI TOÀN QUI HOẠCH TUYẾN TÍNH TƯƠNG ĐƯƠNG Ký hiệu k = min p k ( t ) , k = max p k ( t ) , k = 0, 1, ... , n (ak, bk tồn tại do p k(t) liên tục). a k  t bk a k  t b k Khi đó, các ràng buộc cuối của (Q) có thể viết lại dưới dạng pk(tk) = k + (k - k)k với 0 ≤ k ≤ 1, k = 0, 1, ... , n, 7 U u Q J 9 L K e F 7 K Q J / R Q J (1) 73 . • \ W X F { Q J W U u Q K N K R D K e F qk = ck + (dk - ck)k với 0 ≤ k ≤ 1, k = 0, 1, ... , n. Thay pk(tk), qk theo (1) - (2) vào (Q) ta nhận được bài toán: (R) (2) (0 + (0 - 0)0)y0 + (1 + (1 - 1)1)y1 + ... + (n + ( n - n)n)yn → min, (c0 + (d0 - c0)0)y0 + (c1 + (d 1 - c1)1)y1 + ... + (cn + (d n - cn)n)yn = 1, (3) - by0 + A1 y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. 0 ≤ k ≤ 1, 0 ≤ k ≤ 1, k = 0, 1, . . . , n. Ràng buộc đẳng thức (3) có thể viết lại thành (d0 - c0)0 y0 + (d1 - c1)1 y1 + ... + (dn - cn)nyn + c0 y0 + c1 y1 + ... + cnyn = 1, Do yk ≥ 0, 0 ≤ k ≤ 1, ck - dk ≤ 0 với mọi k = 0, 1, ... , n, nên ta có 1 ≥ 1 + (c0 - d0)0 y0 + (c1 - d1)1y1 + ... + (cn - dn)n yn ≥ ≥ 1 + (c0 - d0)y0 + (c1 - d1)y1 + ... + (cn - d n)yn. Thay só 1 ở biểu thức giữa của (5) bằng biểu thức (4) ta nhận được 1 ≥ c0 y0 + c1 y1 + ... + cnyn ≥ 1 + (c0 - d0)y0 + (c1 - d1)y1 + ... + (cn - d n)yn. Từ bất đẳng thức đầu và bất đẳng thức cuối của (6) cho thấy c0 y0 + c1 y1 + ... + cnyn ≤ 1, d0 y0 + d1 y1 + ... + dnyn ≥ 1. (4) (5) (6) (7) (8) Ngược lại, nếu có y = (y0, y1, ... , yn)T thoả mãn (7) - (8) thì đặt k =  ∀k, trong đó   0 khi c T y  1  1 khi d T y  1 , =   1  (c 0  c1 y1    c n y n )   (d 0  c 0 )  (d1  c1 ) y1    (d n  c n ) y n (9) ta nhận được q = c + (d - c) và qTy = 1, tức y, q sẽ thoả mãn (3). Do vậy bằng cách sử dụng (7) - (8) thay cho (3), bài toán (R) biến đổi thành bài toán qui hoạch phi tuyến: (S) (0 + (0 - 0)0)y0 + (1 + (1 - 1)1)y1 + ... + (n + ( n - n)n)yn → min, c0 y0 + c1 y1 + ... + cnyn ≤ 1, d0 y0 + d1 y1 + ... + dnyn ≥ 1. - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. 0 ≤ k ≤ 1, k = 0, 1, . . . , n. Hàm mục tiêu của bài toán này có dạng đặc biệt. Ta sẽ tìm cách thay nó bằng một hàm mục tiêu tuyến tính.  Thật vậy, giả sử y = ( y 0 , y1 , ... , y n ) là một lời giải chấp nhận được bất kỳ của (S) với 0 ≤ k ≤ 1, k - k ≥ 0 với mọi k = 0, 1, ... , n. Khi đó giá trị hàm mục tiêu tại y có đánh giá (0 + (0 - 0)0) y 0 + (1 + (1 - 1)1) y1 + ... + (n + (n - n)n) y n = = 0 y0 + 1 y1 + ... + n y n + (0 - 0)0 y0 + (1 - 1)1 y1 + ... + (n - n)n y n ≥ ≥ 0 y 0 + 1 y1 + ... + n y n (do y k , k, k - k ≥ 0 ∀k = 0, 1, ... , n). 74 7 U u Q J 9 L K e F 7 K Q J / R Q J . • \ W X F { Q J W U u Q K N K R D K e F Điều này chứng tỏ lời giải tối ưu của (S) đạt được khi mọi k = 0. Chính vì thế có thể thay thế bài toán tối ưu phi tuyến (S) bằng qui hoạch tuyến tính: 0 y0 + 1 y1 + ... + n yn → min, c0 y0 + c1y1 + ... + cnyn ≤ 1, d 0 y0 + d1y1 + ... + d nyn ≥ 1. - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. Như vậy, bài toán qui hoạch phân thức (P) qui được về bài toán qui hoạch tuyến tính (LP). Từ nghiệm tối ưu của bài toán tuyến tính này cùng với p k(tk) = k, tức tk = argmin pk(t) (tương ứng với k = 0), q k = ck + (d k - ck)k, k =  tính theo (9), ta thu được nghiệm tối ưu của bài toán (Q). Từ đó, theo Định lý 1 ta tính ra nghiệm tối ưu của bài toán ban đầu (P). (LP) 3. THUẬT TOÁN GIẢI Để đưa ra thuật toán giải, ta nhắc lại tóm tắt lập luận trên như sau. Bài toán qui hoạch phân thức: (P) min xk , tk , q k p 0 ( t 0 )  p1 ( t 1 ) x 1    p n ( t n ) x n , q 0  q1x1    q n x n A1x1 + ... + Anxn ≤ b, x1 ≥ 0, ... , xn ≥ 0. ak ≤ tk ≤ b k, ck ≤ qk ≤ dk, k = 0, 1, ... , n, trong đó ak, bk, ck, d k ∈ ℝ, Ak ∈ ℝm (k = 1, ... , n), b ∈ ℝm cho trước; pk(t) là hàm liên tục theo t ∈ [ak, bk]. Gỉa thiết: a) X = {x ∈ ℝn : A1x1 + ... + Anxn ≤ b, x ≥ 0} ≠ ∅, compac và b) q 0 + q1x1+ ... + qnxn > 0 ∀x = (x1, ... , xn)T ∈ X, ∀qk ∈ [ck, d k]. 1. Thực hiện phép biến đổi Charnes - Cooper 1 y0 = , yk = y0xk, k = 1, ... , n q 0  q1 x 1    q n x n bài toán ban đầu được đưa về dạng (các biến yk, tk, q k, k = 0, 1, ... , n) (Q) p0(t0)y0 + p1(t1)y1 + ... + p n(tn)yn → min, q0 y0 + q1 y1 + ... + qnyn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. ak ≤ tk ≤ b k, ck ≤ qk ≤ d k, k = 0, 1, . . . , n. 2. Gỉa sử k = min p k ( t ) , k = max p k ( t ) . Thực hiện phép đổi biến số a k t bk a k  t b k pk = k + (k - k)k, qk = ck + (d k - ck)k, k = 0, 1, . . . , n đưa bài toán (Q) về dạng (các biến yk, k, k, k = 0, 1, ... , n) (R) (0 + (0 - 0)0)y0 + (1 + (1 - 1)1)y1 + ... + (n + (n - n)n)yn → min, (c0 + (d 0 - c0)0)y0 + (c1 + (d1 - c1)1)y1 + ... + (cn + (d n - cn)n)yn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. 0 ≤ k ≤ 1, 0 ≤ k ≤ 1, k = 0, 1, . . . , n. 7 U u Q J 9 L K e F 7 K Q J / R Q J 75 . • \ W X F { Q J W U u Q K N K R D K e F 3. Thay ràng buộc đẳng thức trong (R) bởi hai bất đẳng thức tương đương ta có bài toán (S) (0 + (0 - 0)0)y0 + (1 + (1 - 1)1)y1 + ... + (n + (n - n)n)yn → min, c0 y0 + c1 y1 + ... + cnyn ≤ 1, d 0 y0 + d 1 y1 + ... + dnyn ≥ 1. - by0 + A1 y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. 0 ≤ k ≤ 1, k = 0, 1, . . . , n. 4. Cho mọi k = 0 ta đi đến bài toán qui hoạch tuyến tính (các biến yk, k = 0, 1, ... , n) (LP) 0 y0 + 1 y1 + ... + n yn → min, c0 y0 + c1y1 + ... + cnyn ≤ 1, d 0 y0 + d1y1 + ... + d nyn ≥ 1. - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. • Tóm lại, thuật toán là lập và giải qui hoạch tuyến tính này. Giả sử nhận được lời giải tối ưu:  y* = ( y , y1 , ... , y  )T. 0 n Khi đó, lời giải tối ưu của bài toán qui hoạch phân thức ban đầu là  x* = ( x1 , ... , x  )T với x  = y  / y ∀k = 1, ... , n. 0 n k k tk = arg min p k (t ) , qk = ck + (dk - ck)k, với k xác định theo (9). a k  t b k 4. VÍ DỤ MINH HOẠ Giải bài toán qui hoạch phân thức phi tuyến: min xk , t k , qk p 0 ( t 0 )  p1 ( t 1 ) x 1  p 2 ( t 2 ) x 2 q 0  q1 x1  q 2 x 2 với các điều kiện - x1 + x2 ≤ 2, x1 + 2x2 ≤ 10, x1 - 4x2 ≤ 4, x1 ≥ 0, x2 ≥ 0, 2 p0(t0) = t0 + 5, p 1(t1) = t 1 + 2, p 2(t2) = t 3 , 2 0 ≤ t0 ≤ 3, - 1 ≤ t1 ≤ 2, - 1 ≤ t2 ≤ 3, 1 ≤ q 0 ≤ 5, 2 ≤ q1 ≤ 4, 1 ≤ q2 ≤ 3. Miền chấp nhận được X của bài toán được vẽ ở Hình 1. Ta thấy 0 = min {p 0(t0)} = 5, 1 = min {p1(t1)} = 2, 2 = min {p2(t2)} = - 1. Thay bài toán cần giải bằng bài toán qui hoạch tuyến tính: 5y0 + 2y1 - y2 → min, y0 + 2y1 + y2 ≤ 1, 5y0 + 4y1 + 3y2 ≥ 1, - 2y0 - y1 + y2 ≤ 0, - 10y0 + y1 + 2y2 ≤ 0, - 4y0 + y1 - 4y2 ≤ 0, y0 ≥ 0, y1 ≥ 0, y2 ≥ 0.  Lời giải tối ưu của bài toán này là y = 0,04; y1 = 0,08; y = 0,16 với giá trị mục tiêu 0 2 tối ưu = 0,2. 76 7 U u Q J 9 L K e F 7 K Q J / R Q J