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 THỊ HUỆ CẢI TIẾN PHƯƠNG PHÁP ĐƠN HÌNH
GIẢI QUY 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

1.1.2 Một số tính chất . . . . . . . . . . . . . . . . 8
1.2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 11
1.2.1 Dạng bài toán đối ngẫu . . . . . . . . . . . . 11
1.2.2 Định lí đối ngẫu . . . . . . . . . . . . . . . . 12
1.3 PHƯƠNG PHÁP ĐƠN HÌNH . . . . . . . . . . . . . . 13
1.3.1 Thuật toán đơn hình gốc . . . . . . . . . . . 14
1.3.2 Thuật toán đơn hình đối ngẫu . . . . . . . 17
2 PHƯƠNG PHÁP ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI
BIÊN 22
2.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 22
2.1.1 Nội dung bài toán và các kí hiệu . . . . . . 22
2.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . 23
2.2 THUẬT TOÁN ĐƠN HÌNH GỐC - ĐỐI NGẪU CẢI
BIÊN (RPDSA) . . . . . . . . . . . . . . . . . . . . . . 25
2.3 PHƯƠNG PHÁP M - LỚN ( BIG M - METHOD) . . 27
2.3.1 Tìm cơ sở đối ngẫu chấp nhận được B và
phân hoạch ( B, N ) ban đầu. . . . . . . . . 27
2.3.2 Tìm điểm gốc chấp nhận được y ban đầu 27
1
2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2.3.3 Phương pháp M - lớn ( Big - M Method . 28
2.3.4 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . 30
3 HAI PHƯƠNG PHÁP CẢI TIẾN KHÁC 33
3.1 BÀI TOÁN VÀ Ý TƯỞNG THUẬT TOÁN . . . . . . 33
3.1.1 Nội dung bài toán và các kí hiệu . . . . . . 33
3.1.2 Ý tưởng thuật toán . . . . . . . . . . . . . . 34
3.2 PHƯƠNG PHÁP GÓC NGHIÊNG NHỎ NHẤT . . . . 37
3.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . 37
3.2.2 Ví dụ 3.1 . . . . . . . . . . . . . . . . . . . . . 39
3.3 PHƯƠNG PHÁP CÔSIN ĐƠN HÌNH . . . . . . . . . 41

3
4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
kể có thuật toán đơn hình gốc đối ngẫu của K. Paparrizos et al., ([10],
2003) thuật toán cải tiến cơ sở ban đầu cho thuật toán đơn hình do
H. V. Junior và M. P. E. Lins đề xuất ([6], 2005) và thuật toán cô sin
đơn hình do H. W. Corley et al., đề xuất ([5], 2005) Kết quả tính toán
trên các bài toán thử nghiệm cho thấy các thuật toán mới hiệu quả
hơn thuật toán đơn hình cổ điển khoảng 30% và tỏ ra rất có triển vọng.
Luận văn này nhằm tìm hiểu và giới thiệu một số thuật toán mới
cải tiến thuật toán đơn hình, thuộc nhóm thứ hai kể trên. Cụ thể luận
văn sẽ trình bày phương pháp đơn hình điểm ngoài (EPSA, RPDSA),
phương pháp góc nghiêng nhỏ nhất (MA) và phương pháp côsin đơn
hình (CSA). Các thuật toán này có ý tưởng rõ ràng, dễ thực thi, khối
lượng tính toán giảm và do đó hiệu quả tính toán cao hơn. Vì thế,
tìm hiểu và nghiên cứu chủ đề này là cần thiết và hữu ích, giúp hiểu
rõ các mở rộng và ứng dụng của phương pháp đơn hình trong thực tiễn.
Nội dung luận văn được chia làm ba chương:
Chương 1: Kiến thức chuẩn bị Nhắc lại tóm tắt một số kiến thức
cơ bản cần thiết về nài toán quy hoạch tuyến tính và bài toán quy
hoạch tuyến tính đối ngẫu cùng các tính chất của chúng, về phương
pháp đơn hình và đơn hình đối ngẫu giải bài toán quy hoạch tuyến
tính. Nhiều khái niệm, sự kiện trình bày ở chương này được giải thích,
minh họa qua các ví dụ bằng số và hình vẽ cụ thể. Các kiến thức này
sẽ được dùng đến ở các chương sau.
Chương 2: Phương pháp đơn hình đối ngẫu- đối ngẫu cải biên
trình bày thuật toán đơn hình gốc - đối ngẫu cải biên (RPDSA) mà
thực chất là sự cải biên thuật toán đơn hình đối ngẫu. Thuật toán
RPDSA cũng có thể xem như một thuật toán đơn hình điểm ngoài
( exterior point simple algorithm - EPSA), vì các nghiệm cơ sở
k

đã quan tâm giúp đỡ, động viên để tôi hoàn thành tốt luận văn này.
Thái Nguyên, tháng 9/2011
5
6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Chương 1
KIẾN THỨC CHUẨN BỊ
Chương này trình bày một số kiến thức cơ bản cần thiết về quy
hoạch tuyến tính, phương pháp đơn hình ( thuật toán đơn hình gốc
và thuật toán đơn hình đối ngẫu ) và đối ngẫu trong quy hoạch tuyến
tính. Nội dung của chương chủ yếu dựa trên các tài liệu tham khảo
[1] - [4]
1.1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ TÍNH
CHẤT
Quy hoạch tuyến tính là bài toán tìm cực tiểu ( cực đại ) của một
hàm tuyến tính f(x) trên một tập lồi đa diện D ⊂ R
n
. Quy hoạch
tuyến tính là một trong những lớp bài toán tối ưu quan trọng nhất và
được ứng dụng rộng rãi nhất trong thực tiễn. Nó bắt nguồn từ nững
nghiên cứu của nhà bác học Nga nổi tiếng, Viện sĩ L. V. Kantorovich
trong một loạt công trình về kế hoạch hóa sản xuất công bố năm 939
và nó thực sự phát triển mạnh mẽ kể từ khi nhà toán học Mỹ G. B.
Dantzig đề xuất thuật toán đơn hình giải quy hoạch tuyến tính vào
năm 1947.
1.1.1 Nội dung bài toán
Bài toán quy hoach tuyến tính thường được viết ở một số dạng sau:
Dạng tổng quát ( abstract form ):
min{f(x) = c
T
x : x ∈ D}

→ min
với điều kiện
x
1
+ 2x
2
≥ 5,
3x
1
+ x
2
≥ 4,
x
1
≥ 0, x
2
≥ 0.
Dạng chính tắc ( canonical form):
min{f(x) = c
T
x : Ax = b, x ≥ 0}
với các kí hiệu như ở trên.
Ví dụ 1.2
Quy hoạch tuyến tính dạng chính tắc ba biến:
x
1
+ 3x
2
+ 2x
3

7
8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Trong các dạng trên, f được 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
, x
2
, , x
n
)
T
∈ D gọi
là một phương án hay một lời giải chấp nhận được của bài toán. Một
phương án cực tiểu ( cực đại ) của hàm mục tiêu gọi là phương án tối
ưu hay lời giải tối ưu.
Với mỗi bài toán quy hoạch tuyến tính chỉ xảy ra 1 trong 3 khả năng
sau:
a) Bài toán không có phương án ( tập ràng buộc D rỗng ).
b) Bài toán có phương án nhưng không có phương án tối ưu.
c) Bài toán có phương án tối ưu.
1.1.2 Một số tính chất
Định lí sau nêu điều kiện để một quy hoạch tuyến tính có phương
án tối ưu:
Định lí 1.1:
Nếu một quy hoạch tuyến tính có ít nhất một phương án và hàm
mục tiêu bị chặn dưới trong miền ràng buộc (đối với bài toán min) thì
bài toán chắc chắn có phương án tối ưu.
Nhận xét 1.1:
Định lí 1.1 chỉ đúng cho bài toán quy hoạch tuyến tính, định lí không
còn đúng khi hàm mục tiêu hoặc một trong các ràng buộc không còn

