Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC


NGUYỄN VĂN HÙNG

BÀI TOÁN QUI HOẠCH PHÂN TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2013
Mục lục
Mở đầu 3
1 Kiến thức chuẩn bị 5
1.1 Tập lồi và tập lồi đa diện . . . . . . . . . . . . . . . . . . . . 5
1.2 Hàm lồi, hàm lõm và mở rộng . . . . . . . . . . . . . . . . . 8
1.3 Cực tiểu địa phương và tồn cục . . . . . . . . . . . . . . . . 11
2 Bài tốn qui hoạch phân tuyến tính 15
2.1 Bài tốn và tính chất . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Dạng chính tắc và dạng tổng qt . . . . . . . . . . . . . . . 18
2.3 Liên hệ với quy hoạch tuyến tính . . . . . . . . . . . . . . . . 20
2.4 Bài tốn hai biến số . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.1 Lời giải tối ưu duy nhất . . . . . . . . . . . . . . . . . 21
2.4.2 Nhiều lời giải tối ưu . . . . . . . . . . . . . . . . . . . 23
2.4.3 Lời giải tối ưu hữu hạn và vơ cực . . . . . . . . . . . . 23
2.4.4 Lời giải tối ưu tiệm cận . . . . . . . . . . . . . . . . . 24
3 Phương pháp giải qui hoạch phân tuyến tính 27
3.1 Biến đổi Charnes và Cooper . . . . . . . . . . . . . . . . . . 27
3.2 Thuật tốn Gilmore và Gomory . . . . . . . . . . . . . . . . 31
3.3 Thuật tốn Dinkelbach . . . . . . . . . . . . . . . . . . . . . 34
3.4 Thuật tốn Béla Martos . . . . . . . . . . . . . . . . . . . . 38
3.4.1 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . 38
3.4.2 Các bước thuật tốn . . . . . . . . . . . . . . . . . . . 39
Kết luận 44
Tài liệu tham khảo 45
1

có hiệu quả để giải bài tốn qui hoạch tuyến tính và các bài tốn được đưa
về qui hoạch tuyến tính.
Mơ hình tốn học của bài tốn qui hoạch tuyến tính (chính tắc) có dạng
như sau:
Tìm các biến số x
j
(j = 1, 2, . . . , n) sao cho
c
1
x
1
+ c
2
x
2
+ . . . + c
n
x
n
→ min,
với điền kiện
a
i1
x
1
+ a
i2
x
2
+ . . . + a

ngun thiên nhiên có hạn nên việc sử dụng một tiêu chuẩn cụ thể nào đó
ngày càng trở nên phổ biến. Vì thể ứng dụng qui hoạch phân tuyến tính giải
các bài tốn thực tế về tối ưu hóa hiệu quả hoạt động cũng hữu ích như qui
hoạch tuyến tính.
Luận văn này nhằm mục đích tìm hiểu và trình bày các kết quả đã có về
3
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
bài tốn qui hoạch phân tuyến tính, một mở rộng trực tiếp của bài tốn qui
hoạch tuyến tính. Đặc biệt là các tính chất đặc thù rất đáng chú ý và các
phương pháp quen thuộc giải bài tốn qui hoạch phân tuyến tính. Luận văn
gồm lời nói đầu, ba chương, kết luận và danh mục các tài liệu tham khảo.
Chương 1 với tiêu đề "Kiến thức chuẩn bị" trình bày một số kiến thức về
tập lồi (tập lồi da diện), hàm lồi (hàm lõm), các hàm lồi mở rộng và tính chất
cực trị của các hàm này. Các kiến thức này sẽ được dùng đến khi xét bài tốn
tối ưu với hàm mục tiêu phân tuyến tính, với các ràng buộc tuyến tính.
Chương 2 với tiêu đề "Bài tốn qui hoạch phân tuyến tính" đề cập tới bài
tốn qui hoạch phân tuyến tính, đó là bài tốn tìm cực đại (hay cực tiểu) của
một hàm phân thức tuyến tính (tỉ số của hai hàm tuyến tính) với các ràng
buộc (đẳng thức hay bất đẳng thức) tuyến tính. Hàm phân thức có tính chất
đơn điệu (tăng hoặc giảm) theo từng phương và cực trị địa phương ln là
cực trị tồn cục. Từ đó cực trị của hàm phân thức trên một đa diện lồi ln
đạt tại một đỉnh của nó. Phần đầu nêu nội dung và ý nghĩa thực tiến của
bài tốn, các dạng hay gặp của bài tốn và nêu mối liên hệ giữa bài tốn qui
hoạch phân tuyến tính và bài tốn qui hoạch tuyến tính. Cuối chương, xét
tính chất nghiệm của bài tốn hai biến số.
Chương 3 với tiêu đề "Phương pháp giải qui hoạch phân tuyến tính" đề
cập tới các phương pháp tiêu biểu giải bài tốn qui hoạch phân tuyến tính.
Khi tập ràng buộc của bài tốn là tập đa diện lồi (tập lồi đa diện bị chặn),
thuật tốn Charnes và Cooper (1962) đưa về giải bài tốn quy hoạch tuyến
tính tương đương. Tiếp đó là thuật tốn Gilmore và Gomory (1960), chuyển

