ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
——————-

HỒ THỊ THU THỦY

PHƯƠNG PHÁP GIẢI BÀI TOÁN
TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - 2016



ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
——————-

HỒ THỊ THU THỦY

PHƯƠNG PHÁP GIẢI BÀI TOÁN
TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH

Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12

LUẬN VĂN THẠC SĨ KHOA HỌC

Người hướng dẫn khoa học: PGS. TS. Tạ Duy Phượng



7

1.1. Một số kết quả của giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2. Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

1.2.1. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2. Phương pháp đơn hình giải bài toán QHTT . . . . . . . . . . . . . . . . . . . . . . . . .

13
16

Chương 2. Bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . . . . . . . . . . . . .

23

2.1. Khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.2. Phương pháp đơn hình giải bài toán tối ưu đa mục tiêu tuyến tính



3.2.1. Thuật toán trọng số giải bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . 50
3.2.2. Thuật toán đơn hình chứa tham số của bài toán tối ưu hai mục tiêu tuyến
tính. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3


3.2.3. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

4


LỜI MỞ ĐẦU
Trong mọi lĩnh vực của cuộc sống, ta luôn quan tâm tới bài toán tìm ra phương
án tốt nhất để đạt mục tiêu mong muốn trong những điều kiện ràng buộc nhất định.
Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải
pháp tốt nhất về định lượng và định tính. Trong những năm gần đây, các phương
pháp tối ưu hóa ngày càng được áp dụng sâu rộng và hiệu quả vào kinh tế, kỹ thuật,
công nghệ thông tin và các ngành khoa học khác.

dụng trong quy hoạch đa mục tiêu.
Khi k (k ≥ 2) , các hàm mục tiêu đều là hàm tuyến tính và miền ràng buộc là
tập lồi đa diện khác rỗng trong Rk , ta nhận được bài toán quy hoạch tuyến tính đa
mục tiêu. Cho tới nay, có rất nhiều thuật toán đưa ra để xác định một phần hoặc
toàn bộ tập nghiệm hữu hiệu của bài toán, chẳng hạn: phương pháp vô hướng hoá,
phương pháp tham số, phương pháp đơn hình đa mục tiêu và các dạng cải biên,
phương pháp nón pháp tuyến,... Tuy nhiên, khối lượng tính toán của các thuật toán
này tăng nhanh khi kích thước của bài toán quy hoạch tuyến tính đa mục tiêu (tức
số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm
mục tiêu) tăng.
Trong những năm gần đây nhiều nhà toán học đó chuyển sang nghiên cứu giải
quyết bài toán quy hoạch tuyến tính đa mục tiêu. Luận văn này chủ yếu trình bày
phương pháp đơn hình giải bài toán quy hoạch tuyến tính đa mục tiêu trong không
gian Rk , dựa trên giáo trình "Multiobjective Linear Programming: An Introduction"
của GS. Đinh Thế Lục, Springer International Publishing Switzerland (2016); và
bài giảng "Multiobjective Linear Programming Theory" của Matthias Ehrgott, The
University of Auckland, New Zealand (2007).
Nội dung chính của luận văn là trình bày các phương pháp đơn hình để giải bài
toán quy hoạch tuyến tính, một trong những phương pháp phổ biến nhất trong toán
học tính toán. Ngoài phần Mục lục, Mở đầu và Tài liệu trích dẫn nội dung chính của
luận văn gồm ba chương.
• Chương 1 dành cho việc giới thiệu một số khái niệm cơ bản về giải tích lồi,
trình bày bài toán quy hoạch tuyến tính (QHTT) và phương pháp đơn hình
giải bài toán quy hoạch tuyến tính một mục tiêu.
• Chương 2 trình bày bài toán tối ưu đa mục tiêu tuyến tính.
• Chương 3 trình bày phương pháp đơn hình và thuật toán giải bài toán tối ưu
đa mục tiêu tuyến tính; phương pháp trọng số giải bài toán tối ưu đa mục
tiêu tuyến tính và thuật toán đơn hình chứa tham số của bài toán tối ưu tuyến
tính hai mục tiêu.
Hà Nội, ngày 24 tháng 12 năm 2016


