Đây là tài liệu cung cấp về mối quan hệ giữa các bài toán đối ngẫu thông qua các định lý, các hệ quả, các ví dụ và bài tập điển hình. Giúp người đọc nắm rõ được kiến thức về bài toán đối ngẫu, mời các bạn tham khảo
AMBIENT/
Chủ đề:
Nội dung Text: Các định lý cơ bản về cặp bài toán đối ngẫu 2016
- §2 Các định lý cơ bản về cặp bài toán đối
ngẫu
1. Mối quan hệ giữa cặp bài toán đối ngẫu
2. Ứng dụng của bài toán đối ngẫu:
2. 1. Tìm PATƯ của bài toán đối ngẫu
2. 2. Chứng tỏ tính tối ưu của một phương
án
2. 3. Giải bài toán có dạng đặc biệt.
- Mối quan hệ giữa cặp bài toán đối ngẫu
f (x) = c1x1 + c 2 x 2 + ...... + c n x n Min (Max)
a11x1 + a12 x 2 + ...... + a1n x n = b1
....................................................
a m1x1 + a m2 x 2 + ...... + a mn x n = b m
xj 0 ∀j = 1, n
Bài toán đối ngẫu:
g(y) = b1y1 + b 2 y 2 + ...... + b m y m Max (Min)
a11 y1 + a 21y 2 + ...... + a m1 y m c1 ( c1 )
....................................................
a1n y1 + a 2n y 2 + ...... + a mn y m cn ( cn )
- Mối quan hệ giữa cặp bài toán đối ngẫu
Mối quan hệ giữa hai bài toán được thể hiện
trong các định lý sau:
Định lý 1: Đối với cặp bài toán đối ngẫu bao giờ
cũng chỉ xẩy ra một trong 3 trường hợp sau:
- Cả hai bài toán đều không có phương án.
- Cả hai bài toán đều có phương án, lúc đó
cả hai bài toán đều có PATƯ và giá trị hàm mục
tiêu của chúng bằng nhau
- Một trong 2 bài toán không có phương án,
bài toán kia có phương án, khi ấy bài toán có
phương án sẽ không có PATƯ.
- Mối quan hệ giữa cặp bài toán đối ngẫu
Hệ quả 1: Nếu một trong 2 bài toán đối ngẫu có
PATƯ thì bài toán kia cũng có PATƯ
- Mối quan hệ giữa cặp bài toán đối ngẫu
Hệ quả 2: x0, y0 là hai phương án của bài toán (I),
(I’), khi đó x0, y0 là PATƯ khi và chỉ khi
f(x0) = g(y0)
Chứng minh:
Điều kiện cần: Được suy từ định lý trên
Điều kiện đủ:
Gọi x’ là phương án bất kì của bài toán (I),
khi đó ta có:
n n � m �, m �n �0
f (x ') = � jx ,j
c �� ijyi � j =
� a
0
x � � ijx j �i
� a
,
y
j =1 j = 1 �=1
i � i = 1 �=1
j �
m
= bi y = g(y ) = g(x )
0
i
0 0
i =1
- Mối quan hệ giữa cặp bài toán đối ngẫu
Hay x0 là PATƯ.
Mặt khác do f(x0) = g(y0) nên theo định lý
trên y0 cũng là PATƯ.
Định lý 2: (Tiêu chuẩn tối ưu)
Hai phương án của cặp bài toán đối ngẫu là
PATƯ khi và chỉ khi với mỗi cặp ràng buộc đối
ngẫu nếu một ràng buộc thõa mãn với dấu bất
đẳng thức thực sự thì ràng buộc kia thõa mãn với
dấu bằng.
Chứng minh:
- Mối quan hệ giữa cặp bài toán đối ngẫu
x0 = (x01, x02 , ... , x0n) và y0 = (y01, y02, ... , y0m) lần
lượt là PATƯ cua bài toán (I) và (I’)
Xét đẳng thức:
m n
g(y 0 ) − f (x 0 ) = � i .y i0 − � j .x 0
b c j
i =1 j =1
m �n �0 n
= �� ij .x j � i − � j .x j
� a
0
.y c 0
i =1 � 1
j= � j =1
n � m �0 n
= �� ij .yi0 � j − � j .x 0
� a .x c j
j =1 � 1
i= � j =1
n � m �0
= �� ij .yi − c j � j
� a
0
.x
j =1 � 1
i= �
- Mối quan hệ giữa cặp bài toán đối ngẫu
Do x0, y0 là PATƯ khi và chỉ khi:
n � m �0
g(y ) − f (x ) = � � ij .y i − c j � j = 0
0 0
� a
0
.x
j =1 � 1
i= �
Điều kiện cần: x0, y0 là PATƯ nên:
� m n �0
g(y ) − f (x ) = � � ij .y i − c j � j = 0
0 0
� a
0
.x
j =1 � 1
i= �
m
Mặt khác ta có: a ij .y 0
i c j và x 0
j 0 ∀j = 1, n
i =1 m
Vì vậy: - Nếu x j > 0 thì:
0 a ij .y = c j
0
i
i =1
m
- Nếu a ij .y < c j
0
i thì x0j = 0
i =1
- Mối quan hệ giữa cặp bài toán đối ngẫu
Điều kiện đủ: Hiển nhiên được suy ra từ bất
đẳng thức trên
Định lý 3: (Tiêu chuẩn tối ưu phát biểu cho cặp
bài toán đối ngẫu tổng quát)
Điều kiện cần và đủ để 2 phương án x0, y0
của cặp bài toán đối ngẫu tối ưu là trong mỗi cặp
ràng buộc đối ngẫu nếu ràng buộc này thõa mãn
với dấu bất đẳng thức thực sự thì ràng buộc kia
thõa mãn với dấu bằng.
- Ứng dụng của bài toán đối ngẫu
2.1 Tìm PATƯ của bài toán đối ngẫu
PP 1: Nhờ tiêu chuẩn tối ưu nên khi ta biết
được PATƯ của một trong cặp bài toán đối ngẫu
thì ta dễ dàng tìm được PATƯ của bài toán còn
ạ
lVíi.dụ 1: Cho bài toán QHTT sau:
f (x) = 3x1 + 4x 2 + x 3 min
−3x1 + 2x 2 − 4x 3 15
2x1 − x 2 − 5x 3 8
4x1 + 2x 2 + 2x 3 10
x1 0; x 2 0; x 3 0
Cho biết bài toán trên có PATƯ là x0 = (7, 0, -9).
Hãy lập và giải bài toán đối ngẫu của bài toán trên.
- Tìm PATƯ của bài toán đối ngẫu
Giải:
Bài toán đối ngẫu là:
f(x) = 15y1 + 8y2 + 10y3 → Max
Các ràng buộc:
-3y1 + 2y2 + 4y3 ≤ 3
2y1 - y2 + 2y3 ≤ 4
-4y1 - 5y2 + 2y3 ≤ 1
Trong đó: y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Do bài toán đối ngẫu có phương án tối ưu là
x0 = (7, 0, -9) nên theo định lí độ lệch bù yếu ta có:
-3y1 + 2y2 + 4y3 = 3 (1)
-4y1 -5y2 + 2y3 = 1 (2)
- Tìm PATƯ của bài toán đối ngẫu
Mặt khác khi thay phương án x0 vào các ràng
buộc của bài toán gốc ta thấy ràng buộc thứ ba
thõa mãn không chặt nên:
y2 = 0 (3)
Từ hệ phương trình (1), (2), (3) ta dễ dàng
suy ra nghiệm là y0 = (1/5, 0, 9/10) ta thấy
nghiệm này thõa mãn hai ràng buộc còn lại của
bài toán đối ngẫu nên nó là PATƯ của bài toán
đối ngẫu. bài toán đối ngẫu có phương án tối ưu
Vậy
là: y0 = (1/5, 0, 9/10) và g(y0) = 12.
- Tìm PATƯ của bài toán đối ngẫu
Phương pháp 2: (Sử dụng bảng đơn hình)
Để vận dụng PP này ta dùng thuật toán đơn
hình để giải (I), khi đó PATƯ của bài toán (I’) s ẽ
là: yi = cj + ∆ j i = 1, 2, …. , m
cj, ∆ j là hệ số tương ứng với ẩn cơ sở xj của
phương trình thứ i trong bảng đơn hình đầu tiên.
∆ j là hệ số trong bảng đơn hình cuối cùng ứng với
PATƯ.
Lưu ý: Trong bảng đơn hình đối với bài toán (I)
cần phải đưa vào cột đơn hình ứng với ẩn giả
- Tìm PATƯ của bài toán đối ngẫu
Ví dụ: Cho bài toán QHTT :
f(x) = x1 + 2x2 + 3x3 + 3x4 → Max
Các ràng buộc:
2x1 + x2 + x3 + 2x4 ≤ 20
x1 + 2x2 + 3x3 + 4x4 = 18
2x1 + x2 + 2x3 + x4 ≥ 16
Trong đó:
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
a. Hãy giải bài toán.
b. Hãy viết bài toán đối ngẫu và chỉ ra
PATƯ của bài toán đối ngẫu.
- Tìm PATƯ của bài toán đối ngẫu
Bài toán ở dạng chuẩn:
f(x) = x1 + 2x2 + 3x3 + 3x4 – Mx7 – Mx8 → Max Các
ràng buộc:
2x1 + x2 + x3 + 2x4 + x5 = 20
x1 + 2x2 + 3x3 + 4x4 + x7 = 18
2x1 + x2 + 2x3 + x4 - x6 + x8 = 16
Trong đó:
x5, x6 là biến phụ; x7, x8 là biến giả
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0;
x7 ≥ 0; x8 ≥ 0
- Tìm PATƯ của bài toán đối ngẫu
ci xi yi y1 y2 y3 y4 y5 y6 y7 y8
0 x5 20 2 1 1 2 1 0 0 0
-M x7 18 1 2 3 4 0 0 1 0
-M x8 16 2 1 2 1 0 -1 0 1
f(x) 0 -1 -2 -3 -3 0 0 0 0
-34 -3 -3 -5 -5 0 1 0 0
- Tìm PATƯ của bài toán đối ngẫu
ci xi yi x1 x2 x3 x4 x5 x6 x7 x8
0 x5 14 5/3 1/3 0 2/3 1 0 -1/3 0
3 x3 6 1/3 2/3 1 4/3 0 0 1/3 0
-M x8 4 4/3 -1/3 0 -5/3 0 -1 -2/3 1
f(x) 18 0 0 0 1 0 0 1 0
-4 -4/3 1/3 0 5/3 0 1 1/3 0
- Tìm PATƯ của bài toán đối ngẫu
ci xi bi x1 x2 x3 x4 x5 x6 x7 x8
0 x5 9 0 3/4 0 11/4 1 5/4 1/2 -5/4
3 x3 5 0 3/4 1 7/4 0 1/4 1/2 -1/4
1 x1 3 1 -1/4 0 -5/4 0 -3/4 -1/2 3/4
f(x) 18 0 0 0 1 0 0 1+M M
PATƯ của bài toán mở rộng là : (3,0,5,0,9,0,0,0)
Giá trị hàm mục tiêu đạt được là : f(x) = 18
PATƯ của bài toán xuất phát: (3,0,5,0)
fmax = 18
- Chứng tỏ tính tối ưu của một phương án
Vấn đề: Không giải bài toán QHTT xem xét
phương án x0 có là PATƯ hay không?
Phương pháp: Lập bài toán đối ngẫu, giả sử x0 là
PATƯ sau đó dùng tiêu chuẩn tối ưu để tìm
phương án tương ứng với x0, nếu tồn tại phương
án tương ứng thì x0 là PATƯ còn không tồn tại
phương án chứng tỏ x0 không là PATƯ.
- Chứng tỏ tính tối ưu của một phương án
Ví dụ: Cho bài toán QHTT
f(x) = - 8x1 + 6x2 + 4x3 + 5x4 → min
Ràng buộc:
x1 – 2x3 + x4 ≤ 7
-2x1 + x2 – x3 + 3x4 = -4
3x1 – x2 + 2x3 – 6x4 ≥ 5
x1 ≥ 0; x2 ≥ 0; x4 ≥ 0
a. Viết bài toán đối ngẫu của bài toán trên
b. Chứng tỏ x* = (3, 0, -2, 0) là phương án. x*
có là PATƯ hay không? Tìm tập PATƯ của bài
toán đối ngẫu?
c. Tìm tập PATƯ của bài toán xuất phát?
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
