..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THƠNG

HỒNG XN THÁI

MỘT SỐ THUẬT TỐN GIẢI BÀI TỐN
PHỦ TẬP HỢP VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun - Năm 2014
Số hóa bởi Trung tâm Học liệu
/>

1

ĐẠI HOẠC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THƠNG

HỒNG XN THÁI

MỘT SỐ THUẬT TỐN GIẢI BÀI TỐN
PHỦ TẬP HỢP VÀ ỨNG DỤNG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số

:

60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƢỜI HƢỚNG DẪN KHOA HỌC
GS. TS. ĐẶNG QUANG Á

Thái Nguyên - Năm 2014

Số hóa bởi Trung tâm Học liệu

/>

2

MỤC LỤC
Trang
LỜI CẢM ƠN ............................................................................................................ 4
LỜI CAM ĐOAN ...................................................................................................... 5
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................ 6
DANH MỤC BẢNG .................................................................................................. 7
DANH MỤC HÌNH ................................................................................................... 8
MỞ ĐẦU .................................................................................................................... 9
Chƣơng 1. TỔNG QUAN ........................................................................................ 11
1.1. KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TOÁN NP-HARD ..............11
1.1.1. Định nghĩa về lớp bài tốn P và NP ......................................................11
1.1.2. Các ví dụ về bài tốn NP .......................................................................14
1.2. LÝ THUYẾT QUY HOẠCH TỐN HỌC ................................................15
1.2.1. Khái niệm chung....................................................................................16

1.2.2. Quy hoạch tuyến tính ............................................................................19
1.2.3. Quy hoạch rời rạc ..................................................................................22
1.3. TỔNG KẾT CHƢƠNG ...............................................................................25
Chƣơng 2. BÀI TOÁN PHỦ TẬP HỢP ................................................................. 26
2.1. GIỚI THIỆU BÀI TỐN PHỦ TẬP HỢP ....................................................26
2.1.1. Một số ví dụ về bài toán phủ tập hợp ....................................................26
2.1.2. Bài toán phủ tập hợp..............................................................................28
2.2. MỘT SỐ KẾT QUẢ LÝ THUYẾT VỀ BÀI TOÁN PHỦ TẬP HỢP ..........29
2.2.1. Hƣớng tiếp cận giải bài toán SCP ...........................................................29

Số hóa bởi Trung tâm Học liệu

/>

3

2.2.2. Một số phƣơng pháp tìm giải pháp gần tối ƣu cho bài tốn SCP ...........31
2.3. THUẬT TỐN HEURISTIC GIẢI BÀI TỐN PHỦ TẬP HỢP ................35
2.3.1. Thuật tốn Heuristic ..............................................................................35
2.3.2. Ứng dụng thuật toán Heuristics giải bài toán SCP ................................36
2.3.3. Tính hiệu quả của thuật tốn Heuristic ..................................................45
2.4. THUẬT TỐN CHÍNH XÁC .......................................................................50
2.4.1. Ví dụ về thuật tốn nhánh cận .....................................................................50
2.4.2. Thuật tốn chính xác giải bài tốn SCP ......................................................54
2.5. TỔNG KẾT CHƢƠNG .................................................................................57
Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH VÀ ỨNG DỤNG .................................. 58
3.1. BÀI TOÁN PHÂN LỊCH TRỰC BÁC SĨ .....................................................58
3.1.1. Phát biểu bài toán ........................................................................................58
3.1.2. Cài đặt thuật toán tham lam ........................................................................59
3.1.3. Cài đặt thuật toán Nhánh cận ......................................................................60

3.2. XÂY DỰNG CHƢƠNG TRÌNH PHÂN LỊCH TRỰC BÁC SĨ ...................64
3.2.1. Cơng cụ lựa chọn ...................................................................................64
3.2.2. Modul chƣơng trình ...............................................................................64
3.2.3. Giao diện chƣơng trình ..........................................................................66
3.3. THỬ NGHIỆM VÀ ĐÁNH GIÁ ...................................................................70
3.4. TỔNG KẾT CHƢƠNG .................................................................................70
KẾT LUẬN VÀ KIẾN NGHỊ ................................................................................. 72
DANH MỤC TÀI LIỆU THAM KHẢO ................................................................. 74

Số hóa bởi Trung tâm Học liệu

/>

4

LỜI CẢM ƠN
Em xin chân thành cảm ơn Ban Giám hiệu, Phịng Đào tạo Sau Đại học,
Khoa Cơng nghệ Thơng tin Trường Đại học công nghệ thông tin và truyền thơng
Thái Ngun đã tận tình giúp đỡ, tạo mọi điều kiện thuận lợi cho em trong quá
trình học tập, nghiên cứu và thực hiện luận văn.
Đặc biệt, em xin gửi lời tri ân sâu sắc đến GS. TS Đặng Quang Á – người đã
dành nhiều thời gian, công sức và tận tình hướng dẫn khoa học cho em trong suốt
quá trình hình thành và hồn chỉnh luận văn.
Xin chân thành cảm ơn Quý Thầy, Cô đã giảng dạy, truyền đạt cho em
những tri thức quý báu, thiết thực trong suốt khóa học.
Cuối cùng xin bày tỏ lịng biết ơn đối với gia đình, người thân, bạn bè, đồng
nghiệp đã giúp đỡ, động viên, đóng góp ý kiến quý báu cho em trong việc hoàn
thành luận văn này.