α} , H + = {x : a, x

α} ,

mỗi nửa không gian này ở về một phía của siêu phẳng và phần chung của chúng
chính là siêu phẳng H. Tương tự, siêu phẳng H cũng chia Rn thành hai nửa không
gian mở
{x : a, x < α} ,
{x : a, x > α} .
7


Định nghĩa 1.1.1.
• Tập Q ⊆ Rn được gọi là tập afin nếu Q chứa trọn cả đường thẳng đi qua hai
điểm bất kỳ của Q, tức là ∀a, b ∈ Q, λ ∈⇒ (1 − λ ) a + λ b ∈ Q.
• Bao afin (affine hull) của một Q ⊆ Rn tập là giao của tất cả các tập afin
chứa Q. Đó là tập afin nhỏ nhất chứa Q, ký hiệu là a f f (Q).
Định nghĩa 1.1.2. Giả sử Q ⊆ Rn là một tập hợp khác rỗng.
• Tập Q được gọi là tập lồi (convex set) nếu nó chứa trọn đoạn thẳng nối hai
điểm bất kỳ thuộc Q, tức là với mọi x, y ∈ Q và mỗi số thực λ ∈ [0, 1], thì ta
có
λ x + (1 − λ )y ∈ Q. (Hình 1.1)

Hình 1.1: Tập lồi.

• Giả sử x1 , . . . , xk ∈ Rn là k điểm của Q. Khi đó
k

k

Định nghĩa 1.1.3. Giả sử Q ⊆ Rn là một tập hợp khác rỗng.
• Tập Q được gọi là một nón (cone) nếu với mọi x ∈ Q và mọi λ ≥ 0 ta có
λ x ∈ Q (Hình 1.3).
• Một nón Q được gọi là nón lồi nếu Q đồng thời là một tập lồi.

Hình 1.3: Nón lồi

Nón không lồi

• Bao nón (conic hull) của một tập Q, ký hiệu là cone(Q) là
cone (Q) := {ta : a ∈ Q,t ∈ R,t

0} .

• Bao lồi dương của một tập Q, ký hiệu là pos (Q) , là
k

pos (Q) :=

∑ ti ai : ai ∈ Q,ti ∈ R,ti

0, i = 1, . . . , k, k ∈ N

i=1

Định nghĩa 1.1.4.
• Cho tập Q bất kỳ, một điểm x gọi là điểm trong của Q, nếu
∃ε > 0 : B(x, ε) := {x ∈ Rn : x − x0 < ε} ⊂ Q.
Tập hợp các điểm trong của tập Q được ký hiệu là int Q.
9

H = {x ∈ Rn : v, x = α} ,
là một siêu phẳng với v khác không. Ta nói H là một siêu phẳng tựa (supporting hyperplane) của P tại một điểm x ∈ P nếu giao của H với P chứa x
và P được chứa hoàn toàn trong một nửa không gian đóng xác định bởi H.
(Hình 1.4).
• Tập khác rỗng H ∩ P được gọi là một diện (hay mặt) của P. Một tập con khác
rỗng F của P là một mặt nếu có một véctơ khác không v ∈ Rn mà
v, y ≤ v, x với mọi x ∈ F, y ∈ P.
10


Hình 1.4: Siêu phẳng tựa
Theo quy ước P cũng là một mặt của chính nó và được gọi là mặt chính thường.
Định nghĩa 1.1.7.
• Một điểm x ∈ Q được gọi là điểm cực biên (hay là đỉnh) của Q, nếu không
tồn tại a, b ∈ Q, a = b, λ ∈ (0, 1) sao cho x = λ a + (1 − λ ) b.
• Mặt có chiều bằng 1 được gọi là cạnh biên. Hai đỉnh kề nhau nếu chúng là
điểm cuối của cạnh biên.
• Một cạnh vô hạn được gọi là một tia cực biên (hay là một diện nửa đường
thẳng). Phương của tia cực biên được gọi là phương cực biên (extreme directions).
Nhận xét 1.1.1. Đỉnh của tập lồi đa diện P là một diện có thứ nguyên bằng 0. Số
điểm cực biên của một tập lồi có thể hữu hạn hoặc vô hạn. Khi tập lồi có hữu hạn
điểm cực biên thì chúng thường được gọi là các đỉnh. Nếu P là một đa diện lồi thì
tập các phương cực biên bằng rỗng.
Định nghĩa 1.1.8.
• Cho Q là một tập lồi khác rỗng trong Rn . Một véctơ v = 0 được gọi là một
tiệm cận (asymptotic) hoặc hướng lùi xa (recession direction) của Q, nếu
mọi tia xuất phát từ một điểm bất kỳ của Q theo phương v đều nằm trọn
trong Q, tức là v là phương lùi xa khi và chỉ khi
x + tv ∈ Q