n
: a
T
x = α, a ∈ R
n
\{0}, với
α ∈ R}
c) Các nửa khơng gian đóng H
1
= {x ∈ R
n
: a
T
x ≤ α}, H
2
= {x ∈ R
n
:
a
T
x ≥ α}
d) Các nửa khơng gian mở K
1
= {x ∈ R
n
: a
T
x < α}, K
2
= {x ∈ R

m×n
, b ∈ R
m
}.
Giao của bất kỳ các tập afin là tập afin.
Định nghĩa 1.2.
a) Điểm x ∈ R
n
có dạng x = λ
1
a
1
+ λ
2
a
2
+ . . . + λ
k
a
k
với a
i
∈ R
n
,
λ
i
≥ 0, λ
1
+ λ

1
+ λ
2
+ . . . λ
k
= 1, gọi là một tổ hợp afin của các điểm a
1
, a
2
, . . . , a
k
.
c) Điểm x ∈ R
n
có dạng x = λ
1
a
1
+ λ
2
a
2
+ . . . + λ
k
a
k
với a
i
∈ R
n

đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính.
a
i1
x
1
+ a
i2
x
2
+ . . . + a
in
x
n
≤ b
i
, i = 1, 2, . . . , m.
6
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
nghĩa là tập các x ∈ R
n
nghiệm đúng Ax ≤ b với A = (a
ij
) ∈ R
m×n
,
b = (b
1
, . . . , b
m
)

n
≤ b
i
, i = p + 1, . . . , m,
Một tập lồi đa diện có thể khơng bị chặn (khơng giới nội). Một tập lồi đa
diện bị chặn còn được gọi là một đa diện lồi (polytope). Các đa giác lồi theo
nghĩa thơng thường trong R
2
là những ví dụ cụ thể về đa diện lồi.
Cho D = {x ∈ R
n
: Ax = b, x ≥ 0}, tức D là tập nghiệm khơng âm của
một hệ phương trình tuyến tính. Theo định nghĩa, D là một tập lồi đa diện.
Tập này khơng chứa trọn đường thẳng nào (do x ≥ 0) nên D có đỉnh. Các
phương cực biên (đã chuẩn hóa) của D là các nghiệm cơ sở của hệ Ay = 0,
e
T
y = 1, y ≥ 0 trong đó e = (1, . . . , 1)
T
.
Ta có định lý biểu diễn sau đây, hay được dùng trong các chứng minh.
Định lý 1.1. Mỗi điểm của tập lồi đa diện D = {x ∈ R
n
: Ax = b, x ≥ 0}
có thể biểu diễn dưới dạng một tổ hợp lồi của một tập hữu hạn các đỉnh của
D cộng với một tổ hợp tuyến tính khơng âm của một tập hữu hạn các phương
cực biên của D.
Ví dụ 1.2. Ví dụ này nhằm minh họa cho cách biểu diễn một điểm thuộc
một tập lồi đa diện dưới dạng một tổ hợp lồi của một tập hữu hạn các đỉnh
cộng với một tổ hợp tuyến tính khơng âm của một tập hữu hạn các phương

