Bài 3. TÍNH CHẤT CỦA TẬP PHƯƠNG ÁN VÀ TẬP PHƯƠNG ÁN TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ppsx

Chương I

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

Bài 3. TÍNH CHẤT CỦA TẬP

PHƯƠNG ÁN VÀ TẬP PHƯƠNG ÁN

TỐI ƯU CỦA BÀI TOÁN QUY

HOẠCH TUYẾN TÍNH

1. Tập hợp lồi.

a) Khái niệm tổ hợp lồi:

Giả sử 1 2

, ,..,

m n x x x R ∈ . Điểm n

x R ∈

được gọi là tổ hợp lồi của các điểm

1 2

, ,..,

m

x x x nếu tồn tại 1 2 1 2 , ,.., 0, .. 1 m m λ λ λ λ λ λ ≥ + + + =

1 1 2 2 .. m m

x x x x = + + + λ λ λ

Ví dụ 1:Trong R, cho x1=1; x2= 4. Điểm

x=3 là tổ hợp lồi của hai điểm 1; 4.

Thật vậy, 1 2 1 2 1 2 3 .1 .4, ; 0; 1

3 3 3 3 3 3

= + ≥ + =

Ví dụ 2: Trong R2

, cho tam giác ABC, với

A(1,1); B(1,2); C(3;4). Khi đó trọng tâm G

là tổ hợp lồi của các đỉnh A, B, C.