Chương 5
Bài toán Đối ngẫu –
Phân tích Độ nhạy
2
C5. Bài toán Đối ngẫu – Phân tích Độ nhạy
1. Bài toán Đối ngẫu
2. Phân tích Độ nhạy
cho Bài toán QHTT 2 biến bằng đồ thị
3. Phân tích Độ nhạy cho Bài toán QHTT
bằng Phần mềm Excel/ABQM
4. Ý nghĩa của giá mờ
3
1. Bài toán Đối ngẫu (Dual Problem)
1.1. VD dẫn nhập
Công ty 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 x
1
, x
2
là số sản phẩm
A, B được sản xuất.
Max Z = 50 x
1
+ 80 x
2
Ràng buộc: 2x
1
+ 3x
2

3 u
1
+ 4 u
2
≥ 80 (nếu không thì cty Y không nhận gia công)
u
1
, u
2
≥ 0
5
1. Bài toán Đối ngẫu (tt2)
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.
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)
≥ b
i
≤ b
i
= b
i
Tương ứng sẽ có
“

i
≥ b
i
= b
i
Tương ứng sẽ có
“
“
u
i
≥ 0
u
i
≤ 0
u
i
không bị giới hạn
x
i
≥ 0
x
i
≤ 0
x
i
không bị giới hạn
“
“
“
≥ c

2x
1
+ 2x
2
+ x
3
≥ 6 2u
1
+ 2u
2
≤ 4
x
1
, x
2
, x
3
≥ 0 3u
1
+ u
2
≤ 5
u
1
, u
2
≥ 0
Max Z = 2x
1
+ 3x

+ 3x
3
≤ 1 –2u
1
– u
2
+ 5u
3
– 4u
4
≥ 3
–3x
1
+ 5x
2
+ x
3
≥ –3 5u
1
+ 3u
2
+ u
3
– 2u
4
≤ –
2
–x
1
– 4x

Rb: 2x
1
+ x
2
+ x
3
≤ 2
x
1
+ x
2
+ 3x
3
≤ 4
x
1
, x
2
, x
3
≥ 0
Bài toán đối ngẫu:
Min Z’ = 2u
1
+ 4u
2
Rb: 2u
1
+ u
2

Làm thế nào tìm x
1
, x
2
, x
3
?
Giải BT đối ngẫu, bằng pp đồ thị.
10
1. Bài toán Đối ngẫu (tt7)
1.3. Lưu ý:

Đối ngẫu của BT đối ngẫu sẽ cho ra BT gốc.

BT gốc không bị chặn (unbounded) thì BT đối ngẫu sẽ không có nghiệm khả dĩ, và
ngược lại BT đối ngẫu không bị chặn thì BT gốc không có nghiệm khả dĩ.

Giá trị tối ưu của hàm mục tiêu của BT đối ngẫu và BT gốc là giống nhau.

Nghiệm của BT gốc là những giá trị ở hàng dưới cùng ứng với các biến bù trong bảng
đơn hình sau cùng của BT đối ngẫu.

Nghiệm của BT đối ngẫu là những giá trị ở hàng dưới cùng ứng với các biến bù trong
bảng đơn hình sau cùng của BT gốc.

Một biến QĐ trong BT gốc có giá trị ≠ 0, thì biến bù tương ứng trong BT đối ngẫu sẽ có
giá trị = 0.

Một biến bù trong BT gốc có giá trị ≠ 0, thì biến QĐ tương ứng trong BT đối ngẫu sẽ có
giá trị = 0.

+ 18x
3
Rb: 2x
1
+ x
2
+ x
3
+ s
1
= 2
x
1
+ x
2
+ 3x
3
+ s
2
= 4
Bài toán đối ngẫu:
Min Z’ = 2u
1
+ 4u
2
Rb: 2u
1
+ u
2
- t

u
1
= 9, u
2
= 3 => (t
1
= 7, t
2
= 0, t
3
= 0) => (x
1
= 0, x
2
≠ 0, x
3
≠ 0).
Thay s
1
= 0, s
2
= 0, x
1
= 0 vào các ràng buộc của BT gốc, tính được x
2
= 1, x
3
= 1.
12
1. Bài toán Đối ngẫu (tt9)

