Tối ưu Số Cho Bài Toán Tối ưu Một Mục Tiêu - Tài Liệu Text - 123doc

Tải bản đầy đủ (.doc) (85 trang)

1. Trang chủ
>>
2. Kỹ thuật
>>
3. Điện - Điện tử - Viễn thông

Tối ưu số cho bài toán tối ưu một mục tiêu

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (773.4 KB, 85 trang )

Luận án tốt nghiệp Phần 0Phần 0MỞ ĐẦUMỞ ĐẦU1Luận án tốt nghiệp Ngày nay, các bài toán tối ưu thường xuất hiện trong kinh tế và kỹ thuật, chúng có nhiều ứng dụng rất rộng rãi và đa dạng.Trên thế giới có rất nhiều giải thuật để giải các bài toán tối ưu. Trong đó, các giải thuật tiến hóa áp dụng cho các bài toán tối ưu một mục tiêu hay đa mục tiêu đã chứng tỏ tính hiệu quả của nó một cách rộng rãi trong những năm gần đây thông qua một số lượng lớn các áp dụng. Tuy nhiên, hầu hết các nghiên cứu hiện hành trên các ứng dụng của giải thuật tiến hóa để giải các bài toán tối ưu một hay nhiều mục tiêu đều tập trung trên các chiến lược xử lý các hàm mục tiêu, gán giá trò fitness và chọn lọc nhằm cố gắng đạt được mục đích là hướng dẫn việc tìm kiếm của giải thuật đến một miền thu hẹp có chứa lời giải tối ưu đối với bài toán tối ưu một mục tiêu hay biên tối ưu Pareto đối với bài toán tối ưu đa mục tiêu.Tuy nhiên các lời giải tìm được thường là các lời giải xấp xỉ khá tốt nhưng không phải lời giải tối ưu (một mục tiêu) hay tối ưu Pareto (đa mục tiêu). Mặc dù các toán tử sinh sản như lai ghép và đột biến đã được cải tiến rất nhiều nhưng chúng vẫn sản sinh ra các cá thể con mà hoàn toàn không biết đến các cá thể con đó có khả năng tốt hơn hay xấu hơn cha mẹ của chúng như thế nào. Nói cách khác, lý do để các giải thuật tiến hóa thường không đạt được các lời giải tối ưu (một mục tiêu) hay tối ưu Pareto (đa mục tiêu) là các toán tử di truyền như lai ghép và đột biến theo kiểu truyền thống không đủ mạnh để sản sinh ra các cá thể tốt nhất như mong muốn.Để vượt qua khó khăn đó, người ta đề xuất một hướng tiếp cận mới, được gọi là giải thuật Tìm Kiếm Ngẫu Nhiên Theo Xác Suất (TKNNTXS), để giải các bài toán tối ưu một hay nhiều mục tiêu. Hướng tiếp cận này có những đặc điểm sau- Không cần thiết kế một hàm phụ trợ như các hàm phạt. Việc xử lý các hàm mục tiêu và các ràng buộc được tách biệt nhau. Xử lý trực tiếp trên các chữ số của biến quyết đònh để phát sinh lời giải khả thi tốt hơn và sử dụng chính các hàm mục tiêu làm hàm đo độ tốt của lời giải.- Không sử dụng kỹ thuật di truyền truyền thống như lai ghép và đột biến tại một hay nhiều điểm. Việc sản sinh và tìm kiếm lời giải tối ưu là ngẫu nhiên được hướng dẫn bởi xác suất.2Luận án tốt nghiệp Phần 1Phần 1TỔNG QUANTỔNG QUAN3Luận án tốt nghiệp I.Khái quát: Phần mềm áp dụng giải thuật Tìm Kiếm Ngẫu Nhiên Theo Xác Suất để tìm ra các đáp số tối ưu cho bài toán một mục tiêu (Bài toán Min hoặc bài toán Max). Tuy nhiên, phân mềm không đưa ra các đáp số đã tìm được là tối ưu nhất, chỉ là tương đối.Mục đích của phần mềm này là: Đưa ra đáp số tối ưu cho bài toán một mục tiêu. Từ đó, có thể giúp mọi người giải quyết vấn đề của họ. Giúp người học giải các bài toán tối ưu bằng máy tính.2. Phạm vi sử dụng: Chương trình sẽ được sử dụng trong các trường học để giúp cho người học tìm ra các đáp án tối ưu cho bài toán tối ưu với độ chính xác cao nhất.Sử dụng trong việc tìm ra phương án tối ưu để giải quyết các vấn đề phức tạp.III. Người sử dụng: Các lập trình viên, người phân tích thiết kế và mọi người.IV.Nhiệm vụ: Tìm ra các phương án tối ưu cho bài toán một mục tiêu.Ngôn ngữ cài đặt cho chương trình là Visual Basic 6.0.4Luận án tốt nghiệp Phần 2Phần 2GIỚI THIỆU CÁC PHƯƠNG PHÁP TỐI ƯU CỔ ĐIỂNGIỚI THIỆU CÁC PHƯƠNG PHÁP TỐI ƯU CỔ ĐIỂN5Luận án tốt nghiệp A.MỞ ĐẦU I. ĐỐI TƯNG NGHIÊN CỨU Các thuật toán tối ưu có rất nhiều ứng dụng trong kinh tế và trong khoa học kỹ thuật. Đối với mỗi thuật toán, cần phải xây dựng cơ sở lý thuyết của thuật toán, chứng minh tính hữu hạn hay hội tụ của nó, thuật toán cần phải lập trình được và chạy có hiệu quả trên máy tính.1. BÀI TOÁN TỐI ƯU TỔNG QUÁT :Bài toán tối ưu tổng quát được phát biểu như sau. Cực đại hóa (cực tiểu hóa) hàmf(x) → max (min) (1)với các điều kiệngi(x) (≤,=,≥) bi, i=1, ….,m (2)x ∈ X ⊂ Rn (3)Bài toán (1)-(3) được gọi là một quy hoạch, hàm f(x) được gọi là hàm mục tiêu, các hàm gi(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ệ (2) được gọi là một ràng buộc. Tập hợp D= x ∈ X | gi(x) (≤,=,≥) bi, i=1, ….,m (4)được gọi là miền ràng buộc (hay miền chấp nhận được). Mỗi điểm x=(x1,x2,….,xn) ∈ D được gọi là một phương án (hay một 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.6Luận án tốt nghiệp 2. PHÂN LOẠI CÁC BÀI TOÁN :Một trong những phương pháp hiển nhiên nhất để giải bài toán đặt ra là phương pháp duyệt toàn bộ: tìm giá trò hàm mục tiêu f(x) 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 án 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 không lớ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 phần tử, trong nhiều trường hợp là không đếm được.Vì vậy cần phải có những nghiên cứu trước về mặt lý thuyết để có thể tách ra từ bài toán tổng quát những lớp 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 hàm 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 bài toán tối ưu được gọi là: Quy hoạch tuyến tính (QHTT) nếu hàm mục tiêu f(x) và tất cả các hàm ràng buộc gi(x), i=1, ….,m là tuyến tính. Tập X là một tập lồi đa diện. Một trường hợp riêng quan trọng của quy hoạch tuyến tính là bài toán vận tải. Quy hoạch tham số 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 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 nếu f(x) hoặc có ít nhất một trong các hàm gi(x) là phi tuyến, hoặc cả hai trường hợp đó cùng xảy ra. Quy hoạch lồi nếu tìm cực tiểu của hàm lồi f(x) trên tập lồi D. Quy hoạch lõm nếu tìm cực tiểu hàm lõm f(x) trên tập lồi D. Quy hoạch rời rạc 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. Một 7Luận án tốt nghiệp trường hợp riêng của quy hoạch nguyên là quy hoạch biến Boole khi các biến số chỉ nhận giá trò 0 hay 1. Quy hoạch đa mục tiêu nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau.II.VẤN ĐỀ MÔ HÌNH HÓA TOÁN HỌC 1. XÂY DỰNG MÔ HÌNH TOÁN HỌC CHO MỘT VẤN ĐỀ THỰC TẾViệc mô hình hóa toán học cho một vấn đề thục tế có thể chia làm bốn bước. Bước 1: Xây dựng mô hình đònh tính cho vấn đề thực tế, tức là xác đònh các yếu tố có ý nghóa quan trọng nhất và xác lập các quy luật mà chúng phải tuân theo. Nói một cách khác là phát biểu mô hình bằng lời và bằng những biểu đồ, các điều kiện về kinh tế kỹ thuật, tự nhiên, xã hội, các mục tiêu cần đạt được. Bước 2: Xây dựng mô hình cho vấn đề đang xét, tức là diễn tả lại dưới dạng ngôn ngữ toán học cho mô hình đònh tính. Khi có một hệ thống, ta chọn các biến số đặc trưng cho các trạng thái của hệ thống. Mô hình toán học thiết lập mối liên hệ giữa các biến số và các hệ số điều khiển hiện tượng. Việc làm rất quan trọng ở bước này là phải xác đònh hàm mục tiêu, tức là một đặc trưng bằng số mà giá trò càng lớn (càng nhỏ) của nó tương ứng với hiệu quả càng tốt hơn giải quyết vấn đề mà người nhận lời giải mong muốn. Tiếp theo, phải diễn tả bằng các phương trình hay bất phương trình các điều kiện kinh tế kỹ thuật …, đó là các ràng buộc toán học mà các biến số phải tuân theo. Bước 3: Sự dụng các công cụ toán học để khảo sát và giải quyết bài toán hình thành trong Bước 2. Căn cứ vào mô hình đã xây dựng cần phải chọn hoặc xây dựng phương pháp giải cho phù hợp. Tiếp đó, cụ thể hóa phương pháp bằng các thuật toán tối ưu. Vì các bài toán thực tế thường có kích thước lớn nên không thể giải bằng tay được mà phải sử dụng máy tính điện tử. Vậy cần phải chương trình hóa thuật toán bằng một ngôn ngữ lập trình thích hợp, sau đó đưa lên máy tính để chạy và in ra kết quả.8Luận án tốt nghiệp  Bước 4: Phân tích và kiểm đònh lại các kết quả thu được trong Bước 3. Trong bước này cần phải xác đònh mức độ phù hợp của mô hình và kết quả tính toán với vấn đề thực tế hoặc áp dụng phương pháp phân tích chuyên gia. Ở đây có thể xảy ra một trong hai khả năng sau.− Khả năng 1: Mô hình và các kết quả tính toán phù hợp với thực tế. Khi đó cần lập một bảng tổng kết ghi rõ cách đặt vần đề, mô hình hóa toán học thuật toán tối ưu, chương trình, cách chuẩn bò số liệu để đưa vào máy tính, nghóa là toàn bộ các công việc cần thiết cho việc áp dụng mô hình và kết quả để giải quyết vấn đề thực tế đặt ra. Trong trường hợp mô hình cần được sử dụng nhiều lần thì phải xây dựng hệ thống phần mềm bảo đảm giao diện thuận tiện giữa người sử dụng và máy tính điện tử, không đòi hỏi người sử dụng phải có trình độ chuyên môn cao về toán.− Khả năng 2: Mô hình và các kết quả tính toán không phù hợp với thực tế. Trong trường hợp này cần phải xem xét các nguyên nhân của nó. Có thể nêu ra bốn nguyên nhân sau: Các kết quả tính toán trong Bước 3 chưa đủ độ chính xác cần thiết. Khi đó cần phải xem lại các thuật toán cũng như các chương trình tính toán đã viết và sử dụng. Các số liệu ban đầu (các hệ số, thông số) không phản ánh đúng thực tế giá cả, hoặc chi phí trên thò trường, hoặc các đònh mức vật tư, hoặc các số liệu khác về công suất, khả năng máy móc, dự trữ tài nguyên, … Khi đó cần điều chỉnh lại một cách nghiêm túc, chính xác. Mô hình đònh tính xây dựng chưa phản ánh được đầy đủ hiện tượng thực tế. Nếu vậy cần rà soát lại Bước 1 xem có yếu tố hoặc quy luật nào còn bò bỏ sót không? Việc xây dựng mô hình toán học ở Bước 2 chưa thỏa đáng. Cần phải xây dựng lại cho phù hợp, mức độ tăng dần từ tuyến tính đến phi tuyến, từ tónh đến động.2. MỘT SỐ MÔ HÌNH THỰC TẾ : Bài toán lập kế hoạch sản xuất.9Luận án tốt nghiệp  Bài toán vận tải. Bài toán cái túi.B. CÁC LOẠI BÀI TOÁN TỐI ƯU VÀ PHƯƠNG PHÁP CỔ ĐIỂNI. QUY HOẠCH TUYẾN TÍNH Quy hoạch tuyến tính (QHTT) là một trong những lớp bài toán tối ưu được nghiên cứu trọn vẹn cả về phương diện lý thuyết lẫn thực hành.QHTT bắt nguồn từ những nghiên cứu của nhà toán học Nga nổi tiếng, Viện sỹ Kantorovich L.V, trong một loạt các công trình về bài toán kế hoạch hóa sản xuất, công bố năm 1938. Năm 1947, nhà toán học Mỹ Dantzig đã nghiên cứu và đề xuất phương pháp đơn hình (Simplex method) để giải bài toán QHTT. Năm 1952 phương pháp đơn hình đã được chạy trên máy tính điện tử ở Mỹ.QHTT có một vò trí quan trọng trong tối ưu hóa vì 2 lý do. Lý do thứ nhất là mô hình tuyến tính đơn giản trong việc áp dụng. Lý do thứ hai là nhiều bài toán quy hoạch nguyên và quy hoạch phi tuyến có thể xấp xỉ với độ chính xác cao bởi một dãy các bài toán QHTT.1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH a) Bài toán tổng quát :Để nhất quán lập luận ta xét bài toán tím cực đại, sau đó ta sẽ xét cách chuyển bài toán tìm cực tiểu sang tìm cực đại. Bài toán tổng quát của QHTT có dạng:∑=nj 1cjxj → max (1)∑=nj 1aiixj (≤,=,≥) bi, i=1, ….,m (2)xj ≥ 0, j=1,…,n (3)10Luận án tốt nghiệp Nếu gặp bài toán Min, tức là:)(xf= ∑=nj 1cjxj → minx ∈ D thì giữ nguyên ràng buộc và đưa về bài toán Max bằng cách)(xf= - ∑=nj 1 cjxj → maxNếu bài toán Max có phương án tối ưu là x* thì bài toán Min cũng có phương án là x* và maxmin ff−=b) Dạng chuẩn và dạng chính tắc :Người ta thường xét bài toán QHTT dưới hai dạng sau:(1) Dạng chuẩn:∑=nj 1cjxj → max∑=nj 1aiixj ≤ bi , i=1, ….,mxj ≥ 0, j=1,…,n(2) Dạng chính tắc:∑=nj 1cjxj → max∑=nj 1aiixj = bi , i=1, ….,mxj ≥ 0, j=1,…,n11Luận án tốt nghiệp 2. MỘT SỐ TÍNH CHẤT CHUNG : Tập hợp tất cả các phương án của một bài toán QHTT là tập lồi. Hàm mục tiêu của bài toán QHTT sẽ đạt MAX tại điểm cực biên của tập D. Nếu hàm mục tiêu không chỉ nhận MAX tại một điểm cực biên của tập lồi D mà tại nhiều điểm cực biên thì nó sẽ đạt giá trò cực đại tại những điểm là tổ hợp lồi của các điểm đó. Nếu các vectơ A1,A2,….,Ak là độc lập tuyến tính và thỏa mãnx1 A1 + x2 A1 + … + xkAk = btrong đó xj > 0, j=1,……,k thì điểmx=( x1 ,x2 , ,xk, 0,…,0)là điểm cực biên của tậo lồi đa diện D. Để x=( x1 ,x2 , ,xn) là phương án cực biên của QHTT dưới dạng chính tắc thì cần và đủ là các véctơ cột Aj của ma trận A ứng với các thành phần xj > 0 là độc lập tuyến tính. 3. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI QHTT Cơ sở của phương pháp này được Dantzig công bố năm 1947 có tên gọi là phương pháp đơn hình. Sở dó có tên gọi như vậy là vì những bài toán đầu tiên được giải bằng phương pháp đó có các ràng buộc dạng:∑=nj 1xj = 1, xj ≥ 0, j=1,…,nmà tập các điểm x ∈ Rn thỏa mãn các ràng buộc trên là một đơn hình trong không gian n chiều.a) Đường lối chung của thuật toán :12Luận án tốt nghiệp Phương pháp đơn hình dựa trên hai nhận xét sau : nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của D là phương án tối ưu, đa diện lồi D có một số hữu hạn đỉnh. Như vậy phải tồn tại thuật toán hữu hạn. Thuật toán gồm hai giai đoạn: Giai đoạn 1: tìm một phương án cực biên (một đỉnh).  Giai đoạn 2: kiểm tra điều kiện tối ưu đối với phương án tìm được ở giai đoạn 1. Nếu điều kiện tối ưu được thỏa mãn thì phương án đó là tối ưu. Nếu không, ta chuyển sang phương án cực biên mới sao cho cải tiến giá trò hàm mục tiêu. Tiếp theo lại kiểm tra điều kiện tối ưu đối với phương án mới.Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương án tối ưu, hoặc đến tình huống bài toán không có phương án tối ưu.b) Thuật toán đơn hình :Giả sử ta đã đưa QHTT về dạng chính tắc:cx = Z → maxAx = b Bước 1 : xây dựng bảng đơn hình xuất phát. Tìm một phương án cực biên xuất phát x và cơ sở của nó Aj, j ∈ J Xác đònh các số zjk bởi hệ phương trình:∑∈J jzjk Aj = Ak Đối với mỗi k ∉ J, tính các ước lượng:∆k = ∑∈J jzjk cj - ckcòn với j ∈ J thì ∆j = 0. Tính giá trò hàm mục tiêu13Luận án tốt nghiệp Z0 = ∑∈J jcj xj Bước 2 : kiểm tra tối ưuNếu ∆k ≥ 0, ∀k ∉ J thì x là phương án tối ưu, dừng thuật toán. Trái lại, chuyển sang bước 3. Bước 3 : tìm véctơ đưa vào cơ sở. Có 2 khả năng xảy ra: Tồn tại k ∉ J sao cho ∆k < 0 và zjk ≤ 0, ∀ j ∈ J thì bài toán QHTT không có lời giải tối ưu (Z không bò chặn trên). Dừng thuật toán. Đối với mỗi k ∉ J sao cho ∆k < 0 đều tồn tại j ∈ J: zjk > 0. Khi đó chọn chỉ số s theo tiêu chuẩn:∆s = min ∆k | ∆k < 0đưa véctơ AS vào cơ sở. Bước 4 : tìm véctơ loại khỏi cơ sở. Xác đònh:S = min  xj / zrs | zjs > 0 = xr / zrsvà đưa véctơ Ar ra khỏi cơ sở. Bước 5 : chuyển sang phương án cực biên mới và cơ sở mới. Cở sở mới là Aj | j ∈ J’ với J’=J \ {r} U {s}. Phương án cực biên mới x’ được tính theo công thức khác, khai triển các véctơ AK theo các véctơ cơ sở mới được tính theo công thức :Sau đó quay lên bước 2.Chú ý: Đối với bài toán min{<c,x> | Ax = b, x ≥ 0} thì tiêu chuẩn tối ưu là ∆k≤ 0 (∀k) và véctơ AS được chọn đưa vào cơ sở theo công thức:14zjk – (zrk / zrs) zjs, nếu j ≠ rzrk / zrs nếu j = rz’jk =Luận án tốt nghiệp ∆s = max ∆k | ∆k > 0, k ∉ J4. THUẬT TOÁN ĐƠN HÌNH CẢI BIÊN :Quá trình tính toán của phương pháp đơn hình cải biên được bố trí trong 2 bảng sau.Bảng 1:b1 bma11 a1S a1n am1 amS amn∆ (1)∆ (2)∆1 ∆S ∆n∆1 ∆S ∆nTrong bảng 1, m+1 dòng đầu lưu các hệ số aij, bi, cj của bài toán. Từ dòng m+2 trở đi của bảng 1 lưu các ước lượng ∆ j của từng bước lặp theo công thức ∆K=cJZk – ck = cJ AJ-1 - ckBảng 2:cJAJq0q1 qmASθcj+1 cjr cjmAj1 Ajr Ajmq10 qr0 qm0q11 q1m qr1 qrm qm1 qmmz1s zrs zmsqm+1,0qm+1,1 qm+1,m∆SBảng này gọi là bảng đơn hình cải biên. Cột cJ ghi hệ số hàm mục tiêu ứng với các biến cơ sở. Cột AJ ghi các véctơ cơ sở, do đó ta cũng nhận được chỉ số các biến cơ sở. Cột q0 : m phần tử đầu là phương án cực biên đang xét, phần tử cuối là trò số hàm mục tiêu. Ma trận nghòch đảo cơ sở AJ-1 : m dòng đầu của các cột q1, ,qm. Dòng cuối cùng của các cột q1, , qm : phương án của bài toán đối ngẫu, nó được tính theo công thức:(qm+1,1, , qm+1,m) = cJ AJ-115Luận án tốt nghiệp Cột AS : m phần tử đầu của cột là khai triển của véctơ đưa vào cơ sở AS theo cơ sở, phần tử cuối chính là ∆S.Thuật toán đơn hình cải biên gồm các bước: Bước 0 : xây dựng bảng đơn hình xuất phát. Giả sử ta có cơ sở Aj , j ∈ J và phương án cực biên x. Tính ma trận nghòch đảo Aj-1(điền vào m dòng đầu của các cột q1, , qm). Tính m phần tử đầu của cột q0 theo :AJxJ = b suy ra xJ = AJ-1bvàqm+1,0 = <cJ, xJ>Tính dòng m+1 ứng với các cột q1, , qm : qm+1,j là tích vô hướng của cột qj với cột cJ. Bước 1 : Tìm cột quay và kiểm tra tối ưu.Tính ước lượng các cột theo công thức :∆K = cJZk – ck = cJ AJ-1 - ckvới ∆K là tích vô hướng của dòng m+1 thuộc bảng 2 với cột j của bảng 1. Nếu ∆j ≥ 0 với mọi j thì phương án cực biên đang xét là tối ưu. Trái lại, ta xác đònh véctơ AS đưa vào cơ sở theo công thức :∆S = min ∆j | ∆j < 0, j ∉ J Bước 2 : tìm dòng quay.Trước tiên tính cột quay, tức cột AS của bảng 2 theo công thức: lấy cột AS của bảng 1 nhân vô hướng với từng dòng của ma trận AJ-1 ta sẽ được từng phần tử của cột AS thuộc bảng 2. Phần tử cuối của cột AS bảng 2 lấy là ∆S.Nếu zjs ≤ 0 với mọi j ∈ J thì hàm mục tiêu bài toán quy hoạch tuyến tính không bò chặn trên. Nếu trái lại ta xác đònh véctơ Ar loại khỏi cơ sở theo công thức:θS = qr0 / zrs = J∈ jmin qj0 / zjs | zjs > 016Luận án tốt nghiệp cột θ trong bảng 2 để lưu qj0 / zjs với j ∈ J Bước 3 : Biến đổi ma trận nghòch đảo mở rộng. Đưa AS vào cơ sở thay cho Ar và biến đổi toàn bộ các cột q0, , qm theo công thức :phần tử chính của phép biến đổi là zrs. Quay lên bước 1.II. QUY HOẠCH ĐỐI NGẪU :Khái niệm đối ngẫu là một trong các khái niệm cơ bản của QHTT. Trong rất nhiều trường hợp để có được những kết luận chấp nhận được cho một trong các bài toán trên thì việc nghiên cứu bài toán đối ngẫu của nó lại tỏ ra thậun tiện hơn. Hơn nữa khi phân tích song song một cặp bài toán đối ngẫu ta có thể nhận được những kết luận hay, cả về toán học và cả về ý nghóa kinh tế.1. QHTT DƯỚI DẠNG CHUẨN, CẶP BÀI TOÁN TUYẾN TÍNH ĐỐI NGẪU ĐỐI XỨNG:Cho QHTT dưới dạng chuẩn:(P) <c,x> = z → minAx ≥ bx ≥ 0Ta gọi đối ngẫu của nó là bài toán QHTT dạng:(P’) <b,y> = ω → maxA’y ≤ c y ≥ 0 ở đây A’ là ma trận chuyển vò của A, y là véctơ cột có m phần tử.2. QHTT DƯỚI DẠNG CHÍNH TẮC, CẶP BÀI TOÁN TUYẾN TÍNH ĐỐI NGẪU KHÔNG ĐỐI XỨNGXét bài toán17qjk – (qrk / zrs) zjs, nếu j ≠ rqrk / zrs nếu j = rq’jk =Luận án tốt nghiệp <c,x> = z (min)Ax = bx ≥ 0Để chuyển về dạng chuẩn ta thay ràng buộc Ax=b bởi hai ràng buộc Ax ≥ b và –Ax ≥ -b. Khi ấy ta thay (1) và (2) bởi<A’,y1> - <A’,y2> ≤ c, y1≥ 0, y2≥ 0Đặt y = y1 – y2, y không bò ràng buộc về dấu và ta có quy hoạch đối ngẫu của dạng chính tắc:<b,y> = ω → maxA’y ≤ c3. CẶP BÀI TOÁN ĐỐI NGẪU TỔNG QUÁT Xét bài toán gốc:(G) ∑=nj 1cjxj → min∑=nj 1aijxj = bi, i ∈ I1∑=nj 1aijxj ≥ bi, i ∈ I2∑=nj 1aijxj ≤ bi, i ∈ I3xj , j ∈ J1 không có ràng buộc về dấuxj ≥ 0, j ∈ J2 , xj ≤ 0 , j ∈ J3trong đó | I1| + | I2| + | I3| =m, | J1| + | J2| + | J3| =n. Đối ngẫu với nó là bài toán:∑=nj 1biyi → max∑=nj 1aijyi = cj, j ∈ J118Luận án tốt nghiệp ∑=nj 1aijyi ≤ cj, j ∈ J2∑=nj 1aijyi ≥ cj, j ∈ J3yj , i ∈ I1 không có ràng buộc về dấuyj ≥ 0, i ∈ I2 , yj ≤ 0 , i ∈ I34. Ý NGHĨA CẶP BÀI TOÁN ĐỐI NGẪU a) Ý nghóa toán học Khi có cj ≥ 0, ∀j thì biết ngay được một phương án cực biên của bài toán đối ngẫu.Nếu y là phương án cực biên của bài toán đối ngẫu thì khi bài toán gốc thêm một ràng buộc ta có (y,0) vẫn là phương án cực biên của bài toán đối ngẫu.Đôi khi dùng cặp bài toán đối ngẫu để giải gần đúng theo ý nghóa sau: giải cả hai bài toán và nếu hiệu giữa các giá trò tương ứng của các hàm mục tiêu đủ nhỏ thì dừng lại và phương án cực biên thu được lấy làm nghiệm gần đúng.b) Ý nghóa kinh te áGiả sử bài toán (P) mang nội dung kinh tế sau. Có n phương pháp khác nhau để sản xuất m loại sản phẩm. Khi sử dụng một đơn vò thời gian cho phương pháp j sẽ thu được đồng thời aij đơn vò sản phẩm i (i=1, , m) và mất một chi phí là cj. Nhu cầu xã hội về sản phẩm là bi (i=1, , m). Hãy xác đònh các khoảng thời gian xj sử dụng mỗi phương pháp j (j=1, , m) sao cho tổng chi phí sản xuất là nhỏ nhất với điều kiện tổng số đơn vò sản xuất là nhỏ nhất với điều kiện tổng số đơn vò sản phẩm i mỗi loại sản xuất ra không ít hơn bi (i=1, , m).Hình thức hóa bài toán:19Luận án tốt nghiệp ∑=nj 1[chi phí cho một đơn vò thời gian ụng phương pháp j ].[khoảng thời gian sử dụng phương pháp j] = Tổng chi phí → Min.∑=nj 1[số đơn vò sản phẩm i thu được khi sử dụng một đơn vò thời gian cho phương pháp j].[khoảng thời gian sử dụng phương pháp j] ≥ [nhu cầu xã hội về sản phẩm i], i=1, ,m.[khoảng thời gian sử dụng phương pháp j] ≥ 0, j = 1, ,nNội dung bài toán đối ngẫu (P’) sẽ là:Trong những điều kiện như trên hãy tìm một hệ thống giá trò yi (i=1, ,m) sao cho tổng giá trò toàn bộ sản phẩm theo yêu cầu xã hội đạt giá trò cực đại với điều kiện tổng các giá trò các sản phẩm sản xuất theo từng phương pháp j trong một đơn vò thời gian không vượt quá chi phí sản xuất cj.Hình thức hóa bài toán:∑=mi 1[nhu cầu xã hội về sản phẩm i] . [giá trò đơn vò sản phẩm i] = [Tổng giá trò sản phẩm] → Max.∑=mi 1[số đơn vò sản phẩm i thu được khi sử dụng một đơn vò thời gian cho phương pháp j]. [giá trò đơn vò sản phẩm i] ≤ [chi phí cho một đơn vò thời gian phương pháp j], j=1, ,n.[giá trò đơn vò sản phẩm i] ≥ 0, i = 1, ,mĐể thích hợp ta sẽ gọi phương án x của bài toán (P) là phương án sản xuất, phương án của bài toán (P’) là phương án đánh giá. Từ đònh lý về độ lệch bù ta suy ra:(i) Nếu một phương án sản xuất được sử dụng (xj > 0) thì tổng giá trò các sản phẩm sản xuất thep phương pháp ấy phải đúng bằng chi phí.(ii)Nếu một phương án có giá trò (yi ≥ 0) thì tổng số đơn vò sản phẩm ấy sản xuất ra phải đúng bằng nhu cầu.20Luận án tốt nghiệp Các vấn đề nêu trên hoàn toàn phù hợp với lý luận kinh tế, đồng thời có thể dùng làm căn cứ để xác đònh hệ thống giá cả sản phẩm, có tác dụng thúc đẩy sản xuất.5. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU :Nội dung của thuật toán là ta áp dụng thuật toán đơn hình để giải bài toán đối ngẫu nhưng ta lại diễn tả quá trính trong ngôn ngữ của bài toán gốc, và bằng cách đó ta tìm được nghiệm của bài toán gốc.Giả sử ta đã biết một phương án cực biên y0 của bài toán đối ngẫu (P’), tức là ta biết một cơ sở đối ngẫu { Aj ≤ 0 , j ∈ J} sao cho∆j = 0 (∀j ∈ J) và ∆j ≤ 0 (∀j ∉ J) Bước 1 : Xây dựng bảng đơn hình ban đầu cho giả phương án x với cơ sở đã cho. Bảng đơn hình vẫn bố trí như củ. Cột phương án tính theo công thức: xJ=AJ-1b. Hàm mục tiêu: f = < cJ, xJ >. Khai triển của véctơ Ak theo các véctơ cơ sở: ZK = AJ-1 Ak. Dòng ước lượng tính theo công thức : ∆k=<cJ,ZK> - ck. Bước 2 : kiểm tra tiêu chuẩn tối ưu cho giả phương án x. Nếu xj ≥ 0, ∀j ∈ J, khi đó x là phương án tối ưu của bài toán (P), dừng tính toán. Trái lại, nếu tồn tại xj < 0, j ∈ J thì chuyển sang Bước 3. Bước 3 : xác đònh dòng quay. Có thể xảy ra một trong các trường hợp sau: Tồn tại xj < 0 và zjk ≥ 0, ∀k ∉ J. Khi đó hàm mục tiêu của bài toán đối ngẫu không bò chặn trên, do đó bài toán (P) không có phương án chấp nhận được, dừng tính toán. Đối với mỗi xj > 0, j ∈ J đều tồn tại k ∉ J sao cho zjk < 0. Khi đó chọn dòng quay theo công thức:xr = J∈ jmin{ xj | xj < 0}Véctơ Ar bò đưa ra khỏi cơ sở J. Bước 4 : xác đònh cột quay. Xác đònh bước dòch chuyển theo công thức:θS = ∆s / zrs = min  ∆k / zrk | zrk < 0, k ∉ J 21Luận án tốt nghiệp Véctơ AS bò đưa ra khỏi cơ sở. Bước 5 : biến đổi bảng đơn hình. Cơ sở đối ngẫu mới  Aj , j ∈ J’ trong đó J’ = J\ {r} U {s}. Biến đổi bảng đơn hình theo công thức với zrs là phần tử chính. Kết quả ta nhận được giả phương án mới x’. Quay lại Bước 2.III.QUY HOẠCH TUYẾN TÍNH DẠNG ĐẶC BIỆT 1. PHƯƠNG PHÁP PHÂN RÃ QUY HOẠCH TUYẾN TÍNH Phương pháp phân ra trong quy hoạch tuyến tính do G.B. Dantzig và P.Wolfe đề xuất năm 1960. Xét bài toán quy hoạch tuyến tính mà các ràng buộc phân thành hai khối:L(X) = <C,X> → max. (1)A(0)X = B(0)(2)A(1)X = B(1)(3)X ≥ 0 (4)Trong đó C, X ∈ Rn ,A(0) là ma trận m hàng n cột, A(1) là ma trận m1 hàng n cột, B(0) ∈ Rm , B(1) ∈ Rm1. Giả sử tập hợp G xáx đònh bởi (3)-(4) là bò chặn và nó có các đỉnh là X1,X2, ,XN. Theo đònh lý biểu diễn tập hợp lồi, với mọi điểm X ∈ G ta có:X = ∑=Nv 1zvXv∑=Nv 1zv = 1, zv ≥ 0, v=1, ,N.Công thức này cho phép biến đổi X của bài toán (1)-(4) sang biến zv:22zjk – (zrk / zrs) zjs, nếu j ≠ rzrk / zrs nếu j = rz’jk =Luận án tốt nghiệp ∑=Nv 1<C, Xv>zv → max∑=Nv 1( A(0) Xv)zv = B(0)∑=Nv 1zv = 1, zv ≥ 0, v=1, ,N.ký hiệu σv = <C, Xv>, Pv = A(0) Xv , bài toán trên viết lại thành∑=Nv 1σv zv → max (5)∑=Nv 1Pvzv = B(0)zv ≥ 0, v=1, ,N.Để giải bài toán (5) tại mỗi bước lặp chỉ cần biết m+1 véctơ điều kiện lập nên cơ sở. Còn việc chọn véctơ đưa vào cơ sở sẽ được tiến hành nhờ giải một bài toán quy hoạch tuyến tính phụ với điều kiện (3)-(4)2. PHƯƠNG PHÁP KARMARKAR Thuật toán Karmarkar có nhiều điểm chung với thuật toán đơn hình. Trước hết đó là: cả hai đều là các thuật toán lặp và đều xuất phát từ một phương án chấp nhận được của bài toán cần giải. Thứ hai là, ở mỗi bước lặp cả hai thuật toán đều di chuyển từ một phương án hiện có tới một phương án tốt hơn. Cuối cùng, quá trình này đều được lặp đi lặp lại cho đến khi đạt tới phương án tối ưu.Sự khác nhau cơ bản giữa hai thuật toán là ở bản chất của các phương án cần kiểm tra. Trong phương pháp đơn hình, các phương án kiểm tra là những phương án cực biên và việc di chuyển dọc theo cạnh trên biên của miền ràng buộc. Còn trong thuật toán Karmarkar, phương án kiểm tra là các điểm trong không nằm trên biên của miền ràng buộc. Vì thế, thuật toán Karmarkar và các biến thể của nó có tên gọi là các thuật toán điểm trong hay đường trong.23Luận án tốt nghiệp Hơn nữa, trong thuật toán Karmarkar sự di chuyển đi theo hướng làm cải tiến giá trò mục tiêu với tốc độ nhanh nhất có thể, đồng thời sau mỗi bước lặp tiến hành biến đổi miền ràng buộc để đưa phương án hiện có vào gần tâm của miền, nhờ đó tạo khả năng thực hiện tốt nhất việc di chuyển tiếp theo. Việc làm này được gọi là thay đổi thước đo (rescaling) trong quá trình giải bài toán.Để áp dụng được phương pháp Karmarkar, trước hết ta cần đưa bài toán về dạng chính tắcmin f = cTx : Ax = b, x ≥ 0Giả sử là x0 một phương án của bài toán này. Phương pháp Karmarkar đòi hỏi x0 phải thuộc phần trong của miền ràng buộc, nghóa là x0 không được chọn nằm trên một cạnh hay siêu phẳng tựa của miền đó. Trong phương pháp đơn hình, phương án cực biên có ít nhất n – m thành phần bằng 0, còn ở đây mọi thành phần của x0 đòi hỏi phải khác không. Ta phải tìm phương án mới x1 sao cho gần hơn với phương án tối ưu của bài toán. Giả sử x1 = x0 + d. Ta sẽ tìm cách chọn d theo yêu cầu này, muốn thế không những phải chọn d theo yêu cầu này, muốn thế không những phải chọn hướng của véctơ mà cả độ dài của nó sao cho đảm bảo x1 vẫn còn thuộc phần trong của miền ràng buộc. Để ý rằng hàm mục tiêu tại x1 bằng:cTx1 = cTx0 + cTdVì đây là bài toán tìm cực tiểu nên đại lượng cTd phải âm và về giá trò tuyệt đối càng lớn càng tốt, có như thế hàm mục tiêu sẽ giảm một lượng nhiều nhất có thể. Hơn nữaA x1 = A x0 + AdĐể cho x1 cũng là phương án, ta phải có A x1 = b hay Ad = 0. Cuối cùng, x1 phải là véctơ không âm, nghóa làx1 = x0 + d ≥ 0 hay d ≥ – x0Véctơ d cần tìm phải thỏa mãn tất cả các điều kiện vừa nêu trên. Cho z là một véctơ bất kỳ. Khi đó véctơ 24Luận án tốt nghiệp Pz = (I – AT (A AT)-1 A)z = z - AT (A AT)-1Azsẽ thỏa mãn A(Pz) = 0. Thật vậy:A(Pz) = Az - AT (A AT)-1Az = Az – Az = 0.Nếu ta đặt z = -c và chọn d = -Pc thì cTd là số âm lớn nhất có thể về giá trò tuyệt đối.Như vậy, ta đã tìm được hướng dòch chuyển tốt nhất là (-Pc). Vấn đề còn lại là chọn độ dài của véctơ này sao cho x1 vẫn còn thuộc phần trong của miền ràng buộc, bởi vì ta phải đảm bảo không đi quá gần tới biên. Muốn thế ta chọnx1 = x0 - 0,98 * s * || PcPc,trong đó s là khoảng cách từ x0 tới biên (có thể tính dựa theo bất đẳng thức d ≥ - x0) và -|| PcPc là véctơ có độ dài bằng 1 theo hướng của véctơ –Pc.IV. QUY HOẠCH PHI TUYẾN 1. CỰC TIỂU HÀM LỒI MỘT BIẾN THEO PHƯƠNG PHÁP LÁT CẮT VÀNGa) Phát biểu bài toán Tìm cực tiểu hàm lồi một biến f(x) trên đoạn [u,v] thuộc đường thẳng số thực R1. Hàm một biến f(x) gọi là lồi trên đoạn [u,v] nếu thỏa mãn:f(λx+(1 - λ)y) ≤ λf(x) + (1 - λ)f(y)∀x,y ∈ [u,v], λ ∈ (0,1).b) Thuật toán giải Thuật toán lát cắt vàng sử dụng hai hằng số (gọi là các hằng số Phi-bô-nát-si):25

