9. PHƯƠNG PHÁP ĐƠN HÌNH (SIMPLEX METHOD)
9.2.4. Cách biễu diễn biến thiếu, biến thừa và biến nhân tạo trong hàm mục tiêu
nhân tạo trong hàm mục tiêu
Tất cả các loại biến đều phải thể hiện trong hàm mục tiêu của bài tốn. Biến thiếu và biến thừa khơng sinh ra lợi nhuận, do đĩ chúng sẽ được gán hệ số bằng 0 trong hàm mục tiêu. Biến nhân tạo khơng phải là nghiệm, do đĩ chúng ta sẽ gán nĩ hệ số Cj = + M (số vơ cùng lớn) trong bài tốn cực tiểu hĩa và Cj = - M (số vơ cùng bé) trong bài tốn cực đại hĩa.
Trong bài tốn QHTT chuẩn, hệ số của các biến thiếu trong hàm mục tiêu được gán bằng 0. Điều này ám chỉ các biến thiếu diễn tả nguồn tài nguyên chưa dùng hết nên khơng ảnh hưởng đến giá trị của hàm mục tiêu. Tuy nhiên, trong một số tình huống thực tế, các tài
nguyên chưa được sử dụng cĩ thể được đem đi bán và cũng mang lại lợi nhuận. Khi đĩ, các biến thiếu này lại trở thành các biến quyết định thể hiện tổng số tài nguyên bán được. Nghĩa là các hệ số khác khơng trong hàm mục tiêu của từng biến trong các biến này sẽ phản ánh lợi nhuận của việc bán được 1 đơn vị tài nguyên liên quan.
Ví dụ1: Bài tốn QHTT cực đại hĩa Hàm mục tiêu: Max Z = 70x1 + 50x2 (USD) Ràng buộc:
4x1 + 3x2 ≤ 240 2x1 + 1x2 ≥ 100 5x1 + 3x2 = 400 Sau khi biến đổi:
Hàm mục tiêu: Max Z = 70x1 + 50x2+ 0s1+ 0s2 - MA1 (USD) Ràng buộc:
4x1 + 3x2 + 1s1 = 240 2x1 + 1x2 - 1s2 = 100 5x1 + 3x2 + 1A1 = 400
* Ghi chú: Hệ số Cj của biến thiếu và biến thừa (surplus and slack variables) trong hàm mục tiêu là 0 trong khi hệ số Cj của biến nhân tạo là một số rất lớn ký hiệu là -M.
Ví dụ 2: Bài tốn QHTT cực tiểu hĩa Hàm mục tiêu: Min Z = 2x1 + 3x2 Ràng buộc: 1x1 ≥ 125 1x1 + 1x2 ≥ 350 2x1 + 1x2 ≤ 600 x1, x2 ≥ 0 Sau khi biến đổi:
Ràng buộc:
1x1 – 1s1 = 125 1x1 + 1x2 - 1s2 = 350 2x1 + 1x2 + 1s3 = 600 x1, x2, s1, s2, s3 ≥ 0
* Chú ý: Với hàm mục tiêu, ta cĩ quan hệ sau đây: Max Z = - Min (- Z)
Ví dụ: Max Z = 5x1 + 3x2 cĩ cùng lời giải với Min (-Z) = - 5x1 - 3x2