= 0) và (x
1
= 0, x
2
≥ 2).
Các phương cực biên của D gồm có v
1
= (1, 0)
T
và v
2
= (0, 1)
T
.
Với ví dụ này, Định lý 1.1 nói rằng mỗi điểm x ∈ D có thể viết dưới dạng:
x = α
1

2
0

+ α
2

0
2

+ β
1


= β
2
= 1 hoặc α
1
= α
2
= 0, 5, β
1
= 0,
β
2
= 2 hoặc một tổ hợp lồi bất kỳ của hai biểu diễn này.
1.2 Hàm lồi, hàm lõm và mở rộng
Định nghĩa 1.6.
a) Hàm f : S → [−∞, +∞] xác định trên một tập lồi S ⊆ R
n
gọi là một
hàm lồi trên S nếu với mọi x
1
, x
2
∈ S và mọi số thực λ ∈ [0, 1] ta có
f[λx
1
+ (1 − λ)x
2
] ≤ λf(x
1
) + (1 − λ)f(x
2

f hữu hạn và vừa lồi, vừa lõm trên S.
Một hàm afin trên R
n
có dạng f(x) = a
T
x + α với a ∈ R
n
, α ∈ R bởi vì
với mọi x
1
, x
2
∈ R
n
và mọi λ ∈ [0, 1] ta có
f[λx
1
+ (1 − λ)x
2
] = λf(x
1
) + (1 − λ)f(x
2
)
Hàm tuyến tính là trường hợp riêng của hàm afin, khi α = 0. Tuy nhiên,
hàm afin (nói riêng, hàm tuyến tính) khơng lồi chặt hay lõm chặt.
8
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Nhận xét 1.2. Hàm lồi f : S → [−∞, +∞] có thể mở rộng thành hàm lồi
xác định trên R

+ Hàm khoảng cách từ điểm x ∈ R
n
tới C : d
C
(x) = inf
y∈C
x − y.
• Bốn phép tốn cơ bản bảo tồn tính lồi của hàm (suy trực tiếp từ định
nghĩa):
a) Nếu f
i
: R
n
→ R, (i = 1, . . . , m) là các hàm lồi thì α
1
f
1
+ . . . + α
m
f
m
lồi với mọi α
i
≥ 0 và lồi chặt nếu ít nhất một trong các hàm f
i
lồi chặt
với α
i
> 0.
b) Nếu f

m
(x)
(x ∈ R
n
) lồi nếu với
mọi c
i
≥ 0 và mọi hàm g
i
(x) lồi (chẳng hạn f(x
1
, x
2
) = e
x
1
+x
2
+ 2e
x
1
−x
2
là
hàm lồi).
Định lý sau nêu mối liên hệ đáng chú ý giữa hàm lồi và tập lồi.
Định lý 1.2. Giả sử f : R
n
→ [−∞, +∞] là một hàm lồi trên tồn khơng
gian R

x
1
, x
2
∈ S ta có bất đẳng thức
f[λx
1
+ (1 − λ)x
2
] ≤ max{f(x
1
), f(x
2
)} với mọi λ ∈ (0, 1)
Ví dụ 1.4. Các hàm f(x) = x
3
, f(x) =