Thái Nguyên, ngày tháng năm 2014

Tác giả

Hồng Xn Thái

Số hóa bởi Trung tâm Học liệu

/>

5

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi dưới sự hướng
dẫn trực tiếp của GS.TS. Đặng Quang Á.
Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệu
tham khảo theo đúng qui định.
Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin
chịu hoàn toàn trách nhiệm.

Thái Nguyên, ngày tháng năm 2014
Tác giả

Hồng Xn Thái

Số hóa bởi Trung tâm Học liệu

/>

6

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Tiếng Anh
Từ viết tắt

Tên đầy đủ

Diễn giải

GA

Genetic Algorithm

Giải thuật di truyền

LP

Linear Programming

Quy hoạch tuyến tính

NP

Nondeterministic Polynomial
Time

Thuật tốn bất định trong thời gian
đa thức

SA

Simulated Annealing


Giải thuật luyện thép

SCP

Set Covering Problem

Bài toán phủ tập hợp

Tiếng Việt
BTQHTT

Bài tốn quy hoạch tuyến tính

BTQHPT

Bài tốn quy hoạch phi tuyến

BTQHL

Bài tốn quy hoạch lồi

BTQHTP

Bài tốn quy hoạch tồn phƣơng

Số hóa bởi Trung tâm Học liệu

/>


7

DANH MỤC BẢNG
Trang
Bảng 3.1. Danh sách các bác sĩ và các dịch vụ mà bác sĩ đó có thể thực hiện trong
trƣờng hợp tổng quát .................................................................................................58
Bảng 3.2. Thời gian trung bình (miligiây) ................................................................70

Số hóa bởi Trung tâm Học liệu

/>

8

DANH MỤC HÌNH
Trang
Hình 1.1 Mơ hình phân lớp các bài tốn P, NP, CO-NP, NP-Complete, NP-hard 15
Hình 1.2. Đồ thị hàm f(x)

17

Hình 2.1. Thuật tốn Meta-RaPS tìm giải pháp cơ sở

38

Hình 2.2. Thủ tục cập nhật

38

Hình 2.3. Thủ tục tìm giải pháp láng giềng


39

Hình 2.4. Thuật tốn Meta-RaPS giải bài tốn SCP

40

Hình 2.5. Ví dụ bài tốn SCP

42

Hình 2.6. Kết quả sau khi thực hiện thuật tốn tham lam

43

Hình ví dụ thuật tốn tham lam

44

Hình 2.7. Kết quả cây phân nhánh

52

Hình 2.8. Ma trận chi phí của bài tốn ngƣời du lịch

54

Hình 2.9. Cây phân nhánh giải bài tốn ngƣời du lịch

54


Hình 3.1. Giao diện chính của chƣơng trình

67

Hình 3.2. Giao diện nạp dữ liệu

68

Hình 3.3. Giao diện phân lịch bằng thuật tốn tham lam

68

Hình 3.4. Giao diện phân lịch bằng thuật tốn tham lam

69

Hình 3.5. Giao diện lƣu kết quả phân lịch

69

Hình 3.6. Đồ thị biểu diễn thời gian thực hiện trung bình

70

Số hóa bởi Trung tâm Học liệu

/>

9


MỞ ĐẦU
1. Lý do chọn đề tài
Bài toán tối ƣu tổ hợp là dạng bài tốn có độ phức tạp tính tốn cao thuộc lớp
NP khó. Đã có nhiều giải thuật đƣợc đƣa ra để giải quyết bài toán trên nhƣ họ giải
thuật kiến (Ant Algorithm), giải thuật luyện thép SA (Simulated Annealing), giải
thuật di truyền GA (Genetic Algorithm) và giải thuật Meta-Heuristic. Những giải
thuật này đã giải quyết các bài toán với hiệu quả cao và cho kết quả lời giải gần tối
ƣu.
Với độ phức tạp tính tốn cao của các bài toán tối ƣu tổ hợp cũng nhƣ địi hỏi
về mặt thời gian, việc giải các bài tốn này với tính chất tuần tự của các giải thuật sẽ
gặp phải những vấn đề về thời gian thực hiện chƣơng trình, tốc độ xử lý, khả năng
lƣu trữ của bộ nhớ, xử lý dữ liệu với quy mô lớn, … Kích thƣớc bài tốn tăng lên và
khơng gian tìm kiếm càng lớn yêu cầu cần phải có các giải thuật để tăng tốc độ và
hiệu quả của giải thuật.
Bài toán phủ tập hợp (set covering problem) là một bài toán tối ƣu tổ hợp cơ
bản. Dạng bài toán này có rất nhiều trong thực tế nhƣ: lập lịch biểu, lập kế hoạch
sản xuất, định tuyến, phân bổ đầu tƣ, …Đã có nhiều nghiên cứu về phƣơng pháp
hiệu quả để giải quyết bài toán này bao gồm các giải thuật heuristic, thuật toán sử
dụng ý tƣởng tham lam (Greedy Method) và các thuật toán sử dụng các phƣơng
pháp của quy hoạch ngun.
Vì vậy, việc tìm hiểu bài tốn dạng phủ tập hợp, các thuật toán giải quyết bài
toán để từ đó ứng dụng vào trong thực tế là một việc làm có ý nghĩa khoa học và
thực tiễn. Đây chính là mục đích của luận văn này.
2. Đối tƣợng nghiên cứu
Đối tƣợng nghiên cứu của luận văn này là bài toán phủ tập hợp và các vấn đề
liên quan, các thuật toán để giải quyết pài toán phủ tập hợp.

