Bài giảng Khoa học dịch vụ: Chương 4

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

thể được”

❖ “Trong cuộc sống, dù làm việc gì thì hãy làm tốt nhất có

➢Mục tiêu dịch vụ

❖ “Tối đa” giá trị được tạo ra cho nhà cung cấp và người

❖ “làm tốt nhất có thể được” → “tối ưu hóa”

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)

❖ 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

❖ Cho:

❖ 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

❖ 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ư)

❖ Tiến hành sơ bộ:

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

❖ 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

❖ Cho:

❖ 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

❖ Cần xếp:

KHDV 2015 – Chương 2 - Trang 5

Ví dụ: lập lịch nhân viên phục vụ

❖ Lịch trình: Bố trí bao nhiêu nhân viên trong một đơn 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 chi tiết: Bố trí bao nhiều nhân viên trong mỗi

thời gian (ngày)?

khoảng thời gian trong đơn vị thời gian ? Ca làm việc

❖ 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

trong ngày.

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

❖ 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

➢ 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.

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 đề

➢Yếu tố 1: Ta đã biết (có) được gì ? Cho INPUT

❖ 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ả

❖ 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

❖ Đâ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

❖ 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ụ 2: Xếp lịch hội thảo

❖ 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

❖ Ví dụ 3: lập lịch nhân viên

KHDV 2015 – Chương 2 - Trang 8

Yếu tố 2: Cần quyết định điều gì ?

➢ Nội dung

➢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.

❖ Đ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

KHDV 2015 – Chương 2 - Trang 9

Yếu tố 3: Cái gì cố gắng để đạt được

➢ Nội dung

➢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.

❖ 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.

KHDV 2015 – Chương 2 - Trang 10

Yếu tố 4: Cái gì cản trở tối ưu

➢ Nội dung

➢ Ví dụ

❖ Hạn chế về tài nguyên ❖ các ràng buộc

❖ 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

❖ Ví dụ “dự báo, phân lớp”: theo tập dữ liệu mẫu có được.

hoặc trong từng ca làm việ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

➢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?

của mô hình. Các khía cạnh phi mô hình

❖ 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 đề

pháp riêng

❖ Mỗi loại bài toán có các đặc trưng riêng → đòi hỏi giải

❖ Tồn tại nhiều không phân loại: NEOS, [Daskin10], v.v.

➢Một khung phân loại

Các khung phân loại có phân giao chung

❖ 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

➢Ràng buộc – Không ràng buộc: các biến

một dãy bài toán tối ưu hóa liên tục

❖ Không ràng buộc: Không hạn chế không gian giá trị các

❖ 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.

biến (không gian trạng thái)

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

dân cư”, “tối đa độ ưu tiên phân lớp – môn học”, v.v.

❖ Hầu hết là một hàm mục tiêu duy nhất: “tối đa hài lòng

❖ “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

➢Tất định – xác suất

❖ Đ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: 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ả

lời giải là tối ưu

❖ Tuyến tính (ngoại trừ quy hoạch nguyên) khi có lời giải thì

➢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

❖ Phi tuyến: Lời giải nói chung chỉ cho kết quả “tựa tối ưu”

➢Liên hệ

❖ 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

phẳng tuyến tính. Dùng hàm nhân để biến đổi

❖ Thuật toán SVM yêu cầu khả tách tuyến tính để tìm siêu

❖ 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

là hàm tuyến tính 

▪ "f xác định trên tập tuyến tính B:

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

Tối ưu tuyến tính Tối ưu mạng

➢ Tối ưu mạng: Tìm đường đi ngắn nhất

❖ Các đỉnh: trạng thái, cung có trọng số: giá thành ❖ Đường đi ngắn nhất: tối ưu từ trạng thái ban đầu tới trạng

➢Biểu diễn tối ưu tuyến tính dạng mạng ❖ Tối ưu tuyến tính biểu diễn thành mạng ❖ Bố trí cấp cứu: điểm dân cư là nút, đoạn các điểm dân cư là

thái kết

cung có trọng số

giá trị 1,2,3, 

❖ Lịch hội thảo: sinh viên và hội thảo là nút, kết nối là cung với

KHDV 2015 – Chương 2 - Trang 21