| x | trên R là những hàm tựa lồi,
nhưng khơng lồi.
Hàm f được gọi là tựa lõm nếu −f là hàm tựa lồi.
Định nghĩa 1.9. Cho hàm f : S → R với S là một tập lồi khác rỗng trong R
n
.
Hàm f được gọi là tựa lồi chặt (strictly quasiconvex) nếu với mọi x
1
, x
2
∈ S
và f(x

1
= 1, x
2
= −1
thì f(x
1
) = f(x
2
) = 0 và
f(
1
2
x
1
+
1
2
x
2
) = f(0) = 1 > max{f(x
1
), f(x
2
)} = 0.
Định nghĩa 1.10. Cho S là một tập lồi mở khác rỗng trong R
n
và giả sử
hàm f : S → R khả vi trên S. Hàm f được gọi là giả lồi (pseudoconvex) nếu
với mọi x
1

R
n
và f : S → R là một hàm giả lồi, khả vi trên S. Khi đó, f đồng thời là
hàm tựa lồi và tựa lồi chặt.
1.3 Cực tiểu địa phương và tồn cục
Định nghĩa 1.11. x
∗
∈ S gọi là một điểm cực tiểu địa phương (local minimum)
của f trên S nếu có ε > 0 sao cho f(x
∗
) ≤ f(x) với mọi x ∈ S và x−x
∗
 < ε.
Nếu f(x
∗
) < f(x) với mọi x ∈ S, x = x
∗
và x − x
∗
 < ε thì x
∗
được gọi là
cực tiểu địa phương chặt (strictly local minimum) của f trên S.
Định nghĩa 1.12. x
∗
∈ S gọi là một điểm cực tiểu tồn cục (global minimum)
của f trên S nếu f(x
∗
) ≤ f(x) với mọi x ∈ S. Nếu f(x
∗

x∈S
f(x) = −∞.
Định lý sau nêu một số tính chất đặc trưng cơ bản của các hàm lồi.
Định lý 1.4. (Xem [2], tr. 67) Cho S là một tập khác rỗng trong R
n
và
f : R
n
→ R là một hàm lồi. Mọi điểm cực tiểu địa phương của f trên S đều
là điểm cực tiểu tồn cục. Tập tất cả các điểm cực tiểu của f trên S là một
tập lồi.
Tương tự Định lý 1.4: Bất cứ điểm cực đại địa phương nào của một hàm
lõm trên một tập lồi cũng là điểm cực đại tồn cục và tập tất cả các điểm cực
đại của một hàm lõm trên một tập lồi là lồi.
Định lý 1.4 có thể mở rộng cho hàm tựa lồi chặt (xem Định nghĩa 1.9).
Định lý 1.5. Cho S là một tập lồi, khác rỗng trong R
n
và f : R
n
→ R là một
hàm tựa lồi chặt. Mọi điểm cực tiểu địa phương của f trên S đều là điểm cực
tiểu tồn cục.
Chứng minh: Giả sử x ∈ S là một điểm cực tiểu địa phương của f trên
S. Nếu x khơng là cực tiểu tồn cục trên S thì tìm được ˆx ∈ S sao cho
f(ˆx) < f(x). Do S lồi nên λˆx + (1 − λ)x ∈ S với mọi λ ∈ (0, 1). Do x là
cực tiểu địa phương nên f(x) ≤ f[λˆx + (1 − λ)x] với mọi λ ∈ (0, δ), trong
đó δ > 0 đủ nhỏ. Nhưng vì hàm f tựa lồi chặt và f(ˆx) < f(x) nên ta có
f[λˆx + (1 − λ)x] < f(x) với mọi λ ∈ (0, 1). Điều này trái với x là cực tiểu
địa phương và vì thể định lý được chứng minh.
Với hàm lồi chặt ta có tính chất đáng chú ý sau.

∗
= 1, trong khi đó hàm lồi chặt f(x) = e
x
+ 1 (x ∈ R) khơng có điểm
cực tiểu nào.
Về cực đại của hàm lồi ta chú ý tới tính chất sau:
12
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Định lý 1.7. Giả sử S là một tập lồi compact trong R
n
và f : S → R là một
hàm lồi. Khi đó, nếu f đạt cực đại trên S thì cực đại sẽ đạt tại một điểm cực
biên của S.
Chứng minh: Trước hết ta chỉ ra rằng hàm f đạt cực đại tại một điểm biên
của S. Giả sử x
∗
∈ S là điểm tại đó f đạt cực đại trên S. Nếu x
∗
khơng phải
là điểm biên của S thì ta đặt
L = {x : x = x
∗
+ λd, λ ∈ R}
là đường thẳng đi qua x
∗
, trong đó d ∈ R
n
là véctơ với các tọa độ dương. Khi
đó, sử dụng tính lồi và tính compact của S, ta thấy rằng tập S ∩ L có dạng
{x

2
λ
2
− λ
1
)f(x
∗
+ λ
2
d)
<
λ
2
λ
2
− λ
1
f(x
∗
) + (1 −
λ
2
λ
2
− λ
1
)f(x
∗
+ λ
2

1
là điểm cực biên của T
1
thì như đã
biết trong giải tích lồi, x
1
cũng sẽ là một điểm cực biên của S và định lý được
chứng minh. Nếu trái lại (x
1
khơng phải là điểm cực biên của T
1
) thì ta xem
M
1
như khơng gian (n − 1) chiều và xây dựng T
2
là giao của T
1
với một siêu
phẳng của T
1
đi qua M
1
trong x
1
và để T
1
ở một phía của nửa khơng gian
tạo bởi siêu phẳng đó. Siêu phẳng này có số chiều bằng (n − 2). Lặp lại q
trình này nhiều nhất n lần, cho đến khi nhận được tập T

i
) < f(x
∗
) với mọi i = 1, . . . , k. Tương tự Định lý 1.1, ta có biểu diễn
x
∗
=
k

i=1
λ
i
x
i
với mọi λ
i
≥ 0, i = 1, . . . , k và
k

i=1
λ
i
= 1.
Do f(x
∗
) > f(x
i
) với mọi i = 1, . . . , k nên
f(x
∗

∗
) = f(x
i
) với một
đỉnh x
i
nào đó của S.
Tóm lại, chương này đã nhắc lại kiến thức cần thiết về tập lồi, tập lồi đa
diện và các tính chất của chúng; hàm lồi, hàm lõm và một số mở rộng của các
hàm này, cùng các tính chất cơ bản. Cuối chương nêu một số tính chất cực
trị đáng chú ý của các hàm này. Các kiến thức này sẽ được dùng đến ở các
chương sau, khi xét lý thuyết và thuật tốn giải các bài tốn tối ưu với hàm
mục tiêu là tỉ số của hai hàm tuyến tính.
14
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Chương 2
Bài tốn qui hoạch phân tuyến tính
Chương này xét bài tốn tối ưu với hàm mục tiêu là tỉ số của hai hàm
tuyến tính (hàm phân tuyến tính) và với các ràng buộc (đẳng thức hay bất
đẳng thức) tuyến tính. Các bài tốn như thế gọi là bài tốn qui hoạch phân
tuyến tính. Phần đầu trình bày nội dung và ý nghĩa thực tiễn của bài tốn,
các dạng hay gặp của bài tốn và nêu mối quan hệ giữa bài tốn qui hoạch
phân tuyến tính và bài tốn qui hoạch tuyến tính. Cuối chương, xét tính chất
nghiệm của bài tốn với hai biến số. Nội dung của chương được tham khảo
chủ yếu từ các tài liệu [3], [4] và [6].
2.1 Bài tốn và tính chất
Nhà tốn học Hung-ga-ri Béla Martos (1960) đã nêu ra và nghiên cứu bài
tốn sau đây, gọi là bài tốn qui hoạch hypecbolic, trong tài liệu tiếng Anh
gọi là bài tốn qui hoạch phân tuyến tính. Ở dạng chung nhất, bài tốn này
được phát biểu như sau.















n

j=1
a
ij
x
j
≤ b
i
, i = 1, 2, . . . , m
1
,
n

j=1
a

j
≥ 0, i = 1, 2, . . . , m, (2.3)
trong đó p = (p
1
, p
2
, . . . , p
n
)
T
, q = (q
1
, q
2
, . . . , q
n
)
T
là các véctơ cột n−chiều,
b = (b
1
, b
2
, . . . , b
m
)
T
là các véctơ cột m−chiều, A = (a
ij
)

hàm q(x) liên tục nên tồn tại x ∈ [x
1
, x
2
], tức x ∈ S, sao cho q(x) = 0. Vì
thế, khơng giảm tổng qt, ta có thể giả thiết q(x) > 0 với mọi x ∈ S. Trường
hợp q(x) < 0, 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), sẽ có q(x) > 0. Hơn nữa, ta giả thiết m ≤ n và hệ (2.2) độc lập tuyến
tính, nghĩa là ma trận A = (a
ij
)
m×n
có hạng bằng m (rank A = m).
Có thể giải thích ý nghĩa thực tiễn của bài tốn qui hoạch phân tuyến tính
như sau: 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 b
i
là lượng vật tư i, (i = 1, 2, . . . , m) mà xí nghiệp
có và a
ij
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, 2, . . . , 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

là hàm đơn điệu trên mỗi đoạn thẳng nằm trọn
trong miền chấp nhận được S.
Chứng minh: Lấy hai điểm tùy ý a ∈ S, b ∈ S và tính giá trị hàm f
tại điểm x bất kì trên đoạn thẳng nối a và b, tức là x = λa + (1 − λ)b với
0 ≤ λ ≤ 1. Ta thấy
f(x) =
p[λa + (1 − λ)b]
q[λa + (1 − λ)b]
=
λp(a) + (1 − λ)p(b)
λq(a) + (1 − λ)q(b)
.
Đạo hàm theo λ:
df(x)
dλ
=
1
q
2
(x)
×




p(a) p(b)
q(a) q(b)




2
∈ S sao cho q
T
x
1
+ β > 0 và
q
T
x
2
+ β < 0, do đó sẽ có q
T
x + β = 0 với x là một tổ hợp lồi của x
1
và x
2
,
trái với giả thiết định lý.
Trước hết ta chứng minh f giả lồi. Thật vậy, giả sử x
1
∈ S, x
2
∈ S thỏa
mãn (x
2
− x
1
)
T
 f(x

T
 f(x
1
) ≥ 0 và do (q
T
x
1
+ β)
2
> 0 nên
0 ≤ (x
2
− x
1
)
T
[(q
T
x
1
+ β)p − (p
T
x
1
+ α)q]
= (p
T
x
2
+ α)(q

x
1
+β)
và (q
T
x
2
+ β) cùng dương hoặc cùng âm nên chia cả hai vế cho
(q
T
x
1
+ β)(q
T
x
2
+ β) > 0
17
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
ta được
p
T
x
2
+ α
q
T
x
2
+ β

). Vì thế, f giả lõm. Định lý được chứng minh.
Từ định lý 2.2 ở trên suy ra các hệ quả đáng chú ý sau về hàm phân tuyến
tính f(x):
1. Do hàm mục tiêu f(x) vừa giả lồi vừa giả lõm nên theo Định lý 1.3,
f(x) cũng đồng thời là hàm tựa lồi, tựa lõm, tựa lồi chặt và tựa lõm chặt.
2. Do hàm mục tiêu f(x) vừa tựa lồi chặt vừa tựa lõm chặt nên theo Định
lý 1.5 điểm cực tiểu (cực đại) địa phương cũng là điểm cực tiểu (cực đại) tồn
cục trên miền chấp nhận được.
3. Hàm mục tiêu f(x) vừa giả lồi vừa giả lõm nên theo Định lý 4.3.8 (xem
[4], tr.207), điểm thỏa mãn điều kiện KKT cho bài tốn cực tiểu cũng là điểm
cực tiểu tồn cục trên miền chấp nhận được. Tương tự, điểm thỏa mãn điều
kiện KKT cho bài tốn cực đại cũng là điểm cực đại tồn cục trên miền chấp
nhận được.
4. Do hàm mục tiêu f(x) tựa lõm (tựa lồi) nên nếu miền chấp nhận được
bị chặn thì theo Định lý 1.8, f(x) đạt cực tiểu (cực đại) tại một đỉnh của
miền chấp nhận được.
Các sự kiện nêu trên về hàm mục tiêu f(x) cho thấy rằng nếu bài tốn qui
hoạch phân tuyến tính (LFP) có lời giải tối ưu thì nó cũng có lời giải cực biên
tối ưu, nghĩa là ta có thể tìm lời giải tối ưu trong số các đỉnh của tập lồi đa
diện S. Do vậy, phương pháp đơn giản là đi từ một đỉnh của S, qua đỉnh kề
nó, cho tới khi gặp đỉnh thỏa mãn điều kiện KKT thì dừng lại và đó là đỉnh
tối ưu.
2.2 Dạng chính tắc và dạng tổng qt
Để tiện cho việc giải tốn, người ta thường xét hai trường hợp riêng sau
đây của bài tốn (2.1) − (2.3).
Dạng chuẩn (standard form). Đó là bài tốn có dạng:
f(x) =
p(x)
q(x)
=

x
j
≥ 0, j = 1, 2, . . . , n.
Trong bài tốn này mọi ràng buộc chính có dạng đẳng thức và mọi biến
số đều khơng âm, tương ứng với m
1
= m
2
= 0 và n
1
= n trong (2.2), (2.3).
Dạng tổng qt (general form). Đó là bài tốn có dạng:
f(x) =
p(x)
q(x)
=
n

j=1
p
j
x
j
+ α
n

j=1
q
j
x

1j
, a
2j
, . . . , a
mj
)
T
, j = 1, 2, . . . , n,
b = (b
1
, b
2
, . . . , b
m
)
T
, A = (A
1
, A
2
, . . . , A
n
),
x = (x
1
, x
2
, . . . , x
n
)

