ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
VŨ THỊ HỒNG
MỘT PHƯƠNG PHÁP XẤP XỈ NGOÀI
TÌM NGHIỆM CỦA HỆ BẤT PHƯƠNG TRÌNH
TUYẾN TÍNH VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2014
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
Vũ Thị Hồng
MỘT PHƯƠNG PHÁP XẤP XỈ NGOÀI
TÌM NGHIỆM CỦA HỆ BẤT PHƯƠNG TRÌNH
TUYẾN TÍNH VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 60.46.01.12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. NGUYỄN ANH TUẤN
Thái Nguyên - 2014
i
Mục lục
Bảng ký hiệu vi
Mở đầu 1
1 Một số khái niệm cơ bản và một số bài toán thực tế đưa
về bài toán tìm nghiệm chấp nhận của hệ bất phương
trình tuyến tính 4
1.1 Một số khái niệm cơ bản về tập lồi . . . . . . . . . . . . 4
1.2 Một số khái niệm cơ bản liên quan đến hàm số tuyến tính 7
1.3 Khái niệm về miền ràng buộc tuyến tính không bị chặn,
phương vô hạn chấp nhận được và hướng tăng, giảm của

3.1 Thuật toán nón xoay tìm nghiệm chấp nhận của hệ bất
phương trình tuyến tính với cơ sở xuất phát từ gốc toạ
độ là đỉnh của nón R
n
+
. . . . . . . . . . . . . . . . . . 47
3.2 Bảng lặp nón xoay tìm nghiệm chấp nhận của hệ bất
phương trình tuyến tính với cơ sở xuất phát từ gốc toạ
độ là đỉnh của nón R
n
+
. . . . . . . . . . . . . . . . . . 49
3.3 Các ví dụ minh hoạ cho thuật toán BPT . . . . . . . . 50
iii
3.4 Giải bài toán qui hoạch tuyến tính dạng chuẩn từ việc
tìm nghiệm chấp nhận của hệ bất phương trình tuyến
tính đối ngẫu bởi thuật toán nón xoay bất phương trình
(BPT) với cơ sở xuất phát từ gốc toạ độ và ví dụ minh hoạ 56
3.4.1 Đưa bài toán qui hoạch tuyến tính về bài toán tìm
nghiệm chấp nhận của hệ bất phương trình tuyến
tính với cơ sở xuất phát từ gốc toạ độ . . . . . . 56
3.4.2 Hệ bất phương trình tuyến tính đối ngẫu đối xứng 58
3.4.3 Ví dụ minh hoạ . . . . . . . . . . . . . . . . . . 59
3.5 Thuật toán nón xoay BPT giải ví dụ Klee-Minty . . . . 62
3.6 Vài nét về độ phức tạp tính toán của thuật toán BPT và
kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Tài liệu tham khảo 71
iv
Lời cảm ơn
Luận văn này được hoàn thành tại trường Đại học Khoa học, Đại

∗
trong C, với C là giao của
hữu hạn các tập lồi đóng C
i
trong không gian Hilbert. Bài toán này đã
được giải bằng thuật toán hiệu quả là phương pháp chiếu trực giao liên
tiếp lên các tập lồi đóng và trong trường hợp riêng khi tất cả các C
i
đều là các nửa không gian Affine trong R
n
thì ta thu được thuật toán
xấp xỉ tìm nghiệm chấp nhận của một hệ bất phương trình tuyến tính
(xem[13]).
Trong việc giải bài toán quy hoạch tuyến tính bằng thuật toán đơn
hình và các thuật toán điểm trong thì đầu tiên chúng ta đều phải giả
thiết là biết trước một điểm chấp nhận được của bài toán. Để có được
một điểm như vậy chúng ta phải đi giải một bài toán quy hoạch tuyến
tính khác hay một bài toán tương đương khác.
Chính vì vậy, luận văn này đề nghị một thuật toán trực tiếp tìm
nghiệm chấp nhận của một hệ bất phương trình tuyến tính, nói cụ thể
chính xác hơn là tìm một điểm cực biên (nếu có) của một hệ ràng buộc
ở dạng các bất phương trình tuyến tính.
Thuật toán ở đây là một cải tiến trực tiếp từ thuật toán nón xoay
tuyến tính giải bài toán quy hoạch tuyến tính dạng chuẩn trình bày
trong cuốn sách “Quy hoạch tuyến tính với phương pháp nón xoay”[1].
2
Thuật toán kết thúc sau hữu hạn bước lặp với điểm xuất phát ban đầu
của thuật toán là từ gốc tọa độ của R
n
.

