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

a) Định lý 1: Tập hợp các phương án củabài toán Quy hoạch tuyến tính là một tậplồi.b) Định lý 2: Tập hợp các phương ántối ưu của bài toán Quy hoạch tuyếntính là một tập lồi.
Nội dung trích xuất từ tài liệu:
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ÍNHChương IBÀ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ÍNH1. Tập hợp lồi.a) Khái niệm tổ hợp lồi: nGiả sử x , x ,.., x R . xR 1 2 m nđược gọi là tổ hợp lồi iểm các điểm Đ của 1 2 m x , x ,.., x nếu tồn tạiλ 1 , λ 2 ,.., λ m 0, λ 1 + λ 2 + .. + λ m = 1 x = λ1 x1 + λ2 x2 + .. + λm xmVí dụ 1:Trong R, cho x1=1; x2= 4. Điểmx=3 là tổ hợp lồi của hai điểm 1; 4. 1 2 12 12 Thật vậy,3 = .1 + .4, ; 0; + = 1 3 3 33 33Ví dụ 2: Trong R2, cho tam giác ABC, vớiA(1,1); B(1,2); C(3;4). Khi đó trọng tâm Glà tổ hợp lồi của các đỉnh A, B, C.Vì ta có trọng tâm G(5/3, 7/3). � 7� 1 5 1 1 � , � (1,1) + (1, 2) + (3, 4) = � 3� 3 3 3 3 111 111 0; + + = 1. ,, 333 333b) Định nghĩa tập lồi: TậpL R được ngọi là tập lồi, nếu x, y � L λ x + (1 − λ ) y � L, ∀ λ ;0 � λ� 1 ∀ � Nói cách khác, tập L là tập lồi, nếuđoạn thẳng nối hai điểm trong L nằm gọntrong L.Ví dụ: Trong mặt phẳng, đoạn thẳng,đường thẳng, tia, toàn bộ mặt phẳng, nửamặt phẳng, đa giác lồi, tam giác, hình tròn,hình elip đều là các tập lồi. Trong không gian, đoạn thẳng, đường thẳng, mặt phẳng, đa diện lồi, hình cầu… là các tập lồi.c) Điểm cực biên của một tập lồi: Điểm x0 được gọi là điểm cực biêncủa tập lồi L, nếu: x0 = λ x + (1 − λ ) x , x ; x �� x0 = x = x 1 2 1 2 1 2 L 0 < λ < 1.Ví dụ 1:Trong R, cho đoạn [1, 4]. Haiđiểm 1; 4 là hai điểm cực biên. Giải: Giả sử 1 = λ x + (1 − λ ) y, x, y � 4], 0 < λ < 1. [1; Ta sẽ chứng minh x=y=1. Thật vậy, từ : x, y 1 λ ,1 − λ > 0 � λ x + (1 − λ ) y � 1 + (1 − λ )1 = 1 λ Dấu bằng xảy ra khi x=y=1.Ví dụ 2: Trong mặt phẳng Oxy ta xét tamgiác OAB, với O(0;0), A(4;1), B(1,4). Khiđó các điểm O, A, B là các điểm cực biên.Giải: Có thể thấy phương trình các cạnhOA, AB, BC lần lượt là: 4 x − y = 0, x − 4 y = 0, x + y − 5 = 0Miền trong của tam giác OAB là tập cácđiểm (x,y) thỏa hệ bất phương trình: 4x − y 0 x −4 y 0 x+y 5Chẳng hạn chứng minh điểm B(4,1) làđiểm cực biên B = λ X + (1 − λ )Y , X , Y �∆OAB, 0 < λ < 1. (4,1) = λ ( x1 , y1 ) + (1 − λ )( x2 , y2 )Trong đó ( x1 , y1 ), ( x2 , y2 ) thỏa hệ phươngtrình ở trên.trên ta có: Từ 4 = λ x1 + (1 − λ ) x2 1 = λ y1 + (1 − λ ) y2Có thể chứng minh được ( x1 , y1 ) = ( x2 , y2 ) = (4,1)Ví dụ 3: Hình đa giác lồi; đa diện lồi, thìcác đỉnh là các điểm cực biên. 2. Tính chất của bài toán Quy hoạch tuyến tính:a) Định lý 1: Tập hợp các phương án của bài toán Quy hoạch tuyến tính là một tậplồi. b) Định lý 2: Tập hợp các phương án tối ưu của bài toán Quy hoạch tuyến tính là một tập lồi.3. Tính chất của bài toán Quy hoạchtuyến tính dạng chính tắc: Xét bài toán Quy hoạch tuyến tính dạng chính tắc: f ( x) min Ax = b x 0, Trong đó A là ma trận cấpm n và x1 A + x2 A + .. + xn A = b 1 2 na) Định nghĩa 1: Giả sử x = ( x10 , x20 ,.., xn 0 ) 0là một phương án của bài toán Quy hoạchtuyến tính dạng chính tắc. Khi đó x10 A + x20 A + .. + xn 0 A = b 1 2 n x j 0 > 0 hệ véctơ { A }Ứn g với jnhững được gọi là hệ véctơ liên kết với x0.Ví dụ: Xét bài toán Quy hoạch tuyến tính f = 4 x1 − x2 − x3 min 2 x1 + x2 − x3 = 5 x1 − x2 + 4 x3 = 2 0, j = 1,3. xj trong đóTa có: x1 A1 + x2 A2 + x3 A3 = b − �� 2 � � 3 � 1� �� 2 1 5 A = ��A = � �A = � �b = �� 1 , , , − 1 � 1� 4 2 �� � � �� �1 � 7 một phương ánTa có: x = � , , 0 � là 0 �3 � 3của bài toán 5 �� 7112 và ta có . A + . A + 0. A = b = �� 3 ...