p
T
x + α
q
T
x + β
: Ax ≤ b, x ≥ 0}.
Cũng như trong qui hoạch tuyến tính, bằng cách dùng một số phép biến
đổi đơn giản ta có thể đưa bài tốn (2.1) − (2.3) về dạng chuẩn hoặc dạng
tổng qt và cũng có thể chuyển bài tốn từ dạng chuẩn sang dạng tổng qt
19
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
hoặc ngược lại.
Hơn nữa, do
max
x∈S
f(x) = − min
x∈S
[−f(x)]
nên bài tốn tìm max có thể đưa về bài tốn tìm min và ngược lại. Vì thế,
đơi khi ta chỉ cần xét bài tốn tìm min là đủ.
2.3 Liên hệ với quy hoạch tuyến tính
Rõ ràng là nếu mọi q
j
= 0, (j = 1, 2, . . . , n) và β = 1 thì bài tốn qui
hoạch phân tuyến tính (2.1) − (2.3) trở thành bài tốn qui hoạch tuyến tính:
min{p(x) : x ∈ S}. Vì thế, có thể thấy qui hoạch phân tuyến tính là sự mở
rộng của qui hoạch tuyến tính.
Trong vài trường hợp cá biệt, bài tốn qui hoạch phân tuyến tính có thể
được thay thế bằng bài tốn qui hoạch tuyến tính thích hợp:

p(x)
q(x)
=
α
n

j=1
q
j
x
j
+ β
.
có thể thay bằng hàm q(x). Trong trường hợp này cực tiểu (cực đại) của hàm
mục tiêu ban đầu f(x) được thay bằng
• Cực đại (cực tiểu) của hàm mục tiêu mới q(x) trên tập S nếu α > 0.
• Cực tiểu (cực đại) của hàm mục tiêu mới q(x) trên tập S nếu α < 0.
3. Nếu véctơ p = (p
1
, p
2
, . . . , p
n
)
T
và q = (q
1
, q
2
, . . . , q

q
j
x
j
+ β
20
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
có thể thay bằng hàm q(x). Rõ ràng trong trường hợp này, cực tiểu (cực đại)
của hàm mục tiêu ban đầu f(x) có thể thay thế bằng
• Cực đại (cực tiểu) của hàm q(x) trên tập S nếu α − λβ > 0.
• Cực tiểu (cực đại) của hàm q(x) trên tập S nếu α − λβ < 0.
Cần chú ý là trong trường hợp α − λβ = 0 thì f(x) = λ, nghĩa là
f(x) = const với mọi x ∈ S. Ta sẽ khơng xét bài tốn như thế, vì nó khơng
có ý nghĩa gì.
Vì vậy, từ đây về sau ta khơng cần xét tới ba trường hợp tầm thường sau:
a) p(x) = const với mọi x ∈ S.
b) q(x) = const với mọi x ∈ S.
c) f(x) = const với mọi x ∈ S.
bởi vì trong các trường hợp này bài tốn qui hoạch phân tuyến tính ban đầu
qui được về bài tốn qui hoạch tuyến tính (hai trường hợp đầu) hoặc thực sự
trở thành vơ nghĩa (trường hợp cuối).
2.4 Bài tốn hai biến số
Xét bài tốn qui hoạch phân tuyến tính hai biến số:
f(x) =
p(x)
q(x)
=
p
1
x

