• Cả hai bài toán đều ở dạng chuẩn tắc;
• Một bài toán min, một bài toán max; • Một bài toán min, một bài toán max;
• Số biến của bài toán này là số ràng buộc của bài
toán kia và ngược lại;
• và đổi vai trò cho nhau
18 trang |
Chia sẻ: lylyngoc | Lượt xem: 1723 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Chương 2 Lý thuyết đối ngẫu, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Chương 2
LÝ THUYẾT ĐỐI NGẪU
20/6/2012 1MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
NỘI DUNG
1. Bài toán đối ngẫu quy hoạch tuyến tính
1.1 Xây dựng bài toán đối ngẫu
1.2 Các định lý đối ngẫu
2. Phương pháp đơn hình đối ngẫu
20/6/2012 2MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
Bài toán đối ngẫu QHTT
1. Xây dựng bài toán đối ngẫu QHTT
Xét bài toán
( ) nmi
n
jjcf x x
=
= →∑
20/6/2012 3MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
1
, 1,
( )
0, 1, .
j
n
iij j
j
j
ba x i m
P
x j n
=
≥ =
≥ =
∑
Bài toán đối ngẫu QHTT
Bài toán đối ngẫu của bài toán trên là
1
( ) xma
m
i
i
m
ibg y y
=
= →
∑
∑
20/6/2012 4MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
, 1,( )
0, 1, .
jij i
i
i
ca y j n
D
y i m
=
≤ =
≥ =
Bài toán đối ngẫu QHTT
Nhận xét:
• Cả hai bài toán đều ở dạng chuẩn tắc;
• Một bài toán min, một bài toán max;
• Số biến của bài toán này là số ràng buộc của bài
toán kia và ngược lại;
• và đổi vai trò cho nhau.
20/6/2012 5MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
jc ib
Bài toán đối ngẫu QHTT
Ví dụ 1 Lập bài toán đối ngẫu của bài toán sau
1 2 3
1 2 3
( ) 3 2 5 min
2 4 6
f x x x x
x x x
= + + →
− + + ≥
20/6/2012 6MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1 2 35 2 8
0, 1,2,3j
x x x
x j
− + ≥
≥ =
Bài toán đối ngẫu QHTT
1 2 3
1 2 3
1 2 3
( ) min
2 4
( ) 5 2
0, 1,2,
3
8
5
6
2
3
f x x x x
x x x
P x x x
x j
= + + →
− + + ≥
− + ≥
≥ = ( ) max6 8g y y y= + →
20/6/2012 7MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
j 1 2
1 2
1 2
1 2
1 2
32
5( )
4 2
0, 0
5
2
y y
y y
D
y y
y y
− + ≤
− ≤
+ ≤
≥ ≥
Bài toán đối ngẫu QHTT
Quy tắc lập bài toán đối ngẫu
Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc)
Biến: Biến:
Hàm mục tiêu: Hàm mục tiêu:
1 2, ,..., nx x x 1 2, ,..., my y y
n
∑
m
∑
Ràng buộc: Dấu của biến:
20/6/2012 8MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
( ) minj j
j
f x c x
=
= →
1
( ) maxi i
i
g y b y
=
= →
1
2
1
3
,
,
,
in
ij j i
j
i
b i I
a x b i I
b i I=
≥ ∈
= ∈
≤ ∈
∑
1
2
3
0,
,
0,
i
i I
y i I
i I
≥ ∈
∈ ∈
≤ ∈
ℝ
Bài toán đối ngẫu QHTT
Quy tắc lập bài toán đối ngẫu (tt)
Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc)
Dấu của biến: Ràng buộc:
,c j J≤ ∈≥ ∈
20/6/2012 9MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
2
1
3
,
,
j
m
ij i j
i
j
a y c j J
c j J=
= ∈
≥ ∈
∑
1
2
3
0,
,
0,
j
j J
x j J
j J
∈ ∈
≤ ∈
ℝ
Bài toán đối ngẫu QHTT
Ví dụ 2 Lập bài toán đối ngẫu của bài toán sau
1 2 3
1 2 3
( ) 2 7 min
3 5 4 1
f x x x x
x x x
= + + →
+ − ≥
− + =
20/6/2012 10MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1 2 3
1 2 3
1 2 3
2 2 4( )
2 6 8
0, 0,
x x x
P
x x x
x x x
+ + ≤
≥ ≤ ∈ ℝ
Bài toán đối ngẫu của bài toán trên:
1 2 3
1 2 3
( ) 4 8 max
3 2 2
5 2 1
g y y y y
y y y
y y y
= + + →
+ + ≤
− + ≥
20/6/2012 11MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1 2 3
1 2 3
1 2 3
( )
4 2 6 7
0, , 0
D
y y y
y y y
− + + =
≥ ∈ ≤ ℝ
Bài toán đối ngẫu QHTT
2. Định lý đối ngẫu
Định lý 1 (Đối ngẫu yếu)
Nếu x là PA của (P) và y là PA của (D), thì
... ...c x c x c x b y b y b y+ + + ≥ + + +
20/6/2012 12MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1 1 2 2 1 1 2 2
( ) ( )
n n m m
f x g y= =
Bài toán đối ngẫu QHTT
Định lý 2 (đối ngẫu mạnh)
Nếu một QH có PATƯ thì QH đối ngẫu của nó cũng
có PATƯ và giá trị mục tiêu của chúng là bằng nhau.
20/6/2012 13MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
Bài toán đối ngẫu QHTT
Định lý 3 (Định lý tồn tại)
Đối với mỗi cặp bài toán (P) và (D), một trong ba
khả năng sau xảy ra:
i) Cả (P) và (D) đều không có PA.
ii) Cả (P) và (D) đều có PA. Khi đó, chúng sẽ có
PATƯ và giá trị mục tiêu là bằng nhau.
iii) Một QH có PA còn QH kia thì không. Khi đó,
QH có PA sẽ không có PATƯ.
20/6/2012 14MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
Bài toán đối ngẫu QHTT
Định lý 4 (đk độ lệch bù (yếu))
Một cặp PA x, y của (P) và (D) là những PATƯ khi
và chỉ khi chúng nghiệm đúng hệ:
0 1, (1)
n
y a x b i m − = ∀ =
∑
20/6/2012 15MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
1
(1 2, )0
m
j j i
i ij j i
j
j i
i
x c a y j n
=
=
− = ∀ =
∑
Phương pháp đơn hình đối ngẫu
Là phương pháp đơn hình áp dụng cho bài toán
đối ngẫu nhưng để tìm nghiệm cho bài toán gốc và
các bước tính toán đều làm trên bài toán gốc.
20/6/2012 16MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
Phương pháp đơn hình đối ngẫu
Thuật toán:
Xuất phát từ “giả PA” (thỏa mãn ràng buộc và
dấu hiệu tối ưu nhưng chưa thỏa mãn đk
0x
0,j j∆ ≤ ∀
0).x ≥
- Lập bảng đơn hình đối ngẫu với giả PA
- Kiểm tra: nếu các phần tử trên cột giả PA đều
không âm thì dừng thuật toán. Ngược lại, tìm (giả)
PA mới:
+ Chọn biến ra: là biến nằm trên dòng có
phần tử âm nhỏ nhất ở cột giả PA.
20/6/2012 17MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
0
.x
Phương pháp đơn hình đối ngẫu
+ Chọn biến vào: lập tỉ số giữa các phần tử
ở dòng ước lượng với các phần tử âm ở
dòng quay (dòng chứa biến ra), chọn tỉ số
nhỏ nhất.
Chỉ số tương ứng với tỉ số nhỏ nhất là chỉ số của
biến vào.
- Lập bảng đơn hình mới, với các số liệu được
tính toán giống như thuật toán đơn hình thông
thường.
- Quay lại bước Kiểm tra.
20/6/2012 18MaMH: 501014 Chương 2: Lý thuyết đối ngẫu