Giáo trình Toán ứng dụng - Trường Đại học Nông nghiệp

Nội dung text: Giáo trình Toán ứng dụng - Trường Đại học Nông nghiệp

1. Quy trình giải BTQHTT tổng quát có sơ đồ khối giản lược như trình bày trên hình I.2. Trong sơ đồ trên, vì mục đích trình bày vấn đề đơn giản, chúng ta không đề cập tới các trường hợp khi BTQHTT có miền phương án là tập rỗng (lúc đó ta không tìm được phương án xuất phát) cũng như khi ta không tìm được điểm cực biên kề tốt hơn mặc dù điều kiện tối ưu chưa thoả mãn (lúc đó tập các giá trị hàm mục tiêu z không bị chặn). 1.3. Phương pháp đơn hình Đây là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ đã cho, trước hết chúng ta cần đưa BTQHTT về dạng chính tắc bằng cách thêm vào các biến bù không âm x3 và x4 như sau: z = 8x1 + 6x2 + 0x3 + 0x4 → Max với các ràng buộc: 4x1 + 2x2 + x3 = 60 2x1 + 4x2 + x4 = 48 x1, x2, x3, x4 ≥ 0 Cách lập và biến đổi các bảng đơn hình Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trình bày trong bảng I.1. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình bước 1: − Cột 1 là cột hệ số hàm mục tiêu ứng với các biến cơ sở đã chọn. Phương án xuất phát có thể chọn là x1 = x2 = 0 (đây chính là điểm gốc toạ độ O(0, 0)), do đó x3 = 60, x4 = 48). Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên trong phương án chưa có đơn vị sản phẩm loại I hay II được sản xuất ra (chỉ “sản xuất” ra các lượng nguyên liệu dư thừa, ta cũng nói là các “sản phẩm” loại III và IV), và giá trị hàm mục tiêu z tạm thời bằng 0. Các biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại tương ứng chưa được sử dụng hết. Ta gọi các biến x3 và x4 là các biến cơ sở vì chúng có giá trị lớn hơn 0 còn x1 và x2 là các biến ngoài cơ sở vì chúng có giá trị bằng 0. Với bài toán có hai ràng buộc, tại mỗi bước chỉ có hai biến cơ sở. − Cột 2 là cột các biến cơ sở. Trong cột 3 (cột phương án) cần ghi các giá trị của các biến cơ sở đã chọn. − Các cột tiếp theo là các cột hệ số trong các điều kiện ràng buộc tương ứng với các biến x1, x2, x3 và x4 của bài toán đã cho. 11
2. Bảng I.1. Các bảng đơn hình giải BTQHTT Hệ số hàm Biến cơ Phương c1 = 8 c2 = 6 c3 = 0 c4 = 0 mục tiêu cj sở án x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng Δj = cj − zj Δ1 = 8 Δ2 = 6 Δ3 = 0 Δ4 = 0 8 x1 15 1 1/2 1/4 0 0 x4 18 0 3 −1/2 1 Hàng z z0 = 120 z1 = 8 z2 = 4 z3 = 2 z4 = 0 Hàng Δj = cj − zj Δ1 = 0 Δ2 = 2 Δ3 = −2 Δ4 = 0 8 x1 12 1 0 1/3 −1/6 6 x2 6 0 1 −1/6 1/3 Hàng z z0 = 132 8 6 5/3 2/3 Hàng Δj = cj − zj 0 0 −5/3 −2/3 Phân tích bảng đơn hình bước 1 − Hệ số ứng với biến x1 trên hàng thứ nhất là a11 = 4 có nghĩa là tỉ lệ thay thế riêng giữa một đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 (giải thích: xét phương trình / ràng buộc thứ nhất 4x1 + 2x2 + x3 = 60, x1 tăng một đơn vị thì x3 phải giảm bốn đơn vị nếu giữ nguyên x2). Tương tự ta có thể giải thích được ý nghĩa của các hệ số aij khác cho trên hàng 1 và hàng 2 trong bảng đơn hình bước 1. − Chúng ta xét hàng z của bảng đơn hình. Để tính z1, cần áp dụng công thức z1 = (cột hệ số của hàm mục tiêu) × (cột hệ số của biến x1) = 0×4 + 0×2 = (giá một đơn vị sản phẩm loại III)×(tỉ lệ thay thế riêng loại I / loại III) + (giá một đơn vị sản phẩm loại IV) × (tỉ lệ thay thế riêng loại I / loại IV) = tổng chi phí phải bỏ ra khi đưa thêm một đơn vị sản phẩm loại I vào phương án sản xuất mới = 0. Các giá trị zj, với j = 1, 2, 3, 4, được tính tương tự và chính là các chi phí khi đưa một thêm một đơn vị sản phẩm loại xj vào phương án sản xuất mới. Còn z0 là giá trị của hàm mục tiêu đạt được tại phương án đang xét: z0 = (cột hệ số của hàm mục tiêu)× (cột phương án) = 0×60 + 0×48 = 0. − Trên hàng Δj cần ghi các giá trị Δj, j = 1, 2, 3, 4, tính theo công thức Δj = cj –zj = lợi nhuận trên một đơn vị sản phẩm – chi phí trên một đơn vị sản phẩm. Vậy Δj là "lãi biên"/một đơn vị sản phẩm khi đưa thêm một đơn vị sản phẩm loại j vào phương án sản xuất mới. Nếu Δj > 0 thì hàm mục tiêu còn tăng được khi ta đưa thêm các đơn vị sản phẩm loại j vào phương án sản xuất mới. Có thể chứng minh được Δj chính là đạo hàm riêng ∂z/∂xj của hàm mục tiêu z theo biến xj. Như vậy, x1 tăng lên 1 thì z tăng lên 8 còn x2 tăng lên 1 thì z tăng lên 6. 12
3. Do Δ1 và Δ2 đều dương nên vẫn còn khả năng cải thiện hàm mục tiêu khi chuyển sang (hay “xoay sang”) một phương án cực biên kề tốt hơn (quay lại nhận xét ở phần giải bài toán bằng phương pháp đồ thị: điểm cực biên kề của điểm (0, 0) có thể là A(0, 12) hay C(15, 0)). Thủ tục xoay (pivotal procedure) Bước 1: Chọn cột xoay là cột có Δj > 0 tức là chọn biến xj làm biến cơ sở mới do xj tăng kéo theo hàm mục tiêu tăng. Ở đây ta chọn đưa x1 vào (đánh dấu √ ở cột Δ1). Bước 2: Chọn hàng xoay để xác định đưa biến nào ra khỏi số biến cơ sở (vì tại mỗi bước số biến cơ sở là không thay đổi). Để chọn hàng xoay, ta thực hiện quy tắc “tỉ số dương bé nhất" bằng cách lấy cột phương án (60 48)T chia tương ứng cho cột xoay (4 2)T để chọn tỉ số bé nhất. Một điều cần chú ý là ta chỉ xét các tỉ số có mẫu số dương. Vì Min{60/4, 48/2} = 60/4 đạt được tại hàng đầu, nên ta đánh dấu √ vào hàng xoay là hàng đầu (hàng tương ứng với biến x3). Do đó cần đưa x3 ra khỏi các biến cơ sở. Bước 3: Chọn phần tử xoay nằm trên giao của hàng xoay và cột xoay. Bước 4: Xoay sang bảng đơn hình mới, xác định các biến cơ sở mới để điền vào cột biến cơ sở, đồng thời thay các giá trị trong cột hệ số hàm mục tiêu. Sau đó, tính lại các phần tử của hàng xoay bằng cách lấy hàng xoay cũ chia cho phần tử xoay để có hàng mới tương ứng. Bước 5: Các phần tử còn lại của bảng đơn hình mới được tính theo quy tắc "hình chữ nhật": (1)mới = (1)cũ – (2)cũ× (4)cũ/(3)cũ, trong đó (3) là đỉnh tương ứng với phần tử xoay (xem hình I.3). (2) (3) Chẳng hạn: (1)cũ = 4, 2(cũ) = 2 (3)cũ = phần tử xoay = 4, (4)cũ = 2 2 ⇒ (1)mới = 4 − 2 × = 3. 4 (1) (4) Hình I.3. Quy tắc hình chữ nhật Giải thích: Các bước xoay trên đây chỉ là phép biến đổi tương đương hệ phương trình 4x1 + 2x2 + x3 = 60 (a) 2x1 + 4x2 + x4 = 48 (b) để có hệ x1 + (1/2)x2 + (1/4)x3 = 15 (a’) 0x1 + 3x2 − (1/2)x3 + x4 = 18 (b’) 13
4. bằng cách lấy phương trình (a) chia cho 4 (phần tử xoay) để có (a’), rồi lấy (b) trừ bớt 2 × (a)/4 để có (b’). Đây chính là nội dung của bước 4 và bước 5. Còn bước 3 sẽ đảm bảo rằng giá trị của các biến cơ sở mới không âm (x1 = 15, x4 = 18). Áp dụng thủ tục xoay cho các phần tử nằm trên hàng 1 và 2 của bảng đơn hình bước 1, sau đó tính các giá trị trên hàng zj và Δj tương tự như khi lập bảng đơn hình bước 1, chúng ta sẽ nhận được bảng đơn hình bước 2. Phân tích bảng đơn hình bước 2 Bảng bước 2 có thể được phân tích tương tự như bảng bước 1. Cần chú ý rằng lúc này ta đang ở vị trí của điểm C(15, 0) vì x1 = 15 còn x2 = 0; giá trị của hàm mục tiêu là z0 = 120 đã được cải thiện hơn so với bước 1. Ta thấy Δ2 = 2 > 0 nên còn có thể cải thiện hàm mục tiêu bằng cách chọn biến x2 làm biến cơ sở mới. Thực hiện các bước xoay sang phương án cực biên kề tốt hơn, chúng ta sẽ có bảng đơn hình bước 3. Phân tích bảng đơn hình bước 3 Tại bảng đơn hình bước 3 ta thấy điều kiện tối ưu đã được thoả mãn (Δj ≤ 0 ∀j=1, 2, 3, 4) nên không còn khả năng cải thiện phương án. Phương án tối ưu đã đạt được tại x1 = 12, x2 = 6, x3 = 0, x4 = 0, tức là tại điểm cực biên B(12, 6) với giá trị zmax = 132. Một số chú ý − Điều kiện tối ưu cho các BTQHTT dạng Max là Δj ≤ 0 ∀j. − Đối với các BTQHTT cần cực tiểu hoá hàm mục tiêu thì điều kiện tối ưu (hay tiêu chuẩn dừng) là Δj ≥ 0 ∀j (nếu tồn tại j mà Δj ≤ 0 thì cần tiếp tục cải thiện hàm mục tiêu bằng cách chọn cột j làm cột xoay ). − Trong thực tiễn giải các BTQHTT dạng tổng quát có thể xảy ra trường hợp không tìm được phương án xuất phát (tức là không có phương án khả thi, xem thêm mục 1.2). Lúc này có thể kết luận mô hình đã thiết lập có các điều kiện ràng buộc quá chặt chẽ, cần xem xét nới lỏng các điều kiện này. − Trong trường hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị chặn trên (đối với các BTQHTT dạng Max) hoặc không bị chặn dưới (đối với các BTQHTT dạng Min). Khi đó dừng quá trình giải và kết luận mô hình quy hoạch tuyến tính đã thiết lập không phù hợp với thực tế. 1.4. Giải mô hình quy hoạch tuyến tính bằng các phần mềm tính toán Hiện nay có nhiều phần mềm tính toán giải BTQHTT khá hiệu quả như Excel, Lingo. Những phần mềm này rất thân thiện với người dùng. Tuy nhiên cần nhấn mạnh rằng, việc phát biểu được mô hình bài toán và phân tích, đánh giá được kết quả mới chính là những khâu quan trọng nhất trong phương pháp mô hình hoá. Sau đây, chúng ta dùng phần mềm Lingo để giải ví dụ đã xét ở trên. z = 8x1 + 6x2 → Max 14
5. với các ràng buộc: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. Để giải bài toán này, chúng ta cần cài đặt Lingo vào trong máy tính. Nhấn vào biểu tượng Lingo trên màn hình để vào cửa sổ Lingo. Sau đó thực hiện các lệnh Lingo: Menu > New > và gõ vào các dữ liệu của bài toán như hình I.4. Hình I.4. Nhập dữ liệu của bài toán quy hoạch tuyến tính trong Lingo Tiếp theo, cần nháy chuột vào nút LINGO và giải bài toán để thu được kết quả chi tiết như trên hình I.5. Hình I.5. Kết quả giải bài toán quy hoạch tuyến tính trong Lingo Kết quả chi tiết cho ta biết giá trị cực đại của hàm mục tiêu là 132 với phương án tối ưu là: x1 = 12, x2 = 6. Các giá trị tối ưu của các biến đối ngẫu là y1 = 5/3 và y2 = 2/3 (còn gọi là các giá ước định hay giá bóng Shadow Prices). 15
6. 1.5. Một số ứng dụng của phương pháp đơn hình (Giải các bài toán quy hoạch sản xuất trong lĩnh vực cơ khí và điện lực) Bài toán phân phối điện năng Có ba hộ phụ tải cần được cung cấp điện năng từ hai nguồn điện nằm cách xa nhau. Giá thành truyền tải một đơn vị điện năng từ nguồn i đến hộ tiêu thụ j là cij. Khả năng cung cấp điện năng của mỗi nguồn bị giới hạn bởi trữ lượng hiện có của chúng là A1 và A2. Nhu cầu tiêu dùng của các hộ tiêu thụ là B1, B2 và B3. Gọi xij là lượng điện năng được đưa từ nguồn i tới hộ tiêu thụ j. Cần phải xác định các xij sao cho tổng chi phí là nhỏ nhất. Như vậy ta có BTQHTT sau: 23 z = → Min ∑∑cxij ij i1== j1 với các điều kiện ràng buộc là: x11 + x12 + x13 ≤ A1, x21 + x22 + x23 ≤ A2, x11 + x21 = B1, x12 + x22 = B2, x13 + x23 = B3, xij ≥ 0, ∀i = 1, 2 và ∀j = 1, 2, 3. Bài toán trên đây (hoặc ở dạng tổng quát hơn) có thể giải được bằng phương pháp đơn hình đã biết hay phương pháp phân phối sẽ được nghiên cứu ở mục 1.3, chương II. Bài toán phân tải cho máy Một xí nghiệp có hai loại máy M1 và M2. Các loại máy này có thể sản xuất được ba loại sản phẩm P1, P2 và P3 với các năng suất là aij, chẳng hạn máy M1 sản xuất sản phẩm P2 với năng suất a12. Mỗi đơn vị sản phẩm mang lại lãi suất cj với j = 1, 2, 3. Mỗi tháng xí nghiệp phải sản xuất sản phẩm loại j không ít hơn bj đơn vị và không vượt quá dj đơn vị, j = 1, 2, 3. Hãy lập kế hoạch phân tải cho các máy sao cho đạt tổng lợi nhuận lớn nhất. Dễ thấy bài toán này dẫn tới BTQHTT sau: 32 z = → Max ∑∑caxjijij j1== i1 với các điều kiện ràng buộc: 16
7. a11x11 + a21x21 ≥ b1, a12x12 + a22x22 ≥ b2, a13x13 + a23x23 ≥ b3, a11x11 + a21x21 ≤ d1, a12x12 + a22x22 ≤ d2, a13x13 + a23x23 ≤ d3, x11 + x12 + x13 ≤ m1, x21 + x22 + x23 ≤ m2, xij ≥ 0, i = 1, 2 và j = 1, 2, 3. (trong đó m1 và m2 là tổng thời gian chạy máy M1 và M2). Bài toán trên đây còn có thể phát biểu một cách tổng quát hơn và vẫn giải được bằng phương pháp đơn hình. Hơn nữa, trong lĩnh vực quy hoạch sản xuất hay quản lí kinh doanh, nói riêng trong ngành cơ khí và điện lực, BTQHTT được ứng dụng rất rộng rãi và mang lại hiệu quả cần thiết. 2. Bổ sung thêm về phương pháp đơn hình 2.1. Đưa BTQHTT về dạng chính tắc Ví dụ 1: (Trường hợp các ràng buộc đều có dấu ≤) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+ 2x≤ 60 ⎪ ⎨2x12+ 4x≤ 48 ⎪ ⎩x,x12≥ 0 Đưa BTQHTT về dạng chính tắc như đã biết bằng cách thêm hai biến bù (slack variables) x3 và x4. Ta có BTQHTT dạng chính tắc là: z = 8x1 + 6x2 + 0x3 + 0x4 → Max ⎧4x123+ 2x+= x 60 ⎪ ⎨2x124+ 4x+= x 48 ⎪ ⎩x,x,x,x1234≥ 0 Lúc này, trong hệ hai điều kiện ràng buộc đã có đủ hai biến đứng độc lập trong từng phương trình với hệ số +1, nên đã có thể tìm được phương án cực biên xuất phát để bắt đầu quá trình giải bài toán. Một cách tổng quát, BTQHTT dạng chính tắc là bài toán với các 17
8. biến không âm, các ràng buộc với dấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi phương trình bắt buộc phải có một biến đứng độc lập với hệ số +1. Ví dụ 2: (Trường hợp có điều kiện ràng buộc với dấu ≥) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+≤ 2x 60 ⎪ ⎨2x12+≥ 4x 48 ⎪ ⎩x,x12≥ 0 Ta thêm các biến bù x3 (slack variable) mang dấu “+”, x4 (surplus variable) mang dấu “−” để có hệ điều kiện ràng buộc sau: ⎧4x123+ 2x+= x 60 ⎪ ⎨2x124+ 4x−= x 48 ⎪ ⎩x,x,x,x1234≥ 0 Phải thêm biến giả x5 (x5 gọi là lượng vi phạm của phương trình thứ hai) để được hệ điều kiện ràng buộc ⎧4x1 + 2x 2 + x 3 = 60 ⎪ ⎨2x1 + 4x 2 − x 4 + x 5 = 48 ⎪ ⎩x1 , x 2 , x 3 , x 4 , x 5 ≥ 0 Lúc này, đã có đủ hai biến đứng độc lập trong từng phương trình với hệ số +1, nên đã có thể tìm được phương án cực biên xuất phát để bắt đầu quá trình giải bài toán bằng phương pháp đơn hình với hàm mục tiêu là z = 8x1 + 6x2 + 0x3 + 0x4 − Mx5 → Max, trong đó M ≈ +∞ và biểu thức −Mx5 gọi là lượng phạt (đánh thuế). Bài toán đã được đưa về dạng chính tắc. Lượng vi phạm x5 càng lớn thì hàm mục tiêu càng giảm, giá trị của hàm mục tiêu chỉ có thể đạt Max khi x5 = 0. Ví dụ 3: (Trường hợp có biến không dương) z = 8x1 − 6x2 → Max với các ràng buộc: ⎧4x123++≤ 2x x 60 ⎪ ⎨2x124+−= 4x x 48 ⎪ ⎩x0,x0,x0,x01234≥≤≥≥ Lúc này muốn giải bài toán bằng phương pháp đơn hình ta phải đổi biến x'2 = −x2. Ta có BTQHTT với các biến đều không âm. 18
9. z = 8x1 + 6x'2 → Max với các ràng buộc: ⎧4x123− 2x '+≤ x 60 ⎪ ⎨2x124− 4x '−= x 48 ⎪ ⎩x,x',x,x1234≥ 0 Ví dụ 4: (Trường hợp có biến với dấu tuỳ ý) z = 8x1 + 6x2 → Max với các ràng buộc: ⎧4x12+ 2x≤ 60 ⎪ ⎨2x12+ 4x≤ 48 ⎪ ⎩x0,x12≥ dấu tuỳ ý Lúc này ta viết biến x2 dưới dạng x2 = x'2 − x''2 với ⎧x'22= max[0,x ] ⎧x'2 ≥ 0 ⎨ thì đảm bảo ⎨ ⎩x''22=− max[0, x ] ⎩x''2 ≥ 0 Các ràng buộc sẽ là ⎧4x1223+ 2x'−+= 2x'' x 60 ⎪ ⎨2x1224+−+= 4x' 4x' x 48 ⎪ ⎩x1 ,x' 2 ,x'',x 234 ,x≥ 0 Bài toán với hàm mục tiêu là: z = 8x1 + 6x'2 − 6x''2 + 0x3 + 0x4 và các điều kiện ràng buộc trên là BTQHTT dạng chính tắc. Kết luận: Bao giờ cũng đưa được BTQHTT bất kì (các biến có dấu tuỳ ý, các ràng buộc có thể ≤, ≥, =) về dạng chính tắc. 2.2. Phương pháp đơn hình mở rộng Phương pháp đơn hình mở rộng còn gọi là phương pháp đánh thuế M được áp dụng để để giải BTQHTT có biến giả. Ví dụ: z = 8x1 + 6x2 → Max với các ràng buộc: 19
10. ⎧4x12+ 2x≤ 60 ⎪ (a)⎨ 2x12+ 4x≥ 48 ⎪ ⎩x,x12≥ 0 hay: z = 8x1 + 6x2 +0x3 + 0x4 → Max với các ràng buộc ⎧4x123+ 2x+= x 60 ⎪ (b)⎨ 2x124+ 4x−= x 48 ⎪ ⎩x,x,x,x1234≥ 0 Ta có thể đưa bài toán về dạng chính tắc sau gọi là bài toán M: Max z = 8x1 + 6x2 +0x3 + 0x4 − Mx5 (trong đó M ≈ +∞) với các ràng buộc ⎧4x123++= 2x x 60 ⎪ (c)⎨ 2x1245+ 4x−+= x x 48 ⎪ ⎩x,x,x,x,x12345≥ 0 Cách 1: Có thể giải BTQHTT với các điều kiện ràng buộc (a) bằng phương pháp đồ thị để nhận được kết quả: phương án tối ưu là (x1 = 0, x2 = 30) và zmax = 180. Cách 2: Giải BTQHTT với các điều kiện ràng buộc (c) bằng cách lập bảng đơn hình như thông thường nhưng chú ý hệ số M ≈ +∞ (xem bảng I.2). Bảng I.2. Các bảng đơn hình giải bài toán M Hệ số Biến Phương 8 6 0 0 −M hàm mục cơ sở án tiêu x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 −M x5 48 2 4 0 −1 +1 Hàng z z0 = −48M z1 = −2M z2 = −4M z3 = 0 z4 = M z5 = −M Hàng Δj Δ1 = 8+2M Δ2 = 6+4M Δ3 = 0 Δ4 = −M Δ5 = 0 0 x3 36 3 0 1 1/2 −1/2 6 x2 12 1/2 1 0 −1/4 1/4 Hàng z 72 3 6 0 −3/2 3/2 Hàng Δj 5 0 0 3/2 −M − 3/2 0 x4 72 6 0 2 1 −1 6 x2 30 2 1 1/2 0 0 Hàng z 180 12 6 3 0 0 Hàng Δj −4 0 −3 0 −M 20
11. Tại bảng đơn hình cuối cùng, ta thấy Δj ≤ 0 ∀j nên phương án tối ưu đã đạt được với x2 = 30, x4 = 72, các xj khác = 0 và zMax = 180. Lưu ý − Khi một biến giả đã được đưa ra khỏi cơ sở thì không bao giờ quay lại nữa. Do đó ta có thể xoá cột biến giả đó khỏi bảng đơn hình. − Nếu dấu hiệu dừng xuất hiện (Δj ≤ 0 ∀j) nhưng vẫn còn biến giả với giá trị dương trong số các biến cơ sở thì điều này chứng tỏ bài toán ban đầu không thể có phương án khả thi (có thể chứng minh bằng phản chứng). − Với ví dụ trên (xem bảng I.2) ta thấy quá trình giải chia làm hai pha: pha 1 nhằm giải bài toán M cho tới khi biến giả (x5) được đưa ra khỏi số biến cơ sở (lúc này có phương án cực biên xuất phát cho bài toán (b)) và pha 2 nhằm tìm phương án tối ưu cho bài toán (b). − Phần mềm tính toán Lingo có thể giải được tất cả các BTQHTT không đòi hỏi người dùng phải đưa chúng về dạng chính tắc. 3. Mô hình quy hoạch tuyến tính đa mục tiêu 3.1. Các khái niệm cơ bản Phát biểu mô hình Trong các bài toán kĩ thuật, công nghệ, quản lí, kinh tế nông nghiệp v.v nảy sinh từ thực tế, chúng ta thường phải xem xét để tối ưu hoá đồng thời một lúc nhiều mục tiêu. Các mục tiêu này thường là khác về thứ nguyên, tức là chúng được đo bởi các đơn vị khác nhau. Những tình huống như vậy tạo ra các bài toán tối ưu đa mục tiêu. Như vậy, chúng ta cần phải tối ưu hoá (cực đại hoá hoặc cực tiểu hoá tuỳ theo tình huống thực tế) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả các mục tiêu đã đặt ra. Bài toán tối ưu đa mục tiêu mà trong đó miền ràng buộc D là tập lồi đa diện và các mục tiêu zi = fi(X), với i = 1, 2, , p, là các hàm tuyến tính xác định trên D, được gọi là bài toán quy hoạch tuyến tính đa mục tiêu. Khi đó, ta có mô hình toán học sau đây được gọi là mô hình quy hoạch tuyến tính đa mục tiêu : Max CX với ràng buộc X ∈ D, trong đó: C là ma trận cấp p × n D = { X ∈ Rn: AX ≤ B} với A là ma trận cấp m × n và B ∈ Rm. Ví dụ: BTQHTT với hai mục tiêu f1(X) = x1 + 2x2 → Min hay z1 = f’1 (X) = −x1 − 2x2 → Max z2 = f2(X) = 2x2, → Max 21
12. với các ràng buộc ⎧−+xx12 ≤ 3 ⎪ ⎨ xx12+ ≥ 3 ⎪ ⎩ x,12 x≥ 0 Ta có thể viết bài toán này dưới dạng ma trận như sau: Max CX với ràng buộc 2 T T X ∈ D = {X∈ R : AX ≤ B}, trong đó X = (x1, x2) , B = (3, −3, 0, 0) , còn ⎡−1 1⎤ ⎢ ⎥ ⎡−1 − 2⎤ ⎢−1 −1⎥ C = ⎢ ⎥ , A = . ⎣0 2 ⎦ ⎢−1 0⎥ ⎢ ⎥ ⎣ 0 −1⎦ Có thể nói, BTQHTT đa mục tiêu là BTQHTT mà trong đó chúng ta phải tối ưu hoá cùng một lúc nhiều mục tiêu. Tuy nhiên, các mục tiêu này thường đối chọi cạnh tranh với nhau. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số mục tiêu khác. Vì vậy việc giải các bài toán tối ưu đa mục tiêu, tức là tìm ra một phương án khả thi tốt nhất theo một nghĩa nào đó, thực chất chính là một bài toán ra quyết định. Có thể thấy lại ở đây một lần nữa khẳng định "Tối ưu hoá chính là công cụ định lượng chủ yếu nhất của quá trình ra quyết định". Hiện tại các tài liệu, sách chuyên khảo, tạp chí cập nhật về lĩnh vực liên ngành Toán − Tin, Khoa học quản lí, Công nghệ, Kinh tế, Điện, Cơ khí nông nghiệp, đề cập rất nhiều tới bài toán tối ưu đa mục tiêu. Vấn đề nghiên cứu cơ sở lí thuyết, thuật toán, lập mô hình, xây dựng hệ máy tính trợ giúp quyết định, và áp dụng các mô hình tối ưu đa mục tiêu cho các quá trình công nghệ, quản lí, là một vấn đề liên ngành được rất nhiều nhà khoa học và kĩ sư thực hành quan tâm. Phương án tối ưu Pareto Khái niệm then chốt trong tối ưu hoá đa mục tiêu là khái niệm phương án tối ưu Pareto. Định nghĩa: Một phương án tối ưu Pareto X* có tính chất sau đây: − Trước hết nó phải thuộc vào miền các phương án khả thi của bài toán, tức là phải thoả mãn tất cả các ràng buộc: X* ∈ D. − Với mọi phương án khả thi khác X ∈ D mà có một mục tiêu nào đó tốt hơn (fi(X) tốt * * hơn fi(X )) thì cũng phải có ít nhất một mục tiêu khác xấu hơn (fj(X) xấu hơn fj(X ), j ≠ i). Nói một cách khác, không tồn tại một phương án khả thi nào X ∈ D có thể trội hơn X* trên tổng thể. Để minh hoạ định nghĩa trên, ta xét ví dụ đã cho. 22
13. Ví dụ: Xét BTQHTT với hai mục tiêu. f1 (X) = x1 + 2x2 → Min f2 (X) = 2x2 → Max Với các ràng buộc ⎧−+xx12 ≤3 ⎪ ⎨ xx12+≥3 ⎪ ⎩ xx12, ≥ 0 y d A 3 D 2 G n 2 B o -3 x 3 G n1 Hình I.6. Minh hoạ đồ thị BTQHTT hai mục tiêu Miền các phương án khả thi D (miền giới hạn bởi đoạn AB và các tia Ad, Bx) được G G biểu thị trên hình I.6. n1 (−1, −2) là hướng giảm của mục tiêu 1, còn n2 (0, 2) là hướng tăng của mục tiêu 2. Lúc này A(0, 3) cũng như B(3, 0) là hai phương án tối ưu Pareto của bài toán trên. Dễ thấy tập hợp P tất cả các phương án tối ưu Pareto bao gồm các điểm nằm trên đoạn AB và Ad. 3.2. Một số phương pháp giải BTQHTT đa mục tiêu Định nghĩa 1 Giải bài toán tối ưu toàn cục đa mục tiêu là chọn ra từ tập hợp P các phương án tối ưu Pareto của bài toán một (hoặc một số) phương án tốt nhất (thoả mãn nhất) theo một nghĩa nào đó dựa trên cơ cấu ưu tiên của người ra quyết định. Trong ví dụ trên, tuỳ theo cơ cấu ưu tiên của người ra quyết định, chúng ta có thể 23