tailieunhanh - 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ủa bài toán Quy hoạch tuyến tính là một tập lồ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. | 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ử . Điểm được gọi là tổ hợp lồi của các điểm nếu tồn tại 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, 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. Vì ta có trọng tâm G(5/3, 7/3). b) Định nghĩa tập lồi: Tập được gọi là tập lồi, nếu 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ọn trong L. Ví dụ: Trong mặt phẳng, đoạn thẳng, đường thẳng, tia, toàn bộ mặt phẳng, nửa mặ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ên của tập lồi L, nếu: Ví dụ 1:Trong R, cho đoạn [1, 4]. Hai điểm 1; 4 là hai điểm cực biên. Ta sẽ chứng minh x=y=1. Giải: Giả sử Thật vậy, từ : Dấu bằng xảy ra khi x=y=1. Ví dụ 2: Trong mặt phẳng Oxy ta xét tam giá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ạnh OA, AB, BC lần lượt là: Miề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: Chẳng hạn chứng minh điểm B(4,1) là điểm cực biên Trong đó thỏa hệ phương trình ở trên. Từ trên ta có: Có thể chứng minh được 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ập lồ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ạch tuyế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: Trong đó A là ma trận cấp và a) Định nghĩa 1: Giả sử là một phương án của bài toán Quy hoạch tuyến . | 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ử . Điểm được gọi là tổ hợp lồi của các điểm nếu tồn tại 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, 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. Vì ta có trọng tâm G(5/3, 7/3). b) Định nghĩa tập lồi: Tập được gọi là tập lồi, nếu 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ọn trong L. Ví dụ: Trong mặt phẳng, đoạn thẳng, đường thẳng, tia, toàn bộ mặt phẳng, nửa mặ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ên của tập lồi L, nếu: Ví dụ 1:Trong R, cho đoạn [1, 4]. Hai điểm 1; 4 là hai
đang nạp các trang xem trước
