PHƯƠNG PHÁP HÌNH HỌC

PHƯƠNG PHÁP & VÍ DỤ


VÍ DỤ 1

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


VÍ DỤ 2

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


VÍ DỤ 3

f (x) = 3x + 2y → max
x − y ≤ 1

Cho tập hợp lồi C ⊂ ¡

n

; X0 ∈ C

X 0 được gọi là điểm cực biên của C nếu

không tồn tại X1,X2 ∈ C sao cho
X 1 ≠ X2

và

X=

1
1
X1 + X 2
2
2

 Chứng minh được rằng miền ràng buộc

(tập xác định) của một bài toán quy
hoạch tuyến tính là một tập hợp lồi.
■ Dấu hiệu của phương án cực biên và các
định lý


PHƯƠNG ÁN CỰC BIÊN