PHƯƠNG PHÁP ĐƠN HÌNH

CÁC VÍ DỤ


V. PHƯƠNG PHÁP ĐƠN HÌNH
 Xét bài toán f (X) = CX → min
AX = B

X ≥ 0
 Trong đó ma trận A cấp m × n, rankA = m
 Ta có các vectơ cột A j ∈ ¡ m . Trường hợp X là phương
án cực biên, ta có { A j / j ∈ J(X)} độc lập tuyến tính.
 Khi đó | J(X) |≤ m
 Nếu |J(X)| < m ta nói X là phương án cực biên suy biến.


Nếu |J(X)| = m ta nói X là phương án cực biên không suy
biến.


PHƯƠNG PHÁP ĐƠN HÌNH
 Ta xét bài toán min dạng chính tắc với các giả thiết đã

nêu ở trên, và Xo là phương án cực biên không suy
biến của bài toán.
 Ta có

{A

/ j ∈ J(X)}

f (X) = f (X 0 ) −

∆K x K
∑
K∉J
0


VÍ DỤ 1
f (x) = 2x1 + 2x 2 + x 3 − 6x 4 → min
 x1 + 3x 2 + x 3 = 7

x4 = 2
 x1 + x 2 +

 x j ≥ 0, j = 1, 4


VÍ DỤ 2

f (x) = 2x1 + x 2 − 8x 3 → min
−3x1 + x 2 = 2

 − x1 + x 3 = 4
 x ≥ 0, j = 1, 2,3
 j


VÍ DỤ 1
f (x) = x1 + 4x 2 − x 3 − x 4 + x 5 + 3x 6 → min

 − x1 + x 3 = 4
 x ≥ 0, j = 1, 2,3
 j


VÍ DỤ 2
f (x) = 2x1 + x 2 − 3x 3 + x 4 − x 5 − 2x 6 → min
+ x6 = 2
 x 2 + 2x 3 + 5x 4

+ 2x 6 = 1
 x1 − 2x 3 + x 4

4x 3 + x 4 + x 5 − 4x 6 = 1

 x ≥ 0, j = 1, 6
 j


VÍ DỤ 3

f (x) = − x1 + 4x 2 + 2x 3 − x 4 → max
2x1 − x 2 + x 3
=4

+ x4 = 7
3x1 + x 2

 x j ≥ 0, j = 1, 4


+ x4 = 4
 x1 − x 2
x , x , x ≥ 0 ; x ≤ 0
2
 1 2 3


VÍ DỤ 7
f (x) = x1 + 4x 2 − 2x 3 + 2x 4 → min
=4
2x1 + x 2 + x 3

+ x4 = 6
− x1 + 4x 2
x , x , x ≥ 0 ; x ∈ ¡
1
 2 3 4


VÍ DỤ 8

f (x) = x1 − 2x 2 − 3x 3 + x 4 → min
4x + x + 2x + 2x = 1
1
2
3
4

 x1 + 2x 2 + 5x 3 − 4x 4 = 6


x ≥ 0
 j
n

j

→ min
(i = 1, m )
(j = 1, n )


BÀI TOÁN ĐỐI NGẪU

g (Y ) =

m

∑b y
i =1

i

i

→ max

m
∑ aij yi ≤ c j (j = 1, n )
 i =1
( y ∈ R i = 1, m )

m



n

∑ a = ∑b
i =1

i

j =1

j

► BÀI TOÁN
 Các dịa điểm A1 , A2 , . . . , Am được
phát hết hàng và các địa điểm B1 ,
B2 , . . ., Bn được nhận đủ yêu cầu.
 Đồng thời tổng chi phí chuyên chở

là ít nhất.


BÀI TOÁN CHO DƯỚI DẠNG
BẢNG
Thu Bj
Phát Ai

b1


...
cm1


ĐỊNH NGHĨA
Ta gọi một tập hợp ô có dạng
{ (i1,j1), (i1,j2), (i2,j2),…, (ik,jk), (ik,j1)}
là một vòng nếu
2 ô liên tiếp thì cùng nằm trên một
dòng hoặc cùng nằm trên một cột.
3 ô bất kỳ thì không cùng nằm trên
một dòng và không cùng nằm trên
một cột.