ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HỒNG LÊ
PHƯƠNG PHÁP ĐIỂM TRONG
GIẢI QUI HOẠCH TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HỒNG LÊ
PHƯƠNG PHÁP ĐIỂM TRONG
GIẢI QUI HOẠCH TUYẾN TÍNH
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 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
LỜI NÓI ĐẦU 1
Nội dung 5
1 KIẾN THỨC CHUẨN BỊ 5
1.1 Qui hoạch tuyến tính và qui hoạch đối ngẫu . . . . . . . . 5
1.2 Phương pháp đơn hình và đơn hình đối ngẫu . . . . . . . . 9
1.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 12
1.4 Ví dụ Klee-Minty về độ phức tạp mũ . . . . . . . . . . . . . 15
2 PHƯƠNG PHÁP ELLIPSOID 19

còn được sử dụng rộng rãi để giải các bài toán qui hoạch tuyến tính. Cách
tiếp này chỉ cần xét các đỉnh của tập đa diện ràng buộc và mỗi lần lặp đi
từ một đỉnh tới một đỉnh kề với nó, thường là tốt hơn đỉnh trước đó (cải
tiến được giá trị của hàm mục tiêu). Cuối cùng, nó đạt tới đỉnh mà từ đó
không thể cải tiến hàm mục tiêu được nữa, đỉnh đó chính là lời giải cần
tìm của bài toán.
Mặc dầu nó rất hiệu quả trong thực tiễn (số lần lặp thường nhỏ hơn
m+n, trong đó m là số ràng buộc tuyến tính và n là số biến của bài toán).
Tuy nhiên, V.Klee và G.Minty(1972) đã đưa ra một bài toán qui hoạch
tuyến tính đặc biệt mà để giải nó cần một thời gian tỉ lệ với hàm mũ của
n. Điều này chứng tỏ về mặt lý thuyết thuật toán đơn hình không phải là
một thuật toán thời gian đa thức.
Vào những năm 1950, người ta đã đề cao tới các phương pháp điểm
trong (đi từ phía trong miền ràng buộc). Tuy nhiên, chúng chưa thành đạt
như phương pháp đơn hình. Năm 1979 [4] Khachian là người đầu tiên đã
chứng minh được rằng có thể giải bài toán qui hoạch tuyến tính trong thời
gian đa thức, bằng cách sử dụng thuật toán điểm trong thích hợp. Mặc
dầu thuật toán Khachian chưa đủ hiệu quả trong thực tiễn, nhưng thành
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
tựu này của Khachian đã làm khởi sắc sự quan tâm trở lại tới các phương
pháp điểm trong giải qui hoạch tuyến tính.
Tiếp đó, năm 1984 [3] Karmarkar đã đề xuất một phương pháp điểm
trong mới giải qui hoạch tuyến tính. Phương pháp này có độ phức tạp đa
thức và nó có hiệu năng thực tiễn cao, đặc biệt đối với các bài toán tuyến
tính cỡ lớn.
Các công trình nghiên cứu của Khachian và Karmarkar là điểm khởi
đầu cho nhiều nghiên cứu về các phương pháp điểm trong giải qui hoạch
tuyến tính. Đó cũng là chủ đề chính của luận văn này. Cách tiếp cận mới
khác cơ bản với phương pháp đơn hình . Thay cho đi trên các cạnh của tập

sự kiện trình bày ở chương này được minh họa qua các ví dụ và hình vẽ
cụ thể.
Chương 3 “ Phương pháp điểm trong ” trình bày các khái niệm cơ
bản về tâm giải tích, đường trung tâm gốc và đối ngẫu; những nội dung
chính của phương pháp gốc-đối ngẫu, từ ý tưởng phương pháp (đi men
theo đường trung tâm) đến thuật toán cụ thể (thuật toán bám đường).
Phương pháp này được đánh giá là phương pháp điểm trong hiệu quả nhất
giải qui hoạch tuyến tính. Tiếp đó, giới thiệu hai thuật toán bám đường
tiêu biểu: thuật toán dự báo và thuật toán hiệu chỉnh. Vấn đề khởi sự và
kết thúc thuật toán cũng được đề cập tới.
Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập
tới những nội dung cơ bản của phương pháp điểm trong giải qui hoạch
tuyến tính, chưa đi sâu vào các chi tiết thực thi thuật toán. Trong quá
trình viết luận văn cũng như trong xử lý văn bản chắc chắn không tránh
khỏi những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp
ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện
hơn.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Tác giả xin trân trọng cảm ơn các thầy, cô giáo Trường Đại học Khoa
học- Đại học Thái Nguyên, Viện Toán học-Viện 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.
Tác giả cũng xin chân thành cảm ơn Ban giám hiệu, tổ toán –tin Trường
THPT Ngô Quyền –Thái Nguyên và tập thể bạn bè đồng nghiệp cùng gia
đình đã quan tâm giúp đỡ, động viên tác giả hoàn thành tốt luận văn này.
Thái Nguyên, tháng 09 năm 2011.