inf
x∈D
f(x) = 0 (xem Hình 1.1).
8
9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ví dụ 1.4
Xét bài toán
min{f(x) =
1
1 + x
2
: x ∈ R
2
}.
Miền chấp nhận được D ≡ R là một tập lồi đa diện, khác rỗng. Tuy
nhiên, hàm mục tiêu f(x) =
1
1+x
2
là hàm phi tuyến tính và f(x) ≥ 0
với mọi x ∈ D ( f bị chặn dưới trên D), nhưng rõ ràng bài toán này
cũng không có phương án tối ưu, mặc dù inf
x∈D
f(x) = 0 (xem Hình
1.2).
Định lí 1.2:
Nếu x
0
là một phương án tối ưu của bài toán quy hoạch tuyến tính
(dạng bất kì) và nếu x

2
∈ D thì x = x
1
= x
2
Định lí 1.3:
Để một lời giải chấp nhận được ¯x = {¯x
1
, ¯x
2
, , ¯x
n
} của quy hoạch
tuyến tính chính tắc là lời giải cơ sở thì điều kiện cần và đủ là các
véc tơ cột A
j
của ma trận A ứng với các thành phần ¯x
j
> 0 là độc lập
9
10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
tuyến tính.
Từ định lí 1.3 ta dễ dàng suy ra các hệ quả sau:
Hệ Quả 1.1:
Số phương án cực biên của bài toán quy hoạch tuyến tính chính tắc
là hữu hạn.
Hệ Quả 1.2:
Số thành phần dương trong mỗi phương án cực biên của bài toán
quy hoạch tuyến tính dạng chính tắc tối đa bằng m (m là số hàng của
ma trận A)