≥ 0, x
2
≥ 0. (2.6)
2.4.1 Lời giải tối ưu duy nhất
Giả sử các ràng buộc (2.5) - (2.6) xác định miền chấp nhận được vẽ ở
Hình 2.1.
Cho γ là một hằng số tùy ý. Với mỗi γ, phương trình f(x) = γ hay
(p
1
− γq
1
)x
1
+ (p
2
− γq
2
)x
2
+ (α − γβ) = 0
biểu thị một đường thẳng, gọi là đường mức mục tiêu, trong mặt phẳng hai
chiều x
1
Ox
2
. Nếu đường mức cắt tập ràng buộc S thì mỗi điểm thuộc phần
21
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Hình 2.1: Lời giải tối ưu duy nhất
chung này là một lời giải chấp nhận của bài tốn và có giá trị hàm mục tiêu

tốn qui hoạch tuyến tính. Vì thế, trong trường hợp này cực tiểu của hàm
mục tiêu f(x) sẽ được thay bằng cực đại hay cực tiểu của mẫu số q(x) của
nó, tùy thuộc vào dấu của biểu thức α − λβ.
Ta trở lại xét trường hợp hai đường thẳng p(x) = 0 và q(x) = 0 cắt nhau.
Lấy một giá trị γ tùy ý và vẽ đường mức f(x) = γ (xem Hình 2.1). Ta viết
lại phương trình f(x) = γ thành
x
2
=
p
1
− γq
1
p
2
− γq
2
x
1
−
α − γβ
p
2
− γq
2
Trong trường hợp này hệ số góc
k =
p
1
− γq

khơng phụ thuộc vào γ, vì thế ta có thể viết
sign{
dk
dγ
} = sign{q
1
p
2
− q
2
p
1
} = const.
Điều này có nghĩa là khi quay đường mức mục tiêu quanh tiêu điểm F của
nó theo chiều quay của kim đồng hồ thì giá trị hàm mục tiêu f(x) tăng hay
giảm phụ thuộc vào dấu của biểu thức (q
1
p
2
− p
2
q
1
).
Hình (2.1) minh họa trường hợp khi quay đường mức theo chiều quay của
kim đồng hồ làm tăng giá trị f(x). Khi quay đường mức quanh F tới hai vị
trí giới hạn (trái và phải), đường thẳng f(x) = γ cắt tập ràng buộc S tại hai
đỉnh tương ứng x
∗
và x