Tài liệu Lập kế hoạch sản xuất tối ưu giữa tổng công ty và các công ty con trên cơ sở lý thuyết quy hoạch toán học

i MỤC LỤC Nội dung Trang Mục lục i Danh mục các chữ viết tắt iv Danh mục các hình v MỞ ĐẦU 1 Chương 1. Tổng quan về quy hoạch toán học 3 1.1. Phát biểu bài toán Quy hoạch toán học 3 1.1.1. Bài toán Quy hoạch toán học tổng quát 3 1.1.2. Phân loại bài toán 4 1.2. Phát biểu bài toán đối ngẫu và phân tích nghiệm của bài toán đó. 5 1.2.1. Cách thành lập bài toán đối ngẫu 5 1.2.2. Các tính chất và định lý đối ngẫu 7 1.3. Giới thiệu một số phương pháp giải điển hình của quy hoạch toán học 1.3.1. Mô hình và một số phương pháp giải bài toán quy hoạch đa mục tiêu 1.3.2 Bài toán quy hoạch phi tuyến và một số phương pháp giải 1.4. Ví dụ 10 19 24 1.4.1. Áp dụng phương pháp so sánh, sắp xếp phương án bài toán quy hoạch đa mục tiêu 1.4.2. Vài bài toán thực tế dẫn đến quy hoạch phi tuyến Chương 2. Các dạng lập kế hoạch sản xuất dựa vào quy hoạch Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 8 24 26 30 http://www.lrc-tnu.edu.vn ii Nội dung Trang tuyến tính 2.1. Giới thiệu 30 2.2. Các ràng buộc 30 2.2.1. Tập nghiệm của bất phương trình tuyến tính 2.2.2. Vấn đề phương án cực biên và cơ sở xuất phát giai đoạn I 2.3 Các hàm mục tiêu 30 32 35 2.3.1. Ý nghĩa kinh tế của hàm mục tiêu 35 2.3.2. Hàm mục tiêu của một số mô hình lập kế hoạch sản xuất thực tế 2.4. Các phương pháp giải 36 38 2.4.1. Phương pháp đơn hình giải bài toán quy hoạch tuyến tính 2.4.2. Giải bài toán quy hoạch tuyến tính hai biến bằng phương pháp hình học 2.5. Phân tích phương án tối ưu 38 44 45 2.5.1. Phương án 45 2.5.2. Phương án cực biên 45 2.5.3. Phương án tối ưu 45 2.5.4. Sự tồn tại phương án tối ưu 45 Chương 3. Bài toán hỗn hợp (quy hoạch tuyến tính đa mục tiêu) lập kế hoạch đồng bộ giữa tổng công ty và các công ty con 3.1. Giải bài toán tại tổng công ty 47 3.1.1. Tìm phương án sản xuất tối ưu của tổng công ty 3.1.2. Phân phối (chỉ tiêu) phương án sản xuất tối ưu cho các công ty con Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 47 48 50 http://www.lrc-tnu.edu.vn iii Nội dung Trang 3.1.3. Giải lại bài toán đa mục tiêu trên cơ sở các thông tin phản hồi từ các công ty con 3.2. Giải bài toán tại công ty con 54 3.2.1. Tìm phương án tối ưu tại công ty con có ràng buộc là các chỉ tiêu của tổng công ty. 3.2.2. Các thông tin phản hồi lên tổng công ty 3.3. Chạy phần mềm thí nghiệm 50 54 56 56 3.3.1. Sơ đồ thuật toán 56 3.3.2. Cài đặt phần mềm 58 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 63 TÀI LIỆU THAM KHẢO 64 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT Stt Từ viết tắt Ý nghĩa Trang 1  ≤, =, ≥ 2  Quan hệ trội hơn 3 ~ Quan hệ không phân biệt 4  Rỗng 5 QHTT Quy hoạch tuyến tính 4 6 BTVT Bài toán vận tải 4 7 QHTS Quy hoạch tham số 4 8 QHĐ Quy hoạch động 4 9 QHPT Quy hoạch phi tuyến 4 10 QHRR Quy hoạch rời rạc 4 11 QHN Quy hoạch nguyên 4 12 QHĐMT Quy hoạch đa mục tiêu 5 13 NNLG Người nhận lời giải 14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 3 http://www.lrc-tnu.edu.vn v DANH MỤC CÁC HÌNH Stt Hình Nội dung Trang 1 2.1 2 2.2 3 3.1 4 3.2 Kết quả nhập mới dữ liệu của chương trình 60 5 3.3 Kết quả giải bài toán riêng rẽ một mục tiêu 61 6 3.4 Kết quả bảng thưởng phạt của chương trình 62 7 3.5 Kết quả bài toán 62 Sơ đồ thuật toán đơn hình 43 Minh hoạ phương pháp giải bài toán QHTT hai biến bằng phương pháp hình học Sơ đồ thuật toán giải bài toán lập kế hoạch sản xuất đồng bộ Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 44 57 http://www.lrc-tnu.edu.vn -1- MỞ ĐẦU Trong giai đoạn kinh tế thị trường, sự cạnh tranh hàng hoá quyết liệt xẩy ra thường xuyên thì một phương án sản xuất cần phải được cân nhắc kỹ càng trước khi nó được thực thi. Một phương án sản xuất thường phụ thuộc rất nhiều vào các yếu tố như lao động, nguyên vật liệu, sức tiêu thụ, …Vì vậy một phương án sản xuất cần phải được bao hàm các hạn chế trên, đồng thời phải đảm bảo được mức tổng lãi (hoặc chi phí) tốt nhất. Đặc biệt, khi một tổng công ty có nhiều công ty con, mỗi công ty đều muốn có phương án sản xuất tốt nhất của mình nhưng phải nằm trong mục tiêu của tổng công ty. Vì vậy, phương án sản xuất tốt kết hợp giữa tổng công ty và các công ty con cần phải được nghiên cứu. Do đó tôi tiến hành nghiên cứu đề tài: “Lập kế hoạch sản xuất tối ưu giữa tổng công ty và các công ty con trên cơ sở lý thuyết quy hoạch toán học”. Với nội dung nghiên cứu:  Mục tiêu nghiên cứu và tính cấp thiết của đề tài Ứng dụng quy hoạch tuyến tính để hỗ trợ các nhà lập kế hoạch và quản lý kinh tế ra những quyết định chính xác và tốt nhất có thể, nó là một công cụ đáng tin cậy để phân tích và dự đoán hướng phát triển có mục tiêu của các cơ sở kinh tế nói chung và của các công ty và tổng công ty nói riêng.  Phạm vi nghiên cứu và ứng dụng - Nghiên cứu về quy hoạch tuyến tính đơn mục tiêu và đa mục tiêu – phương pháp tối ưu kiểu pareto. - Nghiên cứu một số phương pháp lập kế hoạch dựa trên các quy trình công nghệ đã cho như: hàm sản xuất tuyến tính dạng X = AX, trong đó: + A là ma trận công nghệ. + X là phương án sản xuất  Ý nghĩa khoa học Trên cơ sở tối ưu pareto để tìm ra các phương án sản xuất cho tổng công ty và các công ty con dựa trên phương pháp cạnh tranh và bù đắp. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -2-  Phƣơng pháp nghiên cứu - Phương pháp tìm các hệ số chi phí trong quy trình sản xuất của toàn công ty và của từng công ty con. Ứng dụng phương pháp quy hoạch tuyến tính để giải bài toán tìm phương án sản xuất tối ưu giữa tổng công ty và các công ty con  Cấu trúc luận văn MỞ ĐẦU CHƢƠNG 1. TỔNG QUAN VỀ QUY HOẠCH TOÁN HỌC CHƢƠNG 2. CÁC DẠNG LẬP KẾ HOẠCH SẢN XUẤT DỰA VÀO QUY HOẠCH TUYẾN TÍNH CHƢƠNG 3. BÀI TOÁN HỖN HỢP (QUY HOẠCH TUYẾN TÍNH ĐA MỤC TIÊU) LẬP KẾ HOẠCH ĐỒNG BỘ GIỮA TỔNG CÔNG TY VÀ CÁC CÔNG TY CON KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TÀI LIỆU THAM KHẢO Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -3- CHƢƠNG 1 TỔNG QUAN VỀ QUY HOẠCH TOÁN HỌC 1.1. Phát biểu bài toán Quy hoạch toán học tổng quát Khi tiến hành lập kế hoạch sản xuất, điều khiển các hệ thống và thiết kế kỹ thuật mà biết dựa trên các nguyên tắc cực trị sẽ tiết kiệm được vật tư, tiền vốn, tài nguyên, sức lao động, thời gian và tăng được hiệu quả giải quyết các vấn đề đặt ra. Những cơ sở lý thuyết và các phương pháp thực hành để giải quyết các vấn đề nằm trong môn học Tối ưu hóa hay còn gọi là Quy hoạch toán học… 1.1.1. Bài toán Quy hoạch toán học tổng quát Một bài toán Quy hoạch toán học tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm: f(x) → max (min) (1.1) Với các điều kiện: g i ( x)  bi , i  1, m (  {, , }) x  X  Rn (1.2) (1.3) Bài toán (1.1)  (1.3) được gọi là một quy hoạch, f(x) được gọi là hàm mục tiêu, các hàm g i ( x), i  1, m được gọi là các hàm ràng buộc, mỗi đẳng thức hoặc bất đẳng thức trong hệ (1.2) được gọi là ràng buộc. Tập hợp: D  {x  X | g i ( x)  bi , i  1, m } (1.4) được gọi là hàm ràng buộc (hay miền chấp nhận được). Mỗi điểm x  ( x1 , x 2 ,..., xn )  D được gọi là một phương án (hay lời giải chấp nhận được). Một phương án x *  D đạt cực đại (hay cực tiểu) của hàm mục tiêu, cụ thể là: f ( x * )  f ( x), x  D đối với bài toán max f ( x * )  f ( x), x  D đối với bài toán min được gọi là phương án tối ưu (lời giải tối ưu). Khi đó giá trị f ( x * ) được gọi là giá trị tối ưu của bài toán. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -4- 1.1.2. Phân loại các bài toán Một trong những phương án hiển nhiên nhất để giải bài toán đặt ra là phương pháp điểm diện: tính giá trị hàm mục tiêu trên tất cả các phương án, sau đó so sánh các giá trị tính được để tìm ra giá trị tối ưu và phương pháp tối ưu của bài toán. Tuy nhiên cách giải quyết này khó có thể thực hiện được, ngay cả khi kích thước của bài toán (số biến n và số ràng buộc m) là không lớn, bởi vì tập D thông thường gồm một số rất lớn các phần tử, trong nhiều trường hợp còn không đếm được. Vì vậy cần phải có những nghiên cứu về mặt lý thuyết để có thể tách ra từ bài toán tổng quát những bài toán “dễ giải”. Các nghiên cứu lý thuyết đó thường là: - Nghiên cứu các tính chất của các thành phần bài toán (hàm mục tiêu, các ràng buộc, các biến số, các hệ số…); - Các điều kiện tồn tại lời giải chấp nhận được; - Các điều kiện cần và đủ của cực trị; - Tính chất của các đối tượng nghiên cứu. Các tính chất của các thành phần của bài toán và đối tượng nghiên cứu giúp ta phân loại các bài toán. Một số bài toán tối ưu (quy hoạch toán học) được gọi là: - Quy hoạch tuyến tính (QHTT) nếu hàm mục tiêu ràng buộc và tất cả các hàm là tuyến tính. Một trường hợp riêng quan trọng của QHTT là bài toán vận tải (BTVT); - Quy hoạch tham số (QHTS) nếu các hệ số trong biểu thức của hàm mục tiêu và của các ràng buộc phụ thuộc vào tham số; - Quy hoạch động (QHĐ) nếu đối tượng xét là các quá trình có nhiều giai đoạn nói chung, hay các quá trình phát triển theo thời gian nói riêng; - Quy hoạch phi tuyến (QHPT) nếu hoặc có ít nhất một trong các hàm là phi tuyến hoặc cả hai trường hợp đó cùng xảy ra; - Quy hoạch rời rạc (QHRR) nếu miền ràng buộc D là tập rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên ta có Quy hoạch nguyên (QHN). Một trường hợp riêng của QHN là quy hoạch biến booles khi các biến số chỉ nhận giá trị là 0 hoặc 1. Còn tối ưu hóa tổ hợp liên quan đặc Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -5- tính hữu hạn của đối tượng nghiên cứu, hay sự tồn tại một cấu trúc cho ta một định tính không gian của các tình huống cần so sánh; - Quy hoạch đa mục tiêu (QHĐMT) nếu trên cùng một miền ràng buộc ta xét các mục tiêu khác nhau. 1.2. Phát biểu bài toán đối ngẫu và phân tích nghiệm của bài toán đó 1.2.1. Cách thành lập bài toán đối ngẫu a. Cặp bài toán đối ngẫu không đối xứng Xét bài toán dạng chính tắc (I): n f ( x)   c j x j  Min( Max ) j 1 n aij x j  bi , i  1, m  j 1   x  0, j  1, n  j Ta gọi bài toán này là bài toán gốc. Dựa vào bài toán gốc (I), ta xây dựng một bài toán quy hoạch tuyến tính khác gọi là bài toán đối ngẫu của bài toán (I) có dạng sau: m ~ f ( y )   bi yi  Max ( Min) i 1 m a i 1 ij yi  ()c j , j  1, n Ký hiệu bài toán này là (I’). Cặp bài toán (I, I’) gọi là cặp bài toán không đối xứng.  Nguyên tắc thành lập bài toán đối ngẫu ~ - Nếu f(x) → Min thì f ( y ) → Max và hệ ràng buộc của bài toán đối ngẫu có dạng “≤”. ~ - Nếu f(x) → Max thì f ( y ) → Min và hệ ràng buộc của bài toán đối ngẫu có dạng “≥”. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -6- - Số ràng buộc (không kể ràng buộc dấu) trong bài toán này bằng số biến số trong bài toán kia, từ đó thấy tương ứng với một ràng buộc của bài toán này là một biến số của bài toán kia. - Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc trong bài toán kia. - Ma trận điều kiện trong hai bài toán là chuyển vị của nhau. - Các biến số trong bài toán đối ngẫu không có ràng buộc về dấu. Khi phân tích quan hệ của hai bài toán đối ngẫu cần sử dụng một khái niệm quan trọng: Cặp ràng buộc đối ngẫu: Ta gọi 2 ràng buộc bất đẳng thức (kể cả ràng buộc dấu) trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu. Trong hai bài toán (I) và (I’) có n cặp ràng buộc đối ngẫu: m xi  0   aij yi  ()c j , j  1, n i 1 b. Cặp bài toán đối ngẫu đối xứng Xét bài toán (II): n f ( x)   c j x j  Min( Max ) j 1 n aij x j  ()bi , i  1, m  j 1   x  0, j  1, n  j Đưa bài toán về dạng chính tắc, ký hiệu là (II~): n f ( x)   c j x j  Min( Max ) j 1 n aij x j  () xn 1  bi , i  1, m   j 1  x  0, j  1, n  m  j Bài toán đối ngẫu của (II~) và cũng là đối ngẫu của (II) có dạng: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -7- m ~ f ( y )   bi yi  Max ( Min) i 1 n  aij yi  ()c j , j  1, n .  j 1  y  0, i  1, m  i Ký hiệu bài toán này là (II’). Do đặc điểm cấu trúc của hai bài toán, ta gọi (II) và (II’) là cặp bài toán đối ngẫu đối xứng . Hai bài toán này có n + m cặp rằng buộc đối ngẫu sau: x j  0   aij yi  ()c j , j  1, n n a j 1 ij x j  ()bi  yi , i  1, m c. Cặp bài toán đối ngẫu tổng quát Đối với bài toán bất kỳ, đưa về dạng chính tắc, xây dựng bài toán đối ngẫu của bài toán này và gọi là bài toán đối ngẫu của bài toán đã cho. Chúng ta có thể sử dụng các quy tắc nêu trong lược đồ dưới đây để trực tiếp viết bài toán đối ngẫu mà không cần phải thực hiện bước biến đổi về dạng chính tắc. Lƣợc đồ tổng quát Bài toán gốc n f ( x)   c j x j  Min( Max ) j 1 n a j 1 ij x j  bi , i  1, m n  aij x j  ()bi , i  1, m j 1 n  aij x j  ()bi , i  1, m j 1 x j không ràng buộc về dấu. x j  0, j  1, n x j  0, j  1, n Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên Bài toán đối ngẫu m ~ f ( y )   bi yi  Max ( Min) i 1 y i không ràng buộc về dấu. yi  0, i  1, m yi  0, i  1, m m a ij yi  c j , j  1, n a ij yi  ()c j , j  1, n a ij yi  ()c j , j  1, n i 1 m i 1 m i 1 http://www.lrc-tnu.edu.vn -8- 1.2.2. Các tính chất và định lý đối ngẫu a. Các tính chất  Tính chất 1: Với mọi cặp phương án x và y của hai bài toán đối ngẫu ta luôn ~ có: f ( x)  () f ( y ).  Tính chất 2: Nếu đối với hai phương án x * và y* của một cặp bài toán đối ~ ngẫu mà f ( x * )  f ( y * ) thì x* và y* tương ứng là hai phương án tối ưu. b. Các định lý  Định lý 1: Nếu một trong hai bài toán đối ngẫu giải được thì bài toán kia cũng giải được và khi đó với mọi cặp phương án tối ưu x * và y* ta luôn có ~ f ( x* )  f ( y * ) .  Định lý 2: Điều kiện cần và đủ để hai phương án x và y của một cặp bài toán đối ngẫu tối ưu là trong các ràng buộc đối ngẫu nếu một ràng buộc thoả mãn với dấu bất đẳng thức thực sự (lỏng) thì ràng buộc kia phải thoả mãn với dấu bằng (chặt). Ví dụ: Quy hoạch đối ngẫu của bài toán là quy hoạch: 1.3. Giới thiệu một số phƣơng pháp giải điển hình của quy hoạch toán học Như đã trình bày trong mục (1.1.2), một bài toán quy hoạch toán học được phân loại thành nhiều dạng khác nhau dựa vào tính chất của các thành phần và đối tượng nghiên cứu. Mỗi dạng lại có phương pháp giải đặc trưng riêng như: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn -9-  Quy hoạch tuyến tính: - Phương pháp đơn hình và đơn hình cải biên - Phương pháp hình học - Phương pháp Hungary  Quy hoạch động: - Phương pháp phương trình truy toán  Quy hoạch phi tuyến: - Phương pháp giải quy hoạch phi tuyến không có ràng buộc o Các phương pháp sử dụng đạo hàm o Các phương pháp không sử dụng đạo hàm o Tối ưu hoá hàm “khe” bằng “R-algorithm” o Các phương pháp vượt khe - Phương pháp giải quy hoạch phi tuyến có ràng buộc o Phương pháp hàm phạt o Phương pháp gradient o Phương pháp các nhân tử Lagrange  Quy hoạch rời rạc: - Phương pháp nhánh – cận - Các phương pháp gần đúng o Phương pháp tối ưu cục bộ o Phương pháp tìm kiếm ngẫu nhiên  Quy hoạch đa mục tiêu: - Phương pháp nhượng bộ dần - Phương pháp thoả hiệp TAMM - Phương pháp Người – Máy (của Geoffrion, Dyer, Fienberg) - Phương pháp từng bước Benayoun - Thuật toán thích nghi ổn định tối ưu hoá vectơ - Phương pháp giải theo dãy mục tiêu đã được xắp xếp - Phương pháp ràng buộc Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 10 - - Phương pháp trọng số - Phương pháp so sánh, sắp xếp phương án bài toán quy hoạch đa mục tiêu - Phương pháp đồ thị 1.3.1. Mô hình và một số phƣơng pháp giải bài toán quy hoạch đa mục tiêu a. Mô hình bài toán quy hoạch đa mục tiêu Y ( X )  max(min) (1.5) X  D  Rn (1.6) Y ( X )  (Y1 ( X ),......,Yk ( X ))  R k (1.7) gọi là vectơ mục tiêu X gọi là phương án. D là tập các phương án. Y1, ……Yk gọi là các hàm mục tiêu. Khi xử lý tập phương án Pareto vai trò người nhận lời giải có tác dụng đáng kể trong quá trình giải. Người nhận lời giải như ngụ ý rằng: Trong tập phương án đó, các phương án đã có quan hệ trội hơn (  ) và không phân biệt (~) được hình thành từ việc so sánh “lợi ích” của các phương án. Giải bài toán như vậy gọi là bài toán quy hoạch đa mục tiêu kết hợp sở thích người nhận lời giải. Ở đây ta hiểu “lợi ích” là một hàm U: Y(D) → R. Thông thường ta giả thiết U thoả mãn một số điều kiện nào đó khái quát từ bài toán thực tế và hiện tượng thực tiễn. Chẳng hạn U là một hàm lõm (hàm lợi ích tăng lên khi các hàm mục tiêu tăng lên) tức là: U / Yi  0 i  1, k (1.8)  2U /  Y i  0 i  1, k (1.9) 2 Tuy nhiên ở đây ta hiểu U đơn thuần chỉ là một ánh xạ “đo” sở thích người nhận lời giải. Hàm U có thể cho dưới dạng tường minh hoặc dạng ẩn (tức là biểu hiện rằng: các phương án có thể so sánh được với nhau theo một nghĩa “hơn” “kém” “không phân biệt” nào đó). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 11 - Bài toán quy hoạch đa mục tiêu kết hợp với lợi ích của người nhận lời giải trong trường hợp hàm U tường minh có thể viết: MaxU (Y ( X )) X D (1.10) (1.11) b. Một số phƣơng pháp giải bài toán quy hoạch đa mục tiêu.  Phƣơng pháp nhƣợng bộ dần Phương pháp này dẫn đến việc tìm một lời giải thoả hiệp tốt nhất tức là tìm nghiệm X* mà theo ý thích của người nhận lời giải thì X  D : X *  X hoặc X* ~ X Thuật toán giải: Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ. Sau đó lập bảng thưởng phạt (trong đó X1 là phương án tối ưu. Y10 là giá trị tối ưu). Hàm mục tiêu Y1 Y2 Yk Y1 0 Y2(X1) Yk(X1) Phương án X1 X2 Y2 0 … Xk Yk 0 Bước 2: Căn cứ vào bảng thưởng phạt và Y10 người nhận lời giải bắt Y1 phải nhượng bộ một lượng Y1 và giải bài toán: max Y2 ( X ) X D Y1 ( X )  Y1  Y1 0 Giả sử Y2* là giá trị tối ưu của bài toán, chuyển sang bước 3. Bước 3: Người nhận lời giải căn cứ vào Y20 và Y2* bắt Y2 phải nhượng bộ một lượng Y2 và giải bài toán: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 12 - max Y3 ( X ) X D Y1 ( X )  Y1  Y1 0 Y2 ( X )  Y2  Y2 0 Giả sử Y3* là giá trị tối ưu của bài toán, chuyển sang bước tiếp theo: ….. Bước k: Căn cứ vào Yk-10 và Yk-1* bắt Yk-1 nhượng bộ một lượng Yk-1 và giải bài toán: max Yk ( X ) X D Y1 ( X )  Y1  Y1 0 Y2 ( X )  Y2  Y2 * .... Yk 1 ( X )  Yk 1  Yk 1 * Nghiệm của bài toán cuối cùng này lấy làm nghiệm cho bài toán xuất phát.  Phƣơng pháp thoả hiệp của TAMM Giải bài toán max Y ( X ) X D (1.12) (1.13) Thuật toán giải như sau: Bước 1: Giải k bài toán một mục tiêu riêng rẽ. Giải sử nghiệm tối ưu là X i , i  1, k . Đặt Mi = Yi(X) (1.14) Đưa vào biến phụ W: i  1, k : M i  Yi ( X ) W Mi M i  Yi ( X ) gọi là độ lệch tương đối chung Mi Bước 2: Giải bài toán: min W Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên (1.15) http://www.lrc-tnu.edu.vn - 13 - M i  Yi ( X )  W (i  1, k ) Mi (1.16) X D (1.17) .. .. Từ đó tìm được nghiệm tối ưu X và W Ở đây hàm “lợi ích” U tỷ lệ với độ lệch tương đối chung. Còn X 1  X 2 nếu độ lệch tương đối chung của X1 nhỏ hơn của X2 và ta có: X  D : X  X hoặc X ~ X .  Phƣơng pháp từng bƣớc của Benayoun Phương pháp có hai biến dạng như sau: - Các độ lệch tương đối của hàm mục tiêu thì được gắn với một bộ trọng số tương ứng. Trọng số này được xác định dựa trên khoảng biến động của từng mục tiêu. - Miền chấp nhận được của nó có thể thay đổi qua các bước giải. Hàm “lợi ích” và các quan hệ xác định như phương pháp tìm nghiệm có khoảng cách nhất đến nghiệm lý tưởng. Bài toán cơ bản mà phương pháp này xét  I M I  YI ( X )  d ' I  1, k (1.18) X  Di (1.19) Trong đó: MI là giá trị max YI(X) XD Ta viết d ' là metric đã thay đổi. Di là miền chấp nhận được. Khi i = 0 thì D0  D. Thuật toán giải như sau: Bước 1: Xây dựng bảng “thưởng phạt” xác định MI và mI (giá trị max và min của YI(X)) ở cột I. Bước 2: Tìm các trọng số Xác định I để tính  I : Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 14 - I  M I  mI * MI 1 n  (C ) j 1 Ở đây C I j (1.20) I 2 j là các hệ số của hàm mục tiêu thứ I. Đặt i = bước sang bước 3. Bước 3: Tính  I : I  I  I (1.21) và giải bài toán i. Bước 4: Giả sử nghiệm của bài toán I là X(i). Đưa cho người nhận lời giải nghiệm X(i). Người nhận lời giải phân tích kết quả và xảy ra: 1) Nếu người nhận lời giải (NNLG) chấp nhận X(i) thì thuật toán kết thúc. 2) Nếu NNLG không chấp nhận X(i) và nếu chỉ số i < k-1 thì sang bước 5. 3) Nếu NNLG không thoả mãn X(i) và i = k – 1 thì chọn cách giải khác. Bước 5 : NNLG phân tích kết quả và tìm ra mục tiêu I* có thể nhượng bộ. NNLG cho một nhượng bộ I* và sang bước 6. Bước 6 : Xác nhận miền chấp nhận mới D(i+1) X  Di YI ( X )  YI X (i ) I  I * * YI ( X )  YI | X (i ) | YI * * * Coi  I  0   I  0 * * Còn đối với I  I* thì tính nhờ giá trị tối ưu của bài toán tìm hướng và giá trị hàm lợi ích. Tăng i lên một đơn vị và chuyển về bước 3. Thuật toán kết thúc sau không quá k lần lặp.  Thuật toán thích nghi ổn định tối ƣu hoá vectơ Bài toán quy hoạch đa mục tiêu được hiểu như là bài toán tối ưu hoá vectơ: X  D  Rn Y1 ( X ),......,Yk ( X ) Các Y1(X) biểu hiện độ tốt xấu của X theo nghĩa nào đó. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - 15 - Ta xét bài toán max. Giả thiết X 0  D là vectơ tối ưu đối với người nhận lời giải. Yêu cầu người nhận lời giải ước lượng giá trị mà mình thích nhất: Y0v, ( v  1, k ) với điều kiện: Y 0 v  Yv ( X 0 ) Vectơ X là lời giải tối ưu của: E{Y 0 v  Yv ( X )}  0, v  1, k E{ Y 0 v  Yv ( X ) }  min X D Đặt độ lệch:  v (Y 0 v ( X ))  Y 0 v  Yv ( X )  bài toán hay  v  1, k E{ 2 v {Y 0 v ( X )}  min X D k  v 1 v E{(Y 0 v  Yv ( X )) 2 }  min k Ở đây:  v  0;  v  1 v 1 (ký hiệu E là kỳ vọng toán học) Người ta mở rộng bài toán trên và đưa ra một thuật toán giải nó. Hàm lợi ích trong trường hợp này không thể hiện một cách tường minh mà người nhận lời giải ngụ ý rằng trên D có một hàm ý thích. Còn quan hệ , ~ được rút ra thông qua việc so sánh các hàm mục tiêu.  Phƣơng pháp so sánh, sắp xếp phƣơng án bài toán quy hoạch đa mục tiêu - Cơ sở của hệ thống trừu tƣợng nhƣ các quan hệ mờ trên các tham số Giả sử cho hệ thống S, chúng ta cần mô tả hành vi của hệ thống đó thông qua các tham số X = {Xi}. Thực tế ta không biết tất cả các tham số X  X : X  { X i }iI , nên chỉ mô tả gần đúng hệ S: S  U x Vi, i  I. Trong đó Vi tập hợp các giá trị có thể có của tham số Xi. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn