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