Số hóa bởi Trung tâm Học liệu


/>

10

3. Phạm vi nghiên cứu
Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết
nhƣ: Lý thuyết các bài toán NP-hard, quy hoạch tuyến tính, quy hoạch nguyên, các
phƣơng pháp giải chúng và áp dụng vào bài toán phủ tập hợp.
4. Nhiệm vụ nghiên cứu
-

Tìm hiểu và hệ thống các kiến thức cơ sở về lý thuyết các bài tốn NP-hard

-

Tìm hiểu về quy hoạch toán học, bài toán phủ tập hợp và ứng dụng.

-

Tìm hiểu một vài thuật tốn chính xác giải bài toán phủ tập hợp.

-

Cài đặt và thử nghiệm một vài thuật tốn.

5. Những nội dung nghiên cứu chính
Bố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đối tƣợng và
nhiệm vụ nghiên cứu của đề tài. Chƣơng một, tập trung trình bày những kiến thức
tổng quan về lý thuyết NP-hard và quy hoạch toán học. Chƣơng hai, giới thiệu bài
toán phủ tập hợp, một số kết quả lý thuyết về bài toán phủ tập hợp, trình bày thuật

tốn Heuristic và thuật tốn chính xác giải bài toán phủ tập hợp. Chƣơng 3, ứng
dụng những kiến thức về bài toán phủ tập hợp và những thuật tốn đã trình bày,
trong chƣơng này chúng tơi trình bày phần cài đặt chƣơng trình ứng dụng.
Với những kết quả đạt đƣợc, phần cuối của luận văn nêu ra những phép đo
tính hiệu quả của nghiên cứu, đánh giá thuật toán và nêu vài đề xuất nhằm tối ƣu
thuật toán, đánh giá các kết quả đạt đƣợc, những hạn chế và đề xuất hƣớng nghiên
cứu tiếp theo của đề tài.
6. Phƣơng pháp nghiên cứu
-

Phƣơng pháp đọc tài liệu

-

Phƣơng pháp quan sát

-

Phƣơng pháp phân tích – tổng hợp lý thuyết.

-

Phƣơng pháp thực nghiệm.

Số hóa bởi Trung tâm Học liệu

/>

11


Chƣơng 1. TỔNG QUAN
KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TỐN NP-HARD

1.1.