1.2.

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

1.2.1.

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

Bài toán quy hoạch tuyến tính (QHTT) (Linear Programming) có thể được phát
biểu dưới dạng:
Tìm cực đại
c, x
với điều kiện
Ax = b,
(1.2.2)
x 0,
trong đó A = (ai j )m×n được gọi là ma trận hệ số ràng buộc, b ∈ Rm hay b =
(b1 , . . . , bm )T được gọi là véc tơ vế phải và điểm x ∈ Rn hay x = (x1 , . . . , xn )T được
gọi là các biến cần tối ưu.
Hàm tuyến tính x → c, x là hàm mục tiêu hay hàm giá (cost function).
• Bài toán (LP) được cho bởi ràng buộc (1.2.2) được gọi là chuẩn tắc (standard
form). Nó được gọi là chính tắc (canonical form) khi ràng buộc (1.2.2) thay
bằng bất đẳng thức Ax ≤ b.
• Vì phương trình tuyến tính có thể được chuyển thành bất phương trình tuyến
tính và ngược lại, nên bất kỳ bài toán quy hoạch tuyến tính đều có thể đưa
về dạng (LP) ở trên.
• Điểm x ∈ Rn thỏa mãn mọi ràng buộc của bài toán được gọi là điểm chấp
nhận được hay là một phương án. Tập hợp tất cả các phương án, ký hiệu là
X, được gọi là tập ràng buộc hay tập chấp nhận được của bài toán (LP), tức

Cho X khác rỗng. Bốn điều kiện sau là tương đương.
(i) (LP) có nghiệm tối ưu.
(ii) (LP) có nghiệm tối ưu đạt tại đỉnh.
(iii) Hàm giá là không dương trên mỗi phương tiệm cận của X.
(iv) Hàm giá là bị chặn trên trên X.
Chứng minh. (i) ⇒ (iv). Hiển nhiên.
(iv) ⇒ (iii). Giả sử α là cận trên của hàm giá trên X và giả sử u là phương tiệm cận
không bằng 0 của X nếu nó tồn tại. Vì X = 0, nên có thể chọn điểm x bất kỳ. Do u
là phương tiệm cận nên với mỗi số dương t, điểm x + tu thuộc X. Do đó
c, x + tu = c, x + t c, u

α.

Bất đẳng thức này đúng với mọi dương t, suy ra c, u
0.
(iii) ⇒ (ii). Giả sử v1 , ..., v p là tập các đỉnh và giả sử u1 , ..., uq là tập hợp các
tia cực biên của đa diện X. Chú ý răng, tập hợp các tia cực biên có thể là rỗng. Chọn
đỉnh vi0 sao cho
c, vi0 = max c, v1 , ..., c, v p .
14


Giả sử x là điểm bất kỳ trong X. Theo Định lý 2.4.9 [4], có các số không âm ti và s j
p

p

q

i=1

(i) Giả sử x là nghiệm chấp nhận được bất kỳ của bài toán. Khi đó x là nghiệm của
hệ Ax = b, cơ sở xB của x tương ứng với cột cơ sở của B là các tọa độ phi cơ sở của
nó qua
xB = B−1 b − B−1 NxN = x¯B − B−1 NxN .
(1.2.3)
Giá trị của hàm giá tại x là
c, x = cB , xB + cN , xN
= cB , B−1 b − B−1 NxN + cN , xN
= cB , x¯B + c¯N , xN
= c, x¯ + c¯N , xN .
Vì xN là dương và giả thiết c¯N là âm, nên c, x
c, x¯ . Vì x là nghiệm chấp nhận
được tùy ý của bài toán, ta suy ra x¯ là nghiệm tối ưu và B là một cơ sở tối ưu.
(ii) Giả sử ngược lại, véctơ giá không âm, tức là tồn tại c¯ j > 0, với một chỉ số phi
cơ sở j.
Ta tìm nghiệm xˆ ở dạng đặc biệt:
xˆ =

