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

u; mà thường làm giảm giá trị hàm mục tiêu
Bổ sung ràng buộc (2)
KHDV 2015 – Chương 2 - Trang 31
➢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
Quy hoạch tuyến tính: Dạng kinh điển
KHDV 2015 – Chương 2 - Trang 32
➢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
Quy hoạch tuyến tính: Dạng chuẩn 
KHDV 2015 – Chương 2 - Trang 33
➢Đố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
❖ Ví dụ: Dạng kinh điển (phải), đối ngẫu (trái)
❖ “Hàm mục tiêu”: max min
❖ 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
Quy hoạch tuyến tính: kinh điển đối ngẫu
KHDV 2015 – Chương 2 - Trang 34
➢Đối ngẫu dạng chuẩn
➢Tính chất đối ngẫu
❖ Nếu bài toán gốc không khả thi (vùng khả thi rỗng) thì
❖ (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
❖ Quan tâm trường hợp bài toán gốc và bài toán đỗi ngẫu khả
thi.
Đối ngẫu dạng chuẩn và tính chất đối ngẫu
KHDV 2015 – Chương 2 - Trang 35
➢Giả thiết hai bài toán khả thi
❖  tập khả thi biến quyết định Xj, tập khả thi biến quyết định
đối ngẫuWi:
❖ Đượ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àmmục tiêu đối ngẫu cần được cực tiểu hóa.
❖ Đố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àmmục tiêu gốc và đối ngẫu
là chính xác bằng nhau
Biện luận lời giải: Phân tách và kết nối
KHDV 2015 – Chương 2 - Trang 36
➢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
chomọ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
Biện luận: Phương trình lời giải
KHDV 2015 – Chương 2 - Trang 37
➢Tính chất đối ngẫu: giả thiết hai bài toán khả thi (2)
❖ Đối ngẫu của đối ngẫu là gốc: nếu tìm được bài toán đối ngẫu
của bài toán đối ngẫu thì đấy chính là gốc
❖ Và bài toán đối ngẫu với các biến Total, MaxPolice,
MinPolice
Phương trình lời giải
KHDV 2015 – Chương 2 - Trang 38
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 39
➢ 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
Ví dụ 1. Gán sinh viên – lớp môn học
KHDV 2015 – Chương 2 - Trang 40
➢ 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
học, ASSIGNjk nhận giá trị 0,1
❖ Ràng buộc 2: số sinh viên gán cho một lớp-môn học
không vượt quá dung lượng
❖ Ràng buộc 3: giá trị gán không âm.
➢Lưu ý
❖ 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:
❖ 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
Ví dụ 1: Giải thích
KHDV 2015 – Chương 2 - Trang 41
➢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’.
❖ Với mỗi đăng ký của sinh viên j: bổ sung rankjảo = giá trị
lớn (10*|STUDENT|*|SEMjk).
❖ 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.
Ví dụ 1: Vấn đề không khả thi
KHDV 2015 – Chương 2 - Trang 42
➢ 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
ràng buộc
❖ Nếu thêm ràng buộc tỷ lệ sinh viên nam/nữ không quá
gấp đôi nhau thì sẽ dẫn tới không khả thi
Ví dụ 1: Lưu ý
KHDV 2015 – Chương 2 - Trang 43
➢ 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ó
cung đi tới j.
❖ 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
đi tối ưu, = 0 nếu không có
Ví dụ 2: Bài toán đường đi ngắn nhất
KHDV 2015 – Chương 2 - Trang 44
➢ Giải thích
❖ Hàmmụ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
j.
Ví dụ 2: Trình bày bài toán
KHDV 2015 – Chương 2 - Trang 45
➢ Giới thiệu
❖ 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:
❖ 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.
❖ Ba ràng buộc điển hình
❖ Đườ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
❖ Mục tiêu của bài toán đường đi mạng
❖ 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
6. Quy hoạch tuyến tính: Dạng mạng
KHDV 2015 – Chương 2 - Trang 46
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 47
➢ 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ớpmô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
Mạng sinh viên – lớp môn học
KHDV 2015 – Chương 2 - Trang 48
➢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
Bipartie Graph và hệ tư vấn
KHDV 2015 – Chương 2 - Trang 49
➢ Các lý do
❖ Nhiều bài toán quan trọng có thể được xây dựng dưới
dạng QHTTmạng
❖ 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
❖ 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”
❖ Sẵn có một số thuật toán và công cụ: MENU-OKF
personal.umich.edu/~msdaskin/servicescience/Chap%20
2/Menu-OKF.zip
Tính quan trọng của QHTT mạng
KHDV 2015 – Chương 2 - Trang 50
➢ 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)
và Fire (2.14) !
❖ Làm tròn xuống (16,2). ? Làm tròn lên còn đáp ứng ràng buộc
? (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
7. Quy hoạch nguyên
KHDV 2015 – Chương 2 - Trang 51
➢ 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)
Dạng quy hoạch nguyên
KHDV 2015 – Chương 2 - Trang 52
➢ Các trường hợp
❖ Ngân sách được 5.400.000: Có (12,3), dùng hết ngân
sách,mục tiêu 4.35 (hơn 0.05)
❖ Ngân sách được 6.000.000 có Police=15 và Fire=3
(3000+3000) dung hết ngân sách.
Yếu tố 5: Ngân sách tăng cường
KHDV 2015 – Chương 2 - Trang 53
➢ Đặt vấ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 !
➢Biến nhị phân
❖ Giá trị 0,1 nguyên
❖ Được sử dụng theomột trong haimục đích:
❖ 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
❖ 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
Sử dụng biến nguyên
KHDV 2015 – Chương 2 - Trang 54
➢Phạm vi
❖ Biến nghị phân cho nhiều ngữ cảnh
➢Quyết định có/không
❖ Định tuyến xe: khách hang k đi ngay sau khách hang j (1)
hoặc không (0)
❖ Lập thời khóa biểu: Một lớp học vào 1 phòng
học/khoảng thời gian (time slot)
➢Điều kiện logic cần có giữa các quyết định
❖ 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
Sử dụng biến nhị phân
KHDV 2015 – Chương 2 - Trang 55
➢ 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
toán
❖ Ràng buộc Police 16. Có lời giải Police=16, Fire=2.15,
hàm mục tiêu 4.5975
❖ Ràng buộc Police 17. Không có lời giải
Giải bài toán quy hoạch nguyên
KHDV 2015 – Chương 2 - Trang 56
➢Phân nhánh tiếp: với ràng buộc police 16
Nhánh và ràng buộc
KHDV 2015 – Chương 2 - Trang 57
➢Bài toán sinh viên-hội thảo hạn chế
❖ 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ế).
➢Lời giải heristic
❖ 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
tiêu tốt nhất đang tì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.
Theo kinh nghiệm (Heristic)
KHDV 2015 – Chương 2 - Trang 58
➢Quy tắc 1. Định nghĩa tường minh mọi tập
hợp trong văn bản
❖ Dùng chữ cái in hoa để ký hiệu tập: chọn chữ cái ở giữa
bảng chữ cái.
❖ 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: chiamục ký hiệu thành cácmụ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ì ?
7. Mười quy tắc đánh dấu
KHDV 2015 – Chương 2 - Trang 59
➢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
Quy tắc đánh dấu
KHDV 2015 – Chương 2 - Trang 60
➢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.
Quy tắc đánh dấu: QT 5 và 6
KHDV 2015 – Chương 2 - Trang 61
➢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
❖ Xj = 1 nếu định vị được tại nút vị trí j, Zi = 0
❖ Có vẻ hoàn hảo !
Quy tắc đánh dấu: Quy tắc 6
KHDV 2015 – Chương 2 - Trang 62
➢Nhận xét
❖ 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
vị Xj.
➢Giải pháp
❖ Liên kết biến quyết định với các biến khác bằng ràng
buộc
❖  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
Quy tắc đánh dấu: Quy tắc 6
KHDV 2015 – Chương 2 - Trang 63
➢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
khác
❖ 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)
❖ 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
Quy tắc đánh dấu: Quy tắc 6
KHDV 2015 – Chương 2 - Trang 64
➢Quy tắc 7. Nếu một biến/hằng số được sử dụng
trong một ràng buộc chứa một chỉ số, thì hoặc (a)
tính tổng trên chỉ số (b) đặc tả giá trị của chỉ số
được áp dụng cho ràng buộc. Không làm cả hai trên
cùng một ràng buộc
❖ Ví dụ ràng buộc phù hợp :
❖ Ràng buộc có vấn đề
chỉ số k
❖ Ráng buộc có vấn đề
chỉ dấn lặp j, thiếu i
Đánh dấu: quy tắc 7
KHDV 2015 – Chương 2 - Trang 65
➢Quy tắc 8. Cố giữ phát biểu bài toán ở tuyến tính
có thể được
❖ Không nhân các biến quyết định
❖ Không hàmmũ đối với biến quyết định
❖ Không có dạng : biến quyết định làmũ của một hằng số
➢Quy tắc 9. Tránh ràng buộc kiểu M-lớn
❖ Sử dụng một hằng lớnM thi hành điều kiện nào đó.
❖ Hằng lớn như trong Excel
➢Quy tắc 10. Tách rời ràng buộc theo khả
năng
❖ Lấy ví dụ bài toán phân công nhân viên
Đánh dấu: quy tắc 8