1
, x
2
≥ 0 u
1
, u
2
≥0
Giải bài toán gốc bằng phương pháp đơn hình.
(Xem bảng đơn hình cuối cùng của bài toán đối ngẫu.)
Giải bài toán đối ngẫu bằng phương pháp đơn hình.
(Xem bảng đơn hình cuối cùng của bài toán gốc.)
Nhận xét đó minh họa rõ ý trong mục 1.3.
13
1. Bài toán Đối ngẫu (tt10)
Giải bài toán gốc bằng phương pháp đơn hình
Min Z = 7x
1
+ 12x
2
Max Z
o
= -7x
1
– 12x
2
– Ma
1
– Ma
2

≥ 0 x
1
, x
2
, s
1
, s
2
, a
1
, a
2
≥ 0
x
1
x
2
s
1
s
2
a
1
a
2
Z RHS
2 3 -1 0 1 0 0 15
1 2 0 -1 0 1 0 8
7 12 0 0 M M 1 0
14

1/2 0 -1 3/2* 1 -3/2 0 3
1/2 1 0 -1/2 0 1/2 0 4
1-1/2M 0 M 6-3/2M 0 -6+5/2M 1 -3M-48
15
1. Bài toán Đối ngẫu (tt12)
x
1
x
2
s
1
s
2
a
1
a
2
Z RHS
1/3* 0 -2/3 1 2/3 -1 0 2
2/3 1 -1/3 0 1/3 0 0 5
-1 0 4 0 M-4 M 1 -60
Nghiệm: x
1
= 6; x
2
= 1; s
1
= 0; s
2
= 0; a

+ 8u
2
Max Z’ = 15u
1
+ 8u
2
2u
1
+ u
2
≤ 7 2u
1
+ u
2
+ t
1
= 7
3u
1
+ 2u
2
≤ 12 3u
1
+ 2u
2
+ t
2
= 12
u
1

1
t
2
Z RHS
1 1/2 1/2 0 0 7/2
0 1/2* -3/2 1 0 3/2
0 -1/2 15/2 0 1 105/2
u
1
u
2
t
1
t
2
Z RHS
1 0 2 -1 0 2
0 1 -3 2 0 3
0 0 6 1 1 54
Nghiệm: u
1
= 2; u
2
= 3; t
1
= 0; t
2
= 0; Z’
max
= 54.

2
= 0 cho biết u
1
≠ 0 và u
2
≠ 0. Giá trị 2 và 3 (hàng dưới
cùng ứng với 2 biến bù s
1
và s
2
) chính là nghiệm của bài toán đối
ngẫu u
1
= 2, u
2
= 3.

Nhận xét này minh họa rõ ý trong mục 1.3.
19
2. Phân tích độ nhạy (Sensitive Analysis)
cho Bài toán QHTT 2 biến bằng đồ thị
Phân tích độ nhạy là phân tích sự thay đổi của nghiệm tối ưu khi một
thông tin nào đó của bài toán QHTT ban đầu thay đổi
1. Thay đổi thông số của vế phải ràng buộc, b
i

2. Thay đổi hệ số trong hàm mục tiêu 
3. Thay đổi hệ số trong ma trận ràng buộc
4. Thêm vào một biến quyết định mới
5. Thêm vào một ràng buộc mới

20
18
3
4
5
21
50
90
250
Diện tích
Lượng nước
Nhân lực
Giá trị của biến
2 x
1
6 x
1
20 x
1
x
1
+
+
+
,
3 x
2
4 x
2
5 x

1
6 x
1
20 x
1
x
1
+
+
+
,
3 x
2
4 x
2
5 x
2
x
2
=
=
=
=
50
90
250
0
22
2. Phân tích độ nhạy
cho Bài toán QHTT 2 biến bằng đồ thị (tt3)

3
4
5
21
50
90
250
Diện tích
Lượng nước
Nhân lực
Giá trị của biến
2 x
1
6 x
1
20 x
1
x
1
+
+
+
,
3 x
2
4 x
2
5 x
2
x