T
y : A
T
y ≤ c, y ≥ 0}
(A
T
là ma trận chuyển vị của A ) A
T
y ≤ c còn viết dưới dạng
s = c − A
T
y ≥ 0
Ví dụ 1.5
Đối ngẫu của bài toán cho ở ví dụ 1.1 ( dạng chuẩn) là bài toán
g(y) = 5y
1
+ 4y
2
→ max
với điều kiện
y
1
+ 3y
2
≤ 3,
2y
1
+ y
2
≤ 2,

2
+ y
3
≤ 1,
−y
1
+ y
2
+ y
3
≤ 3,
y
1
− y
2
+ y
3
≤ 2.
1.2.2 Định lí đối ngẫu
Các kết quả dưới đây đúng cho mọi cặp bài toán đối ngẫu (P)và
(Q) dạng bất kì.
Định lí 1.6.( Đối ngẫu yếu)
Nếu x là một phương án của bài toán gốc (P) và y là một phương
án của bài toán đối ngẫu (Q) thì
f(x) = c
1
x
1
+ c
2

là một phương án của bài toán gốc, y
∗
là một phương án
12
13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
của bài toán đối ngẫu và f(x∗) = g(y∗) thì x
∗
là phương án tối ưu của
bài toán gốc và y
∗
là phương án tối ưu của bài toán đối ngẫu.
Định lí 1.7 (Đối ngẫu mạnh):
Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của
nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau.
Định lí 1.8 (Đối ngẫu cơ bản):
Đối với mỗi cặp quy hoạch đối ngẫu nhau chỉ có thể xảy ra 1 trong
3 khả năng sau đây:
a) Cả 2 quy hoạch đều có phương án.
b) Cả 2 quy hoạch đều có phương án. Khi đó cả 2 quy hoạch đều
có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng
nhau.
c) Một quy hoạch có phương án và quy hoạch kia không có phương
án. Khi đó quy hoạch có phương án sẽ không có phương án tối ưu và
hàm mục tiêu của nó không giới nội trong miền ràng buộc.
Quan hệ giữa cặp quy hoạch đối ngẫu còn thể hiện ở sự kiện sau
Định lí 1.9 (Định lí độ lệch bù)
Mỗi cặp phương án x, y của 2 quy hoạch đối ngẫu (P) và (Q) là
những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ
thức:
y