4. Tối ưu hóa: Bài toán từng gặp

KHDV 2015 – Chương 2 - Trang 22

Sai số bình phương tối thiểu

❖ Đạo hàm bậc 1 theo a và b và gán giá trị 0 ❖ Giải hệ hai phương trình hai biến theo a và b ❖ Gọi

➢ Z làm hàm theo hai biến a và b

, là trung bình cộng các giá trị xi và yi, nhận được

các giá trị

KHDV 2015 – Chương 2 - Trang 23

Sai số bình phương tối thiểu

KHDV 2015 – Chương 2 - Trang 24

5. Quy hoạch tuyến tính

➢Giới thiệu

➢Ví dụ ❖

❖ Bài toán tối ưu tuyến tính ❖ Làm tối đa hoặc tối thiếu một hàm (biến) mục tiêu tuyến tính trong miền ràng buộc tuyến tính các biến độc lập ❖ Hàm mục tiêu tuyến tính và các ràng buộc tuyến tính

Z = 3x1+5x2 → max

 12  18

với  4

x1 2x2 3x1 + 2x2

và

x1  0, x2  0,

KHDV 2015 – Chương 2 - Trang 25

Quy hoạch tuyến tính: Trình diễn đồ thị

➢ Ví dụ

❖ Phân bổ ngân sách xe dịch vụ đô thị cảnh sát, cứu hỏa ❖ Xe cảnh sát: 200.000 $, xe cứu hỏa: 1 triệu $ ❖ Ràng buộc: Tổng ngân sách 5.350.000 $ ❖ Ràng buộc: xe cảnh sát ít nhất 1,5 lần xe và nhỏ hơn 7,5

lần cứu hỏa

❖ Kỳ vọng mục tiêu: cứu sống người. Cứu 0,2 người cho 1

Vùng (trạng thái) khả thi: Tập tất cả các điểm đáp ứng mọi ràng buộc

xe cảnh sát và 0.65 người cho một xe cứu hỏa

KHDV 2015 – Chương 2 - Trang 26

Bài toán phân bổ ngân sách

KHDV 2015 – Chương 2 - Trang 27

Vùng khả thi và đường viền mục tiêu

➢Biểu diễn đồ thị

❖ Ba đường viền: Ngân sách, cực đại Police/Fire, cực tiểu

Police/Fire (theo các ràng buộc)

❖ Bốn đường thẳng // tương ứng giá hàm mục tiêu: 1,400, 2,800, 4,200, 4,601 (đỉnh C của tam giác) với 16,05 xe cảnh sát (3.210.000) và 2.14 xe cứu hỏa (2.140.000). Điểm tối ưu đạt tại một đỉnh ở vùng biên !

KHDV 2015 – Chương 2 - Trang 28

Bổ sung ràng buộc

➢Bổ sung ràng buộc

❖ Hội đồng thành phố không muốn có quá 11 xe cảnh sát:

Police  11. Vùng khả thi có các đỉnh A, E, D, B

❖ Điểm tối ưu cũ C không còn, vẽ đường mục tiêu có vị trí tối ưu

ở D với giá trị mục tiêu 4,2475 < 4,601

KHDV 2015 – Chương 2 - Trang 29

Bổ sung ràng buộc (2)

➢Bổ sung ràng buộc

❖ Hội đồng thành phố không muốn có quá 3 xe cứu hỏa:

Fire  3. Vùng khả thi có các đỉnh A, C, G, F

❖ Điểm tôi ưu cũ C vẫn thuộc vùng khả thi: bổ sung ràng buộc không

thay đổi vị trí tối ưu

❖ Thêm ràng buộc vào bài toán tối ưu hóa không thể nâng cao giá

trị hàm mục tiêu; mà thường làm giảm giá trị hàm mục tiêu

KHDV 2015 – Chương 2 - Trang 30

Quy hoạch tuyến tính: Dạng kinh điển

➢Dạng kinh điển (Canonical Form)

❖ Một giải thích: J là tập các sản phẩm/dịch vụ cần sản xuất; Xj biến quyết định thứ j  số lượng sản phẩm/dịch vụ j, cj lợi ích đơn vị SP/DV thứ j; I là tập đầu vào (tài nguyên) với bi tối đa tài nguyên i và aij là số đơn vị tài nguyên i để tạo ra một đơn vị SP/DV j.

