..
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
NGUYỄN THU HẰNG
THUẬT TOÁN GIẢI BÀI TOÁN
PHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ
KHOẢNG Ở HÀM MỤC TIÊU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
NGUYỄN THU HẰNG
THUẬT TOÁN GIẢI BÀI TOÁN
PHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ
KHOẢNG Ở HÀM MỤC TIÊU
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng
Mã số
: 60 46 01 12
NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS.TS. Trần Vũ Thiệu
THÁI NGUYÊN - 2016
i
Mục lục
Danh mục các hình vẽ
ii
Mở đầu
1
1 Một số kiến thức chuẩn bị
4
1.1. Bài toán qui hoạch phân tuyến tính . . . . . . . . . . . . . . . .
1.2. Tính chất nghiệm của bài toán . . . . . . . . . . . . . . . . . .
1.3. Minh họa hình học . . . . . . . . . . . . . . . . . . . . . . . .
4
8
9
1.3.1. Nghiệm tối ưu duy nhất . . . . . . . . . . . . . . . . . 10
1.3.2. Nhiều nghiệm tối ưu . . . . . . . . . . . . . . . . . . . 11
1.3.3. Nghiệm tối ưu hữu hạn và vô cực . . . . . . . . . . . . 12
1.3.4. Nghiệm tối ưu tiệm cận . . . . . . . . . . . . . . . . . . 13
1.3.5. Bài toán vô nghiệm . . . . . . . . . . . . . . . . . . . . 13
1.4. Biến đổi về bài toán tuyến tính tương đương . . . . . . . . . . . 14
2 Qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu
18
2.1. Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2. Thuật toán đưa về qui hoạch tuyến tính . . . . . . . . . . . . . . 21
2.3. Thuật toán dùng phép tính khoảng . . . . . . . . . . . . . . . . 25
2.3.1. Phép tính khoảng . . . . . . . . . . . . . . . . . . . . . 25
2.3.2. Qui hoạch phân tuyến tính khoảng . . . . . . . . . . . . 28
2.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Kết luận
38
i
Tài liệu tham khảo
39
ii
Danh mục các hình vẽ
Hình 1.1. Phân bổ công suất phát sóng tối ưu
Hình 1.2. Năm tập mức trong R2 với γ1 > 0 > γ2 > γ3 > γ4 .
Hình 1.3. Nghiệm tối ưu duy nhất đạt tại x∗
Hình 1.4. Nhiều nghiệm tối ưu: xopt ∈ [x∗ , x∗∗ ]
Hình 1.5. Nghiệm tối ưu hữu hạn và vô cực
Hình 1.6. Nghiệm tối ưu tiệm cận ( f ∗ hữu hạn, không đạt được)
Hình 1.7. Bài toán vô nghiệm ( f (x) ց −∞)
Hình 1.8. Tập ràng buộc của bài toán ở Ví dụ 1.1
Hình 2.1. Tập ràng buộc X của bài toán ở Ví dụ 2.1
Hình 2.2. Tập ràng buộc X của bài toán ở Ví dụ 2.2
Hình 2.3. Tập ràng buộc X của bài toán ở Ví dụ 2.4
1
Lời mở đầu
Qui hoạch phân tuyến tính (LFP) là bài toán tìm cực tiểu (hay cực đại) của một
hàm phân thức afin (tỉ số hai hàm tuyến tính afin) với các ràng buộc đẳng thức
hay bất đẳng thức tuyến tính.
Qui hoạch phân tuyến tính là một trường hợp riêng của qui hoạch phân thức
phi tuyến, thường dùng để mô hình hóa các bài toán thực tế với một hay nhiều
mục tiêu (chẳng hạn lợi nhuận / chi phí, sản phẩm / số lao động, ...) và được ứng
dụng rộng rãi trong nhiều ngành khác nhau của kỹ thuật, kinh tế, tài chính, ...
Một trong những bài toán qui hoạch phân thức tuyến tính đang được nhiều
người quan tâm nghiên cứu là bài toán phân thức tuyến tính với hệ số khoảng ở
hàm mục tiêu (không cố định như trước). Bài toán này có dạng:
f (x) =
p(x) [a1 , b1 ] x1 + . . . + [an , bn ] xn + [a0 , b0 ]
=
→ min
q(x)
[c1 , d1 ] x1 + . . . + [cn , dn ] xn + [c0 , d0 ]
với điều kiện Ax < b, x ≥ 0, (A ∈ Rm×n , b ∈ Rm ).
Mô hình bài toán này linh hoạt và dễ áp dụng hơn. Có một số tài liệu mới
([4], [5] và [6] năm 2012, 2013) đề cập tới các phương pháp giải bài toán này.
Đáng chú ý là hai phương pháp nêu ở [4] và [6].
Vì thế chúng tôi chọn đề tài luận văn:
"Thuật toán giải bài toán phân thức
tuyến tính với hệ số khoảng ở hàm mục tiêu"
nhằm mục đích tìm hiểu và trình bày các ý tưởng, phương pháp và thuật toán
giải mô hình bài toán nêu trong hai tài liệu tham khảo gần đây [4, 6]. Cả hai
phương pháp tuy khác nhau, nhưng đều mở rộng và phát triển thuật toán giải
qui hoạch phân tuyến tính đã có. Vì thế trước hết cần tìm hiểu qua về bài toán
2
qui hoạch phân tuyến tính và một số tính chất nghiệm tối ưu của bài toán phân
tuyến tính. Sau đó sẽ tìm hiểu và trình bày từng cách tiếp cận riêng ở [4] và [6].
Về đại thể phương pháp [4] nêu cách đưa bài toán ban đầu về một qui hoạch
tuyến tính, phương pháp [6] dựa trên phép tính khoảng tìm cách đưa bài toán
được xét về bài toán với hàm mục tiêu khoảng. Đây là đề tài mới về qui hoạch
phân tuyến tính, đang được nhiều người quan tâm tìm hiểu, nghiên cứu.
Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [6].
Kết quả cần đạt được: hiểu và trình bày về bài toán qui hoạch phân tuyến
tính, tính chất nghiệm tối ưu của bài toán, mô hình bài toán qui hoạch phân
tuyến tính với hệ số khoảng ở hàm mục tiêu và một số thuật toán xử lý mô hình.
Đóng góp chính của luận văn là tổng hợp và giới thiệu có chọn lọc hai thuật
toán giải bài toán qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu.
Luận văn được viết trong hai chương.
Chương 1 "Kiến thức chuẩn bị" đề cập tới bài toán tối ưu với hàm mục
tiêu phân tuyến tính và với các ràng buộc tuyến tính. Nêu một số ví dụ thực tế
có mô hình toán học là qui hoạch phân tuyến tính (bài toán sản xuất) và qui
hoạch phân tuyến tính suy rộng (bài toán tăng trưởng kinh tế Von Neumann và
bài toán phân bổ tối ưu công suất phát sóng). Tiếp đó nêu các tính chất nghiệm
của bài toán thông qua các minh họa hình học nghiệm tối ưu của bài toán qui
hoạch phân tuyến tính. Cuối chương trình bày phép biến đối Charnes - Cooper
đưa bài toán qui hoạch phân tuyến tính về bài toán qui hoạch tuyến tính tương
đương, mà không cần giả thiết tập ràng buộc của bài toán phân tuyến tính bị
chặn.
Chương 2 "Qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu"
giới thiệu cách tiếp cận đưa ra trong [4, 6] tìm nghiệm tối ưu cho bài toán qui
hoạch phân tuyến tính với các hệ số mục tiêu thay đổi trong một khoảng. Thuật
toán giải [4] dùng phép biến đổi Charnes - Cooper và thuật toán giải [6] dựa
trên phép tính khoảng. Cuối chương nêu một số ví dụ minh hoạ cho các thuật
toán giải đã trình bày.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn
GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn.
3
Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán-Tin,
Trường Đại học Khoa học Thái Nguyên và của Viện Toán học, Viện Công nghệ
thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy
và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
Thái Nguyên, tháng 5 năm 2016
Học viên
Nguyễn Thu Hằng
4
Chương 1
Một số kiến thức chuẩn bị
Chương này đề cập tới bài toán tối ưu với hàm mục tiêu phân tuyến tính (tỉ số
của hai hàm tuyến tính afin) và với các ràng buộc tuyến tính. Các bài toán như
thế gọi là qui hoạch phân tuyến tính. Phần đầu trình bày nội dung và ý nghĩa
bài toán, tiếp đó nêu tính chất và minh họa hình học nghiệm tối ưu của bài toán.
Cuối chương giới thiệu cách đưa bài toán về qui hoạch tuyến tính tương đương.
Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [3].
1.1.
Bài toán qui hoạch phân tuyến tính
Một cách tổng quát có thể phát biểu bài toán như sau. Cho tập lồi C ⊆ Rn và
các hàm f , g, hi : Rn → R(i = 1, . . . , m). Xét bài toán tối ưu với hàm mục tiêu
phân thức (tỉ số của hai hàm số), ký hiệu bài toán (FP):
(FP)
inf
x∈X
f (x)
,
g(x)
trong đó X = x ∈ C : hi (x) ≤ 0, i = 1, . . . , m. Ta phân biệt các loại bài toán sau:
• Khi f , g và hi là các hàm afin thì (FP) gọi là bài toán qui hoạch phân
tuyến tính (Linear Fractional Program).
• Khi f và g là các hàm toàn phương và hi là các hàm afin thì (FP) gọi là bài
toán qui hoạch phân thức toàn phương (Quadratic Fractional Program).
5
• Khi f ≥ 0 là hàm lồi, g > 0 là hàm lõm và hi là các hàm lồi thì (FP) gọi
là bài toán qui hoạch phân thức lồi (Convex Fractional Program).
Trong bài toán (FP) chỉ xét một hàm phân thức. Tuy nhiên, trong nhiều ứng
dụng ta còn có thể xét nhiều hàm phân thức. Chẳng hạn,
• Qui hoạch phân thức suy rộng (Generalized Fractional Program):
n f (x) o
i
(gi > 0 ∀i).
λ = min max
x∈X 1≤i≤k gi (x)
∗
• Qui hoạch tổng các hàm phân thức (Sum-of-ratios Program):
k
∗
λ = min ∑
x∈X
i=1
n f (x) o
i
gi (x)
(gi > 0 ∀i).
• Qui hoạch phân thức đa mục tiêu (Multi-Objective Fractional Program):
n f (x)
fk (x) o
1
,...,
(gi > 0 ∀i).
λ = min
x∈X g1 (x)
gk (x)
∗
Luận văn này chủ yếu tập trung xét bài toán qui hoạch phân tuyến tính:
(LFP)
p(x) pT x + α
: Ax ≤ b, x ≥ 0,
min f (x) =
=
q(x) qT x + β
(1.1)
trong đó p, q ∈ Rn , α , β ∈ R, A ∈ Rm×n , b ∈ Rm . Ký hiệu
X = {x ∈ Rn : Ax ≤ 0, x ≥ 0}.
Tương tự, có thể xét bài toán tìm cực đại: max{ f (x) : x ∈ X}.
Khi cần ta có thể dùng qui ước a/0 = +∞ nếu a > 0 và a/0 = −∞ nếu a ≤ 0.
Qui hoạch tuyến tính là một trường hợp riêng của qui hoạch phân tuyến tính
khi q = 0 và β = 1. Trong [2] phân tích một số trường hợp riêng khác cho phép
đưa bài toán qui hoạch phân tuyến tính về bài toán tuyến tính thích hợp.
6
• Để tiện giải thích ý nghĩa thực tiễn của mô hình qui hoạch phân tuyến tính
và qui hoạch phân tuyến tính suy rộng ta xét bài toán tìm cực đại.
a) Bài toán sản xuất. Giả sử một xí nghiệp có thể dùng m loại vật tư hiện có
để sản xuất ra n loại sản phẩm. Gọi bi là lượng vật tư i (i = 1, . . . , m) mà xí
nghiệp có và ai j là định mức tiêu hao vật tư i để sản xuất một đơn vị sản
phẩm j ( j = 1, . . . , n). Mỗi đơn vị sản phẩm j sản xuất ra sẽ cho lợi nhuận
là p j và tốn chi phí sản xuất là q j , α là lợi nhuận cố định thu được và β là
chi phí cố định cần bỏ ra (α , β không phụ thuộc số lượng sản phẩm sản
xuất). Hỏi với số vật tư đã có xí nghiệp nên sản xuất bao nhiêu đơn vị sản
phẩm mỗi loại sao cho hiệu quả sản xuất của xí nghiệp (đo bằng tỉ số giữa
tổng lợi nhuận thu được trên tổng chi phi sản xuất) là lớn nhất? Bài toán
này dẫn đến mô hình qui hoạch phân tuyến tính.
b) Bài toán tăng trưởng kinh tế Von Neumann. Xét mô hình tăng trưởng
kinh tế đơn giản với n ngành, sản xuất và tiêu dùng m loại hàng. Ký hiệu:
• xi(t) là cường độ hoạt động của ngành i ở năm t (biến cần tìm);
• a x(t) là lượng hàng i tiêu dùng ở năm t cho mọi ngành;
• b x(t) là lượng hàng i do mọi ngành sản xuất ra ở năm t.
Tốc độ tăng trưởng của ngành i đo bằng tỉ số xi (t)/xi (t − 1), i = 1, . . . , n.
Tỉ số thấp nhất được dùng làm thước đo tốc độ tăng trưởng năm t của nền
kinh tế. Bài toán đặt ra là các ngành hoạt động sao cho cả nền kinh tế đạt
tốc độ tăng trưởng lớn nhất? Bài toán này dẫn đến mô hình qui hoạch phân
tuyến tính suy rộng:
xi(t)
: Ãx(t) ≤ Bx(t − 1), x(t) ≥ 1},
1≤i≤n t − 1
max{ f (x) = min
trong đó x(t) = (x1 (t), . . . , xn (t))T .
c) Phân bổ tối ưu công suất phát sóng.
b
7
b
b
trạm phát k
b
máy thu (i,j)
b
trạm phát i
b
b
b
Hình 1.1. Phân bổ công suất phát sóng tối ưu
b
b
Giả sử
• có m trạm phát âm (k = 1, . . . , m) và m × n máy thu, tất cả cùng một
tần số.
• trạm phát i muốn truyền tín hiệu tới n máy thu, đánh số (i, j), j =
1, . . . , n.
• ai jk là lợi thế về đường đi từ trạm phát k tới máy thu (i, j).
• ni j là mức độ ồn nội tại (tạp âm) của máy thu (i, j).
• các biến số: công suất phát sóng pk , k = 1, . . . , m.
Ở máy thu (i, j) có các thông số:
• cường độ tín hiệu thu: si j = ai ji pi .
• cường độ nhiễu và ồn: fi j = ∑k6=i ai jk pk + ni j .
• tỉ số cường độ tín hiệu thu trên cường độ nhiễu và ồn: si j / fi j .
Các trạm phát k 6= i gây nhiễu đối với các máy thu (i, j). Cần xác định các
công suất phát sóng pi (i = 1, . . . , m) sao cho làm cực đại tỉ số si j / fi j nhỏ
nhất đối với mọi máy thu (i, j)? Mô hình toán học cho bài toán này như
sau.
max{min
i, j
ai ji pi
: 0 ≤ pi ≤ pmax , i = 1, . . . , n}.
∑k6=1 ai jk pk + ni j
Đây là một bài toán qui hoạch phân tuyến tính suy rộng.
8
1.2.
Tính chất nghiệm của bài toán
Bây giờ ta trở lại xét bài toán qui hoạch phân tuyến tính (1.1). Để bài toán có
nghĩa ta giả thiết mẫu số q(x) ≡ qT x + b 6= 0 ∀x ∈ X = {x : Ax ≤ b, x ≤ 0}.
Nếu q(x) có dấu khác nhau trên X, tức là có x1 , x2 ∈ X sao cho qT x1 + β > 0
và qT x2 + β < 0 thì do q(x) liên tục nên tồn tại x ∈ x1 , x2 , tức x ∈ X, sao
cho q(x) = 0, trái với giả thiết. Vì thế, không mất tổng quát, ta có thể giả thiết
q(x) > 0 với mọi x ∈ X. (Nếu có q(x) < 0 thì nhân cả tử số p(x) và mẫu số q(x)
của hàm mục tiêu f (x) với (−1), ta sẽ có q(x) > 0). Hơn nữa, ta giả thiết m ≤ n
và rankA = m.
Sau đây là một số khái niệm và định nghĩa cần thiết đối với bài toán (LFP),
tương tự như trong lý thuyết qui hoạch tuyến tính.
Trong bài toán (LFP), f (x) gọi là hàm mục tiêu (objective function). Tập X
gọi là tập ràng buộc hay miền chấp nhận được (feasible set). Véctơ x ∈ X gọi là
một phương án hay nghiệm chấp nhận được (feasible solution), một phương án
mà đồng thời là đỉnh của tập ràng buộc X gọi là một phương án cực biên hay
nghiệm cơ sở (basic feasible solution). Phương án đạt giá trị nhỏ nhất của hàm
mục tiêu f (x) gọi là một phương án tối ưu hay nghiệm tối ưu (optimal solution).
Ta nói bài toán (1.1) là bất khả thi hay không chấp nhận được (infeasible)
nếu tập X = ∅, bài toán gọi là giải được (solvable) nếu tập X 6= ∅ và hàm f (x)
có cận dưới (đối với bài toán min) hữu hạn trên X. Nếu hàm mục tiêu f (x)
không bị chặn dưới trên X thì bài toán được gọi là không bị chặn (unbounded):
inf f (x) = −∞.
x∈X
Ta biết rằng hàm phân tuyến tính f (x) = p(x)/q(x) có tính chất đáng chú ý
là f (x) đơn điệu trên mỗi đoạn thẳng nằm trong tập {x : q(x) > 0}, do đó cực
tiểu (hay cực đại) của f (x) trên mỗi đoạn thẳng sẽ đạt tại một đầu mút của đoạn
thẳng đó. Từ đó, nếu hàm f (x) có cực tiểu (hay cực đại) trên một tập lồi đa diện
có đỉnh thì cực tiểu (hay cực đại) đó sẽ đạt được tại một đỉnh của tập đa diện đó.
Với bài toán qui hoạch phân tuyến tính, có thể xảy ra các trường hợp sau:
9
a. Tập ràng buộc X = ∅ (bài toán bất khả thi).
b. Nghiệm tối ưu duy nhất (đạt tại một đỉnh của X).
c. Vô số nghiệm tối ưu hữu hạn (đạt tại một diện bị chặn của X).
d. Có nghiệm tối ưu hữu hạn và vô cực (đạt tại một diện vô hạn của X).
e. Nghiệm tối ưu tiệm cận ( f ∗ = infx∈X f (x) > −∞ và ∄x∗ ∈ X : f (x∗ ) = f ∗ ).
f. Không có nghiệm tối ưu (infx∈X f (x) = −∞ - bài toán không bị chặn).
1.3.
Minh họa hình học
Ta nhắc lại bài toán (LFP): Tìm x ∈ Rn , f ∗ ∈ R sao cho
p(x) pT x + α
f = min{ f (x) =
=
: Ax ≤ b, x ≥ 0}.
q(x) qT x + β
∗
Ký hiệu X = {x ∈ Rn : Ax ≤ b, x ≥ 0}. Giả thiết ∅ 6= X ⊆ {x : qT x + β > 0}.
Như đã nhận xét: cực tiểu (nếu có) của hàm phân tuyến tính f (x) = p(x)/q(x)
trên tập lồi đa diện X đạt được tại một trong các đỉnh của X.
Để tiện cho việc giải thích các nghiệm tối ưu của bài toán, ta thêm biến mới
γ ∈ R và viết lại (LFP) dưới dạng tương đương sau (các biến γ ∈ R, x ∈ Rn ):
min{γ : pT x + β ≤ γ (qT x + β ), Ax ≤ b, x ≥ 0}.
Trong bài toán này, hàm mục tiêu là tuyến tính, nhưng các ràng buộc không
còn là tuyến tính nữa. Tuy nhiên, dạng bài toán này tiện cho việc minh họa.
Các tập mức của hàm mục tiêu của bài toán (LFP) có dạng:
Cγ = {x ∈ Rn : qT x + β > 0, (pT x + α )/(qT x + β ) = γ }
= {x ∈ Rn : (p − γ q)T x = (γβ − α )}, mức γ ∈ R.
Trong R2 , mỗi tập mức Cγ là một đường thẳng đi qua giao điểm F của hai
đường thẳng p(x) = 0 và q(x) = 0 (⇒ p(x) − γ q(x) = 0, tức là x ∈ Cγ , ∀γ ∈ R).
10
qT x + β
qT x + β > 0
<0
q
Cγ1
p
F
b
pT x + α > 0 C0
pT x + α < 0
Cγ2
Cγ4
Cγ3
Hình 1.2. Năm tập mức trong R2 với γ1 > 0 > γ2 > γ3 > γ4 .
Bài toán qui hoạch phân tuyến tính với X 6= ∅ có thể có các tình huống sau.
1.3.1.
Nghiệm tối ưu duy nhất
Nghiệm tối ưu duy nhất, đạt tại đỉnh x∗ ∈ X (Hình 1.3 a) và b)).
11
qT x + β = 0
F
X
b
Cf ∗
p
x∗
pT x + α = 0
q
a) Miền ràng buộc X bị chặn
qT x + β = 0
b
F
X
b
p
b
x∗
q
b
pT x + α = 0
Cf ∗
b) Miền ràng buộc X không bị chặn
Hình 1.3. Nghiệm tối ưu duy nhất đạt tại x∗
1.3.2.
Nhiều nghiệm tối ưu
Vô số nghiệm tối ưu hữu hạn (đạt được trên một diện bị chặn của X).
b
b
12
b
qT x + β = 0
X
F
p
pT x + α = 0
b
x∗
x∗∗ C f ∗
q
Hình 1.4. Nhiều nghiệm tối ưu: xopt ∈ [x∗ , x∗∗ ]
1.3.3.
Nghiệm tối ưu hữu hạn và vô cực
Nếu tập ràng buộc X không bị chặn và một cạnh vô hạn của X nằm trên đường
mức mục tiêu (Hình 1.5) thì bài toán có vô số nghiệm tối ưu, một trong số đó
là đỉnh x∗ và các nghiệm tối ưu khác là các điểm còn lại trên cạnh vô hạn đi từ
x∗ . Điều đáng chú ý ở đây là trong các nghiệm tối ưu khác x∗ , có một nghiệm
ở vô cực. Vì thế, trong trường hợp này ta nói bài toán có "nghiệm tối ưu hỗn
hợp" (mixed solutions): nghiệm tối ưu hữu hạn và nghiệm tối ưu vô cực. Trong
b
b
b
b
b
trường hợp này các nghiệm tối ưu đạt được tại một diện vô hạn của X.
b
qT x + β = 0
b
X
b
F
p
pT x + α = 0
b
b
x∗
q
Cf ∗
Hình 1.5. Nghiệm tối ưu hữu hạn và vô cực
13
b
b
b
1.3.4.
Nghiệm tối ưu tiệm cận
b
b
b
Trường hợp này xảy ra khi
f∗
= infx∈X f (x) > −∞ và ∄x∗ ∈ X : f (x∗ ) = f ∗ .
qT x + β = 0
b
X
b
F
p
b
b
b
b
q
pT x + α = 0
b
b
Cf ∗
Hình 1.6. Nghiệm tối ưu tiệm cận ( f ∗ hữu hạn, không đạt được)
1.3.5.
Bài toán vô nghiệm
Xảy ra khi f ∗ = infx∈X f (x) = −∞ (hàm mục tiêu không bị chặn dưới).
qT x + β = 0
b
b
b
p
F
X
b
q
pT x + α = 0
Cγ
Hình 1.7. Bài toán vô nghiệm ( f (x) ց −∞)
14
1.4.
Biến đổi về bài toán tuyến tính tương đương
• Xét bài toán qui hoạch phân tuyến tính (LFP):
pT x + α
min{ f (x) = T
: Ax ≤ b, x ≥ 0}.
q x+β
Giả thiết tập X = {x : Ax ≤ b, x ≥ 0} 6= ∅ và qT x + β > 0 với mọi x ∈ X.
Bài toán qui hoạch phân tuyến tính (LFP) có thể đưa được về bài toán qui
hoạch tuyến tính, nhờ dùng phép đổi biến số Charnes - Cooper:
t=
1
> 0, y = t.x ∈ Rn , x ∈ X.
T
q x+β
Nhân ràng buộc Ax ≤ b với t > 0, ta đưa (LFP) về bài toán tuyến tính:
(LP)
min{g(y,t) ≡ pT y + α .t : Ay − bt ≤ 0, qT y + β .t = 1, y ≥ 0, t ≥ 0}.
So với (LFP), bài toán (LP) có thêm một biến và một ràng buộc mới. Các
nghiệm (tối ưu) của hai bài toán (LP) và (LFP) có những mối liên hệ như sau.
Định lý 1.1. Với các ký hiệu trên, ta có các kết luận sau đây:
a) Nếu (y0 ,t 0 ) là nghiệm chấp nhận được của (LP) và t 0 > 0 thì x0 = y0 /t 0
là nghiệm chấp nhận được của (LFP) và
f (x0 ) = t 0 (pT x0 + α ) = pT y0 + α t 0 = g(y0 ,t 0 ).
b) Nếu x0 là một nghiệm chấp nhận được của (LFP) thì (y0 ,t 0 ) là một nghiệm
chấp nhận được của (LP) với
t0 =
1
, y0 = x0 .t 0
T
0
q x +β
và g(y0 ,t 0 ) = pT y0 + α t 0 = t 0 (pT x0 + α ) = f (x0 ).
Định lý 1.2.
15
a) Nếu (y∗ ,t ∗ ) là nghiệm tối ưu của (LP) và t ∗ > 0 thì x∗ = y∗ /t ∗ là nghiệm
tối ưu của (LFP).
b) Giả sử (LFP) chấp nhận được. Khi đó, (LP) không bị chặn dưới khi và chỉ
khi (LFP) không bị chặn dưới.
Định lý 1.3. Giả sử (LFP) có nghiệm chấp nhận được. Khi đó, (LP) có nghiệm
tối ưu và mọi nghiệm tối ưu đều có t = 0 thì giá trị mục tiêu của (LFP) có cận
dưới đúng hữu hạn, nhưng cận dưới đó không đạt tới được. Đó là trường hợp
(LFP) có nghiệm tối ưu tiệm cận.
Trong trường hợp này, có thể tạo ra các nghiệm ε - tối ưu với bất kỳ ε > 0,
nghĩa là trong X tồn tại một cạnh vô hạn mà dọc theo cạnh đó giá trị mục tiêu
của (LFP) tiến dần về cận dưới đúng nói trên.
Định lý 1.4. Nếu X 6= ∅ và qT x + β = 0 với mọi x ∈ X thì (LP) không có nghiệm
chấp nhận được (bài toán (LP) là bất khả thi).
Các định lý trên cũng áp dụng được vào cặp ràng buộc {x : Ax = b, x ≥ 0}
và {(y,t) : Ay − bt = 0, y ≥ 0,t ≥ 0}.
• Dựa vào phép biến đổi Charnes - Cooper, ta có thể giải bài toán qui hoạch
phân tuyến tính (LFP) bằng cách lập và giải bài toán qui hoạch tuyến tính (LP)
tương ứng. Kết quả giải (LP) cho ra một trong các khả năng sau:
a) (LP) bất khả thi ⇒ X = ∅ hoặc (LFP) không xác định (Định lý 1.1 và
1.4).
b) (LP) có nghiệm tối ưu (y∗ ,t ∗ ) với t ∗ > 0 ⇒ (LFP) có nghiệm tối ưu x∗ =
y∗ /t ∗ (Phần a) Định lý 1.2).
c) Mọi nghiệm tối ưu (y∗ ,t ∗ ) của (LP) đều có t ∗ = 0 ⇒ (LFP) có nghiệm tối
ưu tiệm cận (Định lý 1.3).
d) (LP) không bị chặn dưới ⇒ (LFP) không bị chặn dưới hoặc X = ∅ (Phần
b) Định lý 1.2).
• Để minh họa thuật toán giải (LFP) dựa trên phép biến đổi Charnes Cooper ta xét ví dụ sau.
- Xem thêm -