1.1.1. Định nghĩa về lớp bài tốn P và NP
1.1.1.1. Khái niệm các loại thời gian tính
Thời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiện thuật
toán với mọi bộ dữ liệu đầu vào kích thƣớc n.
Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuật tốn
với mọi bộ dữ liệu đầu vào có kích thƣớc n.
Thời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toán trên
một tập hữu hạn các bộ dữ liệu đầu vào có kích thƣớc n. Thời gian tính trung bình
đƣợc tính theo cơng thức sau:
Thời gian tính trung bình=(Tổng thời gian tính tất cả các bộ dữ liệu có thể)/ Số
bộ dữ liệu.
Định nghĩa 1.1 [1]. Bài toán quyết định là bài toán mà đầu ra chỉ có thể là „yes‟
hoặc „no‟ (đúng/sai, 0/1).
Đối với một bài tốn quyết định, có những bộ dữ liệu vào cho ra câu trả lời (đầu
ra) là „yes‟, chúng ta gọi đây là bộ dữ liệu „yes‟, nhƣng cũng có những bộ dữ liệu
vào cho ra câu trả lời là „no‟, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu „no‟.
1.1.1.2. Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài tốn quyết định có một đặc điểm chung, đó là để xác nhận câu
trả lời ặc điểm chung, đó là để xác nhận câu trả lời „yes‟ đối với bộ dữ liệu vào
„yes‟ của chúng, chúng ta có thể đƣa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận
câu trả lời „yes‟ cho bộ dữ liệu vào „yes‟ đó. Tính ngắn gọn dễ kiểm tra ám chỉ việc
thời gian kiểm tra để đƣa ra kết quả chỉ mất thời gian đa thức. Ví dụ về những bài
toán quyết định kiểu này:
-


Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu trả
lời „yes‟ cho đầu vào n, chúng ta có thể đƣa ra một ƣớc số b (1Để kiểm tra xem b có phải là ƣớc số của n chúng ta có thể thực hiện phép chi

Số hóa bởi Trung tâm Học liệu

/>

12

n cho b sau thời gian đa thức. Trong ví dụ này, b là bằng chứng ngắn gọn (vì
bcủa n không).
-

Đối với bài toán Hamilton, để xác nhận câu trả lời „yes‟ cho đồ thị đã cho G,
chúng ta có thể đƣa ra một chu trình Hamilton của đồ thị:
v1, v2, v3, …, vn, v1

Việc kiểm tra dãy đỉnh nói trên có là chu trình Hamilton của đồ thị đã cho hay
khơng có thể thực hiện sau thời gian đa thức. Khi đó chúng ta nói dãy đỉnh nói trên
là bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời „yes‟ của bài tốn
Hamilton.
-

Đối với bài tốn về tính chấp nhận đƣợc của biểu thức Bun, để xác nhận câu
trả lời „yes‟ đối với một biểu thức đã cho, chúng ta chỉ cần đƣa ra một bộ giá
trị các biến số mà tại đó biểu thức nhận giá trị true. Việc tính giá trị của biểu
thức tại một bộ giá trị có thể thực hiện sau thời gian đa thức.

Một các tƣơng tự, có thể đƣa ra khái niệm bằng chứng ngắn gọn dễ kiểm tra để
xác định câu trả lời „no‟. Đối với mỗi bài toán, việc đƣa ra bằng chứng ngắn gọn dễ
kiểm tra để xác nhận câu trả lời „no‟ là dễ dàng hơn so với việc đƣa ra bằng chứng
ngắn gọn xác định câu trả lời là „yes‟.
1.1.1.3. Khái niệm quy dẫn
Định nghĩa 1.2 [1]. Giả sử chúng ta có hai bài tốn quyết định A và B. Chúng
ta nói A có thể quy dẫn về B nếu như sau một thời gian tính đa thức nếu tồn tại một
thuật toán thời gian đa thức R cho phép biến đổi bộ dữ liệu x của A thành bộ dữ
liệu vào R(x) của B sao cho x là bộ dữ liệu yes của A khi và chỉ khi R(x) là dữ liệu
vào yes của B.
Nếu A quy dẫn về đƣợc B sau thời gian đa thức và B có thể giải đƣợc sau thời
gian đa thức thì A cũng có thể giải đƣợc sau thời gian đa thức.
1.1.1.4. Lớp bài toán P.
Định nghĩa 1.3 [1]. Chúng ta gọi P là lớp các bài tốn có thể giải được trong
thời gian đa thức, NP là lớp các bài toán quyết định mà để xác định câu trả lời

Số hóa bởi Trung tâm Học liệu

/>

13

“yes” của nó chúng ta có thể đưa ra các bằng chứng ngắn gọn dễ kiểm tra, co-NP
là lớp các bài toán quyết định mà để xác định câu trả lời “no” của nó chúng ta có
thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 1.1. Bài tốn cây khung nhỏ nhất giải đƣợc nhờ thuật toán Prim với thời
gian O(n2) thuộc lớp bài toán P.
1.1.1.5. Lớp bài toán NP
Định nghĩa 1.4 [1]. Ta gọi NP là lớp các bài toán quyết định mà để xác nhận
câu trả lời “yes” của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.

Ví dụ 1.2. Bài tốn kiểm tra tính hợp số: “Có phải n là hợp số không?”, để xác
nhận câu trả lời “yes” cho đầu vào n ta có thể đƣa ra một ƣớc số b (1Để kiểm tra xem b có phải là ƣớc số của n hay khơng ta có thể thực hiện phép chia
n cho b sau thời gian đa thức. Trong ví dụ này dễ thấy b là bằng chứng ngắn gọn
(bƣớc số của n).
1.1.1.6. Lớp bài tốn Co-NP
Định nghĩa 1.5 [1]. Ta gọi Co-NP là lớp các bài toán quyết định mà để xác
nhận câu trả lời “no” của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 1.3. Bài tốn kiểm tra tính ngun tố: “Có phải n là số ngun tố
khơng?”, để đƣa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời “no” cho
đầu vào n ta có thể đƣa ra một ƣớc số b của n.
1.1.1.7. Lớp bài toán NP-đầy đủ (NP-Complete)
Định nghĩa 1.6 [1]. Một bài toán quyết định A được gọi là NP-đầy đủ (NPComplete) nếu như:
-

A là một bài toán NP

-

Mọi bài toán trong NP đều có thể quy dẫn về A

Bổ đề. Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc NP, và bài toán A quy
dẫn đƣợc về bài tốn B. Khi đó bài tốn B cũng là NP-đầy đủ.

Số hóa bởi Trung tâm Học liệu

/>

14

1.1.1.8. Lớp bài tốn NP-khó (NP-Hard)
Một cách ngắn gọn có thể hiểu bài tốn NP-Hard là bài tốn mà khơng có thuật
tốn thời gian tính đa thức để giải nó trừ khi P=NP, mà chỉ có các thuật tốn giải
trong thời gian hàm mũ.
Định nghĩa 1.7 [1]. Một bài toán A được gọi là NP-khó (NP-Hard ) nếu như sự
tồn tại thuật tốn đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải
mọi bài tốn trong NP.
1.1.2. Các ví dụ về bài tốn NP
Bài tốn bè cực đại (MaxClique): Cho đồ thị vơ hƣớng G=(V, E). V là tập các
đỉnh, E là tập các cạnh tƣơng ứng các đỉnh trong V. Cần tìm bè lớn nhất của G. Bè
là tập các đỉnh trong đồ thị mà đơi một có cạnh nối với nhau (là một đồ thị con đầy
đủ trong đồ thị G).
Bài toán tập độc lập (Independsent set): Cho đồ thị vô hƣớng G=(V, E) và số
ngun K, hỏi có thể tìm đƣợc tập độc lập S với |S| ≥ K. Tập độc lập là tập các đỉnh trong
đồ thị mà chúng đôi một khơng có cạnh nối với nhau.
Bài tốn phủ đỉnh (Vertex cover ): Ta gọi một phủ của đồ thị vô hƣớng G = (V, E) là
một tập con các đỉnh của đồ thị S

V sao cho mỗi cạnh của đồ thị có ít nhất một đầu

mút trong S. Bài tốn đặt ra là: Cho đồ thị vơ hƣớng G = (V, E) và số nguyên k. Hỏi G
có phủ đỉnh với kích thƣớc k hay khơng?
Một cách khơng hình thức, có thể nói rằng nếu ta có thể giải đƣợc một cách hiệu quả
một bài tốn NP-khó cụ thể, thì ta cũng có thể giải hiệu quả bất kỳ bài toán NP bằng cách
sử dụng thuật toán giải bài tốn NP-khó nhƣ một chƣơng trình con.
Từ định nghĩa bài tốn NP-khó có thể suy ra rằng mỗi bài tốn NP-đầy đủ đều là NPkhó. Tuy nhiên một bài tốn NP-khó khơng nhất thiết phải là NP-đầy đủ.
Cũng từ bổ đề nêu trên, ta có thể suy ra rằng để chứng minh một bài tốn A nào đó là
NP-khó, ta chỉ cần chỉ ra phép qui dẫn một bài toán đã biết là NP-khó về nó.
Từ phần trình bày trên, ta thấy có rất nhiều bài tốn ứng dụng quan trọng thuộc vào

lớp NP-khó, và vì thế khó hy vọng xây dựng đƣợc thuật toán đúng hiệu quả để giải chúng.

Số hóa bởi Trung tâm Học liệu

/>

15

Do đó, một trong những hƣớng phát triển thuật tốn giải các bài toán nhƣ vậy là xây dựng
các thuật tốn gần đúng.

Hình 1.1 Mơ hình phân lớp các bài toán P, NP, CO-NP, NP-Complete và NPhard
1.2.

LÝ THUYẾT QUY HOẠCH TỐN HỌC

Tối ƣu hóa, đƣợc khởi nguồn nhƣ một ngành của Tốn học, có rất nhiều ứng
dụng hiệu quả và rộng rãi trong quy hoạch tài nguyên, thiết kế chế tạo máy, điều
khiển tự động, quản trị kinh doanh, kiến trúc đô thị, công nghệ thông tin, trong việc
tạo nên các hệ hỗ trợ ra quyết định trong quản lý và phát triển các hệ thống lớn.
Chính vì vậy, các lĩnh vực của Tối ƣu hóa ngày càng trở nên đa dạng, mang nhiều
tên gọi khác nhau nhƣ Quy hoạch toán học, Điều khiển tối ƣu, Vận trù học, lý
thuyết trị chơi …
Có thể tạm định nghĩa quy hoạch tuyến tính là lĩnh vực tốn học nghiên cứu các
bài tốn tối ƣu mà hàm mục tiêu (vấn đề đƣợc quan tâm) và các ràng buộc (điều
kiện của bài toán) đều là hàm và các phƣơng trình hoặc bất phƣơng trình tuyến tính.

Số hóa bởi Trung tâm Học liệu

/>

16

Đây chỉ là một định nghĩa mơ hồ, bài toán quy hoạch tuyến tính sẽ đƣợc xác định rõ
ràng hơn thơng qua các ví dụ.
Các bƣớc nghiên cứu và ứng dụng một bài tốn quy hoạch tuyến tính điển hình
là nhƣ sau:
-

Xác định vấn đề cần giải quyết, thu thập dữ liệu

-

Lập mơ hình tốn học

-

Xây dựng các thuật tốn để giải bài tốn đã mơ hình hóa bằng ngơn ngữ
thuận lợi cho việc lập trình cho máy tính.

-

Tính tốn thử và điều chỉnh mơ hình nếu cần.

-

Áp dụng giải các bài toán thực tế.

1.2.1. Khái niệm chung
1.2.1.1. Bài toán tối ưu tổng quát

Tối ƣu hóa là một trong những lĩnh vực kinh điển của tốn học có ảnh hƣởng
đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế - xã hội. Trong thực tế,
việc tìm giải pháp tối ƣu cho một vấn đề nào đó chiếm một vai trò hết sức quan
trọng. Phƣơng pháp tối ƣu là phƣơng pháp hợp lý nhất, tốt nhất, tiết kiệm chi phí,
tài nguyên, nguồn lực mà lại cho hiệu quả cao.
Ví dụ 1.4. Tìm

x

D

2.2,1.8

R1

3
sao cho f ( x) x 3x 1

Max

Bài tốn tối ƣu trên có dạng cực đại hóa đƣợc giải nhƣ sau: Cho
f '( x) 3x 2 3 0 , ta có các điểm tới hạn là x=-1 và x=+1. Xét giá trị hàm số f(x) tại

thời điểm tới hạn vừa tìm đƣợc và tại các giá trị x = -2.2 và x = 1.8 (các điểm đầu
mút của đoạn [-2.2, 1.8]), ta có f(-2.2) = -3.048, f(-1)=3, f(1.8)= 1.432. Vậy giá trị x
cần tìm là x= -1. Kết quả của bài toán đƣợc minh họa trên hình I.1

Số hóa bởi Trung tâm Học liệu

/>

17

Hình 1.2. Đồ thị hàm f(x)
Cho hàm số f : D
với x D

Rn

R . Bài toán tối ƣu tổng quát có dạng: Max (Min) f(x),

Rn . Nhƣ vậy, cần tìm điểm x ( x1 , x2 ,..., xn ) D

Rn sao cho hàm mục

tiêu f(x) đạt đƣợc giá trị lớn nhất đối với bài tốn Max – cực đại hóa (giá trị bé nhất
đối với bài toán Min – cực tiểu hóa).
Điểm x ( x1 , x2 ,..., xn ) D

Rn đƣợc gọi là phƣơng án khả thi (hay phƣơng án

chấp nhận đƣợc hoặc phƣơng án, nếu nói vắn tắt) của bài toán tối ƣu: Max (Min)
f(x), với x D

Rn . Miền D đƣợc gọi là miền ràng buộc. Các tọa độ thành phần

của điểm x đƣợc gọi là các biến quyết định, còn x cũng đƣợc gọi là vectơ quyết
định.
Xét bài tốn cực đại hóa: Max f(x), với x D

*
Rn . Điểm x

( x1* , x*2 ,..., x*n ) R n

*
đƣợc gọi là điểm tối ƣu (hay phƣơng án tối ƣu) toàn cục nếu x D và

f ( x* )

f ( x), x

D . Điểm x

R n đƣợc gọi là điểm tối ƣu (hay phƣơng án tối ƣu)

Số hóa bởi Trung tâm Học liệu

/>

18

địa phƣơng nếu x D và tồn tại một lân cận N
f ( x)

f ( x), x

đủ nhỏ của điểm x sao cho

D.

N

Đối với bài tốn cực tiểu hóa Min f(x), với x D

Rn , điểm x*

*
*
điểm tối ƣu (hay phƣơng án tối ƣu) toàn cục nếu x D và f ( x )

Rn đƣợc gọi là
f ( x), x

D.

n
Điểm x R đƣợc gọi là điểm tối ƣu (hay phƣơng án tối ƣu) địa phƣơng nếu x D

và tồn tại một lân cận N đủ nhỏ của điểm x sao cho f ( x)

f ( x), x

N

D

.

Dễ thấy, mọi phƣơng án tối ƣu toàn cục cũng là phƣơng án tối ƣu địa phƣơng,
trong khi đó một phƣơng án tối ƣu địa phƣơng khơng nhất thiết là phƣơng án tối ƣu
tồn cục. Trên hình …, điểm x=1 chỉ là phƣơng án tối ƣu địa phƣơng khi xét bài
tốn cực tiểu hóa.
Ví dụ 1.5. Xét bài toán tối ƣu sau: Max f(x)= 8 x1 6 x2 với điều kiện ràng buộc
x D

x1 , x2

R 2 : 4 x1 2 x2

60; 2 x1 4 x2

48, x1

0, x2

0

Bài tốn tối ƣu trên đây cịn đƣợc gọi là bài tốn quy hoạch tuyến tính. Ngƣời ta
đã chứng minh đƣợc rằng mọi phƣơng án tối ƣu địa phƣơng của bài tốn quy hoạch
tuyến tính cũng đồng thời là phƣơng án tối ƣu toàn cục.
1.2.1.2. Phân loại các bài toán tối ưu
Các bài toán tối ƣu, cũng đƣợc gọi là các bài toán quy hoạch toán học, đƣợc chia
thành các lớp sau [2]:
-

Bài toán quy hoạch tuyến tính (BTQHTT)

-

Bài tốn tối ƣu phi tuyến hay cịn gọi là bài toán quy hoạch phi tuyến
(BTQHPT), bao gồm cả bài toán quy hoạch lồi (BTQHL) và bài toán quy
hoạch tồn phƣơng (BTQHTP).

-

Bài tốn tối ƣu rời rạc, bài tốn tối ƣu nguyên và hỗn hợp nguyên.

-

Bài toán quy hoạch động.

Số hóa bởi Trung tâm Học liệu

/>

19

-

Bài toán quy hoạch đa mục tiêu.

-

Bài toán quy hoạch ngẫu nhiên/ mờ …

Các phƣơng pháp toán học giải các lớp bài toán tối ƣu tổng quát nhƣ nêu trên
đây đƣợc gọi là các phƣơng pháp tối ƣu toán học (hay các phƣơng pháp quy hoạch
toán học).

1.2.2. Quy hoạch tuyến tính
1.2.2.1. Phát biểu bài tốn
Bài tốn quy hoạch tuyến tính trong [2] là bài tốn có dạng
n

x0

cjxj

(1)

max

j 1

n

aij x j

bi , i 1, 2,..., l

(2)

aij x j

bi , i

(3)

j 1

n

l 1,..., m

j 1

xj

(4)

0, j 1,..., n

Miền xác định: tập hợp các véc tơ x thỏa mãn (2) và (4)
Phƣơng án bài toán: véc tơ x thỏa mãn (2) và (4)
Nếu ( x1 ,..., xn ) là phƣơng án của bài tốn, x0

n

c j x j thì X

( x0 , x1 ,..., xn ) gọi là

j 1

phƣơng án mở rộng của bài toán (1) – (4).
Phƣơng án X * đạt cực đại (1) gọi là phƣơng án tối ƣu. Phƣơng án mở rộng X *
gọi là phƣơng án tối ƣu mở rộng nếu X * là phƣơng án tối ƣu.
Ký hiệu:

Số hóa bởi Trung tâm Học liệu

/>

20

L – miền xác định của bài toán (1) – (4)
(L, C) – kí hiệu bài tốn qui hoạch tuyến tính (1) – (4)
X(L, C) – phƣơng án tối ƣu của bài toán (1) – (4)
X (L, C) – phƣơng án tối ƣu mở rộng của bài toán (1) – (4)

LC là tập hợp các phƣơng án tối ƣu của bài tốn (L, C)
Bài tốn quy hoạch tuyến tính gọi là giải đƣợc nếu tồn tại phƣơng án tối
ƣu.
1.2.2.2. Dạng chính tắc của bài tốn qui hoạch tuyến tính
n

x0

max

(5)

bi , i 1, 2,..., m

(6)

cjxj
j 1

n

aij x j
j 1

xj

(7)

0, j 1,..., n

a1 j
a2 j

Gọi A j

.
là vectơ điều kiện thứ j của bài toán (5) – (7)
.
amj

b1
b2
B

.

là vectơ ràng buộc của bài toán (5) – (7).

.

bm

Phƣơng án X của bài toán (5) – (7) gọi là tựa nếu các véc tơ điều kiện ứng với
các thành phần dƣơng của nó là độc lập tuyến tính.

Số hóa bởi Trung tâm Học liệu

/>

21

Cơ sở của phƣơng án tựa X là tập hợp

0 . Các thành phần của phƣơng

Aj x j

án tựa ứng với các vectơ cơ sở gọi là các thành phần cơ sở (các biến tƣơng ứng gọi
là biến cơ sở), các thành phần còn lại gọi là các thành phần phi cơ sở (các biến
tƣơng ứng gọi là biến cơ sở).
Nếu X

phƣơng án tựa của bài toán quy hoạch tuyến tính,

x1 ,..., xn

( Aj1 ,..., Ajk ) là cơ sở của phƣơng án tựa, B

tiêu
xi

có

x0 , x1 ,..., xn

xi 0

xij ( x j ), i

thể

biểu

diễn

j1 ,..., jk , N

1,.., n \ B thì hàm mục

qua

biến

các

phi

cơ

sở:

0,1,..., n

j N

Kí hiệu Q n

0,1,..., n

B0

Bảng đơn hình T

xij

0 , N0

B

i Qn , j N 0

N

0

gọi là bảng đơn hình đầy đủ.

Phƣơng án tựa bài tốn (5) – (7) gọi là khơng suy biến nếu số ràng buộc của hệ
(6) – (7) mà phƣơng án thỏa mãn với dấu bằng bằng đúng n (các ràng buộc này là
độc lập tuyến tính). Phƣơng án tựa là suy biến nếu số ràng buộc mà phƣơng án tựa

thỏa mãn chặt là lớn hơn n.
Phƣơng án tựa X của bài tốn (5) – (7) là khơng suy biến nếu các thành phần cơ
sở của nó là dƣơng. Cơ sở của phƣơng án tựa không suy biến xác định duy nhất.
Ứng với phƣơng án tựa suy biến có nhiều cơ sở.
Tiêu chuẩn tối ƣu: để cho phƣơng án mở rộng X '

x0' , x1' ,..., xn' là tối ƣu điều

kiện cần và đủ là tồn tại cơ sở B sao cho
xi

xi'

xij ( x j ), i

0,1,..., n

j N

x0 j

0, j

Số hóa bởi Trung tâm Học liệu

N

/>

22

Giả sử ràng buộc (6) của bài toán (5) – (7) viết ở dạng:
xi

xi 0

xij ( x j ), i

0,1,..., n

j N

Bảng đơn hình tƣơng ứng T
X
X

xij

i Qn , j N 0

x1 , x2 ,..., xn

,
( x10 , x20 ,..., xn 0 ),
n

x1 , x2 ,..., xn

(

c j x j , x1 ,..., xn ).
j 1

Nếu xi 0

0 (i 1, 2,..., n) thì bảng đơn hình T gọi là chấp nhận đƣợc, vectơ X là

phƣơng án tựa của bài toán quy hoạch tuyến tính.
Nếu x0 j

0, j

N thì bảng đơn hình T là chuẩn (đối ngẫu chấp nhận đƣợc),

vectơ X gọi là giả phƣơng án, X gọi là giả phƣơng án mở rộng.
1.2.3. Quy hoạch rời rạc
1.2.3.1. Định nghĩa [2]
Trong các bài tốn quy hoạch tuyến tính, các biến số có thể nhận những giá trị
thực khơng âm. Tuy nhiên, trong thực tiễn thƣờng gặp các bài toán mà các biến số
chỉ có thể nhận một số hữu hạn hay đếm đƣợc giá trị, thƣờng là các giá trị nguyên.
Chẳng hạn sẽ là vô nghĩa khi đƣa ra câu trả lời: cần sản xuất nửa cái bàn hay cần
thuê 2,7 cái ơ tơ để vận chuyển hàng hóa … Trong một số bài toán, chẳng hạn bài
toán vận tải với các lƣợng hàng cung và cầu là các số nguyên, song nhiều bài tốn
khác thì khơng phải nhƣ vậy. vì thế trong chƣơng này sẽ đề cập đến nội dung và
phƣơng pháp giải các bài toán tối ƣu trên lƣới các điểm nguyên hay trên các tập rời
rạc, gọi tắt là bài toán quy hoạch rời rạc hay bài toán quy hoạch ngun. Bài tốn
quy hoạch rời rạc có dạng sau:
Tìm cực đại của hàm f ( x, y) phụ thuộc hai nhóm biến x và y với các ràng buộc
có dạng:

Số hóa bởi Trung tâm Học liệu

/>

23

gi ( x, y ) 0, i 1, 2,..., m, x

Trong đó, x

x1 , x2 ,..., x p , y

y1 , y2 ,..., yq , p

(8)

D

0, q 0 , D là tập hữu hạn các

véc tơ p – chiều, còn f, gi là các hàm tuyến tính và D là lƣới các điểm ngun, thì ta
có bài tốn quy hoạch ngun tuyến tính, cịn nếu D là tập các véc tơ p thành phần 0
hay 1 thì ta có bài toán quy hoạch nguyên 0 – 1.
Nếu q = 0, nghĩa là chỉ có các biến rời rạc x1 , x2 ,..., x p thì ta có bài tốn đƣợc gọi
là bài tốn quy hoạch ngun hồn tồn. Cịn nếu q>0 thì bài tốn đƣợc gọi là bài
tốn ngun bộ phận.
1.2.3.2. Các bài toán thực tế dẫn tới quy hoạch rời rạc
 Bài tốn vận tải
Có m kho hàng (điểm phát) chứa một loại hàng hóa, lƣợng hàng ở kho i là ai và
n nơi tiêu thụ (điểm thu), nhu cầu ở nơi thu là b j , cij là chi phí vận chuyển một đơn

vị hàng từ điểm phát i đến điểm thu j. Xác định các lƣợng hàng vận chuyển xij từ
các điểm phát i tới các điểm thu j sao cho tổng chi phí là nhỏ nhất và nhu cầu các
điểm thu đƣợc thỏa mãn.
Dạng toán học của bài toán là:
cij xij

(9)

min

ij

n

xij

ai , i 1, 2,..., m

(10)

xij

b j , j 1, 2,..., n

(11)

j 1

m
i 1

xij

(12)

0

m

n

ai
i 1

bj

(13)

j 1

Nếu các ai và bj là nguyên thì đa diện lồi xác định bởi các ràng buộc của bài
tốn có mọi đỉnh đều là nguyên. Do đó ta có thể dùng phƣơng pháp đơn hình để giải
bài tốn quy hoạch tuyến tính này, lời giải cuối cùng nhận đƣợc sẽ là một phƣơng

Số hóa bởi Trung tâm Học liệu

/>

24

án ngun.
 Bài tốn phân việc
Có n đơn vị sản xuất cần sản xuất n loại sản phẩm, cij là chi phí cho đơn vị i sản
xuất sản phẩm j. Hãy phân công mỗi đơn vị sản xuất một sản phẩm để tổng chi phí
là nhỏ nhất.
Dạng tốn học của bài toán là:
n

n

cij xij

min

i 1 j 1

n

xij 1, i 1, 2,..., n
j 1

m

xij 1, j 1, 2,..., n
i 1

xij {0;1}

 Bài tốn cái túi
Có một cái túi chứa đƣợc nhiều nhất một trọng lƣợng là b, có n đồ vật cần

mang, đồ vật j nặng aj, giá trị của nó là cj. Bài toán đặt ra là cho những đồ vật nào
vào túi để tổng giá trị của nó lớn nhất. Ký hiệu xj là số đồ vật j đƣợc đƣa vào túi.
Dạng toán học của bài toán là:
n

cjxj

max

j 1
n

ajxj

b

j 1

xj

0, x j

Z

 Bài toán xếp hàng lên tàu
Một tàu chở hàng có trọng tải T và thể tích K, tàu chở n loại hàng, hàng loại j có
số lƣợng là sj, có trọng lƣợng là aj, thể tích bj và giá trị sử dụng là cj. Bài toán đặt ra

Số hóa bởi Trung tâm Học liệu

/>