❖ Bài toán min: đổi dấu hàm mục tiêu ra max, ❖ Tính tiến biến nếu giới hạn  0 ❖ Biến trong miền âm: đổi ngược dấu biến

KHDV 2015 – Chương 2 - Trang 31

Quy hoạch tuyến tính: Dạng chuẩn

➢Dạng chuẩn (standard form) quy hoạch tuyến tính

❖ Biến “lỏng” Si : hiệu vế phải so với vế trái “phần dư tài

nguyên khi thứ i tại phương án tối ưu”,

❖ Dạng chuẩn: thích hợp khi bàn luận các điều kiện lỏng

KHDV 2015 – Chương 2 - Trang 32

Quy hoạch tuyến tính: kinh điển đối ngẫu



➢Đối ngẫu (dual)

❖ A bài toán quy hoạch tuyến tính   B bài toán quy

hoạch tuyến tính đối ngẫu

min max 

❖ Ví dụ: Dạng kinh điển (phải), đối ngẫu (trái) ❖ “Hàm mục tiêu”: ❖ Ràng buộc tài nguyên: “”  “” và trao đổi số lượng ❖ Biến wi đối ngẫu với biến Xi , tương ứng ❖ bi : giới hạn tài nguyên  hệ số mục tiêu ở đối ngẫu ❖ ci : hệ số mục tiêu  giới hạn tài nguyên ở đối ngẫu ❖ Hệ số ma trận ràng buộc aij  aji

KHDV 2015 – Chương 2 - Trang 33

Đối ngẫu dạng chuẩn và tính chất đối ngẫu

➢Đối ngẫu dạng chuẩn

➢Tính chất đối ngẫu

❖ (a) Bài toán đỗi ngẫu cũng không khả thi ❖ (b) bài toán đỗi ngẫu là không giới hạn, có nghĩa là hàm mục tiêu đối

ngẫu có thể được làm nhỏ tùy ý ❖ Nếu bài toán gốc là không giới hạn, thì

❖ (a) Bài toán đỗi ngẫu cũng không khả thi

❖ Nếu bài toán gốc không khả thi (vùng khả thi rỗng) thì

❖ Quan tâm trường hợp bài toán gốc và bài toán đỗi ngẫu khả

thi.

KHDV 2015 – Chương 2 - Trang 34

Biện luận lời giải: Phân tách và kết nối

➢Giả thiết hai bài toán khả thi

đối ngẫu Wi:

❖ Được gọi là điều kiện đối ngẫu yếu (weak dualitycondition) ❖  giải pháp khả thi cho bài toán gôc,  giải pháp khả thi cho bài toán đối ngẫu, giá trị hàm mục tiêu nguyên thủy cần tối đa hoá luôn  giá trị hàm mục tiêu đối ngẫu cần được cực tiểu hóa.

❖  tập khả thi biến quyết định Xj, tập khả thi biến quyết định

❖ Đối với lời giải tối ưu cho bài toán gốc và đỗi ngẫu, ký hiệu tương ứng là X* và S* cho gốc và W* và T * cho đỗi ngẫu thì

Hàm mục tiêu gốc và đối ngẫu là chính xác bằng nhau

KHDV 2015 – Chương 2 - Trang 35

Biện luận: Phương trình lời giải

➢Tính chất đối ngẫu: giả thiết hai bài toán khả thi

❖ Tại giải pháp tối ưu, X*T* = 0 cho mọi sản phẩm j, và W*S* = 0 cho mọi đầu vào hoặc tài nguyên i. Đây chính điều kiện lỏng bổ sung.

 i:

❖ Chứng tỏ rằng nếu không dùng hết tài nguyên i thì giá trị bổ sung cho nguồn tài nguyên này là 0 hoặc W*=0. Nếu trả số tiền dương cho tài nguyên I (W*>0) thì phải sử dụng hết tài nguyên đang có S*=0 hay

❖ Ít nhất một giải pháp tối ưu tại điểm góc của vùng khả thi,

có nghĩa là nơi giao nhau một số ràng buộc

KHDV 2015 – Chương 2 - Trang 36