n
+
.
T là ký hiệu chuyển vị véctơ, D = {x ∈ R
n
: Ax ≥ b, x ≥ 0} là một tập
lồi đa diện.
• Dạng chính tắc (canonical form):
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
min

f (x) = c
T
x : Ax = b, x ≥ 0

,
trong đó các ký hiệu A ∈ R
m×n
, b ∈ R
m
, c, x ∈ R
n
như ở trên. Trong bài
toán này, tập D = {x ∈ R
n
: Ax = b, x ≥ 0} cũng là một tập lồi đa diện.
Trong hai dạng trên, f gọi là hàm mục tiêu, D gọi là tập ràng buộc
hay miền chấp nhận được. Điểm x = (x
1

min) thì qui hoạch đó chắc chắn có lời giải tối ưu. 
Định nghĩa 1.1. Một lời giải chấp nhận được x ∈ D mà đồng thời là
đỉnh của D gọi là một lời giải cơ sở, nghĩa là x không thể biểu diễn dưới
dạng một tổ hợp lồi của bất cứ hai lời giải chấp nhận được khác của D.
Nói một cách khác, hễ x = λx
1
+ (1 −λ) x
2
với 0 < λ < 1 và x
1
, x
2
∈ D
thì phải có x = x
1
= x
2
.
Định lý sau nêu một tính chất đặc trưng cho lời giải cơ sở của qui hoạch
tuyến tính chính tắc với giả thiết m ≤ n và rank(A) = m.
Định lý 1.2. Để một lời giải chấp nhận được
x = {x
1
, x
2
, . . . , x
n
} của qui
hoạch tuyến tính chính tắc là lời giải cơ sở, thì cần và đủ là các véctơ cột
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

T
y ≤ c, y ≥ 0

(A
T
là ma trận chuyển vị của ma trận A).
• Đối ngẫu của qui hoạch tuyến tính dạng chính tắc
min

f (x) = c
T
x : Ax = b, x ≥ 0

là quy hoạch tuyến tính max

g (y) = b
T
y : A
T
y ≤ c

(biến đối ngẫu y
dấu tùy ý).
Định lý 1.3. (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của
bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu
(Q) thì
f (x) = c
1
x
1

nào.
c) Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trên tập
ràng buộc của nó thì bài toán gốc không có bất kỳ lời giải chấp nhận được
nào.
d) Nếu x
∗
là một lời giải chấp nhận được của bài toán gốc, y
∗
là một lời
giải chấp nhận được của bài toán đối ngẫu và f(x*) = g(y*) thì x
∗
là lời
giải tối ưu của bài toán gốc và y
∗
là lời giải tối ưu của bài toán đối ngẫu.
Định lý 1.4. (Đối ngẫu mạnh). Nếu một qui hoạch có lời giải tối ưu thì
qui hoạch đối ngẫu của nó cũng có lời giải tối ưu và các trị tối ưu bằng
nhau. 
Các kết quả trên cho thấy quan hệ sau giữa hai qui hoạch gốc và đối
ngẫu.
Định lý 1.5. (Định lý đối ngẫu cơ bản). Đối với mỗi cặp qui hoạch tuyến
tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây:
a) Cả hai bài toán đều không có lời giải chấp nhận được.
b) Cả hai bài toán đều có lời giải chấp nhận được. Khi đó, cả hai đều
có lời giải tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau.
c) Một bài toán có lời giải chấp nhận được và bài toán kia không có lời
giải chấp nhận được. Khi đó, bài toán có lời giải chấp nhận được sẽ có giá
trị tối ưu vô cực (+∞ hay −∞ tuỳ theo bài toán max hay min ). 
Định lý 1.6. (Định lý độ lệch bù). Một cặp lời giải chấp nhận được x, y
của hai qui hoạch đối ngẫu (P) và (Q) là cặp lời giải tối ưu khi và chỉ khi

y
i

= 0 với mọi j = 1, 2, . . . , n.
Định lý 1.7. (Định lý độ lệch bù chặt). Nếu cặp bài toán đối ngẫu
(P) và (Q) có lời giải chấp nhận được thì tồn tại cặp lời giải tối ưu x
∗
, y
∗
nghiệm đúng
y
∗
+ (Ax
∗
− b) > 0và x
∗
+

c −A
T
y
∗

> 0.
1.2 Phương pháp đơn hình và đơn hình đối ngẫu
Bằng cách thực hiện một số phép biến đổi đơn giản, ta có thể đưa bài
toán qui hoạch tuyến tính từ dạng này sang dạng khác. Vì thế khi giải ta
chỉ cần chọn một dạng thuận tiện để xét mà không làm giảm tính tổng
quát của phương pháp.
Xét qui hoạch tuyến tính chính tắc (m ràng buộc đẳng thức, n biến):

> 0 (j = 1, 2, . . . , m) .
Ký hiệu
J = {j : x
j
> 0} = {1, 2, . . . , m}.
Các vectơ {A
j
, j ∈ J} là độc lập tuyến tính (Định lý 1.2) và |J| = m
(do x không suy biến). Hệ vectơ {A
j
, j ∈ J} gọi là cơ sở của lời giải x.
Để cho tiện, đôi khi ta cũng gọi J (với các tính chất trên) là cơ sở của
x. Các vectơ A
j
và các biến x
j
với j ∈ J được gọi là các vectơ cơ sở và
biến cơ sở tương ứng với x . Còn các vectơ A
j
và các biến x
j
với j /∈ J
gọi là các vectơ và biến ngoài cơ sở.
Ký hiệu B là ma trận lập nên từ các vectơ cơ sở đang xét:
B = {A
1
, A
2
, . . . , A
m

mk
A
m
vớik = 1, . . . , n (1.1)
Ký hiệu các vectơ cột z
k
= (z
1k
, z
2k
, . . . , z
mk
)
T
, x
B
= (x
1
, x
2
, . . . , x
m
)
T
,
vectơ hàng c
B
= (c
1
, c

1
x
1
+ c
2
x
2
+ . . . + c
m
x
m
= c
B
B
−1
b. (1.2)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
Với mỗi k = 1, 2, . . . , n ta tính số sau đây, gọi là ước lượng của biến x
k
:
∆
k
= c
B
z
k
− c
k
= c

, ta có x
B
= B
−1
(b −Nx
N
) ( nói riêng x
B
= B
−1
b
do x
N
= 0 ) , suy ra công thức biểu diễn các biến ngoài cơ sở theo các
biến cơ sở:
x
B
= x
B
− B
−1
Nx
N
.
Từ đó, giá trị hàm mục tiêu tại x bằng
c
T
x = c
B
x

N

x
N
(1.4)
Chú ý là
B
−1
N =

B
−1
A
k
: k /∈ J

= {z
k
, k /∈ J}
thì vectơ ∆
N
= c
B
B
−1
N − c
N
= {c
B
z

hình để giải qui hoạch tuyến tính. Ta có
Định lý 1.8. (Dấu hiệu tối ưu). Nếu với lời giải cơ sở x của bài toán ta
có các hệ thức ∆
k
≤ 0 với mọi k /∈ J thì x là một lời giải (cơ sở) tối ưu
của bài toán.
Định lý 1.9. (Dấu hiệu bài toán có trị tối ưu vô cực). Nếu đối với lời giải
cơ sở x tồn tại chỉ số k /∈ J sao cho ước lượng ∆
k
> 0 và z
jk
≤ 0 với
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
mọi j ∈ J thì bài toán đã cho có trị tối ưu vô cực (−∞ đối với bài toán
min).
Có thể chứng minh được rằng nếu bài toán qui hoạch tuyến tính có lời
giải chấp nhận được và không suy biến thì thuật toán đơn hình sẽ cho lời
giải tối ưu (hữu hạn hay vô cực) sau một số hữu hạn lần thay đổi lời giải
cơ sở.
• Thuật toán đơn hình đối ngẫu.
Như đã thấy thuật toán đơn hình gốc xuất phát từ một lời giải cơ sở chấp
nhận được tương ứng với ma trận cơ sở B và luôn giữ cho B
−1
b ≥ 0.
Cơ sở B được biến đổi cho tới khi đạt lời giải tối ưu (∆
k
≤ 0 với mọi
k = 1, 2, . . . , n) hoặc khi phát hiện bài toán có giá trị tối ưu vô cực (có
∆

Từ ngữ độ phức tạp ám chỉ số lượng nguồn lực (bộ nhớ, thời gian) mà
máy tính đòi hỏi. Mục này tập trung vào nguồn lực đặc biệt, đó là thời
gian tính toán. Tuy nhiên trong lý thuyết độ phức tạp, người ta không
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
quan tâm tới thời gian thực hiện một chương trình máy tính viết bằng
một ngôn ngữ chương trình cụ thể, chạy trên một máy tính cụ thể với một
bộ dữ liệu đầu vào cụ thể. Thời gian tính toán phụ thuộc nhiều yếu tố
ngẫu nhiên. Thay vào đó, ta muốn gắn kết thuật toán với thước đo phản
ánh được bản chất của những đòi hỏi về thời gian tính.
Nói nôm na, để làm việc này ta cần xác định:
• Khái niệm kích thước đầu vào (input size),
• Tập các phép toán cơ bản (basic operations) và
• Chi phí cho mỗi phép toán cơ bản.
Hai đại lượng sau cho phép gắn kết với chi phí của một tính toán (cost
of a computation). Nếu x là một bộ dữ liệu đầu vào bất kỳ thì chi phí
C(x) của tính toán với đầu vào x là tổng các chi phí của mọi phép toán cơ
bản cần thực hiện trong tính toán đó.
Giả sử A là một thuật toán và I
n
là tập tất cả các đầu vào kích thước
n. Hàm chi phí trong trường hợp xấu nhất (worst-case cost function) của
thuật toán A là hàm T
w
A
(n) xác định bởi
T
w
A
(n) = sup

được miêu tả không quá số lượng cố định về bộ nhớ của máy tính; một số
loại khác lại đòi hỏi một số lượng thay đổi.
Ví dụ về loại thứ nhất là các số thực dấu phẩy động có độ chính xác
cố định được lưu trữ trong một lượng bộ nhớ cố định (thường là 32 hoặc
64 bit). Với loại dữ liệu này kích thước của mỗi số được lấy là 1 và do đó
mỗi số có kích thước đơn vị (unit size).
Ví dụ về loại thứ hai là các số nguyên đòi hỏi một số bít xấp xỉ bằng
logarit (cơ số 2) của giá trị tuyệt đối của chúng. Số logarit này thường
được gọi là kích thước bit (bit size) của số nguyên. Ý tưởng tương tự cũng
được áp dụng cho các số hữu tỉ.
Giả sử B là một loại dữ liệu nào đó và x = (x
1
, . . . , x
n
) ∈ B
n
. Nếu
B thuộc loại thứ nhất kể trên thì ta định nghĩa size (x) = n. Trái lại,
size(x)=tổng kích thước bit của các x
i
(i = 1, . . . , n) .
Chi phí của mỗi phép toán trên hai số kích thước đơn vị được lấy là 1
và được gọi chi phí đơn vị (unit cost). Trong trường hợp kích thước bit,
chi phí của phép toán trên hai số là tích hai kích thước bit của chúng (đối
với phép nhân và phép chia) hoặc bằng số lớn nhất trong hai kích thước
ấy (đối với phép cộng, phép trừ và phép so sánh).
Việc xét các dữ liệu nguyên và hữu tỉ với kích thước bit của chúng và
xét chi phí bit cho các phép toán số học thường được gọi là mô hình tính
toán Turing (Turing model of computation). Việc xét các số thực lý tưởng
hóa với kích thước đơn vị và chi phí đơn vị được gọi là mô hình số học

n
, số lần lặp đơn hình để giải
bài toán, bắt đầu từ một lời giải cơ sở chấp nhận được, là một bội số nhỏ
của m, thường là giữa 2m và 3m. Trên thực tế, Dantzig đã quan sát thấy
rằng đối với các bài toán có số ràng buộc m ≤ 50, số biến n ≤ 200 thì số
lần lặp đơn hình nói chung nhỏ hơn 1, 5m.
Có lúc các nhà nghiên cứu đã tin và thử tìm chứng minh rằng thuật
toán đơn hình (hay biến thể nào đó của nó) luôn đòi hỏi số lần lặp bị chặn
bởi một đa thức theo kích thước bài toán. Mãi cho đến khi Victor Klee và
George Minty đưa ra lớp bài toán qui hoạch tuyến tính mà mỗi bài trong
số đó đòi hỏi số lần lặp là hàm mũ, khi bài toán được giải theo phương
pháp đơn hình quen thuộc.
Để tiện tham khảo, sau đây nêu một dạng ví dụ của V.Klee và G.Minty.
n

j=1
10
n−j
x
j
→ max (KM)
với điều kiện
2
i−1

j=1
10
i−j
x
j

1
+ 20x
2
+ x
3
≤ 10000,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0
Trong trường hợp này bài toán có ba ràng buộc bất đẳng thức và ba biến
(với các biến có ràng buộc không âm). Sau khi thêm vào các biến bù (để
đưa các ràng buộc bất đẳng thức về ràng buộc đẳng thức) bài toán có dạng
chính tắc. Hệ ràng buộc có m = 3 phương trình và n = 6 biến không âm.
Có thể kiểm tra lại rằng (bằng cách lập bảng đơn hình và giải theo thuật
toán đơn hình) cần 2
3
−1 = 7 lần biến đổi bảng đơn hình để giải bài toán (ở
mỗi lần lặp ta chọn cột xoay là cột có ước lượng âm nhỏ nhất, vì đây là bài
toán tìm cực đại). Kết quả giải ví dụ này được ghi lại ở bảng 1.1 với phương
án tối ưu tìm được là: x
opt
= (0, 0, 10000, 1, 100, 0)
T
, f
max
= 10000.

j−1
y
j
→ min (MK)
với điều kiện
2
n

i=j+1
10
i−j
y
i
+ y
j
≥ 10
n−j
, j = 1, . . . , n
y
i
≥ 0, i = 1, . . . , n
Để giải bài toán (MK) tổng quát cũng cần 2
n
− 1 lần lặp theo thuật
toán đơn hình đối ngẫu.
Tóm lại, chương này đã trình bày tóm tắt về bài toán qui hoạch tuyến
tính, bài toán qui hoạch tuyến tính đối ngẫu, tính chất của lời giải cơ sở,
ý tưởng của phương pháp đơn hình và đơn hình đối ngẫu giải qui hoạch
tuyến tính. Có thể tìm thấy chứng minh các định lý trong tài liệu tham
khảo[1]. Nêu khái niệm độ phức tạp của thuật toán, thuật toán thời gian

x ≤ b
i
, i = 1, . . . , m

,
trong đó a
i
= (a
i1
, . . . , a
in
) ∈ R
n
. Như sẽ thấy, tìm một điểm thuộc Ω
tương đương với giải một qui hoạch tuyến tính. Chẳng hạn, min {ex : x ∈ X}
với e = (1, . . . , 1) ∈ R
n
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
20
2.1 Về hệ bất phương trình đại số tuyến tính
Xét một hệ gồm m bất phương trình tuyến tính của n biến độc lập
x
1
, . . . , x
n
a
i
x ≡ a
i1

n
.n!, ∀j = 1, . . . , n.
Hình 2.1: Minh họa Bổ đề 2.1
Chứng minh
Ký hiệu X là tập nghiệm của (2.1). Theo giả thiết X = ∅. Nếu mọi
a
ij
= 0 thì X = R
n
và hiển nhiên bổ đề đúng. Nếu trái lại ta xét tập
X ∩

a
1
x = b
1

. Nếu tập này rỗng, nghĩa là siêu phẳng

a
1
x = b
1

không
cắt X thì bất đẳng thức thứ nhất trong (2.1) là thừa và có thể bỏ đi mà
không làm thay đổi X. Nếu trái lại, ta thay bất đẳng thức thứ nhất trong
(2.1) bằng đẳng thức. Trong cả hai trường hợp ta thu được một hệ phương
trình và bất phương trình với tập nghiệm không rỗng X
1

, i = 1, . . . , k (2.2)
và định thức D = det a
ij

k
i,j=1
= 0. Vì a
i
j nguyên nên |D| ≥ 1. Cho
x
j
= 0 với j > k rồi giải (2.2) ta thu được nghiệm
x
j
=
k

s=1
D
js
D
, j = 1, . . . , k, (2.3)
trong đó D
js
là tử thức của D. Vậy |D
js
| ≤ (k − 1)!C
k−1
và |x
j

ij
D
js
b
s
+
ε
D
k

j=1
k

s=1
a
ij
D
js
≤ b
i
+ ε, i = 1, . . . , m (2.6)
Ta sẽ chứng tỏ rằng
1
D
k

j=1
k

s=1