CHƯƠNG 5: BÀI TOÁN ĐỐI NGẪU
Bài ví dụ: xem bài toán gốc trong giáo trình
Giải thích cách viết bài toán đối ngẫu như sau:
Dự định không sản xuất nữa mà bán Nguyên vật liệu luôn. Ta gọi y1, y2, y3 lần
lượt là giá bán đơn vị của NVL A, B, C. yi ≥ 0.
* Bên mua NVL chỉ mua được khi thõa mãn các điều kiện sau:
+ Điều kiện 1: Chúng ta sử dụng 3 đơn vị NVL A, 2 đơn vị NVL B, 1 đơn vị NVL
C để sản xuất ra 1 sản phẩm I. Mà 1 sản phẩm I dự kiến thu lại lợi nhuận là 2 $. Vậy
chúng ta không sử dụng NVL để sản xuất nữa mà chúng ta bán NVL khi và chỉ khi đạt điều kiện sau: 3y1 + 2y2 + 1y3 ≥ 2 $
+ Điều kiện 2: Chúng ta sử dụng 4 đơn vị NVL A, 1 đơn vị NVL B, 3 đơn vị
NVL C để sản xuất ra 1 sản phẩm II…… 4y1 + y2 + 3y3 ≥ 4
+ Điều kiện 3: Chúng ta sử dụng 2 đơn vị NVL A, 2 đơn vị NVL B, 2 đơn vị NVL
C để sản xuất ra 1 sản phẩm III…… 2y1 + 2y2 + 2y3 ≥ 3
* Còn phía bên mua Nguyên vật liệu, thì họ mong muốn mua được khi:
(y) =60y1+ 40y2 +80y3 => Min
A) NGUYÊN TẮC VIẾT HỆ SỐ CHO BÀI TOÁN ĐỐI NGẪU
Như vậy nguyên tắc viết hệ số trong các ràng buộc của bài toán đối ngẫu là dựa
vào ma trận chuyển vị của các hệ số trong ràng buộc ở bài gốc: 3 4 2 2 1 2 1 3 2 2 4 3
Ma trận chuyển vị sẽ là: 3 2 1 ≤ = ≥ 2 4 1 3 ≤ = ≥ 4 2 2 2 ≤ = ≥ 3 Và:
+ Các hệ số ở hàm mục tiêu của BTĐN chính là các vế phải của các ràng buộc ở BTG.
+ SỐ BIẾN SỐ CỦA BTĐN = SỐ RÀNG BUỘC CỦA BTG
+ Và ngược lại: SỐ RÀNG BUỘC CỦA BTĐN = SỐ BIẾN SỐ CỦA BTG
B) NGUYÊN TẮC VIẾT DẤU CHO BÀI TOÁN ĐỐI NGẪU:
DẠNG 1: BTG MAX => BTĐN MIN
Ta hình dung từ Max chuyển về Min là NGƯỢC ( vì là từ Lớn về Nhỏ)
Mà khi ta viết một bài toán thì ta viết hệ (1) là hệ biến số trước, rồi đến hệ (2) là hệ
ràng buộc, rồi mới đến hệ (3) là hàm mục tiêu.
Vậy hê (1) là hệ biến số: thì biến số y của BTĐN NGƯỢC
dấu với dấu của RÀNG BUỘC trong BTG.
Vậy suy ra hệ (2) là hệ ràng buộc: thì dấu của các RÀNG BUỘC của BTĐN
CÙNG dấu với dấu của BIẾN SỐ trong BTG.
Lưu ý: biến số của BTG có dấu tùy ý thì ràng buộc tương ứng của BTĐN sẽ có dấu =. BÀI TẬP:
Câu 8 SGK: Cho bài toán quy hoạch tuyến tính: f(x) = 4x1 + 2x − 3x 2 + 5x 3 4 max 2x1 – x + x 2 + 2x 3 ≥ 50 4 3x1 − x + 2x 3 4 ≤ 80 x1 + x2 + x = 60 4 x1, x2, x3, x4 ≥ 0.
a. Giải bài toán bằng phương pháp đơn hình?
b. Viết bài toán đối ngẫu? Tìm phương án tối ưu của bài toán đối ngẫu thông qua phương
án tối ưu của bài toán gốc đã tìm được ở câu a?
BÀI TOÁN ĐỐI NGẪU:
Đây là cặp bài toán Gốcmax ->Đối Ngẫu min, từ Max qua Min là NGƯỢC, vậy hệ (1)-
hệ biến số sẽ dùng chữ NGƯỢC, hệ (1) đã dùng chữ này thì suy ra hệ (2)-hệ ràng buộc, phải dùng chữ CÙNG.
(1)-Hệ biến số: BTG có 3 ràng buộc => BTĐN có 3 biến số là y1, y2, y3, dấu của biến
số này NGƯỢC dấu với dấu của 3 RÀNG BUỘC ở BTG. y1≤ 0, y2 ≥0, y3 tùy ý.
(2)- Hệ ràng buộc: BTG có 4 biến số, suy ra BTĐN có 4 ràng buộc. 4 ràng buộc này
CÙNG dấu với dấu của 4 biến số ở BTG. 2y1 + 3y2 + y3 ≥ 4 -y1 + 0y2 +y3 ≥ 2 y1 –y2 + 0y3 ≥ -3 2y2 + 2y2 + y3 ≥ 5
(3)- Hàm mục tiêu (y) = 50y1 +80 y2 + 60y3 => min 
DẠNG 2: BTG MIN => BTĐN MAX
Ta hình dung từ Min chuyển về Max là THUẬN ( vì là từ nhỏ về Lớn)
Vậy hê (1) là hệ biến số: thì biến số y của BTĐN CÙNG dấu với dấu của RÀNG BUỘC trong BTG.
Vậy suy ra hệ (2) là hệ ràng buộc: thì dấu của các RÀNG BUỘC của BTĐN
NGƯỢC dấu với dấu của BIẾN SỐ trong BTG.
Lưu ý: biến số của BTG có dấu tùy ý thì ràng buộc tương ứng của BTĐN sẽ có dấu =. BÀI TẬP Câu 9 SGK
Cho bài toán quy hoạch tuyến tính: f(x) = 4x1 + 5x + 3x 2 3  min 4x1 + 2x ≥ 20 3 x2 − x3 ≤ − 8 x1 − 2x2 = − 4 2x + x 1 2 + x ≤ 12 3 x1, x2, x3 ≥ 0.
a. Giải bài toán bằng phương pháp đơn hình? Nhận xét phương án tối ưu?
b. Viết bài toán đối ngẫu của bài toán đã cho?
BÀI TOÁN ĐỐI NGẪU:
Đây là cặp bài toán Gốcmin ->Đối Ngẫu max, từ Min qua Max là THUẬN, vậy hệ (1)-
hệ biến số sẽ dùng chữ THUẬN, hay gọi là chữ CÙNG, hệ (1) đã dùng chữ này thì suy ra hệ
(2)-hệ ràng buộc, phải dùng chữ NGƯỢC.
(1)-Hệ biến số: BTG có 4 ràng buộc => BTĐN có 4 biến số là y1, y2, y3, y4, dấu của 4
biến số này CÙNG dấu với dấu của 4 RÀNG BUỘC ở BTG.
y1 ≥ 0, y2 ≤ 0, y3 tùy ý, y4 ≤ 0
(2)- Hệ ràng buộc: BTG có 3 biến số, suy ra BTĐN có 3 ràng buộc. 3 ràng buộc này
NGƯỢC dấu với dấu của 3 biến số ở BTG.
4y1 + 0y2 + y3 + 2y4 ≤ 4 0y1 + y2 -2y3 + y4 ≤ 5 2y1 –y2 + 0y3 + y4 ≤ 3
(3)- Hàm mục tiêu (y) = 20y1 – 8y2 -4y3 + 12y4 => max 
------------------------//--------------------------