Thuật toán xấp xỉ ngoài bất phương trình (BPT) tìm nghiệm chấp
nhận của hệ bất phương trình tuyến tính đề nghị trong luận văn này
được xây dựng chi tiết, các bước của thuật toán được trình bày sao cho
chúng ta có thể dễ dàng lập trình chuyển sang các chương trình trên
máy tính bằng các ngôn ngữ như Pascal, C, Java,
Luận văn này hoàn thành dựa trên cuốn sách “Quy hoạch tuyến tính
với phương pháp nón xoay” [1] và trên các sách, tài liệu có trong phần
tài liệu tham khảo.
4
Chương 1
Một số khái niệm cơ bản và một
số bài toán thực tế đưa về bài toán
tìm nghiệm chấp nhận của hệ bất
phương trình tuyến tính
Trong chương này, tôi trình bày một số khái niệm về bài toán tối ưu
tổng quát và một số mô hình bài toán thực tế, cũng như một số khái
niệm liên quan đến tập lồi đa diện, bài toán quy hoạch tuyến tính.
1.1 Một số khái niệm cơ bản về tập lồi
Định nghĩa 1.1.1. Một tập lồi mà là giao của một số hữu hạn nửa
không gian đóng gọi là tập lồi đa diện. Nói cách khác, đó 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
i
, x ≤ b
i
, i = 1, , m(a
i
∈ R
n
, b

những ví dụ cụ thể về đa diện lồi.
Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh
của nó. Tập các đỉnh của C ký hiệu là

C
. Mỗi cạnh vô hạn của một tập
lồi đa diện tương ứng với một phương cực biên của nó.
Cho tập lồi đa diện D = 0 xác định bởi hệ bất phương trình tuyến
tính (1.1). Khi đó mỗi bất phương trình (1.1) gọi là một ràng buộc của
D. Ta nói điểm x
0
∈ D thoả mãn chặt ràng buộc i nếu a
i
, x
0
 = b
i
.
Với mỗi x ∈ D ký hiệu I(x) = {i : a
i
, x = b
i
} là tập chỉ số của
những ràng buộc thoả mãn chặt tại x.
Ký hiệu I
0
= {i : a
i
, x = b
i

0

.
Hệ quả 1.1.3. Nếu D là một tập lồi đa diện xác định bởi hệ (1.1) thì:
a) Điểm x
0
∈ D là một đỉnh của D khi và chỉ khi
rank

a
i
: i ∈ I(x
0
)

= n
, nghĩa là X
0
thoả mãn chặt n ràng buộc độc lập tuyến tính của hệ (1.1).
b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) T ≤ D
là một cạnh của D thì T được xác định bởi một tập chỉ số I sao cho
rank

a
i
: i ∈ I(x
0
)

= n − 1

i
(i = 1, , p) là các đỉnh của
C.
b) Với tập lồi đa diện C không giới nội , mỗi x ∈ C có thể biểu diễn
dưới dạng một tổ hợp lồi của các đỉnh của C cộng với một tổ hợp tuyến
tính không âm của các phương cực biên của C, nghĩa là
x ∈ C ⇐⇒ x = λ
1
v
1
+ λ
2
v
2
+ + λ
p
v
p
+ µ
1
u
1
+ µ
2
u
2
+ + µ
q
u
q

nhóm thứ hai đều là các phương vô hạn của C.
Ngược lại, có thể chứng minh được rằng nếu cho trước hai nhóm hữu
hạn véctơ thì tập tất cả các điểm có thể biểu diễn như trên xác định
một tập lồi đa diện.
1.2 Một số khái niệm cơ bản liên quan đến hàm
số tuyến tính
Hàm tuyến tính là một hàm gần lồi - gần lõm và không bị chặn trên
R
n
([1]). Do đó các kết quả lý thuyết cũng như phương pháp tìm cực
tiểu đối với hàm gần lồi - gần lõm đưa ra trong sách “Quy hoạch gần
lồi-gần lõm ứng dụng vào quy hoạch tuyến tính” ([1]) có thể áp dụng
đối với hàm tuyến tính. Chính vì vậy, trước khi trình bày bài toán quy
hoạch tuyến tính dạng chuẩn và thuật toán nón xoay giải nó, chúng ta
nhắc lại một số khái niệm, định nghĩa, các định lý, hệ quả và các tính
chất cơ bản của hàm gần lồi - gần lõm đã trình bày trong sách “Quy
hoạch gần lồi - gần lõm ứng dụng vào quy hoạch tuyến tính” ([1]). Việc
chứng minh các định lý, hệ quả và các tính chất này, chúng ta có thể
tìm thấy trong cuốn sách nói trên.
Định nghĩa 1.2.1. Hàm f : R
n
→ R
l
là một hàm tựa lõm (quasi -
8
concave) nếu ∀x, y ∈ R
n
và ∀α ∈ [0, 1] ta luôn có:
f(αx + (1 − α)y) ≥ min{f(x), f(y)}
Định nghĩa 1.2.2. Hàm f : R