xˆB
xˆN

với xˆN = x¯N + te j = te j ,

trong đó e j là tọa độ phi cơ sở của véctơ đơn vị thứ j trong Rn và t là số dương được
chọn sao cho xˆ là tối ưu.
15


Vì xˆN là dương, theo (1.2.3), xˆ là tối ưu, tức là
xˆB = x¯B − tB−1 Ne j ≥ 0.

Bước 4. Giả sử s là chỉ số mà c¯s > 0. Chọn cột as của ma trận A và tính a¯s = B−1
k as .
Nếu véctơ này là âm, thì dừng lại. Bài toán là có giá trị bằng +∞.
Ngược lại tìm chỉ số l sao cho
xˆs :=

b¯ i
b¯ l
= min
: a¯is > 0 .
a¯ls
a¯is

Bước 5. Lập một cơ sở chấp nhận được mới Bk+1 từ Bk bằng cách gạch đi cột al
và thay vào cột as . Đỉnh tương ứng với xk+1 nhận được từ xk bằng cách đặt biến
xs = xˆs > 0 và biến xl = 0.
Bước 6. Tính ma trận nghịch đảo B−1
k+1 của cơ sở mới Bk+1 và quay về Bước 2.

16


Phần tử a¯ls nhận được ở trên từ ma trận A được gọi là phần tử xoay (pivot),
cột a¯s = (a¯1s , ..., a¯ms )T và hàng a¯l = (a¯l1 , ..., a¯ln ) được gọi là hàng xoay (pivotal
column) và cột xoay (pivotal row) của thuật toán. Do số đỉnh của miền ràng buộc
là hữu hạn, nên nếu bài toán có nghiệm, sau hữu hạn bước ta sẽ tìm được đỉnh tối ưu.
Tìm cơ sở chấp nhận được
Ta xét ràng buộc của bài toán (LP)
Ax = b và x



17


của Bk . Kí hiệu D là m × m-ma trận, gọi là ma trận đổi cơ sở (matrix for change of
basic), là ma trận đơn vị trừ cột thứ l bằng véctơ
−

a¯1s
1
a¯ms
, ...,
, ..., −
a¯ls
a¯ls
a¯ls

T

.

Cụ thể là


1 ... −a¯1s /a¯ls

D =  0 ...
1/a¯ls
0 ... −a¯ms /a¯ls


là cơ sở chấp nhận được. Để rút gọn, véctơ giá c được đặt hàng đầu của bảng.
Bảng đơn hình ban đầu có dạng, kí hiệu T
cT =

cTB

cTN

0

A=

B

N

b

Bằng cách nhân vào bên phải bảng T bởi ma trận mở rộng S
18


1

−cTB B−1

0

B−1


: a¯is > 0
a¯ls
a¯is

sẽ là cơ sở.

Bảng đơn hình T ∗ thu được bằng cách nhân vào bên phải ma trận T với ma trận S
1

0

1

−c¯s /a¯ls

0

0

0
..
.

1
..
.

···

−a¯1s /a¯ls


Sử dụng bảng đơn hình ta có véctơ giá rút gọn c¯1 và c¯2 . Cơ sở tối ưu đối với λ = 1
là B = {3, 4} , nghiệm cơ sở tối ưu chấp nhận được là x = (0, 0, 3, 6) .
Bắt đầu với giai đoạn 3
Lặp 1:
c¯1

−3

−1

0

0

0

c¯2

1

2

0

0

0

x3

Lặp 2:
c¯1

−3

−1

0

0

0

c¯2

1

2

0

0

0

x3

0

1


2

1

12

c¯2

0

0

−7/3

−1/3

−9

x2

0

1

1

0

3