Chương 1 BÀI TOÁN VẬN TẢI Nội dung của chương được tham khảo ở các tài liệu [1], [2], [3], [4]. Bài toán quy hoạch tuyến tính 1. Mô hình một số bài toán thực tế Chương này sẽ trình bày những kiến thức cơ bản nhất của bài toán quy hoạch tuyến tính. Dantzig đã đưa ra mô hình toán học này sau khi nghiên cứu các bài toán lập kế hoạch cho lực lượng không quân Mỹ.
Ban đầu, ông gọi là "Quy hoạch trong cấu trúc tuyến tính" (Programming in a linear structure). Dantzig đã đồng ý sử dụng tên gọi ngắn gọn là "Quy hoạch tuyến tính" (Linear Programming) sau khi được Tijalling Koopmans góp ý. Nhiều năm sau, Albert Tuckey dùng thuật ngữ ngắn hơn là "Linear Program". Ngay sau khi G.
Dantzig đưa ra mô hình quy hoạch tuyến tính, người ta thấy nhiều bài toán thực tế thuộc nhiều lĩnh vực khác nhau có thể mô tả bằng mô hình bài toán quy hoạch tuyến tính. Bài toán lập kế hoạch sản xuất (Production Planning Prob- lem). Công ty Reddy Mikks sản xuất hai loại sản phẩm là sơn nội thất và sơn ngoài trời. Nguyên liệu gồm hai loại A và B với nguồn dự trữ tương ứng là 60 tấn và 80 tấn.
Để sản xuất một tấn sơn nội thất cần 2 tấn nguyên liệu A, 1 tấn nguyên liệu B và để sản xuất một tấn sơn ngoài trời cần 1 tấn nguyên liệu A, 2 tấn nguyên liệu B. Được biết nhu cầu thị trường sử dụng hai loại sản phẩm này trong một ngày là: - Nhu cầu sơn nội thất không hơn nhu cầu sơn ngoài trời quá 1 tấn; - Nhu cầu cực đại của sơn nội thất là 2 tấn. Giá bán buôn 1 tấn sơn nội thất là 2000 USD, 1 tấn sơn ngoài trời 4 là 3000 USD. Vấn đề đặt ra là cần sản xuất mỗi ngày như thế nào để doanh thu là lớn nhất.
Gọi x1 là số lượng sơn nội thất cần sản xuất trong một ngày; Gọi x2 là số lượng sơn ngoài trời cần sản xuất trong một ngày; x1 , x2 gọi là các biến (variable) hay là một phương án (alternative) của bài toán. Vì sản lượng sản phẩm phải là một số thực không âm, nên x1 ≥ 0, x2 ≥ 0, đơn vị tính là tấn. Khi đó doanh thu trong một ngày thu được sẽ là F (x) = 2000x1 + 3000x2 và F được gọi là hàm mục tiêu (objective funtion). Mặt khác, số lượng sản phẩm được sản xuất x1 , x2 không thể vượt quá số lượng nguyên liệu dự trữ hạn chế.
Các hạn chế trên các biến x1 , x2 gọi là các ràng buộc (constraint), cụ thể là: ( 2x1 + x2 ≤ 60 x1 + 2x2 ≤ 80 Hơn nữa, việc sản xuất lại phải đảm bảo không nhiều hơn nhu cầu của thị trường, do đó: ( x1 − x2 ≤ 1 x1 ≤2 Ta gọi cặp sắp thứ tự (x1 , x2 ) gọi là phương án chấp nhận được (feasible) nếu nó thoả mãn mọi ràng buộc. Ta có mô hình toán học của bài toán lập kế hoạch sản xuất như sau: Tìm phương án chấp nhận được làm hàm mục tiêu F (x) đạt cực đại max và được biểu diễn dưới dạng toán học dưới đây: F (x) = 2000x1 + 3000x2 → max 2x1 + x2 ≤ 60 x1 + 2x2 ≤ 80 x1 − x2 ≤ 1 x1 ≤2 x1 ≥ 0, x2 ≥ 0 Ví dụ 1. Bài toán phân công lao động. Ta xét một bài toán cụ thể sau đây: 5 Một đội sản xuất cần phân công một số người đi gặt, số còn lại thì ở nhà đập lúa.
Cả đội có 12 lao động loại A, 26 lao động loại B và 16 lao động loại C. Năng suất làm việc của lao động loại A trong một ngày gặt được 2 sào và đập được 5 sào; tương ứng với lao động loại B là 1, 8 và 3, 6; lao động loại C là 1, 5 và 2, 4. Hãy phân công lao động sao cho gặt được nhiều nhất và số lúa được gặt về cũng được đập hết trong ngày. Gọi x, y, z lần lượt là số lao động các loại A, B, C được phân công để đi gặt lúa, x ≥ 0, y ≥ 0, z ≥ 0.
Khi đó số lao động ở nhà đập lúa tương ứng là: 12 − x, 26 − y và 16 − z. Mặt khác, hai công việc phải đảm bảo cân đối, nên: 2x + 1, 8y + 1, 5z = 5(12 − x) + 3, 6(26 − y) + 2, 4(16 − z) hay 7x + 5, 4y + 3, 9z = 192 Khi đó mô hình toán học của bài toán này là: F (x) = 2x + 1, 8y + 1, 5z → max 0 ≤ x ≤ 12 0 ≤ y ≤ 26 0 ≤ z ≤ 16 x, y, z ∈ Z 7x + 5, 4y + 3, 9z = 192 Ví dụ 1. Bài toán vận tải (Transportation Problem). Ta xét một dạng bài toán tổng quát.
Trong quá trình sản xuất, hàng hoá được vận chuyển từ 02 kho A, B đến 02 cửa hàng bán lẻ I, II. Lượng hàng ở kho A 15 tấn, kho B 15 tấn và nhu cầu tiêu thụ ở kho I là 10 tấn, kho II là 20 tấn. Cước phí vận chuyển một tấn hàng hoá từ kho A đến hai cửa hàng I, II tương ứng là 1 triệu VNĐ, 3 triệu VNĐ và kho B đến hai cửa hàng I, II tương ứng là 2 triệu VNĐ, 5 triệu VNĐ: Yêu cầu đặt ra là hãy lập kế hoạch vận chuyển hàng hoá từ kho A, B đến cửa hàng thứ I, II sao cho tổng chi phí là ít nhất, với điều kiện các kho phát hết hàng và các siêu thị, cửa hàng nhận đủ số hàng hoá theo nhu cầu. Gọi lượng hàng vận chuyển từ kho i đến cửa hàng j là xij (i = 1, 2; j = 1, 2; xij ≥ 0).
Ta có kế hoạch vận chuyển, hay còn gọi là phương án vận chuyển hàng hoá là một ma trận thực cấp 2 × 2, X = (xij ). Khi đó cước phí vận chuyển hàng hoá là F (x) = x11 + 3x12 + 2x21 + 5x22. 6 Ta phải tìm các xij sao cho F là nhỏ nhất. Chú ý rằng xij ≥ 0 không được giảm tùy ý, vì phải đảm bảo phải phát hết hàng ở các kho và các cửa hàng phải nhận đủ số hàng theo nhu cầu.
Ta có: x11 + x12 = 15 x + x = 15 21 22 x11 + x21 = 10 x12 + x22 = 20 Khi đó, mô hình toán học của bài toán vận tải này như sau: F (x) = x11 + 3x12 + 2x21 + 5x22 → min x11 + x12 = 15 x21 + x22 = 15 x11 + x21 = 10 x12 + x22 = 20 xij ≥ 0, i = 1, 2; j = 1, 2. Mô hình này gọi là mô hình vận tải đóng (close transportation model) hay còn gọi là mô hình vận tải cân bằng vì khả năng phát và khả năng thu bằng nhau. Trong trường hợp khả năng phát và khả năng thu khác nhau thì mô hình bài toán của chúng ta gọi là mô hình vận tải mở (open transportation model) hay mô hình vận tải không cân bằng. Các bài toán trên đều dẫn đến một mô hình chung là tìm nghiệm của hệ ràng buộc sao cho một hàm mục tiêu F (x) đạt max hoặc min.
Đây chính là mô hình tổng quát của bài toán tối ưu. Bài toán quy hoạch tuyến tính Bài toán quy hoạch tuyến tính có dạng tổng quát đầy đủ như sau: n X F (x) = cj xj → min(max) (1.1) j=1 n X aij xj ≥ bi , (i = 1, 2, .2) j=1 Xn aij xj = bi , (i = m1 + 1, m1 + 2, .4) 7 trong đó F (x) gọi là hàm mục tiêu. Một ràng buộc đẳng thức có thể thay thế bằng hai ràng buộc dạng bất đẳng thức, cụ thể là: Xn aij xj ≥ bi n X j=1 aij xj = bi ⇔ Xn − aij xj ≥ −bi j=1 j=1 Một ẩn xj nào đó không bị ràng buộc về dấu có thể được thay bằng hai ẩn không âm bằng cách đặt: xj = x0j − x0n+j ; x0j ≥ 0, x0n+j ≥ 0, ( x0j = max{0, xj } trong đó: x0n−j = max{0, −xj }. Như vậy, mọi bài toán quy hoạch tuyến tính đều có thể đưa được về dạng chuẩn tắc sau đây: n X F (x) = cj xj → min(max) (1.5) j=1 n X aij xj ≥ bi , (i = 1, 2, .7) Mặt khác, một ràng buộc bất đẳng thức có thể đưa về ràng buộc dạng đẳng thức bằng cách bổ sung thêm ẩn phụ, cụ thể: n X n X aij xj ≥ bi ⇔ aij xj − yi = bi , yi ≥ 0 j=1 j=1 Việc thêm ẩn phụ yi cùng điều kiện không âm của nó không làm ảnh hưởng đến kết quả của bài toán.
Khi đó ta có dạng chính tắc của bài toán quy hoạch tuyến tính: n X F (x) = cj xj → min(max) (1.8) j=1 n X aij xj = bi , (i = 1, 2, .10) 8 Định lý sau đây cho ta thấy phép biến đổi đó không làm thay đổi bản chất của bài toán., αn ) của bất phương trình: n X aij xj ≥ bi j=1 ứng với một nghiệm duy nhất Y = (α1 , α2 , ., αn , αn+1 ) của hệ: X n aij xj − yi = bi j=1 yi ≥ 0 và ngược lại., αn ) sao cho: n X aij αj ≥ bi. j=1 Tiếp theo ta chọn: n X yi = αn+1 = aij αj − bi ., αn , αn+1 ) thoả mãn hệ: n X aij xj − yi = bi j=1 yi ≥ 0. Ngược lại, nếu Y = (α1 , α2 , ., αn , αn+1 ) thoả mãn: n X aij αj − αn+1 = bi j=1 α1 , ., αn , αn+1 ≥ 0, thì ta có ngay: n X aij αj ≥ bi j=1 n X hay X = (α1 , α2 , ., αn ) thoả mãn bất đẳng thức aij xj ≥ bi. Đưa bài toán sau đây về dạng chính tắc: F (x) = 2x1 − 3x4 + x5 + 2x6 → min − 3x4 x1 + x2 + 2x6 = 5 2x2 − 3x3 + x4 + x5 ≤4 3x1 − x2 + 2x3 − 2x5 ≥3 x1 , x2 , x5 , x6 ≥ 0 Đầu tiên ta đưa thêm hai ẩn phụ x7 ≥ 0, x8 ≥ 0 để đưa các ràng buộc về dạng đẳng thức.