Tài liệu Phân tích độ nhạy

BÀI TOÁN ĐỐI NGẪU
PHÂN TÍCH ĐỘ NHẠY
I. Bài toán đối ngẫu (Dual problem)
1.1 Ví dụ dẫn nhập
Cty sản xuất 2 loại sản phẩm A, B qua 2 công đoạn cắt,
ráp. Một sản phẩm A có lợi nhuận $50 cần 2 giờ cắt, 1 giờ
ráp. Một sản phẩm B có lợi nhuận $80, cần 3 giờ cắt và 4
giờ ráp. Thời gian hoạt động sẵn có của công đoạn cắt, ráp
là 100 giờ và 60 giờ. Gọi x1, x2 là số sản phẩm A, B được
sản xuất
Max Z = 50x1 + 80x2
S.t 2x1 + 3x2 ≤ 100
x1 + 4x2 ≤ 60
x1
, x2 ≥ 0
Hiểu cách khác - Gọi u1, u2, là chi phí thuê công ty Y gia
công cho 1 giờ cắt và ráp. Bài toán trên tương đương:
Min Z' = 100u1 + 60u2 (chi phí thuê gia công càng nhỏ càng tốt)
S.t 2u1 + u2 ≥ 50 (nếu không thì cty Y không nhận gia công)
3u1 + 4u2 ≥ 80 (nếu không thì cty Y không nhận gia công)
1.2 Các nguyên tắc hình thành bài toán đối ngẫu
1. Bài toán gốc là Max → bài toán đối ngẫu là Min, và
ngược lại
2. Vế phải RHS bi của các ràng buộc của bài gốc → các hệ
số trong hàm mục tiêu của bài toán đối ngẫu
3. Các hệ số cj trong hàm mục tiêu của bài gốc → các giá
trị vế phải của ràng buộc bài toán đối ngẫu
Chương 5 – Bài toán Đối ngẫu & Phân tích độ nhạy 2 GV. Nguyen Vu Quang
4. Các hệ số trong các ràng buộc của bài gốc → chuyển vị
(ma trận) → các hệ số ràng buộc của bài toán đối ngẫu
5. Dấu bất đẳng thức thay đổi theo nguyên tắc sau:
Gốc (Min) Đối ngẫu (Max)
≥ bi
≤ bi
= bi
Tương ứng sẽ có
''
''
ui ≥ 0
ui ≤ 0
ui không bị giới hạn
xi ≥ 0
xi ≤ 0
xi không bị giới hạn
''
''
''
≤ cj
≥ cj
= cj
Gốc (Max) Đối ngẫu (Min)
≤ bi
≥ bi
= bi
Tương ứng sẽ có
''
''
ui ≥ 0
ui ≤ 0
ui không bị giới