14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
a) Nếu QHTT chính tắc có phương án tối ưu thì cũng có phương án
cực biên tối ưu, nghĩa là có ít nhất 1 đỉnh của miền ràng buộc là lời
giải của bài toán
b) Mỗi điểm cực biên địa phương của hàm tuyến tính (cũng là hàm
lồi) trên một tập hợp lồi là một điểm cực tiểu tuyệt đối.
1.3.1 Thuật toán đơn hình gốc
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 quy 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 quy hoạch tuyến tính chính tắc (m ràng buộc đẳng thức, n biến):
min{c
T
x : Ax =, x ≥ 0} với A là ma trận cấp m × n (A
j
∈ R
m
là cột
j của A), b ∈ R
m
, c, x ∈ R
n
.
Giả thiết: m ≤ n (m > n bài toán có thể vô nghiệm) và rank(A) = m
Bài toán quy hoạch tuyến tính được gọi là không suy biến nếu tất
cả các phương án cực biên của nó đều không suy biến, tức là đều có
m thành phần dương. Bài toán được gọi là suy biến nếu nó có dù chỉ
là một phương án cực biên suy biến ( số thành phần dương nhỏ hơn m).
Xuất phát từ một phương án cực biên (đỉnh ) không suy biến. Chẳng

B
= {c
j
: j ∈ J}
14
15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
là véc tơ hệ số các biến cơ sở.
Tính
Z
k
= B
−1
A
k
là véc tơ hệ số khai triển cột A
k
theo cơ sở B( k /∈ J)
∆
k
= c
B
Z
k
− c
k
với mọi k = 1,2, ,n (∆
k
là ước lượng của biến x
k
)

b, x
N
= 0 là phương án tối ưu ( Định lí 1.9): dừng quá trình giải.
Trái lại, chuyển sang bước 3.
Bước 3 ( Dấu hiệu bài toán không có phương án tối ưu)
Nếu ∆
k
> 0 và Z
rj
≤ 0 với mọi j = 1, 2, , m thì bài toán không có
phương án tối ưu ( Định kí 1.10): dừng quá trình giải. Trái lại chuyển
sang bước 4
15
16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bước 4 ( Chọn cột quay)
Chọn s = max{j : ∆
j
 0} Chuyển sang bước 5
Bước 5 (Chọn dòng quay)
Chọn r = min{i : (B
−1
b)
i
/z
is
, z
is
 0} làm dòng quay và z
rs
gọi là

4
= 10,
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
Quá trình giải bài toán theo thuật toán đơn hình gốc được ghi ở bảng
sau.
1.3.2 Thuật toán đơn hình đối ngẫu
Về thực chất đây là phương pháp đơn hình áp dụng vào bài toán đối
ngẫu nhưng để tìm lời giải của bài toán gốc và diễn đạt các bước tính
toán theo ngôn ngữ bài toán gốc. Phương pháp này do G.E.Lemke đề
xuất 1954.
Phương pháp đơn hình giải quy hoạch tuyến tính bắt đầu từ một
phương án ( nghiệm đúng Ax = b, x  0) mà nó chưa thỏa mãn điều
kiện tối ưu (định lí 1.9). Sau mỗi bước lặp ta sẽ tìm được phương án
mới, tốt hơn phương án cũ (giá trị hàm mục tiêu giảm xuống đối với
bài toán tìm cực tiểu) và quá trình này tiếp tục cho đến khi nhận được
phương án thỏa mãn dấu hiệu tối ưu hoặc tới khi phát hiện bài toán
không có phương án tối ưu ( hàm mục tiêu giảm vô hạn ).
17
18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phương pháp đơn hình đối ngẫu lại xuất phát từ một "giả phương
án" (nghiệm đúng Ax = b ) mà nó thỏa mãn tiêu chuẩn tối ưu nhưng
chưa thỏa mãn điều kiện x  0. Bảng đơn hình được biến đổi sao cho

Bước 1.
Lập bảng đơn hình đối ngẫu ban đầu ( xem ví dụ 1.8)
Bước 2 ( Dấu hiệu tối ưu).
Nếu B
−1
b ≥ 0 thì x
∗
= (x
B
, x
N
) với x
B
= B
−1
b, x
N
= 0 là phương
án tối ưu: dừng quá trình giải. Trái lại, chuyển sang bước 3.
Bước 3 (Chọn dòng quay)
Chọn r = min{i : (B
−1
b)
i
≺ 0} Chuyển sang bước 4.
18
19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bước 4 ( Dấu hiệu bài toán không có phương án )
Nếu Z
rj

