Tài liệu Một số thuật toán giải qui hoạch phân tuyến tính dựa trên phép biến đổi charnes cooper

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐINH VĂN DŨNG MỘT SỐ THUẬT TOÁN GIẢI QUI HOẠCH PHÂN TUYẾN TÍNH DỰA TRÊN PHÉP BIẾN ĐỔI CHARNES - COOPER LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐINH VĂN DŨNG MỘT SỐ THUẬT TOÁN GIẢI QUI HOẠCH PHÂN TUYẾN TÍNH DỰA TRÊN PHÉP BIẾN ĐỔI CHARNES - COOPER 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 - 2016 1 Mục lục Mở đầu 2 1 Phép biến đổi Charnes - Cooper 5 1.1 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Hàm phân thức afin . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Bài toán qui hoạch phân tuyến tính . . . . . . . . . . . . . . 10 1.4 Cách tiếp cận Charnes - Cooper . . . . . . . . . . . . . . . 13 2 1.4.1 Phép biến đổi Charnes - Cooper . . . . . . . . . . . 14 1.4.2 Thuật toán giải (LFP) . . . . . . . . . . . . . . . . . 21 1.4.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 22 Bài toán qui hoạch phân thức với các hệ số mục tiêu thay đổi 26 2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Bài toán qui hoạch tuyến tính tương đương . . . . . . . . . . 29 2.3 Thuật toán giải . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 35 Kết luận 41 Tài liệu tham khảo 43 2 Mở đầu Qui hoạch phân tuyến tính (Linear Fractional Programming, viết tắt là (LFP) là bài toán tìm cực tiểu (hay cực đại) của một hàm phân thức afin (tỉ số hai hàm tuyến tính afin) với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Qui hoạch phân tuyến tính là một trường hợp riêng của qui hoạch phi tuyến, thường dùng để mô hình hoá các bài toán thực tế với một hay nhiều mục tiêu (chẳng hạn lợi nhuận / chi phí, sản phẩm / số lao động, v.v ...) và được ứng dụng rộng rãi trong nhiều ngành khác nhau của kỹ thuật, kinh tế, tài chính, v.v ... Một trong những bài toán qui hoạch phân thức sớm nhất là mô hình cân bằng kinh tế do Von Neumann nêu ra năm 1973 (xem [5]). Charnes và Cooper [7] năm 1962 đã chỉ ra rằng qui hoạch phân tuyến tính có thể biến đổi tương đương về qui hoạch tuyến tính, nhờ phép đổi biến phi tuyến, gọi là phép biến đổi Charnes - Cooper. Về sau, phép biến đổi này được nhiều tác giả vận dụng và mở rộng. Nói riêng, các tác giả [4], [5] và [6] đã sử dụng nó để đưa ra thuật toán giải các dạng qui hoạch phân tuyến tính mở rộng như: qui hoạch phân tuyến tính với hệ số mục tiêu thay đổi, qui hoạch phân thức giá trị tuyệt đối, qui hoạch tích các phân thức tuyến tính, v.v ... Các thuật toán này đáng được chú ý tham khảo. Sau khi học được các chuyên đề về giải tích lồi, tối ưu hóa và các kiến thức có liên quan, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học, các kiến thức mở rộng và ứng dụng của những kiến thức này, chúng tôi 3 chọn đề tài luận văn: "Một số thuật toán giải qui hoạch phân tuyến tính dựa trên phép biến đổi Charnes - Cooper". Mục đích chính của luận văn là tìm hiểu và trình bày về bài toán qui hoạch phân tuyến tính và một số bài toán mở rộng, phép biến đổi Charnes - Cooper đưa br qui hoạch phân tuyến tính về bài toán qui hoạch tuyến tính tương đương và giới thiệu các thuật toán dựa trên phép biến đổi này để giải một số bài toán qui hoạch phân tuyến tính mở rộng. Cụ thể là bài toán qui hoạch phân tuyến tính với các hệ số mục tiêu thay đổi và bài toán qui hoạch phân tuyến tính với giá trị tuyệt đối. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [2] - [4] và [6]. Nội dung của luận văn gồm hai chương. Chương 1: Chương 1 “Phép biến đổi Charnes - Cooper” nhắc lại kiến thức về tập lồi đa diện và các tính chất đặc trưng của tập này; nhắc lại khái niệm hàm afin và các tính chất đáng chú ý của hàm afin, giới thiệu bài toán qui hoạch phân tuyến tính và cách tiếp cận Charnes - Cooper đưa bài toán phân tuyến tính về bài toán qui hoạch tuyến tính tương đương. Cuối chương, nêu thuật toán giải qui hoạch phân tuyến tính và đưa ra hai ví dụ minh họa cho hai tình huống tiêu biểu thường gặp của bài toán: Có nghiệm tối ưu hữu hạn và có nghiệm tối ưu tiệm cận với infimum hữu hạn đối với hàm mục tiêu của bài toán. Chương 2: Chương 2 "Bài toán qui hoạch phân thức với các hệ số mục tiêu thay đổi" trình bày một mở rộng cách tiếp cận đưa ra trong [4] tìm nghiệm tối ưu cho bài toán qui hoạch phân tuyến với các hệ số mục tiêu thay đổi trong một khoảng. Thuật toán giải dùng phép biến đổi Charnes - Cooper và đưa bài toán về một qui hoạch tuyến tính với nhiều hơn một biến và hai ràng buộc so với bài toán ban đầu. Cuối chương dẫn ra các ví dụ số minh 4 hoạ cho thuật toán giải trình bày. 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 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ả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Trần Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành cảm ơn các thầy giáo, 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 Hàn lâm 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. Thái Nguyên, tháng 01 năm 2016 Học viên Đinh Văn Dũng 5 Chương 1 Phép biến đổi Charnes - Cooper Chương này nhắc lại một số kiến thức cần thiết về tập lồi đa diện và các tính chất đáng chú ý của hàm phân thức afin (tỉ số của hai hàm tuyến tính afin), giới thiệu bài toán qui hoạch phân tuyến tính và phép biến đổi Charnes - Cooper đưa bài toán qui hoạch phân tuyến tính về bài toán qui hoạch tuyến tính. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1], [2], [3] và [6]. 1.1 Tập lồi đa diện Tập lồi đa diện là một dạng tập lồi có cấu trúc đơn giản và rất hay gặp trong lý thuyết tối ưu tuyến tính. Định nghĩa 1.1. Một tập lồi mà là giao của một số hữu hạn các nửa không gian đóng gọi là một tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính: ai1 x1 + ai2 x2 + · · · + ain xn ≤ bi , i = 1, 2, . . . , m, nghĩa là tập các x nghiệm đúng Ax ≤ b với a = (aij ∈ Rm×n ), b = (b1 , . . . , bm )T . (1.1) 6 Nhận xét 1.1. Do một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính, nên tập nghiệm của một hệ (hữu hạn) phương trình và bất phương trình tuyến tính cũng là một tập lồi đa diện: ai1 x1 + ai2 x2 + · · · + ain xn = bi , i = 1, 2, . . . , k, ai1 x1 + ai2 x2 + · · · + ain xn ≤ bi , i = k + 1, . . . , m, Một tập lồi đa diện có thể bị chặn hoặc không bị chặn (không giới nội). Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi. Các đa giác lồi theo nghĩa thông thường trong mặt phẳng hai chiều (tam giác, hình vuông, hình tròn, v.v ...) là những ví dụ cụ thể về đa diện lồi trong R2 . Cho D là một tập lồi đa diện xác định bởi hệ bất phương trình tuyến tính (1.1). Sau đây để đơn giản, ta giả thiết D không chứa đường thẳng nào (tức là @a, b ∈ D sao cho λa + (1 − λ)b ∈ D với mọi λ ∈ R). Hai yếu tố chính cấu tạo nên tập lồi đa diện D là các đỉnh và các cạnh vô hạn của D. Theo giải tích lồi [1, Hệ quả 2.6], có thể hiểu các khái niệm này như sau. Định nghĩa 1.2. Điểm x0 ∈ D được gọi là một đỉnh của D nếu  rank {ai : ai , x0 = bi } = n (với ai = (ai1 , . . . , ain ), i = 1, . . . , m). Định nghĩa tương đương: x0 ∈ D là một đỉnh của D nếu @x1 , x2 ∈ D, x1 6= x0 hoặc x2 6= x0 , và @λ ∈ (0, 1) sao cho x0 = λx1 + (1 − λ)x2 , nói một cách khác: x0 không thể là điểm nằm ở trong một đoạn thẳng nào đó nối hai điểm thuộc D. Định nghĩa 1.3. Đoạn thẳng [x1 , x2 ], x1 6= x2 , được gọi là một cạnh hữu hạn của D nếu x1 , x2 là các đỉnh của D và   rank {ai : ai , x1 = ai , x2 = bi } = n − 1. 7 Định nghĩa 1.4. Tia Γ = {x0 +λd : λ ≥ 0} ⊆ D, trong đó x0 ∈ D, d ∈ Rn , được gọi là một cạnh vô hạn của D nếu  rank {ai : ai , x = bi , ∀x ∈ Γ} = n − 1. Để hiểu rõ hơn về tập lồi đa diện ta cũng cần biết một số khái niệm sau đây. Định nghĩa 1.5. Véctơ d ∈ Rn , d 6= 0, được gọi là một hướng lùi xa của D nếu ∃x ∈ D sao cho {x + λd : λ ≥ 0} ⊆ D. Tập hợp các hướng lùi xa của D cộng với gốc 0 tạo thành một nón lồi đóng, gọi là nón lùi xa của D, ký hiệu rec D. Định nghĩa 1.6. Hướng lùi xa d của D được gọi là một hướng cực biên nếu không tồn tại hai hướng lùi xa khác d1 , d2 sao cho d = λd1 + λ2 d2 với λ1 , λ2 > 0. Có thể chứng minh được rằng tập lồi đa diện D không bị chặn khi và chỉ khi rec D 6= {0}, nghĩa là khi và chỉ khi D có ít nhất một hướng lùi xa. Hình 1.1: Đỉnh, cạnh vô hạn của tập lồi đa diện Trong các bài toán tối ưu, ta thường gặp tập lồi đa diện có dạng S = {x ∈ Rn : Ax ≤ b, x ≥ 0} với A ∈ Rm×n , b ∈ Rm }, 8 tức S là tập nghiệm không âm của một hệ (hữu hạn) bất phương trình tuyến tính. Tập này không chứa đường thẳng nào (do x ≥ 0) nên S có đỉnh [1, tr. 59]. Từ các định nghĩa nêu trên cho thấy: a) Điểm x0 ∈ S là một đỉnh của S khi và chỉ khi hệ véctơ  {ak : ak , x0 = bk } ∪ {ek : x0k = 0} có hạng bằng n. b) Các hướng cực biên (chuẩn hóa) của S là các nghiệm cơ sở của hệ Ay ≤ 0, eT y = 1, y ≥ 0, trong đó eT = (1, . . . , 1). c) Giả sử tia Γ = {x0 + λd : λ ≥ 0}, trong đó x0 là một đỉnh và d là một hướng cực biên của S. Khi đó Γ là một cạnh vô hạn của S khi và chỉ khi  rank ({ak : ak , x = bk , ∀x ∈ Γ} ∪ {ek : xk = 0, ∀x ∈ Γ}) = n − 1. 1.2 Hàm phân thức afin Hàm phân thức afin thường gặp trong các bài toán tối ưu. Hàm này có dạng f (x) = p(x) pT x + α = T , q(x) q x+β trong đó p, q ∈ Rn , α, β ∈ R và dom f = {x ∈ Rn : q T x + β > 0}. Ký hiệu S là tập lồi sao cho q(x) = q T x + β 6= 0 với mọi x ∈ S. Nếu q(x) có dấu khác nhau trên S, tức là có x, y ∈ S sao cho q T x + β > 0 và q T y + β < 0 thì do hàm q(x) liên tục nên tồn tại z ∈ [x, y], tức z ∈ S, sao cho q(z) = 0. Vì thế, không giảm tổng quát, ta có thể giả thiết q(x) > 0 với mọi x ∈ S. Trường hợp q(x) < 0 với mọi x ∈ S thì nhân cả tử số p(x) và 9 mẫu số q(x) của hàm f (x) với (- 1) sẽ có q(x) > 0 với mọi x ∈ S. Định lý sau nêu tính chất đơn điệu theo phương của hàm phân thức afin. p(x) là hàm đơn điệu trên mỗi đoạn thẳng q(x) nằm trọn trong tập lồi S = {x : q T x + β > 0}. Định lí 1.1. ([2, tr. 78]). f (x) = Chứng minh. Lấy hai điểm tùy ý a, b ∈ S và tính giá trị hàm f tại điểm x bất kỳ trên đoạn thẳng nối a và b, tức là x = λa + (1 − λ)b với 0 ≤ λ ≤ 1. Ta thấy f (x) = p[λa + (1 − λ)b] λp(a) + (1 − λ)p(b) = . q[λa + (1 − λ)b] λq(a) + (1 − λ)q(b) Đạo hàm của f theo λ:     p(a) p(b) q(a)q(b) − p(b)q(a) df (x) 1 = = 2 × . dλ q (x) q(a) q(b) q 2 (x) Dấu của đạo hàm phụ thuộc dấu của biểu thức [p(a)q(b) − p(b)q(a)]. Vì thế, khi λ thay đổi trong đoạn [0, 1] thì hàm f (x) hoặc tăng hoặc giảm hoặc đồng nhất bằng hằng số trên [a, b]. Ta nhắc lại rằng hàm khả vi f : Rn → R được gọi là giả lồi nếu với mọi x, y ∈ S ta có ∇f (x)T (y − x) ≥ 0 kéo theo f (y) ≥ f (x), nghĩa là nếu f (y) < f (x) thì ∇f (x)T (y − x) < 0. Hàm f được gọi là giả lõm nếu −f là giả lồi. Định lý sau nêu một tính chất quan trọng khác của hàm phân thức afin. (pT x + α) và S là tập lồi sao cho Định lí 1.2. ([3, tr. 703]). Giả sử f (x) = T (q x + β) (q T x + β) 6= 0 trên S. Khi đó, hàm f (x) vừa giả lồi, vừa giả lõm trên S. Chứng minh. Ta để ý rằng hoặc q T x + β > 0 với mọi x ∈ S hoặc q T x + β < 0 với mọi x ∈ S, vì nếu trái lại sẽ có a ∈ S, b ∈ S sao cho q T a + β > 0 và q T b + β < 0, do đó sẽ có q T z + β = 0 với z là một tổ hợp 10 lồi của a và b, trái với giả thiết định lý. Trước hết ta chứng minh f giả lồi. Thật vậy, giả sử x, y ∈ S thỏa mãn ∇f (x)T (y − x) ≥ 0. Ta cần chỉ rõ f (y) ≥ f (x). Ta có ∇f (x) = (q T x + β)p − (pT x + α)q . (q T x + β)2 Do ∇f (x)T (y − x) ≥ 0 và do (q T x + β)2 > 0 nên 0 ≤ [(q T x + β)p − (pT x + α)q]T (y − x) = (pT y + α)(q T x + β) − (q T y + β)(pT x + α) Vì thế, (pT y + α)(q T x + β) ≥ (q T y + β)(pT x + α). Nhưng do (q T x + β) và (q T y + β) cùng dương hoặc cùng âm nên chia cả hai vế cho (q T x + β)(q T y + β) > 0 ta nhận được pT y + α pT x + α ≥ T , tức là f (y) ≥ f (x). qT y + β q y+β Vì thế, f giả lồi. Tương tự, có thể chứng minh được rằng ∇f (x)T (y − x) ≤ 0 kéo theo f (y) ≤ f (x). Vì thế, f giả lõm và định lý được chứng minh. 1.3 Bài toán qui hoạch phân tuyến tính Một cách tổng quát có thể phát biểu bài toán như sau. Cho tập lồi C ⊆ Rn và các hàm f, g, hj : Rn → R (j = 1, . . . , m). Xét bài toán tối ưu với hàm mục tiêu phân thức (tỉ số của hai hàm số), ký hiệu bài toán (FP) (FP) f (x) , x∈S g(x) inf 11 trong đó S = {x ∈ C : hj (x) ≤ 0, j = 1, . . . , m}. Ta phân biệt các loại bài toán sau: • Khi f, g và hj là các hàm tuyến tính afin thì (FP) gọi là bài toán qui hoạch phân tuyến tính. • Khi f và g là các hàm toàn phương và hj là các hàm tuyến tính afin thì (FP) gọi là bài toán qui hoạch phân thức toàn phương. • Khi f ≥ 0 là hàm lồi, g > 0 là hàm lõm và hj là các hàm lồi thì (FP) gọi là bài toán qui hoạch phân thức lồi. Trong bài toán (FP) chỉ xét một hàm phân thức. Tuy nhiên, trong nhiều ứng dụng ta còn có thể xét nhiều hàm phân thức. Chẳng hạn, • Qui hoạch phân thức suy rộng: λ∗ = min max  x∈S 1≤i≤k  fi (x) (gi > 0 ∀i). gi (x) • Qui hoạch tổng các hàm phân thức: ∗ λ = min x∈S k X fi (x) i=1 gi (x) (gi > 0 ∀i). • Qui hoạch phân thức đa mục tiêu:   f1 (x) fk (x) ∗ λ = min ,..., (gi > 0 ∀i). x∈S g1 (x) gk (x) Luận văn này chủ yếu tập trung xét bài toán qui hoạch phân tuyến tính: (LFP) min {f (x) = p(x) pT x + α = T :Ax ≤ b, x ≥ 0, q(x) q x+β (1.2) q T x + β > 0}, trong đó p, q ∈ Rn , α, β ∈ R, A ∈ Rm×n , b ∈ Rm . Trong nhiều ứng dụng thường tập ràng buộc S = {x ∈ Rn : Ax ≤ 0, x ≥ 0} kéo theo q T x+β > 0. 12 Tương tự, có thể xét bài toán tìm cực đại: max {f (x) : x ∈ S}. Như vậy, qui hoạch phân tuyến tính là bài toán tìm cực tiểu (hay cực đại) của một hàm phân thức afin (tỉ số của hai hàm tuyến tính afin) trên một tập lồi đa diện (xác định bởi một hệ phương trình hay bất phương trình tuyến tính). Qui hoạch tuyến tính là một trường hợp riêng của qui hoạch phân tuyến tính khi q = 0 và β = 1. Trong [2] phân tích một số trường hợp riêng khác cho phép đưa bài toán qui hoạch phân tuyến tính về bài toán tuyến tính thích hợp. Bây giờ trong bài toán (1.2) ta giả thiết q(x) ≡ q T x + β 6= 0 với mọi x ∈ S. Nếu q(x) có dấu khác nhau, tức có x1 , x2 ∈ S sao cho q T x1 + β > 0 và q T x2 + β < 0 thì do hàm q(x) liên tục nên tồn tại x ∈ [x1 , x2 ], tức x ∈ S, sao cho q(x) = 0, trái với giả thiết. Vì thế, không mất tổng quát, ta có thể giả thiết q(x) > 0 với mọi x ∈ S (trường hợp q(x) < 0, nhân cả tử số p(x) và mẫu số q(x) của hàm mục tiêu f (x) với (- 1), sẽ có q(x) > 0). Hơn nữa, ta giả thiết m ≤ n và rank A = m. Sau đây là một số khái niệm và định nghĩa cần thiết, tương tự như trong lý thuyết qui hoạch tuyến tính. Trong bài toán (LFP), f (x) gọi là hàm mục tiêu. Tập S gọi là tập ràng buộc hay miền chấp nhận được. Véctơ x ∈ S gọi là một phương án hay nghiệm chấp nhận được, một phương án mà đồng thời là đỉnh của tập ràng buộc S gọi là một phương án cực biên hay nghiệm cơ sở. Phương án đạt giá trị nhỏ nhất của hàm mục tiêu f (x) gọi là một phương án tối ưu hay nghiệm tối ưu. Ta nói bài toán (1.2) là bất khả thi hay không chấp nhận được nếu tập S = ∅, bài toán gọi là giải được nếu tập S 6= ∅ và hàm f (x) có infimum hữu hạn (đối với bài toán min) trên S. Nếu hàm mục tiêu f (x) không bị chặn 13 dưới trên S thì bài toán được gọi là không bị chặn dưới (inf f (x) = −∞). x∈S Với bài toán qui hoạch phân tuyến tính, có thể xảy ra các trường hợp sau: a) Tập ràng buộc S = ∅ (bài toán bất khả thi). b) Nghiệm tối ưu duy nhất (đạt tại một đỉnh của S). c) Vô số nghiệm tối ưu hữu hạn (đạt tại một diện bị chặn của S). d) Có nghiệm tối ưu hữu hạn và vô cực (đạt tại một diện vô hạn của S). e) Nghiệm tối ưu tiệm cận (f ∗ = inf f (x) > −∞ và x∈S ∗ ∗ ∗ @x ∈ S : f (x ) = f ). f) Không có nghiệm tối ưu (inf f (x) = −∞ - bài toán không bị chặn dưới). x∈S 1.4 Cách tiếp cận Charnes - Cooper A. Charnes và W. Cooper (1962) đã chỉ ra rằng bài toán qui hoạch phân tuyến tính với tập ràng buộc khác rỗng có thể đưa được về bài toán qui hoạch tuyến tính, nhờ phép đổi biến số, gọi là biến đổi Charnes - Cooper. Ta nhắc lại, bài toán qui hoạch phân tuyến tính có dạng:   pT x + α (LFP) min f (x) = T : Ax ≤ b, x ≥ 0 , q x+β trong đó p, q là các véctơ trong Rn , α, β là các số thực, A là ma trận cấp m × n, b là véctơ trong Rm (p, q, α, β, A, b cho trước), x ∈ Rn là véctơ biến cần tìm. Ký hiệu S = {x ∈ Rn : Ax ≤ b, x ≥ 0}. Ta giả thiết tập S 6= ∅. Nhận xét 1.2. Bài toán sẽ không có nghĩa (không xác định) nếu ∃x0 ∈ S, q T x0 + β = 0. 14 Do S là tập lồi và q T x + β là hàm liên tục nên nếu ∃x1 , x2 ∈ S với q T x1 + β > 0 và q T x2 + β < 0 thì sẽ tìm được x0 ∈ [x1 , x2 ] ⊆ S sao cho q T x0 + β = 0. Vì thế để bài toán được hoàn toàn xác định ta phải có hoặc q T x + β > 0 ∀x ∈ S hoặc q T x + β < 0 ∀x ∈ S. Có thể kiểm tra điều này bằng cách giải qui hoạch tuyến tính qmin := min {q T x + β : x ∈ S} hoặc qmax := max {q T x + β : x ∈ S}. (qmin > 0 ⇒ q T x + β > 0 ∀x ∈ S hoặc qmax < 0 ⇒ q T x + β < 0 ∀x ∈ S). Không giảm tổng quát, từ đây về sau ta luôn giả thiết q T x + β > 0 ∀x ∈ S (nếu cần, có thể đổi dấu tử số và mẫu số của hàm f (x)). 1.4.1 Phép biến đổi Charnes - Cooper Dùng phép đổi biến số T = 1 > 0, y = tx ∈ Rn , ∀x ∈ S T q x+β và nhân ràng buộc Ax ≤ b với t > 0, ta đưa bài toán (LFP) về bài toán tuyến tính (LP) min {g(y, t) ≡ pT y + αt : Ay − bt ≤ 0, q T y + βt = 1, y ≥ 0, t ≥ 0}. So với (LFP), bài toán (LP) có thêm một biến và một ràng buộc mới. Giữa hai bài toán (LFP) và (LP) có mối quan hệ được nêu ra trong các mệnh đề sau. Mệnh đề 1.1. Với các ký hiệu trên, ta có các kết luận sau đây: a) Nếu x0 là một nghiệm chấp nhận được của (LFP) thì (y 0 , t0 ) là một 15 nghiệm chấp nhận được của (LP) với 1 t0 = q T x0 +β , y 0 = x 0 t0 và g(y 0 , t0 ) = pT y 0 + αt0 = t0 (pT x0 + α) = f (x0 ). y0 b) Nếu (y , t ) là nghiệm chấp nhận được của (LP) và t > 0 thì x = 0 t là nghiệm chấp nhận được của (LFP) và 0 0 0 0 f (x0 ) = t0 (pT x0 + α) = pT y 0 + αt0 = g(y 0 , t0 ). Chứng minh. a) Do x0 thỏa mãn Ax0 ≤ b, x0 ≥ 0 và t0 = 1 >0 (q T x0 + β) nên y 0 = x0 t0 sẽ thỏa mãn y 0 ≥ 0, Ay 0 − bt0 ≤ 0 và q T y 0 + βt0 = 1, nghĩa là (y 0 , t0 ) là một nghiệm chấp nhận được của (LP). Hơn nữa, ta có hệ thức g(y 0 , t0 ) = pT y 0 + αt0 = t0 (pT x0 + α) = f (x0 ). y0 b) Từ Ay − bt ≤ 0, y ≥ 0 và t > 0 suy ra x = 0 thỏa mãn t Ax0 ≤ b, x0 ≥ 0, tức x0 là một nghiệm chấp nhận được của (LFP). Hơn 0 0 0 0 0 nữa, từ q T y 0 + βt0 = 1 ta có t0 (q T x0 + β) = 1 và (pT x0 + α) f (x ) = T 0 = t0 (pT x0 + α) = pT y 0 + αt0 = g(y 0 , t0 ). (q x + β) 0 y∗ Mệnh đề 1.2. a) Nếu (y , t ) là nghiệm tối ưu của (LP) và t > 0 thì x = ∗ t là nghiệm tối ưu của (LFP). ∗ ∗ ∗ ∗ b) Giả sử (LFP) chấp nhận được. Khi đó, (LP) không bị chặn dưới khi và chỉ khi (LFP) không bị chặn dưới. Chứng minh. a) Do (y ∗ , t∗ ) là một nghiệm chấp nhận được của (LP) và y∗ ∗ ∗ t > 0 nên theo kết luận b) của Mệnh đề 1.1, x = ∗ là một nghiệm chấp t ∗ nhận được của (LFP). Ta chứng minh x là nghiệm tối ưu của (LFP). 16 Thật vậy, lấy bất kỳ x ∈ S, tức Ax ≤ b, x ≥ 0. Do giả thiết q T x + β > 0 x 1 nên (y, t) với y = T ,t= T sẽ là một nghiệm chấp nhận (q x + β) (q x + β) được của (LP). Mặt khác, (y ∗ , t∗ ) là nghiệm tối ưu của (LP) nên pT y ∗ + αt∗ ≤ pT y + αt. Bằng cách thay y ∗ = x∗ t∗ , y = 1 x và t = ta thấy (q T x + β) (q T x + β) t∗ (pT x∗ + α) ≤ (pT x + α) (q T x + α) Chia vế trái bất đẳng thức trên cho q T x∗ + βt∗ = t∗ (q T x∗ + β) = 1 ta được pT x∗ + α pT x + α f (x ) = T ∗ ≤ f (x) = T q x +β q x+β ∗ Chứng tỏ x∗ là nghiệm tối ưu của (LFP). Nếu hàm mục tiêu của (LP) không bị chặn dưới thì tồn tại (y 0 , t0 ) sao cho Ay 0 − bt0 ≤ 0, q T y 0 + βt0 = 0, pT y 0 + αt0 < 0, y 0 ≥ 0, t0 ≥ 0. (1.3) y0 ta sẽ có Ax0 ≤ b, 0 t 0 T 0 x ≥ 0, q x + β = 0. Điều này trái với giả thiết không tồn tại x0 ∈ S như Từ đó suy ra t0 = 0, vì nếu t0 > 0 thì đặt x0 = thế. Do đó, (1.3) tương đương với các hệ thức: Ay 0 ≤ 0, y 0 ≥ 0, q T y 0 = 0, pT y 0 < 0, Giả sử x0 là một nghiệm chấp nhận được bất kỳ của (LFP). Xét x(θ) = x0 + θy 0 , ta thấy x(θ) là nghiệm chấp nhận được của (LFP) với mọi θ ≥ 0 và pT x(θ) + α pT x0 + α + θpT y 0 f (x(θ)) = T = → −∞ khi θ → +∞, q x(θ) + β q T x0 + β 17 nghĩa là (LFP) không bị chặn dưới. Ngược lại, nếu hàm mục tiêu của (LFP) không bị chặn dưới thì pT x(θ) + α < − θ. ∀θ > 0, ∃x(θ) sao cho Ax(θ) ≤ b, x(θ) ≥ 0 và T q x(θ) + β Xét dãy (y(θ), t(θ)), trong đó t(θ) = 1 và y(θ) = x(θ)t(θ). +β Mỗi phần tử thuộc dãy này là một nghiệm chấp nhận được của (LP) và (q T x(θ) pT x(θ) + α p y(θ) + αt(θ) = T < − θ. q x(θ) + β T Vì thế, hàm mục tiêu của (LP) cũng không bị chặn dưới. Mệnh đề 1.3. Nếu (LFP) có nghiệm chấp nhận được, (LP) có nghiệm tối ưu và mọi nghiệm tối ưu đều có t = 0 thì giá trị mục tiêu của (LFP) có infimum (cận dưới đúng) hữu hạn, nhưng infimum đó không đạt tới được. Đó là trường hợp (LFP) có nghiệm tối ưu tiệm cận. Trong trường hợp này, có thể tạo ra các nghiệm ε - tối ưu với bất kỳ ε > 0, nghĩa là trong S tồn tại một cạnh vô hạn mà dọc theo cạnh đó giá trị mục tiêu của (LFP) tiến dần về cận dưới đúng nói trên. Chứng minh. Do (LFP) chấp nhận được và (LP) có nghiệm tối ưu nên theo kết luận ở phần b) của Mệnh đề 1.2, (LFP) không thể là bài toán không bị chặn (tức là phải có inf f (x) > −∞). Nếu (LFP) có nghiệm tối ưu x∗ thì x∈S 1 t∗ = T ∗ , y ∗ = x∗ t∗ là một nghiệm tối ưu của (LP) với t∗ > 0, (q x + β) điều này trái với giả thiết. Do vậy (LFP) có nghiệm tối ưu tiệm cận và giá trị mục tiêu của (LFP) có infimum hữu hạn, ký hiệu là w∗ , và (LFP) không có nghiệm chấp nhận được nào có giá trị mục tiêu bằng w∗ . Bây giờ giả sử (y ∗ , 0) là một nghiệm tối ưu của (LP). Khi đó Ay ∗ ≤ 0, q T y ∗ = 1, y ∗ ≥ 0. 18 Ta sẽ chứng minh pT y ∗ = w∗ . Thật vậy, trước hết ta chỉ ra (i) pT y ∗ ≤ w∗ : Giả sử xk là một nghiệm εk - tối ưu của (LFP) với p T xk + α ≤ w k + εk . f (x ) = T k q x +β k Theo kết luận a) của Mệnh đề 1.1 thì (y k , tk ) với tk = 1 (q T xk + β) và y k = xk tk là một nghiệm chấp nhận được đối với (LP) và pT x k + α g(y , t ) = p y + αt = T k ≤ wk + εk . q x +β k k T k k Do bất đẳng thức trên đúng với mọi εk > 0 nên cho k → ∞ ta thấy (i) đúng. (ii) Bây giờ ta chỉ ra pT y ∗ ≥ w∗ : Giả sử trái lại pT y ∗ < w∗ . Xét x(θ) = x0 + θy ∗ với θ ≥ 0 và x0 ∈ S. Kiểm tra cho thấy x(θ) ∈ S với mọi θ ≥ 0 và f (x(θ)) = pT (x0 + θy ∗ ) + α pT x0 + α + θpT y ∗ = → pT y ∗ khi θ → ∞. T 0 ∗ T 0 q (x + θy ) + β q x +β+θ và θ có thể chọn sao cho giá trị này nhỏ hơn w∗ . Nhưng điều này sẽ dẫn tới mâu thuẫn. Vì thế (ii) đúng và điều khẳng định được chứng minh (pT y ∗ = w∗ ). Nghiệm ε - tối ưu đã nói trước đây của (LFP được sinh ra bằng cách chọn giá trị θ đủ lớn thích hợp trong x(θ) = x0 + θy ∗ . Mệnh đề 1.4. Nếu S 6= ∅ và q T x + β = 0 với mọi x ∈ S thì (LP) không có nghiệm chấp nhận được (bài toán (LP) là bất khả thi). Chứng minh. Theo kết luận b) của Mệnh đề 1.1, nếu (LP) có nghiệm chấp y nhận được (y, t) với t > 0 thì x = ∈ S và từ q T y + βt = 1 suy ra t 1 q T x + β = 6= 0, trái với giả thiết của mệnh đề. Còn nếu (LP) có nghiệm t chấp nhận được (y, 0) thì Ay ≤ 0, y ≥ 0 và q T y = 1. Khi đó, lấy bất