Bai 3 Chuong 1

Bài 3. Tính chất của tập phương án 3.1 Tập hợp lồi 3.2 Tính chất của tập phương án 3.3 Phương án của bài toán dạng chính tắc

1

3.1.a Tổ hợp lồi 1

2

Cho x , x ,  , x

m

n

là m điểm trong kh.gian  ,

Điểm x được gọi là một tổ hợp lồi của các điểm này nếu tồn tại một bộ số không âm  1 ,  2 ,  ,  m  0 thoả mãn hai điều kiện

1   2     m  1 x  1x1  2 x 2    m x m

2

Ví dụ 2  Cho x=(0,0), y=(3,6 )là hai điểm trong , z=(1,2)thì

2 1 2 1 z  (1,2)  (0,0)  (3,6)  x  y 3 3 3 3

Vậy z là một tổ hợp lồi của x và y, các hệ số không âm

1  2 / 3, 2  1/ 3

3

Nhận xét i) Tập hợp tất cả các tổ hợp lồi của hai điểm x và y là một đoạn thẳng D nối x và y. Dz |z  x (1)y, 0,1

ii) Tập tất cả các tổ hợp lồi của 3 điểm A, B, C không thẳng hàng trong không gian tạo thành miền trong của tam giác ABC. iii) Tập tất cả các tổ hợp lồi của 4 điểm A, B, C, D trong không gian tạo thành phần trong của tứ diện ABCD. 4

2.3.b Tập hợp lồi n C  Tập hợp đ.g.là một tập lồi nếu:

mọi t.h.lồi của 2 điểm bất kỳ x , y  C cũng phải thuộc C.

5

Ví dụ i) Trong mặt phẳng, các tập hợp sau là tập lồi: đoạn thẳng, tia, đường thẳng, nửa mặt phẳng, tam giác, tứ giác lồi, đa giác lồi, hình tròn, hình elíp,... ii) Trong mặt phẳng, các tập sau không phải là các tập lồi: tập có 2 điểm, tứ giác lõm, hình vành khăn, hình trăng khuyết, sao vàng năm cách, … Quy ước: tập rỗng và tập 1 phần tử là tập lồi.

6

Mệnh đề Giao của của các tập lồi là tập lồi. C  AB

7

Một số tính chất i) Tập hợp tất cả các tổ hợp lồi của m điểm cho trước x1 , x 2 , , x m là một tập lồi, gọi tập lồi này là đa diện lồi

sinh bởi m điểm đã cho. 1 2 k x , x ,  , x ii) Nếu C là tập lồi thì mọi tổ hợp lồi của

tuỳ ý trong C cũng phải thuộc C.

8

2.3.c) Điểm cực biên của một tập lồi 0 x Cho C là một tập lồi, điểm trong C đ.g.là điểm cực

1 2 x biên của C nếu: không tồn tại 2 điểm phân biệt , x C

0

1

sao cho với 0    1 thoả mãn x   x  (1   )x

9

2

Ví dụ. Điểm O=(0,0) là điểm cực biên của Oxy  (x, y) : x  0, y  0

10

Chú ý: Phân biệt điểm biên và cực biên i) Điểm cực biên là điểm biên, ngược lại không đúng ii) Ví dụ về tập lồi có điểm biên đồng thời là điểm cực biên iii) Ví dụ về tập lồi có biên nhưng không có điểm cực biên iv) Trong đa diện lồi, các đỉnh của nó là các điểm cực biên, còn các điểm khác không phải là cực biên.

11

3.2.b Tính chất của tập phương án Ta có thể chỉ ra được tập các điểm thoả mãn phương trình và bất phương trình sau đây là lồi

a1x1  a2 x2  ...  anxn  b a1x1  a2 x2  ...  anxn  b Mệnh đề. Tập các phương án D của bài toán quy hoạch tuyến tính là một tập lồi Kiểm tra tính lồi của D trong các bài toán trước?

12

3.2.c) Tính chất của tập các phương án tối ưu Mệnh đề. Tập tất cả các phương án tối ưu là một tập lồi. Nhận xét. tập các phương án tối ưu của bài toán quy hoạch tuyến tính hoặc là bằng  hoặc là có duy nhất 1 điểm hoặc là có vô số.

13

