Bài giảng Khoa học dịch vụ: Chương 4 - PGS.TS. Hà Quang Thụy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:65

Thêm vào BST

Báo xấu

34
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Khoa học dịch vụ - Chương 4: Tối ưu hóa trong dịch vụ. Những nội dung chính được trình bày trong chương gồm có: Năm yêu tố quan trọng trong tối ưu hóa, phân loại bài toán tối ưu hóa, bài toán tối ưu hóa từng gặp, quy hoạch tuyến tính, dạng mạng đặc biệt, giải bài toán nguyên, mười quy tắc hình thức hóa bài toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khoa học dịch vụ: Chương 4 - PGS.TS. Hà Quang Thụy

NHẬP MÔN KHOA HỌC DỊCH VỤ CHƯƠNG 4. TỐI ƯU HÓA TRONG DỊCH VỤ PGS. TS. HÀ QUANG THỤY HÀ NỘI 09-2018 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI 1
Nội dung chương ➢Giới thiệu ➢Năm yêu tố quan trọng trong tối ưu hóa ➢Phân loại bài toán tối ưu hóa ➢Bài toán tối ưu hóa từng gặp ➢Quy hoạch tuyến tính ➢Dạng mạng đặc biệt ➢ Giải bài toán nguyên ➢Mười quy tắc hình thức hóa bài toán KHDV 2015 – Chương 2 - Trang 2
1. Giới thiệu ➢ Châm ngôn ❖ “Trong cuộc sống, dù làm việc gì thì hãy làm tốt nhất có thể được” ❖ “làm tốt nhất có thể được” → “tối ưu hóa” ➢Mục tiêu dịch vụ ❖ “Tối đa” giá trị được tạo ra cho nhà cung cấp và người tiêu dùng ❖ “Tối đa” là kết quả giải bài toán “tối ưu hóa” ❖ Tối ưu hóa phát sinh trong nhiều dịch vụ ❖ “Con người được đặt lên hàng đầu” KHDV 2015 – Chương 2 - Trang 3
Ví dụ: đặt trạm xe cấp cứu ➢ Ví dụ 1. Đặt trạm xe cấp cứu (105) ở Austin (Texas) ❖ Cho: ❖ Dân số 350 nghìn người, 358 cụm dân cư, hệ thống giao thông ❖ Có 10 chục xe cứu thương, “hiện thời” ở chung cư ❖ Xe không được bảo vệ → Thuốc/thiết bị đắt tiền ở phòng ❖ Khi nhận cuộc gọi đưa thuốc, dụng cụ ra xe → chậm trễ  cấp cứu tính phút, giây ❖ Cần: ❖ tổ chức lại vị trí đặt đội cứu thương, xe được bảo vệ → tối đa lượng người được phục vụ theo thời gian quy định: tối ưu hóa ❖ Tiến hành sơ bộ: ❖ Phân tích lịch sử mọi cuộc gọi dịch vụ 105 ❖ Dữ liệu nhân khẩu học trong thành phố (và 358 cụm dân cư) KHDV 2015 – Chương 2 - Trang 4
Ví dụ: Phân sinh viên vào lớp-môn học ➢ Ví dụ 2. Phân phối sinh viên vào lớp-môn học ❖ Cho: ❖ Có 1000 sinh viên năm thứ nhất cần phải học một môn chung ❖ Có 70 lớp - môn học, mỗi lớp – môn học  15 sinh viên ❖ Mỗi sinh viên được đăng ký 3 lớp-môn học với ưu tiên 1,2,3 ❖ Cần xếp: ❖ Mỗi sinh viên vào một lớp-môn học ❖ Xếp theo ưu tiên theo yêu cầu đăng ký ❖ Mọi sinh viên được học môn học chung ❖ Mỗi lớp-môn học không quá 15 sinh viên ❖ Yêu cầu: ❖ Giảm thiểu sinh viên xếp ngoài 3 đăng ký → tối ưu hóa KHDV 2015 – Chương 2 - Trang 5
Ví dụ: lập lịch nhân viên phục vụ ➢ Ví dụ 3. Cần tiến hành một dịch vụ (bác sỹ - y tá – hộ lý trực phục vụ bệnh nhân trong một khoa) ❖ Lịch trình: Bố trí bao nhiêu nhân viên trong một đơn vị thời gian (ngày)? ❖ Lịch trình chi tiết: Bố trí bao nhiều nhân viên trong mỗi khoảng thời gian trong đơn vị thời gian ? Ca làm việc trong ngày. ❖ Nhân viên nào cần được bố trí trong mỗi ca làm việc ? ❖ Yêu cầu: Tối ưu hóa  cực đại chi phí nhân viên cân bằng với hài lòng người tiêu dùng KHDV 2015 – Chương 2 - Trang 6
Ví dụ: Lập lịch vận hành nhà máy điện ➢ Ví dụ 4. Lập lịch ca trực vận hành nhà máy điện Sơn La và Lai Châu. ❖ Một số quy định: Số lượng nhân viên/ca trực; thời gian nghỉ tối thiểu mỗi ca (8 giờ); đảm bảo số ngày công/mỗi nhân viên; bố trí công việc từng ca trực; lịch vệ sinh ca trực VS1, VS2; nghỉ bù của nhân viên ❖ Lịch trình: Bố trí bao nhiêu nhân viên trong một ngày? ❖ Lịch trình chi tiết: Bố trí bao nhiêu nhân viên ở mỗi ca trực. ❖ Lịch chi tiết ca trực: Nhân viên nào đảm nhận việc nào trong mỗi ca trực ? ❖ Yêu cầu: Tối ưu hóa  cực đại giá trị vận hành cân bằng với hài lòng nhân viên https://uet.vnu.edu.vn/trien-khai-thanh-cong-thong-toi-uu-hoa-lap-lich-ca-truc-van-hanh- nhom-nghien-cuu-truong-dai-hoc-cong-nghe-thuc-hien-tai-hai-nha-may-thuy-dien-son- la-va-lai-chau/ do ORLab trường ĐHCN KHDV 2015 – Chương 2 - Trang 7
2. Tối ưu hóa: Năm yếu tố cốt yếu ➢ Đặt vấn đề ❖ 5 yếu tố cốt yếu dưới dạng 5 câu hỏi ❖ Giải đáp 5 yếu tố này → dịch vụ hiệu quả ➢Yếu tố 1: Ta đã biết (có) được gì ? Cho INPUT ❖ Đây là bước đầu tiên cho mọi trường hợp nghiên cứu ❖ Ví dụ 1: Đặt trạm cấp cứu ❖ Vị trí, thời gian, loại cấp cứu của khoảng 4000 cuộc gọi cấp cứu, ❖ 358 khu vực dân cư trong thành phố, ❖ Thời gian xe cấp cứu di chuyển theo mỗi cặp khu vực ❖ Ví dụ 2: Xếp lịch hội thảo ❖ Số lượng hội thảo, quy mô từng hội thảo ❖ Số lượng sinh viên, đăng ký hội thảo của từng sinh viên ❖ Ví dụ 3: lập lịch nhân viên ❖ Số lượng tối thiểu nhân viên trong mỗi đơn vị thời gian ❖ Số lượng tối thiểu nhân viên trong ca làm việc ❖ Sở thích nhân viên trong từng đơn vị thời gian … ❖ Mối quan hệ số lượng nhân viên từng thời điểm với chất lượng KHDV 2015 – Chương 2 - Trang 8
Yếu tố 2: Cần quyết định điều gì ? ➢ Nội dung ❖ Điều gì thực sự cần phải quyết định ❖ Biến quyết định, Đầu ra (Output) ❖ Quan trọng: Phân biệt biến đầu ra và biến đầu vào ➢Trường hợp khá dễ xác định ❖ Ví dụ 1. Vị trí cần đặt xe cứu thương an toàn ❖ Ví dụ 2. Sinh viên nào cho mỗi buổi hội thảo ➢Trường hợp khá dễ xác định ❖ Ví dụ 3. Bài toán lập lịch nhân viên: Thoạt nghĩ: phân nhân viên theo ca (sáng, chiều, đêm) và các ca không chồng nhau. Tuy nhiên, phân nhân viên theo ca chồng nhau lại là mục tiêu cần được xác định (y tá theo dõi bệnh nhân …) ❖ Ví dụ khác: chẳng hạn bài toán xây dựng mô hình dự báo trong thực tế “biến dự báo”, “biến phân lớp” v.v. KHDV 2015 – Chương 2 - Trang 9
Yếu tố 3: Cái gì cố gắng để đạt được ➢ Nội dung ❖ Cố tìm gì trong không gian lời giải ? ❖ Cái gì cần cực đại hoặc cực tiếu ? ❖ Hàm mục tiêu ❖ Có thể là đa mục tiêu. ➢Ví dụ ❖ Ví dụ 1. Tối đa số lượng nhu cầu cấp cứu được đáp ứng. Cực tiểu chi phí vận hành xe. Giảm thời gian đáp ứng yêu cầu. Giảm thiểu thời gian tối đa đáp ứng ca “xấu nhất” ❖ Ví dụ 2. Tối thiếu tổng xếp hạng ưu tiên của các sinh viên. Giảm tối thiểu phân công tồi nhất. ❖ Ví dụ 3. Giảm chi phí nhân viên. Tăng hài lòng khách hàng. ❖ Ví dụ “dự báo, phân lớp”: Các độ đo sai số nhỏ nhất, các độ đo chính xác là cao nhất. KHDV 2015 – Chương 2 - Trang 10
Yếu tố 4: Cái gì cản trở tối ưu ➢ Nội dung ❖ Hạn chế về tài nguyên ❖ các ràng buộc ➢ Ví dụ ❖ Ví dụ 1. Ngân sách thành phố cho 105 ❖ Ví dụ 2. Hai ràng buộc: (i) mỗi sinh viên một lớp – môn học và mỗi lớp – môn học  15 SV ❖ Ví dụ 3. Lượng nhân viên tối thiểu trong mọi thời điểm hoặc trong từng ca làm việc ❖ Ví dụ “dự báo, phân lớp”: theo tập dữ liệu mẫu có được. KHDV 2015 – Chương 2 - Trang 11
Yếu tố 5: Cái gì tìm hiểu thêm được ➢ Nội dung ❖ 4 câu hỏi trên cho xây dựng mô hình ❖ Phân tích bối cảnh mô hình rộng hơn: nâng cao ý nghĩa của mô hình. Các khía cạnh phi mô hình ➢Ví dụ ❖ Ví dụ 1. Bao nhiêu % dân số được phủ sau khi định vị ? Tăng, giảm xe thì % dân số được hưởng dịch vụ tăng- giảm ra sao? ❖ Ví dụ 2. Nếu tăng dung lượng một lớp – môn học lên 20 sinh viên thì tổng xếp hạng giảm bao nhiều? ❖ Ví dụ 3. Nếu yêu cầu số nhân viên từng thời điểm tăng thêm thì cần thêm bao nhiêu nhân viên, lịch trình và lịch trình chi tiết thay đổi ra sao ? KHDV 2015 – Chương 2 - Trang 12
3. Phân loại bài toán tối ưu ➢ Đặt vấn đề ❖ Mỗi loại bài toán có các đặc trưng riêng → đòi hỏi giải pháp riêng ❖ Tồn tại nhiều không phân loại: NEOS, [Daskin10], v.v. Các khung phân loại có phân giao chung ➢Một khung phân loại ❖ https://neos-guide.org/optimization-tree (Types of Optimization Problems) ❖ The NEOS (Network-Enabled Optimization System) ❖ Wisconsin Institute for Discovery (University of Wisconsin in Madison) ❖ 60+ công cụ hiện đại giải 10+ loại bài toán tối ưu hóa ❖ Bốn cặp “đối ngẫu”: Liên tục – rời rạc, Không ràng buộc – ràng buộc, Không - một – đa mục tiêu, tất định – xác suất KHDV 2015 – Chương 2 - Trang 13
Liên tục – rời rạc, Ràng buộc – không RB ➢ Liên tục – rời rạc: giá trị các biến quyết định ❖ Liên tục  giá trị thực, rời rạc – giá trị nguyên ❖ Vị dụ: “quy hoạch”  “quy hoạch nguyên” ❖ “Liên lục” có tiềm năng dễ giải hơn “rời rạc” ❖ Có tính phổ biến: bài toán tối ưu hóa rời rạc quy thành một dãy bài toán tối ưu hóa liên tục ➢Ràng buộc – Không ràng buộc: các biến ❖ Không ràng buộc: Không hạn chế không gian giá trị các biến (không gian trạng thái) ❖ Ràng buộc: hạn chế không gian giá trị các biến/trạng thái. Được phân loại thành các loại con: (i) “bản chất của ràng buộc/hàm mục tiêu”: tuyến tính, phi tuyến, lồi; (ii) “độ mịn của hàm mục tiêu”: phân biệt được/không phân biệt được. KHDV 2015 – Chương 2 - Trang 14
Hàm mục tiêu và tất định – Xác suất ➢Không – một – đa mục tiêu ❖ Hầu hết là một hàm mục tiêu duy nhất: “tối đa hài lòng dân cư”, “tối đa độ ưu tiên phân lớp – môn học”, v.v. ❖ “Không mục tiêu”  “tính khả thi” : Tìm tập các biến thỏa mãn mọi ràng buộc bài toán ❖ Đa mục tiêu: “cân bằng” giữa hai/nhiều mục tiêu xung đột “giảm chi phí nhân viên”  “tăng độ hài lòng người bệnh”, v.v. ➢Tất định – xác suất ❖ Tất định: Giá trị các biến là rõ và được biết chính xác. Mô hình tất định có tính phổ biến ❖ Xác suất: giá trị các biến thực tế không được biết chính xác do : lỗi đo lường, dữ liệu nào đó trình diễn thông tin về tương lai (nhu cầu sản phẩm, giá sản phẩm trong tương lai). Ví dụ: quy hoạch ngẫu nhiên. KHDV 2015 – Chương 2 - Trang 15
“Cây phân loại” tối ưu hóa https://neos- guide.org/content/optimization- taxonomy 16 KHDV 2015 – Chương 2 - Trang 16
Phân loại bài toán tối ưu hóa [Daskin10] ➢Phân loại [Daskin10] ❖ Đơn/đa mục tiêu (single/multiple objective). Hầu hết đa mục tiêu (phân lớp), nghiên cứu hai mục tiêu. ❖ Tuyến tính (linear): Hàm mục tiêu và hàm ràng buộc tuyến tinh. Phi tuyến (non-linear): Vi phạm tuyến tính. ❖ Mạng (network), tổng quát (general), nguyên (integer) KHDV 2015 – Chương 2 - Trang 17
Lưu ý tối ưu tuyến tính và phi tuyến ➢ Về kết quả ❖ Tuyến tính (ngoại trừ quy hoạch nguyên) khi có lời giải thì lời giải là tối ưu ❖ Phi tuyến: Lời giải nói chung chỉ cho kết quả “tựa tối ưu” ➢Về thuật toán ❖ Thuật toán tuyến tính khá phổ biến ❖ Thuật toán phi tuyến hiếm hơn: đang ngày càng tăng ➢Về kích thước ❖ Tuyến tính đòi hỏi nhiều biến hơn so với phi tuyến ❖ Công thức phi tuyến nhiều khi cần thiết ➢Liên hệ ❖ Thuật toán SVM yêu cầu khả tách tuyến tính để tìm siêu phẳng tuyến tính. Dùng hàm nhân để biến đổi ❖ Quy hoạch tuyến tính. Dùng hàm phạt KHDV 2015 – Chương 2 - Trang 18
Tập lồi và tập không lồi • Tập tuyến tính - trái ▪ Được xác định: một tập các ràng buộc tuyến tính. ▪ Ví dụ: Phần mặt phẳng giới hạn bởi năm đường thẳng ▪ Tập lồi (convex set) ▪ x,yB → t[0,1], z=t*x+(1-t)*yB: Đoạn thẳng nối x, y bất kỳ thuộc B cũng thuộc B. Tập tuyến tính → lồi ▪ Tập không lồi ▪ x,yB → t[0,1], z=t*x+(1-t)*yB: Tồn tại x,y thuộc B: đoạn thẳng nối chúng không nằm trọn trong B 19 KHDV 2015 – Chương 2 - Trang 19
Hàm tuyến tính và hàm lồi • Hàm tuyến tính ▪ Cho tập tuyến tính A: Hàm tuyến tính f biểu diễn tuyến tính theo các biến ▪ "f xác định trên tập tuyến tính B: f là hàm tuyến tính  x,yB,t[0,1] → f(t*x+(1-t)*y) = t*f(x) + (1-t)*f(y)" ▪ Hàm lồi / lõm ▪ f xác định trên tập lồi B: f là hàm lồi  x,yB, t[0,1] → f(t*x+(1- t)*y)  t*f(x) + (1-t)*f(y) ▪ f xác định trên tập lồi B: f là hàm lõm  x,yB, t[0,1] → f(t*x+(1- t)*y)  t*f(x) + (1-t)*f(y) ▪ Hàm lồi: cực tiểu; hàm lõm: cực đại, hàm tuyến tinh: cực đại và cực tiểu 20 KHDV 2015 – Chương 2 - Trang 20