CHƯƠNG III MÔ HÌNH TỐI ƯU TUYẾN TÍNH (QHTT)
I. Thí dụ mở đầu II. Mô hình bài toán QHTT III. Các tính chất chung của bài toán QHTT IV. Phương pháp đơn hình V. Bài toán đối ngẫu
I. Thí dụ mở đầu
• Thí dụ 1: Bài toán lựa chọn danh mục đầu tư - Nội dung: Một công ty đầu tư dự định dùng khoản quỹ đầu tư 500 tỷ đồng để mua một số cổ phiếu trên thị trường chứng khoán. Để phòng ngừa rủi ro công ty đưa ra các yêu cầu về đa dạng hoá danh mục đầu như sau:
+ Loại cổ phiếu và giới hạn mua:
Loại CK
Giới hạn mua
Lợi tức
A
7%/năm
100 tỷ
B
8,5%/năm
300 tỷ
C
7,8%/năm
250 tỷ
D
8,2%/năm
320 tỷ
+ Tỷ lệ đầu tư vào cổ phiếu A và C phải chiếm ít nhất 55% và cổ phiếu B
phải chiếm ít nhất 15% tổng số vốn đầu tư thực hiện
- Bài toán: Với số tiền dự kiến đầu tư, hãy xác định một danh mục đầu tư sao cho đảm bảo về đa dạng hoá danh mục đầu tư và đem lại mức lợi tức lớn nhất.
- Mô hình hoá: + Gọi xA, xB, xC, xD là các khoản tiền đầu tư vào các loại chứng
khoán A, B, C, D
+ Các điều kiện về đa dạng hoá danh mục đầu tư:
(1) (2) (3) (4) (5)
0 xA 100; 0 xB 300 0 xC 250, 0 xD 320 xA + xC 0,55(xA + xB+ xC + xD) xB 0,15(xA + xB+ xC + xD) xA + xB+ xC + xD 500
+ Mức lợi tức ứng với danh mục đầu tư:
Z = 0,07xA + 0,085xB+ 0,078xC + 0,082xD (tỷ đồng)
- Xác định x = (xA, xB, xC, xD) sao cho:
Z Max; với các điều kiện (1), (2), (3), (4), (5).
- Bài toán này gọi là bài toán QHTT
• Thí dụ 2: Bài toán vận tải - Nội dung: Một công ty kinh doanh xăng dầu tại khu vực Z hàng tuần cần cung ứng xăng cho 3 trạm bán lẻ A, B và C. Công ty có thể đưa xăng đến các trạm từ tổng kho I và II. Lượng xăng dự trù cung ứng cho các trạm của kho I là 20 tấn, kho II là 40 tấn. Nhu cầu tiêu thu xăng hàng tuần của các trạm A, B, C lần lượt là 20, 15, 15 (tấn). Chi phí cho việc cung ứng xăng được cho dưới bảng sau: Đơn vị: nghìn đồng/tấn
Kho\ Trạm I
A 500
B 400
C 700
II
600
500
500
- Bài toán: Cần lập một kế hoạch cung ứng xăng từ các kho đến các trạm để đảm bảo đáp ứng đủ nhu cầu của các trạm với tổng chi phí vận chuyển là nhỏ nhất.
- Mô hình hoá: + Gọi x1A, x1B, x1C, x2A, x2B, x2C (tấn) lần lượt là các lượng xăng
vận chuyển từ kho I, kho II đến các trạm A, B, C. + Điều kiện để đáp ứng đầy đủ nhu cầu của các trạm:
x1A + x2A = 20 x1B + x2B = 15 x1C + x2C = 15
(1) (2) (3) + Điều kiện về lượng xăng dự trù cung ứng của các kho: (4) (5)
x1A + x1B + x1C 20 x2A + x2B + x2C 40 + Tổng chi phí vận chuyển: Y = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C (nghìn
đồng)
- Xác định x1A, x1B, x1C, x2A, x2B, x2C 0 sao cho:
Y Min; với các điều kiện (1), (2), (3), (4), (5)
Bài toán này gọi là bài toán QHTT
II. Mô hình bài toán QHTT
1. Bài toán dạng tổng quát 2. Một số khái niệm và định nghĩa 3. Các dạng đặc biệt
1. Bài toán dạng tổng quát - Là bài toán tìm cực trị (cực đại hoặc cực tiểu) của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương và (hoặc) các bất phương trình tuyến tính.
- Xác định véc tơ x = (x1, x2, …, xn) sao cho:
n
f x ( )
Min Max (
)
c x j
j
j
1
n
)
a x ij
j
b i ( i
I 1
j
1
n
I
)(*)
,
I
I
I
I
I
a x ij
j
b i ( i
2
I 1
2
3
2
3
I 1
1
j
n
I
)
a x ij
j
b i ( i
3
1
j
2. Một số khái niệm và định nghĩa - Hàm f(x) cần tìm cực trị gọi là hàm mục tiêu của bài toán - Hệ (*) gọi là hệ điều kiện của bài toán - Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc của bài toán và hệ điều kiện còn gọi là hệ ràng buộc - Véc tơ x thoả mãn mọi ràng buộc của bài toán gọi là một phương án
(PA) của bài toán
- Tập hợp các PA có thể có của bài toán gọi là tập PA của bài toán,
ký hiệu: D = {x: t/m (*)}
- Xét bài toán QHTT có f(x) Min và hai PA xA, xB. Khi đó: + Nếu f(xA) f(xB) thì PA xA gọi là không xấu hơn PA xB + Nếu f(xA) < f(xB) thì PA xA gọi là tốt hơn PA xB - Một PA mà tại đó hàm mục tiêu đạt cực trị gọi là PA tối ưu
(PATƯ), ký hiệu: x* và f* = f(x*) gọi là trị tối ưu, f(x*) f(x) với mọi PA x của bài toán.
- Một bài toán có ít nhất một PATƯ gọi là bài toán giải được - Một bài toán không có PA TƯ gọi là bài toán không giải được + Bài toán không có PA không có PATƯ + Bài toán có PA nhưng hàm mục tiêu không bị chặn trên tập PA - Xét với PA x: + Nếu ràng buộc i (iI) thoả mãn với dấu “=“ thì PA x gọi là thoả mãn “chặt” ràng buộc i hay ràng buộc i là chặt đối với PA x + Nếu ràng buộc i (iI) thoả mãn với dấu “>” hoặc “<“ thì PA x gọi là thoả mãn “lỏng” ràng buộc i hay ràng buộc i là lỏng đối với PA x
- Nếu một ràng buộc có dạng dấu “=“ thì nó là chặt với mọi PA
của bài toán
- Nếu một ràng buộc có dạng dấu ““ hoặc ““ thì nó có thể là
lỏng đối với PA này nhưng lại là chặt đối với PA khác
-
i = (ai1, ai2,…, ain) và tập
i (iI) tạo thành một ma trận, ký hiệu: A* và
-
i tương ứng độc
Với ràng buộc i ta ký kiệu véc tơ A* hợp các véc tơ A* gọi là ma trận hệ ràng buộc của bài toán Gọi một nhóm các ràng buộc có hệ véc tơ A* lập tuyến tính gọi là các ràng buộc độc lập tuyến tính
- Một PA thoả mãn chặt n ràng buộc độc lập tuyến tính gọi là
PA cực biên (PACB)
+ PACB thoả mãn đúng n ràng buộc gọi là PACB không suy
biến
+ PACB thoả mãn hơn n ràng buộc gọi là PACB suy biến - Một bài toán có tất cả các PACB đều không suy biến gọi là bài
toán không suy biến
- Một bài toán có ít nhất một PACB suy biến gọi là bài toán suy
biến
Ví dụ 1
f x (
)
2
x
M in
x 2
1
x
2
x
6 (1)
1
x
2
3
x
(2 )
1
2
x
0
(3)
1
0
x
(4 )
2
3. Các dạng đặc biệt
3.1. Bài toán dạng chính tắc -
Min Max (
f x ( )
c x j
j
Xác định véc tơ x = (x1, x2, …, xn) sao cho: n )
j
1
n
1
m
)
(1)
a x ij
j
b i ( i
j 1 x
0(
j
1
n
)
(2)
j
-
+
+
Bài toán dạng chính tắc có một hệ phương trình ràng buộc và các biến số đều không âm (1) là nhóm các ràng buộc dạng phương trình gọi là các phương trình ràng buộc (2) là nhóm các ràng buộc dạng bất phương trình gọi là các ràng buộc về dấu đối với các biến
- Ký hiệu:
A = ((aij))mn gọi là ma trận điều kiện của bài toán Aj là véc tơ cột j của ma trận A- gọi là véc tơ điều kiện j c là véc tơ hệ số của các biến trong hàm mục tiêu b là véc tơ vế phải của hệ phương trình ràng buộc - Khi đó bài toán dạng chính tắc có thể viết dưới dạng
n
f x ( )
(
f x ( )
c x Min Max ( , ) )
(
c x Min Max ) j
j
j
1
n
hoặc
x A b j j
Ax b x 0
0(
j
n 1 )
1 j x j
Mệnh đề - Mọi bài toán QHTT đều có thể quy về bài toán dạng chính tắc
tương đương theo nghĩa trị tối ưu của hai bài toán là như nhau và từ PATƯ của bài toán này có thể suy ra PATƯ của bài toán kia. Các phép biến đổi tương đương như sau:
’ = - xj 0
x
x
x
j
' j
'' j
- + Nếu xj 0 thì đặt: xj + Nếu xj không có ràng buộc về dấu thì đặt:
0
' x x , j
'' j
n
n
a x ij
j
p x i
b i
+ Nếu ràng buộc i có dạng thì biến đổi:
j
1
a x ij
j
b i
j
1
0
p x i n
n
a x ij
j
p x i
b i
+ Nếu ràng buộc i có dạng thì biến đổi:
j
1
j
b i
a x ij
j
1
0
p x i
Ví dụ 2
- Cho bài toán QHTT:
f x (
)
2
x
x
3
x
M in
1
3
2 x
2
x
x
6
(1)
2
1
3
4
x
x
x
1 0 ( 2 )
2
1
3
x
x
4
(3)
2
3
( 4 )
0
x
1
(5)
0
x
2
- Đưa bài toán về dạng chính tắc tương đương
Định lý 1
- PA x của bài toán dạng chính tắc là PACB khi và chỉ khi hệ thống các véc tơ {Aj: xj > 0} là độc lập tuyến tính
- Ví dụ 3: Cho bài toán QHTT
f x (
)
2
x
4
x
6
x
M in
1
2
3
3
x
4
x
4
x
1 0
(1)
1
2
3
x
x
4
x
1
( 2 )
2 1
3 3)
0 (
j
1
x
j
Chứng tỏ véc tơ x0 = (2, 1, 0) là PACB bằng hai cách
Nhận xét - Với bài toán dạng chính tắc, không làm mất tính chất tổng quát ta giả thiết hệ phương trình ràng buộc gồm m phương trình độc lập và m < n, tức là r(A) = m < n
- Bởi vì: + Nếu m = n thì hệ phương trình ràng trở thành hệ Cramer, hệ
này có tối đa một nghiệm nên việc tìm PATƯ trở thành không cần thiết
+ Nếu m > n thì bằng phép biến đổi tương đương ta có thể đưa về hệ chỉ có n phương trình và hệ này cũng là hệ Cramer
- Từ định lý 1 ta thấy: + Một PACB có tối đa m thành phần dương (?) + Một PACB không suy biến có đúng m thành phần dương (?) + Một PACB suy biến có ít hơn m thành phần dương (?)
Định nghĩa cơ sở của PACB
- -
Xét bài toán dạng chính tắc và PACB x Gọi m véc tơ {Aj} độc lập tuyến tính bao hàm hệ thống các véc tơ {Aj: xj > 0} là cơ sở của PACB x, ký hiệu một cách quy ước là J Cơ sở J của PACB x bao hàm 3 nội dung: Số phần tử của J là m
- + + Hệ véc tơ {Aj: j J} độc lập tuyến tính + -
{Aj: j J} {Aj: xj > 0} Nếu PACB x không suy biến thì có một cơ sở duy nhất:
-
-
{Aj: j J} {Aj: xj > 0} Nếu PACB x suy biến thì có thể có nhiều cơ sở khác nhau mà phần chung của chúng là các véc tơ {Aj: xj > 0} Với PACB x ta gọi: xj (j J) gọi là thành phần cơ sở của PACB x: xj > 0 j J xk(k J) gọi là thành phần phi cơ sở của PACB x: k J xk = 0
3.2. Bài toán dạng chuẩn
-
-
n
Là bài toán dạng chính tắc có bi 0 (i) và mỗi phương trình ràng buộc đều có một biến với hệ số bằng 1 và không có mặt ở các phương trình khác. Xác định véc tơ x = (x1, x2, …, xn) sao cho:
M in M a x (
f x (
)
)
c x j
j
j
1
a
x
...
x
1
m
1
1
1
x
a
m x
...
a x 1 n a
n x
b 1 b
2
2
m
m
1
1
2
n
n
2 ....................................................................
x
a
x
...
a
x
b
m
m m
1
m
1
n
m
m n
x
0 (
j
1
n
)
j
-
Bài toán dạng chuẩn cho ta PACB x0 = (b1, b2, …, bm, 0, …, 0) với cơ sở {Aj: j J} {ej: j = 1m} gọi là cơ sở đơn vị + Nếu bi > 0 (i) thì PACB x0 là PACB không suy biến + Nếu có ít nhất một bi = 0 thì PACB x0 PACB suy biến
Ví dụ 4
- Cho bài toán QHTT:
f x (
)
2
x
5
x
M a x
2
x 3 x 2
3
x
1 2
1 x
3
(1)
3
4
1
2
x
x
2
x
4
x
( 2 )
1
2
4
3 x
4
x
8
3
x
(3)
4
3 4 )
0 (
j
1
1
x
j
- Đưa bài toán về dạng chính tắc và dạng chuẩn - Xác định một PACB của bài toán và cho biết
tính chất của PACB
III. Các tính chất chung của bài toán QHTT
1. -
-
Sự tồn tại của PACB Nếu bài toán có PA và hạng của ma trận hệ ràng buộc (A*) bằng n thì bài toán có PACB. Nếu bài toán dạng chính tắc có PA thì chắc chắn có PACB (vì hạng của ma trận hệ ràng buộc luôn bằng n).
2. Tính hữu hạn của số PACB: Số PACB của mọi bài toán QHTT
đều hữu hạn. 3. Sự tồn tại PATƯ -
-
Nếu bài toán có PA và f(x) M (bị chặn dưới) với bài toán có f(x) Min và f(x) M (bị chặn trên) với bài toán có f(x) Max trên tập PA thì bài toán có PATƯ, tức là giải được. Nếu bài toán có PACB và giải được thì phải có PACB tối ưu. Do đó nếu bài toán dạng chính tắc giải được thì có PACB tối ưu. Nếu bài toán có hơn một PATƯ thì sẽ có vô số PATƯ (?)
-
IV. Phương pháp đơn hình
1. Nội dung 2. Cơ sở lý thuyết 3. Thuật toán đơn hình 4. Áp dụng thuật toán đơn hình tìm PACB
1. Nội dung - Xét bài toán không suy biến dạng chính tắc và
biết một PACB.
- Xuất phát từ PACB, tìm cách đánh giá nó, nếu chưa tối ưu thì tìm cách di chuyển sang một PACB khác tốt hơn. Vì số PACB của bài toán QHTT là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu không bị chặn trên tập PA hoặc sẽ tìm được PACB tối ưu.
n
f x ( )
Min
2. Cơ sở lý thuyết - Xét bài toán dạng chính tắc có PACB x0 và cơ sở J0: c x j
j
j
1
n
b
(1)
x A j
j
1 j x
0(
j
1
n
)
(2)
j
x0 x0
j (j J0) là thành phần cơ sở: x0 j > 0 (j J0) k (k J0) là thành phần phi cơ sở: k J0 x0
k = 0
- Với PACB x0, ta có:
b
(*)
0 x A j j
0 x A j j
0 x A k k
0 x A j j
n 1 j
j J 0
k J 0
j J 0
)
-
Ta có:
A k
x A k J ( jk
j
0
j J 0
- Ký hiệu:
J
)
k
c x j
jk
c k ( k
0
j J
0
- Với x là PA bất kỳ của bài toán, ta có:
b
x A j
j
x A j
j
x A k k
j J
n j 1
k J
0
0
b
(
)
x A j
j
j
x k
x A jk
j J
j J
k J
0
0
0
b
A
x A j
j
j
x x k jk
j J
j J
k J
0
0
0
b
(
x
)
A
(**)
j
j
x x k jk
j J
k J
0
0
Định lý 2: Dấu hiệu tối ưu
- Nếu đối với PACB x0 có cơ sở J0 của bài toán dạng
k
J
)
chính tắc mà
0
k 0(
k
J
)
thì x0 là PATƯ 0( thì x0 là PATƯ duy nhất
k
0
0(
J
k
)
0
+ Nếu + Đối với PACB x0, cơ sở J0 thoả mãn định lý 2 mà tồn tại thì x0 có thể không phải là k PATƯ duy nhất.
Chứng minh
x
x
x
x
x
x
(
j
J
)
- Từ (*) và (**), ta có x
x j
0 j
k
jk
0
k
jk
0 j
j
k J
k J
0
0
f x ( )
c x j
j
c x j
j
c x k k
j J
k J
n 1 j
0
0
x
c
x
f x ( )
(
x
)
0 j
j
k
jk
c x k k
j J
k J
k J
0
0
0
c
x
f x ( )
x
c x j
0 j
j
k
jk
c x k k
j J
j J
k J
k J
0
0
0
0
f x ( )
c x j
0 j
c x j
jk
c x ) k k
j J
0
( k J j J 0
0
0
f
x ( )
f x (
)
x
k
k
k J
0
- Như vậy:
0
k
0(
J
)
0
f x ( )
f x (
)
0
k
k
x k
k J
0
- Bài toán chính tắc có thể quy về bài toán dạng chuẩn:
0
f x ( )
f x (
)
Min
x k
k
k J
0
x
x
(
j
J
)
x k
jk
0 j
0
k J
0
x
0(
j
1
n )
j
x j
- Định lý 3: Dấu hiệu bài toán không giải được
Nếu đối với PACB x0, cơ sở J0 của bài toán dạng chính tắc mà k > 0 (kJ0) mà xjk 0 (jJ0) thì bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA.
- Định lý 4: Dấu hiệu cải tiến PA
Nếu với mỗi k > 0 (kJ0) đều có ít nhất một xjk > 0 (jJ0) thì ta có thể chuyển sang một PACB mới, ký hiệu: x1 tốt hơn x0, tức là f(x1) < f(x0).
k
)
Chứng minh + Với PACB x0, cơ sở J0 mà thì theo dấu hiệu tối ưu x0 J 0( k
0
chưa phải là PATƯ
k: j =1m) và gọi là
+ Với mỗi chỉ số kJ0 xác định một véc tơ Zk = {zj
phương Zk theo công thức:
x
J
)
(
j
0
jk j
0(
&
Z
k
J
)
j
k j
0
&
k
J
)
j
j
0
1( + Xuất phát từ PACB x0 di chuyển theo phương Zk với bước di chuyển
> 0 ta có véc tơ x() = x0 + Zk f(x()) = f(x0) - k
+ Ảnh hưởng của phương Zk đến giá trị hàm mục tiêu được đánh giá
thông qua k như sau:
+> Nếu k < 0 thì f(x()) > f(x0) Zk gọi là phương tăng +> Nếu k = 0 thì f(x()) = f(x0) thì Zk gọi là phương không đổi +> Nếu k > 0 thì f(x()) < f(x0) Zk gọi là phương giảm
+> Nếu k > 0 (kJ0) và xjk 0 (jJ0) thì Zk gọi là
phương giảm vô hạn của hàm mục tiêu.
+>Nếu với mỗi k > 0 (kJ0) đều xjk > 0 (jJ0) thì Zk gọi
là phương giảm hữu hạn của hàm mục tiêu.
x
0 j
,
x
0
0
0
jk
+ Xét Zk là phương giảm hữu hạn: +> Với các xjk > 0 ta xác định
Min j J
0
x
jk
+> Với bước di chuyển 0 ta xác định PA x1:
x1 = x(0) = x0 + 0k và f(x1) = f(x0) - 0k < f(x0)
+ PA x1 là PACB mới tốt hơn PACB x0
3. Thuật toán đơn hình
- Áp dụng cho bài toán dạng chính tắc đã biết PACB x0, cơ sở J0 ={1,2,…,m}, tức là cơ sở bao gồm m véc tơ {A1, A2,…,Am}.
- Thuật toán bao gồm 5 bước như sau: + Bước 1: Lập bảng đơn hình ứng với PACB x0, cơ sở J0 là bảng ghi các hệ số phân tích của véc tơ b và các véc tơ điều kiện qua cơ sở J0 theo mẫu sau:
Bảng đơn hình
… Cr … Cm Cm+1 … Ck … Cs … Cn
Hệ số
Cơ sở
PACB C1 C 2 x2 … xr … xm
x1
xm+1 … xk … xs … xn
x0
1
0 … 0 … 0
C1
x1
1
x0
1 … 0 … 0
0
C2
x2
2
… …
x1m+1 … x1k … x1s … x1 n x2m+1 … x2k … x2s … x2 n … … … … … … … … … … … … … …
x0
0
0 … 1 … 0
Cr
xr
r
xrm+1 … xrk … [xrs] … xrn
… …
… … … … … … … … … … … … … …
x0
0 … 0 … 1
0
Cm
xm
m
f(x)
f(x0)
0 … 0 … 0
0
xmm+1 … xmk … xms … xm n m+1 … k … s … n
+ Bước 2: Kiểm tra dấu hiệu tối ưu +> Nếu k 0 (kJ0) thì PACB x0 là PACB tối ưu -> Nếu k < 0 (kJ0) thì PACB x0 là PACB tối ưu duy nhất -> Nếu k = 0 (kJ0) thì PACB x0 có thể là PACB không duy nhất +> Nếu k > 0 (kJ0) thì chuyển sang bước 3 + Bước 3: Kiểm tra tính không giải được của bài toán +> Nếu k > 0 (kJ0) mà xjk 0 (jJ0) thì bài toán không giải được
vì trị số hàm mục tiêu giảm vô hạn trên tập PA
+> Nếu với mỗi k > 0 (kJ0) đều có ít nhất một xjk > 0 (jJ0) thì
chuyển sang bước 4
+ Bước 4: Chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi cơ
k
s
x
0 j
sở Max +> Giả sử: 0k +> Xác định:
0 r
0
J
x
x
r
(
,
,
0)
0
rs
js
0
Min j J
0
khi đó ta đưa véc tơ As vào cơ sở x x
x
rs
js
khi đó loại véc tơ Ar ra khỏi cơ sở
+ Bước 5: Biến đổi bảng đơn hình +> Trong cột cơ sở thay xr bằng xs và trong cột hệ số thay cr bằng cs; dòng r gọi là dòng xoay, cột s gọi là cột xoay, phần tử [xrs] gọi là phần tử trục xoay.
+> Chia lần lượt các phần tử nằm trên dòng xoay cho phần tử trục
xoay ta thu được một dòng tương ứng ở bảng đơn hình mới gọi là dòng chuẩn.
+> Tìm trên dòng cần biến đổi còn lại phần tử thuộc cột xoay, đổi dấu
nó, rồi đem nhân với dòng chuẩn, sau đó cộng với chính dòng đó ở bảng đơn hình cũ ta thu đợc một dòng mới tương ứng ở bảng đơn hình mới.
+> Dòng ước lượng cũng được biến đổi như một dòng bình thường
+
hoặc xác định lại theo công thức đã có. Sau bước 5 quay trở lại bước bước 2 và tiếp tục thuật toán với PACB mới x1, cơ sở J1. Sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA hoặc sẽ tìm được được PACB tối ưu.
Chú ý
- Khi 0 = 0 ta vẫn thực hiện thuật toán một cách bình
thường, khi đó kết quả của việc biến đổi sẽ cho ta chuyển sang một cơ sở khác của cùng một PACB suy biến.
- Tại bước 4, nếu khi chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi có sở mà có nhiều véc tơ thuộc diện lựa chọn thì ta chọn ngẫu nhiên một trong các véc tơ đó.
- Với bài toán có g(x) Max ta đưa về bài toán có f(x) Min bằng cách đổi dấu toàn bộ các hệ số trong hàm mục tiêu. Sau đó áp dụng thuật toán một cách bình thường, tuy nhiên: gmax = - fmin.
Ví dụ 5
- Cho bài toán QHTT:
f
(
x
)
2
x
3
x
x
x
M in
1
2
3
4
x
x
x
x
1 8
(1)
1
2
3
4
1 2 1 2 8
x
4
x
x
8
( 2 )
2
3
4
x
2
x
2
3
x
2 0
(3 )
4
2 0 (
j
3 1
x
4 )
j
- Giải bài toán sau bằng phương pháp đơn hình
Ví dụ 6
- Cho bài toán QHTT:
f x ( )
4
x
3
Min
2
x 3
2
x
16
2
(1)
x 1 x 1
2
4
28
2
(2)
2
12
x
(3)
x 1 x 1
x
0(
j
x 3 x 3 x 2 3 1 3)
j
- Giải bài toán sau bằng phương pháp đơn hình
Ví dụ 7
- Cho bài toán QHTT:
f
(
x
)
2
x
3
x
5
x
M i n
2
3
1 x
4
x
2
x
1 2
(1)
1
2
3
2
x
x
x
8
( 2 )
1
2
3
2
x
x
x
2 0
( 3 )
1
2
3
x
0 (
1
3 )
1 2 3 2 j
j
- Giải bài toán sau bằng phương pháp đơn hình
4. Áp dụng thuật toán đơn hình tìm PACB
- Nội dung: Áp dụng cho bài toán dạng chính tắc chưa biết thông tin về PACB. Để áp dụng thuật toán đơn hình cần tìm một PACB và cơ sở tương ứng của nó.
n
f x ( )
Min
- Xét bài toán dạng chính tắc có bi 0 (i): c x j
j
j
1
n
1
m
)
(1)
a x ij
j
b i ( i
I ( )
1 j x
0(
j
1
n
)
(2)
j
- Từ bài toán này xây dựng bài toán phụ (P):
m
g
P x x ( ,
)
x
Min
g i
i
1
1
m
)
x
a x ij
j
g i
b i ( i
j
1
n
n 1 j x
0 (
)
j
i
1
m
x
0 (
)
g i
g là các biến giả
Trong đó: xi
Nhận xét - Véc tơ x là PA, PACB của bài toán (I) khi và chỉ khi (x, xg = 0) là PA, PACB của bài toán (P). - Bài toán (P) là bài toán chuẩn và P(x, xg) 0 nên
luôn giải được.
và
x x ( ,
)g
- Ký hiệu PACB tối ưu của bài toán (P) là x x ( ,
)g
trị tối ưu Pmin = P
m
0
0
0
- Có hai trường hợp xảy ra: +
bài toán (I) không có
g x i
1
i
m
0
0(
)
i
x
+
là PACB của bài
g x i
g x i
g x P min i PA, tức là không giải.
i
1
P 0 min toán (I)
- Ta cần tìm cơ sở của PACB của bài toán (I): + Nếu trong cơ sở của PACB tối ưu của bài toán (P) không có các véc tơ tương ứng với các biến giả thì đó cũng là cơ sở của PACB của bài toán (I).
+ Nếu trong cơ sở của PACB tối ưu của bài toán (P) có ít
nhất một véc tơ tương ứng với các biến giả thì ta loại các cột ứng với các k(P) < 0 và tính lại dòng ước lượng k theo hàm f(x) và tiếp tục thuật toán.
- Chú ý: + khi xây dựng bài toán (P) chỉ cần cộng biến giả vào những phương trình cần thiết sao cho bài toán (P) trở thành bài toán chuẩn.
+ Một biến giả đã bị loại ra khỏi cơ sở thì không cần tính ở
các bước tiếp sau.
Thuật toán đơn hình mở rộng - Bước 1: Đưa bài toán QHTT về dạng chính tắc có vế phải không âm + Nếu bài toán dạng chuẩn thì áp dụng thuật toán để giải + Nếu bài toán chưa phải dạng chuẩn thì chuyển sang bước 2 - Bước 2: Xây dựng bài toán phụ (P) tương ứng - Bước 3: Giải bài toán (P) bằng phương pháp đơn hình + Nếu Pmin > 0 thì kết luận bài toán gốc không có PA + Nếu Pmin = 0 thì chuyển sang bước 4 - Bước 4: Tìm cơ sở của PACB của bài toán gốc + Nếu trong cơ sở của PACB tối ưu của bài toán (P) không có các véc tơ tương ứng với các biến giả thì đó cũng là cơ sở của PACB của bài toán (I).
+ Nếu trong cơ sở của PACB tối ưu của bài toán (P) có ít nhất một véctơ tương ứng với các biến giả thì ta loại các cột ứng với các k(P) < 0 và tính lại dòng ước lượng k theo hàm f(x) và tiếp tục thuật toán.
Ví dụ 7
- Cho bài toán QHTT:
f
(
x
)
2
x
3
x
5
x
M i n
2
3
1 x
4
x
2
x
1 2
(1)
1
2
3
2
x
x
x
8
( 2 )
1
2
3
2
x
x
x
2 0
( 3 )
1
2
3
x
0 (
1
3 )
1 2 3 2 j
j
- Giải bài toán sau bằng phương pháp đơn hình
Ví dụ 8
- Cho bài toán QHTT:
3
4
f ( x ) 3 x 4 x 2 x 2 x M in
1 x
2 x
1
2
4
2 2 x 2 8 (1)
1
2
3
4
x 5 x 2 x 2 x 3 1 ( 2 )
2
4
2 x 2 x x 1 6 3 x ( 3 )
1
3 4 )
j
- Giải bài toán sau bằng phương pháp đơn hình
x 0 ( j 1
Ví dụ 9
- Cho bài toán QHTT:
1
3
2
4
f ( x ) 2 x 4 x x 3 x M in
2
4
3
1
1 2 2 2 x x 3 x 5 0 2 x (1)
2
3
1
8 x 2 x 3 x 8 0 4 x ( 2 )
4 x
2
4
4 x 2 4 0 x 4 x ( 3 )
3 4 )
1
j
- Giải bài toán sau bằng phương pháp đơn hình
0 ( j 1 x
Sơ đồ giải bài toán QHTT
BÀI TOÁN KHÔNG CHÍNH TẮC
Bài toán chính tắc với bi không âm
Giải bằng thuật toán đơn hình
Kiểm tra Dạng chuẩn
Bài toán phụ (P)
Pmin = 0 và mọi ẩn giả đều là phi cơ sở
k 0 Xác định được PA tối ưu
Thu hẹp bài toán
Pmin = 0 và có ẩn giả trong cơ sở
k > 0 và xjjk 0 Bài toán không giải được
Giải bằng đơn hình với bài toán (P)
Pmin > 0
Bài toán chính không có PA (không giải được)
V. Bài toán đối ngẫu
1. Đặt vấn đề 2. Cách thành lập bài toán đối ngẫu 3. Phân tích quan hệ trong cặp bài toán đối ngẫu 4. Các ứng dụng
1. Đặt vấn đề
- Với mỗi bài toán QHTT, theo các quy tắc nhất định ta xây dựng một bài toán QHTT thứ hai và gọi là bài toán đối ngẫu của bài toán đã cho.
- Quan hệ giữa hai bài toán này rất chặt chẽ, nếu biết kết quả của bài toán này có thể suy ra được kết quả của bài toán kia.
2. Cách thành lập bài toán đối ngẫu
- Xét bài toán dạng chính tắc và gọi là bài toán gốc
n
f x ( )
Min Max (
)
c x j
j
j
1
n
1
m
)
(1)
a x ij
j
b i ( i
I ( )
(2)
0(
n
)
j
1 j x
j
1 - Dựa vào bài toán (I) ta xây dựng bài toán QHTT sau:
m
Max Min (
)
(cid:0) f y ( )
b y i i
i
1
m
( )
c
(
j
1
n
)
( ) I
a y ij i
j
i
1
- Bài toán ( ) gọi là bài toán đối ngẫu của bài toán (I)
I
Nhận xét (cid:0) ( f
M ax
y
)
- Nếu f(x) Min thì và hệ ràn buộc của bài toán đối ngẫu có dạng “”
M in
y
(cid:0) ( f
- Nếu f(x) Max thì và hệ ràn buộc của bài
) toán đối ngẫu có dạng “”
- Số ràng buộc không kể các ràng buộc dấu trong bài toán
này bằng số biến số trong bài toán kia
- Các hệ số trong hàm mục tiêu của bài toán này là các hệ số
ở vế phải của hệ ràng buộc trong bài toán kia
- Ma trận điều kiện trong hai bài toán là chuyển vị của nhau.
Bài toán gốc
Bài toán đối ngẫu
c
b
A
b
AT
c
Cặp ràng buộc đối ngẫu
- Gọi hai ràng buộc bất đẳng thức (kể cả rang buộc về dấu) trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu.
- Các cặp ràng buộc đối ngẫu trong hai bài toán (I)
I và ( )
m
x
0
c
(
j
1
n
)
j
a y ij
i
j
i
1
Ví dụ 10
- Cho bài toán QHTT sau:
f x (
)
5
x
2
x
7
x
M in
2
3
1
x
2
x
3
x
5
(1)
2
3
2
1 x
x
2
x
6
( 2 )
x
1
2 1
3 3)
0 (
j
j
- Viết bài toán đối ngẫu của bài toán trên và chỉ ra
các cặp ràng buộc đối ngẫu.
Hai cách viết bài toán đối ngẫu
- Cách 1: Đưa bài toán QHTT về dạng chính tắc
tương đương, sau đó viết bài toán đối ngẫu của bài toán chính tắc và qui ước gọi đó là bài đối ngẫu của bài toán ban đầu.
- Cách 2: Sử dụng lược đồ tổng quát
Lược đồ tổng quát
STT
Bài toán đối ngẫu (cid:0) ( M ax M in f ) (
y
)
Bài toán gốc M in M f x (
(
)
ax )
n
1
j
b i
yi không ràng buộc dấu
a x ij
1 i n
2
yi 0
a x ij
j
( ) b i
i
1 n
3
a x ij
j
( ) b i
yi 0
i
1
m
( )
c
4
a y ij i
j
xj 0
1 i m
5
( )
c
xj 0
a y ij i
j
1 i m
6
c
j
xj không ràng buộc dấu
a y ij i
i
1
Ví dụ 11
- Cho bài toán QHTT:
f x (
)
2
x
x
3
x
M in
1
3
2 x
2
x
x
6
(1)
2
1
3
4
x
x
x
1 0 ( 2 )
2
1
3
x
x
4
(3)
2
3
( 4 )
0
x
1
(5)
0
x
2
- Viết bài toán đối ngẫu của bài toán trên bằng 2 cách và chỉ
ra các cặp ràng buộc đối ngẫu
3. Mối quan hệ giữa hai bài toán đối ngẫu
f x (
(cid:0) f
y
(
)
3.1. Các tính chất và định lý đối ngẫu - Tính chất 1: Với mọi PA x và y của hai bài toán đối ngẫu ) M a x
(cid:0) ( có f(x) min và ta luôn có: f y )
m
m
1
n
c
(
)
j
a y ij i
j
1
i
1
n
x
)
(
j
a y ij i
c x j
j
j
1
i
1
0(
n
)
j
j
- Chứng minh: + Xét hai PA x và y bất kỳ của hai bài toán đối ngẫu. + Ta có: x
n
m
n
m n
n
(cid:0) f y ( )
f x ( )
j
a y ij i
c x j
j
a x y ij j i
c x j
j
x
i
1
j
1
j
1
i
1
j
1
j
1
- Tính chất 2: Nếu đối với hai PA x* và y* của một cặp bài
*
*
y
)
(
)
(cid:0) f
toán đối ngẫu mà thoả mãn: thì x* và y* tương f x ( ứng là hai PA tối ưu.
(cid:0) ( f
y
)
M a x
*
*
(cid:0) * f y (
f x ( )
f x (
x
)
)
là PA tối ưu
*
*
*
(cid:0) f y (
f x (
)
)
)
y
- Chứng minh: + Xét cặp bài toán f(x) Min và + Lấy một PA x bất kỳ của bài toán gốc + Theo tính chất 1, ta có: + Lấy một PA y bất kỳ của bài toán đối ngẫu (cid:0) + Theo tính chất 1, ta có: f y (
là PA tối ưu
- Định lý 1: Nếu một trong hai bài toán giải được thì bài
*
*
f x (
(cid:0) f
y
(
)
)
toán kia cũng giải được và khi đó với mọi cặp PATƯ x* và y* ta luôn có:
- Hệ quả 1: Điều kiện cần và đủ để hai bài toán đối ngẫu giải
được là mỗi bài toán có ít nhất một PA.
- Chứng minh: + Giả sử: Hai bài toán giải được, khi đó hai bài toán có PATƯ, tức là mỗi bài toán có ít nhất một PA. (đpcm)
(cid:0) 0 y f (
)
)
+ Giả sử: Mỗi bài toán có một PA x0 và y0. + Khi đó: với mỗi PA x bất (nếu có) của bài toán gốc ta có: tức là hàm mục tiêu bị chặn. Như vậy, bài f x ( toán gốc giải được và theo định lý 1 bài toán đối ngẫu cũng giải được (đpcm).
- Hệ quả 2: Điều kiện cần và đủ để một bài toán có PA còn một bài toán không có PA là trị số hàm mục tiêu của bài toán có PA không bị chặn trên tập PA của nó.
- Chứng minh: + Giả sử: bài toán gốc có PA còn bài toán đối ngẫu không có PA, tức là bài toán đối ngẫu không giải được và theo định lý 1 bài toán gốc không giải đươc vì trị số hàm mục tiêu không bị chặn trên tập PA (đpcm).
+ Giả sử: bài toán gốc có PA và trị số hàm mục tiêu không bị chặn, tức là bài toán gốc không giải được và theo định lý 1 bài toán đối ngẫu không giải được vì không có, bởi vì, nếu bài đối ngẫu có PA thì theo hệ quả 1 hai bài toán đều giải được (trái với GT) (đpcm).
Nhận xét
Với một cặp bài toán đối ngẫu chỉ xảy ra một trong ba trường hợp
- Trường hợp 1: Cả hai bài toán đều không có PA thì
hai bài toán cùng không giải được
- Trường hợp 2: Một bài toán có PA và một bài toán không có PA thì cả hai bài toán cùng không giải được
- Trường hợp 3: Cả hai bài toán đều có PA thì cả hai
bài toán cùng giải được
- Định lý 2: Điều kiện cần và đủ để hai PA x và y của một
cặp bài toán đối ngẫu tối ưu là trong các cặp ràng buộc đối ngẫu, nếu một ràng buộc thoả lỏng thì ràng buộc kia phải thoả mãn chặt.
m
m
c
c
j
j
a y ij i
a y ij i
1i
1i
- Nếu xj > 0 thì hoặc thì xj = 0 - Hệ quả: Nếu một ràng buộc là lỏng đối với PATƯ của bài toán này thì ràng buộc đối ngẫu với nó phải là chặt đối với mọi PATƯ của bài toán kia.
3.2. Các ứng dụng - Khảo sát sự tồn tại của PA và PA tối ưu: + Sử dụng các tính chất và định lý 1 ta có thể khảo sát sự tồn tại của PA, PATƯ của cặp bài toán đối ngẫu mà không cần thiết phải giải.
+ Ví dụ 12: Cho bài toán QHTT x 2
f x (
2
x
x
x
)
M in
1
2
3
4
1 5
(1)
x
x
1
2
( 2 )
x
8
x
4
3 1
4 )
x
0 (
j
j
Hãy viết bài toán đối ngẫu của bài toán trên và chứng tỏ bài toán đối ngẫu đó có PATƯ.
+ Ví dụ 13: Cho bài toán QHTT
f x (
)
2
x
2
x
p x
2
x
M a x
2
3
x 5
4
1 x
2
x
x
4
p
1
x
(1)
1
2
x
2
4 x
5 x
3 2
( 2 )
x
2
4
5
x
x
x
1 8
(3)
3 x
5
3
1 ,
x
x
2
0
3
4
Trong đó: p là tham số Hãy viết bài toán đối ngẫu của bài toán trên và dựa vào bài toán này để biện luận theo p về sự tồn tại PATƯ của bài toán gốc.
- Phân tích tính chất của véc tơ x đối với bài toán: + Sử dụng hệ quả của định lý 2 để phân tích tính chất tối ưu của một PA. Ví dụ: cần phân tích xem x có phải là PATƯ của bài toán gốc hay không.
+ Các phân tích như sau: +> Giả sử x là PATƯ của bài toán gốc thì theo định lý 2 mọi PATƯ
của bài toán đối ngẫu phải thoả mãn chặt các ràng buộc đối ngẫu với các ràng buộc mà x thoả mãn lỏng. Tập hợp các ràng buộc chặt này tạo thành một hệ phương trình đối với véc tơ y
+> Giải hệ phương trình này: -> Nếu hệ vô nghiệm thì x không phải là PATƯ -> Nếu hệ có nghiệm thì ta thử lần lượt các nghiệm này vào các ràng
buộc còn lại của bài toán đối ngẫu TH1: Nếu mọi nghiệm đều không thoả mãn thì x không phải là PATƯ TH2: Nếu có nghiệm y thoả mãn thì y là PATƯ của bài toán đối ngẫu vã cũng là PATƯ của bài toán gốc
+ Ví dụ 14: Cho bài toán QHTT (I)
f x (
)
3
x
x
p x
M in
1
2
3
2
x
2
x
x
6
1
2
3
x
2
x
2 (
I
)
2
x
2
1
x
0 (
j
3 1, 2, 3)
j
Trong đó: p là tham số
+> Hãy viết bài toán đối ngẫu của bài toán (I) và chỉ
ra các cặp ràng buộc đối ngẫu
+> Tìm P để véc tơ y = (0, ½) là PATƯ
