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

ó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. Phần 1 TỔNG QUAN 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. 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. 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. 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. Phần 2 GIỚI THIỆU CÁC PHƯƠNG PHÁP TỐI ƯU CỔ ĐIỂN MỞ ĐẦU ĐỐ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. 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àm f(x) ® max (min) (1) với các điều kiện gi(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. 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 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. VẤN ĐỀ MÔ HÌNH HÓA TOÁN HỌC 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ả. 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. MỘT số mô hình thực tế: Bài toán lập kế hoạch sản xuất. Bài toán vận tải. Bài toán cái túi. CÁC LOẠI BÀI TOÁN TỐI ƯU VÀ PHƯƠNG PHÁP CỔ ĐIỂN 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. BÀI TOÁN quy hoạch tuyến tính 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: cjxj ® max (1) aiixj (£,=,³) bi, i=1, ….,m (2) xj ³ 0, j=1,…,n (3) Nếu gặp bài toán Min, tức là: = cjxj ® min x Ỵ D thì giữ nguyên ràng buộc và đưa về bài toán Max bằng cách = - cjxj ® max Nế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à 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: Dạng chuẩn: cjxj ® max aiixj £ bi , i=1, ….,m xj ³ 0, j=1,…,n Dạng chính tắc: cjxj ® max aiixj = bi , i=1, ….,m xj ³ 0, j=1,…,n 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ãn x1 A1 + x2 A1 + ….. + xkAk = b trong đó xj > 0, j=1,……,k thì điểm x=( 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. 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: xj = 1, xj ³ 0, j=1,…,n mà 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. Đường lối chung của thuật toán: 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. Thuật toán đơn hình: Giả sử ta đã đưa QHTT về dạng chính tắc: cx = Z ® max Ax = 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: zjk Aj = Ak Đối với mỗi k Ï J, tính các ước lượng: Dk = zjk cj - ck còn với j Ỵ J thì Dj = 0. Tính giá trị hàm mục tiêu Z0 = cj xj Bước 2: kiểm tra tối ưu Nếu Dk ³ 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 Dk < 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 Dk 0. Khi đó chọn chỉ số s theo tiêu chuẩn: Ds = min íDk | Dk < 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 / zrs và đư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 : zjk – (zrk / zrs) zjs, nếu j ¹ r zrk / zrs nếu j = r z’jk = Sau đó quay lên bước 2. Chú ý: Đối với bài toán min{ | Ax = b, x ³ 0} thì tiêu chuẩn tối ưu là Dk£ 0 ("k) và véctơ AS được chọn đưa vào cơ sở theo công thức: Ds = max íDk | Dk > 0, k Ï Jý 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 ... bm a11 ........ a1S ........ a1n .... ....... ..... ........ .... am1 ........ amS ........ amn D (1) D (2) D1 ........ DS ........ Dn D1 ........ DS ........ Dn Trong 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 D j của từng bước lặp theo công thức DK=cJk – ck = cJ AJ-1 - ck Bảng 2: cJ AJ q0 q1 .... qm AS q cj+1 ... cjr ... cjm Aj1 ... Ajr ... Ajm q10 ... qr0 ... qm0 q11 ... q1m ... ... .... qr1 .... qrm ... .... ... qm1 .... qmm z1s ... zrs ... zms qm+1,0 qm+1,1 .... qm+1,m DS Bả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-1 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à DS. 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-1b và qm+1,0 = 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 : DK = cJk – ck = cJ AJ-1 - ck với DK 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 Dj ³ 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 : DS = min íDj | Dj < 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à DS. 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: qS = qr0 / zrs = í qj0 / zjs | zjs > 0ý cột q 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 : qjk – (qrk / zrs) zjs, nếu j ¹ r qrk / zrs nếu j = r q’jk = phần tử chính của phép biến đổi là zrs. Quay lên bước 1. 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ế. 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) = z ® min Ax ³ b x ³ 0 Ta gọi đối ngẫu của nó là bài toán QHTT dạng: (P’) = w ® max A’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ử. 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ứng Xét bài toán = z (min) Ax = b x ³ 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 - £ 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: = w ® max A’y £ c Cặp bài toán đối ngẫu tổng quát Xét bài toán gốc: (G) cjxj ® min aijxj = bi, i Ỵ I1 aijxj ³ bi, i Ỵ I2 aijxj £ bi, i Ỵ I3 xj , j Ỵ J1 không có ràng buộc về dấu xj ³ 0, j Ỵ J2 , xj £ 0 , j Ỵ J3 trong đó | I1| + | I2| + | I3| =m, | J1| + | J2| + | J3| =n. Đối ngẫu với nó là bài toán: biyi ® max aijyi = cj, j Ỵ J1 aijyi £ cj, j Ỵ J2 aijyi ³ cj, j Ỵ J3 yj , i Ỵ I1 không có ràng buộc về dấu yj ³ 0, i Ỵ I2 , yj £ 0 , i Ỵ I3 Ý nghĩa cặp bài toán đối ngẫu Ý 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. Ý nghĩa kinh tế 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: [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. [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,...,n Nộ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: [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. [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: 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í. 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. 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. 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 Dj = 0 ("j Ỵ J) và Dj £ 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 = . Khai triển của véctơ Ak theo các véctơ cơ sở: K = AJ-1 Ak. Dòng ước lượng tính theo công thức : Dk= - 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 = { 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: qS = Ds / zrs = min í Dk / zrk | zrk < 0, k Ï J ý 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 zjk – (zrk / zrs) zjs, nếu j ¹ r zrk / zrs nếu j = r z’jk = 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. QUY HOẠCH TUYẾN TÍNH DẠNG ĐẶC BIỆT 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) = ® 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 = zvXv zv = 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: zv ® max ( A(0) Xv)zv = B(0) zv = 1, zv ³ 0, v=1,....,N. ký hiệu sv = , Pv = A(0) Xv , bài toán trên viết lại thành sv zv ® max (5) vzv = (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) 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. 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ắc min í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 + cTd Vì đâ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ữa A 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 ³ – x0 Vé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ơ Pz = (I – AT (A AT)-1 A)z = z - AT (A AT)-1Az sẽ 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ọn x1 = x0 - 0,98 * s * , 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à - là véctơ có độ dài bằng 1 theo hướng của véctơ –Pc. QUY HOẠCH PHI TUYẾN CỰC TIỂU hàm lồi một biến theo phương pháp lát cắt vàng 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(lx+(1 - l)y) £ lf(x) + (1 - l)f(y) "x,y Ỵ [u,v], l Ỵ (0,1). 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): F1 = (3 - )/2 » 0.38197, F2 = ( - 1)/2 = 1- F2 » 0.61803 Hai số này có tính chất đặc biệt : F1 = (F2)2. Thuật toán lát cắt vàng tìm cực tiểu hàm f(x) gồm các bước sau: Bước 1: Chia ba đoạn [u,v] bởi các điểm w1, w2 và tính giá trị của hàm tại các điểm này, tức là tính w1 = u + F1 * (v - u), z1 = f(w1), w2 = u + F2 * (v - u), z2 = f(w2). Bước 2: So sánh z1 và z2, nếu z1 £ z2 thì chuyển tới Bước 3, nếu z1 > z2 thì chuyển tới Bước 4. Bước 3: Lấy đoạn [u’,v’] mới với u’ = u, v’ = w2. Nếu |v’ – u’| £ e thì điểm cực tiểu là x* = w1 và f(x*) = z1, dừng tính toán. Nếu |v’ – u’| > e thì chia đoạn [u’,v’] thành ba đoạn bởi hai điểm chia w1’, w2’: Điểm w2’ lấy chính là điểm w1 cũ, như vậy z2’=f(w2’) = z1. Điểm được w1’ tính theo công thức: w1’ = u’ + F1 * (v’ – u’), sau đó tính z1’ = f(w1’). Chuyển tới Bước 2 với sự thay đổi vai trò z1, z2 bởi z1’, z2’. Bước 4: Lấy đoạn [u’,v’] mới với u’ = w1, v’ = v. Nếu |v’ – u’| £ e thì điểm cực tiểu là x* = w2 và f(x*) = z2, dừng tính toán. Nếu |v’ – u’| > e thì chia đoạn [u’,v’] thành ba đoạn bởi hai điểm chia w1’, w2’: Điểm w1’ lấy chính là điểm w2 cũ, như vậy z1’=f(w1’) = z2. Điểm được w2’ tính theo công thức: w2’ = u’ + F2 * (v’ – u’), sau đó tính z2’ = f(w2’). Chuyển tới Bước 2 với sự thay đổi vai trò z1, z2 bởi z1’, z2’. Ưu điểm cơ bản của phương pháp lát cắt vàng: đoạn [u’,v’] của một bước được chia làm ba đoạn bởi các điểm chia w1’, w2’ nhưng chỉ cần tính giá trị của hàm tại một điểm mới, điều đó giảm được đáng kể thời gian tính toán so với các phương pháp khác. Ưu điểm này có được chính là do tính chất đặc biệt của các số Phi-bô-nát-si. Thuật toán trên cũng dùng để tìm cực đại một hàm lõm h(x). Khi đó Max h(x)=-Min f(x) với f(x) = - h(x) và f(x) lỗi. QUY HOẠCH toàn phương Các dạng bài toán cơ bản Quy hoạch toàn phương là bài toán tìm cực tiểu của hàm lồi bậc hai với các ràng buộc tuyến tính. Có ba dạng bài toán cơ bản: Dạng chính tắc: f(x) = p0 + 2 + ® min Ax = b, x ³ 0, trong đó: x = (x1, x2,..., xn)T là véctơ biến cần tìm; C – ma trận vuông đối xứng cấp n nửa xác định dương (nghĩa là ³ 0 với mọi x); A – ma trận cấp m,n; p – véctơ n thành phần; b – véctơ m thành phần; p0 – hằng số (thông thường p0 =0). Giả thiết mọi thành phần của b không âm (nếu cần thì đổi dấu cả hai vế của phương trình ràng buộc). Dạng chuẩn: f(x) ._.