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

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.