Phương trình lời giải

➢Tính chất đối ngẫu: giả thiết hai bài toán khả thi (2)

của bài toán đối ngẫu thì đấy chính là gốc

❖ Đối ngẫu của đối ngẫu là gốc: nếu tìm được bài toán đối ngẫu

❖ Và bài toán đối ngẫu với các biến Total, MaxPolice,

MinPolice

KHDV 2015 – Chương 2 - Trang 37

Giải bài toán đối ngẫu

Nhận được các phương trình

Giải hệ ba phương trình có Total = 0.00086, MaxPolice = 0.028 và MinPolice = 0. Lời giải tối ưu là 4,601 (như đã biết)

KHDV 2015 – Chương 2 - Trang 38

Ví dụ 1. Gán sinh viên – lớp môn học

➢ Phát biểu bài toán

❖ STUDENT là tập sinh viên, SEM là tập lớp giảng đường. Mỗi sinh viên j một tập con SEMj,  kSEMj: rankjk trong đó rank càng nhỏ thì giá trị càng lớn; k SEM: capk là dung lượng k. Có |STUDENT|*|SEM| các biến ASSIGNjk

KHDV 2015 – Chương 2 - Trang 39

Ví dụ 1: Giải thích

➢ Giải thích

❖ Hàm mục tiêu: Cực tiểu gán lớp MH cho sinh viên ❖ Ràng buộc 1: mỗi sinh viên được gán vào một lớp-môn

❖ Ràng buộc 2: số sinh viên gán cho một lớp-môn học

học, ASSIGNjk nhận giá trị 0,1

không vượt quá dung lượng

➢Lưu ý

❖ Ràng buộc 3: giá trị gán không âm.

❖ Việc lựa chọn của sinh viên không thừa nhận lời giải khả thi: 5 sinh viên và ba lớp-môn học, mỗi lớp-môn học chứa 2 sinh viên; cả 5 sinh viên không chọn lớp-môn học 3. Không thể gán sinh viên tới lớp-môn học mà họ không đăng ký. Tổng số sinh viên vượt qua dung lượng lớp-môn học

❖ Trong định nghĩa QHTT: các biến thực, dương ❖ Ở đây các biến nguyên (0,1) ❖ Bài toán có thể không có lời giải khả thi:

KHDV 2015 – Chương 2 - Trang 40

Ví dụ 1: Vấn đề không khả thi

➢Vấn đề không khả thi: Phương pháp

❖ Tạo một lớp-môn học “ảo” có dung lượng bằng tổng số sinh viên. Sinh viên được gán vào lớp-môn học này: không thể gán vào lớp-môn học ‘thực’.

lớn (10*|STUDENT|*|SEMjk).

❖ Với mỗi đăng ký của sinh viên j: bổ sung rankjảo = giá trị

❖ Số sinh viên không được phân công sẽ rơi vào lớp-môn

học ảo

❖ 7 sinh viên, 3 lớp-môn học dung lượng 2  sinh viên rơi vào lớp-môn học ảo cho bất kỳ sự lựa chọn của sinh viên.

KHDV 2015 – Chương 2 - Trang 41

Ví dụ 1: Lưu ý

➢ Với bài toán tối ưu (và quy hoạch tuyến tính)

❖ cần đảm bảo rằng mô hình đối phó được với

tính bất khả thi do các yếu tố đầu vào.

❖ cần phòng ngừa tính bất khả thi do dư thừa

gấp đôi nhau thì sẽ dẫn tới không khả thi

ràng buộc ❖ Nếu thêm ràng buộc tỷ lệ sinh viên nam/nữ không quá

KHDV 2015 – Chương 2 - Trang 42

Ví dụ 2: Bài toán đường đi ngắn nhất

➢ Các điều kiện đầu bài ❖ N tập các nút trên mạng. ❖ Hai nút đặc biệt: nút xuất phát o và nút đích d ❖ L NN tập các cung: kết nối hai nút liền kề (j,k). ❖ jN: O(j) tập nút có cung từ j đi tới, I(j) tập nút có

❖ Giá (trọng số) cung t(j,k) độ dài, thời gian, tiền xe … ❖ X(j,k) là biến quyết định, X(j,k) =1 nếu có trên đường

