CÁC MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU - CHƯƠNG 4

GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU BẰNG PHƯƠNG PHÁP THOẢ DỤNG MỜ 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. Phát biểu mô hìnhTrong các bài toán kĩ thuật, công nghệ, quản lý, kinh tế nông nghiệp v.v... nảy sinh từ thực tế, chúng ta thường phải xem xét để tối ưu hoá đồng thời một lúc nhiều mục tiêu. Các mục tiêu này thường là khác nhau về thứ nguyên, tức là chúng được đo bởi các đơn vị khác nhau. Những tình huống như vậy tạo ra các bài toán tối ưu đa mục...
Nội dung trích xuất từ tài liệu:
CÁC MÔ HÌNH VÀ PHẦN MỀM TỐI ƯU - CHƯƠNG 4Chương IVGIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐA MỤC TIÊUBẰNG PHƯƠNG PHÁP THOẢ DỤNG MỜ1. CÁC KHÁI NIỆM CƠ BẢN1.1. Phát biểu mô hình Trong các bài toán kĩ thuật, công nghệ, quản lý, kinh tế nông nghiệp v.v... nảysinh từ thực tế, chúng ta thường phải xem xét để tối ưu hoá đồng thời một lúc nhiềumục tiêu. Các mục tiêu này thường là khác nhau về thứ nguyên, tức là chúng được đobởi các đơn vị khác nhau. Những tình huống như vậy tạo ra các bài toán tối ưu đa mụctiêu. Như vậy, chúng ta cần phải tối ưu hoá (cực đại hoá hoặc cực tiểu hoá tuỳ theotình huống thực tế) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả cácmục tiêu đã đặt ra. Bài toán tối ưu đa mục tiêu mà trong đó miền ràng buộc D là tập lồi đa diện vàcác mục tiêu zi = zi(x), với i = 1, 2,…, p, là các hàm tuyến tính xác định trên D, đượcgọi là BTQHTT đa mục tiêu. Với mục đích tìm hiểu bước đầu, BTQHTT đa mục tiêu (BTQHTT đa mụctiêu) được phát biểu như sau (Bài toán 1): Max Cx với ràng buộc x ∈ D, trong đó: C là ma trận cấp p × n và D = {x ∈R : Ax ≤ b} với A là ma trận cấp m × n và b ∈ Rm. n Các hàng của ma trận C là các véc tơ gradient c1, c2, …, cp của các hàm mụctiêu z1 = c1Tx , z2 = c2Tx , …, zp = cpTx. V í d ụ: Giải BTQHTT hai mục tiêu. z1 = 8x1+ 6x2 → Max z2 = x1 + 3x2 → Max với các ràng buộc: 4x1 + 2x2 ≤ 60 (D) 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. Ta có thể viết bài toán này dưới dạng ma trận như sau: Max Cx với ràng buộcx ∈ D = {x∈ R2 : Ax ≤ b}, trong đó x = (x1, x2)T, b = (60, 48)T, còn ⎡8 6⎤ ⎡ 4 2⎤ C= ⎢ , A= ⎢ . 3⎥ 2 4⎥ ⎣1 ⎦ ⎣ ⎦ Có thể nói, BTQHTT đa mục tiêu là BTQHTT mà trong đó chúng ta phải tốiưu hoá cùng một lúc nhiều mục tiêu. Tuy nhiên, các mục tiêu này thường đối chọicạnh tranh với nhau. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi 52một số mục tiêu khác. Vì vậy việc giải các bài toán tối ưu đa mục tiêu, tức là tìm ramột phương án khả thi tốt nhất theo một nghĩa nào đó, thực chất chính là một bài toánra quyết định.1.2. Phương án tối ưu Pareto Khái niệm then chốt trong tối ưu hoá đa mục tiêu là khái niệm phương án tối ưuPareto. Xét Bài toán 1 , chúng ta cần biết các định nghĩa và định lý sau đây. Định nghĩa 1 Một phương án tối ưu Pareto x* có tính chất sau đây: − Trước hết nó phải thuộc vào miền các phương án khả thi của bài toán, tức làphải thoả mãn tất cả các ràng buộc: x* ∈ D. − Xét phương án khả thi x ∈ D, x ≠ x*. Nếu tồn tại tại một chỉ số i ∈ {1, 2, …,p} sao cho zi(x) > zi(x*) thì tồn tại j ∈ {1, 2, …, p}, j ≠ i, sao cho zj(x) < zj(x*). Nói một cách khác, không tồn tại một phương án khả thi nào x ∈ D có thể trội *hơn x trên tổng thể tất cả các mục tiêu. Định nghĩa 2 Một phương án tối ưu Pareto yếu x* có tính chất sau đây: − Trước hết nó phải thuộc vào miền các phương án khả thi của bài toán, tức làphải thoả mãn tất cả các ràng buộc: x* ∈ D. − Xét một phương án khả thi x ∈ D, x ≠ x*. Nếu tồn tại tại một chỉ số i ∈ {1, 2,…, p} sao cho zi(x) > zi(x*) thì tồn tại j ∈ {1, 2, …, p}, j ≠ i, sao cho zj(x) ≤ zj(x*). Để nhận biết tập phương án tối ưu Pareto chúng ta cần tới các định nghĩa sau. Định nghĩa 3 Nón cảm sinh bởi các véc tơ gradient c1, c2, …, cp của các hàm mục tiêu đượcgọi là nón tiêu chuẩn (criterion cone). Để tìm tập các phương án tối ưu Pareto chúng ta có thể sử dụng tập các điểmtrội. Định nghĩa 4 Cho x ∈ D. Tập điểm trội tại x là tập D x = { x }⊕ C≥ , với C≥ = {x = (x1,x2) ∈ R2 : Cx ≥ 0, Cx ≠ 0}là nón đối cực nửa dương (semi-positive polar cone). Định lý 1: Xét Bài toán 1. Lúc đó: x ∈ D là phương án tối ưu Pareto khi vàchỉ khi D x ∩ D = { x }. Chứng minh. Giả sử x là phương án tối ưu Pareto và D x ∩ D ≠ { x }. Lúc đó tồn tại x ∈ ˆD x ∩ D sao cho x ≠ x và x = x + x với x ∈ C≥ . Do Cx ≥ 0, Cx ≠ 0 nên C x ≥ C x ˆ ˆ ˆvà C x ≠ C x . Điều này vô lí do x là phương án tối ưu Pareto. ˆ Ngược lại, giả sử D x ∩ D = { x }. Lúc này nếu tồn tại x ≠ x sao cho C x ≥ ˆ ˆ 53C x và C x ≠ C x thì x ∉ D. Vậy x là phương án tối ưu Pareto. ˆ ˆ Để minh hoạ ...