là một hàm gần lồi - gần lõm
(almost - convex and almost - concave) nếu nó vừa là một hàm gần lồi
- vừa là một hàm gần lõm.
Từ các định nghĩa trên ta suy ra một số tính chất sau của hàm vừa
tựa lồi vừa tựa lõm:
Tính chất 1.2.6. min{f(x), f(y)} ≥ f(αx+(1−α)y) ≤ max{f(x), f(y)},
∀x, y ∈ R
n
và ∀α ∈ [0, 1].
Tính chất 1.2.7. Nếu f(x) = f(y) thì f(x) = f(αx+(1−α)y) = f(y),
∀α ∈ [0, 1].
Nếu f là một hàm gần lồi - gần lõm thì nó sẽ thoả mãn các tính chất:
Tính chất 1.2.8. Nếu f(x) = f(y) thì f(x) = f(αx+(1−α)y) = f(y),
∀α ∈ R
l
.
9
Tính chất 1.2.9. Nếu f(x) = f(y) thì
min{f(x), f(y)} < f(αx + (1 − α)y) < max{f(x), f(y)},
∀x, y ∈ R
n
và ∀α ∈ (0, 1).
Ta có thể chứng minh được rằng nếu f là một hàm gần lồi thì cực
tiểu địa phương sẽ là cực tiểu toàn cục.
Các định lý sau đây là cơ sở lý luận cho việc xây dựng các thuật toán
sau này.
Định lý 1.2.10. Nếu f là một hàm gần lồi - tựa lõm, và f(x) ≤ f(y)
∀x = y, thì f(x) ≤ f(αx + (1 − α)y), ∀α ≥ 0.
Định lý này cho ta kết luận rằng hàm f gần lồi - tựa lõm và ∀x = y
mà f(x) ≤ f(y) thì x là điểm cực tiểu của f trên tia x + α(y − x)

z
N
) ≤ max{f(z
1
), , f(z
N
)}
∀α
i
∈ [0, 1],
N

i=1
α
i
= 1, i = 1, 2 , N
10
1.3 Khái niệm về miền ràng buộc tuyến tính không
bị chặn, phương vô hạn chấp nhận được và
hướng tăng, giảm của hàm gần lồi - gần lõm
Ta gọi P := {x ∈ R
n
:

A
i
, x

+ b
i

với X :=
(x
1
, x
2
, , x
n
), Y := (y
1
, y
2
, , y
n
)
Định nghĩa 1.3.1. Miền ràng buộc tuyến tính P được gọi là không bị
chặn nếu nó tồn tại một điểm chấp nhận x
0
thuộc P và một điểm z = 0
sao cho x
0
+ αz ∈ P , ∀α ≥ 0, khi đó điểm z được gọi là phương vô hạn
chấp nhận của P tại x
0
. Tập hợp các điểm x = x
0
+ αz, ∀α ≥ 0 gọi là
tia vô hạn chấp nhận được của P.
Từ định nghĩa này chúng ta dễ dàng chứng minh được các tính chất
sau:
Tính chất 1.3.2. z = O là một phương vô hạn chấp nhận được tại

0
) > f(x
0
+ αz) ∀α > 0, hay ta nói f giảm theo
hướng z từ x
0
.
3. Điểm z = 0 được gọi là một hướng không đổi của f nếu f(x
0
) =
f(x
0
+ αz) ∀α ∈ R
l
.
Từ các định nghĩa trên ta suy ra một vài tính chất sau:
Định lý 1.3.5. Nếu tồn tại α
1
> 0 mà f(x) < f(x + α
1
z) thì z là một
hướng tăng từ x của hàm gần lồi - gần lõm f.
Hệ quả 1.3.6. Nếu tồn tại f(x) < f(x + z) thì z là một hướng tăng từ
x của hàm gần lồi - gần lõm f.
Định lý 1.3.7. Nếu tồn tại α
1
> 0 mà f(x) > f(x + α
1
z) thì z là một
hướng giảm từ x của hàm gần lồi - gần lõm f.