cung đi tới j.

đi tối ưu, = 0 nếu không có

KHDV 2015 – Chương 2 - Trang 43

Ví dụ 2: Trình bày bài toán

➢ Giải thích

❖ Hàm mục tiêu (2.36) giảm thiểu tổng thời gian ❖ Ràng buộc (2.38): biến quyết định là không âm ❖ Số hạng đầu vế trái (2.37), nO(j) Χ(j,n): tổng số lần rời

hay ra khỏi nút j,

❖ Số hạng thứ hai vế trái, nI(j) Χ(n,j): tổng số lần đi tới nút

KHDV 2015 – Chương 2 - Trang 44

6. Quy hoạch tuyến tính: Dạng mạng

➢ Giới thiệu

❖ Phân công: sinh viên →hội thảo, hang tồn kho → thời điểm tiếp theo, nhân viên → thời điểm ca tiếp theo v.v.

❖ Một tập bài toán QHTT có dạng mạng ❖ Bài toán QHTT : dạng mạng với nút và cung ❖ Nút: thời điểm, vị trí, người, lớp học, công việc .. ❖ Biến quyết định liên quan tới cung:

❖ Đường đi tối thiểu đi qua cung ❖ Đường đi cho phép cực đại qua cung ❖ Đơn vị giá tương ứng với đường đi qua cung

❖ Ba ràng buộc điển hình

❖ Cực tiểu tổng giá tương ứng đường đi tối ưu cần tìm ❖ Giá cung là tổng số giá số lần đi theo cung

❖ Mục tiêu của bài toán đường đi mạng

KHDV 2015 – Chương 2 - Trang 45

Dạng mạng đặc biệt: Biểu diễn toán

➢ Ma trận liên kết

❖ 1 điểm đầu cung, -1 điểm cuối cung, 0 còn lại (cung

thưa)

❖ Có thể dung ma trận liền kề (cung dầy)

KHDV 2015 – Chương 2 - Trang 46

Mạng sinh viên – lớp môn học

➢ Các yếu tố chính

❖ Hai tập nút: {Student} và {Seminar} ❖ Tập cung: Nối một Student → một số Seminar. Cung có trọng số: Chi phí 0, 1, 2, Lớn. Tính chất: Không có cung nối giữa nội tại {Student} và {Seminar} bipartite graph/ bipartite network

❖ Nối sinh viên – lớp môn học: dưới 0, trên 1. ❖ Bổ sung hai nút Source, Sink để duyệt hết sinh viên. Tìm đường đi ngắn nhất qua tất cả sinh viên và đúng một lần

KHDV 2015 – Chương 2 - Trang 47

Bipartie Graph và hệ tư vấn

➢Quan hệ khách hàng – sản phẩm

❖ Bipartie Graph: Khách hàng “mua” sản phẩm (trái) ❖ Two-layer Graph: Mở rộng khách hàng-khách hàng, sản phẩm-sản phẩm, khách hàng-sản phẩm (giao dịch).

❖ Zan Huang. Graph-based Analysis for E-commerce Recommendation. PhD Thesis, The University of Arizona

KHDV 2015 – Chương 2 - Trang 48

Tính quan trọng của QHTT mạng

➢ Các lý do

❖ Nhiều bài toán quan trọng có thể được xây dựng dưới

❖ Biểu diễn dạng mạng → biểu diễn hình ảnh tinh thần cho bài toán → xây dựng được hình ảnh để nắm bắt bản chất bài toán

dạng QHTT mạng

❖ Sẵn có một số thuật toán và công cụ: MENU-OKF

❖ Nếu biểu diễn bài toán lưu lượng mạng với giá trị nguyên → dòng tối ưu có giá trị nguyên  giải bài toán quy hoạch nguyên. Bài toán luồng cực đại “Maximum flow problem”

http://www- personal.umich.edu/~msdaskin/servicescience/Chap%20 2/Menu-OKF.zip

KHDV 2015 – Chương 2 - Trang 49

7. Quy hoạch nguyên

➢ Giới thiệu

❖ Lời giải bài toán quy hoạch tuyến tính điểm C Police (16.05)

❖ Làm tròn xuống (16,2). ? Làm tròn lên còn đáp ứng ràng buộc

