Bài giảng Khoa học dịch vụ - Chương 4: Tối ưu hóa trong dịch vụ

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

Bài giảng Khoa học dịch vụ - Chương 4: Tối ưu hóa trong dịch vụ - Hà Quang Thụy