. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Trong việc nghiên cứu các bài toán tối ưu nói chung, giải tích lồi giữ một vai
trò rất quan trọng. Nó được sử dụng làm cơ sở toán học trong việc xây dựng các
thuật toán.
Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu được nghiên cứu
trọng vẹn cả về phương diện lý thuyết lẫn thực hành, Bài toán vận tải là một dạng
đặc biệt của QHTT. Do đó chương này nhằm giới thiệu một số khái niệm và kiến
thức cơ bản về giải tích lồi và QHTT.
1.1 Một số khái niệm về giải tích lồi
1.1.1 Không gian Euclude
Một vector n chiều trên trường số thực là một bộ được sắp thứ tự gồm n số
thực x=(x
1
, x
2
, ..., x
n
). Các x
i
, i =1, ..., n gọi là các thành phần hay toạ độ của
vector. Ví dụ x=(4,5,10,20).
Hai vectơ x và y gọi là bằng nhau x=y, nếu x
i
=y
i
, ∀i =1, ..., n.
Xét hai phép toán trên các vector:
Phép cộng: x+y=(x
1
+y
1

==⇔=
∑
=
αα
Các vector x
(i)
∈R
n
, i =1, ..., m được gọi là độc lập
tuyến tính nếu:
Nếu:
∑
=
=
m
i
i
i
xx
1
)(
α
với ít nhất một α
i
≠ 0 thì x gọi là tổ hợp tuyến tính của các
x
(i)
, i =1, ..., m. Hơn nữa nếu α
i
> 0, i =1, ..., m và

(2)
, ..., e
(n)
. Ta gọi tích vô hướng của hai vector
x=(x
1
, x
2
, ..., x
n
) và y=(y
1
, y
2
, ..., y
n
), ký hiệu, <x,y>, là một số bằng.
∑
=
=><
n
i
ii
yxyx
1
,
Tích vô hướng là một dạng song tuyến tính, đối xứng, không
âm, tức là:
1. <x,y> = <y, x>. ∀x,y ∈ R
n

1
, x
2
, ..., x
n
) là một số xác định
bởi.
( ) ( )
∑
=
−=>−−<=−=
n
i
ii
yxyxyxyxyx
1
2
,,
ρ
Khoảng cách giữa hai vector x
và y là một số xác định bởi:
Không gian vector trong đó có tích vô hướng và khoảng cách như trên gọi là
không gian Euclude.
1.1.2 Tập compact
Dãy {x
(k)
}⊂R
n
k=1, 2, ... được gọi là có giới hạn x
(0)

tụ thì bao giờ cũng giới nội.
* Một tập hợp G⊂R
n
được gọi là mở nếu với mọi x∈G đều tồn tại một hình
cầu tâm x nằm gọn trong G. Một tập F⊂R
n
được gọi là đóng nếu với mọi dãy hội
tụ{x
(k)
}⊂ F ta đều có:
Fx
k
k
∈
∞→
)(
lim

Một tập chứa mọi điểm biên của nó là tập đóng.
* Tập C được gọi là tập Compact nếu từ mọi dãy vô hạn {x
(k)
} thuộc C đều có
thể trích ra một dãy con {x
(ki)
} hội tụ tới phần tử thuộc C. Tập C là Compact khi và
chỉ khi C đóng và giới nội. Tập Compact M của tập đóng C cũng đóng trong C.
Tập con đóng M của tập Compact cũng Compact.
Hàm f(x) liên tục trên tập Compact C thì sẽ đạt cực trị trên tập ấy.
1.1.3 Tập lồi
Cho hai điểm a, b ∈R

1
+ a
2
x
2
+ ... + a
n
x
n
= α trong đó a
1
, a
2
, ..., a
n
, α ∈R
* Tập hợp các điểm x=(x
1
, x
2
, ..., x
n
) ∈R
n
thoản mãn bất phương trình tuyến
tính a
1
x
1
+ a

là tập lồi đa diện.
Mệnh đề: Giao của hai tập lồi là một tập lồi.
.
...
....................
...
...
2211
22222121
11212111







≤+++
≤+++
≤+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
Hệ quả 1. Giao của một số bất kỳ tập hợp lồi là
tập lồi.
Hệ quả 2. Miền chứa nghiệm của một hệ bất phương trình tuyến tính dạng.
là một tập lồi (đa diện lồi). Một tập lồi đa diện giới nội gọi là một đa diện.

 Bài toán tổng quát.
( )
1.1max
1
→
∑
=
j
n
j
j
xc
( ) ( )
( )
3.1,...,1,0
2.1...,,1,,,
1
njx
mibxa
j
i
n
j
jij
=≥
=≥=≤
∑
=
Để nhất quán lập
luận ta xét bài toán tìm cực đại, sau đó ta xét cách chuyển bài toán tìm cực tiểu

→−=
∑
=
max
1
Thì giữ nguyên ràng buộc và đưa về bài toán Max bằng
cách
Nếu bài toán Max có phương án tối ưu là x* thì bài toán min cũng có phương
án là x* và f
min
=-

f
max
Thật vậy, vì x* là phương án tối ưu của bài toán Max nên ta có:
Dxxcxc
hayDxxcxcf
n
j
jj
n
j
jj
j
n
j
j
n
j
jj

xc
j
i
n
j
jij
n
j
jj
,...,1,0
,...,1,
max
1
1
=≥
=≤
→
∑
∑
=
=
-Dạng chính tắc:
njx
mibxa
xc
j
i
n
j
jij

j
ij
bxa −≤−
∑
=1
.''
1
ij
n
j
ij
bxa ≤
∑
=
Có thể đưa về ràng buộc bằng cách nhân hai vế
với (-1) và viết lại
ii) Một ràng buộc đẳng thức
i
n
j
jij
bxa =
∑
=1
i
n
j
jiji
n
j