và Fire (2.14) !

? (16,2) vi phạm Police  7.5 Fire !

❖ Làm tròn lời giải QHTT có thể không đáp ứng ràng buộc

KHDV 2015 – Chương 2 - Trang 50

Dạng quy hoạch nguyên

➢ Dang quy hoạch nguyên

❖ Giá trị của Police và Fire nguyên (Integer). ❖ Miền khả thi. Lời giải (15,2)

KHDV 2015 – Chương 2 - Trang 51

Yếu tố 5: Ngân sách tăng cường

➢ Các trường hợp

❖ Ngân sách được 5.400.000: Có (12,3), dùng hết ngân

❖ Ngân sách được 6.000.000 có Police=15

và Fire=3

sách, mục tiêu 4.35 (hơn 0.05)

(3000+3000) dung hết ngân sách.

KHDV 2015 – Chương 2 - Trang 52

Sử dụng biến nguyên

➢ Đặt vấn đề

➢Biến nhị phân

❖ Lời giải không nguyên không có ý nghĩa: ¼ người ! ❖ Làm tròn có thể không đùng: vi phạm ❖ Làm tròn là phương án ban đầu !

❖ Quyết định: hoặc thực hiện hoặc không thực hiện. Đa phần quyết định hành động/không hành động. Gán sinh viên hội thảo hoặc không !

❖ Nắm bắt quan hệ giữa các quyết định cốt lõi

❖ Giá trị 0,1 nguyên ❖ Được sử dụng theo một trong hai mục đích:

❖ Các chọn lựa: tới 100 triệu tỷ hành động  Quy hoạch

nguyên với giá trị 0,1

KHDV 2015 – Chương 2 - Trang 53

Sử dụng biến nhị phân

➢Phạm vi

➢Quyết định có/không

❖ Biến nghị phân cho nhiều ngữ cảnh

❖ Định tuyến xe: khách hang k đi ngay sau khách hang j (1)

hoặc không (0)

học/khoảng thời gian (time slot)

➢Điều kiện logic cần có giữa các quyết định

❖ Lập thời khóa biểu: Một lớp học vào 1 phòng

❖ Không thể có quá 70 hội thảo ❖ Một sinh viên được phân đúng một hội thảo

KHDV 2015 – Chương 2 - Trang 54

Giải bài toán quy hoạch nguyên

➢ Nhánh và ràng buộc

❖ Không cần quan tâm cụ thể cách Excel Solver giải hoặc cái gì tốt nhất để giải bài toán QH nguyên. Coi như phần mềm tiếp nhận các biến nguyên/nhị phân

❖ Cần hiểu biết phần mềm làm như vậy và khó khan của

giải bài toán quy hoạch nguyên

❖ Xét ví dụ: Phân ngân sách Police/Fire: Lời giải tối ưu

16,05 Police, 2.14 Fire và hàm mục tiêu 4.601.

❖ Với 16.05: xem xét các số nguyên 16 hoặc 17, dẫn hai bài

hàm mục tiêu 4.5975

❖ Ràng buộc Police  17. Không có lời giải

toán ❖ Ràng buộc Police  16. Có lời giải Police=16, Fire=2.15,

KHDV 2015 – Chương 2 - Trang 55

Nhánh và ràng buộc

➢Phân nhánh tiếp: với ràng buộc police  16

KHDV 2015 – Chương 2 - Trang 56

Theo kinh nghiệm (Heristic)

➢Bài toán sinh viên-hội thảo hạn chế

➢Lời giải heristic

❖ Có danh sách 70 hội thảo sinh viên đăng ký song cần quyết định chỉ với 50 hội thảo (do tài nguyên hạn chế).

tiêu tốt nhất đang tìm được)

