Ứ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