QUI HOẠCH TUYẾN TÍNH

Chia sẻ: Gray Swan | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

268
lượt xem 80
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

CHƯƠNG 2 QUI HOẠCH TUYẾN TÍNH Kết thúc chương này, sinh viên có thể: 1. Nắm được những thành phần và các dạng khác nhau của bài toán 2. Có thể thực hiện chuyển đổi giữa các dạng bài toán 3. Xây dựng bài toán 4. Nắm được các phương pháp giải các bài toán 5. Hiểu được bài toán đối ngẫu và thực hiện biến đổi giữa bài toán đối ngẫu và bài toán gốc 6. Hiểu được phân tích độ nhạy và sử dụng chúng trong phân tích 7. Biết được các bài toán qui hoạch nguyên và ứng dụng...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: QUI HOẠCH TUYẾN TÍNH

CHƯƠNG 2 QUI HOẠCH TUYẾN TÍNH Kết thúc chương này, sinh viên có thể: 1. Nắm được những thành phần và các dạng khác nhau của bài toán 2. Có thể thực hiện chuyển đổi giữa các dạng bài toán 3. Xây dựng bài toán 4. Nắm được các phương pháp giải các bài toán 5. Hiểu được bài toán đối ngẫu và thực hiện biến đổi giữa bài toán đối ngẫu và bài toán gốc 6. Hiểu được phân tích độ nhạy và sử dụng chúng trong phân tích 7. Biết được các bài toán qui hoạch nguyên và ứng dụng của nó 8. Sử dụng được các phần mềm phổ biến để giải các bài toán
Mục lục 26 2.1. Đặt vấn đề 2.2. Những dạng bài toán qui hoạch 2.3. Những phương pháp giải bài toán qui hoạch tuyến tính 2.4. Bài toán đối ngẫu 2.5. Phân tích độ nhạy 2.6. Qui hoạch nguyên
2.1. Đặt vấn đề 27 Trong thực tế, tồn tại nhiều bài toán qui hoạch tuyến tính đáp ứng nhiều nhu cầu khác nhau trong nghiên cứu. Tuy nhiên, xét theo hàm mục tiêu, các bài toán qui hoạch tuyến tính có thể chia thành hai bài toán cơ bản sau: Bài toán cực đại, Bài toán cực tiểu. Cách thức xây dựng, dạng và các thành phần của bài toán này như thế nào?
2.1.1. Bài toán cực đại đơn giản 28 ABC là công ty nhỏ chuyên sản xuất sản phẩm hoá chất. Trong quá trình sản xuất, có 3 nguyên liệu thô được dùng để sản xuất 2 sản phẩm: chất phụ gia, bazơ hoà tan. Ba nguyên liệu thô được pha trộn thành chất phụ gia và bazơ hoà tan như trên Bảng: Sản phẩm Khả năng cung ứng (tấn) Chất phụ gia Bazơ hoà tan Nguyên liệu 1 0,4 0,5 20 Nguyên liệu 2 0,2 5 Nguyên liệu 3 0,6 0,3 21 Lợi nhuận mỗi tấn 40 30
Xây dựng bài toán 29 Xác định biến quyết định F = số tấn chất phụ gia được sản xuất B = số tấn bazơ hoà tan được sản xuất Hàm mục tiêu : Max 40F + 30B Các ràng buộc 0,4F + 0,5B ≤ 20 Nguyên liệu 1 0,2B ≤ 5 Nguyên liệu 2 0,6F + 0,3B ≤ 21 Nguyên liệu 3 F, B ≥ 0
2.1.2. Bài toán cực tiểu đơn giản 30 Công ty hoá chất M&D sản xuất 2 sản phẩm A và B để bán làm nguyên liệu cho các công ty sản xuất xà phòng. Dựa trên mức tồn kho hiện tại và nhu cầu tiềm tàng cho tháng tới, các nhà quản trị xác định tổng mức sản xuất trong tháng tới của cả hai sản phẩm ít nhất 350 galông. Riêng sản phẩm A phải không ít hơn 125 galông. Thời gian để sản xuất sản phẩm A, B tương ứng là 2 giờ/galông và 1giờ/galông. Trong tháng đến, tổng quỹ thời gian là 600 giờ. Chi phí sản xuất sản phẩm A và B tương ứng là 2$/galông và 3$/galông. Mục tiêu của công ty M&D là cực tiểu tổng chi phí sản xuất.
Xây dựng bài toán 31 Ký hiệu: A = số galông sản phẩm A được sản xuất, B = số galông sản phẩm B được sản xuất. Bài toán: Min 2A+3B Ràng buộc 1A ≥ 125 Nhu cầu của sản phẩm A 1A+1B ≥ 350 Nhu cầu tổng 2 sản phẩm 2A+1B ≤ 600 Thời gian sản xuất A,B ≥ 0
2.1.3. Những ký hiệu chung của bài toán QHTT 32 Ký hiệu: x1= số tấn chất phụ gia được sản xuất x2= số tấn chất bazơ hoà tan được sản xuất Khi đó, bài toán RMC có dạng như sau: Max (40x1 + 30x2) Ràng buộc 0,4x1 + 0,5x2 ≤ 20 Nguyên liệu 1 0,2x2 ≤ 5 Nguyên liệu 2 0,6x1 + 0,3x2 ≤ 21 Nguyên liệu 3 x1, x2 ≥ 0
2.1.3. Những ký hiệu chung của bài toán QHTT 33 Ký hiệu: x1= số galông sản phẩm A được sản xuất x2= số galông sản phẩm B được sản xuất Khi đó, bài toán M&D sẽ có dạng như sau: Min (2x1+3x2) Ràng buộc 1x1 ≥ 125 Nhu cầu của sản phẩm A 1x1+1x2 ≥ 350 Nhu cầu tổng các sản phẩm 2x1+1x2 ≤ 600 Thời gian sản xuất x1, x2 ≥ 0
2.2. Những dạng bài toán qui hoạch 34 2.2.1. Những thành phần của bài toán 2.2.2. Các dạng bài toán qui hoạch tuyến tính 2.2.3. Biến đổi dạng của bài toán qui hoạch a. Đưa dạng tổng quát về dạng chính tắc b. Đưa dạng chính tắc về dạng chuẩn
2.2.1. Những thành phần của bài toán 35 Hàm mục tiêu (Objective function), đây là hàm tuyến tính của các biến quyết định và có thể đạt cực trị. Các ràng buộc (Constraints) là những phương trình hay bất phương trình tuyến tính thể hiện sự kết hợp các biến quyết định. Các ràng buộc về dấu của các biến quyết định: các biến quyết định trong những bài toán trong kinh tế thường không âm. Tuy nhiên, trong trường hợp tổng quát, các biến có thể nhận giá trị âm.
Dạng tổng quát (theo ký hiệu thông thường) 36 n n f ( x ) = ∑ c j x j → min(max ) hay Min (Max )∑ c j x j Hàm mục tiêu j=1 j=1 Ràng buộc ⎧n ⎪ ∑ a ij x j = b i i ∈ I 1 ⎪ j=1 ⎪n ⎨ ∑ a ij x j ≤ b i i ∈ I 2 ⎪ j=1 ⎪n ⎪ ∑ a ij x j ≥ b i i ∈ I 3 ⎩ j=1 Ràng buộc dấu: xj≥0 (j∈J1); xj≤0 (j∈J2); xj tuỳ ý (j∈J3)
Ví dụ: 37 Max (3x1 − x 2 + 2x3 + x 4 + 5x5 ) S.t. 2x1 − x 2 + x 3 + 2x 4 + x5 ≤ 17 4x1 − 2x 2 + = x3 20 x1 − x 2 + 2x3 + x 5 ≥ − 18 x1 + x 2 + 2x3 ≤ 100 x4 x1 , x 4 ≥ 0; x 2 , x 5 ≤ 0; x 3 tùy ý I1={2}, I2={1,4} và I3={3} J1={1,4}, J2={2,5} và J3={3}
Dạng chính tắc (Theo ký hiệu thông thường) 38 n n Hàm mục tiêu f ( x ) = ∑ c j x j → min(max ) hay Min (Max)∑ c j x j j=1 j=1 n ∑a x j =b i i ∈ I1 Ràng buộc Chỉ là phương trình ij j =1 xj≥0 (j∈J1) Ràng buộc dấu : Không âm
Dạng chính tắc (ký hiệu ma trận) 39 Min (Max) cx Ax = b x≥0 Trong đó: ⎛ a 11 ... a 1n ⎞ a 12 ... a 1 j ⎡ x1 ⎤ ⎡ b1 ⎤ ⎡0 ⎤ ⎜ ⎟ ⎢x ⎥ ⎢b ⎥ ⎢0 ⎥ ⎜ a 21 a 22 ... a 2 j ... a 2 n ⎟ ⎢ 2⎥ ⎢ 2⎥ ⎢⎥ ⎜ ... ... ... ⎟ ⎢ Μ⎥ ⎢ Μ⎥ ... ... ... ⎢Μ ⎥ A=⎜ ⎟ x=⎢ ⎥ b=⎢ ⎥ 0=⎢ ⎥ ⎜ a i1 ... a in ⎟ a i2 ... a ij ⎢x j ⎥ ⎢ bi ⎥ ⎢0 ⎥ ⎜ ... ... ... ⎟ ⎢ Μ⎥ ⎢ Μ⎥ ... ... ... ⎢Μ ⎥ ⎜ ⎟ ⎢⎥ ⎢⎥ ⎢⎥ ⎜a ⎟ a m2 ... a mj ... a mn ⎠ ⎢x n ⎥ ⎢b m ⎥ ⎣⎦ ⎣⎦ ⎝ m1 ⎢0 ⎥ ⎣⎦ c = (c1 c 2 Κ cn )
Dạng chuẩn 40 n n Hàm mục tiêu f (x) = ∑ c j x j → min(max) hay Min(Max)∑ c j x j j=1 j=1 Ràng buộc + a1(m+1) x(m+1) + Κ + a1nxn = b1 ⎧x1 ⎪x + a2(m+1) x(m+1) + Κ + a2nxn = b2 ⎪ 2 ⎨ Ο Κ Κ ΚΚΚ Κ ΚΚ ⎪ ⎪ + am(m+1) x(m+1) + Κ + amnxn = bm xm ⎩ Ràng buộc dấu: xj≥0 ∀j=1,…,n và bi ≥0 ∀i=1,…,m
Dạng chuẩn (Theo ký hiệu ma trận) 41 Min (Max) cx S.t. Không âm (b≥0) Ax = b x≥0 Trong đó: Λ Λ ⎛1 a1n ⎞ 0 0 a1( m +1) ⎜ ⎟ Λ Λ ⎜0 1 0 a 2( m +1) a 2n ⎟ A=⎜ Λ⎟ Λ Λ Λ Λ Λ Λ ⎜ ⎟ ⎜0 a mn ⎟ Λ a m ( m +1) Λ 0 1 ⎝ ⎠ Ma trận đơn vị cấp m
Nhận xét 42 Bài toán dạng chuẩn là bài toán dạng chính tắc có thêm các điều kiện: Các số hạng tự do ở vế phải không âm; Ma trận các hệ số các ràng buộc A có chứa một ma trận đơn vị cấp m. Hàm mục tiêu: Min (3x1-x2+x3-3x4+x5) Ràng buộc 2x1+ x2- x3 + x4 = 10 2x1-2x2+ x3 + x6 = 20 x1 - x2+2x3 +x5 = 18 xj ≥0 ∀j=1,…,6
Một số khái niệm 43 Một tập giá trị của các biến quyết định thỏa mãn các ràng buộc của bài toán gọi là phương án của bài toán. Các biến ứng với các véc tơ cột đơn vị trong ma trận A được gọi là các biến cơ bản. Các biến còn lại là các biến không cơ bản. Biến cơ bản ứng với véc tơ đơn vị thứ i gọi là biến cơ bản thứ i. Một phương án mà các biến không cơ bản bằng 0 gọi là phương án cơ bản. Một phương án cơ bản có đủ m thành phần dương gọi là không suy biến; có ít hơn m thành phần dương gọi là suy biến.
2.2.3. Biến đổi dạng của bài toán qui hoạch 44 Bài toán qui hoạch tuyến tính tồn tại nhiều dạng khác nhau: dạng tổng quát, dạng chính tắc và dạng chuẩn. Trong thuật toán giải bài toán qui hoạch tuyến tính bằng phương pháp đơn hình đòi hỏi bài toán ở dạng chuẩn. Chính vì vậy, cần phải chuyển bài toán dạng tổng quát, dạng chính tắc về dạng chuẩn. Dạng chuẩn Dạng chính ttắc Dạng ttổng quát Dạng chuẩn Dạng chính ắc Dạng ổng quát