❖ Tốt song có thể không tối ưu ❖ Cắt nhánh nếu hàm mục tiêu quá nhỏ (tỷ lệ so với mục

❖ Tìm lời giải heristic: Xây dựng lời giải ban đầu và Cải tiến

thuật toán.

KHDV 2015 – Chương 2 - Trang 57

7. Mười quy tắc đánh dấu

➢Quy tắc 1. Định nghĩa tường minh mọi tập hợp trong văn bản

bảng chữ cái.

❖ Dùng chữ cái in hoa để ký hiệu tập: chọn chữ cái ở giữa

❖ Biến: chữ cái thường ứng chữ cái tập (in hoa) ❖ Tập cần được định nghĩa rõ ràng

➢Quy tắc 2. Phân biệt tường minh các tập, các đầu vào khác,

❖ Luôn là ý tưởng tốt: chia mục ký hiệu thành các mục con: tập đầu vào, đầu vào khác (hằng và tham số), các biến quyết định

❖ Vi phạm: bắt người đọc đặt câu hỏi: đầu vào là gì, biến

quyết định là gì ?

KHDV 2015 – Chương 2 - Trang 58

Quy tắc đánh dấu

➢Quy tắc 3. Khi định nghĩa đầu vào và biến quyết định bằng văn bản, nếu một chỉ số xuất hiện trong đầu vào hoặc biến quyết định, có nên xuất hiện trong định nghĩa bằng lời

❖ Nếu đầu vào dij thì cần chỉ dẫn bằng lời cho i và j, ví dụ dij

khách cách KH iI tới mặt hàng jJ.

❖ Không chỉ giải thích chỉ số mà còn phạm vị chỉ số. ❖ Phân vân “dij là khoảng cách” ? Giữa các vị trí ?

➢Quy tắc 4. Không để lơ lửng các subscript ở hàm mục tiêu

❖ Một subscript không chỉ dẫn tổng, ❖ Cần phải viết ❖ Không thể viết

KHDV 2015 – Chương 2 - Trang 59

Quy tắc đánh dấu: QT 5 và 6

➢Quy tắc 5. Ít nhất một biến mục tiêu phái xuất hiện trong hàm mục tiêu và mỗi ràng buộc

❖ Nếu không có biến quyết định trong hàm mục tiêu hoặc nếu một ràng buộc không chứa một biến quyết định, việc phát biểu bài toán là không chính xác

➢Quy tắc 6. Chắc chắn rằng mọi biến liên kết theo cách nào đó tới mỗi biến khác. Ngược lại bài toán là tách rời và nhiều khả năng đã lỗi trong phát biểu bài toán

❖ Xét bài toán định vị phủ cực đại: I tập nút yêu cầu, J các vị trí ứng viên. iI lượng nhu cầu hi. Nếu vị trí ứng viên j phủ đầy đủ nhu cầu → aij=1, ngược lại aij=0.

KHDV 2015 – Chương 2 - Trang 60

Quy tắc đánh dấu: Quy tắc 6

➢Lưu ý

❖ Chọn p vị trí tại đó cực đại số nhu cầu được phủ ❖ Hai lớp biến quyết định ❖ Zi = 1 nếu nút nhu cầu i được đáp ứng bởi vị trí bất kỳ

được chọn, Zi = 0

❖ Có vẻ hoàn hảo !

❖ Xj = 1 nếu định vị được tại nút vị trí j, Zi = 0

KHDV 2015 – Chương 2 - Trang 61

Quy tắc đánh dấu: Quy tắc 6

➢Nhận xét

vị Xj. ➢Giải pháp

❖ Phát biểu bài toán có vẻ tốt ? ❖ Biến quyết định phủ Zi không được liên kết với biến định

buộc

❖ Liên kết biến quyết định với các biến khác bằng ràng

❖  chọn p địa điểm bất kỳ dành cho cơ sở ❖ khẳng định nút nhu cầu được chọn phủ bằng cách thiết

lập mọi biến Z, thành 1

❖ Cần một ràng  buộc

KHDV 2015 – Chương 2 - Trang 62

Quy tắc đánh dấu: Quy tắc 6

➢Nhận xét sau bổ sung

❖ Các biến quyết định không có liên kết trực tiếp mọi biến

❖ Xét 3 tình huống có thể:

❖ (a) liên kết đầy đủ: Quá nhiều ràng buộc và nảy sinh vấn đề ❖ (c) hai cặp liên kết nhau: Chia hai vấn đề con (W,X) và (Y, Z) ❖ (b) các cặp biến liên kết nhau (dù không trực tiếp)

khác

❖ biến quyết định phải được kết nối trực tiếp hoặc gián tiếp

đến mọi lớp biến quyết định khác