10/26/2012<br />
<br />
ĐẠI HỌC TÀI CHÍNH – MARKETING<br />
BỘ MÔN TOÁN – KHOA CƠ BẢN<br />
<br />
Bài giảng<br />
QUY HOẠCH TUYẾN TÍNH<br />
<br />
ThS.<br />
ThS. Nguyeãn Vaên Phong<br />
Email : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vn<br />
<br />
Chương 2. BÀI TOÁN ĐỐI NGẪU<br />
1. KHÁI NIỆM - THÀNH LẬP BÀI TOÁN ĐỐI NGẪU<br />
2. CÁC ĐỊNH LÝ ĐỐI NGẪU<br />
3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU<br />
<br />
2<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
KHÁI NIỆM – THÀNH LẬP<br />
Tùy thuộc vào dạng của bài toán QHTT gốc (P) khi đó<br />
ta xây dựng bài toán đối ngẫu (D) như sau<br />
Gốc<br />
(P)<br />
<br />
min c , x<br />
<br />
Đối<br />
ngẫu (D)<br />
<br />
max b , y<br />
<br />
a i , x = bi , i ∈ M1<br />
<br />
Dấu<br />
<br />
y i töï do, i ∈ M1<br />
<br />
a , x ≤ bi , i ∈ M2<br />
<br />
y i ≤ 0,<br />
<br />
i ∈ M2<br />
<br />
a i , x ≥ bi , i ∈ M3<br />
<br />
y i ≥ 0,<br />
<br />
i ∈ M3<br />
<br />
x j ≥ 0,<br />
<br />
Ràng<br />
Buộc<br />
<br />
j ∈ N1<br />
<br />
A j , y ≤ c j , j ∈ N1<br />
<br />
x j ≤ 0,<br />
<br />
j ∈ N2<br />
<br />
Aj , y ≥ c j , j ∈ N2<br />
<br />
i<br />
<br />
x j töï do, j ∈ N3<br />
<br />
Dấu<br />
<br />
Aj , y = c j , j ∈ N3<br />
<br />
Ràng<br />
Buộc<br />
<br />
M1 + M2 + M3 = m , N1 + N2 + N3 = n<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
3<br />
NGUYEÃN VAÊN PHONG<br />
<br />
1<br />
<br />
10/26/2012<br />
<br />
KHÁI NIỆM – THÀNH LẬP<br />
QUAN HỆ GIỮA BT (P) VÀ BT (D) như sau<br />
- Mục tiêu của hai bài toán thì đối ngẫu (min ↔ max)<br />
- Số ràng buộc của (P) bằng với số ẩn của (D)<br />
- Số ẩn của (P) bằng với số ràng buộc của (D)<br />
- Dấu của ẩn của (P) và Dấu ràng buộc của (D) thì<br />
trái dấu.<br />
QUY TẮC:<br />
MIN<br />
<br />
MAX<br />
<br />
MIN<br />
<br />
RÀNG<br />
BUỘC<br />
<br />
RÀNG<br />
BUỘC<br />
<br />
RÀNG<br />
BUỘC<br />
<br />
DẤU<br />
<br />
DẤU<br />
4<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
CÁC ĐỊNH LÝ ĐỐI NGẪU<br />
1. Định lý đối ngẫu (Yếu). Nếu x là một PACNĐ bất kỳ của<br />
(P) và y là một PACNĐ bất kỳ của (D), thì b, y ≤ c , x<br />
2. Hệ quả. Giả sử x là một PACNĐ của (P) và y là một<br />
PACNĐ của (D), và b, y = c , x . Khi đó x là PATƯ của (P)<br />
và y PATƯ của (D)<br />
3. Định lý đối ngẫu (Mạnh). Nếu một bài toán có PATU thì<br />
bài toán đối ngẫu của nó cũng có PATU và giá trị TU của<br />
hai hàm mục tiêu bằng nhau.<br />
Chứng minh. Trước hết ta nhắc lại một số ký hiệu sau<br />
Baøi toaùn (D)<br />
Baøi toaùn (P)<br />
<br />
f = c , x → min<br />
<br />
g = b, y → max<br />
<br />
Ax = b<br />
x ≥0<br />
<br />
AT y ≤ c<br />
y töï do<br />
5<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
CÁC ĐỊNH LÝ ĐỐI NGẪU<br />
*<br />
<br />
Giaû söû x laø PATU cuûa (P), ta coù<br />
<br />
{<br />
<br />
}<br />
<br />
{<br />
<br />
}<br />
<br />
{<br />
<br />
}<br />
<br />
B * = Aj , j ∈ J ( x * ) , CB* = c j , j ∈ J ( x * ) , X B * = x *j , j ∈ J ( x * )<br />
Khi ñoù, ta coù<br />
X B * = (B * )−1 b vaø fmin = f ( x * ) = CB * (B * )−1 b<br />
Vaø vì x * laø PATU neân<br />
∆ k = CB* (B * )−1 Ak − ck ≤ 0, ∀k<br />
hay<br />
T<br />
<br />
AT CB* (B * )−1 − c ≤ 0<br />
<br />
<br />
T<br />
<br />
Ta ñaët y * = CB * (B * )−1 thì AT y * ≤ c (y* laø ACNÑ cuûa (D))<br />
<br />
<br />
Hôn nöõa<br />
T<br />
<br />
6<br />
b, y * = y * b = CB* (B * )−1 b = CB * X B* = c , x * NGUYEÃN VAÊN PHONG<br />
(ñpcm)<br />
<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
2<br />
<br />
10/26/2012<br />
<br />
CÁC ĐỊNH LÝ ĐỐI NGẪU<br />
4. Định lý độ lệch bù. Giả sử x là PACNĐ của (P), y là<br />
PACNĐ của (D). Khi đó x là PATU của (P) và y là PATU của<br />
(D), nếu và chỉ nếu<br />
<br />
<br />
Ax − b, y = 0<br />
<br />
T<br />
c − A y,x = 0<br />
<br />
Áp dụng.<br />
<br />
Vì x ≥ 0, y ≥ 0 neân ñònh lyù ñöôïc vieát laïi nhö sau<br />
y i > 0 ⇒ a i , x = bi<br />
− bi y i = 0, ∀i ⇔ i<br />
a , x − bi > 0 ⇒ y i = 0<br />
<br />
x j > 0 ⇒ Aj , y = c j<br />
(II ) : c j − y , Aj x j = 0, ∀j ⇔ <br />
c j − y , A j > 0 ⇒ x j = 0<br />
<br />
(I ) :<br />
<br />
( a ,x<br />
i<br />
<br />
(<br />
<br />
)<br />
<br />
)<br />
<br />
7<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
1. Hệ phương trình đối ngẫu. Xét hai hệ sau<br />
Hệ (I)<br />
a11x1<br />
<br />
<br />
a j 1x1<br />
<br />
<br />
am1x 1<br />
<br />
c1x1<br />
<br />
Hệ (II)<br />
<br />
− a11y 1<br />
<br />
<br />
− a1i y 1<br />
<br />
<br />
− a1n y 1<br />
<br />
− b1y 1<br />
<br />
+ ... + a1i x i<br />
...<br />
<br />
+ ... + a1n x n<br />
...<br />
<br />
+ x n+1<br />
<br />
= b1<br />
<br />
+ ... + a ji x i<br />
...<br />
<br />
+ ... + a jn x n<br />
...<br />
<br />
+ x n+ j<br />
<br />
= bj<br />
<br />
+ ... + ami x i<br />
+ ... + ci x i<br />
<br />
+ ... + amn x n<br />
+ ... + cn x n<br />
<br />
+ x n+ m<br />
+ f<br />
<br />
= bm<br />
= α<br />
<br />
− ... − a j 1y j<br />
<br />
− ... − am 1y m<br />
<br />
+ y m +1<br />
<br />
= c1<br />
<br />
− ... − a ji y j<br />
<br />
− ... − ami y m<br />
<br />
+ y m +i<br />
<br />
= ci<br />
<br />
− ... − a jn y j<br />
− ... − b j y j<br />
<br />
− ... − amn x n<br />
− ... − bm y m<br />
<br />
+ y m +n<br />
+ g<br />
<br />
= cn<br />
= −α<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
8<br />
NGUYEÃN VAÊN PHONG<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
Hệ (I), (II) được gọi là đối ngẫu, nếu<br />
- Hệ số các ẩn tự do trong phương trình thứ j của hệ (I) và hệ<br />
số của ẩn tự do thứ j của hệ (II) (hệ số của yj trong các<br />
phương trình của hệ (II)) thì đối nhau.<br />
- Số hạng tự do của hệ (I) và hệ số các ẩn tự do của phương<br />
trình cuối hệ (II) thì đối nhau.<br />
- Số hạng tự do của hệ (II) và hệ số các ẩn tự do của phương<br />
trình cuối hệ (I) thì bằng nhau.<br />
- Số hạng tự do phương trình cuối trong hai hệ thì đối nhau.<br />
Khi đó, ta có sự tương quan giữa các ẩn tự do của hệ này<br />
với các ẩn cơ sở của hệ kia, như sau<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
9<br />
NGUYEÃN VAÊN PHONG<br />
<br />
3<br />
<br />
10/26/2012<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
2. Hai bài toán đối ngẫu<br />
Từ định lý đối ngẫu mạnh, ta có nhận xét sau:<br />
- Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU),<br />
- Sau đó ta thực hiện một phép biến đổi cơ sở tương<br />
ứng trong BT (D) cũng tối ưu.<br />
- Khi đó, nghiệm cơ sở TU của BT (D) được xác định<br />
như sau :<br />
- Giả sử cơ sở tối ưu của bài toán min là {x1, x2, …,xn} ,<br />
{xn+1, xn+2, …,xn+m}, là các ẩn tự do mà đối với cơ sở này bài<br />
toán min đạt cực tiểu.<br />
- Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2,<br />
…,ym} , {ym+1, ym+2, …,ym+n}, là các ẩn tự do.<br />
- Khi đó, hai BT này tạo thành hai hệ phương trình đối<br />
ngẫu.<br />
10<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
2. Hai bài toán đối ngẫu<br />
Từ định lý đối ngẫu mạnh, ta có nhận xét sau:<br />
- Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU),<br />
- Sau đó ta thực hiện một phép biến đổi cơ sở tương<br />
ứng trong BT (D) (max) cũng tối ưu.<br />
- Khi đó, nghiệm cơ sở TU của BT (D) được xác định<br />
như sau:<br />
- Giả sử cơ sở tối ưu của bài toán min là {x1, x2, …,xn} ,<br />
các ẩn {xn+1, xn+2, …,xn+m}, là các ẩn tự do mà đối với cơ sở<br />
này bài toán min đạt cực tiểu.<br />
- Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2,<br />
…,ym} , các ẩn {ym+1, ym+2, …,ym+n}, là các ẩn tự do.<br />
- Khi đó, hai BT này tạo thành hai hệ phương trình đối<br />
ngẫu. Và các ẩn của chúng có quan hệ như trong phần 1.<br />
11<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
2. Hai bài toán đối ngẫu<br />
Và nghiệm của bài toán (D) được xác<br />
định như sau:<br />
Chú ý. Ta thấy trong cặp bài toán đối<br />
ngẫu nhau chỉ xảy ra một trong ba<br />
trường hợp sau :<br />
* Trường hợp 1. Cả hai bài toán cùng có<br />
phương án thì cả hai bài toán cùng có<br />
phương án tối ưu.<br />
* Trường hợp 2. Bài toán này có phương<br />
án, bài toán kia không có phương án thì<br />
cả hai bài toán không có phương án tối<br />
ưu.<br />
* Trường hợp 3. Cả hai bài toán không<br />
có phương án thì hiển nhiên cả hai<br />
không có phương án tối ưu.<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
y1<br />
<br />
...<br />
ym<br />
<br />
<br />
y m +1<br />
...<br />
<br />
<br />
y m+n<br />
<br />
= cn +1<br />
... ...<br />
= cm<br />
= c1<br />
... ...<br />
=<br />
<br />
cn<br />
<br />
Trong đó, các cj là<br />
các hệ số của các<br />
ẩn trong hàm mục<br />
tiêu ở bảng đơn<br />
hình TU<br />
12<br />
NGUYEÃN VAÊN PHONG<br />
<br />
4<br />
<br />
10/26/2012<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
3. Thuật toán đơn hình đối ngẫu<br />
Nghĩa là: Ta dùng thuật toán đơn hình trên bài toán đối ngẫu<br />
và sử dụng mối quan hệ giữa các ẩn của hai bài toán đê suy<br />
ra nghiệm cho bài toán gốc và ngược lại.<br />
Ví dụ. Tìm nghiệm của bài toán sau bằng thuật toán đơn hình<br />
đối ngẫu.<br />
BT (P)<br />
<br />
BT (D)<br />
<br />
g = x 1 − x 2 → min<br />
<br />
f = − y 1 − 2 y 2 − 3 y 3 → max<br />
− y 1 + 2 y 2 − 3y 3<br />
<br />
2y 1 − y 2 − y 3<br />
y 1 , y 2 , y 3 ≥ 0.<br />
<br />
− x1 + 2 x 2<br />
<br />
2 x1 − x 2<br />
−3 x − x<br />
1<br />
2<br />
<br />
<br />
≤ 1<br />
≤ −1<br />
<br />
≥ −1<br />
≥ −2<br />
≥ −3<br />
<br />
x 1 , x 2 ≥ 0.<br />
13<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
3. Thuật toán đơn hình đối ngẫu<br />
Trước tiên, ta viết hai bài toán này thành hai hệ đối ngẫu.<br />
BT (P)<br />
<br />
− y 1 + 2y 2 − 3y 3 + y 4<br />
<br />
2y 1 − y 2 − y 3<br />
y + 2y + 3 y<br />
1<br />
2<br />
3<br />
<br />
1<br />
=<br />
= −1<br />
<br />
+ y5<br />
+f<br />
<br />
=<br />
<br />
0<br />
<br />
BT (D)<br />
<br />
=<br />
x1 − 2 x 2 + x 3<br />
<br />
+ x4<br />
=<br />
−2 x 1 + x 2<br />
<br />
+ x5<br />
=<br />
3 x1 + x 2<br />
− x1 + x 2<br />
+g =<br />
<br />
<br />
1<br />
2<br />
3<br />
0<br />
14<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUẬT TOÁN ĐỐI NGẪU<br />
Đối với (D), ta chuyển về dạng chuẩn như sau<br />
g = x 1 − x 2 → min ( g − x 1 + x 2 = 0 )<br />
<br />
x1 − 2 x 2 + x 3<br />
<br />
+ x4<br />
−2 x 1 + x 2<br />
3 x + x<br />
+ x5<br />
2<br />
1<br />
x 1, x 2 , x 3 , x 4 , x 5 ≥ 0.<br />
<br />
= 1<br />
= 2<br />
= 3<br />
<br />
Và lập bảng đơn hình<br />
Hệ số<br />
CB<br />
<br />
Cơ sở<br />
B<br />
<br />
Phương<br />
án<br />
<br />
1<br />
<br />
-1<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
A1<br />
<br />
A2<br />
<br />
A3<br />
<br />
A4<br />
<br />
A5<br />
<br />
0<br />
<br />
A3<br />
<br />
1<br />
<br />
1<br />
<br />
-2<br />
<br />
1<br />
<br />
0<br />
<br />
0<br />
<br />
0<br />
<br />
A4<br />
<br />
2<br />
<br />
-2<br />
<br />
1<br />
<br />
0<br />
<br />
1<br />
<br />
0<br />
<br />
0<br />
<br />
A5<br />
<br />
3<br />
<br />
3<br />
<br />
1<br />
<br />
0<br />
<br />
0<br />
<br />
1<br />
<br />
g<br />
<br />
0<br />
<br />
-1<br />
<br />
1<br />
<br />
0<br />
<br />
0<br />
<br />
θ<br />
<br />
0<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
15<br />
NGUYEÃN VAÊN PHONG<br />
<br />
5<br />
<br />
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
