ĐẠ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.