Trích đoạn

• (2)CÁC PHƯƠNG THỨC BIÊN HÓA CỤA THUAƠT GIẠI DI TRUYEĂN
• CƠ SỞ SINH HĨC
• Đôi với bài toán tôi ưu moơt múc tieđu: “ ≤” : đôi với bài toán lây min
• GIẠI THUAƠT CHUYEƠN ĐOƠI TỪ DÁNG TRUNG TÔ SANG HAƠU TÔ BA LAN NGƯỢC

Tài liệu liên quan

• Điều kiện tối ưu cho một số lớp bài toán tối ưu hai cấp
  • 104
  • 548
  • 0
• Nghiên cứu một số bài toàn mở rộng: vận tải ba chỉ số không hạn chế và có hạn chế khả năng thông qua, bài toán vận tải ba chỉ số khoảng và giới thiệu một số bài toán vận tải đa mục tiêu
  • 64
  • 862
  • 2
• Bài toán vận tải đa mục tiêu.
  • 79
  • 527
  • 0
• Bài toán vận tải đa mục tiêu
  • 79
  • 549
  • 0
• Bài toán quy hoạch đa mục tiêu
  • 36
  • 768
  • 0
• Xấp xỉ hữu hạn chiều cho bài toán cực trị đa mục tiêu không chỉnh các phiếm hàm lồi trong không gian Banach. docx
  • 9
  • 486
  • 0
• Nghiên cứu ứng dụng giả thuật di truyền cho bài toán điều khiển tối ưu đa mục tiêu
  • 94
  • 661
  • 0
• Điều kiện tối ưu cấp một và cấp hai cho bài toán tối ưu trong không gian vectơ tôpô
  • 23
  • 623
  • 0
• Tối ưu số cho bài toán tối ưu một mục tiêu
  • 85
  • 724
  • 1
• Phương pháp đại số cho bài toán ước lượng hợp lý cực đại áp dụng trên cây sinh loài nhỏ
  • 73
  • 405
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(4.62 MB - 85 trang) - Tối ưu số cho bài toán tối ưu một mục tiêu Tải bản đầy đủ ngay ×