2
≥ 12
x
1
≥ 0, x
2
≥ 0.
Dùng 2 biến phụ x
3
và x
4
để đưa bài toán về dạng chính tắc rồi đổi
dấu 2 vế các ràng buộc đẳng thức nhận được, ta đưa đến bài toán:
f(x) = 5x
1
+ 10x
2
→ min
với điều kiện
−2x
1
− 3x
2
+ x
3
= −14,
−x
1
− 4x
2

≤ 0 với mọi k = 1, 2, , n và biến đổi cơ
sở B cho tới khi x
B
= B
−1
b ≥ 0(x
∗
= (x
B
, 0) là phương án tối ưu )
hoặc tới khi phát hiện bài toán không có phương án ( có (B
−1
b)
i
< 0
và mọi z
jk
≥ 0).
Có thể tóm tắt phương pháp đơn hình trong bảng sau:
20
21Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
♣ Tóm lại, chương này đã trình bày về bài toán quy hoạch tuyến
tính và các tính chất, lý thuyết đối ngẫu trong quy hoạch tuyến tính,
phương pháp đơn hình ( thuật toán gốc và thuật toán đối ngẫu ) giải
quy hoạch tuyến tính. Có thể tìm thấy chứng minh các định lí đã nêu
ở chương này trong các tài liệu tham khảo [ 1 ], [ 3 ]. Những kiến thức
cơ sở đã giới thiệu sẽ cần đến ở các chương sau.
21
22Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Chương 2

n
.
Ta sử dụng các kí hiệu sau: a
ij
là phần tử ở hàng i và cột j của A;
ˆ
A
r
(r chỉ số dưới) là hàng thứ r của A; A
j
(j chỉ số trên) là cột thứ j của
A. Nếu I (J) là chỉ số hàng (cột) của A thì A
IJ
là ma trận con của A
gồm các phần tử ở hàng i ∈ I và cột j ∈ J. Nói riêng, A
rJ
là các phần
tử của A trên hàng r và cột j ∈ J. Phần tử thứ r của cột chỉ số I, J lí
hiệu lần lượt là I(r), J(r). Thành phần thứ j của véctơ x kí hiệu là x
j
22
23Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Giả sử
J ⊂ {1, 2, , n},
¯
J = {1, 2, , n}\J
Nếu J gồm m chỉ số và nếu hệ véctơ cột {A
j
: j ∈ J} độc lập tuyến
tính thì J được gọi là một cơ sở và B = {A

B
= {c
j
: j ∈ J} thì véc tơ hàng
y
T
= (c
B
)
T
B
−1
gọi là các nhân đơn hình ( simple multipliers). Khi đó,
y là một nghiệm cơ sở của (DP). Nghiệm cơ sở y là chấp nhận được
của (DP) nếu s = c −A
T
y ≥ 0. Một cơ sở mà nghiệm (x
B
, x
N
) là chấp
nhận được của (LP) và nghiệm ( y, s) là chấp nhận được của (DP) gọi
là một cơ sở tối ưu.
Với các kí hiệu trên, ràng buộc và hàm mục tiêu của (LP) trở thành:
Ax = b, x ≥ 0 ⇔ Bx
B
+ Nx
N
= b, x
B

B
−1
(b − Nx
N
) + (c
N
)
T
x
N
= (c
B
)
T
B
−1
b + (c
N
− (B
−1
N)
T
c
B
)
T
x
N
= (s
N

−1
b − B
−1
Nx
N
≥ 0, x
N
≥ 0
Trường hợp m = 4, n = 6 ( n - m = 2) miền chấp nhận được (feasible
region) của bài toán ( LP) rút gọn nêu trên được minh họa ở Hình 2.1
(miền có dấu chấm).
2.1.2 Ý tưởng thuật toán
Thuật toán bắt đầu từ một (ma trận) cơ sở B đối ngẫu chấp nhận
được(cách tìm B sẽ nói sau), nghĩa là (y, s) xác định như trên là một
nghiệm cơ sở chấp nhận được của (DP). Gọi J là cột chỉ số các véc tơ
cột của B,
¯
J = {1, 2, , n}\J. Lần lượt kí hiệu các nghiệm của (LP)
và (DP) tương ứng với phân hoạch cơ sở (B, N) là (x
B
, x
N
) và (y, s)
với x
B
= B
−1
b, x
N
= 0 và y