x thuộc R
n
. Do đó ta gọi z là một hướng không giảm của hàm f. Từ
Định lý 1.3.10 ta dễ dàng chứng minh được hệ quả sau:
Hệ quả 1.3.11. f : R
n
→ R
l
là một hàm gần lồi - gần lõm, nếuf(x
0
) >
f(x
0
+ z) thì z là một hướng giảm của hàm f, ∀x ∈ R
n
, tức là f(x) >
12
f(x + αz), ∀α > 0, ∀x ∈ R
n
. Và ta gọi z là một hướng giảm của hàm
f.
Hệ quả 1.3.12. f : R
n
→ R
l
là một hàm gần lồi - gần lõm, z = 0 là
một hướng tăng của hàm f, khi và chỉ khi f(0) > f(αz), ∀α > 0.
Hệ quả 1.3.13. f : R
n
→ R

→ R
l
là một hàm gần lồi - gần lõm, nếu z = 0
và f(x
0
) = f(x
0
+ z) tức z là một hướng không đổi của hàm f tại x
0
thì
z là một hướng không đổi của hàm f tại mọi điểm x thuộc R
n
, tức là
f(x) = f(x + αz), ∀α ∈ R
l
, ∀x ∈ R
n
. Và ta nói z là một hướng không
đổi của hàm f
Hệ quả 1.3.17. f : R
n
→ R
l
là một hàm gần lồi - gần lõm, nếu z = 0 là
một hướng không đổi của hàm f, khi và chỉ khi f(0) = f(αz), ∀α ∈ R
l
và α = 0.
Từ Tính chất 1.3.3 và Hệ quả 1.3.16 ta có thể chứng minh dễ dàng
hệ quả sau:
13

j
là số đồ vật loại j sẽ chất vào túi. Ta có bài toán sau :
n

j=1
c
j
x
j
→ max
n

j=1
a
j
x
j
≤ b
x
j
≥ 0, x
j
: nguyên, j = 1, 2, , n
Đây là bài toán quy hoạch nguyên.
14
1.4.2 Bài toán lập kế hoạch sản xuất (Cực đại tổng lãi suất )
Bài toán lập kế hoạch sản xuất tối ưu được phát biểu như sau:
Giả sử một xí nghiệp sản xuất n loại sản phẩm và sử dụng m loại
nguyên liệu khác nhau. Ta đưa vào các kí hiệu sau:
x

ij
x
j
≤ b
i
(i = 1, 2, , n)
x
j
≥ 0, j = 1, 2, , n
1.4.3 Bài toán mua (thuê) máy bay tối ưu
Để mở rộng hoạt động, hãng hàng không dự định mua (thuê) K loại
máy bay (B777, B767, A321, A330, A320, AT7, ) ta gọi tương ứng là
loại máy bay k(k = 1, 2, . . . , K). máy bay loại k có giá mua (thuê) là c
k
và có thời gian sử dụng là T
k
năm. Hãng đự định mua (thuê) tối đa là
N máy bay trong các loại máy bay trên với số vốn đầu tư hiện có là V ,
Bài toán cần giải quyết là hãng hàng không nên mua (thuê) bao nhiêu
máy bay mỗi loại để tổng thời gian sử dụng là nhiều nhất?
15
Ta gọi x
k
là số lượng máy bay loại k cần mua (thuê), khi đó mô hình
bài toán đặt ra là:
M =
K

k=1
T

Người ta thường xét bài toán quy hoạch tuyến tính dưới hai dạng
sau:
- Dạng chuẩn:
n

j=1
c
j
x
j
→ max,
n

j=1
a
ij
x
j
≤ b
i
, i = 1, , m,
x
j
≥ 0, j = 1, , n.
16
- Dạng chính tắc:
n

j=1
c

i
,
Có thể đưa về ràng buộc:
−
n

j=1
a
ij
x
j
≤ −b
i
,
bằng cách nhân hai vế với (-1) và viết lại:
n

j=1
a

ij
x
j
≤ b

i
,
2. Một ràng buộc đẳng thức:
n


biến không âm bằng cách đặt:
x
j
= x
+
j
− x
j
−
với x
+
j
≥ 0, x
+
j
≤ 0,
4. Một ràng buộc bất đẳng thức:
n

j=1
a
ij
x
j
≤ b
i
,
Có thể đưa về ràng buộc đẳng thức bằng cách đưa vào biến phụ
y
i