BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Năm 2011
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Chuyên ngành : TOÁN GIẢI TÍCH
Mã số : 60 46 01
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
TS. TRỊNH CÔNG DIỆU
Năm 2011
Mở đầu
Nhiều vấn đề của thực tế cuộc sống hoặc trong các lĩnh vực khoa học kỹ thuật, kinh tế…
dẫn đến việc giải quyết các bài toán tối ưu hóa. Trong số các mô hình tối ưu hóa thì hệ
tuyến tính liên tục là trường hợp đã có các kết quả tương đối trọn vẹn. Tình hình tương tự
cũng xảy ra đối với hệ tuyến tính rời rạc, đó là trường hợp mà tất cả hoặc một số biến chỉ
nhận giá trị nguyên. Tuy nhiên các thuật toán giải hệ tuyến tính rời rạc đều áp dụng cho các
mô hình có tập phương án bị chặn, cơ sở lý luận cho trường hợp không bị chặn chưa có kết
quả nào . Việc hoàn chỉnh cơ sở lý luận cho các thuật toán giải quy hoạch nguyên là một
việc làm cần thiết. Luận văn này sẽ góp phần làm điều đó.
Luận văn được chia làm 4 chương:
Chương 1: Cấu trúc tập ràng buộc của bài toán quy hoạch tuyến tính
Chương 2: Bài toán quy hoạch tuyến tính nguyên
Chương 3: Thuật toán cắt Gomory giải bài toán quy hoạch tuyến tính nguyên
Chương 4: Thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên.
Luận văn trình bày chi tiết một số kết quả của quy hoạch tuyến tính nguyên. Việc nghiên
cứu quy hoạch nguyên với mô hình tuyến tính bất kỳ đã có thêm một số kết quả (không có
trong các tài liệu, giáo trình về quy hoạch tuyến tính nguyên đang lưu hành) như sau:
+ Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bài
toán quy hoạch tuyến tính (không có điều kiện nguyên) tương ứng (định lý 2.4,2.5).
+ Mở rộng điều kiện sử dụng phương pháp nhánh cận (định lý 4.6), do đó cho phép
thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên có thể áp dụng cho một lớp
bài toán rộng hơn các kết quả đã có.
Trong luận văn này có thể xem các kết quả trên là đóng góp của tác giả cho việc khảo
sát bài toán quy hoạch tuyến tính nguyên.
Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến Tiến sĩ Trịnh Công Diệu, Thầy đã tận
tình hướng dẫn và tạo điều kiện thuận lợi giúp tôi hoàn thành luận văn này.
Tôi xin gởi lời cảm ơn chân thành đến quý thầy cô trường Đại học Sư phạm Tp. Hồ Chí
Minh đã nhiệt tình giảng dạy tôi trong suốt quá trình học tập.
Tôi cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ tôi trong quá
trình học tập cũng như thực hiện luận văn này.
Mục lục
Mở đầu ......................................................................................................... 3
Mục lục ........................................................................................................ 4
Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ............................................................................ 6
1.1. Tập lồi, tập affine và tập nón .................................................................................. 6
1.1.1. Tập lồi ........................................................................................................................ 6
1.1.2. Tập affine ................................................................................................................... 6
1.2. Tập lồi đa diện ........................................................................................................ 7
1.1.3. Tập nón ...................................................................................................................... 7
1.2.1. Điểm và phương cực biên của tập lồi, đóng .............................................................. 7
1.2.2. Tập lồi đa diện ........................................................................................................... 9
Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN ...... 20
2.1. Khái niệm bài toán quy hoạch tuyến tính nguyên ................................................ 20
2.2. Mối liên hệ giữa dạng chuẩn tắc và chính tắc của bài toán quy hoạch tuyến tính nguyên ......................................................................................................................... 20
2.3. Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bài toán quy hoạch tuyến tính tương ứng .......................................................................... 22
Chương 3: THUẬT TOÁN CẮT GOMORY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 25
3.1. Bảng đơn hình ...................................................................................................... 25
3.1.1. Khái niệm ................................................................................................................. 25
3.2. So sánh theo nghĩa từ vựng .................................................................................. 27
3.1.2. Phép biến đổi cơ bản của bảng đơn hình ................................................................. 26
3.2.1. Các khái niệm cơ bản ............................................................................................... 27
3.2.2. Các tính chất cơ bản ................................................................................................. 27
3.3. Bảng đơn hình l-chuẩn ......................................................................................... 29
3.4. Thuật toán đơn hình đối ngẫu từ vựng tìm phương án tối ưu từ vựng ................. 30
3.5. Thuật toán cắt Gomory ......................................................................................... 41
3.2.3. Tối ưu theo nghĩa từ vựng ........................................................................................ 28
3.5.1. Điều kiện để sử dụng thuật toán Gomory ................................................................ 41
3.5.2. Thuật toán cắt Gomory ............................................................................................ 42
3.5.3. Cơ sở lí luận của thuật toán...................................................................................... 43
3.5.4. Ví dụ ......................................................................................................................... 48
Chương 4: THUẬT TOÁN NHÁNH CẬNGIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 52
4.1. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính ....................... 52
4.2. Kỹ thuật tái tối ưu hóa .......................................................................................... 53
4.3. Thuật toán nhánh cận ........................................................................................... 54
4.3.1. Điều kiện để sử dụng thuật toán nhánh cận ............................................................. 54
4.3.2. Thuật toán nhánh cận ............................................................................................... 54
4.3.3. Cơ sở lí luận của thuật toán...................................................................................... 56
4.3.4. Ví dụ ......................................................................................................................... 61
Kết luận ..................................................................................................... 65
Tài liệu tham khảo .................................................................................... 66
Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.1. Tập lồi, tập affine và tập nón
n
∈
+ − (1
λ λ y :
)
1.1.1. Tập lồi
x y ∈ được gọi là đoạn thẳng nối x và y và ,
[
} ] 0;1
Tập hợp với + Đoạn thẳng: { λ x
] ;x y .
=
x y ;
y x ;
được ký hiệu là [
]
]
. Nhận xét: [ [
n
A ⊂ được gọi là tập lồi nếu
∈ ⇒
x y A ,
x y ;
∈ . A
[
]
+ Tập lồi:
,
n∅ là các tập lồi.
Ví dụ:
+ Bao lồi:
Giao của tất cả các tập lồi chứa A được gọi là bao lồi của A . Kí hiệu bao lồi
của A là convA .
Nhận xét:
k
=
≥ ∀ =
,
,...,
+ + ...
:
0
i
1,
k
- Bao lồi của A là tập lồi nhỏ nhất (theo nghĩa bao hàm) chứa A .
}
{ conv x x 2
1
x 2 2
x 1 1
x k
λ k
x k
= λ λ 1, i
i
∑
= 1
i
+ λ λ
-
1.1.2. Tập affine
n
λ x
+ − (1
λ λ y :
)
+ Đường thẳng:
} ∈ với
x y ∈ được gọi là đường thẳng đi qua x và y . ,
Tập hợp {
n
,x y A∈ thì đường thẳng đi qua
,x y cũng nằm
+ Tập affine:
A ⊂ gọi là tập affine nếu
-
trong A .
Định lý 1.1: [4, tr.7-8]
=
∃ ∈
= −
L
y
:
x A y
,
{
} x a
Nếu A là tập affine và a A∈ thì tập là không gian con
n đồng thời L là duy nhất đối với A và không phụ thuộc vào a . Ta cũng
của
= + .
viết A a L
- Số chiều của tập affine:
Số chiều của tập affine A là số chiều của không gian con L gắn với A , tức
= + .Kí hiệu số chiều của A là dim A .
là A a L
- Bao affine:
Giao của tất cả các tập affine chứa A được gọi là bao affine của A . Kí hiệu bao affine
của A là affA .
Nhận xét:
Bao affine của A là tập affine nhỏ nhất (theo nghĩa bao hàm) chứa A .
n
+ Số chiều của một tập bất kỳ:
A ⊂ là số chiều của bao affine của A .
Số chiều của tập
1.1.3. Tập nón
n
A ⊂ được gọi là là tập nón nếu
λ
x A
0
∈ ⇒ ∈ ∀ > . x Aλ ,
+ Tập nón:
n
+ λ λ
≥ ∀ ∈
+ + ...
:
0,
i
1,
k
+ Tập nón hữu hạn sinh:
x 1 1
x 2 2
λ λ x k i
k
ix ∈ được gọi là nón sinh bởi
}
,...,
,
,...,
với - Tập hợp {
{
}
}
, x x 1 2
x k
{ cone x x 2
1
x k
+ λ λ
λ ≥ ∀ ∈ 0,
i
1,
k
+ + ...
, ký hiệu là .
i
λ k
x k
x 1 1
x 2 2
,...,
- Tổ hợp tuyến tính với được gọi là tổ hợp nón
x x , 1 2
x . k
của
Nhận xét:
Tập nón hữu hạn sinh là một tập nón và cũng là tập lồi.
1.2. Tập lồi đa diện
1.2.1. Điểm và phương cực biên của tập lồi, đóng
Cho A là tập lồi và đóng.
1.2.1.1. Điểm cực biên của tập lồi, đóng
∈ y z A y ,
,
z
≠ sao cho
∈
λ∈
=
x
y z ;
∈ y z A y ,
,
x
λ y
+ − (1
λ )
z
+ x A∈ được gọi là điểm cực biên của A nếu không tồn tại
≠ và z
} y z ,
(
)0;1
[
] { \
,tức là không tồn tại sao cho .
+ Tập hợp các điểm cực biên của A được kí hiệu là extA .
n
+ ∈ ∀ ∈
λ
λ
x
u A x A , ,
u ≠ và 0
> . 0
u ∈ được gọi là phương vô tận của A nếu
1.2.1.2. Phương vô tận của tập lồi, đóng
Nhận xét:
0λ> . Như
Nếu u là phương vô tận của thì uλ cũng là phương vô tận của A với mọi
vậy tập hợp các phương vô tận của A là tập nón. Vì thế ta thường gọi tập các phương vô tận
của A là nón các phương vô tận của A .
Định lý 1.2:
Một tập lồi đóng và không bị chặn thì có phương vô tận.
n
Chứng minh:
A ⊂ là tập lồi đóng và không bị chặn. Vì A không bị chặn nên tồn tại dãy
=
b k
A⊂ sao cho lim k a
= +∞ . Xét dãy { }kb xác định bởi
Xét
{ }ka
→∞
k
a k a k
n
∈
=
:
x
x
. Dãy { }kb nằm trong tập
} 1
u
= . Ta chứng minh u là phương vô tận của A.
nên chứa dãy con hội tụ. Không giảm tổng quát, ta có thể compact {
→∞
k
≠
=
k
1,
u
0
u
xem lim k b
= và u
= ∀ .
(
) 1
kb
→∞
k
<
= +∞ nên với k đủ lớn ta có 0
< . 1
Đầu tiên, ta thấy do lim k b
0λ> cho trước. Do lim k a
→∞
k
λ ka
Xét x A∈ và
−
+
∈
1
x
A
Do A lồi nên ta có
a k
λ a k
λ a k
−
+
x
= + x
λ u
.
u Aλ+ ∈ .
a k
→∞
k
λ a k
λ a k
Mặt khác, ta có lim 1
và do A đóng nên x
Vậy u là phương vô tận của A.
n
1.2.2.2. Phương cực biên của tập lồi, đóng
u ∈ được gọi là phương cực biên của A nếu u là phương vô tận của A và không
=
,
+ wα β
v
+
,v w của A và
0α β> sao cho u
tồn tại 2 phương vô tận độc lập tuyến tính .
Nhận xét:
0λ> nên ta
Vì nếu u là phương vô tận của A thì uλ cũng là phương vô tận của A với
n
có thể định nghĩa phương cực biên của tập lồi, đóng như sau:
u ∈ được gọi là phương cực biên của A nếu u là phương vô tận của A và không
+
,v w của A sao cho u
= + . v w
tồn tại 2 phương vô tận độc lập tuyến tính
1.2.2. Tập lồi đa diện
1.2.2.1. Khái niệm tập lồi đa diện
n :
n
+ Tích vô hướng trong
x y ∈ là số thực ,
=
+
x y ,
+ + ...
Tích vô hướng của 2 véc tơ
x y n
n
x y 1 1
x y 2
2
=
=
x
,...,
,
y
,...,
y
,
(
)
(
)
x x , 1 2
x n
y y , 1
2
n
với .
n
∈
=
a
b≠ 0,
x
:
a x ,
(
)
∈ được gọi là siêu phẳng
+ Siêu phẳng:
} b
Tập hợp có thể quy về dạng{
n .
trong
Nhận xét:
Siêu phẳng là một tập affine.
n
∈
≤
a
b≠ 0,
x
:
a x ,
(
)
∈ được gọi là nửa không
+ Nửa không gian đóng :
} b
Tập hợp có thể quy về dạng {
n .
gian đóng trong
Nhận xét:
Nửa không gian đóng là một tập lồi và đóng.
n
D ⊂ được gọi là tập lồi đa diện nếu D là giao của hữu hạn các nửa không gian
+ Tập lồi đa diện:
đóng.
Nhận xét:
m
n
D
H
Tập lồi đa diện là một tập lồi và đóng.
D ⊂ là tập lồi đa diện.
iH là các nửa không gian đóng.
i
= trong đó
= 1
i
Cho
Biểu diễn
b 1
n
=
≤
b
A
,...,
H
:
(
)
a i
a a , 1 i i
2
a in
i
a x , i
b i
{ = ∈ x
}
a a 11 1 n a a m 1 mn
b m
=
=
; ; , .
n
D
:
≤ ∀ = ,
i
1,
( )∗
a x , i
b i
{ = ∈ x
} m
Khi ấy, ta có thể biểu diễn tập lồi đa diện D dưới dạng
D
:n
hoặc
(
)∗∗
{ = ∈ x
} ≤ Ax b
.
Chú ý:
Trong chương này kể từ về sau khi đề cập đến tập lồi đa diện D thì ta hiểu D được
)∗∗ .
cho dưới dạng ( )∗ hoặc (
Như nhận xét trên, tập lồi đa diện là một tập lồi đóng. Do đó tập lồi đa diện cũng có các
khái niệm điểm cực biên, phương vô tận và phương cực biên. Phần tiếp theo ta sẽ nghiên
cứu các khái niệm ấy của tập lồi đa diện
1.2.2.3. Điểm cực biên của tập lồi đa diện
Bổ đề 1.3:
Cho D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Khi ấy, nếu x thuộc
D và x không phải là điểm cực biên thì tồn tại y thuộc D thỏa
a x ,i
b= thì i
a y ,i
b= . i
i
m∈ 1,
+ Nếu
a x ,i
b< và i
a y ,i
b= . i
sao cho + Tồn tại
λ∈
=
extD∉
∈ y z D y ,
,
x
λ y
+ − (1
λ )
z
Chứng minh:
≠ và z
(
)0;1
nên tồn tại sao cho . + Vì x
b= thì ta có
a x ,i
i
=
=
( ≥ − − 1
) λ
( − − 1
) λ
≥ λ λ b i
a y , i
a x , i
a z , i
b i
b i
λ b i
Vậy nếu
a y ,i
b= . i
Suy ra
=
=
a y , i
a z , i
a x , i
= . b i
Tương tự đối với z . Vậy ta có
i
m∈ 1,
b< . Giả sử ngược lại,
a x ,i
i
i
m∈ 1,
b= với mọi
+ Trước hết ta chứng tỏ tồn tại sao cho
a x ,i
i
=
=
i
m
= ∀ = ,
1,
. Theo như chứng minh phần trên, ta có
a y , i
a z , i
a x , i
b i
.
0λ> , ta có
=
λ
,
λ y
z
= ∀ = ,
i
1,
m
Vậy với mọi
( + − 1
) λ
( + − 1
) λ
a i
a y , i
a z , i
b i
.
i
m∈ 1,
Suy ra D chứa đường thẳng qua y,z . Điều này mâu thuẫn với giả thiết D không chứa
a x ,i
b< . i
đường thẳng. Vậy tồn tại sao cho
];y z không thể kéo dài mãi về 2
Do D không chứa đường thẳng nên đoạn thẳng [
phía (mà vẫn còn nằm trong D ). Không mất tính tổng quát ta xem đường thẳng qua y,z
i
m∈ 1,
thoát ra khỏi D tại y.
b< thì ta cũng có
b< . Không mất tính tổng
a x ,i
i
a y ,i
i
Giả sử với mọi nếu
=
i
k
= ∀ = ,
1,
quát ta giả sử
a y , i
a x , i
b i
<
,
,
< ∀ = + i
k
,
1,
m
,
a y , i
b a x i i
b i
−
= + y
x
0
.
t > , ta đặt
( t y
)
ty
i
∈ + k
1,
m
Với mỗi .
b′ < sao cho
b′< .
a y ,i
i
b i
i
0
, chọn Với mỗi
t > đủ nhỏ, ta có
=
+
−
−
x
x
< ∀ = + i
k
,
1,
m
Khi ấy, với
a y , i t
a y , i
t a y , i
′ < + b i
t a y , i
b i
=
= ∀ = ,
i
1,
k
= ∀ = ,
i
1,
k
.
a y , i
a x , i
b i
a y , i t
b i
0
Mặt khác, do .
t > đủ nhỏ. Như vậy đoạn thẳng [
];y z có thể kéo dài về phía y
ty D∈ với
Vậy nên
ty sao cho nó vẫn còn nằm trong D . Điều này mâu thuẫn với giả sử đường thẳng qua y,z
tới
thoát ra khỏi D tại y.
Định lý 1.4:
Tập lồi đa diện khác rỗng nếu không chứa đường thẳng thì có điểm cực biên.
Chứng minh:
extD∈
extD∉
Xét D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Chọn x D∈ bất kỳ.
i
m∈ 1,
, ta có điều phải chứng minh.Ngược lại, giả sử x . Theo bổ đề 1.3 có Nếu x
1x D∈ sao cho tồn tại
thoả mãn
a x ,i
b< và i
a x 1,i
b= . i
n
=
=
H
:
.
x H∉ . Đặt i
D H D i
1
i
a x , i
b i
{ = ∈ x
}
<
=
dim
dim
D
dim
dim
D
Đặt . Ta có
D⊂ nên
D 1
D 1
1D
=
⊂
=
affD affD⊂
dim
dim
D
affD affD=
affD affH H
.
. Thậy vậy, giả sử . Vì Ta chứng minh
1
D 1
1
D 1
H⊂ nên i
1
i
i
∈ ⊂
affD H⊂
. Lại có nên . Vì Suy
x H∉ .
.i
i
extD∉
extD extD⊂
x
ra Điều này mâu thuẫn vì x D affD nhưng
1
extD∈ 1
λ∈
=
x D H D
∈ y z D y ,
,
z
x
λ y
+ − (1
λ )
z
≠ và
Ta chứng minh . Xét . Giả sử x . Khi ấy tồn tại
b= . Do
(
)0;1
nên
a x ,i
i
∈ = 1
i
=
λ∈
=
y z D H ,
x
λ y
+ − (1
λ )
z
sao cho . Vì
= . Suy ra
(
)0;1
∈ nghĩa là
a y , i
a z , i
b i
i
λ∈
=
∈ y z D y ,
,
z
x
λ y
+ − (1
λ )
z
,y z D∈ . Vậy tồn tại
≠ và
với nên ta cũng có
(
)0;1
1
1
x
extD extD⊂
sao cho . Điều này mâu
extD∈ 1
1
. Do đó . thuẫn với giả thiết
1x là điểm cực biên của
1D thì
1x cũng là điểm cực biên của D. Ta có điều
Vậy nếu
1x không phải là điểm cực biên của
1D thì ta lập luận như
phải chứng minh. Ngược lại nếu
dim D vì 1
1D cũng là tập lồi đa diện khác rỗng và không chứa đường
trên và giảm được
kx là điểm cực biên của
⊂ ⊂ ...
⊂ extD extD
thẳng. Quá trình lập luận này phải dừng lại ở một bước k nào đó mà
kD . Do
extD k
1
kx là điểm cực biên của D.
nên
Định lý 1.5:
=
,...,
a
,
1,
b
∀ = i
n
Cho tập lồi đa diện D khác rỗng . Nếu x là điểm cực biên của D thì tồn tại hệ gồm n
}
a a , 1 2
a ,..., m
}
a a , j 1
j 2
j n
, a x j i
j i
sao cho . lấy từ hệ { vectơ độc lập tuyến tính {
,...,
a
Chứng minh:
n< vectơ độc lập tuyến tính {
}
a a , j 1
j 2
j k
=
,
1,
b
∀ = i
k
Giả sử ngược lại có tối đa k lấy từ hệ
{
}
, a a 1 2
,..., m a
, a x j i
j i
=
⊥ = − L n
dim
L n k
1
L
,...,
a
h L h⊥∈
,
0
sao cho .
= − ≥ nên tồn tại
≠ . Vậy
j k
a a , j 1
j 2
=
ε± h
ε± h
. Vì dim Đặt
0ε> đủ nhỏ, ta có
≤ nếu
L∈ và
< nếu
L∉ . Như
a x , i
a x , i
b i
a x ,i
b i
ia
ia
+
=
+
+
−
ε h
≠ − x
ε h
0
x
x
ε h
x
ε h
với
h Dε± ∈ và x
h ≠ . Mặt khác, ta có
(
)
(
)
1 2
1 2
vậy x do . Điều
này mâu thuẫn với x là điểm cực biên.
Số cách chọn n vectơ từ m vectơ là hữu hạn. Do đó ta có hệ quả sau
Hệ quả 1.6:
Tập hợp các điểm cực biên của tập lồi đa diện có hữu hạn phần tử.
1.2.2.4. Phương vô tận của tập lồi đa diện
Định lý 1.7:
0
u ≠ và 0
Au ≤ .
Cho tập lồi đa diện D khác rỗng. Khi ấy u là phương vô tận của D nếu và chỉ nếu
+
0
A x (
bλ )
0
u
,
Chứng minh:
u ≠ và với x D∈ , ta có
λ ≤ ∀ > .
+
λ
0
,
u
0
,
≤ ∀ > . Nếu
> . Như
Nếu u là phương vô tận của D thì
ia u > thì với λ đủ lớn, ta có
a x , i
bλ i
a x ,i
bλ+ u i
≤ ∀ =
0
i
m
0,
1,
Nghĩa là
Au ≤ .
ia u ,
+
=
+
λ
λ
0
A x (
λ u
)
Ax
Au b
0
,
u ≠ và 0
Au ≤ thì với x D∈ , ta có
≤ ∀ > do
hay vậy, ta phải có
≤
λ
≤ Ax b Au
,
0,
0
> . Vậy u là phương vô tận của D.
Nếu
1.2.2.5. Phương cực biên của tập lồi đa diện
Định lý 1.8:
1n −
= ∀ =
,...,
0,
i
1,
n
Cho tập lồi đa diện D khác rỗng. Nếu u là phương cực biên của D thì tồn tại hệ
− . 1
}
, a a 1 2
,..., m a
a −
}
j n
a a , j 1
j 2
1
ija u ,
sao cho lấy từ hệ { vectơ độc lập tuyến tính {
k
1
,...,
a
Chứng minh:
n< − vectơ độc lập tuyến tính {
}
a a , j 1
j 2
j k
= ∀ =
0,
i
1,
k
Giả sử ngược lại có tối đa lấy từ hệ
{
}
a a , 1 2
a ,..., m
ija u ,
=
,
,
L
a
,...,
sao cho .
L∈ và
L∉ .
ia u < nếu 0
ia u = nếu 0
ia
ia
a a , j 1
j 2
j k
⊥ = − L n
dim
L n k
2
. Ta có u L⊥∈ ; Đặt
= − ≥ nên tồn tại h L⊥∈ độc lập tuyến tính với u. Vậy với
hε+
0
hε+
0
0ε> đủ nhỏ, ta có
= nếu
L∈ và
< nếu
L∉ .Do vậy theo định
ia u ,
ia u ,
ia
ia
hε±
Vì dim
lý 1.4, hai vectơ u là các phương vô tận và là các phương vô tận độc lập tuyến tính do 2
=
+
+
−
u
u
ε h
u
ε h
vectơ u,h độc lập tuyến tính.
(
)
(
)
1 2
1 2
Mặt khác, ta có . Điều này mâu thuẫn với u là phương cực
biên.
Hệ quả 1.9:
Tập hợp các phương cực biên của tập lồi đa diện ( không kể các phương cực biên
cùng phương) có hữu hạn phần tử.
1.2.2.6. Cấu trúc của tập lồi đa diện không chứa đường thẳng
Định lý 1.10:
Tập lồi đa diện bị chặn chính là bao lồi của các điểm cực biên của nó.
=
D conv extD
Chứng minh:
(
)
⊂
D conv extD
Xét D tập lồi đa diện bị chặn. Ta sẽ chứng minh .
D⊂ . Ta chứng minh
( conv extD
)
(
)
=
n
dim
D
Vì D là tập lồi chứa extD nên ( )*
( )* đúng với
0n = vì khi ấy D có một phần tử duy nhất. Giả sử ( )* đúng với mọi
n
extD∈
k= . Thật vậy, xét x D∈ . Nếu x
bằng quy nạp theo .
k< , ta chứng minh ( )* cũng đúng với n
λ∈
extD∉
∈ y z D y ,
,
thì ta có
≠ và z
(
)0;1
=
x
λ y
+ − (1
λ )
z
điều phải chứng minh. Giả sử x . Khi ấy tồn tại sao cho
i
m∈ 1,
. Do D bị chặn nên đường thẳng qua y,z thoát ra khỏi D tại 2 điểm. Không
mất tính tổng quát ta giả sử hai điểm đó là y và z. Theo bổ đề 1.3, ta có tồn tại thoả
a x ,i
b< và i
a y ,i
b= . i
n
=
=
H
:
mãn
. Như trong chứng minh định lý 1.4, ta
D H D i
1
i
a x , i
b i
{ = ∈ x
}
⊂
<
D conv extD
dim
dim
D
extD extD⊂
Đặt . Đặt
(
1
) 1 .
D 1
1
⊂
∈
extD extD⊂
z
có và .Theo giả thiết quy nạp ta có Suy ra
(
)
( conv extD
)
(
)
( conv extD
)
y D conv extD 1
∈ ⊂ 1
1
∈
⊂
x
y z ;
. Tương tự ta cũng có . Vậy
( conv extD
)
[
]
.
n
≤
=
D conv extD
Au
:
Định lý 1.11:
(
) { + ∈ u
. Tập lồi đa diện D khác rỗng và không chứa đường thẳng có thể biểu diễn dưới dạng } 0
n
:
Au
D
Chứng minh:
D⊂ nên
( conv extD
)
( conv extD
) { + ∈ u
} ≤ ⊂ 0
n
=
⊂
≤
n
dim
D
D conv extD
:
Au
Vì . Ta chứng minh
(
) { + ∈ u
} 0
. ( )* bằng quy nạp theo
0n = . Giả sử ( )* đúng với mọi n k< , ta chứng minh ( )* cũng
=
D conv extD
Rõ ràng ( )* đúng với
k= . Nếu D bị chặn thì theo định lý 1.7,
(
)
đúng với n . Ta có điều phải chứng
minh. Ngược lại, giả sử D không bị chặn thì theo định lý 1.2 , D có phương vô tận hay tồn
n
≥
≠
≤
x
vλ λ− :
v
0,
v
:
Au
} 0
{ ∈ ∈ u
} 0 .
tại phải thoát khỏi D tại một Xét x D∈ . Ta có tia {
x
vλ λ+ :
i
m∈ 1,
điểm y nào đó vì nếu không D sẽ chứa toàn bộ đường thẳng qua x phương v – đường thẳng
{
}
∈ . Theo bổ đề 1.3, ta có tồn tại
+
v
a x ,i
< và b i
a y ,i
b= . i
n
=
=
H
:
thoả mãn
. Như trong chứng minh định lý 1.4, ta
D H D i
1
i
a x , i
b i
{ = ∈ x
}
<
dim
dim
D
extD extD⊂
Đặt . Đặt
D 1
1
1D cũng là tập lồi đa diện không chứa đường thẳng
n
⊂
≤
=
:
Au
0,
và . Vì có
(
D conv extD 1
1
a u , i
} 0
n
⊂
≤
extD extD⊂
D conv extD
Au
:
. nên theo giả thiết quy nạp, ta có ) { + ∈ u
(
1
1
) { + ∈ u
} 0
>
y
= − x
0
nên . Do
)
( vλ λ 0
0
n
n
≤
⊂
≤
x
Au
D conv extD
Au
:
:
Đặt . Ta có
(
λ= + y 0
v D 1
1
{ ∈ + ∈ u
} 0
) { + ∈ u
} 0
.
n
⊂
≤
D conv extD
:
Au
Vậy
(
) { + ∈ u
} 0
.
Bổ đề 1.12:
n
∈
≤
:
Au
Nếu D là tập lồi đa diện không chứa đường thẳng thì nón các phương vô hạn – tập
} 0
là tập nón hữu hạn sinh. hợp { u
n
≤
:
Au
Chứng minh:
{ = ∈ G u
} 0
=
n
dim
G
Ta chứng minh là tập nón hữu hạn sinh ( )* bằng quy nạp theo
=
=
G
cone
0n = thì
n = . 0
.
{ } 0
{ } 0
≥
k= . Do
Nếu .Vậy ( )* đúng với
( < n k k
)1
≥
x
vλ λ− :
dim
1
v G v∈
,
0
G k= ≥ nên tồn tại
Giả sử ( )* đúng với mọi , ta chứng minh ( )* cũng đúng với n
≠ . Xét x G∈ . Ta có tia {
} 0
phải thoát khỏi G tại
x
vλ λ+ :
một điểm y nào đó vì nếu không sẽ chứa toàn bộ đường thẳng qua x phương v – đường
}
∈ và khi ấy D cũng chứa đường thẳng. Theo bổ đề 1.3, ta có tồn tại
i
m∈ 1,
thẳng {
v+
0
,
< và 0
ia x ,
ia y = .
thoả mãn
n
=
=
H
:
∀ = i
1,
m
. Như trong chứng minh định
G H G i
i
i
a x , i
{ = ∈ x
} 0 ,
<
dim
G
Đặt . Đặt
iG
=
. Vậy theo giả thiết quy nạp, ta có lý 1.4, ta có dim
G coneR i
i
iR là tập hữu hạn.
>
y
= − x
0
với
)
( vλ λ 0
0
∈
x
v
Đặt . Ta có
{ } v
)
λ= + y 0
( cone R i
⊂
0
,
.
ia x = là hữu hạn ( m ràng buộc) nên G coneR
=
Do số ràng buộc với R là tập hữu
hạn. Vì R G⊂ nên coneR G⊂ . Vậy G coneR .
Định lý 1.13:
n
∈
≤
Au
:
Nếu D là tập lồi đa diện không chứa đường thẳng thì nón các phương vô hạn – tập
} 0
là tập nón sinh bởi các phương cực biên của D. hợp { u
Chứng minh:
n
∈
≤
=
:
,...,
Au
Theo bổ đề 1.12, ta giả sử rằng
}
{ cone x 1
x k
{ u
} 0
.
1x có thể biểu diễn thành tổ hợp nón của các
ix còn lại thì ta có
=
,
,...,
,...,
Ta nhận xét rằng nếu
}
}
}
x k
x k
x 1,...,
{ cone x x 2
1
{ cone x 2
x k
vì khi ấy ta có .Vậy ta giả thể loại nó ra khỏi {
}
x 1,...,
x gồm các phần tử mà mỗi phần tử không thể biểu diễn thành tổ hợp nón k
i
k∈ 1,
thiết rằng {
ix là phương cực biên với mọi
1x không phải là phương cực biên. Vậy tồn tại 2 phương vô tận độc lập tuyến tính
1,y z của
1
A sao cho
=
x 1
y 1
+ . z 1
n
≤
=
:
Au
,...,
của các phần tử còn lại. Khi ấy ta có . Thậy vậy, giả sử
}
y z , 1 1
{ cone x 1
x k
{ ∈ ∈ u
} 0
=
λ
+
=
λ
+
z
y 1
x 1 1
y z ; 2 1
x 2 1
2
Vì nên ta có thể biểu diễn
∈
,...,
với
}
y z , 2
2
{ cone x 2
x k
.
=
+
=
+
+
y
z
Khi ấy, ta có
)
(
)
x 1
y 1
z 1
( + λ λ 2
1
x 1
2
2
.
−
=
y
{ 1
} )
( + λ λ 2
1
x 1
2
+ . z 2
Suy ra
−
1
0
< thì
)
( + λ λ 2
1
n
+
∈
≤
y
z
,...,
:
Au
Nếu
(
)
}
− = x 1
2
2
{ cone x 2
x k
{ ⊂ ∈ u
} 0
−
)
} 1
1 { ( λ λ + 2
1
−
1
.
≥ . 0
)
( + λ λ 2
1
−
1
0
Suy ra D chứa đường thẳng. Vậy ta phải có
> thì
)
( + λ λ 2
1
1
=
+
∈
y
z
,...,
Nếu
(
)
}
x 1
2
2
{ cone x 2
x k
−
{ 1
} )
( λ λ + 2
1
.
1x không thể biểu diễn thành tổ hợp
−
1
0
y
z+
Điều này mâu thuẫn với giả sử ban đầu của ta là
= . Điều này dẫn đến
= . 0
)
( + λ λ 2
1
x 2,...,
x . Vậy ta phải có k
2
2
=
λ
=
λ
y
z=
0
= . Suy ra
nón của các phần tử
2
2
y 1
x z ; 1 1 1
x 2 1
. Điều này mâu Mà vì D không chứa đường thẳng nên
1y và
1z . Vậy
1x là phương cực biên. Chứng minh
i
n∈ 1,
thuẫn với tính độc lập tuyến tính của
ix còn lại, ta có
n
∈
≤
:
Au
hoàn toàn tương tự với các . Vậy nón
ix là phương cực biên với mọi } 0
là tập nón sinh bởi các phương cực biên của các phương vô hạn – tập hợp { u
D.
Từ các định lý 1.10, 1.11, 1.13 ta rút ra kết quả quan trọng sau
Định lý 1.14:
u 1,...,
u là các k
v
Cho D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Gọi
v là các phương cực biên của D. Ta có l
điểm cực biên của D và 1,...,
k
=
≥ ∀ =
D
+ + ...
u
:
0
i
1,
k
+ Nếu D bị chặn thì
u 1 1
u 2 2
λ k
k
= λ λ 1, i
i
∑
= 1
i
λ λ +
.
k
l
k
=
+
≥ ∀ =
≥ ∀ =
:
1,
0
1,
,
0
1,
D
v
i
k
j
l
+ Nếu D không bị chặn thì
α u i i
β j
j
= α α i
i
β j
∑
∑
∑
= 1
= 1
= 1
i
j
i
.
1. Bài toán quy hoạch tuyến tính
x X∈
max
:
1.1 Bài toán tối ưu
( ) f x
}
X .
là bài toán tìm giá trị lớn nhất của hàm số f trên Bài toán tối ưu Cho hàm số f xác định trên tập hợp X . {
Hàm mục tiêu: Hàm số f được gọi là hàm mục tiêu của bài toán.
Phương án: Nếu x X∈ thì x được gọi là phương án của bài toán.
≤
Tập ràng buộc: X được gọi là tập ràng buộc hay tập các phương án của bài toán.
X∗ ∈ sao cho
( ) f x
( f x∗
)
x X∈ thì x∗ được gọi là phương án tối ưu của bài toán và giá trị
( f x∗ được gọi là giá trị tối
)
Phương án tối ưu và giá trị tối ưu: Nếu tồn tại x với mọi
ưu của bài toán.
n
n
∈
≠
≥
c
,
c
0
E
:
≤ Ax b x
,
1.2 Bài toán quy hoạch tuyến tính
{ = ∈ x
} 0
max
c x ,
:
Cho và .
{
} x E∈ .
→
c x ,
max
Bài toán quy hoạch tuyến tính dạng chuẩn tắc là bài toán có dạng
≥
≤ Ax b x
,
0
Bài toán thường được viết dưới dạng .
→
c x ,
max
Bài toán quy hoạch tuyến tính dạng chính tắc là bài toán có dạng
≥
= Ax b x
,
0
.
−
≤ Ax b
,
b
≤ − nên một bài
Nhận xét:
(
) A x
Vì ràng buộc Ax b= có thể thay thế bởi các ràng buộc
toán quy hoạch tuyến tính dạng chính tắc cũng là bài toán quy hoạch tuyến tính dạng chuẩn
tắc.
Định lý sau đưa ra một điều kiện cần và đủ để một bài toán quy hoạch tuyến tính
dạng chuẩn tắc có phương án tối ưu.
→
c x ,
max
Định lý 1.16:
≥
≤ Ax b x
,
0
Bài toán quy hoạch tuyến tính dạng chuẩn tắc có phương án tối ưu khi
và chỉ khi tập các phương án của bài toán khác rỗng và hàm mục tiêu bị chặn trên trên tập
các phương án của bài toán.
)⇒ Hiển nhiên.
)⇐
Chứng minh:
,c x đạt giá trị lớn nhất
+ Nếu D bị chặn thì D là tập compact nên hàm liên tục
trên D . Vậy bài toán có phương án tối ưu.
c v ≤ . Thật vậy, giả sử ngược lại ,
0
+ Nếu D không bị chặn.
+
=
+
λ
→ +∞ → +∞ . Điều này
0
c x ,
λ v
c x ,
c v ,
c v > . Lấy cố định x D∈ . Ta có ,
( λ
)
Xét v là phương vô tận của D thì ta có
n
≥
D
:
≤ Ax b x
,
mâu thuẫn với giả thiết hàm mục tiêu bị chặn trên.
{ = ∈ x
} 0
là tập lồi đa diện khác Tập các phương án của bài toán
u 1,...,
u là các điểm cực biên của D và k
v 1,...,
v là các phương cực biên của D. Theo định lý 1.11, ta có với mỗi x D∈ tồn tại các số l
jα β sao cho
,i
k
l
k
=
+
≥ ∀ =
≥ ∀ =
1,
0
1,
,
0
1,
x
v
i
k
j
l
rỗng, không chứa đường thẳng và không bị chặn. Gọi
α u i i
β j
j
= α α i
i
β j
∑
∑
∑
= 1
= 1
= 1
i
j
i
.
k
l
k
=
+
≤
≤
c x ,
c v ,
Suy ra
α i
c u , i
β j
j
α i
c u , i
c u i
∑
∑
∑
max , ≤ ≤ 1 i k
i
j
i
= 1
= 1
= 1
.
Vậy bài toán có phương án tối ưu.
Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN
2.1. Khái niệm bài toán quy hoạch tuyến tính nguyên
Bài toán quy hoạch tuyến tính nguyên ( toàn phần) là bài toán quy hoạch tuyến tính
có thêm ràng buộc các biến phải là các số nguyên.
→
c x ,
max
n
≥
∈
≤ Ax b x
,
0,
x
→
c x ,
max
Dạng chuẩn tắc của bài toán quy hoạch tuyến tính nguyên:
≥
≤ Ax b x
,
0
Bài toán được gọi là bài toán quy hoạch tuyến tính tương ứng với bài
toán trên.
→
max
, c x
(
n
≥
∈
,
0,
= Ax b x
x
) ′ P
→
c x ,
max
P
Dạng chính tắc của bài toán quy hoạch tuyến tính nguyên:
)
≥
= Ax b x
,
0
được gọi là bài toán quy hoạch tuyến tính tương ứng với Bài toán (
)P′ .
bài toán (
Chú ý:
Từ đây về sau ta chỉ xét trường hợp các dữ liệu của bài toán đều là các số nguyên
,A b , vectơ c có các thành phần là các số nguyên.
nghĩa là các ma trận
2.2. Mối liên hệ giữa dạng chuẩn tắc và chính tắc của bài toán quy hoạch tuyến tính nguyên
Vấn đề đặt ra là liệu có thể giải bài toán quy hoạch tuyến tính nguyên dạng chuẩn tắc
nếu biết cách giải bài toán quy hoạch tuyến tính nguyên dạng chính tắc không.
→
c x ,
max
P
(
n
≥
∈
,
0,
≤ Ax b x
x
) ′
Xét bài toán quy hoạch tuyến tính nguyên dạng chuẩn tắc
→
c x ,
max
Ta xét bài toán phụ sau
m
≥
≥
∈
∈
Ax
+ = y
b x ,
0,
y
0,
x
,n
y
.
=
=
z
,
c
A
A I
(
) x y c ,
(
) ,0 ,
m
=
( mI là ma trận đơn vị cấp m ). Khi đó bài toán
Đặt
phụ có thể viết lại dưới dạng một bài toán quy hoạch tuyến tính nguyên dạng chính tắc như
→
max
, c z
P
sau
(
+ n m
=
≥
∈
0,
Az
, b z
z
) ′′
.
Mệnh đề 2.1:
)P′ có phương án tối ưu thì (
)P′′ có phương án tối ưu.
Nếu (
Chứng minh:
)P′ có phương án tối ưu x∗ .
∗
∗
m
= −
Giả sử (
b Ax
y∗ ≥ và 0
)P′
y∗ ∈ . Ta cũng có
∗
∗
∗
=
= . Vậy
z
∗ x y ,
Ax
∗+ y
b
nên Đặt y . Vì x∗ là phương án của (
)P′′ .
(
)
m
=
∈
∈
là phương án của (
z
x
y
x y ,
,n
)P′′ . Ta có
(
là phương án bất kỳ của (
)(
)
∗
∗
=
≤
=
c z ,
c x ,
c x ,
c z ,
Xét
.
)P′′ .
∗
∗
∗
∗
m
∈
∈
=
Vậy z∗ là phương án tối ưu của(
x
,n
y
z
∗ x y ,
)P′′ thì x∗ là phương án
là phương án tối ưu của (
)
)(
Nếu Mệnh đề 2.2: (
)P′
. tối ưu của (
= −
Chứng minh:
b Ax
)P′
=
. Tương tự như chứng minh trong . Đặt y Xét x là phương án bất kỳ của (
z
x y ,
)P′′ .
(
)
mệnh đề 2.1, ta có là phương án của (
∗
∗
=
≤
=
c x ,
c z ,
c z ,
c x ,
Ta có
.
)P′
. Vậy x∗ là phương án tối ưu của(
)P′ dựa trên kết quả
Như vậy qua hai mệnh đề trên, ta có thể đưa ra lời giải của (
)P′′ :
của(
)P′′ không có phương án tối ưu thì (
)P′
cũng không có phương án tối ưu. + Nếu (
∗
∗
∗
∗
m
=
∈
∈
z
∗ x y ,
x
,n
y
)P′′ có phương án tối ưu
thì x∗ là phương án
(
)(
)
+ Nếu (
)P′
. tối ưu của (
2.3. Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bài toán quy hoạch tuyến tính tương ứng
D
:n
Bổ đề 2.3:
{ = ∈ x
} ≤ Ax b
Nếu là tập lồi đa diện không bị chặn, không chứa đường thẳng
và A có các thành phần là các số hữu tỷ thì các phương cực biên của D có các thành phần là
các số hữu tỷ (nếu u là phương cực biên của D thì có thể chọn λ thích hợp để uλ là phương
cực biên của D có các thành phần là các số hữu tỷ) .
=
,...,
Chứng minh:
(
)
a i
a a , 1 i i
2
a in
. Đặt dòng thứ i của ma trận A là
=
Vì D là tập lồi đa diện không bị chặn và không chứa đường thẳng nên D có phương
u
,...,
u
(
)
u u , 1
2
n
= ∀ =
,...,
i
n
0,
1,
cực biên . Theo định lý 1.8, không mất tính tổng quát ta coi hệ
− . 1
{
}
, a a 1 2
a − 1 n
ia u ,
,...,
B
là độc lập tuyến tính và
}
a a , 1 2
a − n 1
−
a a 11 1 n a − 1 n n
n
) 1 1
a (
=
1n − vec tơ cột độc lập tuyến tính. Không mất tính
1
rankB n= − . Vậy có thể chọn từ B
1n − vec tơ cột đầu tiên độc lập tuyến tính, tức là ma trận
Đặt là độc lập tuyến tính nên .Vì hệ {
− 1
C
tổng quát ta giả sử B có
a a 11 1 n
a n
− 1
a n
− − 1 n 1
=
= ∀ =
i
n
0,
1,
1
− , nghĩa là
khả nghịch.
ia u ,
a 1 n
u 1
+
=
C
u
0
n
u
− 1
a (
− 1)
n
n
n
Ta có
a 1 n
u 1
− 1
= −
hay
u C n
u
−
− 1
a (
1)
n
n
n
.
a 1 n
v 1
− 1
= −
C
Đặt
−
v n
− 1
a (
n
1)
n
.
=
=
,...,
,
,...,
u
u
u
Ta có
(
)
) ,1
u 1
n
n
− 1
( u v 1 n
v n
− 1
−
i
1,
n
1
.
∈ ∀ = ,
iv
′ =
u
u
Do A có các thành phần là các số hữu tỷ nên .
1 u
n
→
c x ,
max
Đặt . Ta có u′ là phương cực biên của D có các thành phần là các số hữu tỷ.
)P′ là bài toán quy hoạch tuyến tính nguyên dạng chuẩn tắc
≥
≤ Ax b x
,
0
(
)P là bài toán quy hoạch tuyến tính tương ứng. Hai định lý sau thể hiện mối liên hệ về tính
và Xét (
có nghiệm giữa hai bài toán:
Định lý 2.4:
)P không có phương án tối ưu thì (
)P′
cũng không có phương án tối ưu. Nếu (
Chứng minh:
)P′ không có phương án thì (
)P′ không có phương án tối ưu. Định lý được
Nếu (
)P′ có phương án là
)P . D
0x . Đặt D là tập ràng buộc của bài toán (
chứng minh. Giả sử (
)P không có phương án tối ưu nên D không bị chặn . Gọi
0x ) và vì (
v
u 1,...,
u là các điểm cực biên của D và 1,...,
k
v là các phương cực biên của D. Theo định lý l
khác rỗng (chứa
jα β sao cho
,i
k
l
k
=
+
≥ ∀ =
≥ ∀ =
x
v
1,
0
i
1,
k
,
0
j
1,
l
1.13, ta có với mỗi x D∈ tồn tại các số
α u i i
β j
j
= α α i
i
β j
∑
∑
∑
= 1
= 1
= 1
i
j
i
.
k
l
=
+
c x ,
c v ,
Suy ra
α i
c u , i
β j
j
∑
∑
= 1
= 1
i
j
c v ,
0
> . Thật vậy, giả sử ngược lại
.
c v ≤ 0 , j
0jv sao cho
j 0
j
l= 1,
Tồn tại phương cực biên
. Khi đó với mọi x D∈ , ta có với mọi
k
l
k
=
+
≤
≤
c x ,
c v ,
α i
c u , i
β j
j
α i
c u , i
c u i
∑
∑
∑
max , ≤ ≤ 1 i k
i
j
i
= 1
= 1
= 1
.
)P không có phương án tối ưu .
0λ> thích hợp
Điều này mâu thuẫn với (
0jv có các thành phần là các số hữu tỷ. Ta có thể chọn
Theo bổ đề 2.3,
0jvλ có các thành phần là các số nguyên và vì
0jv là phương cực biên nên
0jvλ cũng là
0
v
vλ=
để
c v > . Khi ấy ,
0j
+
+
)P và
∈ là các phương án nguyên của (
0x
( nv n
)
+
=
+
nv
n c v ,
→ +∞ → +∞ . n
)
(
c x , 0
c x , 0
phương cực biên. Đặt .Ta có v là phương cực biên nguyên và
)P′
không có phương án tối ưu. Vậy (
Định lý 2.5:
)P có phương án tối ưu và có phương án nguyên thì (
)P′
cũng có phương án Nếu (
tối ưu.
Chứng minh:
)P′ có phương án là 1x .
Giả sử (
)P′
)P′
2x sao cho
<
có phương án Nếu ( không có phương án tối ưu thì (
c x , 1
c x , 2
.
)P′
<
< < ...
< ...
c x , 1
c x , 2
c x , n
thỏa mãn Cứ như vậy ta xây dựng được dãy các phương án của ( - dãy { }nx
}
nx là phương án nguyên nên {
, nc x
Vì c có các thành phần là các số nguyên và là
}
, nc x
,c x không bị chặn trên trên tập các phương án của (
)P . Điều này mâu thuẫn với giả thiết
(
)P có phương án tối ưu.
không bị chặn trên. Như vậy hàm mục tiêu dãy các số nguyên tăng ngặt. Do vậy {
)P có phương án tối ưu và có phương án nguyên thì (
)P′
cũng có phương Vậy nếu (
án tối ưu.
Chương 3: THUẬT TOÁN CẮT GOMORY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN
Có thể nói tối ưu rời rạc khai sinh lịch sử phát triển của mình từ năm 1985 khi
Gomory công bố thuật toán cắt nổi tiếng để giải bài toán quy hoạch tuyến tính nguyên.
Trong chương này ta sẽ nghiên cứu thuật toán cắt Gomory và cơ sở lí luận của nó sử dụng
→
c x ,
max
P
(
n
≥
∈
= Ax b x
,
0,
x
) ′
để giải bài toán quy hoạch tuyến tính nguyên dạng chính tắc:
,A b , vectơ c có các thành phần
; các ma trận trong đó A là ma trận cấp m n× và rankA m=
là các số nguyên.
)P′
→
c x ,
max
P
là bài toán Bài toán quy hoạch tuyến tính tương ứng với (
(
)
≥
= Ax b x
,
0
.
3.1. Bảng đơn hình
a 1
j
=
c x ,
A
3.1.1. Khái niệm
x 0
j
a mj
=
⊂
B
. Đặt , cột thứ j của ma trận A:
{ 1,...,
} n
:jA j B∈ độc lập tuyến tính
}
Tập gồm m phần tử sao cho hệ các vec tơ {
=
N
gọi là tập cơ sở.
{ 1,...,
} n B \
j B∈ gọi là các biến cơ sở.
gọi là tập phi cơ sở.
,jx
j N∈ gọi là các biến phi cơ sở.
Các biến
,jx
Các biến
Sử dụng đại số tuyến tính, ta có thể biểu diễn các biến cơ sở qua các biến phi cơ sở.
0x , các biến
x 1,...,
x đều có thể biểu diễn qua các biến phi cơ sở. Cụ n
Như vậy, hàm mục tiêu
=
+
−
=
x
i
0,
n
thể ta có biểu diễn:
x i
x i
0
j
x ij
(
) ,
∑
∈ j N
.
ijx được xác định như sau
Trong đó
−
=
1,
i
j
j N∈ ,
x ij
≠
0 ,
i
j
=
A
∈ i B j N ,
∈ ,
Với ,i .
ijx được xác định bởi hệ thức
j
= ∑ . x A ij i
∈ i B
b
i B j∈
,
Với
= , 0
0ix được xác định bởi hệ thức
x A 0i i
= ∑
∈ i B
=
=
x
,...,
i
0
c x ,
Với .
j= = ,
(
)
x 10
x n
0
x 00
0
=∑ c x i i
∈ i B
=
=
c
i
0,
∈ , j N
Với với .
x 0 j
j
−∑ c x i ij
∈ i B
T
. Với
x ij
=
N
{ ∈ i 0,...
} n j ,
{ } ∈ ∪ 0
,...,
0
i
n= 1,
Đặt . Ma trận T gọi là bảng đơn hình ứng với cơ sở B .
)
x 10
x n
0
ix ≥ với mọi
0
Nếu là thì T gọi là chấp nhận được và khi ấy (
,...,
0
phương án cơ sở ứng với cơ sở B .
)
x 01
x 0
n
jx ≥ với mọi j N∈ thì T gọi là chuẩn và (
0
Nếu gọi là giả phương án ứng
với cơ sở B .
3.1.2. Phép biến đổi cơ bản của bảng đơn hình
kx ra khỏi tập các biến cơ sở, đưa
lx
Phép biến đổi cơ bản của bảng đơn hình : đưa
T
vào .
x ij
=
N
{ ∈ i 0,...
} n j ,
{ } ∈ ∪ 0
B
,...,
0
là bảng đơn hình ứng với cơ sở B , N là tập phi cơ sở và Xét
{ } l
( ′ = ∪ B
) { } k \
x x 1, 0
x lại có thể biểu diễn n
klx ≠ . Khi ấy,
′ =
∪
N
N
cũng là cơ sở và các biến
{ } k
(
) { }\ l
′
T
qua các biến có chỉ số thuộc . Ta có bảng đơn hình mới
′ x ij
′
=
N
{ ∈ i 0,...
} n j ,
{ } ∈ ∪ 0
.
jx trong bảng đơn hình T ,
0R là cột đầu tiên và jR là cột ứng với biến
0R ′ là cột
Gọi
jR ′ là cột ứng với biến
jx trong bảng đơn hình T ′ .Ta có công thức tính lại như
đầu tiên và
′ = − R k
R l x kl
−
R
{ } 0 \
( ∈ ∪ N
) { } l
j
j
, R j l
x kj x kl
′ = R
sau
hoặc viết ở dạng tọa độ
=
0,
, i
n
′ = − x ik
x il x kl
−
,
j
{ } 0 \
( ∈ ∪ N
) { } l
x ij
x il
x kj x kl
′ = x ij
3.2. So sánh theo nghĩa từ vựng
n
3.2.1. Các khái niệm cơ bản
x y ∈ . ,
Cho
0lx >
+ x gọi là dương từ vựng và kí hiệu là nếu x có thành phần khác không đầu
tiên là dương.
x = . 0
0lx ≥
0lx >
y>
x
y− >
nếu hoặc + x gọi là không âm từ vựng và kí hiệu
lx
0l
x
y− ≥
y≥
+ x gọi là lớn hơn từ vựng y và kí hiệu là nếu .
lx
0l
+ x gọi là không bé hơn từ vựng y và kí hiệu là nếu .
x = . 0
0lx ≤
0lx < hoặc
y<
x
y− <
+ x gọi là không dương từ vựng và kí hiệu nếu
lx
0l
x
y− ≤
y≤
+ x gọi là bé hơn từ vựng y và kí hiệu là nếu .
lx
0l
+ x gọi là không lớn hơn từ vựng y và kí hiệu là nếu .
,x y là các vectơ cột.
x
n .
x là các vectơ trong k
Trong định nghĩa trên có thể thay
x 1,...,
x nếu k
x s
x≥ l i
=
=
lex
k
max
1,
i
k∈ 1,
gọi là vectơ cực đại từ vựng của các vectơ với mọi + Giả sử 1,..., )1, ( k∈ sx s
x s
x i : i
{
}
. Kí hiệu .
x 1,...,
x nếu k
x s
x≤ l i
( sx s
)1, k∈
=
=
lex
min
1,
k
i
k∈ 1,
gọi là vectơ cực tiểu từ vựng của các vectơ với mọi +
x s
x i : i
{
}
. . Kí hiệu
′
′
+
x′≤
y′
x
+ < y
x
y
3.2.2. Các tính chất cơ bản
lx
< ly
l
ax <
ax >
và thì . + Nếu
a > và 0
a < . 0
0lx <
0l
0l
+ Nếu thì nếu nếu
=
u
3.2.3. Tối ưu theo nghĩa từ vựng
(
)
)P gọi là phương án tối ưu từ vựng nếu với mọi
u 1,.... n u
=
x
+ Phương án của (
(
)
)P , ta có
x 1,.... n x
≥
,
,...,
u
c x ,
,
,...,
phương án của (
(
)
(
)
c u u , 1
n
l
x 1
x n
c x ,
,
,...,
.
)
x 1,.... n x
)
x n
x 1
(
)P .
của được gọi là phương án mở rộng ứng với phương án ( +(
Nhận xét:
+ Phương án tối ưu từ vựng là phương án tối ưu.
+ Phương án tối ưu từ vựng nếu có thì là duy nhất.
(
)P có phương án tối ưu từ vựng khi và chỉ khi tập các phương án tối ưu của
(
)P khác rỗng và bị chặn.
Định lý 3.1:
)⇐ Đặt
)P . Khi đó tập các phương án tối ưu của (
)P
0x là giá trị tối ưu của (
n
=
∈
=
:
c x ,
Chứng minh:
{ D D x
}0 x
( iu i
)1, k=
cũng là tập lồi đa diện và bị chặn. Đặt là các điểm
x D∈
k
≥ ∀ =
,...,
,
0,
i
1,
k
cực biên của D .Vậy theo định lý 1.11, với mỗi tồn tại
1
λ λ λ 2 k
λ λ = 1, i
i
∑
= 1
i
=
+ λ λ
x
+ + ...
u
u 1 1
u 2 2
λ k
k
=
=
u
lex
k
max
1,
sao cho
0
{ u i : i
}
=
+ λ λ
≤
+ λ λ
=
x
+ + ...
u
+ + ...
u
u
Đặt .Ta có
u 1 1
u 2 2
λ k
k
l
u 1 0
u 2 0
λ k
0
0
.
)P có phương án tối ưu từ vựng là
0u .
)⇒ Giả sử (
)P có phương án tối ưu từ vựng
0u và tập các phương án tối ưu của
(
)P – D không bị chặn.
Vậy (
0u D∈ .
Vì phương án tối ưu từ vựng cũng là phương án tối ưu nên
D là tập lồi đa diện không bị chặn nên có phương vô tận v . Vì các thành phần của
=
0
u
v
0v ≥ và
v ≠ . Vậy
+ . Ta có
0lv >
u 1
0
một phương án của D là không âm nên . Đặt
)P .
1u D∈ và 1 u
u> l
0
0u là phương án tối ưu từ vựng của (
. Điều này mâu thuẫn với
)P khác rỗng và bị chặn.
Vậy tập các phương án tối ưu của (
Định lý 3.2:
)P (nếu có) là phương án cực biên của (
)P .
Phương án tối ưu từ vựng của (
Chứng minh:
)P có phương án tối ưu từ vựng x và x không phải là điểm cực
λ∈
∈ y z D y ,
,
Giả sử ngược lại (
≠ và z
(
)0;1
=
x
λ y
+ − (1
λ )
z
z<
biên của D . Khi đó tồn tại sao cho
ly
=
<
x
λ y
+ − (1
λ )
z
λ z
+ − (1
λ )
z
= . z
l
Không mất tính tổng quát ta giả sử . Khi đó, ta có
)P .
Điều này mâu thuẫn với x là phương án tối ưu từ vựng của (
)P (nếu có) là phương án cực biên của (
)P .
Vậy phương án tối ưu từ vựng của (
3.3. Bảng đơn hình l-chuẩn
x 0
j
=
>
R
T
0
x ij
j
l
=
N
{ ∈ i 0,...
} n j ,
{ } ∈ ∪ 0
x nj
Bảng đơn hình gọi là l-chuẩn nếu với mọi j N∈ .
Nhận xét:
Nếu T là l-chuẩn thì T là chuẩn.
(
)P có phương án tối ưu từ vựng khi và chỉ khi tồn tại cơ sở sao cho bảng đơn hình
Định lý 3.3:
ứng với cơ sở đó là l-chuẩn và chấp nhận được.
)⇐ Giả sử ta có bảng đơn hình T ứng với B là l-chuẩn và chấp nhận được.
Chứng minh:
x 00 x 10
x 0 x 1
−
+
x
R
Biểu diễn hàm mục tiêu và các biến qua các biến phi cơ sở:
j
j
(
)
∑
∈ j N
x n
x n
0
=
0
.
lR >
j
x 00 x 10
x 00 x 10
x 0 x 1
−
≤
+
x
R
với mọi j N∈ . Ta có Do T là chấp nhận được nên
j
l
j
(
)
∑
∈ j N
x n
x n
0
x n
0
=
,...,
.
)
)P .
x 10
x n
0
)⇒ Giả sử (
)P có phương án tối ưu từ vựng x . Theo định lý, x cũng là phương án
Vậy ( là phương án tối ưu từ vựng của (
0
x > . Xét T là bảng đơn hình ứng với x . T là chấp nhận được vì
cực biên tức là phương án cơ sở. Ta chứng minh cho trường hợp x là phương án cơ sở
x là phương án cơ sở. Ta chứng minh T cũng là l-chuẩn. Giả sử ngược lại tồn tại l N∈ sao
0
0
i
n∈ 1,
không thoái hóa nghĩa là
lR <
l
ilx > vì nếu ngược lại thì hàm mục tiêu không bị
. Khi đó tồn tại để cho
)P có phương án tối ưu [3, tr.28-29].
chặn trên, mâu thuẫn với (
lx vào tập các biến cơ sở,
Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa
kx ra theo tiêu chuẩn
0
0
=
=
>
min
:
1,
0
i
, n x il
x k x kl
x i x il
đưa
0
<
−
>
0
(cách chọn k đảm bảo bảng đơn hình mới vẫn là chuẩn).
x k
0,
x kl
R> 0, l
l
′ = R 0
R 0
R l
l
R 0
x k x kl
vì . Điều này mâu thuẫn với x là phương Ta có
)P .
án tối ưu từ vựng của (
3.4. Thuật toán đơn hình đối ngẫu từ vựng tìm phương án tối ưu từ vựng
+ Trường hợp bảng đơn hình xuất phát là l-chuẩn:
Ý tưởng của thuật toán:
Bắt đầu từ một cơ sở mà bảng đơn hình tương ứng là l-chuẩn, nếu bảng đơn hình
chưa là chấp nhận được thì ta tiến hành dịch chuyển sang cơ sở mới mà bảng đơn hình ứng
với cơ sở mới cũng là l-chuẩn cho đến khi gặp bảng đơn hình là chấp nhận được thì dừng.
Khi đó phương án cơ sở ứng với bảng đơn hình cuối là phương án tối ưu từ vựng.
Thuật toán:
Giả sử tồn tại cơ sở B sao cho bảng đơn hình T ứng với B là l-chuẩn.
Bước 1
Nếu T là chấp nhận được thì phương án cơ sở ứng với B là phương án tối ưu từ
vựng. Thuật toán kết thúc.
Ngược lại, ta chuyển sang bước 2.
0,
i
n∈ 1,
Bước 2
≥ ∀ ∈ thì ( j N
)P không có phương án ( vì
ix < và 0
0
ijx
=
+
−
<
x
0
Nếu tồn tại sao cho
)P không có phương án tối ưu từ vựng. Thuật toán kết thúc.
x i
x i
0
j
x ij
(
)
∑
∈ j N
). Vậy (
=
<
k
Ngược lại:
} 0
{ i x min : i
0
R
j
=
<
min
:
,
0
lex
. + Đặt
∈ j N x kj
R l x kl
x kj
+ Chọn l thỏa .
kx ra khỏi tập các biến cơ
+ Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa
lx vào . Quay trở lại bước 1.
sở, đưa
Nhận xét:
Nếu bảng đơn hình xuất phát là l-chuẩn thì chỉ có hai khả năng có thể xảy ra:
)P không có phương án.
+ (
)P có phương án tối ưu từ vựng.
+ (
Định lý 3.4:
Khi sử dụng thuật toán đơn hình đối ngẫu từ vựng thì các bảng đơn hình đều là l-
chuẩn.
Chứng minh:
Với cách chọn dòng và cột xoay như trong thuật toán đơn hình đối ngẫu thì nếu bảng
đơn hình trước là l-chuẩn thì bảng đơn hình sau cũng là l- chuẩn. Thật vậy, thực hiện phép
kx ra khỏi tập các biến cơ sở, đưa
lx vào. Ta có
biến đổi cơ bản của bảng đơn hình : đưa
bảng đơn hình mới được tính lại theo công thức
′ = − R k
R l x kl
−
R
{ } 0 \
( ∈ ∪ N
) { } l
j
j
, R j l
x kj x kl
′ = R
0
lR >
j
R
j
=
<
>
min
:
,
0
lex
0
0
với mọi j N∈ . Giả sử bảng đơn hình trước là l-chuẩn tức là
∈ j N x kj
klx < . Do đó
′ = − R k
l
R l x kl
R l x kl
x kj
−
>
R
R
0 0 0
+ = .
Vì l thỏa nên .
kjx ≥ thì 0
′ = j
j
R l
l
x kj x kl
R
j
=
−
=
−
>
0
R
R
Nếu
′ j
j
R l
x kj
l
kjx < thì 0
x kj x kl
R l x kl
x kj
R
j
=
<
min
:
,
0
lex
Ngược lại, nếu
∈ j N x kj
R l x kl
x kj
0
( vì l thỏa và cách chọn l là duy nhất ).
lR′ >
j
Vậy bảng đơn hình sau cũng là l-chuẩn tức là với mọi j N′∈ .
Mặt khác, bảng đơn hình xuất phát là l-chuẩn. Vậy khi sử dụng thuật toán đơn hình
đối ngẫu từ vựng thì các bảng đơn hình đều là l-chuẩn.
Định lý 3.5:
Khi sử dụng thuật toán đơn hình đối ngẫu từ vựng thì dãy cột đầu tiên của bảng đơn
hình là giảm từ vựng.
0
>
−
<
0
Chứng minh:
x k
0,
x kl
R< 0, l
l
′ = R 0
R 0
R l
l
R 0
x k x kl
Ta có vì .
Cơ sở lí luận của thuật toán:
Do định lý 3.5 ta sẽ tránh được hiện tượng xoay vòng tức là thuật toán lại quay trở về
)P chỉ có hữu hạn các cơ sở nên thuật toán sẽ dừng
một cơ sở mà trước đó đã xét qua và vì (
sau một số hữu hạn các bước lặp.
+ Trường hợp bảng đơn hình xuất phát không là l-chuẩn:
Ý tưởng:
Bắt đầu từ một bảng đơn hình không là l-chuẩn, ta thêm vào một ràng buộc giả tạo
được bảng đơn hình mới. Sau đó chuyển đổi bảng đơn hình này thành l-chuẩn và từ đó áp
dụng thuật toán đơn hình đối ngẫu từ vựng cho cho bảng đơn hình này. Sử dụng kết quả của
bài toán mới để đưa ra kết quả cho bài toán ban đầu.
Thuật toán:
)P có cơ sở B mà bảng đơn hình tương ứng không là l-chuẩn. Ta thêm ràng
Giả sử (
x M
buộc giả tạo vào bài toán:
j
≤∑
∈ j N
0
.
nx + ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về dạng
1
Đặt biến phụ
=
+
M
x
đẳng thức
x + 1n
j
)
( −∑
∈ j N
.
B
Viết dòng trên vào cuối bảng đơn hình ta thu được bảng đơn hình mới ứng với bài
}1
{ n +
)MP . (
)MP có cơ sở là
. toán mở rộng (
1nx + ra khỏi tập các biến cơ
Thực hiện phép biến đổi cơ bản của bảng đơn hình: đưa
∈
=
R j N
lex
min
:
sở, đưa
R l
j
lx vào theo quy tắc từ vựng: }
{
.
Khi đó, ta nhận được bảng đơn hình mới là l-chuẩn. Thật vậy, theo công thức biến
R l
đổi bảng đơn hình ta có
−
R
{ } 0 \
( ∈ ∪ N
) { } l
+′ = − R n 1 ′ = R j
j
R j , l
=
∈
lex
min
R j N
:
.
R l
j
{
}
>
0
0
Vì bảng đơn hình xuất phát không là l-chuẩn và nên
+′ = −
lR <
l
R n
1
R l
l
=
∈
lex
min
R j N
:
. Vậy .
R l
j
{
}
−
R
R
> ∀ ∈ ∪ j
0,
N
Vì và cách xác định l là duy nhất nên
{ } 0 \
(
) { } l
′ = j
j
R l
l
.
vựng cho bài toán mở rộng ( Từ bảng đơn hình l-chuẩn này ta có thể tiến hành thuật toán đơn hình đối ngẫu từ )MP . Chú ý rằng trong quá trình tiến hành thuật toán ta luôn
M . Thuật toán sẽ dừng ở một trong những trường hợp sau:
xem M là số lớn hơn bất kì số nào cần so sánh với nó và chỉ có cột đầu tiên phụ thuộc vào
)P không có phương án. Vậy (
)P không có phương án
)MP không có phương án thì (
+ (
tối ưu từ vựng.
)MP có phương án tối ưu từ vựng Mx . Ta kiểm tra
+ (
)P không có phương án tối ưu.
)MP phụ thuộc vào M thì (
- Nếu giá trị tối ưu của (
)P không có phương án tối ưu từ vựng.
Vậy (
)MP không phụ thuộc vào M (là hằng số). Xét Mx′ nhận được
1n + ( bỏ biến phụ
- Nếu giá trị tối ưu của (
1nx + ). Ta kiểm tra:
)P có tập các phương án tối ưu không bị chặn.Vậy
từ Mx bằng cách loại bỏ thành phần thứ
(
)P không có phương án tối ưu từ vựng.
)P . Xóa
* Nếu Mx′ phụ thuộc vào M thì (
* Nếu Mx′ không phụ thuộc vào M thì Mx′ là phương án tối ưu từ vựng của (
1nx + ) ta nhận được bảng đơn hình là l-chuẩn và chấp nhận
)P .
bỏ dòng cuối (dòng chứa biến phụ
được ứng với Mx′ của (
Chú ý :
)MP và Mx′ tức là kiểm tra cột đầu tiên của bảng đơn hình
Kiểm tra giá trị tối ưu của (
bỏ đi thành phần cuối.
Cơ sở lí luận của thuật toán:
M M≥
Định lý 3.6:
)P có phương án thì tồn tại
)MP có phương
0M sao cho với mọi
0
Nếu ( ta có (
án.
∗
=
x M∗
x
Chứng minh:
)P có phương án
0M sao cho
j
0
∗ x 1 ,...,
∗ x n
(
)
≤∑
∈ j N
=
+
=
M
x
M M≥
,...,
. Chọn . Với Giả sử (
)MP có phương án
∗ x + 1n
∗ j
0
∗ x 1
+ 1
∗ x M
∗ ∗ , x x n n
)
(
)
( −∑
∈ j N
M M≥
, đặt trong đó . Khi ấy (
0
Mx∗ với mọi
.
M M≥
Định lý 3.7:
)P có phương án tối ưu thì tồn tại
)MP có
0M sao cho với mọi
0
Nếu ( ta có (
giá trị tối ưu không phụ thuộc vào M (là hằng số).
Chứng minh:
∗
=
x M∗
x
)P có phương án tối ưu
0M sao cho
j
0
∗ x 1 ,...,
∗ x n
(
)
≤∑
∈ j N
=
+
=
M
x
M M≥
,...,
. Chọn . Với Giả sử (
∗ x + 1n
∗ j
0
∗ x M
∗ x 1
∗ ∗ x x , n n
+ 1
)
(
)
( −∑
∈ j N
,...,
M M≥
, đặt trong đó . Khi ấy Mx∗ phương án tối ưu
)
)MP với mọi
x 1
x x + ,n 1 n
)MP thì
0
∗
=
=
x
x
(
)
của ( . Thậy vậy, xét ( là phương án của (
)P . Do
)P nên
x 1,...,
x n
∗ x 1 ,...,
∗ x n
(
)
≤
,...,
c x ,
c x∗ ,
là phương án của ( là phương án tối ưu của (
)
)MP tại phương án (
x 1
x x + ,n 1 n
=
M M≥
,...,
không lớn . Tức là giá trị hàm mục tiêu của (
0
∗ x M
∗ x 1
∗ ∗ x x , n n
+ 1
(
)
thì là phương án nên là phương án tối ưu hơn tại Mx∗ .Vậy nếu
,c x∗ ( giá trị tối ưu của (
)P ) không phụ thuộc vào
)MP và giá trị tối ưu của (
)MP là
M .
của (
)MP có phương án tối ưu từ vựng Mx và giá trị tối ưu không phụ thuộc vào
1n + ( bỏ biến phụ
M . Xét Mx′ nhận được từ Mx bằng cách loại bỏ thành phần thứ
1nx + ). Khi
Giả sử (
ấy ta có hai kết quả sau:
)P không bị chặn.
Định lý 3.8:
Nếu Mx′ phụ thuộc vào M thì tập các phương án tối ưu của (
β+∈ 1 n
>
α β ,
,
0
Mα β+
Chứng minh:
Mx có dạng
0M sao cho
0
Mα β= +
Mα β= +
0
M M≥
≥ . Khi ấy
≥ với mọi
Mx
0
Mx
trong đó . Chọn Ta có
0
0
M M≥
. Do đó Mx′ là phương án của
(
)P với mọi
0
′+ Mα β′
,α β′
.
′ nhận được từ
,α β bằng cách bỏ đi
0β′ > .
trong đó Ta có Mx′ có dạng
thành phần cuối .Vì Mx′ phụ thuộc vào M nên
)P cũng có giá trị tối ưu là
)MP . Ta chứng minh (
0x là giá trị tối ưu của (
0x .
x M
Đặt
)
)P . Chọn M sao cho
x 1,...,
x n
j
≤∑
∈ j N
=
=
+
,...,
M
x
. Đặt Thật vậy, xét ( là phương án của (
(
)
x M
x 1
, x x + 1 n n
x + 1n
j
)MP có phương án Mx . Vì
0x là giá
)
( −∑
∈ j N
,c x
trong đó . Khi ấy (
)MP nên giá trị hàm mục tiêu của (
x≤ 0
)MP tại Mx :
. trị tối ưu của (
)P cũng có giá trị tối ưu là
)P chứa
0x và tập các phương án tối ưu của (
≥
≥
≥
:
′ ′ + α β M M M
:
Vậy (
0β′ > là tập không bị chặn.
{
} { =
}
′ :Mx M M
}0
′ Mx M M
0
0
với . Mà {
)P không bị chặn.
Vậy tập các phương án tối ưu của (
)P . Xóa bỏ
Định lý 3.9:
Nếu Mx′ không phụ thuộc vào M thì Mx′ là phương án tối ưu từ vựng của (
1nx + ) ta sẽ nhận được bảng đơn hình là l-chuẩn và chấp
)P .
dòng cuối (dòng chứa biến phụ
nhận được ứng với Mx′ của (
Chứng minh:
1nx + phải là biến cơ sở. Thật vậy, giả sử
Giả sử Mx′ không phụ thuộc vào M . Khi ấy
1nx + là biến phi cơ sở thì do Mx′ không phụ thuộc vào M nên
1nx + không phụ thuộc
=
+
M
x
ngược lại
x + 1n
j
)
( −∑
∈ j N
vào M . Điều này mâu thuẫn với . Do bảng đơn hình cuối là l-chuẩn và
1nx + ) ta vẫn sẽ nhận được
chấp nhận được nên khi ta xóa bỏ dòng cuối (dòng chứa biến phụ
1nx + là biến cơ sở nên bảng đơn hình mới
bảng đơn hình là l-chuẩn và chấp nhận được và do
1nx + . Vậy ta có bảng đơn hình là l-chuẩn và chấp nhận được ứng với
)P .
Mx′ của (
không chứa biến
Nhận xét:
Nếu bảng đơn hình xuất phát không là l-chuẩn thì có các khả năng có thể xảy ra khi
tiến hành thuật toán:
)P không có phương án.
+ (
)P có phương án nhưng không có phương án tối ưu.
+ (
)P có tập các phương án tối ưu không bị chặn.
+ (
)P có phương án tối ưu từ vựng.
+ (
Ví dụ 3.10:
2
min
+ → x 2
+
−
=
2
3
7
x 2
+
=
+
x 3
3
x 1 x 1 x 1
x 4
x 2 ≥ ∀ =
0,
1, 4
i
x i
Tìm phương án tối ưu từ vựng của bài toán quy hoạch tuyến tính
Viết lại bài toán dưới dạng
2
max
− → x 2
+
3
x 1 x 1
x 2
−
x 2
1, 4
i
= − x 0 = − + 7 2 x 3 − = 3 x x 4 1 ≥ ∀ = 0, x i
1x−
2x−
Khi ấy ta có bảng đơn hình xuất phát là l-chuẩn
0x
0 1 2
1x
0 -1 0
2x
0 0 -1
3x
-2 -3 -7
4x
3 1 1
3x ra khỏi tập các biến cơ sở, đưa vào
1x
3x−
2x−
0x
1 1 − 2 2
7 2
1x
3 2
7 2
1 − 2
Đưa
2x
-1 0 0
3x
4x
1 − 2
1 − 2
1 2
0 0 -1
4x ra khỏi tập các biến cơ sở, đưa vào
2x
Đưa
4x−
2x−
`
0x
1 -4 1
1x
2 1 3
2x
1 -1 -2
3x
0 -1 0
4x
0 0 -1
x∗ =
Bảng đơn hình cuối là l-chuẩn và chấp nhận được. Ta nhận được phương án tối ưu từ
(
)2,1
vựng của bài toán .
Ví dụ 3.11:
=
4
max =
+ → x 2 +
7
x 0 2
x 1 + 4
+
=
15
x x 2 3 3 x 2
x 1 x 1
x 4
1, 4
i
+ 10 ≥ ∀ = 0, x i
Tìm phương án tối ưu từ vựng của bài toán quy hoạch tuyến tính
4
max
−
4
x 1 x 1
+ → x 2 x 2
−
3
x 1
x 2
1, 4
i
= x 0 = − 7 2 x 3 = − 15 10 x 4 ≥ ∀ = 0, x i
Viết lại bài toán dưới dạng
1x−
2x−
Khi ấy ta có bảng đơn hình xuất phát
0x
0 -1 -4
1x
0 -1 0
2x
0 0 -1
3x
7 2 4
4x
15 10 3
+
x 1
≤ x M 2
0
Bảng đơn hình xuất phát không là l-chuẩn. Ta thêm vào ràng buộc giả tạo
x ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về dạng đẳng 5
Đặt biến phụ
=
−
−
thức
x M x 5 1
x 2
.
1x−
2x−
Ta có bảng đơn hình mở rộng
0x
0 -1 -4
1x
0 -1 0
2x
0 0 -1
3x
7 2 4
4x
15 10 3
5x M
1 1
5x ra khỏi tập các biến cơ sở, đưa vào
2x
1x−
5x−
Đưa
4M
0x
3 4
1x
-1 0 0
M
2x
7 4M−
1 1
3x
15 3M−
-4 -2
4x
7 -3
5x
0 -1 0
3x ra khỏi tập các biến cơ sở, đưa vào
5x
1x−
3x−
Đưa
0x
7 3 4
1x
0 -1 0
2x
7 4
1 1
3x
0 -2 -4
4x
39 4
7 -3
5x
M
7 − + 4
0 -1
Bảng đơn hình trên là l-chuẩn và chấp nhận được và cột đầu tiên của bảng không phụ
x∗
7, 0,
, 0,
thuộc vào M (không kể thành phần cuối). Vậy bài toán đã cho có phương án tối ưu từ vựng
5x ) ta nhận được bảng đơn hình
7 4
39 4
=
. Xóa bỏ dòng cuối (dòng chứa biến phụ
1x−
3x−
là l-chuẩn và chấp nhận được ứng với phương án tối ưu từ vựng x∗ của bài toán
0x
7 3 4
1x
0 -1 0
2x
7 4
1 1
3x
0 -2 -4
4x
39 4
7 -3
1. Lát cắt đúng
∗
=
x
)P có phương án tối ưu là
∗ x 1 ,...,
∗ x n
(
)
n
. Khi Giả sử bài toán quy hoạch tuyến tính (
)P nếu như nó thỏa
a x α i i
≤∑
= 1
i
ấy ràng buộc tuyến tính được gọi là một lát cắt đúng của (
n
a x α∗ .
hai điều kiện sau:
)P tức là
i
i
>∑
= 1
i
+ Ràng buộc tuyến tính cắt bỏ đi phương án tối ưu của (
)P tức là nếu
n
=
x
+ Ràng buộc tuyến tính không làm mất đi phương án nguyên nào của (
(
)
)P thì
x 1,...,
x n
a x α i i
≤∑
= 1
i
. là phương án nguyên của (
3.5. Thuật toán cắt Gomory
3.5.1. Điều kiện để sử dụng thuật toán Gomory
( )i Tập các phương án tối ưu của (
)P bị chặn
Để sử dụng thuật toán Gomory ta cần có điều kiện
và một trong hai điều kiện sau
)ii Hàm mục tiêu bị chặn dưới trên tập các phương án của (
)P ,
(
(
)iii
hoặc
)P có phương án nguyên.
(
Chú ý:
)P có phương án tối ưu nhưng không
+ Điều kiện ( )i để tránh rơi vào trường hợp (
có phương án tối ưu từ vựng. Ở bước đầu tiên trong thuật toán Gomory là sử dụng thuật
)P và với điều kiện
( )i thì khi tiến hành thuật toán chỉ có thể xảy ra hai khả năng hoặc (
)P không có phương án
toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của (
)P có phương án tối ưu từ vựng.
tối ưu hoặc (
)ii hoặc (
)iii
để đảm bảo thuật toán có thể kết thúc sau hữu hạn các + Điều kiện(
bước lặp.
)P có bảng đơn hình xuất phát là l-chuẩn thì điều kiện ( )i được thỏa mãn.
+ Nếu (
)P bị chặn thì điều kiện ( )i và (
)ii được thỏa mãn.
+ Nếu tập các phương án của (
)P′
. Khi đó ta có thể tiến hành thuật toán Gomory để giải (
3.5.2. Thuật toán cắt Gomory
Ý tưởng:
)
( P=
)
0P
k =
0,1,...
. Bước chuẩn bị: Đặt (
Bước lặp
Sử dụng thuật toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của
(
)P′
)kP . Nếu (
)kP không có phương án tối ưu thì (
kx . Nếu
kx nguyên thì
kx là phương án tối ưu của
cũng không có phương án tối ưu. Ngược
)kP có phương án tối ưu từ vựng
(
)P′
lại, (
)kP một lát cắt đúng loại bỏ phương án
. Ngược lại bổ sung thêm vào hệ ràng buộc của (
kx nhưng không làm mất đi phương án nguyên nào của (
)P . Đặt (
)1kP +
1k + .
(
)kP có bổ sung thêm lát cắt đúng. Chuyển sang bước
tối ưu là bài toán
Thuật toán:
Bước 0:
(
)P . Do điều kiện ( )i nên chỉ có thể xảy ra một trong hai khả năng:
Sử dụng thuật toán đơn hình đối ngẫu từ vựng để tìm phương án tối ưu từ vựng của
)P không có phương án tối ưu. Theo định lý 2.4 thì (
)P′
cũng không có phương án + (
0x . Ta kiểm tra:
tối ưu. Thuật toán kết thúc.
)P có phương án tối ưu từ vựng
+ (
0x là phương án nguyên của (
)P thì
0x là phương án tối ưu của (
)P′
- Nếu . Thuật toán
0x là không phải là phương án nguyên thì kí hiệu
kết thúc.
0T là bảng đơn hình
- Ngược lại, nếu
0x và chuyển sang bước lặp thứ
r = . 0
ứng với
( r r ≥
)0
Bước lặp thứ :
rx là phương án cơ sở ứng với bảng đơn hình
rT ( rT là l-chuẩn và chấp nhận
Đặt
=
=
k
i
0,
được).
r n x , 0 i
{ i min :
} ∉ .
−
−
x
Đặt
= − x
{ } x
[ ] x
r x kj
j
r x k
{
}
) { ≥
}0
(
)
∑
(
)(
∈ j N
r
0
n rx + + ≥ , đưa về dạng đẳng thức
1
. Đặt biến phụ Xây dựng lát cắt đúng
= −
+
−
−
x
( ) 1
+ + 1
0
x n r
r x k
r x kj
j
)
{
}
{
}
∑
(
)(
∈ j N
r
Viết dòng ( )1 vào cuối bảng đơn hình. Ta nhận được bảng đơn hình mới vẫn là l-
n rx + + ). Áp
1
chuẩn và không chấp nhận được (tính chấp nhận được chỉ bị vi phạm đối với
n rx + + ra
1
n≥ + thì ta loại bỏ
dụng thuật toán đơn hình đối ngẫu với bảng đơn hình này, đồng thời sau khi đưa
)1
( lx l
khỏi tập các biến cơ sở thì xóa dòng ( )1 và nếu đưa vào biến phụ
dòng của bảng đơn hình ứng với nó.
Nếu cuối cùng nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính
)P′
không có phương án tối ưu. Thuật toán kết thúc. Ngược lại, không có phương án thì (
1rx + là phương án cơ sở ứng
1rT + . Đặt
nhận được bảng đơn hình l-chuẩn và chấp nhận được
1rx + có các thành phần nguyên thì
1rx + là phương án tối ưu của
1rT + . Nếu
với bảng đơn hình
1r + .
(
)P′
. Thuật toán kết thúc. Ngược lại, chuyển sang bước lặp
n≥ + bị đưa vào tập các biến cơ sở, ta loại bỏ dòng chứa nó
Nhận xét:
)1
( lx l
Mỗi khi biến phụ
( lx không tham gian vào các tính toán tiếp theo). Điều này khiến mở rộng tập ràng buộc của
bài toán quy hoạch tuyến tính tương ứng làm giảm hiệu quả của thuật toán nhưng bù lại nó
giúp bảng đơn hình khỏi có số dòng không xác định (sau mỗi bước lặp lại có thêm một biến
2n + dòng và có số cột không thay đổi,
n m− + cột. 1
phụ). Như vậy, trong quá trình thực hiện thuật toán Gomory, bảng đơn hình không có quá
3.5.3. Cơ sở lí luận của thuật toán
r
=
x
Định lý 3.12:
rT và
r 1 ,..., x
r x n
(
)
−
−
∉
x
0,
n
Giả sử là phương án cơ sở ứng với bảng đơn hình
r x kj
j
r x k
0
r kx
{
}
) { ≥
}0
( ∈ k
)
∑
(
)(
∈ j N
r
Nếu thì ( )∗ là lát cắt đúng của bài toán quy
rT .
r
=
x
hoạch ứng với
rT .
r 1 ,..., x
r x n
)
r
> . 0
là phương án cơ sở ứng với bảng đơn hình Đặt Chứng minh: (
0
r kx
kx ∉ nên {
}0
Vì
r
−
−
0
= < 0
x
jx = với mọi
r x kj
r j
r x k
j N∈ nên r
{
}
)
{
}0
∑
(
)(
∈ j N
r
Vì . Tức là ( )∗ thỏa điều kiện
′
=
x
thứ nhất của một lát cắt đúng.
(
)
′ 1,..., x
′ x n
rT và
Xét là phương án nguyên của bài toán quy hoạch ứng với
(
)
)
′ ′ 1, x x ..., 0
′ x n
′ ′ 1, x x ..., 0
′ x n
có cũng có các thành phần nguyên. là phương án mở rộng của x′ thì (
=
+
−
=
+
−
+
−
x
x
x
Ta có
0
0
0
′ x k
r x k
r x kj
′ j
r x k
r x kj
′ j
r x k
r x kj
′ j
(
)
(
)
) { +
}
{
}(
∑
∑
∑
∈ j N
∈ j N
∈ j N
r
r
r
.
= −
+
−
−
z
x
Đặt
0
r x k
r x kj
′ j
)
{
}
{
}
∑
(
)(
∈ j N
r
.
=
+
−
z
x
.
0
r x k
′ j
′ − ∈ x k
(
)
∑ r x kj
∈ j N
r
= −
+
−
−
> −
≥
> − + = − 1 0
1
z
x
x
1,
0,
0
≥ nên
Ta có
0
r x k
r x kj
r j
0
r x k
j
r x kj
{
}
{
}
)
}
{
}
∑
(
)(
∈ j N
r
0
1
. Vì { −
z ≥ . Tức là ( )∗ thỏa điều kiện thứ hai của một lát cắt
z > − và z ∈ nên
Vậy
đúng.
Vậy ( )∗ là lát cắt đúng.
Định lý 3.13:
Nếu trong quá trình thực hiện thuật toán ta nhận được bảng đơn hình ứng với bài toán
)P′ không có phương án.
quy hoạch tuyến tính không có phương án thì bài toán (
Chứng minh:
)P . Vì vậy tập ràng
Lát cắt đúng không làm mất đi một phương án nguyên nào của (
buộc của bài toán quy hoạch tuyến tính ứng với một bảng đơn hình trong quá trình tiến hành
)P′
(
)P′ cũng không có phương án.
.Vậy nếu nó không có phương án thì thuật toán luôn chứa tất cả các phương án của (
Định lý 3.14:
rx có các thành phần nguyên thì
rx là phương án tối ưu của (
)P′
Nếu .
Chứng minh:
rD là tập ràng buộc của bài toán quy hoạch tuyến tính ứng với bảng đơn hình
Gọi
)P′
rT , D′ là tập ràng buộc của (
.
r
≥
c x ,
c x ,
,
∀ ∈ . x D r
Ta có
D D′ ⊂ r
r
≥
c x ,
c x ,
,
x D′ ∀ ∈ .
r
≥
c x ,
c x ,
,
x D′ ∀ ∈ và
rx D′∈ nên
nên Vì
rx là phương án tối ưu của (
)P′
r
=
x
. Vậy
rT ,
r x 1 ,...,
r x n
(
)
r
r
=
=
x
,...,
y
,
,...,
y
Giả sử là phương án cơ sở ứng với bảng đơn hình
rx ,
r r x x 1, 0
r y 0
r y 1
r x n
r n
(
)
(
)
là phương án mở rộng của là giả phương án mở rộng
rT sau khi đưa
n rx + + ra khỏi tập các biến cơ sở và xóa dòng
1
( )1 .
nhận được từ bảng đơn hình
r
r
1
r
>
≥
x
y
x +
Bổ đề 3.15:
Ta có với mọi r ∈ .
Chứng minh:
r
r
r
1
,
,
Kết quả này là hệ quả của định lý vì khi áp dụng thuật toán đơn hình đối ngẫu từ
x y x + nhận được bằng
vựng, dãy cột đầu tiên của bảng đơn hình là giảm từ vựng và
=
:
i
0,
n r ,
∈ bị chặn dưới.
r ix
cách chuyển vị cột đầu tiên của bảng đơn hình tương ứng.
}
Bổ đề 3.16: Tập hợp {
r
r
=
=
0
i
1,
n r ,
x
Chứng minh:
∈ .
ix ≥ với mọi
r 1 ,..., x
r x n
(
)
r
=
c x ,
m
Vì là phương án nên
≥ với mọi r ∈ .
r x 0
=
:
i
0,
n r ,
{ min 0, m .
}
∈ bị chặn dưới bởi
r ix
Nếu hàm mục tiêu bị chặn dưới thì tồn tại m sao cho
}
Vậy tập hợp {
)P có phương án nguyên. Xét x′ là một trong những phương án nguyên của
(
)P . Vì lát cắt đúng không làm mất đi phương án nguyên nào của (
)P nên ta có
r
=
=
≥
:
i
0,
n r ,
,c x′
c x ,
c x′ ,
Nếu (
∈ bị chặn dưới bởi
{ min 0,
}
r ix
r x 0
}
. . Vậy tập hợp {
r
n
=
∉
x
x
n
0,
,...,
x
,
,...,
y
Bổ đề 3.17:
x ∉ và
0
r r x x , 0 1
r y 0
r y 1
r p
r p
r p
l
r p
(
)
( ∈ p
)
) ≥
Nếu . thì (
=
∈
k
i
0,
Chứng minh:
p≤ .
∉ . Ta có k
r n x , 0 i
{ i min :
}
R
r j
=
≠
min
,
:
0
lex
Đặt
{ ∈ j N x kj
}
{
}
r R l x kl
x kj
{
}
=
∈
≠
h
i
0,
Đặt ( dòng quay là lát cắt mới thêm vào).
lR có hệ số khác 0).
r n x , il
{ i min :
} 0
r
r
0
0
(hàng đầu tiên của cột Đặt
rT l-chuẩn nên
lR > . Do đó
hlx > .
r
r
0
p
k
Vì
≤ ≤ .
kx ∉ nên
0
0
kx ≠ . Vậy h
Vì
0
=
−
,
0,
∀ = i
n
Ta có
r y i
r x i
r x il
r x kl
{ r x k {
} }
=
∈
≠
=
h
i
0,
i
0,
,
h
i
.
= ∀ < . Do đó h
∀ < .
r n x , il
r ilx
r y i
r x i
{ i min :
} 0
Vì nên
0
−
=
<
>
y
0,
Ta xét hai khả năng có thể xảy ra
≠ 0.
0
r x h
r h
r x hl
r x h
r x hl
r x k
r x kl
p< } }
=
i
,
y
∀ < ; h
do Ta có Trường hợp 1: h { r x k {
p< nên
r y i
r x i
r h
r x< h
x
y
,...,
,
,...,
và h
r r x x , 0 1
r y 0
r y 1
r p
l
r p
(
)
) ≥
p
k
= = .
. Tóm lại, ta có (
=
=
,
i
,
p
i
∀ < và h h
p= nên
∀ < .
Trường hợp 2: h
r y i
r x i
r y i
r x i
r
r
Vì
klx ∉ và
klx > nên 0
r x kl
{ r x≥ kl
}
0
=
−
≤
−
=
−
y
0
r k
r x k
r x kl
r x k
r x k
r x k
r x k
{
}
{ } r x k
=
.
r x kl
{ r x k {
} }
y
Vì . Do đó ta có
p= nên
r p
r p
x ≤
.
=
i
,
∀ < và r p y
Vì k
r y i
r x i
p
r p
x ≤
nên
x
y
,...,
,
,...,
Vậy ta có
r r x x , 0 1
r y 0
r y 1
r p
l
r p
(
)
(
) ≥
.
Định lý 3.18:
Thuật toán Gomory kết thúc sau một số hữu hạn các bước lặp.
Chứng minh:
r
x
Phản chứng. Giả sử thuật toán có vô hạn các bước lặp. Theo bổ đề 3.15 ta có dãy vô
≥
r
là giảm từ vựng. hạn { } 0
Ta chứng minh các kết quả sau:
( )1
r x 0
≥ r r 0
là dãy hằng. + Tồn tại 0r để { }
r x k
kr sao cho { }
≥ r r k
+ Nếu với mỗi k m< tồn tại là dãy hằng thì tồn tại mr để
( )2
{
} r x m r r ≥ m
cũng là dãy hằng.
=
=
r
max
:
k
0,
m
Chứng minh ( )2 :
x k
{ r k
} − . Ta có { }r 1
≥ r r
r
x
là dãy hằng với mọi k m< và do dãy Đặt
}r x m r r ≥
≥
là dãy giảm. là giảm từ vựng giảm nên {
{ } 0
r
} r x m r r ≥ m
=
:
i
0,
n r ,
r ix
là dãy hằng. Khi ấy Phản chứng. Giả sử ngược lại không tồn tại mr để {
} ∈ bị
}vr x m v
=
a
dãy{ chứa dãy con giảm ngặt { . Theo bổ đề 3.16, tập hợp {
lim vr x m
}r x m r r ≥ chặn dưới. Vậy {
→+∞
}vr x m v
}vr x m v
v
=
a
a> với mọi v
là dãy giảm và bị chặn dưới nên hội tụ. Đặt là . Do {
+∈ . Lại do
lim vr x m
0v
vr mx
→+∞
v
nên tồn tại dãy giảm ngặt và hội tụ về a nên
<
<
1,
+ ∀ ≥ . v
[ ] a
[ ] a
vr x m
v 0
∉ ∀ ≥ ,
v
sao cho
vr mx
v 0
,...,
,
,
,...,
y
Vậy .
r x v m
l
r v m
r x v 1
r x v 0
r y v 0
r y v 1
(
)
(
. Theo bổ đề 3.17, ta có ) ≥
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
≤
+
≤
+
,
,...,
,
,...,
,
,...,
y
Theo bổ đề 3.15, ta có
r y v 0
r y v 1
r v m
l
r x v 0
r x v 1
r x v m
l
r x v 0
r x v 1
r x v m
(
)
(
)
(
)
.
+ 1
+ 1
+ 1
≥
+
,
,...,
,
,...,
y
,
,...,
Vậy
r x v m
l
r v m
l
r x v m
r x v 0
r x v 1
r y v 0
r y v 1
r x v 0
r x v 1
(
)
(
)
) ≥
.
( Vì { }r x k
≥ r r
là dãy hằng với k m< nên
+ 1
=
,
∀ = k
0,
m
− . 1
r x v 0
r x v 0
+ 1
=
=
,
∀ = k
0,
m
1
− và
r x v 0
r y v 0
r x v 0
1
≥
y
Do đó ta có
r x v m
r v m
r x + v m
≥
<
<
+
.
[ ] a
1vr + > . mx a
r x v m
r x v m
( [ ] [ ] a a
)1
=
( )2 được chứng minh.
( )1 được chứng minh tương tự ( )2 .
k
n∈ 0,
và Điều này vô lý vì
r x k
≥ r r k
=
=
s
max
:
k
0,
k
n∈ 0,
là dãy hằng. Đặt Từ ( )1 và ( )2 , ta có với mỗi đều tồn tại kr sao cho { }
x k
r k
{
} n
≥ r s
≥ r s
r
x
là dãy hằng với mọi là . Ta có { }r . Điều này dẫn đến { }r x
≥
r
là giảm từ vựng. dãy hằng, mâu thuẫn với dãy vô hạn { } 0
Vậy thuật toán Gomory kết thúc sau một số hữu hạn các bước lặp.
3.5.4. Ví dụ
Ví dụ 3.18:
min
≤
−
3 ≥
2
0,
∈ ∀ = ,
1, 2
i
x i
+ → x x 1 2 x x 1 2 + 3 5 x x 1 2 ≥ x i
Giải bài toán
−
max
x 1
− → x 2
+
− 3
= − +
+
2 3
5
i
0,
x x 1 2 x x 1 2 ∈ ∀ = ,
1, 4
x i
= x 0 = x 3 x 4 ≥ x i
1,1,3, 6 và bảng đơn hình xuất phát là l-chuẩn. Vậy điều
Xét bài toán phụ
)
Bài toán phụ có phương án (
)iii
để sử dụng thuật toán Gomory được thỏa. Ta áp dụng thuật toán Gomory để kiện ( )i và (
1x−
2x−
giải bài toán phụ. Ta có bảng đơn hình xuất phát của bài toán phụ:
0x
0 1 1
1x
0 -1 0
2x
0 0 -1
3x
3 1 -1
4x
-5 -2 -3
4x ra khỏi tập các biến cơ sở, đưa vào
2x
1x−
4x−
0x
2 − 5
2 5
1 5
Đưa
1x
2x
1 − 5
2 5
3 5
3x
17 5
8 5
1 − 5
0 -1 0
4x
0 -1 0
x = − ∉ nên ta bổ
0
2 5
−
−
−
−
0
Ta nhận được bảng đơn hình l-chuẩn và chấp nhận được. Vì
(
)
(
)
x ≥ , đưa về dạng 5
x 1
x 4
2 5
2 5
1 5
≥ −
sung thêm lát cắt đúng . Đặt biến phụ
−
−
−
−
(
)
(
)
x 5
x 1
x 4
2 5
2 5
= − −
1 5
đẳng thức
−
+
−
hay
(
)
(
)
x 5
x 1
x 4
3 = − + 5
2 5
1 5
.
1x−
4x−
0x
2 − 5
2 5
1 5
Thêm dòng này vào cuối bảng, ta có bảng đơn hình mới
1x
2x
2 5
1 − 5
3 5
3x
1 − 5
17 5
8 5
-1 0 0
4x
5x
3 − 5
2 5
1 5
0 0 -1
5x ra khỏi tập các biến cơ sở, đưa vào
1x và xóa bỏ dòng cuối
5x−
4x−
Đưa
0x
1x
5 − 2
3 2
1 2
2x
1 − 2
1 − 2
3 2
-1 1 0
3x
1 4 -1
4x
0 0 -1
4x ra khỏi tập các biến cơ sở, đưa vào
2x
5x−
2x−
Đưa
0x
-1 1 0
1x
1 -1 1
2x
0 0 -1
3x
2 1 -2
4x
1 -3 -2
1, 0, 2,1 .
Ta nhận được bảng đơn hình l-chuẩn, chấp nhận được và cột đầu tiên có các thành
)
phần là các số nguyên. Thuật toán kết thúc. Bài toán phụ có phương án tối ưu (
)1, 0 .
Vậy bài toán đã cho có phương án tối ưu (
Chương 4: THUẬT TOÁN NHÁNH CẬNGIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN
Phương pháp nhánh cận ra đời năm 1960 áp dụng cho các bài toán tối ưu rời rạc trên
cơ sở hầu hết các bài toán trên thực tế có tập ràng buộc hữu hạn và như vậy về nguyên tắc
có thể điểm diện tất cả các phương án để chọn ra phương án tối ưu. Như vậy thuật toán
nhánh cận có thể áp dụng cho bài toán quy hoạch tuyến tính nguyên với mô hình bị chặn (
tập ràng buộc của bài toán quy hoạch tuyến tính tương ứng là tập bị chặn). Một câu hỏi đặt
ra là liệu với mô hình không bị chặn thì thuật toán có còn sử dụng được hay không ? Trong
chương này ta sẽ đề cập đến vấn đề đó.
Trong chương này ta sẽ nghiên cứu thuật toán nhánh cận và cơ sở lí luận của nó sử
→
c x ,
max
P
(
n
≥
∈
= Ax b x
,
0,
x
) ′
dụng để giải bài toán quy hoạch tuyến tính nguyên dạng chính tắc:
,A b , vectơ c có các thành
; các ma trận trong đó A là ma trận cấp m n× và rankA m=
phần là các số nguyên.
)P′
→
c x ,
max
P
là bài toán Bài toán quy hoạch tuyến tính tương ứng với (
(
)
≥
= Ax b x
,
0
.
4.1. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính Thuật toán đơn hình đối ngẫu khi có bảng đơn hình xuất phát là chuẩn:
Ý tưởng của thuật toán:
Bắt đầu từ một cơ sở mà bảng đơn hình tương ứng là chuẩn, nếu bảng đơn hình chưa
là chấp nhận được thì ta tiến hành dịch chuyển sang cơ sở mới mà bảng đơn hình ứng với cơ
sở mới cũng là chuẩn cho đến khi gặp bảng đơn hình là chấp nhận được thì dừng. Khi đó
phương án cơ sở ứng với bảng đơn hình cuối là phương án tối ưu .
Thuật toán:
Giả sử tồn tại cơ sở B sao cho bảng đơn hình T ứng với B là chuẩn.
Bước 1
Nếu T là chấp nhận được thì phương án cơ sở ứng với B là phương án tối ưu . Thuật
toán kết thúc.
Ngược lại, ta chuyển sang bước 2.
0,
i
n∈ 1,
Bước 2
≥ ∀ ∈ thì ( j N
)P không có phương án ( vì
ix < và 0
0
ijx
=
+
−
<
x
0
Nếu tồn tại sao cho
)P không có phương án tối ưu .Thuật toán kết thúc.
x i
x i
0
j
x ij
(
)
∑
∈ j N
). Vậy (
=
=
i
min
:
1,
Ngược lại:
x k
x i
0
0
{
} n
j
<
:
,
0
+ Chọn k thỏa .
∈ j N x kj
x l 0 min = x kl
x 0 x kj
. + Chọn l thỏa
kx ra khỏi tập các biến cơ
+ Thực hiện phép biến đổi cơ bản của bảng đơn hình : đưa
lx vào. Quay trở lại bước 1.
sở, đưa
Nhận xét:
+ Trong quá trình sử dụng thuật toán đơn hình đối ngẫu thì bảng đơn hình luôn là
chuẩn và hàm mục tiêu không tăng.
+ Trong trường hợp bảng đơn hình xuất phát không là chuẩn thì có thể tiến hành
thuật toán như thuật toán đơn hình đối ngẫu từ vựng với trường hợp bảng đơn hình xuất
phát không là l-chuẩn [3, tr.77-81].
4.2. Kỹ thuật tái tối ưu hóa
)P có phương án tối ưu. Sử dụng thuật toán đơn hình đối ngẫu tìm phương án
Giả sử (
)P ta thu được bảng đơn hình T là chuẩn và chấp nhận được và cơ sở tương
tối ưu của (
)Q là bài toán (
)P có bổ sung thêm ràng buộc
n
ứng B . Xét bài toán (
a x α i i
≤∑
= 1
i
.
Câu hỏi đặt ra: Liệu có thể thể tận dụng những thông tin đã có khi tìm phương án tối
)P để tìm phương án tối ưu của (
)Q hay không? Trong mục này ta sẽ nghiên cứu
ưu của (
0
vấn đề đó.
nx + ≥ với hệ số hàm mục tiêu bằng 0 , chuyển ràng buộc về
1
Đưa thêm biến phụ
dạng đẳng thức
n
= + α+
1
x n
a x i i
−∑
= 1
i
=
+
−
x
∀ = i
0,
n
.
x i
x i
0
j
x ij
(
) ,
∑
∈ j N
n
n
−
+
−
−
x
nên Do
x n
1
a x i i
0
a x i ij
j
)
(
∑
= 1
= 1
i
∈ j N
i
α+ =
∑ ∑
.
′ =
B
B
Viết dòng trên vào cuối bảng đơn hình T ta thu được bảng đơn hình mới T ′ ứng với
}1
{ + n
cơ sở mới . T là chuẩn nên T ′ cũng là chuẩn. Vậy ta có thể áp dụng thuật
)Q .
toán đơn hình đối ngẫu bắt đầu từ bảng đơn hình T ′ để tìm phương án tối ưu của (
Thủ tục vừa mô tả ở trên được gọi là “ kĩ thuật tái tối ưu hóa” trong quy hoạch tuyến
tính. Kỹ thuật này được áp dụng khi gặp các bài toán quy hoạch tuyến tính với số ràng buộc
tăng dần, giúp tiết kiệm thời gian so với việc giải lại từ đầu bài toán với ràng buộc thêm vào.
4.3. Thuật toán nhánh cận
4.3.1. Điều kiện để sử dụng thuật toán nhánh cận
Điều kiện để sử dụng thuật toán nhánh cận giống như điều kiện để sử dụng thuật toán
( )i Tập các phương án tối ưu của (
)P bị chặn
Gomory tức là cần có điều kiện
và một trong hai điều kiện sau
)ii Hàm mục tiêu bị chặn dưới trên tập các phương án của (
)P ,
(
(
)iii
hoặc
)P có phương án nguyên.
(
4.3.2. Thuật toán nhánh cận
Bước 0:
)P . Nếu
(
)P không có phương án tối ưu thì (
)P′ cũng không có phương án tối ưu. Thuật toán kết
0x . Ta kiểm tra:
Sử dụng thuật toán đơn hình đối ngẫu để tìm phương án tối ưu của (
)P có phương án tối ưu
thúc. Ngược lại, nếu (
0x là phương án nguyên của (
)P thì
0x là phương án tối ưu của (
)P′
+ Nếu . Thuật toán
kết thúc.
0x là không phải là phương án nguyên thì ta tiến hành:
Ω =
+ Ngược lại, nếu
)P′ vào danh mục các bài toán cần xét:
{ (
}P′ )
. - Đưa (
)P′
)P .
- Đặt cận trên của ( là giá trị tối ưu của bài toán quy hoạch tương ứng (
)P′ thì :
c y′ ,
- Nếu biết y′ là một phương án của (
= x 0 :
∗ :x
′= y
( giá trị tốt nhất mà ta biết), • Gán giá trị kỉ lục
( phương án tốt nhất mà ta biết). • Gán phương án kỉ lục
0 :x = −∞ .
1r = .
Ngược lại, gán giá trị kỉ lục
- Chuyển sang bước lặp thứ
( r r ≥ :
)1
Bước lặp thứ
)Q′ là bài toán trong Ω có cận trên lớn nhất.
Q
=
x
+ Nếu Ω ≠ ∅ thì chọn (
)Q .
Q x 1 ,...,
Q x n
(
)
=
k
Đặt là phương án tối ưu của bài toán quy hoạch tương ứng (
{ min : Q i x i
} ∉ .
Đặt
)Q′ thành hai bài toán con (
)
)Q′ có bổ sung thêm
) ( ′ Q′ ,Q 2 1
)1Q′ là (
≥
+
1
Tách ( trong đó (
)Q′ có bổ sung thêm ràng buộc
)2Q′
x k
x k
Q x ≤ k
và (
Q x k
) Q . Ta
ràng buộc . là (
) ( ,Q 1
2
Lần lượt tìm phương án tối ưu của các bài toán quy hoạch tương ứng (
gặp phải các trường hợp:
)iQ không có phương án. Khi đó loại bỏ (
)iQ′ khỏi việc xem xét tiếp theo.
iQ
c x ,
iQx . Khi đó nếu
- (
)iQ có phương án tối ưu nguyên
x> 0
iQ
iQ
∗ = :
x
x
c x ,
thì xác định lại giá trị kỉ - (
= x 0 :
iQx . Trong trường hợp này, đặt cận trên của
và phương án kỉ lục . lục
)iQ có phương án tối ưu không nguyên
iQ
c x ,
(
- (
)iQ′ là
)iQ′ vào danh mục các bài toán cần xét:
Ω = Ω ∪
:
và kết nạp (
{ (
} )
iQ′
.
)Q′ và những bài toán có cận trên nhỏ hơn hay bằng giá trị
1r + .
Loại bỏ khỏi Ω bài toán (
kỉ lục. Chuyển sang bước lặp
)P′ có phương án tối ưu là x∗ và giá trị tối ưu là
0x . Thuật toán kết
- Nếu + Nếu Ω = ∅ , ta xét : 0x > −∞ thì (
thúc.
)P′ không có phương án. Vậy(
)P′ không có phương án tối ưu. Thuật
0x = −∞ thì (
- Nếu
toán kết thúc.
4.3.3. Cơ sở lí luận của thuật toán
rx là giá trị kỉ lục sau khi kết thúc bước lặp thứ r trong thuật toán. Theo cách
0
r
x
Gọi
≥
r
0
là dãy không giảm. Vậy khi thuật toán kết thúc nếu ta thức vận hành thuật toán, dãy { }0
0x thì
≤
1
r
∀ ≥ .
rx 0
x 0,
nhận được giá trị kỉ lục
Định lý 4.1:
)P′ có phương án tối ưu là x∗ và giá trị tối
0x > −∞ thì (
Nếu Ω = ∅ và ta nhận được
0x .
ưu là
Chứng minh:
)P′ là khác rỗng ( x∗ là phương án của (
)P′ ).
Trước hết, tập các phương án của (
)P′
)Q′ bị loại bỏ
Xét x′ là phương án của ( . Khi đó x′ là phương án của bài toán (
(
)Q là bài toán quy hoạch tương ứng với (
)Q′ .Vì (
)Q′ bị loại bỏ nên chỉ có các khả năng
trong một bước lặp r nào đó ( bị loại bỏ nhưng không bị tách thành hai bài toán con). Gọi
sau:
)Q có phương án tối ưu nguyên Qx . Khi đó, ta có
Q
′ ≤
≤
≤
=
c x ,
c x ,
c x∗ ,
+ (
r x 0
x 0
.
)Q có phương án tối ưu không nguyên Qx và cận trên nhỏ hơn hoặc bằng giá trị kỉ
+ (
∗
− 1
Q
≤
≤
=
c x ,
c x ,
lục:
r x 0
x 0
.
Q
′ ≤
≤
=
c x ,
c x ,
c x∗ ,
Do đó
x 0
.
′ ≤
=
c x ,
c x∗ ,
Vậy trong cả hai khả năng , ta đều có
x 0
.
)P′ có phương án tối ưu là x∗ và giá trị tối ưu là
0x .
Điều đó có nghĩa là (
Định lý 4.2:
)P′
0x = −∞ thì (
Nếu Ω = ∅ và ta nhận được không có phương án.
Chứng minh:
)P′ có phương án x′ . Khi đó x′ là phương án của bài toán
(
)Q′ bị loại bỏ trong một bước lặp r nào đó (bị loại bỏ nhưng không bị tách thành hai bài
Phản chứng. Giả sử (
)Q là bài toán quy hoạch tuyến tính tương ứng với (
)Q′ .Vì (
)Q′ bị loại bỏ
toán con). Gọi (
nên chỉ có các khả năng sau:
)Q có phương án tối ưu nguyên Qx . Khi đó, ta có
′ ≤
≤
≤
c x ,
, Q c x
+ (
r x 0
x 0
.
)Q có phương án tối ưu không nguyên Qx và cận trên nhỏ hơn hoặc bằng giá trị kỉ
+ (
≤
, Q c x
lục:
−≤ 1 r x 0
x 0
.
0x > −∞ . Điều này mâu thuẫn với giả thiết
0x = −∞ .
Trong hai khả năng , ta đều có
)P′
0x = −∞ thì (
Vậy nếu không có phương án.
,D D là các tập lồi đa diện không chứa đường thẳng trong
n và D D⊂ . Khi ấy ta
Giả sử
có hai định lý sau
max
c x ,
:
x D∈
Định lý 4.3:
{
}( ) 1
max
c x ,
:
x D∈
Nếu bài toán có phương án tối ưu thì bài toán
{
}( ) 2
cũng có phương án tối ưu nếu tập phương án D khác rỗng.
Chứng minh:
0x . Khi ấy, ta có
≤
c x ,
,
∀ ∈ x D .
x 0
Giả sử bài toán ( )1 có giá trị tối ưu là
≤
c x ,
,
∀ ∈ x D .
x 0
Mà do D D⊂ nên
,c x bị chặn trên trên D nên bài toán ( )2 có phương án tối ưu
Vậy hàm mục tiêu
nếu D ≠ ∅ .
Nhận xét:
c x ,
:
max
x D∈ có phương
{
}
max
c x ,
:
Nếu bài toán án tối ưu thì bài toán
{
} x D∈
hoặc không có phương án hoặc có phương án tối ưu.
max
c x ,
:
x D∈
Định lý 4.4:
{
}( ) 1
max
c x ,
:
x D∈
Nếu tập các phương án tối ưu của bài toán khác rỗng và bị chặn
{
}( ) 2
thì tập các phương án tối ưu của bài toán cũng bị chặn.
Chứng minh:
0x là giá trị tối
n
=
∈
=
:
c x ,
Giả sử tập các phương án tối ưu của bài toán ( )2 không bị chặn. Đặt
{ D D x
}0 x
ưu của bài toán ( )2 . Khi đó tập các phương án tối ưu của nó
∗ +
=
0.
,c x
v
x D∗ ∈ . Ta có
cũng là tập lồi đa diện. Vì D không bị chặn nên D có phương vô tận v . Lấy cố định
c v = Do v là phương vô tận của D và D D⊂ nên v ,
x 0
nên
vλ∗ +
x
0λ> . Điều này mâu thuẫn với tập các
cũng là phương vô tận của D . Lấy cố định x∗ là phương án tối ưu của bài toán ( )1 . Khi đó
là phương án tối ưu của bài toán ( )1 với mọi
phương án tối ưu của bài toán ( )1 bị chặn.
Vậy nếu tập các phương án tối ưu của bài toán ( )1 khác rỗng và bị chặn thì tập các
phương án tối ưu của bài toán ( )2 cũng bị chặn.
Định lý 4.5:
)P bị chặn thì thuật toán nhánh cận kết thúc sau một số
Nếu tập các phương án của (
hữu hạn các bước lặp.
Chứng minh:
)1rP +′ nhận được từ (
{ các bài toán (
′ P r
≥
} 1 )
r
bị chia tách sao cho ( Giả sử thuật toán có vô hạn các bước lặp. Vậy trong thuật toán sẽ tồn tại dãy vô hạn )rP′ sau một số bước lặp nào
đó.
)P′
chỉ có hữu hạn thành phần ( n thành phần) nên không Vì một phương án của (
)rP′ bị chia tách do thành phần thứ nhất không nguyên với mọi
1r ≥ .
P r
=
x
giảm tổng quát ta giả sử (
)rP ( bài toán quy hoạch tương ứng với
P x r n
P 1 ,..., x r
(
)
(
)P bị chặn nên tồn tại
[
]
)rP′ ). Do tập các phương án của (
x 1
∈ = A 1
a b 1, 1
1,a b ∈ sao cho
1
Đặt là phương án tối ưu của (
)
A∈ với mọi phương án (
)
x 1,...,
x n
)1P . Giả sử
x 1,...,
x n
x 1
r
(
)rP′ sau một số bước lặp nào đó nên
)rP . Do (
)1rP +′ nhận được từ (
x 1
rP x ≤ 1
hoặc
≥
+
1
của với mọi phương án ( của (
)
)
x n
x 1,...,
x n
x 1,...,
)1rP +
x 1
rP x 1
∈
=
+
\
là phương án của với mọi phương án ( của ( và nếu (
(
)1rP +
)rP . Vậy
A r
A r
x 1
+ 1
P x r 1
P x r 1
(
) 1
,
với mọi phương thì cũng là phương án của (
)
r
x n
x 1,...,
)1rP +
rA ≥ . Do
1,a b ∈ nên với cách xây dựng các tập hợp rA như vậy ta thấy rA có các điểm biên đều là các
1
án ( của ( . Như vậy ta đã xây dựng được dãy vô hạn các tập hợp { } 1
A r
P x r 1
P x r 1
r
rP x 1
A∈ và 1
rPx ∉ , ta có (
) + ⊂ 1
=
−
+
=
− ∀ ≥
1,
r
1
( µ
)
( µ
)
( µ
)
A r
A r
A r
+ 1
P x r 1
P x r 1
(
) 1
,
số nguyên. Vậy từ . Vậy, ta có
( µ
, )
)Aµ là độ đo Lebesgue của A .
(
trong đó
− + =
−
1
1
1
r
r
r
+ − ∀ ≥ . ,
( µ
)
( µ=
)1 A
b 1
a 1
rA
Điều này dẫn đến
= −∞ (vô lý vì độ đo Lebesgue là độ đo dương).
)
( Aµ r
lim →+∞ r
Do đó
Vậy thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp.
Định lý 4.6:
Nếu các điều kiện giống như các điều kiện để sử dụng thuật toán Gomory được thỏa
thì thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp.
Chứng minh:
)1rP +′ nhận được từ (
{ các bài toán (
rn sao cho (
′ P r
≥
} 1 )
r
bị chia tách tại bước lặp Giả sử thuật toán có vô hạn các bước lặp. Vậy trong thuật toán sẽ tồn tại dãy vô hạn )rP′ sau một số
bước lặp nào đó.
)P′
chỉ có hữu hạn thành phần ( n thành phần) nên không Vì một phương án của (
)rP′ bị chia tách do thành phần thứ nhất không nguyên với mọi
1r ≥ .
giảm tổng quát ta giả sử (
rPx là giá trị tối ưu của (
)rP ( bài toán quy hoạch tuyến tính tương ứng với (
)rP′ ).
0
rP
Đặt
)ii được thỏa tức là hàm
}0 x
≥ 1
r
bị chặn dưới. Thậy vậy, nếu điều kiện ( Ta chứng minh dãy{
)P thì ta có điều phải chứng minh còn
mục tiêu bị chặn dưới trên tập các phương án của (
)iii được thỏa tức là (
)P có phương án nguyên x′ thì ta xét:
> −∞ thì theo cách thức tiến
nếu điều kiện (
x 0
rn x= 0 0
0rn nào đó giá trị kỉ lục
+ Nếu tại một bước lặp
rP
r
Px
r
hành thuật toán ta loại bỏ tất cả những bài toán trong danh mục các bài toán cần xét mà có
0
n x≥ r 0 0
0
r> . Vậy dãy{
}0 x
≥ 1
r
cận trên nhỏ hơn hay bằng giá trị kỉ lục nên với mọi bị chặn
dưới.
= −∞ tại mọi bước lặp
x 0
rn x= 0 0
rn . Khi ấy x′ phải là phương
+ Ngược lại, giá trị kỉ lục
rn nào
án của một bài toán nào đó trong danh mục các bài toán cần xét tại bất kỳ bước lặp
rPx là cận trên lớn nhất trong các cận trên của các bài toán trong danh mục các bài toán
0
≥
rPx
c x′ ,
và vì
1r ≥ .
0
rn nên
rP
cần xét ở bước lặp với mọi
}0 x
≥ 1
r
rP
P r
=
α
=
inf
x
bị chặn dưới. Vậy trong mọi trường hợp ta đều có dãy{
(
)rP . Vì
P x r n
P x 1 ,..., r
{
}0 x
(
)
≥ 1
r
n
rP
P r
x
:
c x ,
và là phương án tối ưu của Đặt
)1P . Vì
1D là tập các phương án của (
P x= r 0
{ ⊂ ∈ x
} ≥ c x α ,
}
≥ 1
r
(
)rP nhận được từ (
)1P sau một số bước lặp nên phương án của (
)rP thì cũng là phương án
rP
x
. Đặt nên ta có {
1D . Vậy ta có
)1P . Do đó dãy {
}
≥ r r 1
n
rP
⊂
∈
x
x
:
nằm trong của (
= D D 1
1
{
} ≥ c x α ,
{
}
≥ r r 1
.
1D là tập bị chặn. Thật vậy giả sử ngược lại
1D
1D không bị chặn thì
,c x bị chặn trên trên
Ta chứng minh
)1P có phương án tối ưu nên hàm mục tiêu
D⊂ nên hàm mục tiêu
,c x cũng bị chặn trên trên
D 1
1
1D . Do vậy, ta phải có
1D . Mà
n
0
0
0
:
c v ≤ . Lại có ,
có phương vô tận v . Vì (
c v ≥ . Vậy phải có ,
c v = . Do v là ,
D 1
{ ⊂ ∈ x
} c x α ≥ ,
1Px
vλ+
nên
1D và
D 1
1
D⊂ nên v cũng là phương vô tận của 1D . Vậy ta có
là phương vô tận của
0λ> .Điều này dẫn đến (
)1P với mọi
)1P có tập các phương án tối ưu
phương án tối ưu của (
)P bị
không bị chặn. Ta gặp mâu thuẫn vì theo điều kiện ( )i , tập các phương án tối ưu của (
)1P bị chặn. Vậy
1D là tập bị
chặn nên do định lý 4.4 ta có tập các phương án tối ưu của (
chặn.
rP
x
)1rP +′ nhận được từ (
)rP′ sau một
≥
} 1
r
là dãy không bị chặn. Do ( Ta chứng minh dãy {
)
x 1,...,
x n
)1rP +
x 1
rP x ≤ 1
với mọi phương án (
≤
≥
+
1
hoặc số bước lặp nào đó nên của (
)
x 1
rP 1 1
x 1,...,
x n
)1rP +
x 1
rP x 1
x
với
∈
0;
với mọi phương án ( của ( . Nếu tồn tại 1r sao cho
)
x 1
rP x 1 1
x 1,...,
x n
)
1 1rP +
với mọi phương án
. Khi đó, ta có mọi phương án ( của (
(
)
x 1,...,
x n
)
1 1rP +
≥
+
1
1r ≥ ,
. Tới đây hoàn toàn tương tự chứng minh trong trường hợp tập các của (
)P bị chặn ta dẫn đến điều vô lý. Vậy ta có với mọi
x 1
rP x 1
+ 1
≥
+
1
với phương án của (
1r ≥ . Điều này dẫn đến
)
x 1,...,
x n
)1rP +
P x r 1
P x r 1
rP
rP
x
. Do đó với mọi mọi phương án ( của (
}1 x
≥
≥ 1
} 1
r
r
rP
rP
x
x
là dãy không bị chặn. dãy số { không bị chặn. Vậy dãy {
D 1
1D không bị chặn. Điều này
}
⊂ và dãy {
≥
≥ 1
} 1
r
r
không bị chặn nên Ta có {
1D là tập bị chặn.
mâu thuẫn với
Vậy thuật toán nhánh cận kết thúc sau một số hữu hạn các bước lặp.
4.3.4. Ví dụ
Ví dụ 4.7:
Ta xét lại ví dụ đã minh họa cho phương pháp cắt Gomory. Bây giờ ta giải bài toán
đó bằng phương pháp nhánh cận.
min
≤
−
Giải bài toán
3 ≥
2
0,
∈ ∀ = ,
1, 2
i
x i
+ → x x 2 1 x x 2 1 + 3 5 x x 2 1 ≥ x i
.
−
max
x 1
− → x 2
+
− 3
= − +
+
2 3
5
0,
x x 1 2 x x 1 2 ∈ ∀ = ,
1, 4
i
x i
= x 0 = x 3 x 4 ≥ x i
1,1,3, 6 và bảng đơn hình xuất phát là l-chuẩn. Vậy điều
Xét bài toán phụ
)
Bài toán phụ có phương án (
)iii và ( )i được thỏa. Ta áp dụng thuật toán nhánh cận để giải bài toán phụ:
kiện (
)P′
0,
, 0
. Sử dụng phương pháp đơn hình đối ngẫu xác định phương án + Đặt bài toán phụ là (
)P′ là
2 17 , 5 5
Ω = :
P′
. Thành phần thứ tối ưu của bài toán quy hoạch tuyến tính tương ứng với (
{ (
x∗ = :
- Danh mục các bài toán cần xét hai của phương án tối ưu chưa nguyên nên ta gán: } )
( 1,1,3, 6
)
2
- Phương án kỉ lục
x = − . 0 :
- Giá trị kỉ lục
1r = .
Chuyển qua bước lặp
1r = :
+ Bước lặp
)P′
)
)P′
)1P′ là (
) ( ′ P′ ,P 2 1
có bổ sung thêm ràng Chia ( thành hai bài toán con ( trong đó (
x ≤ và ( 0
)P′
)2P′ là (
2
x ≥ . 2 1
, 0,
, 0
buộc có bổ sung thêm ràng buộc
)1P′ tìm được phương án tối ưu chưa nguyên
2 3
7 3
và giá trị tối ưu tương Giải (
2 − . 3
0,1, 4,3 và giá trị tối ưu tương ứng là
ứng là
)
)2P′
0,1, 4,3
x∗ = :
Giải ( tìm được phương án tối ưu nguyên (
( − > 1
(
)
)0 x
1
x = − . 0 :
Ω = :
. Xác định lại phương án kỉ lục và giá trị kỉ lục
{ (
}1 ) P′
r = . 2
Gán: Danh mục các bài toán cần xét
Chuyển qua bước lặp
r = : 2
+ Bước lặp
)
)P′
)3P′ là (
)1P′ thành hai bài toán con (
) ( ′ P′ ,P 4 3
có bổ sung thêm ràng trong đó ( Chia (
x ≤ và ( 0
)P′
)4P′ là (
1
x ≥ . 1 1
buộc có bổ sung thêm ràng buộc
)3P′ . (
)3P′ không có phương án.
1, 0, 2,1 và giá trị tối ưu tương ứng là
Giải (
)
)4P′
Giải ( tìm được phương án tối ưu nguyên (
( − = 1
)0 x
.
:Ω = ∅ .
1
Gán:
x = − < +∞ nên bài toán phụ (
)P′ có phương án tối ưu là
0
x∗ = :
0,1, 4,3
(
)
Kết luận: Vì giá trị kỉ lục
)0,1 .
. Vậy bài toán đã cho có phương án tối ưu là (
Nếu bài toán quy hoạch tuyến tính không thỏa điều kiện Gomory thì khi tiến hành
thuật toán nhánh cận có thể xảy ra vô hạn các bước lặp ( thuật toán không thể kết thúc). Các
ví dụ sau sẽ đề cập đến vấn đề này.
Ví dụ 4.8:
max =
2
1
i
0,
x 2 ∈ ∀ = ,
1, 2
x i
x i
− → x 1 − x 2 1 ≥
, 0
Giải bài toán
1 2
Bài toán quy hoạch tuyến tính tương ứng có phương án tối ưu duy nhất nên bài
,x x nào thỏa điều kiện 1
2
2
1
= nên tập phương án của bài toán là tập rỗng và hàm mục tiêu
x 1
x− 2 2
1x− không bị chặn
toán thỏa điều kiện (i). Vì không có cặp số nguyên
+
1
2
→ −∞ khi
dưới trên tập các phương án của bài toán quy hoạch tuyến tính tương ứng
2x → +∞ ). Vậy bài toán không thỏa điều kiện (ii) và (iii) nên bài
− = − x 1
x 2 2
(
toán không thỏa điều kiện Gomory.
Thuật toán nhánh cận khi áp dụng cho bài toán có vô hạn các bước lặp. Ở mỗi bước
∉
lặp thứ r có đúng 2 bài toán đươc xem xét: một bài toán có tập phương án rỗng, bài toán còn
2 .
r r , 2
+ 1 2
lại có phương án tối ưu
Ví dụ 4.9:
max +
=
1
x 3
− → x 2 − x 2 2 = 1
x 4
0,
∈ ∀ = ,
i
1, 4
x i
x 1 x 2 1 − x 1 ≥ x i
1,1, 0, 0 . Vậy bài toán thỏa điều kiện (iii). Tuy nhiên tập các
Giải bài toán
)
−
=
≥
,
0
Bài toán có phương án (
) , 0, 0 :
x x , 1 2
x 1
x 2
x 2
1 2
(
phương án tối ưu của bài toán quy hoạch tương ứng là tập
không bị chặn nên bài toán không thỏa điều kiện (i). Vậy bài toán không thỏa điều kiện
Gomory.
Thuật toán nhánh cận khi áp dụng cho bài toán có vô hạn các bước lặp. Ở mỗi bước
lặp thứ r có đúng 2 bài toán được xem xét: một bài toán có tập phương án rỗng ( nếu r lẻ)
, 0, 0
r r , 2 2
∉
, 0, 0
hoặc có phương án tối ưu nguyên ứng với giá trị tối ưu là 0 ( nếu r chẵn) , bài
4 .
r r , 2
+ 1 2
toán còn lại có phương án tối ưu
Kết luận
Luận văn đã trình bày chi tiết một số kết quả đã có của quy hoạch tuyến tính nguyên
và cũng thu được một số kết quả mới trong việc nghiên cứu quy hoạch nguyên với mô hình
tuyến tính bất kỳ.
Bài toán quy hoạch nguyên với mô hình tuyến tính bất kỳ chưa được giải quyết một
cách trọn vẹn. Như các ví dụ 4.8,4.9 cho thấy thuật toán nhánh cận đã khảo sát không thể
giải quyết các bài toán như vậy. Điều này đòi hỏi phải có sự cải tiến thuật toán đó hoặc
nghiên cứu một thuật toán hoàn toàn mới. Đó là vấn đề mà tác giả sẽ tiếp tục nghiên cứu.
Tài liệu tham khảo
[1] R. Tyrrell Rockafellar, Convex analysis .
[2] Bùi Thế Tâm (2008), Quy hoạch rời rạc (Bài giảng cao học), Hà Nội.
[3] Nguyễn Đức Nghĩa (1998), Tối ưu hóa ( Quy hoạch tuyến tính và rời rạc),
Nhà xuất bản Giáo dục.
[4] Hoàng Tụy (1968), Lý thuyết quy hoạch, Nhà xuất bản Khoa học.
![Quyển ghi Xác suất và Thống kê [chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251030/anh26012006/135x160/68811762164229.jpg)
