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

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) kkk q,t,x min nn110 nnn11100 xqxqq x)t(px)t(p)t(p     , với các điều kiện A1x1 + ... + Anxn ≤ b, x1 ≥ 0, ... , xn ≥ 0. ak ≤ tk ≤ bk, 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) q0 + q1x1+ ... + qnxn > 0 ∀x = (x1, ... , xn)T ∈ X, ∀qk ∈ [ck, dk]. 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 y0 = nn110 xqxqq 1   > 0, 72 (P) được viết lại thành bài toán: p0(t0)y0 + p1(t1)y0x1 + ... + pn(tn)y0xn → min, q0y0 + q1y0x1 + ... + qny0xn = 1, A1y0x1 + ... + Any0xn ≤ by0, x1 ≥ 0, ... , xn ≥ 0, y0 ≥ 0. ak ≤ tk ≤ bk, ck ≤ qk ≤ dk, k = 0, 1, ... , n. Bằng cách thay các biến xk bởi yk = y0xk 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 + ... + pn(tn)yn → min, q0y0 + q1y1 + ... + qnyn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. ak ≤ tk ≤ bk, ck ≤ qk ≤ dk, 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* = ( 0y , 1y , ... ,  ny ) T là một nghiệm tối ưu của bài toán (Q) thì 0y > 0 và x* = (  1x ,  2x , ... ,  nx ) T với kx =  ky /  0y sẽ là một nghiệm tối ưu của bài toán (P) ban đầu. Chứng minh. Trước tiên ta chứng minh 0y > 0. Thật vậy, nếu  0y = 0 thì do q Ty* = 1 nên đặt z = ( 1y , ... ,  ny ) ta có z ≠ 0 và z thỏa mãn Az ≤ 0, z ≥ 0. Khi đó z là một hướng lùi xa 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ó 0y ≠ 0. Do  0y ≥ 0 nên  0y > 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),  0y > 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/(q0 + q1x1 + ... + qnxn) > 0, yk = y0xk ≥ 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ó p0(t0) 0y + p1(t1)  1y + ... + pn(tn)  ny ≤ p0(t0)y0 + p1(t1)y1 + ... + pn(tn)yn. Bằng cách thay ky =  0y .  kx , yk = xk/(q0 + q1x1 + ... + qnxn), k = 1, ... , n và y0 = 1/(q0 + q1x1 + ... + qnxn) ta thấy  0y (p0(t0) + p1(t1)  1x + ... + pn(tn)  nx ) ≤ ≤ (p0(t0) + p1(t1)x1 + ... + pn(tn)xn)/(q0 + q1x1 + ... + qnxn). Chia vế trái bất đẳng thức trên cho qTy* = 0y (q0 + q1  1x + ... + qn  nx ) = 1 ta nhận được     nn110 nnn11100 xqxqq x)t(px)t(p)t(p   ≤ nnn10 nnn11100 xqxqq x)t(px)t(p)t(p     . Đó 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 = kk bta k )t(pmin  , k = kk bta k )t(pmax  , k = 0, 1, ... , n (ak, bk tồn tại do pk(t) liên tục). 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, (1) 73 qk = ck + (dk - ck)k với 0 ≤ k ≤ 1, k = 0, 1, ... , n. (2) Thay pk(tk), qk theo (1) - (2) vào (Q) ta nhận được bài toán: (R) (0 + (0 - 0)0)y0 + (1 + (1 - 1)1)y1 + ... + (n + (n - n)n)yn → min, (c0 + (d0 - c0)0)y0 + (c1 + (d1 - c1)1)y1 + ... + (cn + (dn - cn)n)yn = 1, (3) - by0 + A1y1 + ... + 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)0y0 + (d1 - c1)1y1 + ... + (dn - cn)nyn + c0y0 + c1y1 + ... + cnyn = 1, (4) 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)0y0 + (c1 - d1)1y1 + ... + (cn - dn)nyn ≥ ≥ 1 + (c0 - d0)y0 + (c1 - d1)y1 + ... + (cn - dn)yn. (5) Thay só 1 ở biểu thức giữa của (5) bằng biểu thức (4) ta nhận được 1 ≥ c0y0 + c1y1 + ... + cnyn ≥ 1 + (c0 - d0)y0 + (c1 - d1)y1 + ... + (cn - dn)yn. (6) Từ bất đẳng thức đầu và bất đẳng thức cuối của (6) cho thấy c0y0 + c1y1 + ... + cnyn ≤ 1, (7) d0y0 + d1y1 + ... + dnyn ≥ 1. (8) Ngược lại, nếu có y = (y0, y1, ... , yn)T thoả mãn (7) - (8) thì đặt k =  ∀k, trong đó  =            nnn11100 nn110 T T y)cd(y)cd()cd( )ycycc(1 1ydkhi1 1yckhi0   , (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, c0y0 + c1y1 + ... + cnyn ≤ 1, d0y0 + d1y1 + ... + 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 = ( 0y , 1y , ... , ny ) 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) 0y + (1 + (1 - 1)1) 1y + ... + (n + (n - n)n) ny = = 0 0y + 1 1y + ... + n ny + (0 - 0)0 0y + (1 - 1)1 1y + ... + (n - n)n ny ≥ ≥ 0 0y + 1 1y + ... + n ny (do ky , k, k - k ≥ 0 ∀k = 0, 1, ... , n). 74 Đ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: (LP) 0y0 + 1y1 + ... + nyn → min, c0y0 + c1y1 + ... + cnyn ≤ 1, d0y0 + d1y1 + ... + dnyn ≥ 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 pk(tk) = k, tức tk = argmin pk(t) (tương ứng với k = 0), qk = ck + (dk - 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). 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) kq,t,x kk min nn110 nnn11100 xqxqq x)t(px)t(p)t(p     , A1x1 + ... + Anxn ≤ b, x1 ≥ 0, ... , xn ≥ 0. ak ≤ tk ≤ bk, ck ≤ qk ≤ dk, k = 0, 1, ... , n, trong đó ak, bk, ck, dk ∈ ℝ, 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) q0 + q1x1+ ... + qnxn > 0 ∀x = (x1, ... , xn)T ∈ X, ∀qk ∈ [ck, dk]. 1. Thực hiện phép biến đổi Charnes - Cooper y0 = nn110 xqxqq 1   , yk = y0xk, k = 1, ... , n bài toán ban đầu được đưa về dạng (các biến yk, tk, qk, k = 0, 1, ... , n) (Q) p0(t0)y0 + p1(t1)y1 + ... + pn(tn)yn → min, q0y0 + q1y1 + ... + qnyn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. ak ≤ tk ≤ bk, ck ≤ qk ≤ dk, k = 0, 1, . . . , n. 2. Gỉa sử k = kk bta k )t(pmin  , k = kk bta k )t(pmax  . Thực hiện phép đổi biến số pk = k + (k - k)k, qk = ck + (dk - 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 + (d0 - c0)0)y0 + (c1 + (d1 - c1)1)y1 + ... + (cn + (dn - cn)n)yn = 1, - by0 + A1y1 + ... + Anyn ≤ 0, y0 ≥ 0, y1 ≥ 0, ... , yn ≥ 0. 0 ≤ k ≤ 1, 0 ≤ k ≤ 1, k = 0, 1, . . . , n. 75 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, c0y0 + c1y1 + ... + cnyn ≤ 1, d0y0 + d1y1 + ... + dnyn ≥ 1. - by0 + A1y1 + ... + 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) 0y0 + 1y1 + ... + nyn → min, c0y0 + c1y1 + ... + cnyn ≤ 1, d0y0 + d1y1 + ... + dnyn ≥ 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* = ( 0y ,  1y , ... ,  ny ) T. 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* = ( 1x , ... ,  nx ) T với kx =  ky /  0y ∀k = 1, ... , n. tk = kk bta k )t(pminarg  , qk = ck + (dk - ck)k, với k xác định theo (9). 4. VÍ DỤ MINH HOẠ Giải bài toán qui hoạch phân thức phi tuyến: kkk q,t,x min 22110 22211100 xqxqq x)t(px)t(p)t(p   với các điều kiện - x1 + x2 ≤ 2, x1 + 2x2 ≤ 10, x1 - 4x2 ≤ 4, x1 ≥ 0, x2 ≥ 0, p0(t0) = t0 + 5, p1(t1) = 21t + 2, p2(t2) = 3 2t , 0 ≤ t0 ≤ 3, - 1 ≤ t1 ≤ 2, - 1 ≤ t2 ≤ 3, 1 ≤ q0 ≤ 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 {p0(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à 0y = 0,04;  1y = 0,08;  2y = 0,16 với giá trị mục tiêu tối ưu = 0,2. 76 Từ đó suy ra lời giải tối ưu của bài toán ban đầu là  1x =   0 1 y y = 2, 2x =   0 2 y y = 4. với cùng giá trị mục tiêu tối ưu fmin = (5 + 2×2 - 1×4)/(5 + 4×2 + 3×4) = 5/25 = 0,2. Hình 1. Tập ràng buộc X Để kiểm chứng cho lời giải tối ưu trên, lấy bất kỳ tk, qk trong khoảng biên thiên đã cho và giải bài toán, ta sẽ thấy lời giải tối ưu nhận được sẽ không tốt hơn lời giải tối ưu đã có. Chẳng hạn, với t0 = t1 = t2 = 1 thì p0 = 6, p1 = 3, p2 = 1, q0 = 2, q1 = 3, q2 = 2 ta giải bài toán: Xx min  21 21 x2x32 xx36   với cùng điều kiện x ∈ X (Hình 1), cụ thể là - x1 + x2 ≤ 2, x1 + 2x2 ≤ 10, x1 - 4x2 ≤ 4, x1 ≥ 0, x2 ≥ 0. Đưa bài toán này về qui hoạch tuyến tính tương đương (biến đổi Charnes - Cooper): y0 + 3y1 + y2 → min, 2y0 + 3y1 + 2y2 = 1, - 2y0 - y1 + y2 ≤ 0, - 10y0 + y1 + 2y2 ≤ 0, - 4y0 + y1 - 4y2 ≤ 0, y0 ≥ 0, y1 ≥ 0, y2 ≥ 0, Giải bài toán tuyến tính này ta nhân được lời giải tối ưu  0y = 0,0625;  1y = 0,125;  2y = 0,25. Từ đó suy ra lời giải tối ưu của bài toán phân tuyến tính cần giải là  1x =   0 1 y y = 2, 2x =   0 2 y y = 4. với giá trị mục tiêu tối ưu = (6 + 3×2 + 1×4)/(2 + 3×2 + 2×4) = 16/16 = 1 > fmin = 0,2. ∎ x2 x1 X (0, 2) (0, 0) (4, 0) (8, 1) (2, 4) 72 72 77 TÀI LIỆU THAM KHẢO [1] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy. Giáo trình tối ưu phi tuyến. Nxb Đại học Quốc gia Hà Nội, 2011. [2] E. B. Bajalinov. Linear - Fractional Programming: Theory, Methods, Applications and Software. Kluwer Academic Publishers 2003. [3] M. S. Bazara et al., Nonlinear Programming: Theory and Algorithms. 3rd Edition. A John Willey & Sons, Inc., Publication, 2006. [4] M. Borza, A. S. Rambely and M. Saraj. Solving Linear Fractional Programming Problems with Interval Coefficients in the Objective Function. Applied Mathematical Sciences, Vol. 6, 2012, no. 69, 3443 - 3452. SOLVING A CLASS OF NONLINEAR FRACTIONAL PROGRAMMING PROBLEMS Tran Vu Thieu - Thang Long University (Dept of Math) Abstract. In this paper we present a method for solving a class of nonlinear fractional programming problem. Using Charnes - Cooper's transformation (see [2], p. 54), the problem is reduced to an equivalent nonlinear programming problem and then the nonlinear problem is transformed into a linear programming problem with one more variable and two more constraints compare to the initial problem. Finally, numerical examples are given to illustrate the proposed method. BC_LFP_TL_2014.doc (Tue Oct 07, 2014) trvuthieu@gmail.com - 0913.222.991 78