Tài liệu ứng dụng qui hoạch tuyến tính trong phân tích gói dữ liệu

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN LÊ TUÂN ỨNG DỤNG QUI HOẠCH TUYẾN TÍNH TRONG PHÂN TÍCH GÓI DỮ LIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN LÊ TUÂN ỨNG DỤNG QUI HOẠCH TUYẾN TÍNH TRONG PHÂN TÍCH GÓI DỮ LIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số : 60 46 01 12 NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS. Trần Vũ Thiệu THÁI NGUYÊN - 2017 i MỤC LỤC Trang MỤC LỤC............................................................................................................... i DANH MỤC CÁC HÌNH VẼ .............................................................................. ii MỞ ĐẦU ................................................................................................................ 1 Chƣơng 1: KIẾN THỨC CHUẨN BỊ ................................................................. 4 1.1. TẬP LỒI ĐA DIỆN ......................................................................................... 4 1.2. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ...................................................... 7 1.2.1. Nội dung bài toán .......................................................................................... 7 1.2.2. Các tính chất cơ bản ...................................................................................... 8 1.3. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU ............................... 10 1.4. QUAN HỆ ĐỐI NGẪU TRONG QUI HOẠCH TUYẾN TÍNH ................. 12 Chƣơng 2: PHƢƠNG PHÁP PHÂN TÍCH GÓI DỮ LIỆU ........................... 15 2.1. PHƢƠNG PHÁP PHÂN TÍCH BẰNG ĐỒ THỊ .......................................... 15 2.1.1. Đối tƣợng nghiên cứu ................................................................................. 15 2.1.2. Hiệu quả tƣơng đối ..................................................................................... 16 2.1.3. Trƣờng hợp một đầu vào - một đầu ra ........................................................ 16 2.2. MÔ HÌNH CHARNES - COOPER - RHODES ............................................. 22 2.3. MÔ HÌNH CHARNES - COOPER - RHODES ĐỐI NGẪU ........................ 29 2.4. ĐIỂM MẠNH VÀ YẾU CỦA PHƢƠNG PHÁP DEA ................................ 35 KẾT LUẬN .......................................................................................................... 38 TÀI LIỆU THAM KHẢO .................................................................................. 39 ii DANH MỤC CÁC HÌNH VẼ Hình 1.1. Tập ràng buộc của bài toán ở Ví dụ 1.2. .............................................. 10 Hình 1.2. Tập ràng buộc của cặp bài toán đối ngẫu ở Ví dụ 1.5. ......................... 14 Hình 2.1. Biên giới hiệu quả. ................................................................................ 19 Hình 2.2. Phƣơng pháp đồ thị. .............................................................................. 21 1 MỞ ĐẦU Qui hoạch tuyến tính (LP) có nhiều ứng dụng trong thực tiễn, đặc biệt là trong phân tích định lƣợng các hoạt động kinh tế. Luận văn này đề cập tới một ứng dụng của qui hoạch tuyến tính (còn ít đƣợc đề cập đến) trong vấn đề phân tích gói dữ liệu, nhằm giúp đánh giá hiệu quả tƣơng đối, dựa trên tập hợp dữ liệu thu thập đƣợc của các đơn vị khác nhau cùng tham gia trong một lĩnh vực hoạt động nào đó, chẳng hạn các chi nhánh ngân hàng trong một thành phố, các đơn vị sản xuất trong một xí nghiệp, các lớp trong một trƣờng học, v.v ... Phân tích gói dữ liệu (Data Envelopment Analysis, gọi tắt là DEA) là một phƣơng pháp toán học ngày càng phổ biến trong nghiên cứu kinh tế. DEA đƣợc dùng để đánh giá hoạt động của các cơ sở sản xuất, các ngân hàng, bệnh viện, trƣờng học, ... Cách tiếp cận thống kê truyền thống thƣờng có xu hƣớng đánh giá so với cơ sở sản xuất đại diện (mẫu) hoặc trung bình. Trái lại, DEA so sánh mỗi cơ sở sản xuất với chỉ một cơ sở sản xuất "tốt nhất" (xu hƣớng tối ƣu hóa). Với các cơ sở sản xuất, quá trình sản xuất ở mỗi cơ sở sử dụng một tập hợp các vật vào - yếu tố sản xuất (inputs) và sản xuất ra một tập hợp các vật ra - sản phẩm (outputs). Với các ngân hàng, mỗi ngân hàng có một số nhân viên, một số diện tích giao dịch và một số ngƣời quản lý nhất định (vật vào). Có một số chỉ tiêu để đánh giá hoạt động của mỗi ngân hàng, ví nhƣ lƣợng tiền gửi, số tiền cho vay, v.v ... (vật ra). DEA cố gắng xác định xem ngân hàng nào hoạt động hiệu quả nhất và chỉ ra sự hoạt động không hiệu quả cụ thể của các ngân hàng khác. Giả thiết cơ bản ẩn sau phƣơng pháp này là nếu cơ sở sản xuất nào đó, chẳng hạn A, có khả năng sản xuất Y(A) đơn vị sản phẩm (vật ra) bằng cách sử dụng X(A) đơn vị vật vào, thì các cơ sở sản xuất khác cũng sẽ làm đƣợc nhƣ vậy, nếu nhƣ họ hoạt động có hiệu quả. Khi đó, cơ sở sản xuất A, B và các cơ sở sản xuất khác có thể kết hợp lại tạo nên một cơ sở sản xuất "hợp" với các vật vào hợp và các vật ra hợp. Do cơ sở sản xuất hợp này không nhất thiết tồn tại, nên nó thƣờng đƣợc gọi là cơ sở sản xuất ảo. 2 Cốt lõi của phân tích gói dữ liệu chính là tìm ra đƣợc cơ sở sản xuất ảo "tốt nhất" cho mỗi cơ sở sản xuất thực. Nếu cơ sở ảo này tốt hơn cơ sở ban đầu, do làm đƣợc nhiều vật ra hơn với cùng một lƣợng vật vào, hoặc làm đƣợc cùng một lƣợng vật ra nhƣ thế nhƣng tốn ít vật vào hơn, thì cơ sở sản xuất ban đầu đó là kém hiệu quả. Sự tinh tế của DEA là ở chỗ đƣa ra đƣợc các cách khác nhau, theo đó các cơ sở sản xuất A và B có thể mở rộng hay thu hẹp quy mô và kết hợp lại. Để làm đƣợc điều này, phân tích gói dữ liệu (DEA) phải sử dụng đến công cụ toán học mà trƣớc hết là qui hoạch toán học, nói riêng là qui hoạch tuyến tính. Vì thế chúng tôi chọn đề tài luận văn: "Ứng dụng qui hoạch tuyến tính trong phân tích gói dữ liệu" nhằm mục đích tìm hiểu và trình bày ý tƣởng, nội dung phƣơng pháp phân tích gói dữ liệu, thông qua phân tích các ví dụ cụ thể từ đơn giản (một vật vào một hay hai vật ra) đến phức tạp (nhiều vật vào - nhiều vật ra) và tổng quát hóa ở dạng ma trận; đồng thời tìm hiểu mô hình, phƣơng pháp xây dựng hiệu quả tƣơng đối và tìm ra cơ sở sản xuất tốt nhất, theo nghĩa đạt hiệu quả cao nhất. Luận văn đƣợc viết dựa trên các tài liệu tham khảo [1] - [5], trong đó chủ yếu là [3] và [5]. Nội dung luận văn gồm hai chƣơng. • Chƣơng 1 "Kiến thức chuẩn bị" nhắc lại các kiến thức cần thiết về tập lồi đa diện, bài toán qui hoạch tuyến tính, bài toán đối ngẫu của nó và các quan hệ đối ngẫu trong qui hoạch tuyến tính. • Chƣơng 2 “Phân tích gói dữ liệu” trình bày nội dung phân tích gói dữ liệu và ví dụ, mô hình Charnes–Cooper–Rhodes và mô hình Charnes–Cooper–Rhodes đối ngẫu, phân tích những điểm mạnh và điểm yếu của phƣơng pháp DEA. Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng nhƣ trong soạn thảo văn bản chắc chắn không tránh khỏi có những sai sót nhất định. Tác giả luận văn rất mong nhận 3 đƣợc sự góp ý của các thầy, cô và các bạn đồng nghiệp để luận văn đƣợc hoàn thiện hơn. Nhân dịp này, 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 đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán-Tin, Trƣờng Đại học Khoa học Thái Nguyên và của Viện Toán học, Viện Công nghệ thông tin thuộ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 5 năm 2017 Tác giả luận văn Nguyễn Lê Tuân 4 Chƣơng 1 KIẾN THỨC CHUẨN BỊ 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ề bài toán qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu và về các quan hệ đối ngẫu trong qui hoạch tuyến tính. Nội dung của chƣơng tham khảo chủ yếu từ các tài liệu [1], [2] và [5]. 1.1. TẬP LỒI ĐA DIỆN Trƣớc hết chúng tôi nhắc lại các khái niệm cơ bản liên quan tới các tập lồi. Định nghĩa 1.1. Tập C  ℝn đƣợc gọi là một tập lồi nếu a + (1 - )b  C với mọi a, b  C và mọi 0 ≤  ≤ 1. Nói cách khác, tập C là lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Nói riêng, tập , tập gồm duy nhất một phần tử và toàn bộ không gian ℝn là các tập lồi. Ví dụ 1.1. Các tập sau đây đều là tập lồi: a) Tập afin là tập chứa trọn đƣờng thẳng đi qua hai điểm bất kỳ thuộc nó. b) Siêu phẳng là tập có dạng H = {x  ℝn : aTx = , a  ℝn \ {0},   ℝ}. c) Nửa không gian đóng H1 = {x  ℝn : aTx ≤ }, H2 = {x  ℝn : aTx ≥ }. d) Nửa không gian mở K1 = {x  ℝn : aTx < }, K2 = {x  ℝn : aTx > }. e) Hình cầu mở B(a, r) = {x  ℝn : ||x - a|| < r} (a  ℝn, r > 0 cho trƣớc). f) Tập lồi đa diện D = {x  ℝn : Ax ≤ b}, trong đó A  ℝm×n, b  ℝm. g) Nón lồi đa diện K = {x  ℝn : Ax ≤ 0}, trong đó A  ℝm×n, 0  ℝm. • Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau đây: a) Giao của một họ bất kỳ các tập lồi là một tập lồi. b) Tổng của hai tập lồi và hiệu của hai tập lồi cũng là các tập lồi. 5 c) Nếu C  ℝm, D  ℝn lồi thì tích C × D = {(x, y) : x  C, y  D} là một tập lồi trong ℝm+n. (Có thể mở rộng cho tích nhiều tập lồi). d) Tập M là một tập afin khi và chỉ khi M = a + L với a  M và L là một không gian con, gọi là không gian con song song với M, hay tƣơng đƣơng: M là một tập afin khi và chỉ khi M là tập nghiệm của một hệ phƣơng trình tuyến tính, tức có biểu diễn M = {x  ℝn : Ax = b, A  ℝm×n, b  ℝm}. Giao của một số bất kỳ các tập afin là một tập afin. Định nghĩa 1.2. a) Điểm x  ℝn có dạng x = 1a1 + 2a2 + ... + kak với ai  ℝn, i ≥ 0, 1 + ... + k = 1, gọi là một tổ hợp lồi của các điểm a1, a2, ... , ak. b) Điểm x  ℝn có dạng x = 1a1 + 2a2 + ... + kak với ai  ℝn, 1 + 2 + ... + k = 1, gọi là một tổ hợp afin của các điểm a1, a2, ... , ak. c) Điểm x  ℝn có dạng x = 1a1 + 2a2 + ... + kak với ai  ℝn, i ≥ 0, gọi là một tổ hợp tuyến tính không âm hay tổ hợp nón của các điểm a1, a2, ... , ak. Định nghĩa 1.3. Cho tập E bất kỳ trong ℝn. a) Giao của tất cả các tập afin chứa E gọi là bao afin của E, ký hiệu là aff E. Đó là tập afin nhỏ nhất chứa E. b) Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, ký hiệu là conv E. Đó là tập lồi nhỏ nhất chứa E. Định nghĩa 1.4. a) Thứ nguyên (hay số chiều) của một tập afin M, ký hiệu dim M, là số chiều của không gian con song song với nó. Qui ƣớc dim  = - 1. b) Thứ nguyên (hay số chiều) của một tập lồi C, ký hiệu dim C, là thứ nguyên hay số chiều của bao afin aff C của nó. Một tập lồi C trong ℝn gọi là có thứ nguyên đầy đủ (full rank) nếu dim C = n. Định nghĩa 1.5. Một tập con K của ℝn đƣợc gọi là một nón (cone) hay tập nón (mũi tại 0) nếu với mọi x  K và mọi  > 0 thì x  K. Nón K đƣợc gọi là một nón lồi (convex cone) nếu K là tập lồi. 6 Tiếp theo chúng tôi nêu lại các khái niệm có liên quan tới tập lồi đa diện. Định nghĩa 1.6. Tập lồi đa diện là giao của một số hữu hạn các nửa không gian đóng. 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: ai1x1 + ai2x2 + ... + ainxn ≤ bi, i = 1, 2, . . . , m, (1.1) nghĩa là tập các x nghiệm đúng Ax ≤ b với A = (aij) ∈ Rm×n, b = (b1, ... , bm)T. Nhận xét 1.1. Do một phƣơng trình tuyến tính tƣơng đƣơng với 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: Một tập lồi đa diện có thể bi chặn (giới nội) 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, ...) là những ví dụ cụ thể về đa diện lồi trong ℝ2. 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  ∈ ℝ). 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. Có thể hiểu các khái niệm này nhƣ sau. Định nghĩa 1.7. Điểm x0 ∈ D đƣợc gọi là một đỉnh của D nếu rank {ai : = bi} = n (với ai = (ai1, . . . , ain)T, i = 1, ... , m). Định nghĩa tƣơng đƣơng: x0 ∈ D là một đỉnh của D nếu x0 không thể là điểm nằm ở bên trong một đoạn thẳng nào đó nối hai điểm thuộc D. Định nghĩa 1.8. Đoạn thẳng [x1, x2], x1 ≠ 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 : = = bi} = n - 1. Định nghĩa 1.9. Tia  = {x0 + d :  ≥ 0} ⊆ D, trong đó x0 ∈ D, d ∈ ℝn, đƣợc gọi là một cạnh vô hạn của D nếu 7 rank {ai : = 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.10. Véctơ d ∈ ℝn, d ≠ 0, đƣợc gọi là một hướng lùi xa của D nếu ∃x0 ∈ D sao cho {x0 + 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.11. 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 = 1d1 + 2d2 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 ≠ {0}, nghĩa là khi và chỉ khi D có ít nhất một hƣớng lùi xa. 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 ∈ ℝn : Ax ≤ b, x ≥ 0} với A ∈ ℝm×n, b ∈ ℝm, 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. Từ các định nghĩa nêu trên cho thấy: a) x0 ∈ S là một đỉnh ⇔ rank ({ak : = bk} ∪ {ek : x 0k = 0}) = 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, eTy = 1, y ≥ 0, trong đó eT = (1, ... , 1)  ℝn. 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 : = bk, ∀x ∈ } ∪ {ek : xk = 0, ∀x ∈ }) = n - 1. 1.2. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 1.2.1. Nội dung bài toán Bằng các phép biến đổi đơn giản, một bài toán qui hoạch tuyến tính bất kỳ có thể đƣa đƣợc về một trong hai dạng chính sau đây. 8 • Dạng chuẩn tắc: min {f(x) = cTx : Ax ≥ b, x ≥ 0}, trong đó A ∈ ℝm×n, b ∈ ℝm, c  ℝn, x ≥ 0 có nghĩa x ∈ ℝ n . Trong bài toán này tập ràng buộc D = {x ∈ ℝn : Ax ≥ b, x ≥ 0} là một tập lồi đa diện. • Dạng chính tắc: min {f(x) = cTx : Ax = b, x ≥ 0}, trong đó A, b, c và x đƣợc xác định nhƣ ở trên. Trong bài toán này tập ràng buộc D = {x ∈ ℝn : Ax = b, x ≥ 0} cũng là một tập lồi đa diện. Có thể dễ dàng chuyển từ dạng chuẩn tắc sang dạng chính tắc và ngƣợc lại. Trong các bài toán trên f(x) đƣợc gọi là hàm mục tiêu. Mỗi bất phƣơng trình (Ax)i ≥ bi hay phƣơng trình (Ax)i = bi gọi là một ràng buộc chính, xj ≥ 0, j = 1, ... , n, gọi là các ràng buộc không âm hay ràng buộc về dấu. Véctơ (điểm) x ∈ D gọi là một nghiệm chấp nhận được hay một phương án. Một phƣơng án đạt cực tiểu của hàm mục tiêu f(x) gọi là một phương án tối ưu hay một nghiệm tối ưu của bài toán. Với mỗi bài toán qui hoạch tuyến tính, chỉ có một trong ba khả năng: a) Bài toán không có nghiệm chấp nhận đƣợc (miền ràng buộc D = ). b) Bài toán có trị tối ƣu vô cực (f(x)  -  đối với bài toán min). c) Bài toán có nghiệm tối ƣu (min {f(x) : x  D} > - ). 1.2.2. Các tính chất cơ bản Định lý sau nêu điều kiện để một qui hoạch tuyến tính có nghiệm tối ƣu. Định lý 1.1. Nếu một qui hoạch tuyến tính có nghiệm chấp nhận được và nếu hàm mục tiêu bị chặn dưới trên tập ràng buộc (đối với bài toán min) thì qui hoạch đó chắc chắn có nghiệm tối ưu. 9 Định lý 1.2. Nếu x0 là một phương án tối ưu của bài toán qui hoạch tuyến tính dạng bất kỳ và nếu x1, x2 (x1 ≠ x2) là hai phương án thỏa mãn x0 = x1 + (1  )x2, 0 <  < 1, thì x1, x2 cũng là các phương án tối ưu của bài toán. Định nghĩa 1.12. Một nghiệm chấp nhận đƣợc x ∈ D mà đồng thời là một đỉnh của D đƣợc gọi là một nghiệm cơ sở hay một phương án cực biên, nghĩa là x không thể biểu diễn đƣợc dƣới dạng một tổ hợp lồi của bất kỳ hai nghiệm chấp nhận đƣợc (phƣơng án) nào khác của bài toán. Định lý sau nêu một tính chất đặc trƣng cho phƣơng án cực biên (nghiệm cơ sở) của bài toán qui hoạch tuyến tính chính tắc với giả thiêt m ≤ n và rank(A) = m. Định lý 1.3. Để một nghiệm chấp nhận được x = { x1 , x 2 , ... , x n } của qui hoạch tuyến tính chính tắc là nghiệm cơ sở thì cần và đủ là các véctơ cột Aj của ma trận A ứng với các thành phần x j > 0 là độc lập tuyến tính. Ngƣời ta phân ra hai loại nghiệm cơ sở: không suy biến nếu nghiệm đó có số thành phần dƣơng bằng m và suy biến nếu nó có số thành phần dƣơng nhỏ hơn m. Định lý sau cho thấy qui hoạch tuyến tính chính tắc có phƣơng án cực biên. Định lý 1.4. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có ít nhất một phương án thì nó cũng có phương án cực biên, nghĩa là tập ràng buộc D có đỉnh. Định lý sau cho phép tìm phƣơng án tối ƣu của bài toán qui hoạch tuyến tính chính tắc trong số các phƣơng án cực biên của bài toán (số này hữu hạn). Định lý 1.5. Nếu bài toán qui hoạch tuyến tính chính tắc có phương án tối ưu thì nó cũng có phương án cực biên tối ưu. Ví dụ 1.2. Xét bài toán qui hoạch tuyến tính f(x) =  x1 + x2  min, với các điều kiện: x1  3x2  2, x1  x2  4,  3x1 + x2  3, x1  0, x2  0. 10 Tập ràng buộc của bài toán vẽ ở Hình 1.1. Bài toán này có nghiệm cực tiểu. Theo Định lý 1.5, nghiệm tối ƣu của bài toán đạt đƣợc tại một trong các đỉnh. Tọa độ các đỉnh: O = (0, 0), A = (2, 0), B = (5, 1), C = (0, 3). Tính giá trị hàm mục tiêu tại các đỉnh này, ta đƣợc: f(O) = 0, f(A) =  2, f(B) =  4, f(C) = 3. Từ đó cho thấy cực tiểu của hàm f đạt tại đỉnh B = (5, 1) với giá trị cực tiểu fmin =  4. Hình 1.1. Tập ràng buộc của bài toán ở Ví dụ 1.2. 1.3. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH ĐỐI NGẪU Đối ngẫu là phƣơng pháp mà ứng với mỗi bài toán qui hoạch tuyến tính đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán qui hoạch khác (gọi là bài toán đối ngẫu) sao cho từ nghiệm của bài toán này ta sẽ thu đƣợc thông tin về nghiệm của bài toán kia. Sau đây là hai dạng cặp bài toán đối ngẫu thƣờng gặp. • Đối ngẫu của qui hoạch tuyến tính dạng chuẩn tắc (qui hoạch gốc) (P) min {f(x) = cTx : Ax ≥ b, x ≥ 0} là bài toán qui hoạch tuyến tính (qui hoạch đối ngẫu): (Q) max {g(y) = bTy : ATy ≤ c, y ≥ 0} (AT là ma trận chuyển vị của ma trận A). Ví dụ 1.3. Đối ngẫu của bài toán qui hoạch tuyến tính chuẩn tắc f(x) = 25x1 + 10x2  min, x1 + 3x2  20, x1 + x2  30, 11 2x1 + x2  40, x1  0, x2  0, là bài toán qui hoạch tuyến tính: g(y) = 20y1 + 30y2 + 40y3  max, y1 + y2 + 2y3  25, 3y1 + y2 + y3  10, y1  0, y2  0, y3  0. • Đối ngẫu của qui hoạch tuyến tính dạng chính tắc (qui hoạch gốc): (P) min {f(x) = cTx : Ax = b, x ≥ 0} là bài toán qui hoạch tuyến tính (qui hoạch đối ngẫu): (Q) max {g(y) = bTy : ATy ≤ c}. Ví dụ 1.4. Đối ngẫu của bài toán qui hoạch tuyến tính chính tắc f(x) = 0,6x1 + 0,2x4 + 0,8x5  min, 2x1 + x3 + x5 = 150, + 2x2 + x5 = 300, x2 + 2x3 + 3x4 = 500, xj  0, j = 1, 2, 3, 4, 5. là bài toán qui hoạch tuyến tính: g(y) = 150y1 + 300y2 + 500y3  max, 2y1  0,6 2y2 + y3  0, y1 + 2y3  0, 3y3  0,2 y1 + y2  0,8. Dễ kiểm tra lại rằng lấy đối ngẫu của bài toán đối ngẫu ta đƣợc lại bài toán gốc. Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu nhau. 12 1.4. QUAN HỆ ĐỐI NGẪU TRONG QUI HOẠCH TUYẾN TÍNH Các kết quả dƣới đây đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ. Định lý 1.6 (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì f(x) = c1x1 + c2x2 + ... + cnxn ≥ g(y) = b1y1 + b2y2 + ... + bmym, nghĩa là giá trị mục tiêu của một phương án gốc bất kỳ (bài toán min) không nhỏ hơn giá trị mục tiêu của một phương án đối ngẫu bất kỳ (bài toán max). Định lý 1.7 (Đối ngẫu mạnh). Nếu một qui hoạch có nghiệm tối ưu thì qui hoạch đối ngẫu của nó cũng có nghiệm tối ưu và hai giá trị tối ưu bằng nhau. Các định lý trên cho thấy quan hệ sau giữa hai qui hoạch gốc và đối ngẫu. Định lý 1.8 (Định lý đối ngẫu cơ bản). Đối với một cặp bài toán qui hoạch tuyến tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây: a) Cả hai bài toán đều không có nghiệm chấp nhận được. b) Cả hai bài toán đều có nghiệm chấp nhận được. Khi đó, cả hai đều có nghiệm tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau. c) Một bài toán có nghiệm chấp nhận được và bài toán kia không có nghiệm chấp nhận được. Khi đó, bài toán có nghiệm chấp nhận được sẽ có giá trị tối ưu vô cực (+ ∞ hay - ∞ tùy theo bài toán max hay min). Các ví dụ sau đây minh hoạ cho các tình huống a) - c) nêu trên. a) Bài toán gốc và bài toán đối ngẫu không có phƣơng án. f(x) = x1  min, g(y) = y1 + y2  max, x1 + x2  1, y1  y2 = 1, x1  x2  1, y1  y2 = 0, x1, x2 tuỳ ý. y1  0, y2  0. 13 b) Bài toán gốc và bài toán đối ngẫu có phƣơng án. f(x) = 5x1 + 10x2  min, g(y) = 14y1 + 12y2  max, 2x1 + 3x2  14, x1 + 4x2  12, x1  0, x2  0. 2y1 + y2  5, 3y1 + 4y2  10, y1  0, y2  0. Phƣơng án tối ƣu của hai bài toán là x* = (4; 2) và y* = (2; 1) với f(x*) = g(y*) = 40. c) Bài toán gốc và bài toán đối ngẫu đều không có phƣơng án tối ƣu. f(x) = x1  min, g(y) = y1 + y2  max, x1 + x2  1, y1  y2  1, x1  x2  1, y1  y2  0, x1  0, x2  0. y1  0, y2  0. Quan hệ giữa cặp bài toán đối ngẫu nhau còn thể hiện ở định lý sau đây. Định lý 1.9 (Định lý độ lệch bù yếu). Một cặp nghiệm chấp nhận được x, y của hai qui hoạch tuyến tính đối ngẫu nhau (P) và (Q) là cặp nghiệm tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: n yi(  a ij x j  bi) = 0 i = 1, 2, ... , m ⇔ yT(Ax  b) = 0, j1 xj(cj  m  a ij y i ) = 0 j = 1, 2, ... , n ⇔ xT(c  ATy) = 0. i 1 Ví dụ 1.5. Xét cặp bài toán đối ngẫu chuẩn tắc: min {4x1 : x1 + x2  2, x1  x2  2, xj  0, x2  0} và max {2y1 + 2y2 : y1 + y2  4, y1  y2  0, y1  0, y2  0}. Áp dụng Định lý 1.9 vào cặp bài toán đối ngẫu cho ở Ví dụ 1.5, ta thấy x và y là nghiệm tối ƣu của các bài toán gốc và đối ngẫu tƣơng ứng khi và chỉ khi x, y thỏa mãn hệ điều kiện sau: 14 x1 + x2  2, x1  x2  2, x1  0, x2  0 (chấp nhận đƣợc gốc), y1 + y2  4, y1  y2  0, y1  0, y2  0 (chấp nhận đƣợc đối ngẫu), y1(x1 + x2  2) = 0, y2(x1  x2  2) = 0, (độ lệch bù yếu), x1(4  y1  y2) = 0, x2( y1 + y2) = 0 (độ lệch bù yếu). Kiểm tra trực tiếp cho thấy rằng x* = (2, 0) và y* = (0, 4) thỏa mãn hệ điều kiện trên. Vì thế, x* là phƣơng án tối ƣu của bài toán gốc và y* là phƣơng án tối ƣu của bài toán đối ngẫu tƣơng ứng và ta có hệ thức f(x *) = g(y*) = 8. x2 4 2 y2 y* 2 0 4 2 Bài toán gốc x1 x* 0 Bài toán đối ngẫu 4 y1 Hình 1.2. Tập ràng buộc của cặp bài toán đối ngẫu ở Ví dụ 1.5. Tóm tắt chƣơng. Chƣơng này đã trình bày tóm tắt một số kiến thức cơ bản cần thiết về tập lồi đa diện, bài toán qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu và các quan hệ đối ngẫu trong qui hoạch tuyến tính. Các kiến thức này sẽ đƣợc dùng đến ở chƣơng sau. 15 Chƣơng 2 PHƢƠNG PHÁP PHÂN TÍCH GÓI DỮ LIỆU Chƣơng này trình bày nội dung cơ bản của phƣơng pháp phân tích gói dữ liệu, bắt đầu từ phƣơng pháp đồ thị đơn giản, sau đó là mô hình Charnes– Cooper–Rhodes và mô hình Charnes–Cooper–Rhodes đối ngẫu. Cuối chƣơng nêu một số lĩnh vực áp dụng và lƣu ý các điểm mạnh và điểm yếu của phân tích gói dữ liệu. Nội dung của chƣơng tham khảo chủ yếu từ các tài liệu [3] - [5]. 2.1. PHƢƠNG PHÁP PHÂN TÍCH BẰNG ĐỒ THỊ Trƣớc hết ta tìm hiểu một số khái niệm dùng trong phân tích gói dữ liệu. 2.1.1. Đối tượng nghiên cứu Phân tích gói dữ liệu (Data Envelopment Analysis, gọi tắt là DEA), đôi khi còn đƣợc gọi là phân tích biên giới (Frontier Analysis), do Charnes, Cooper và Rhodes (gọi tắt CCR) đề xuất năm 1978. DEA là một kỹ thuật đo hiệu suất, đƣợc sử dụng để đánh giá hiệu quả hoạt động tƣơng đối của các đơn vị (sản xuất, kinh doanh, dịch vụ, nghiên cứu, ...), ví dụ nhƣ: các cơ sở sản xuất, các ngân hàng, các chi cục thuế, bệnh viện, trƣờng học, cơ sở quốc phòng, cửa hàng, v.v ... Để cho gọn, ta sẽ gọi chung tất cả các đối tƣợng cần nghiên cứu, đánh giá hiệu quả hoạt động là các "đợn vị" (unit). Các đơn vị này có đặc điểm chung là đều sử dụng một tập hợp các vật vào - yếu tố sản xuất (inputs - đầu vào) để tạo ra một tập hợp các vật ra - sản phẩm (outputs - đầu ra). Với ngân hàng, mỗi đơn vị có một số nhân viên, một số diện tích giao dịch và một số ngƣời quản lý nhất định (đầu vào). Có một số chỉ tiêu phản ánh hoạt động của mỗi ngân hàng, ví dụ nhƣ số ngƣời đến giao dịch, lƣợng tiền gửi, số tiền cho vay hàng tháng, v.v ... (đầu ra). Nhƣ vậy, "đơn vị" là một thuật ngữ trừu tƣợng dùng để ám chỉ các đối tƣợng nghiên cứu nào đó, có thể biến đổi "đầu vào" thành "đầu ra" và DEA là phƣơng pháp phân tích định lƣợng, chỉ sử dụng dữ liệu liên quan tới đầu vào và đầu ra của các đơn vị đƣợc xét mà không sử dụng thêm thông tin nào khác. 16 DEA có thể đƣợc áp dụng cho nhiều tình huống đa dạng, với điều kiện là: 1. Các đơn vị đƣợc xét có cùng các đầu vào và đầu ra nhƣ nhau. 2. Các đầu vào và đầu ra của các đơn vị có thể đo đƣợc bằng các con số. 2.1.2. Hiệu quả tương đối DEA sẽ nói về hiệu quả tƣơng đối (relative efficiency) của các đơn vị đƣợc xét. Hiệu quả (efficiency) đƣợc xác định theo công thức toán học sau đây: hiệu quả = đâu và o . đâu ra Trong định nghĩa hiệu quả trên đây, ta không thấy có liên hệ gì đến tính tƣơng đối. Quả thực là nhƣ vậy. Tính tƣơng đối sẽ đƣợc đề cập sau. Trong mục nhỏ sau ta sẽ minh họa DEA thông qua một ví dụ đơn giản liên quan đến các chi nhánh ngân hàng ở một vùng X nào đó. Nội dung trình bày sau đây là cách tiếp cận bằng đồ thị của DEA. Điều này rất có lợi để có thể hình dung cách tiếp cận toán học tổng quát của DEA tiếp sau. 2.1.3. Trường hợp một đầu vào - một đầu ra Ví dụ 2.1. Quan sát 4 chi nhánh ngân hàng ở một vùng X. Với mỗi chi nhánh ta có số liệu về đầu ra duy nhất: số giao dịch cá nhân thực hiện trong một tuần. Ta cũng có số liệu về đầu vào duy nhất: số nhân viên của mỗi chi nhánh. Số liệu đã có đƣợc ghi lại trong bảng sau: Giao dịch Số nhân cá nhân viên R 125 18 A 44 16 K 80 17 H 23 11 Chi nhánh