3.3 Phương án của bài toán dạng chính tắc

 A1x1  A2 x2  ...  Anxn  b  x j  0, j  1, n giả thiết

m  rank ( A ) 3.3.a) Điều kiện cần và đủ để một phương án là cực biên 3.3.b) Cách tìm phương án cực biên

14

hệ véc tơ liên kết t

Cho x  D là một phương án, x   x1,x2 ,..., xn , giả sử x có k toạ độ dương là

xj1  0,xj2  0,..., xjk  0 Có hệ k véc tơ cột trong ma trận A tương ứng với các toạ độ dương của x là



j1

j2

H( x)  A , A ,..., A

jk



Ta sẽ gọi H(x) là hệ véc tơ cột liên kết với x (ví dụ?) 15

3.3.a) Điều kiện cần và đủ để một phương án là cực biên Định lý 1 Điểm x là điểm cực biên của tập phương án khi và chỉ khi hệ véc tơ liên kết H(x) độc lập tuyến tính. Ví dụ. Kiểm tra các điểm x=(2,2,0), y=(1,1,2) và z=(0,4,0) xem có là điểm cực biên của miền ràng buộc

 x1  x 2  x 3  4  0  x1  x 2 x ,x ,x 0  1 2 3 16

Hệ quả i) Số phương án cực biên của bài toán quy hoạch tuyến tính dạng chính tắc là hữu hạn ii) Số thành phần dương của một phương án cực biên của bài toán chính tắc luôn ≤ rank(A)

17

Cực biên suy biến

 Phương án cực biên được gọi là không suy biến nếu số thành phần dương của nó bằng rank( A) .

 Ngược lại, nếu số thành phần dương ít hơn rank( A ) thì sẽ được gọi là suy biến.

Ví dụ. Kiểm tra u=(0,0,4) xem có là cực biên suy biến của miền ràng buộc trong ví dụ trên hay không?

18

Cơ sở của phương án cực biên. Giả sử x là phương án cực biên và có hệ liên kết



H(x)  Aj1 , Aj2 ,..., Ajk



Nếu k<m thì ta luôn có thể bổ sung m-k véc tơ cột còn lại m  để H(x) thành một cơ sở của



j1

j2

jm

H(x)  A , A ,..., A



Khi đó ta gọi H(x) là cơ sở của phương án cực biên x.

J 

 j1 , .. . , j m  19

Ví dụ. Hãy tìm một cơ sở của cực biên u=(0,0,4) trong ví dụ trên

 x1  x 2  x 3  4  0  x1  x 2 x ,x ,x 0  1 2 3

20

3.3.b) Cách tìm phương án cực biên Bước 1. Từ hệ n véc tơ





A 1 , A 2 , ..., A n lấy ra tất cả các

hệ véc tơ con độc lập tuyến tính. Bước 2. Khai triển véc tơ b qua các hệ con độc lập tuyến tính vừa nhận được. Bước 3. Các hệ số trong khai triển nói trên đều không âm thì nó là phương án cực biên.

21

Ví dụ. Tìm tất cả các phương án cực biên của bài toán dạng chính tắc có miền ràng buộc

x1 x2 x3  1   1 x1 2x2 x x3  0  1 x2

22

Hai định lý về phương án cực biên

f ( x)  ct x  min  Ax  b   x0

Định lý 2. Nếu tập phương án D của bài toán chính tắc mà khác  thì nó sẽ có ít nhất một phương án cực biên. Định lý 3. Nếu bài toán dạng chính tắc có phương án tối ưu thì sẽ có một phương án tối ưu là phương án cực biên.

23

3.4 Phương án tối ưu của bài toán tổng quát Định lý 4. Nếu tập phương án D khác rỗng và là đa diện lồi thì nó sẽ có một phương án tối ưu là cực biên. Định lý 5. Điều kiện cần và đủ để bài toán quy hoạch tuyến tính tổng quát có phương án tối ưu là hàm mục tiêu bị chặn trên tập phương án.

24

Ví dụ. Cho bài toán quy hoạch tuyến tính dạng chính tắc f ( x)  3x1  4 x2  3x3  x4  8 x5  4 x6  min

 2 x1     x1  x1

x2 2 x2 x2

 x3  x3 x3

 x4 3 x4 x4

25

2 x5 2 x5 5 x5 x5

 x6  x6  x6 x6

2  2 5 0