CHƯƠNG 1 BÀI TOÁN TỐI ƯU Chương này sẽ giới thiệu tổng quan về bài toán tối ưu, bài toansquy 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ế vị 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 quả min (max) và 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ễn bởi hàm: f(x) ® min(max) với x là một biến hoặc vecto biến x = (x1, x2, …. , xn) Biến x hoặc vectơ biến x = (x 1, x2, …. , xn) 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 ràng buộc và đượ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: f(x) ®min(max) (1) Thỏa mãn các điều kiện ràng buộc: x Î D (2) Yêu cầu: Tìm 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 1, x2, …. , xn)) , thỏa mãn điều kiện (1) & (2) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 gọi là phương án tối ưu. Nếu x chỉ thỏa mãn điều kiện (2) gọi x là phương án chấp nhận được hay phương án.
Ví dụ: Tìm x sao cho : f(x) = x3 - 3x + 1 ® max (3) Với: x Î D = [-2,2; 1,8] (4) Với " x Î [-2,2; 1,8] là một phương án Û -2,2 £ 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 f(x) khi -2,2 £ x £ 1,8 Phương pháp tìm GTLN (đã học trong giải tích 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). Tính f(x) tại các điểm dừng Tìm f(-2,2) ; f(1,8) Vậy f(x) = 3x2 – 3 = 0 Û x = ± 1 f(1) = -1 f(-1) = 3 f(-2,2) = -3,048 f(1,8) = 1,432 Do đó f(x) max = 3 khi x* = -1 1. Phân loại các bài toán tối ưu 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ó dạng tuyến tính. - Bài toán tối ưu phi tuyến: trong đó hàm mục tiêu hoặc ít 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, mũ…).
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 - Bài toán tối ưu rời rạc: khi biến hoặc giá 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ị nguyên. Tối ưu đồ thị: là một dạng đặc biệt của bài toán tối ưu rời rạc. Có các đỉnh là các điểm rời rạc.
Tìm đườ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). - 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 phải tối ưu trên cùng một miền ràng buộc.,n với x Î 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 bằng 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 dụng phương pháp mô hình hóa: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 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ước 2: Phát biếu các điều kiện ràng buộc và hàm mục tiêu dướ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 ràng 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 dựng thuật toán và quy trì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 dựng đúng, hợp lý, vì vậy chấp nhận kết quả. Nế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ế. Một số thuật ngữ trong quá trình xây dựng mô hình: - Toán ứng dụng (Applied Mathematic) - Vận trù học (Operation Research – OR) - Khoa học quản lý (Management Science – MS) - Ứng dụng máy tính (Computer Application) - Mô hình tối ưu (Optimization models) - Quy hoạch (Programming) LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 = C1 x1 + C2 x2 +. + Cn xn max / min (5) thỏa mãn các điều kiện ràng buộc: a11x1 + a12x2 + … + a1nxn ≤ b1 …………………….
ai1x1 + ai2x2 + … + ainxn ≥ bi ……………………. (6) aj1x1 + aj2x2 + … + ajnxn = bj ……………………. am1x1 + am2x2 + … + amnxn = bm x+,x+,…x+ ≥ 0 với k ≤ n Trong đó: Z = f(X) gọi là hàm mục tiêu của bài toán, X = (x 1, x2,…, xn ) là vecto n thành phần (một bộ n giá trị hay còn gọi là một điểm trong không gian n chiều). Cj: Các hệ số của hàm mục tiêu (j = 1, 2, …, n) Hệ điều kiện (6) gọi là hệ ràng buộc, trong đó một số điều kiện ràng buộc dạng bất đẳng thức ( < ), một số ràng buộc dạng bất đẳng thức ( > ), một số ràng buộc dạ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 ràng buộc. Ma trận của hệ ràng buộc có dạng: a11 a12 … a1n a21 a22 … a2n LUAN VAN CHAT LUONG download : add luanvanchat@agmail. am1 am2 … amn Một phương án (hay phương án khả thi) là một vectơ X = (x1, x2,…, xn ) thỏa mãn hệ ràng buộc (6).
Rõ ràng mọi điểm (x 1, x2,…, xn ) thuộc miền ràng buôc 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 ưu (optimal solution) là một phương án, mà giá trị hàm mục tiêu tại đó đạt cực đại (hay cục tiểu). Phương án tối ưu thường được ký hiệu là X* hay X-opt. Bài toán vận tải tuyến tính Nội 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) A1, A2…Am đến n địa điểm tiêu thụ (điểm thu) B1 , B2…Bn biết rằng: - Số lượng hàng có ở Ai là ai (i = 1.m) - Số lượng hàng cần ở Bj là bj (j = 1.
- Chi phí vận chuyển một đơn vị hàng từ Ai đến Bj là cij (i = 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 chi phí tỉ lệ với số lượng hàng vận tải. Mô hình toán học của bài toán Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Ta có: m n ∑ ∑ c ij x ij i=1 j =1 : tổng chi phí vận chuyển m ∑ x ij i=1 : số lượng hàng chở đi từ Ai. n ∑ x ij j=1 :số lượng hàng chở tới từ Bj. Vậy mô hình toán học của bài toán là: m n ∑ ∑ c ij x ij f(x) = i=1 j =1 → min (cực tiểu tổng chi phí) với các điều kiện: n m ∑ x ij ∑ x ij j=1 = bi ; i=1 = aj (xij > 0, i = i.n) Với mô hình toán học của bài toán trên áp dụng phương pháp thế vị để tìm ra kết quả tối ưu. Phương pháp thế vị: Phương án cực biên: x = {xij} là phương án cực biên khi và chỉ khi tập hợp các ô (i, j) tương ứng với các thành phần dươ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 dương. Tập hợp m + n – 1 ô không tạo thành vòng bao hàm tập ô tương ứng với các thành phần dương của phương án cực biên x (x ij > 0) gọi là tập ô cơ sở nó, ký hiệu là S. Ô (i, j) ∈ S gọi là ô cơ sở, (i, j) ∉ S gọi là ô phi cơ sở. Một ô phi cơ sở bất kỳ bao giờ cũng tạo thành một vòng duy nhất 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ở duy nhất, đó chính là tập ô tương ứng với các thành phần dươ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 dương. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Xây dựng phương án cực biên Khi xác định được x ij = α , ta nói là đã phân phối cho ô (i, j) một lượng hàng là α.