Chương 1: Bài toán tối ưu. Chương này trình bày khái quát về các vấn đề liên quan tới các bài toán. tối ưu đồng thời mô tả rõ bài toán vận tải. Chương 2: Giải thuật đi truyền và tìm kiếm Tabu.
'Nội dung chương này là những nghiên cứu về giải thuật đi truyền và tim kiếm Tabu làm cơ sở cho chương 3. Chương 3: Kết hợp Giải thuật dĩ truyền va tim kiém Tabu giải bài toán vận tai Chương này trình bây giải pháp kết hợp Giải thuật di truyễn và tìm kiếm Tabu gidi bai toin vận tải đồng thời lập trình thử nghiệm trên các bài toán cụ thể. CHUONG1 BÀI TOAN TOIUU Chương này sẽ giới thiệu tổng quan về bài toán tối tu, bài toamsquy. hoạch tuyến tính tông quát, bài toán vận tãi tuyến tính.
Trình bày thuật toán thé vi giải bài toán vận tải bằng thuật và đưa ra kết quả. Các khái niệm và kết quả trong chương này được tham khảo trong [3], [5]. Giới thiệu bài toán tối ưu tông quát Lý thuyết tối ưu là một trong lĩnh vực kinh điển của toán học có nhiều ảnh hưởng đến nhiều lĩnh vực khoa học công nghệ, kinh tế xã hội. Một phương án tối ưu là một phương án khả thi và tốt nhất, tức là phương ân làm cho hàm mục tiêu đạt két qui min (max) va phải thỏa mãn các điều kiện yêu cầu của bài toán (thõa mãn các điều kiện ràng buộc).
Trong mô hình toán học, mục tiêu của bài toán được biểu di A(x) + min(max) vớix là một biến hoặc vecto biénx = (Xi, Xa,. Xe) Biển x hoặc vectơ biến Xa) thường có yêu cầu phải thỏa. mãn một số điều kiện nào đó. Tập hợp các điều kiện của các biển thì được gọi là.
điều kiện rang bude va được biễu diễn bởi miễn D (miền ràng buộc). "Dạng tổng quát của bài toán tối ưu: Lâm cực tiễu cực đại một hàm mục tiêu: (8) —smin(mas) (1) Théa min các điều kiện rằng buộc: _ xe D (2) Yêu cầu: Tim x để thỏa mãn (2) và làm cực tiễu/ cực đại hàm mục tiêu (1) x* (một bộ các giá trị cụ thể của (Xị, x;, xu). thỏa mãn điều kiện (1) & (2) gọi là phwong an t6i uu. Néu x chi théa man diéu kién (2) gọi x là phương án.
chấp nhận được hay phương án. Vidy: Timx sao cho : Ñx) = Š- 3 + 1 —> max (3) Với: xe D=[-22; 1,8] @) Voi Ý xe [22; 1,8] là một phương án © -22<x< 1,8 - Bài toán tương đương bài toán tìm giá trị lớn nhất (GTLN) của Rx) khi 225x518 Phuong pháp tìm GTLN (đã học trong giải tich 1) thực hiện như sau: ~ Tìm các cực trị của f(x) , tính các giá trị cực trị, tính các giá trị tại các đầu. mút của miền D, sau đó so sánh để tìm ra giá trị lớn nhất (hay nhỏ nhất). — Tim các điểm đừng Ấx) = 0.
Tinh f(x) tại các điểm đừng.2) 81,8) = 1432 Do dé fs) max = 3 khi x* Các bài toán tối ưu chính là các bài toán qui hoạch toán học - Bài toán tối ưu tuyến tính: hàm mục tiêu và tắt cả các ràng buộc đều có đạng. - Bài toán tối ưu phi tuyến: trong d6 ham mục tiêu hoặc it nhất một điều kiện. ràng buộc là phi tuyến (cô chứa ít nhất một yếu tố phi tuyến bậc 2, logic, mi.) - Bài toán tối ưu rời rac: khi bién hodc gia trị hàm mục tiêu là rời rạc. Có thê chia như sau: Tối ưu nguyên (quy hoạch nguyên): các biến hoặc các hàm mục tiêu nhận các giá trị ng én, Tối ưu đỗ thị: là một đạng đặc biệt của bài toán tối ưu rời rạc.
định là các điểm rời rac. Tim đường đi ngắn nhất của đồ thị thỏa mãn điều kiện nào đô. - Bài toán quy hoạch động (những kết quả của bài toán ở bước sau thì phụ 'thuộc vào kết quả của bước trước). Đ®—@>—<Ð>—<4) - Bài toán tối ưu đa mục tiêu: là bài toán trong đó có nhiễu hàm mục tiêu cần hải tối ưu trên cùng một miễn ràng buộc.nvéix €D Trong đồ cô nhiều hàm mục tiêu có thé đối lập nhau.
Khi giải bài toán này phải kết hợp hài hòa các lợi ích (giá trị) đạt được của hàm mục tiêu.3 Ứng dụng của lý thuyết tối ưu. Nhiều vấn đề thực tế, kinh tế, khoa học và xã hội đều có thể giải quyết ‘bing phương pháp tối ưu toán học. Quan trọng là từ thực tẾ phải xây dựng. một mô hình toán học thích hợp.
Tử đó sử dụng phương pháp tối ưu đễ giải cũng với công cụ thích hợp. Các bước cần thiết khi áp đụng phương pháp mô hình hóa: Bước 1: Khão sát vấn đề thực tế, phát hiện vấn đề cần giải quyết bằng phương pháp tối ưu. "Bước2: Phát biếu các điều kiện ràng buộc và hàm mmục tiêu đưới dạng định tính. "Bước 3: Lựa chọn các biến quy định và sau đó định lượng hóa các điều kiện rang buộc và hàm mục tiêu.
Từ đồ xây dựng mô hình định lượng và mô hình toán học (mô hình tối ưu). "Bước 4: Thu thập số liệu và lựa chọn phương pháp toán học thích hợp để giải mô hình. "Bước 5: Xây đựng thuật toán và quy tình giải. Lựa chọn công cụ (giấy bút, máy tính) có thể lập trình cho bài toán Ấy Bước 6: Đánh giá kết quả thu được.
Nếu phù hợp thực tế nó cho kết quả tối ưu. 'khi đó chứng tô mô hình chúng ta xây đựng đúng, hợp lý, vì vậy chấp nhận kết quả. ấu không phù hợp thực tế thì phải xem xét và điều chỉnh mô hình. Kết luận: Cần có sự hợp tác của các chuyên gia chuyên ngành (chẳng hạn kỹ thuật điện, điệntỡ.), chuyên gia về tin học, toán học để giải quyết các bài toán thực tế.
‘Mot số thuật ngữ trong quá trình xây dựng mô hình: - _ Toán ứng dụng (Applied Mathematic) - _ Vận tri hoc (Operation Research ~OR) - Khoa hoc quan ff (Management Science ~ MS) - _ Ứng dung may tinh (Computer Application) ~_ Mô hình tối wu (Optimization models) - _ Quy hoạch Programming) 1. Bài toán quy hoạch tuyến tính tổng quát Bài toán quy hoạch tuyến tính (QHTT) tổng quát có dạng, ~ Tìm cực đại (cực tiểu) của hàm: Z=C| X; +; X; +. +C,X, —> may / min © thôa mãn các điều kiện rằng buộc: aus + am +. + đun € Dị aaxt + a2 +.
taixe > bE © HN + agÑ+. + yNg = Dị AmIXị + am2Xg +.x+ >0 vớiken Trong đó: Z ~ fỢX) gọi là hàm mục tiêu của bài toán, (6, 2. Xe) fa vecton thành phần (một bộ n giá trị hay còn gọi là một diém trong không gian n chiều). C¡¿ Các hệ số của hàm mục tiêu(j = 1.
n) Hệ điều kiện (6) gọi là hệ rang buộc, trong đó một số điều kiện ràng 'buộc đạng bắt đẳng thức ( < ), một số ràng buộc đạng bất đẳng thức ( > ), một số ràng buộc đạng đẳng thức (=). Các biến quyết định (có thể không phải là tất cã) có điều kiện không âm. Miền D xác định bởi hệ ràng buộc gọi là miễn. "Ma trận của hệ rằng buộc có dang ana.
ais an ana. ate ut Qed. de "Một phương án (hay phương án khả thì) là một vecto X = (, X,. x, ) thôa mãn hệ rang buộc (6).
Rõ rằng mọi điểm (;, x,. x, ) thuộc miễn rằng buée D déu là một phương án, vì vậy miễn D còn gọi là tập phương án. Phương án tối tu (optimal solution) là một phương án, mà giá trị ham mục tiêu tại đồ đạt cực đại (hay cục ). Phương án tối ưu thường được ký: hiệu là X* hay X-opt 1.
Bài toán vận tải tuyến tính ‘Noi dung bài toán Giả sử cần vận chuyên một loại hàng thuần nhất (vật tư, lương thực.) từm địa điểm cung cấp (điểm phát) A¡, A;.A„ đến n địa điểm tiêu thụ (điểm. thu) Bị, Bà. Bọ biết rằng: - Số lượng hàng cô ở A: là a: (¡ = 1.m) - Số lượng hàng cần ở B; là b; (j = 1. - Chỉ phí vận chuyên một đơn vị hàng từ A; đến B, là cạ (¡ = 1.
Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các địa điểm cung cấp đến các địa điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất và thỏa mãn nhu cầu thu phát. Bài toán vận tải là tuyến tính nếu chỉ phí tỉ lệ với số lượng hàng vận tải ‘M6 hinh toan hge ciia bai toan Goi xy 14 số lượng hàng cần vận chuyên từ A: đến B,. Ta có: Š Š⁄,x; : tổng chỉ phí van chuyển +, : số lượng hang cho di tA: i= 1m. 3x, -s6 luong hing ché t6i tirB) j= 1.
‘Vay mô hình toán học của bài toán là: fx) =, Dex, — min (cực tiêu tổng chỉ phí) với các điều kiện: >> (ạ>0,i=i.n) _Với mô hình toán học của bài toán trên áp đụng phương pháp thể vị để tìm ra kết quả tối ưu. Phương pháp thể vị Phuong án cực biên: x = {xạ} là phương án cực biên khi và chỉ khi tập hop các ô (1, ) tương ứng với các thành phần đương của phương án không tạo thành vòng. Một phương án cực biên có tối đa m + n — 1 thành phần đương. Tập hợp m + n — 1 6 không tạo thành vòng bao him tập ô tương ứng với các thành phần đương của phương án cực biên x (x5 > 0) gọi là tập ô cơ sở nó, ký hiệu là S.j) € S gọi là ô cơ sở, (ij) € S gọi là ô phí cơ sở.
Một ô phi cơ sở kỷ bao giờ cũng tạo thành một vòng duy với các ô cơ sở. Một phương án cực biên không suy biến chỉ có một tập ô cơ sỡ đuy nhất, đô chính là tập ô tương ứng với các thành phần đương của phương án. Một phương án. cực biên suy biến cô nhiều tập ô cơ sở khác nhau, phần chung của chúng là tập ô ứng với các thành phần đương.
“Xây dựng phương án cực biên Khi xác định được x; = 0., ta nói là đã phân phối cho ô (, j) mét lượng hàng la a. Nguyên tắc phân phối tối đa: Lấy ô (, j) bất kỳ của bảng và phân phối cho nó một lượng hàng tối đa có thể, nghĩa 14 dat xy = min bị. Ba tring hợp có thễ xây ra: cầu của trạm phát thỏa mãn, loại hàng i ra khỏi bảng, đồng axy = b , yêu cầu của trạm thu thỏa mãn, loại cột j ra khỏi bảng, đồng, thời sửa lại yêu cầu cia tram phat: a°:= ai ‘byxy = a = bị ,yêu cầu của cả trạm thu và phát đều thỏa mãn, loại đồng, thời hàng ¡ và cộtj ra khôi bảng.