ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN DUY LONG
PHƯƠNG PHÁP GIẢI MỘT LỚP
BÀI TOÁN QUY HOẠCH
NGUYÊN PHI TUYẾN
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN DUY LONG
PHƯƠNG PHÁP GIẢI MỘT LỚP
BÀI TOÁN QUY HOẠCH
NGUYÊN PHI TUYẾN
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TS. TRẦN VŨ THIỆU
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
LỜI NÓI ĐẦU 1
Nội dung 4
1 MỘT SỐ KIẾN THỨC CHUẨN BỊ 4
1.1 Tập lồi, hàm lồi và một số tính chất . . . . . . . . . . . . . 4
1.1.1 Tập hợp lồi. . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 6
trong thực tiễn. Một số mô hình tối ưu tổ hợp thuộc loại các bài toán "dễ
giải" (có thuật toán đa thức để giải), nhưng phần lớn là các bài toán "khó
giải" (chưa có thuật toán đa thức để giải).
Nhiều vấn đề lý thuyết và thực tiễn có thể diễn đạt dưới dạng một bài
toán tối ưu rời rạc. Những bài toán như vậy thường có các cấu trúc riêng
nào đó. Nếu biết khai thác cấu trúc riêng đó thì có thể tìm ra cách giải
hiệu qủa.
Luận văn đề cập tới một lớp bài toán tối ưu rời rạc, cụ thể là bài toán
qui hoạch nguyên phi tuyến (biến số nhận các giá trị nguyên, hàm mục
tiêu phi tuyến), có thể giải được bằng thuật toán đa thức nhờ khai thác
đặc điểm cấu trúc của bài toán. Bài toán được xét trong luận văn có cấu
trúc khá đặc biệt và có nội dung thực tiễn thiết thực. Có thể xem nó như
mô hình toán học cho một số bài toán thường gặp trong thực tế (mô hình
xếp lịch học tập trong các trường học) và hoàn toàn có thể áp dụng được
trong thực tiễn. Việc phân tích lớp bài toán này giúp ích cho việc đi sâu
tìm hiểu sau này về các bài toán tối ưu rời rạc nói chung và những ứng
dụng của chúng nói riêng.
Nội dung luận văn được chia thành ba chương.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
Chương 1 với tiêu đề "Một số kiến thức chuẩn bị" trình bày những
kiến thức cơ bản cần thiết về tập lồi và hàm lồi làm cơ sở lý thuyết cho
việc phân tích cấu trúc và xây dựng các thuật toán ở những chương sau.
Tiếp theo, chương này trình bày vắn tắt khái niệm thuật toán thời gian
đa thức. Cuối chương giới thiệu khái quát mô hình và ý nghĩa thực tế của
lớp bài toán qui hoạch nguyên phi tuyến được xét trong luận văn.
Chương 2 với tiêu đề "Phương pháp trực tiếp giải bài toán (P)" phân
tích cấu trúc đặc biệt và nêu ra những tính chất nghiệm đáng chú ý của
bài toán qui hoạch nguyên phi tuyến xét trong luận văn, các tính chất này
giúp ích cho việc xây dựng thuật toán giải. Mục tiếp theo của chương trình
Nguyễn Duy Long
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Chương 1
MỘT SỐ KIẾN THỨC CHUẨN BỊ
Chương này sẽ trình bày một số khái niệm và kiến thức cơ bản về giải
tích lồi, cần thiết cho việc phân tích lý thuyết và xây dựng thuật toán
trong các chương sau. Tiếp đó trình bày khái niệm thuật toán đa thức và
cuối cùng giới thiệu bài toán qui hoạch nguyên phi tuyến được xét trong
luận văn. Nội dung của chương được tham khảo từ các tài liệu [2], [3] và
[6].
1.1 Tập lồi, hàm lồi và một số tính chất
1.1.1 Tập hợp lồi.
Khái niệm về tập hợp lồi là một khái niệm cơ bản của giải tích lồi và
quy hoạch lồi. Nhiều tính chất quan trọng và thú vị của bài toán quy hoạch
có được trên miền ràng buộc là một tập hợp lồi.
Định nghĩa 1.1. Một tập X trong không gian Euclide R
n
được gọi là
một tập lồi nếu ∀x
1
, x
2
∈ X và ∀λ ∈ [0; 1] ta có λx
1
+ (1 − λ
2
)x ∈ X.
Như vậy nếu X là một tập lồi thì nó chứa trọn đoạn thẳng nối hai điểm
bất kỳ của nó.
a
11
x
1
+ a
12
x
2
+ + a
1n
x
n
b
1
a
21
x
1
+ a
22
x
2
+ + a
2n
x
n
b
2
g
j
, trong đó
i∈I
λ
i
= 1, λ
i
, µ
j
0 với mọi i, j còn
các d
i
với i ∈ I là đỉnh của X, với j ∈ J là phương các cạnh vô hạn của
X.
Chú ý rằng nếu X giới nội thì nó không có các cạnh vô hạn, do đó trong
biểu diễn trên chỉ còn lại tổng thứ nhất. Trong trường hợp này, mọi điểm
của X đều biểu diễn qua tổ hợp lồi của các đỉnh của X.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
1.1.2 Hàm lồi
Định nghĩa 1.2. Hàm số f(x) xác định trên tập lồi X ⊂ R
n
được gọi
là hàm lồi trên X, nếu với mọi x, y ∈ X, 0 λ 1 ta có:
f (λx + (1 − λ)y) λf(x) + (1 − λ)f(y).
Hàm f (x) được gọi là hàm lồi chặt trên X nếu với ∀x
1
, x
(λf) (x) := λf (x) ,
(f + g) (x) := f (x) + g (x) ,
max (f, g) (x) := max (f (x) , g (x)) .
Các hàm lồi là đóng đối với phép tổ hợp tuyến tính không âm và phép
lấy max. Cụ thể ta có định lý như sau:
Định lý 1.3. Cho f là một hàm lồi trên tập lồi X và g là hàm lồi trên
tập lồi Y. Lúc đó các hàm sau là lồi trên X ∩ Y :
1. λf + βg ∀λ, β 0,
2. max (f, g) .
Định nghĩa 1.3. Cho X ⊂ R
n
khác rỗng và hàm f : X → R (không
nhất thiết lồi). Một điểm x
∗
∈ X được gọi là cực tiểu địa phương của f
trên X, nếu tồn tại lân cận mở U của x
∗
sao cho f (x
∗
) f (x) với mọi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
x ∈ X ∩ U. Điểm x
∗
∈ X được gọi là cực tiểu tuyệt đối của f trên X nếu
f (x
∗
) f (x) với ∀x ∈ X.
Dưới đây là một số tính chất cơ bản về cực trị của hàm lồi và hàm lõm.
Định lý 1.4. Bất kỳ cực tiểu địa phương nào của hàm lồi trên tập lồi
k
) với một k nào đó, nghĩa là có một hằng số c và một số tự
nhiên s’ sao cho f
A
(s) cs
k
với mọi s s
.
• Trong lý thuyết độ phức tạp tính toán, lớp các bài toán có thể giải
được trong thời gian đa thức gọi là lớp P, còn NP là lớp các bài toán mà
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
khi cho một lời giải đúng thì có thể kiểm tra xác nhận tính đúng đắn của
lời giải đó trong thời gian đa thức (chú ý đây không nói gì về lời giải sai);
nói cách khác, NP là lớp các bài toán có thể giải được trong thời gian đa
thức bằng một thuật toán "phi tất định" (non-deterministic) (một thuật
toán phi tất định gồm hai giai đoạn: 1) đoán một lời giải tối ưu; 2) kiểm
tra xác nhận đó đúng là lời giải tối ưu).
Đương nhiên P ⊂ NP, nhưng không rõ liệu có P = NP không. Có
nhiều bài toán tối ưu thuộc lớp P (chẳng hạn, bài toán qui hoạch tuyến
tính) nhưng cũng có rất nhiều bài toán mà cho đến nay mặc dù những cố
gắng của nhiều nhà toán học, chưa ai tìm ra được một thuật toán đa thức
để giải nó, mà cũng chưa ai chứng minh được không thể có một thuật toán
đa thức cho bài toán ấy, nghĩa là không ai biết bài toán ấy có thuộc P
không (bài toán người du lịch là một trong số rất nhiều bài toán như thế).
Giả thuyết P = NP cho đến nay vẫn chưa có ai chứng minh hay bác bỏ
được. Đó là một câu hỏi lớn của toán học có lẽ còn tồn tại lâu dài trong
thế kỷ XXI.
• Một bài toán X
j
x
j
= b, x
j
∈ {0, 1}(j = 1, 2, , n)và đạt cực đại của
n
j=1
c
j
x
j
.
Ta nói một bài toán X là NP -khó (NP - hard) nếu mọi bài toán thuộc
NP đều qui dẫn đa thức được về X. Như vậy, mọi bài toán NP - đầy đủ
đều là NP - khó. Vì thế, lớp bài toán NP - khó rộng hơn lớp bài toán
NP - đầy đủ, vì nó bao gồm các bài toán thuộc lớp NP, cũng như các bài
toán không thuộc NP . Bài toán cái túi được xem như "dễ nhất" trong số
các bài toán NP - khó.
Bài toán sau là NP - khó, nhưng không biết có thuộc lớp NP không:
Cho các số tự nhiên c
1
, c
2
, , c
n
, k và L. Có chăng k tập con khác nhau
S
1
a
ij
mxn
với a
ij
∈ {0, 1} và cho trước các số
nguyên dương p
i
(0 < p
i
n) , i = 1, 2, , m. Xét bài toán tối ưu sau đây:
(P ) f (x) = max
1jn
m
i=1
x
ij
→ min, (1.1)
n
j=1
x
ij
= p
i
, i = 1, 2, , m, (1.2)
0 x
i
, i = 1, 2, , m. (1.2’)
Có thể thấy bài toán (P) tương đương với bài toán quy hoạch nguyên
phi tuyến tính sau đây:
(P
) min
t
n
i=1
x
ij
p
i
, ∀i;
m
i=1
x
ij
t, ∀j; 0 x
ij
a
1 nếu sinh viên i tham gia chuyên đề j,
0 nếu ngược lại.
với i = 1, 2, , m; j = 1, 2, , n.
Rõ ràng các x
ij
phải thỏa mãn điều kiện 0 x
ij
a
ij
(mỗi sinh viên chỉ
tham dự những chuyên đề mà họ ưa thích) và x
i1
+ x
i2
+ + x
in
= p
i
(tổng số chuyên đề sinh viên i tham dự vừa đủ yêu cầu). Khi đó, số lượng
sinh viên tham dự nhóm chuyên đề j là x
1j
+ x
2j
+ + x
mj
và dễ thấy mô
hình toán học cho bài toán đặt ra chính là bài toán (P).
Bài toán lập lịch cho hội nghị: Một hội nghị có m tiểu ban, mỗi
tiểu ban cần sinh hoạt trong một ngày tại phòng họp phù hợp với nó. Có
n phòng họp dành cho việc sinh hoạt của các tiểu ban. Cho biết:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
Chương 2
PHƯƠNG PHÁP TRỰC TIẾP
GIẢI BÀI TOÁN (P)
Chương này phân tích cấu trúc của bài toán qui hoạch nguyên phi tuyến
được xét trong luận văn và nêu các tính chất đáng chú ý về nghiệm của bài
toán. Sau đó, trình bày thuật toán đa thức giải bài toán, nhờ sử dụng kỹ
thuật điều chỉnh dần phương án và kỹ thuật đánh số các hàng, cột trong
bài toán. Nội dung của chương được tham khảo từ các tài liệu [1], [4] và
[5].
2.1 Tính chất nghiệm của bài toán(P).
Trong mục này sẽ nêu điều kiện để bài toán (P) có nghiệm và nêu ra
ước lượng khoảng cho giá trị tối ưu (1.1) của bài toán.
Bổ đề 2.1. Bài toán (P) có phương án khi và chỉ khi:
n
j=1
a
ij
p
i
, i = 1, 2, , m (2.1)
Chứng minh. Điều kiện cần của Bổ đề là hiển nhiên, vì từ các điều
kiện (1.2) và (1.3) ta suy ra các bất đẳng thức trong (2.1). Để chứng minh
điều kiện đủ, ta chỉ cần chỉ ra rằng, nếu điều kiện (2.1) được thực hiện
thì bài toán (P) luôn có phương án. Thực vậy, giả sử điều kiện (2.1) được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
thực hiện. Khi đó, nếu đặt:
với các thành phần được xác
định theo công thức
x
∗
ij
= 1, j ∈ I
+
i
, x
∗
ij
= 0, j /∈ I
∗
i
, i = 1, 2, , m,
là phương án của bài toán (P). Bổ đề được chứng minh.
Điều kiện (1.3) cho thấy tập phương án của bài toán (P) là bị chặn, vì
thế (2.1) cũng là điều kiện cần và đủ để bài toán (P) có nghiệm (phương
án tối ưu).
Để tìm khoảng ước lượng cho giá trị tối ưu (1.1) ta đưa vào các ký hiệu:
a
i
=
n
j=1
a
ij
, i = 1, 2, , m,
b
j
m, ∀j.
Ký hiệu k
∗
là trị tối ưu của hàm mục tiêu (1.1). Khi đó, ta có:
Bổ đề 2.2.Ký hiệu k =
p
n
, trong đó ]x[ biểu thị số nguyên nhỏ nhất
lớn hơn hay bằng x và k = max
1jn
b
j
. Khi đó ta có ước lượng sau đây:
k k
∗
k.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Chứng minh. Tổng số chuyên đề mà mọi sinh viên cần tham dự là p,
mà mỗi chuyên đề có tối đa k
∗
sinh viên tham dự nên k
∗
.n p hay k
∗
p
1jn
b
j
= k
và do đó k
∗
k. Bổ đề được chứng minh.
Không giảm tính tổng quát, ta có thể giả thiết
0 < b
1
b
2
b
n
m. (2.2)
Nếu k được xác định như trong bổ đề 2.2 thỏa mãn k > b
1
thì có thể cải
tiến cận dưới của k
∗
như sau:
Bổ đề 2.3.Với các giả thiết đã nêu trên, nếu k > b
1
thì
k
∗
k
k,
trong đó k
.
Vì các chuyên đề j với j t có tối đa b
j
< k
∗
sinh viên tham dự, nên k*
phải thỏa mãn điều kiện
t
j=1
b
j
+ k
∗
(n − t) p. (2.4)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
Vì thế, nếu k
là một cận dưới của k
∗
, nghĩa là k
k
∗
, thì k
cũng phải
thỏa mãn bất đẳng thức có dạng (2.4) với t thay bởi s, trong đó s là chỉ
số thỏa mãn b
i
= 15.
Theo bổ đề 1.2, k =
15
6
= 3, k = 4.
2.2 Cơ sở phương pháp giải
Xét bài toán (P) ở chương 1:
(P ) f (x) = max
1jn
m
i=1
x
ij
→ min, (2.5)
m
i=1
x
ij
= p
i
, i = 1, 2, , m, (2.6)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
0 x
ij
i
> 0
thì trong bổ đề 2.1 đã chứng minh được rằng điều kiện cần và đủ để bài
toán (P) có lời giải là:
a
i
p
i
với ∀i = 1, 2, , m. (2.8)
Ta có giả thiết bài toán (P) thỏa mãn điều kiện (2.8). Giả thiết mọi
b
j
> 0 là tự nhiên vì nếu có b
j
= 0 thì chuyên đề j sẽ bị loại (do không có
sinh viên nào muốn theo học).
Giả sử x = {x
ij
} là một phương án của bài toán (P), nghĩa là x thỏa
mãn (2.6) và (2.7). Để dễ hình dung, ứng với mỗi phương án x, ta kẻ một
bảng gồm m hàng và n cột, mỗi hàng tương ứng với mỗi một sinh viên,
mỗi cột tương ứng với một chuyên đề. Ô nằm ở hàng i cột j được gọi là ô
(i,j). Phương án x = {x
ij
} sẽ tương ứng với một bảng m hàng và n cột các
số 0 và 1.
Ta quy ước gọi ô (i,j) là ô đen nếu a
ij
= 0 (ô đen sẽ bị cấm do sinh
viên i không ưa thích chuyên đề j nên x
t
x
là giá trị hàm mục tiêu (2.5) tương ứng với phương án x).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
Nếu ta xây dựng mạng G = g
k
với khả năng thông qua các cung
đi tới đỉnh đích của mạng đều bằng k = max
1jn
b
j
thì mỗi phương án của
(P) có thể xem như một luồng ξ trên G với ξ (s, u
i
) = p
i
, ξ (u
i
, w
j
) = x
ij
,
ξ (w
j
, t) = t
x
i=1
p
i
= p. (2.10)
Cột j được gọi là cột đầy nếu t
x
j
= t
x
, gọi là cột gần đầy nếu t
x
j
= t
x
− 1
và gọi là cột vơi nếu t
x
j
t
x
− 2. Để ý rằng các khái niệm ô trắng, ô xanh,
cột đầy, gần đầy, cột vơi đều gắn liền với một phương án cụ thể nào đó.
Từ các khái niệm nêu trên, ta có ngay quy tắc đơn giản sau đây cho
phép nhận biết lời giải của bài toán (P).
Mệnh đề 2.2.1. Nếu phương án x không có cột vơi, nghĩa là:
t
x
= t
x
i
n
j=1
t
y
j
n (t
x
− 1) .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Điều này trái với (2.12). Chứng tỏ x là phương án tối ưu và mệnh đề được
chứng minh.
Xét phương án x =
x
ij
của bài toán (P). Giả sử C là một dây chuyền
các ô xanh và trắng (trong phương án x) xen kẽ nhau nối cột j
0
với cột j
k
:
C = {(i
0
, j
0
) , (i
0
= 1, x
i
t
j
t+1
= 0, t = 0, 1, , k − 1, x
ij
= x
ij
, ∀ (i, j) ∈ C.
Bổ đề sau đây cho thấy phép biến đổi trên không làm thay đổi giá trị hàm
mục tiêu (2.5) của phương án x.
Bổ đề 2.4.Giả sử x’ nhận được từ x nhờ thực hiện phép biến đổi A
trên dây chuyền các ô xanh và trắng xen kẽ nhau nối hai cột không đầy.
Khi đó, ta có t
x
= t
x
.
Chứng minh. Giả sử có dây chuyền (2.14) nối 2 cột không đầy j
0
, j
k
t
x
j
t
x
j
= t
x
j
, ∀j = j
0
, j
k
. (2.15)
Mặt khác, do cột j
0
chỉ có một ô thuộc C, đó là ô trắng (i
0
, j
0
) nên:
t
x
j
0
= t
x
j
0
+ 1 (2.16)
và do cột i
Tương tự, giả sử C là một chu trình các ô xanh và trắng xen kẽ nhau:
C = {(i
0
, j
0
) , (i
0
, j
1
) , , (i
k
, j
k
) , (i
k
, j
0
) , (i
0
, j
0
) , (k 1)}
với (i
t
, j
t
) , t = 0, 1, , k là các ô trắng, còn (i
t
, j
t+1
j
0
= 0, x
ij
= x
ij
, ∀ (i, j) /∈ C.
Bổ đề 2.5. Giả sử x’ nhận được từ x nhờ thực hiện phép biến đổi B
trên chu trình các ô xanh và trắng xen kẽ nhau. Khi đó, ta có t
x
= t
x
.
Mệnh đề 2.2.2. Nếu tồn tại dây chuyền các ô xanh và trắng xen kẽ
nhau nối một cột đầy với một cột vơi thì ta có thể điều chỉnh phương án
hiện có thành phương án mới tốt hơn hoặc có số cột đầy ít hơn.
Chứng minh. Giả sử tìm được dây chuyền C nối cột đầy nối với cột
vơi j
0
. Khi đó, ta thực hiện phép biến đổi A trên C. Lập luận tương tự như
trong chứng minh Bổ đề 2.4 ta nhận được các hệ thức (2.15) và (2.17).
Do cột j
0
vơi nên từ (2.15) và (2.17) suy ra rằng nếu j
k
là cột đầy duy
nhất trong phương án x thì t
x
là ô trắng.
Bước 1: Xây dựng phương án ban đầu.
Với mỗi hàng i, từ hàng 1 tới hàng m, ta lần lượt ghi số 1 vào các ô
trắng, từ trái qua phải cho đến khi đủ p
i
số (các ô còn lại của hàng xem như
được ghi số 0), rồi chuyển sang hàng tiếp theo. Kết quả là ta nhận được
phương án ban đầu x
1
=
x
1
ij
. Cũng có thể xuất phát từ một phương án
đã biết bất kỳ của (P). Đặt k = 1. Chuyển sang bước 2.
Bước 2: Kiểm tra tối ưu.
Với phương án x
k
nhận được, ta quy ước gọi các ô được ghi số 1 là
xanh, các ô (khác ô đen) được ghi số 0 là trắng. Tính các số:
t
k
j
≡ t
x
k
j
=
k
, gọi là
cột gần đầy nếu t
k
x
= t
k
− 1 và là cột vơi nếu t
k
j
t
k
− 2. Nếu không có
cột vơi thì theo Mệnh đề 2.2.1, x
k
là phương án tối ưu. Nếu trái lại, ta
thực hiện gán số cho các hàng và các cột của bảng. Sau khi gán số, nếu
không có cột vơi nào được gán số thì x
k
là phương án tối ưu (Mệnh đề
2.2.3). Trái lại, ta tìm được một dây chuyền C có dạng (2.14), gồm các ô
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©