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

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. | . • \ 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 . 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