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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

167
lượt xem 42
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ì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ả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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương IV 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ì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ả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 tiê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ỳ theo tì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ác mụ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, được gọ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ục tiê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ục tiê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ộc x ∈ 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ọi cạ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 52
mộ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 ra mộ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án ra 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 ưu Pareto. 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 được gọ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ểm trộ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 ≥ ˆ ˆ 53
C x và C x ≠ C x thì x ∉ D. Vậy x là phương án tối ưu Pareto. ˆ ˆ Để minh hoạ các định nghĩa 1, 3 và 4, chúng ta xét lại ví dụ đã biết. 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. c1(1,3) x2 β c2(8,6) O A(0, 12) α G B(12, 6) C(15,0) O x1 Minh hoạ hình học BTQHTT hai mục tiêu Miền các phương án khả thi D (miền giới hạn bởi tứ giác ABCD) được biểu thị trên hình I, c1(8, 6) là véc tơ gradient và hướng tăng của mục tiêu 1, còn c2(1, 3) là véc tơ gradient và hướng tăng của mục tiêu 2. Trên hình, chúng ta có thể thấy nón cảm sinh β và tập điểm trội α tại G ∈ AB. Dễ thấy, tập hợp P tất cả các phương án tối ưu Pareto bao gồm các điểm nằm trên đoạn AB với A(0, 12) và B(12, 6) 1.3. Phương pháp thoả dụng mờ giải BTQHTT đa mục tiêu Cho tới thời điểm hiện nay, hàng chục phương pháp giải BTQHTT đa mục tiêu đã được đề cập tới trong các tạp chí chuyên ngành, mà đa số chúng đều có những ứng dụng rất thành công trong nhiều lĩnh vực, như: phương pháp tham số, phương pháp nón pháp tuyến, phương pháp véc tơ cực đại, phương pháp trọng số tương tác của Chebysev, phương pháp thoả dụng mờ tương tác của Nguyễn Hải Thanh. Sau đây, chúng tôi xem xét phương pháp thoả dụng mờ tương tác cải biên, gọi vắn tắt là phương pháp thoả dụng mờ. Phương pháp này là phiên bản cải tiến của phương pháp 54
thoả dụng mờ tương tác đã được đề xuất trước đây, với một số sửa chỉnh thích hợp nhằm đưa ra không phải chỉ một phương án tối ưu Pareto thoả mãn nhất mà là một tập SP các phương án tối ưu Pareto cần xem xét. Thuật giải thoả dụng mờ giải BTQHTT đa mục tiêu a. Bước khởi tạo i) Nhập số liệu cho các hàm mục tiêu tuyến tính zi (i = 1, 2,..., p) và m điều kiện ràng buộc cho Bài toán 1. Giải BTQHTT cho từng mục tiêu zi (i = 1, 2,..., p) với miền ràng buộc D được xác định bởi m ràng buộc ban đầu để thu được các phương án tối ưu x1, x2,..., xp (nếu với một mục tiêu nào đó bài toán không cho phương án tối ưu thì cần xem xét để chỉnh sửa lại các điều kiện ràng buộc ban đầu). ii) Tính giá trị các hàm mục tiêu tại p phương án x1, x2,..., xp và lập bảng pay−off. Xác định giá trị cận trên z iB và giá trị cận dưới z iw của mục tiêu zi (i =1, 2,..., p), với z iB = zi(xi) và z iw = Min {zi(xj): j = 1, 2, …, p}. iii) Xác định các hàm thoả dụng mờ μ1(z1), μ2(z2), ..., μp(zp) cho từng mục tiêu theo công thức: z i − z iw μi (z i ) = , i = 1, 2, ..., p. z iB − z iw iv) Đặt: SP = {x1, x2,..., xp}, k :=1 và a i( k ) = z iB với i = 1, 2, ..., p. b. Các bước lặp (xét bước lặp thứ k) Bước 1: i) Xây dựng hàm thoả dụng tổ hợp từ các hàm thoả dụng trên: u = w1μ1(z1) + w 2μ2(z2) + ... + w pμp(zp) → Max Trong đó: w1, w2, ..., wp là các trọng số (phản ánh tầm quan trọng của từng hàm thoả dụng trong thành phần hàm thoả dụng tổ hợp) được người giải lựa chọn thoả mãn điều kiện: w1 + w 2 +... + w p = 1 và 0 ≤ w 1, w 2, ..., w p ≤ 1. ii) Giải BTQHTT với hàm thoả dụng tổ hợp với m ràng buộc ban đầu và p ràng buộc bổ sung zi(x) ≤ a i( k ) , i = 1, 2, ..., p, để tìm được phương án tối ưu của bước lặp thứ k là x(k) và giá trị của các hàm mục tiêu zi cũng như của các hàm thoả dụng μi(zi) (với i =1, 2, ..., p). Bước 2: i) Nếu μmin = Min {μi(zi): i = 1, 2, ..., p} bé hơn một ngưỡng t nào đó (t được lựa chọn trong đoạn [0, 1] và có thể được sửa chỉnh lại trong quá trình giải bài toán) thì phương án tìm được x(k) không được chấp nhận. Trong trường hợp trái lại, phương án x(k) được chấp nhận vào tập SP các phương án tối ưu Pareto cần xem xét nếu x(k) ∉ SP. ii) Nếu người giải bài toán còn muốn tiếp tục mở rộng tập SP thì đặt k := k + 1. 55
Nếu k > L1 hoặc số lần bước lặp liên tiếp tập SP không được mở rộng vượt quá L2 (L1 và L2 được người giải tùy chọn) thì đặt a i( k ) = ziB với i = 1, 2, ..., p và chọn ngẫu nhiên một chỉ số h ∈ {1, 2, ..., p} để đặt lại giá trị a (hk ) ∈ ( z h , z B ]. w h Quay về bước 1. iii) Nếu người giải bài toán không muốn mở rộng tập SP thì chuyển sang bước 3. Bước 3: i) Loại khỏi tập SP các phương án bị trội. ii) Kết thúc. 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. a. Bước khởi tạo i) Giải BTQHTT cho từng mục tiêu trong ví dụ trên ta có hai bài toán: z1 = 8x1 + 6x2 → Max với điều kiện ràng buộc (D) cho phương án tối ưu x1(12, 6) và Max z1 = 132; z2 = x1 + 3x2 → Max cho phương án tối ưu x2(0, 12) và Max z2 = 36. ii) Lập bảng pay−off cho các mục tiêu Phương án Xi z1 z2 X1(12, 6) 132 30 X2(0, 12) 72 36 Dựa trên thông tin của bảng pay−off, ta có z1 = 72, z1 = 132; còn z 2 = 30, W B W z B = 36. Do đó, đoạn biến thiên cần xét cho z1 là [72, 132] và cho z2 là [30, 36]. 2 iii) Thiết lập các hàm thoả dụng mờ ứng với hai mục tiêu đã cho như sau: z − zw z − 72 72 z1 z μ1 (z1 ) = 1 1 = 1 = 1− − 1,2 = B w 132 − 72 60 60 60 z1 − z1 Hàm thoả dụng mờ trên đây phụ thuộc vào z1, nên phụ thuộc vào (x1, x2). Khi có một phương án khả thi (x1, x2) ta tính được độ thoả dụng μ1 ( z1 ) đối với mục tiêu z1. Tương tự đối với z2 ta có hàm thoả dụng mờ: 56
w z 2 − 30 z 2 z2 − z2 − 5. μ 2 (z 2 ) = = = zB − z2 w 36 − 30 6 2 iv) Tập SP ban đầu là {x1, x2}. Đặt k = 1, ta có a11) = 132, a (21) = 36. ( b. Các bước lặp Bước 1: i) Lập hàm thoả dụng tổ hợp u = w1 μ1 (z1 ) + w2 μ 2 (z 2 ) , trong đó w1, w2 là các trọng số thoả mãn 0 ≤ w1, w2 ≤ 1 và w1 + w2 = 1. Chọn w1 = 0,5 và w2 = 0,5, thì có u = z z z z 0,5 ( 1 − 1,2) + 0,5 ( 2 − 5) = ( 1 + 2 ) − 3,1. 60 6 120 12 ii) Để cực đại hoá hàm thoả dụng tổ hợp, ta chỉ cần tìm Max ⎧ 1 + 2 ⎫ . Vậy z z ⎨ ⎬ ⎩120 12 ⎭ z z chúng ta cần giải bài toán: Max u = 1 + 2 với các ràng buộc (D), hay bài toán 120 12 tương đương: z = 120u/18 = x1 + 2x2 → Max, với các ràng buộc (D). Giải BTQHTT này ta sẽ có kết quả x(1) = (0, 12). Bước 2: i) Rõ ràng x(1) ≡ x2. Vậy tập SP chưa được mở rộng. ii) Nếu người giải muốn tiếp tục mở rộng tập SP thì đặt k = 2 và quay về bước 1. Quá trình giải được tiếp tục. Trong bước lặp thứ 2, đặt w1 = 0,8, w2 = 0,2, a 12) = 132 và a (22) = 36 sẽ thu ( được phương án x(2)(12, 6) ≡ x1. Do đó tập SP vẫn chưa được mở rộng. Trong bước lặp thứ 3, đặt w1 = 0,8, w2 = 0,2, a 13) = 120 và a (23) = 36 sẽ thu ( được phương án x(3) (9,6; 7,2) mà tại đó z1 = 120 và z2 = 31,2. Tập Sp lúc này là tập {x1, x2, x(3)}. Trong bước lặp thứ 4, đặt w1 = 0,2, w2 = 0,8, a 14) = 132 và a (24) = 35 sẽ thu ( được phương án x(4) (2; 11) mà tại đó z1 = 82 và z2 = 35. Tập Sp lúc này là tập {x1, x2, x(3), x(4)}. Giả sử người giải không muốn tiếp tục mở rộng tập SP thì chuyển sang bước 3. Bước 3: i) Trong các phương án thuộc tập SP không có phương án nào bị trội. ii) Kết thúc với tập SP các phương án cần xem xét. Các phương án này đều có “tính chất tối ưu Pareto” theo một nghĩa nhất định (xem các định lý 3, 4 và 5 ngay tiếp theo). Xét các BTQHTT sau đây (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 ∈ Rn: Ax ≤ b, } 57
với A là ma trận cấp m × n và b ∈ Rm. 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ục tiêu z1 = c1Tx , z2 = c2Tx , …, zp = cpTx. Bài toán 2: Giống như Bài toán 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) , i = 1, 2, ..., p, trong đó a i( k ) = ziB , với mọi i ∈ {1, 2, ..., p}, i ≠ h, còn a (hk ) ∈ ( z h , z B ). w h Định lý 2: Nếu Bài toán 1 có phương án và các BTQHTT với hàm mục tiêu zi có phương án tối ưu với mọi i = 1, 2, ..., p thì Bài toán 2 cũng có phương án. Chứng minh Miền ràng buộc D’ của Bài toán 2 được viết là D’ = D ∩ {x ∈ D: zh(x) ≤ a (hk ) }, trong đó D là miền ràng buộc của Bài toán 1. Rõ ràng D’ chứa điểm xj ∈ D (xj là phương án tối ưu của BTQHTT với miền ràng buộc D và với mục tiêu zj) sao cho z h W = zh(xj). Vậy D’ ≠ ∅. Định lý 3: Các phương án tìm được trong quy trình giải trên đây tại bước 1 của bước lặp k với 0 < w 1, w 2, ..., w p < 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) = ziB , i = 1, 2, ..., p, đều là các phương án tối ưu Pareto của Bài toán 1. Các phương án tìm được trong quy trình giải trên đây tại bước 1 của bước lặp k với 0 < w 1, w 2, ..., w p < 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) , i = 1, 2, ..., p, trong đó a i( k ) = z iB , với mọi i ∈ {1, 2, ..., p}, i ≠ h, còn a (hk ) ∈ ( z h , z B ) đều là các phương án w h tối ưu Pareto của Bài toán 2. Chứng minh Việc chứng minh không quá khó khăn. Chúng ta có thể trình bày việc chứng minh định lý 3 sử dụng ví dụ đang xét để minh hoạ. Định lý 4: Các phương án tìm được trong quy trình giải trên đây tại bước 1 của bước lặp k với 0 ≤ w 1, w 2, ..., w p ≤ 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) = ziB , i = 1, 2, ..., p, đều là các phương án tối ưu Pareto yếu của Bài toán 1. Các phương án tìm được trong quy trình giải trên đây tại bước 1 của bước lặp k với 0 ≤ w 1, w 2, ..., w p ≤ 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) , i = 1, 2, ..., p, trong đó a i( k ) = z iB , với mọi i ∈ {1, 2, ..., p}, i ≠ h, còn a (hk ) ∈ ( z h , z B ) đều là các phương án w h tối ưu Pareto yếu của Bài toán 2. Chứng minh Việc chứng minh định lý 4 là không quá khó khăn, hoàn toàn tương tự như việc chứng minh định lý 3. Định lý 5: Nếu x là phương án tối ưu Pareto của Bài toán 1 đồng thời là phương án của Bài toán 2 thì x cũng là phương án tối ưu Pareto của Bài toán 2. 58
Ngược lại, nếu x là phương án tối ưu Pareto của Bài toán 2 đồng thời zh(x) ≠ a (hk ) thì x cũng là phương án tối ưu Pareto của Bài toán 1. Chứng minh Gọi D và P theo thứ tự là tập phương án và tập phương án tối ưu Pareto của Bài toán 1, còn D’ và P’ theo thứ tự là tập phương án và tập phương án tối ưu Pareto của Bài toán 2. Giả sử x ∈ P ∩ D’ và x ∉ P’. Lúc đó tồn tại x’ ∈ D’ sao cho zi(x’) ≥ zi(x), với mọi i = 1, 2, ..., p và tồn tại ít nhất một chỉ số j ∈ {1, 2, ..., p} sao cho zj(x’) > zj(x). Do D’⊂ D và x ∈ P nên đây là điều vô lí. Vậy x ∈ P’. Ngược lại, cho x ∈ P’ với zh(x) ≠ a (hk ) và x ∉ P. Lúc đó, tồn tại x’ ∈ D sao cho zi(x’) ≥ zi(x), với mọi i = 1, 2, ..., p và tồn tại ít nhất một chỉ số j ∈ {1, 2, ..., p} sao cho zj(x’) > zj(x). Rõ ràng x’ ∉ D’ ( do giả thiết x ∈ P’) nên suy ra x’ ∈ D \ D’. Vậy zh(x’) > a (hk ) > zh(x). Mặt khác, x” = λx + (1 - λ)x’ ∈ D với mọi λ ∈ (0, 1). Dễ dàng tìm được λ ∈ (0, 1) sao cho zh(x”) = λzh(x) + (1 - λ)zh(x’) < a (hk ) . Do đó x” ∈ D’. Ta cũng có ngay: zh(x”) = λzh(x) + (1 - λ)zh(x’) ≥ zi(x), với mọi i = 1, 2, ..., p và tồn tại ít nhất một chỉ số j ∈ {1, 2, ..., p} sao cho zj(x”) > zj(x). Điều này là vô lí vì x ∈ P’. Chú ý. Theo định lý 5, các phương án tìm được trong quy trình giải trên đây tại bước 1 của bước lặp k với 0 < w 1, w 2, ..., w p < 1 với p ràng buộc bổ sung zi(x) ≤ a i( k ) , i = 1, 2, ..., p, trong đó a i( k ) = ziB , với mọi i ∈ {1, 2, ..., p}, i ≠ h, còn a (hk ) ∈ ( z h , z B ) đều w h là các phương án tối ưu Pareto của Bài toán 2 và đều là phương án tối ưu Pareto của Bài toán 1 nếu zh(x) ≠ a (hk ) . 2. GIẢI BTQHTT ĐA MỤC TIÊU BẰNG CHƯƠNG TRÌNH MÁY TÍNH MULTIOPT 2.1. 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. 59
File vào ten3.txt 222001 60 48 42 24 86 13 File ra t3.out CHUONG TRINH QUY HOACH TUYEN TINH BAI TOAN DA MUC TIEU BAI TOAN TIM CUC DAI BANG DON HINH SO BIEN :2 SO RANG BUOC : 2 MA TRAN RANG BUOC 4.00000 X1 + 2.00000 X2 < 60.00 2.00000 X1 + 4.00000 X2 < 48.00 I - Ket qua cac ham muc tieu HAM MUC TIEU 1 Z[1] = 8.00000 X1 + 6.00000 X2 *** Nghiem toi uu tim thay sau : 3 Buoc lap *** PHUONG AN TOI UU ( X[1] ) Bien Gia tri X1 = 12.00000 X2 = 6.00000 Cac bien khac bang khong CUC DAI : 132.0000000 ***** Ket thuc ham muc tieu 1 ***** HAM MUC TIEU 2 Z[2] = 1.00000 X1 + 3.00000 X2 *** Nghiem toi uu tim thay sau : 2 Buoc lap *** PHUONG AN TOI UU ( X[2] ) Bien Gia tri X2 = 12.00000 X3 = 36.00000 Cac bien khac bang khong CUC DAI : 36.0000000 ***** Ket thuc ham muc tieu 2 ***** ***** KET THUC CAC HAM MUC TIEU ***** II - Bang Pay-Off Z[1] Z[2] X[1] 132.0000000 30.0000000 X[2] 72.0000000 36.0000000 60
Gia tri Max - Min tung muc tieu MAX[1] = 132.0000000 MIN[1] = 72.0000000 MAX[2] = 36.0000000 MIN[2] = 30.0000000 III - Ket qua ham lien hop Gia tri cac trong so - lan thu 1 w[1] = 0.50000 w[2] = 0.50000 HAM MUC TIEU LIEN HOP 1 Z = 0.1500000 X1 + 0.3000000 X2 Phan le = -3.1000000 *** Nhieu loi giai *** *** Nghiem toi uu tim thay sau : 2 Buoc lap *** *** Nghiem suy bien *** PHUONG AN TOI UU LIEN HOP 1 Bien Gia tri X2 = 12.00000 X3 = 36.00000 X5 = 60.00000 X6 = 0.00000 Cac bien khac bang khong CUC DAI : 3.6000000 Gia tri cua cac ham thoa dung - Lan thu 1 Z[1] = 72.0000000 pZ[1] = 0.0000000 Z[2] = 36.0000000 pZ[2] = 1.0000000 Gia tri Max cua ham lien hop 1 : 0.5000000 ***** Ket thu ham muc tieu lien hop 1 ***** Gia tri cac trong so - lan thu 2 w[1] = 0.80000 w[2] = 0.20000 HAM MUC TIEU LIEN HOP 2 Z = 0.1400000 X1 + 0.1800000 X2 Phan le = -1.9600000 *** Nghiem toi uu tim thay sau : 3 Buoc lap *** *** Nghiem suy bien *** PHUONG AN TOI UU LIEN HOP 2 Bien Gia tri X1 = 12.00000 X2 = 6.00000 X5 = 0.00000 X6 = 6.00000 Cac bien khac bang khong CUC DAI : 2.7600000 Gia tri cua cac ham thoa dung - Lan thu 2 Z[1] = 132.0000000 pZ[1] = 1.0000000 Z[2] = 30.0000000 pZ[2] = 0.0000000 Gia tri Max cua ham lien hop 2 : 0.8000000 ***** Ket thu ham muc tieu lien hop 2 ***** Gia tri cac trong so - lan thu 3 61
w[1] = 0.80000 w[2] = 0.20000 HAM MUC TIEU LIEN HOP 3 Z = 0.1400000 X1 + 0.1800000 X2 Phan le = -1.9600000 *** Nghiem toi uu tim thay sau : 3 Buoc lap *** PHUONG AN TOI UU LIEN HOP 3 Bien Gia tri X1 = 9.60000 X2 = 7.20000 X3 = 7.20000 X6 = 4.80000 Cac bien khac bang khong CUC DAI : 2.6400000 Gia tri cua cac ham thoa dung - Lan thu 3 Z[1] = 120.0000000 pZ[1] = 0.8000000 Z[2] = 31.2000000 pZ[2] = 0.2000000 Gia tri Max cua ham lien hop 3 : 0.6800000 ***** Ket thu ham muc tieu lien hop 3 ***** Gia tri cac trong so - lan thu 4 w[1] = 0.20000 w[2] = 0.80000 HAM MUC TIEU LIEN HOP 4 Z = 0.1600000 X1 + 0.4200000 X2 Phan le = -4.2400000 *** Nghiem toi uu tim thay sau : 3 Buoc lap *** PHUONG AN TOI UU LIEN HOP 4 Bien Gia tri X1 = 2.00000 X2 = 11.00000 X3 = 30.00000 X5 = 50.00000 Cac bien khac bang khong CUC DAI : 4.9400000 So sanh 2 ve cua cac rang buoc
***** Ket thu ham muc tieu lien hop 4 ***** Tap cac phuong an toi uu sau khi giai bai toan la: X(1) X(1,1)=12.000 X(1,2)=6.000 Z(X(1)) Z(1X(1))=132.0000 Z(2X(1))= 30.0000 X(2) X(2,1)=0.000 X(2,2)=12.000 Z(X(2)) Z(1X(2))= 72.0000 Z(2X(2))= 36.0000 X(5)(Nghiem ham lien hop 3) X(5,1)=9.600 X(5,2)=7.200 Z(X(5)) Z(1X(5))=120.0000 Z(2X(5))= 31.2000 X(6)(Nghiem ham lien hop 4) X(6,1)=2.000 X(6,2)=11.000 Z(X(6)) Z(1X(6))= 82.0000 Z(2X(6))= 35.0000 *** 2.2. Bài toán quy hoạch đất xã Nhân Chính File vào A1.DAT 18 7 0 0 7 1 92.87 27.62 41.52 163.15 16.49 85.02 48.49 000000010100010000 100100000000000100 011000000000000001 000000001000000000 000000000010101000 000001100001000000 000010000000000010 72279 72279 71201 59972 59972 33875 35086 23730 15898 46312 46312 34934 33875 35086 35086 46312 46312 54623 111111111110000000 54.53 54.53 52.25 52.30 52.30 84.08 95.45 75.00 81.80 77.28 77.28 90.90 84.08 95.45 95.45 77.28 77.28 75.00 File ra A11.OUT CHUONG TRINH QUY HOACH TUYEN TINH BAI TOAN DA MUC TIEU BAI TOAN TIM CUC DAI BANG DON HINH 63
SO BIEN : 18 SO RANG BUOC : 7 MA TRAN RANG BUOC 0.00000 X1 + 0.00000 X2 + 0.00000 X3 + 0.00000 X4 + 0.00000 X5 + 0.00000 X6 + 0.00000 X7 + 1.00000 X8 + 0.00000 X9 + 1.00000 X10 + 0.00000 X11 + 0.00000 X12 + 0.00000 X13 + 1.00000 X14 + 0.00000 X15 + 0.00000 X16 + 0.00000 X17 + 0.00000 X18 = 92.87 1.00000 X1 + 0.00000 X2 + 0.00000 X3 + 1.00000 X4 + 0.00000 X5 + 0.00000 X6 + 0.00000 X7 + 0.00000 X8 + 0.00000 X9 + 0.00000 X10 + 0.00000 X11 + 0.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 1.00000 X16 + 0.00000 X17 + 0.00000 X18 = 27.62 0.00000 X1 + 1.00000 X2 + 1.00000 X3 + 0.00000 X4 + 0.00000 X5 + 0.00000 X6 + 0.00000 X7 + 0.00000 X8 + 0.00000 X9 + 0.00000 X10 + 0.00000 X11 + 0.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 0.00000 X16 + 0.00000 X17 + 1.00000 X18 = 41.52 0.00000 X1 + 0.00000 X2 + 0.00000 X3 + 0.00000 X4 + 0.00000 X5 + 0.00000 X6 + 0.00000 X7 + 0.00000 X8 + 1.00000 X9 + 0.00000 X10 + 0.00000 X11 + 0.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 0.00000 X16 + 0.00000 X17 + 0.00000 X18 = 163.15 0.00000 X1 + 0.00000 X2 + 0.00000 X3 + 0.00000 X4 + 0.00000 X5 + 0.00000 X6 + 0.00000 X7 + 0.00000 X8 + 0.00000 X9 + 0.00000 X10 + 1.00000 X11 + 0.00000 X12 + 1.00000 X13 + 0.00000 X14 + 1.00000 X15 + 0.00000 X16 + 0.00000 X17 + 0.00000 X18 = 16.49 0.00000 X1 + 0.00000 X2 + 0.00000 X3 + 0.00000 X4 + 0.00000 X5 + 1.00000 X6 + 1.00000 X7 + 0.00000 X8 + 0.00000 X9 + 0.00000 X10 + 0.00000 X11 + 1.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 0.00000 X16 + 0.00000 X17 + 0.00000 X18 = 85.02 0.00000 X1 + 0.00000 X2 + 0.00000 X3 + 0.00000 X4 + 1.00000 X5 + 0.00000 X6 + 0.00000 X7 + 0.00000 X8 + 0.00000 X9 + 0.00000 X10 + 0.00000 X11 + 0.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 0.00000 X16 + 1.00000 X17 + 0.00000 X18 = 48.49 I - Ket qua cac ham muc tieu HAM MUC TIEU 1 Z[1] = 72279.00000 X1 + 72279.00000 X2 + 71201.00000 X3 + 59972.00000 X4 + 59972.00000 X5 + 33875.00000 X6 + 35086.00000 X7 + 23730.00000 X8 + 15898.00000 X9 + 46312.00000 X10 + 46312.00000 X11 + 34934.00000 X12 + 33875.00000 X13 + 35086.00000 X14 + 35086.00000 X15 + 46312.00000 X16 + 46312.00000 X17 + 54623.00000 X18 64
*** Nghiem toi uu tim thay sau : 8 Buoc lap *** PHUONG AN TOI UU ( X[1] ) Bien Gia tri X1 = 27.62000 X2 = 41.52000 X5 = 48.49000 X7 = 85.02000 X9 = 163.15000 X10 = 92.87000 X11 = 16.49000 Cac bien khac bang khong CUC DAI : 18546863.0800000 ***** Ket thuc ham muc tieu 1 ***** HAM MUC TIEU 2 Z[2] = 1.00000 X1 + 1.00000 X2 + 1.00000 X3 + 1.00000 X4 + 1.00000 X5 + 1.00000 X6 + 1.00000 X7 + 1.00000 X8 + 1.00000 X9 + 1.00000 X10 + 1.00000 X11 + 0.00000 X12 + 0.00000 X13 + 0.00000 X14 + 0.00000 X15 + 0.00000 X16 + 0.00000 X17 + 0.00000 X18 *** Nhieu loi giai *** *** Nghiem toi uu tim thay sau : 8 Buoc lap *** PHUONG AN TOI UU ( X[2] ) Bien Gia tri X1 = 27.62000 X2 = 41.52000 X5 = 48.49000 X6 = 85.02000 X8 = 92.87000 X9 = 163.15000 X11 = 16.49000 Cac bien khac bang khong CUC DAI : 475.1600000 ***** Ket thuc ham muc tieu 2 ***** HAM MUC TIEU 3 Z[3] = 54.53000 X1 + 54.53000 X2 + 52.25000 X3 + 52.30000 X4 + 52.30000 X5 + 84.08000 X6 + 95.45000 X7 + 75.00000 X8 + 81.80000 X9 + 77.28000 X10 + 77.28000 X11 + 90.90000 X12 + 84.08000 X13 + 95.45000 X14 + 95.45000 X15 + 77.28000 X16 + 77.28000 X17 + 75.00000 X18 *** Nghiem toi uu tim thay sau : 8 Buoc lap *** PHUONG AN TOI UU ( X[3] ) Bien Gia tri X7 = 85.02000 X9 = 163.15000 X14 = 92.87000 X15 = 16.49000 X16 = 27.62000 X17 = 48.49000 X18 = 41.52000 Cac bien khac bang khong CUC DAI : 40895.0218000 ***** Ket thuc ham muc tieu 3 ***** ***** KET THUC CAC HAM MUC TIEU ***** II - Bang Pay-Off Z[1] Z[2] Z[3] X[1] 18546863.0800000 475.1600000 36218.4010000 X[2] 16346713.5200000 475.1600000 35039.9800000 X[3] 15206528.6600000 248.1700000 40895.0218000 65
Gia tri Max - Min tung muc tieu MAX[1] = 18546863.0800000 MIN[1] = 15206528.6600000 MAX[2] = 475.1600000 MIN[2] = 248.1700000 MAX[3] = 40895.0218000 MIN[3] = 35039.9800000 III - Ket qua ham lien hop Gia tri cac trong so - lan thu 1 w[1] = 0.40000 w[2] = 0.20000 w[3] = 0.40000 HAM MUC TIEU LIEN HOP 1 Z = 0.0132617 X1 + 0.0132617 X2 + 0.0129769 X3 + 0.0116356 X4 + 0.0116356 X5 + 0.0106817 X6 + 0.0116035 X7 + 0.0088465 X8 + 0.0083732 X9 + 0.0117064 X10 + 0.0117064 X11 + 0.0103933 X12 + 0.0098006 X13 + 0.0107224 X14 + 0.0107224 X15 + 0.0108253 X16 + 0.0108253 X17 + 0.0116648 X18 Phan le = -4.4334534 *** Nghiem toi uu tim thay sau : 8 Buoc lap *** *** Nghiem suy bien *** PHUONG AN TOI UU LIEN HOP 1 Bien Gia tri X1 = 27.62000 X2 = 41.52000 X5 = 48.49000 X7 = 85.02000 X9 = 163.15000 X10 = 92.87000 X11 = 16.49000 X19 = 0.00002 X20 = 0.00000 X21 = 4676.62080 Cac bien khac bang khong CUC DAI : 5.1139598 Gia tri cua cac ham thoa dung - Lan thu 1 Z[1] = 18546863.0800000 pZ[1] = 1.0000000 Z[2] = 475.1600000 pZ[2] = 1.0000000 Z[3] = 36218.4010000 pZ[3] = 0.2012660 Gia tri Max cua ham lien hop 1 : 0.6805064 ***** Ket thu ham muc tieu lien hop 1 ***** Gia tri cac trong so - lan thu 2 w[1] = 0.40000 w[2] = 0.10000 w[3] = 0.50000 HAM MUC TIEU LIEN HOP 2 Z = 0.0137525 X1 + 0.0137525 X2 + 0.0134287 X3 + 0.0120883 X4 + 0.0120883 X5 + 0.0116772 X6 + 0.0127931 X7 + 0.0096869 X8 + 0.0093297 X9 + 0.0125858 X10 + 0.0125858 X11 + 0.0119458 X12 + 0.0112366 X13 + 0.0123526 X14 + 0.0123526 X15 + 0.0121452 X16 + 0.0121452 X17 + 0.0129458 X18 Phan le = -4.9225808 *** Nghiem toi uu tim thay sau : 8 Buoc lap *** PHUONG AN TOI UU LIEN HOP 2 Bien Gia tri X1 = 27.62000 X2 = 41.52000 X7 = 85.02000 X9 = 163.15000 X10 = 92.87000 X11 = 16.49000 66
X17 = 48.49000 X19 = 662373.40002 X20 = 48.49000 X21 = 3465.34060 Cac bien khac bang khong CUC DAI : 5.5259725 Gia tri cua cac ham thoa dung - Lan thu 2 Z[1] = 17884489.6800000 pZ[1] = 0.8017045 Z[2] = 426.6700000 pZ[2] = 0.7863783 Z[3] = 37429.6812000 pZ[3] = 0.4081442 Gia tri Max cua ham lien hop 2 : 0.6033917 ***** Ket thu ham muc tieu lien hop 2 ***** Gia tri cac trong so - lan thu 3 w[1] = 0.40000 w[2] = 0.10000 w[3] = 0.50000 HAM MUC TIEU LIEN HOP 3 Z = 0.0137525 X1 + 0.0137525 X2 + 0.0134287 X3 + 0.0120883 X4 + 0.0120883 X5 + 0.0116772 X6 + 0.0127931 X7 + 0.0096869 X8 + 0.0093297 X9 + 0.0125858 X10 + 0.0125858 X11 + 0.0119458 X12 + 0.0112366 X13 + 0.0123526 X14 + 0.0123526 X15 + 0.0121452 X16 + 0.0121452 X17 + 0.0129458 X18 Phan le = -4.9225808 *** Nhieu loi giai *** *** Nghiem toi uu tim thay sau : 16 Buoc lap *** PHUONG AN TOI UU LIEN HOP 3 Bien Gia tri X1 = 27.62000 X2 = 41.52000 X7 = 85.02000 X9 = 163.15000 X10 = 14.08061 X11 = 16.49000 X14 = 78.78939 X17 = 48.49000 X20 = 127.27939 X21 = 2033.73740 Cac bien khac bang khong CUC DAI : 5.5075996 Gia tri cua cac ham thoa dung - Lan thu 3 Z[1] = 17000000.0000000 pZ[1] = 0.5369137 Z[2] = 347.8806111 pZ[2] = 0.4392731 Z[3] = 38861.2843970 pZ[3] = 0.6526519 Gia tri Max cua ham lien hop 3 : 0.5850188 ***** Ket thu ham muc tieu lien hop 3 ***** Gia tri cac trong so - lan thu 4 w[1] = 0.40000 w[2] = 0.20000 w[3] = 0.40000 HAM MUC TIEU LIEN HOP 4 Z = 0.0132617 X1 + 0.0132617 X2 + 0.0129769 X3 + 0.0116356 X4 + 0.0116356 X5 + 0.0106817 X6 + 0.0116035 X7 + 0.0088465 X8 + 0.0083732 X9 + 0.0117064 X10 + 0.0117064 X11 + 0.0103933 X12 + 0.0098006 X13 + 0.0107224 X14 + 0.0107224 X15 + 0.0108253 X16 + 0.0108253 X17 + 0.0116648 X18 Phan le = -4.4334534 *** Nhieu loi giai *** *** Nghiem toi uu tim thay sau : 10 Buoc lap *** 67
PHUONG AN TOI UU LIEN HOP 4 Bien Gia tri X1 = 27.62000 X2 = 41.52000 X7 = 85.02000 X9 = 163.15000 X10 = 16.20000 X11 = 16.49000 X14 = 76.67000 X17 = 48.49000 X19 = 1523070.82000 X21 = 2072.24670 Cac bien khac bang khong CUC DAI : 4.9992199 Gia tri cua cac ham thoa dung - Lan thu 4 Z[1] = 17023792.2600000 pZ[1] = 0.5440364 Z[2] = 350.0000000 pZ[2] = 0.4486101 Z[3] = 38822.7751000 pZ[3] = 0.6460748 Gia tri Max cua ham lien hop 4 : 0.5657665 ***** Ket thu ham muc tieu lien hop 4 ***** Tap cac phuong an toi uu sau khi giai bai toan la: X(1) X(1,1)=27.620 X(1,2)=41.520 X(1,3)=0.000 X(1,4)=0.000 X(1,5)=48.490 X(1,6)=0.000 X(1,7)=85.020 X(1,8)=0.000 X(1,9)=163.150 X(1,10)=92.870 X(1,11)=16.490 X(1,12)=0.000 X(1,13)=0.000 X(1,14)=0.000 X(1,15)=0.000 X(1,16)=0.000 X(1,17)=0.000 X(1,18)=0.000 Z(X(1)) Z(1X(1))=18546863.0800 Z(2X(1))=475.1600 Z(3X(1))=36218.4010 X(3) X(3,1)=0.000 X(3,2)=0.000 X(3,3)=0.000 X(3,4)=0.000 X(3,5)=0.000 X(3,6)=0.000 X(3,7)=85.020 X(3,8)=0.000 X(3,9)=163.150 X(3,10)=0.000 X(3,11)=0.000 X(3,12)=0.000 X(3,13)=0.000 X(3,14)=92.870 68
X(3,15)=16.490 X(3,16)=27.620 X(3,17)=48.490 X(3,18)=41.520 Z(X(3)) Z(1X(3))=15206528.6600 Z(2X(3))=248.1700 Z(3X(3))=40895.0218 X(5)(Nghiem ham lien hop 2) X(5,1)=27.620 X(5,2)=41.520 X(5,3)=0.000 X(5,4)=0.000 X(5,5)=0.000 X(5,6)=0.000 X(5,7)=85.020 X(5,8)=0.000 X(5,9)=163.150 X(5,10)=92.870 X(5,11)=16.490 X(5,12)=0.000 X(5,13)=0.000 X(5,14)=0.000 X(5,15)=0.000 X(5,16)=0.000 X(5,17)=48.490 X(5,18)=0.000 Z(X(5)) Z(1X(5))=17884489.6800 Z(2X(5))=426.6700 Z(3X(5))=37429.6812 X(6)(Nghiem ham lien hop 3) X(6,1)=27.620 X(6,2)=41.520 X(6,3)=0.000 X(6,4)=0.000 X(6,5)=0.000 X(6,6)=0.000 X(6,7)=85.020 X(6,8)=0.000 X(6,9)=163.150 X(6,10)=14.081 X(6,11)=16.490 X(6,12)=0.000 X(6,13)=0.000 X(6,14)=78.789 X(6,15)=0.000 X(6,16)=0.000 X(6,17)=48.490 X(6,18)=0.000 Z(X(6)) Z(1X(6))=17000000.0000 Z(2X(6))=347.8806 Z(3X(6))=38861.2844 X(7)(Nghiem ham lien hop 4) X(7,1)=27.620 X(7,2)=41.520 69
X(7,3)=0.000 X(7,4)=0.000 X(7,5)=0.000 X(7,6)=0.000 X(7,7)=85.020 X(7,8)=0.000 X(7,9)=163.150 X(7,10)=16.200 X(7,11)=16.490 X(7,12)=0.000 X(7,13)=0.000 X(7,14)=76.670 X(7,15)=0.000 X(7,16)=0.000 X(7,17)=48.490 X(7,18)=0.000 Z(X(7)) Z(1X(7))=17023792.2600 Z(2X(7))=350.0000 Z(3X(7))=38822.7751 ******** KET THUC BAI TOAN - THE END ******** 2.3. Bài toán quy hoạch đất xã Trâu Quỳ File vào TNG.DAT 10 6 2 2 2 1 189.6407 189.6407 26.4 1700.5 43.8931 18 1000000000 0100000000 0000010000 5.14 4.98 3.77 0 0 0 0 0 0 0 0011111000 0000000111 4.48 4.2 2.59 0.98 5.8 15.61 29.67 39.21 116.58 105.13 0.6205 0.5915 0.465 0.1583 0.7065 0.5864 1.2996 1.2735 1.1726 1.756 0.0217 0.0206 0.0154 0.0045 0.0248 0.0109 0.0241 0.0349 0.09 0.0811 206 204 168 216 234 1428 1232 1124 1296 1296 0.7 0.778 1.1273 1.75 1 0.368 0.875 3 3 3 70