Bài giảng: Tài liệu tối ưu hóa
Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính giá trị của hàm ()fx trên tất cả các phương án của miền ràng buộc sau đó so sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong trường hợp tổng quát (chẳng hạn tập là không đếm được). Vì vậy chúng ta phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được......
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
-----o0o-----
Bài giảng môn
TỐI ƯU HÓA
THÂN QUANG KHOÁT
Thái nguyên - 2007
Thân Quang Khoát
MỤC LỤC
Chương 1. MỞ ĐẦU......................................................................................................3
§1. ĐỐI TƯỢNG NGHIÊN CỨU ...............................................................................3
1.1. Bài toán tối ưu tổng quát...................................................................................3
1.2. Phân loại bài toán ..............................................................................................3
1.3. Một số mô hình thực tế .....................................................................................4
§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ..........................................................6
2.1. Dạng tổng quát ..................................................................................................6
2.2. Dạng chuẩn tắc..................................................................................................7
2.3. Dạng chính tắc...................................................................................................7
§3. MỘT SỐ KIẾN THỨC BỔ TRỢ ..........................................................................9
3.1. Tập hợp lồi và điểm cực biên............................................................................9
3.2. Đa diện lồi (polytope) .....................................................................................10
§4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN ........................................11
QUY HOẠCH TUYẾN TÍNH ............................................................................11
4.1. Phương án cực biên và phương án cực biên tối ưu.........................................11
4.2. Điều kiện cần và đủ để một phương án là cực biên ........................................13
4.3. Cơ sở của một phương án cực biên.................................................................15
Chương 2. THUẬT TOÁN ĐƠN HÌNH....................................................................17
§1. MỞ ĐẦU .............................................................................................................17
1.1. Bài toán ...........................................................................................................17
1.2. Phương pháp Hình Học...................................................................................17
§2. THUẬT TOÁN ĐƠN HÌNH ...............................................................................19
2.1. Tư tưởng của thuật toán đơn hình ...................................................................19
2.2. Công thức số gia hàm mục tiêu - dấu hiệu tối ưu ...........................................20
2.3. Tìm phương án cực biên tốt hơn - Công thức đổi cơ sở .................................21
2.4. Thuật toán đơn hình (Simplex method) ..........................................................23
2.5. Bảng đơn hình .................................................................................................24
§3. TÍNH HỮU HẠN CỦA THUẬT TOÁN ĐƠN HÌNH .......................................28
3.1. Trường hợp bài toán không suy biến ..............................................................28
3.2. Trường hợp bài toán suy biến .........................................................................28
§4. PHƯƠNG PHÁP HAI PHA ................................................................................31
4.1. Vấn đề .............................................................................................................31
4.2. Phương pháp hai pha giải bài toán QHTT ......................................................32
Bộ môn Khoa Học Cơ Bản 1
Bài Giảng môn Tối Ưu Hoá
4.3. Một số ví dụ ....................................................................................................34
§5. PHƯƠNG PHÁP ĐÁNH THUẾ.........................................................................36
§6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ...................................41
6.1. Bài toán đối ngẫu ............................................................................................41
6.2. Các định lý đối ngẫu .......................................................................................42
6.3. Một số ứng dụng của lý thuyết đối ngẫu ........................................................44
6.4. Thuật toán đơn hình đối ngẫu .........................................................................46
Chương 3. TỐI ƯU HOÁ RỜI RẠC .........................................................................56
§1. BÀI TOÁN TỐI ƯU HOÁ RỜI RẠC.................................................................56
1.1. Mở đầu ............................................................................................................56
1.2. Một số bài toán tối ưu hoá rời rạc tiêu biểu....................................................56
§2. PHƯƠNG PHÁP CẮT GOMORY GIẢI BÀI TOÁN QHTT NGUYÊN ..........58
2.1. Tư tưởng chung của phương pháp cắt ............................................................58
2.2. Phương pháp cắt Gomory cho bài toán QHTT nguyên hoàn toàn .................59
2.3. Phương pháp cắt Gomory cho bài toán QHTT nguyên bộ phận ....................64
§3. PHƯƠNG PHÁP NHÁNH CẬN ........................................................................65
3.1. Sơ đồ tổng quát ...............................................................................................65
3.2. Thuật toán nhánh cận Land-Doig giải bài toán QHTT nguyên ......................66
3.3. Một số ví dụ ....................................................................................................68
§4. BÀI TOÁN CÁI TÚI...........................................................................................72
4.1. Đưa bài toán QHTT Nguyên về bài toán cái túi .............................................72
4.2. Phương pháp Quy hoạch động giải bài toán cái túi ........................................74
Tài liệu tham khảo.......................................................................................................77
Khoa Công nghệ thông tin - ĐHTN 2
Thân Quang Khoát
Chương 1. MỞ ĐẦU
§1. ĐỐI TƯỢNG NGHIÊN CỨU
1.1. Bài toán tối ưu tổng quát
Bài toán tối ưu tổng quát có dạng như sau:
f (x ) → min (max)
⎧gi(x ) ≥bi , i = 1,m1
⎪
⎪
⎪
⎪g (x ) ≤b , j = m +1,m
⎪ j
⎪ j 1 2
⎨
⎪gk (x ) = bk , k = m2 +1,m
⎪
⎪
⎪
⎪x ∈ X ⊂ℜn
⎪
⎪
⎩
Trong đó f (x ) được gọi là hàm mục tiêu; gi(x ), i = 1,m được gọi là các
hàm ràng buộc. Mỗi một đẳng thức hay bất đẳng thức được gọi là một ràng
buộc. Gọi
⎧
⎪ g (x ) ≥bi,i = 1,m1; g j (x ) ≤bj, j = m1 +1,m2⎫
⎪
D =⎨⎪x ∈ℜn i ⎪
⎬
⎪
⎪ gk (x ) = bk,k = m2 +1,m; x ∈ X ⎪
⎪
⎪
⎩ ⎪
⎭
D được gọi là miền ràng buộc (hay miền chấp nhận được). Mỗi một vectơ
x = (x 1, x 2, ..., x n ) ∈ D được gọi là một phương án của bài toán (hay lời giải chấp
nhận được).
Định nghĩa: Phương án x * ∈ D được gọi là phương án tối ưu của bài toán nếu
thoả mãn điều kiện sau
f (x *) ≤ f (x ) , ∀x ∈ D (®èi víi bµi to¸n t×m Min)
f (x *) ≥ f (x ) , ∀x ∈ D (®èi víi bµi to¸n t×m Max)
khi đó giá trị f (x *) được gọi là giá trị tối ưu.
1.2. Phân loại bài toán
Chúng ta thấy rằng, một cách hiển nhiên nhất để giải bài toán đặt ra là: Tính
giá trị của hàm f (x ) trên tất cả các phương án của miền ràng buộc sau đó so
sánh các giá trị của hàm mục tiêu thu được để tìm ra phương án tối ưu. Tuy
Bộ môn Khoa Học Cơ Bản 3
Bài Giảng môn Tối Ưu Hoá
nhiên cách làm này là rất khó hoặc đúng hơn là không thể làm được trong
trường hợp tổng quát (chẳng hạn tập D là không đếm được). Vì vậy chúng ta
phải phân tách nhỏ ra bằng cách thêm một số điều kiện nào đó để được các bài
toán “dễ giải”. Người ta đã phân ra một số loại bài toán như sau:
+ Quy hoạch tuyến tính
+ Quy hoạch lồi.
+ Quy hoạch phi tuyến.
+ Quy hoạch toàn phương.
+ Quy hoạch rời rạc.
+ Quy hoạch nguyên.
1.3. Một số mô hình thực tế
Ta sẽ xem xét một số bài toán trong thực tế đưa đến bài toán tối ưu hoá và
mô mình toán học tương ứng của nó.
1.3.1. Bài toán lập kế hoạch sản xuất cho một nhà máy
Một nhà máy có khả năng sản xuất n loại sản phẩm. Để sản xuất n loại
sản phẩm này thì cần m loại nguyên liệu. Biết:
aij - lượng nguyên liệu loại i cần thiết để sản xuất một đơn vị sản phẩm loại j
bi - lượng dự trữ nguyên liệu loại i
c j - tiền lãi từ việc bán một đơn vị sản phẩm loại j
i = 1,m , j = 1,n
Hãy xây dựng kế hoạch sản xuất sao cho nhà máy thu được tổng lợi nhuận
là nhiều nhất.
Gọi x j là lượng sản phẩm loại j mà nhà máy sẽ sản xuất, rõ ràng ta có
x j ≥ 0 . Kế hoạch sản xuất của nhà máy sẽ là véctơ x = (x 1, x 2, ..., x n ) . Đại lượng
n
∑ j =1aijx j là tổng chi phí nguyên liệu loại i theo kế hoạch sản xuất x , theo giả
n
thiết ta có: ∑ j =1aijx j ≤bi
Khoa Công nghệ thông tin - ĐHTN 4
Thân Quang Khoát
Tổng lợi nhuận thu được theo kế hoạch sản xuất x sẽ là ∑n=1c jx j . Như vậy
j
yêu cầu của bài toán này đưa về mô hình toán học như sau:
f (x ) = ∑n=1c jx j → Max
j
⎧∑n=1aijx j ≤bi , i = 1,m
⎪ j
⎪
⎨
⎪x j ≥ 0 , j = 1,n
⎪
⎪
⎩
Mô hình thu được chính là một bài toán quy hoạch tuyến tính.
1.3.2. Bài toán cái túi
Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b .
Có n loại đồ vật có thể đem theo. Đồ vật thứ j có trọng lượng là a j và giá trị
sử dụng là c j (j = 1,n) . Hỏi rằng nhà thám hiểm cần lấy các loại đồ vật nào và
số lượng bao nhiêu để cho tổng giá trị sử dụng của các đồ vật mang theo là
nhiều nhất ?
Gọi x j (j = 1,n) là số lượng đồ vật loại j mà nhà thám hiểm sẽ đem theo.
Khi đó tổng giá trị của các đồ vật đó là ∑n=1c jx j , tổng trọng lượng của chúng là
j
n n
∑ j =1a jx j . Từ giả thiết ta có ∑ j =1a jx j ≤b . Như vậy yêu cầu của bài toán sẽ đưa
về việc giải bài toán sau:
n
∑ j =1c jx j → max
⎧∑n=1a jx j ≤b
⎪ j
⎪
⎨
⎪x j ≥ 0 vµ nguyªn (j = 1,n)
⎪
⎩
Đây lại là một bài toán quy hoạch tuyến tính Nguyên.
1.3.3. Bài toán vận tải
Có m kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho thứ i là
ai (i = 1,m) . Có n địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở
điểm j là bj (j = 1,n) . Biết cij là cước phí vận chuyển một đơn vị hàng hoá từ
kho thứ i đến điểm tiêu thụ thứ j . Hãy lập kế hoạch vận chuyển hàng hoá từ
các kho đến các điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất.
Ký hiệu x ij là lượng vận chuyển từ kho i đến điểm tiêu thụ thứ j , khi đó:
Bộ môn Khoa Học Cơ Bản 5
Bài Giảng môn Tối Ưu Hoá
m n
∑ ∑ cijx ij là tổng chi phí vận chuyển
i =1 j =1
n
∑ x ij là lượng hàng vận chuyển từ kho thứ i
j =1
m
∑ x ij là lượng hàng vận chuyển đến điểm tiêu thụ thứ j
i =1
khi đó bài toán lập kế hoạch trên có thể đưa về mô hình toán học như sau:
m n
∑ ∑ cijx ij → Min
i =1 j =1
⎧∑n=1 x ij = ai
⎪ j
⎪
⎪ n
⎪∑ x ij =bj
⎨ j =1
⎪
⎪
⎪x ij ≥ 0, i = 1,m, j = 1,n
⎪
⎪
⎩
Đây chính là một bài toán Quy hoạch tuyến tính.
§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
2.1. Dạng tổng quát
Tìm véctơ x = (x 1, x 2, ..., x n )t ∈ ℜn sao cho:
n
f (x ) = ∑ c jx j → Min (Max )
j =1
với các điều kiện:
⎧∑n=1aijx j ≥bi , i = 1,m1
⎪ j
⎪
⎪ n
⎪
⎪∑ j =1a pjx j ≤bp , p = m1 +1,m2
⎪
⎪ n
⎪
⎪∑ j =1akjx j =bk , k = m2 +1,m
⎪
D =⎪
⎨
⎪x j ≥ 0, j = 1,n1
⎪
⎪
⎪
⎪x j ≤ 0, j = n1 +1,n2
⎪
⎪
⎪
⎪x tù do , j = n +1,n
⎪ j
⎪
⎩ 2
Dễ thấy rằng:
1) f (x ) → min ⇔ − f (x ) → max
Khoa Công nghệ thông tin - ĐHTN 6
Thân Quang Khoát
n n
2) ∑ aijx j ≥bi ⇔ ∑ (−aij )x j ≤−bi
j =1 j =1
n
⎧∑ aijx j ≥bi
⎪
⎪j =1
⎪
n
3) ∑ aijx j =bi ⇔ ⎪
⎨n
j =1 ⎪∑ a x ≤b
⎪ ij j i
⎪j =1
⎪
⎩
n n
4) ∑ aijx j ≥bi ⇔ ∑ aijx j −x n +i =bi , (x n +i ≥ 0)
j =1 j =1
n n
5) ∑ aijx j ≤bi ⇔ ∑ aijx j + x n +i =bi , (x n +i ≥ 0)
j =1 j =1
các biến x n +i được gọi là các biến bù.
6) Một biến x j không ràng buộc về dấu (tự do) có thể được thay bằng hiệu
hai biến không âm:
x j = x j −x j Víi x j ≥ 0, x j ≥ 0
Từ các nhận xét trên ta thấy rằng bất kỳ một bài toán quy hoạch tuyến tính
nào cũng có thể đưa về một trong hai dạng sau đây:
2.2. Dạng chuẩn tắc
n
f (x ) = ∑ c jx j → Min
j =1
n
⎧∑ aijx j ≥bi , i = 1,m
⎪
⎪j =1
⎪
⎨
⎪x ≥ 0 , j = 1,n
⎪ j
⎪
⎩
Hay dưới dạng ma trận
f (x ) = ctx → Min
⎧Ax ≥b
⎪
⎪
⎨
⎪x ≥ 0
⎪
⎩
trong đó: c, x ∈ℜn, b ∈ℜm, A lµ ma trËn cÊp m×n
2.3. Dạng chính tắc
Bộ môn Khoa Học Cơ Bản 7
Bài Giảng môn Tối Ưu Hoá
n
f (x ) = ∑ c jx j → Min
j =1
n
⎧∑ aijx j = bi , i = 1,m
⎪
⎪j =1
⎪
⎨
⎪x ≥ 0 , j = 1,n
⎪ j
⎪
⎩
Hay dưới dạng ma trận
f (x ) = ctx → Min
⎧Ax =b
⎪
⎪
⎨
⎪x ≥ 0
⎪
⎩
Ví dụ: Cho bài toán quy hoạch tuyến tính
f (x ) = 2x 1 − 3x 2 + 4x 3 − 5x 4 → max
⎧ x 1 +x 2
⎪ −x 4 = 6
⎪
⎪
⎪ −2x 2 +9x 3 +3x 4 ≥ 4
⎪
⎨
⎪5x 1 +x 2 −7x 3
⎪ ≤ 2
⎪
⎪x i ≥ 0, i = 1,4
⎪
⎪
⎩
khi đó dạng chính tắc của bài toán sẽ là:
g(x ) =−2x 1 + 3x 2 − 4x 3 + 5x 4 → min
⎧ x 1 +x 2
⎪ −x 4 = 6
⎪
⎪
⎪ −2x 2 +9x 3 +3x 4 −x 5 = 4
⎪
⎨
⎪5x 1 +x 2 −7x 3
⎪ +x 6 = 2
⎪
⎪x i ≥ 0, i = 1,6
⎪
⎪
⎩
dạng chuẩn tắc là:
g(x ) =−2x 1 + 3x 2 − 4x 3 + 5x 4 → min
⎧ x 1 +x 2
⎪ −x 4 ≥ 6
⎪
⎪
⎪
⎪ −2x 2 +9x 3 +3x 4 ≥ 4
⎪
⎪−5x 1 −x 2 +7x 3
⎨ ≥ −2
⎪
⎪ −x 1 −x 2
⎪ +x 4 ≥ −6
⎪
⎪
⎪x i ≥ 0, i = 1,4
⎪
⎩
Khoa Công nghệ thông tin - ĐHTN 8
Thân Quang Khoát
§3. MỘT SỐ KIẾN THỨC BỔ TRỢ
3.1. Tập hợp lồi và điểm cực biên
3.1.1. Tập hợp lồi (convex set)
Đoạn thẳng: cho hai điểm a, b ∈ℜn khi đó đoạn thẳng nối hai điểm đó là tập
hợp điểm có dạng {x ∈ℜ n
x = λa +(1−λ)b, λ ∈[0,1]} . Nếu λ ∈ℜ thì ta sẽ có
đường thẳng đi qua hai điểm a,b .
Tập lồi: Tập C ⊂ℜn được gọi là tập lồi nếu lấy hai điểm bất kỳ x 1, x 2 ∈C thì
đoạn thẳng nối hai điểm này thuộc hoàn toàn trong C .
Hoặc ta có thể phát biểu như sau:
C lµ tËp låi ⇔ ∀x 1, x 2 ∈C , ∀λ ∈ ⎡⎢0; 1⎤⎥ th× x = λx 1 +(1−λ)x 2 ∈C
⎣ ⎦
Các tập lồi
Ví dụ: Trong không gian 2 chiều thì các đa giác, các hình tròn, các hình elip,…
là các tập lồi.
Các siêu phẳng H = {x ∈ℜn ∑n=1cix i = β} cũng là một tập lồi trong ℜn
i
Các nửa không gian H = {x ∈ℜn ∑n=1cix i ≥ β} là các tập lồi trong ℜn
i
Bổ đề: Giao của các tập lồi cũng là một tập lồi.
3.1.2. Điểm cực biên (vertex)
Điểm cực biên: điểm x 0 thuộc tập lồi C được gọi là điểm cực biên của C
nếu nó không là điểm trong của bất kỳ đoạn thẳng nào nối hai điểm khác nhau
thuộc C . Tức là, ∃x 1, x 2 ∈C , x 1 ≠ x 2 : x 0 = αx 1 +(1−α)x 2 với α ∈ ⎡⎢0; 1⎤⎥ .
⎣ ⎦
Ví dụ: C là đa giác lồi trong ℜ2 thì các đỉnh của nó chính là các điểm cực biên,
các điểm khác đều không là điểm cực biên. Tất cả các điểm trên đường tròn là
Bộ môn Khoa Học Cơ Bản 9
Bài Giảng môn Tối Ưu Hoá
điểm cực biên của hình tròn đó.
* Chú ý:
- Cần phân biệt Điểm biên và Điểm Cực biên. Ví dụ các đỉnh của một
tam giác là điểm cực biên, còn các điểm trên các cạnh là các điểm biên.
- Có những tập lồi không có điểm cực biên, chẳng hạn: các nửa không
gian, một mặt phẳng,…
3.2. Đa diện lồi (polytope)
3.2.1. Tổ hợp lồi (convex combinatorial)
Định nghĩa: Một tổ hợp lồi của các điểm x i ∈ℜn (i = 1,m) là điểm x ∈ℜn
có dạng x = α1x 1 + α2x 2 +...+ αmx m trong đó αi ≥ 0 (i = 1,m) và ∑m 1 αi = 1 .
i=
Như vậy nếu ta có 2 điểm A, B thì mọi điểm nằm trên đoạn thẳng nối hai
điểm đó sẽ là tổ hợp lồi của hai điểm A và B. Định lý sau đây sẽ cho ta biết
được một tập khi nào là một tập lồi.
Định lý: Tập C là tập lồi khi và chỉ khi ∀x i ∈C , ∀αi ≥ 0 (i = 1,m) , ∑m 1 αi = 1
i=
thì ∑m 1 αix i ∈C .
i=
Bổ đề: Tập hợp M gồm mọi tổ hợp lồi của hữu hạn các điểm cho trước là một
tập lồi.
3.2.2. Đa diện lồi
Định nghĩa: Tập hợp M gồm mọi tổ hợp lồi của một số hữu hạn điểm cho trước
x 1, x 2,..., x m được gọi là một đa diện lồi sinh bởi hệ điểm đã cho.
Ký hiệu: M = conv {x 1, x 2,..., x m}
Như vậy ta thấy đa diện lồi là một tập hợp lồi. Tuy nhiên không phải tập lồi
nào cũng là đa diện lồi, chẳng hạn hình tròn là tập lồi nhưng không là đa diện
lồi.
Ví dụ: Đoạn thẳng nối hai điểm A và B là một đa diện lồi.
Đa diện lồi sinh bởi 3 điểm A, B, C trên mặt phẳng là một tam giác. Ba
điểm A, B, C là các điểm cực biên của đa diện lồi này.
Định lý: Nếu M là một đa diện lồi thì nó có điểm cực biên. Số điểm cực biên của M
Khoa Công nghệ thông tin - ĐHTN 10
Thân Quang Khoát
là hữu hạn và mọi điểm của M đều là các tổ hợp lồi của các điểm cực biên đó.
Như vậy định lý này cho chúng ta biết được một tính chất quan trọng của
đa diện lồi, đó là số đỉnh cực biên của một đa diện lồi cho trước là hữu hạn.
Về mặt hình học ta thấy, đa diện lồi là một tập lồi và là giao của một số các
nửa không gian đóng trong ℜn . Tuy nhiên điều ngược lại chưa chắc đúng. Vậy
thì làm thế nào để biết được phần giao của các nửa không gian đóng trong ℜn là
một đa diện lồi ?
Hai nhà toán học là Hoàng Tụy và Asmanov sẽ trả lời cho chúng ta bằng
định lý sau đây:
Định lý: Xét tập M = {x ∈ℜn Ax ≥b} trong đó A là ma trận cấp m ×n , b ∈ℜm .
Nếu M ≠ φ và giới nội thì M là một đa diện lồi.
§4. CẤU TRÚC MIỀN RÀNG BUỘC CỦA BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH
4.1. Phương án cực biên và phương án cực biên tối ưu
Không mất tổng quát ta xét bài toán QHTT dạng chính tắc như sau:
f (x ) = c tx → Min
⎧Ax = b
⎪ (I)
⎪
⎨
⎪x ≥ 0
⎪
⎩
Ký hiệu: D = {x ∈ℜn Ax = b, x ≥ 0}
Đặt:
⎛A ⎞ ⎛b ⎞
⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎜ ⎟⎟, b = ⎜−b⎟
⎜−A⎟ E ⎜ ⎟
AE = ⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟⎟
⎜ ⎟
⎝ ⎟
⎜E ⎠ ⎝ ⎟
⎜0 ⎠
khi đó ta có: D = {x ∈ℜn AEx ≥bE }
Phương án cực biên: Phương án x 0 ∈ D được gọi là phương án cực biên của
bài toán (I) nếu x 0 là điểm cực biên của D .
Bộ môn Khoa Học Cơ Bản 11
Bài Giảng môn Tối Ưu Hoá
Phương án cực biên tối ưu: Nếu phương án cực biên x 0 là phương án tối ưu
của bài toán (I) thì x 0 được gọi là phương án cực biên tối ưu của bài toán (I).
Người ta đã chứng minh được định lý sau đây:
Định lý: Xét tập G = {x ∈ℜn Ax ≥b} , Giả sử G ≠ φ . Khi đó G có điểm cực
biên khi và chỉ khi rank(A) = n . Đặc biệt hơn, nếu G ≠ φ thì ∀x ∈G đều có thể
được viết dưới dạng x = ∑m 1 αix i + ∑k=1 β jy j trong đó x i (i = 1,m) là các điểm
i= j
cực biên của G ; αi ≥ 0, ∑im 1 αi = 1, Ay j ≥ 0, β j ≥ 0 (j = 1,k ) .
=
Áp dụng định lý đối với miền ràng buộc D thì ta có: Do rank(AE ) = n nên
theo định lý, nếu D ≠ φ (tức là bài toán (I) có phương án) thì D có đỉnh cực
biên (bài toán (I) có phương án cực biên). Hơn nữa ta có kết quả sau:
Hệ quả: xét miền D = {x ∈ℜn Ax =b, x ≥ 0} , A = (aij )m×n,b ∈ℜm . Khi đó nếu
D ≠ φ thì nó có điểm cực biên và mọi điểm x ∈ D luôn tồn tại biểu diễn
x = ∑ip=1 αix i + ∑k=1 β jy j trong đó x i (i = 1, p) là các điểm cực biên của D ;
j
αi ≥ 0, ∑ip=1 αi = 1, Ay j = 0, β j ≥ 0 (j = 1,k ) .
Chứng minh:
Ta viết lại D dưới dạng D = {x ∈ℜn AE x ≥bE } . Do rank(AE ) = n nên
theo định lý, nếu D ≠ φ thì D có đỉnh cực biên.
Cũng theo định lý thì mọi điểm x ∈ D luôn tồn tại biểu diễn x = ∑ip=1 αix i
+∑k=1 β jy j trong đó x i (i = 1, p) là các điểm cực biên của D ; αi ≥ 0, ∑ip=1 αi = 1 ,
j
AEy j ≥ 0, β j ≥ 0 (j = 1,k ) . Từ AEy j ≥ 0 ta có ngay Ay j ≥ 0, −Ay j ≥ 0 và do đó
Ay j = 0 . Vậy ta có điều phải chứng minh. ■
Bây giờ ta sẽ dùng hệ quả này để chứng minh kết quả sau cho bài toán (I).
Định lý: Nếu bài toán (I) có phương án thì sẽ có phương án cực biên, và nếu
hàm mục tiêu bị chặn dưới trong D thì bài toán sẽ có phương án tối ưu, do đó
có phương án cực biên tối ưu.
Chứng minh:
Rõ ràng theo hệ quả trên ta có: nếu bài toán (I) có phương án thì nó sẽ có
Khoa Công nghệ thông tin - ĐHTN 12
Thân Quang Khoát
phương án cực biên.
Bây giờ ta giả thiết rằng (I) có hàm mục tiêu bị chặn dưới trong D . Khi
đó bài toán (I) sẽ có phương án cực biên tối ưu. Thật vậy:
Theo hệ quả thì mọi phương án x của (I) đều có thể viết dưới dạng:
x = ∑im 1 αix i + ∑k=1 β jy j , trong đó x i (i = 1,m) là các điểm cực biên của D ;
= j
αi ≥ 0, ∑m 1 αi = 1, Ay j = 0, β j ≥ 0 (j = 1,k ) .
i=
Gọi f (x r ) = min{f (x i ), i = 1,m} . Ta sẽ chứng minh rằng x r sẽ là phương án tối
ưu của bài toán (I).
a) Trước hết ta thấy rằng f (y i ) ≥ 0, ∀i = 1,k :
Thật vậy, giả sử tồn tại j 0 mà f (y j0 ) < 0 thì nếu ta lấy β j = 0, ∀j ≠ j 0 còn
β j0 → +∞ thì f (x ) = ∑im 1 αi f (x i )+ β j0 .f (y j0 ) → −∞ . Điều này trái với giả thiết
=
hàm mục tiêu bị chặn dưới trên miền ràng buộc D .
b) ∀x ∈ D thì:
f (x ) = ∑im 1 αi f (x i )+ ∑k=1 β j f (y j )
= j
≥ ∑im 1 αi f (x i )
=
≥ ∑im 1 αi f (x r ) = f (x r )∑im 1 αi = f (x r )
= =
Vậy f (x ) ≥ f (x r ), ∀x ∈ D , hay x r là phương án tối ưu của bài toán (I). Do đó ta
đi đến kết luận của hệ quả này. ■
4.2. Điều kiện cần và đủ để một phương án là cực biên
Xét bài toán QHTT dạng chính tắc (I). Ký hiệu a 1, a 2,..., a n là các véctơ cột
của ma trận ràng buộc
⎛a11 a12 ... a1n ⎞
⎟
⎜
⎜ ⎟
⎜a ⎟
⎜
A = ⎜ 21
⎜
a22 ... a2n ⎟
⎟
⎟
⎟
⎜ ... ...
⎜ ... ... ⎟
⎟
⎜
⎜ ⎟
⎟
⎝am1 am2 ... amn ⎠
Không mất tổng quát ta luôn giả thiết rank(A) = rank {a 1, a 2,..., a n} = m
Bộ môn Khoa Học Cơ Bản 13
Bài Giảng môn Tối Ưu Hoá
(nếu có phương trình nào trong hệ Ax = b là tổ hợp tuyến tính của các phương
trình khác thì ta có thể loại bỏ đi). Khi đó ta có định lý sau:
Định lý: Phương án x 0 ∈ D là một phương án cực biên khi và chỉ khi hệ các
véctơ cột của ma trận A tương ứng với các thành phần dương của x 0 độc lập
tuyến tính.
Ký hiệu: J +(x 0) = {j |x j0 > 0}
Khi đó định lý có thể phát biểu như sau:
x 0 ∈ D là phương án cực biên ⇔ {a j, j ∈J +(x 0)} độc lập tuyến tính.
Chứng minh:
Không mất tổng quát ta có thể giả thiết J (x 0) = {1,2,...,k} (có thể đánh lại
chỉ số các biến nếu cần thiết để thu được điều kiện này).
“Điều kiện cần”: giả thiết x 0 ∈ D là một phương án cực biên của (I).
Giả sử hệ vectơ {a j, j ∈J +(x 0)} = {a 1,a 2,...,a k } phụ thuộc tuyến tính. Khi
đó tồn tại các số z1, z 2,..., z k không đồng thời bằng 0 để z1a 1 +...+ z ka k = θ . Đặt
z = (z1,..., z k,0,...,0)t ∈ℜn . Khi đó ta có: Az = θ
Xét hai vectơ x ' = x 0 −λz và x '' = x 0 +λz . Khi đó Ax ' = Ax '' = Ax 0 = b (do
Az = θ ).
Nếu ta lấy λ đủ bé sao cho x ' ≥ 0, x '' ≥ 0 (luôn lấy được λ vì z ≠ θ ) thì ta có
x ' ∈ D, x '' ∈ D . Mà ta lại có x 0 = 1 x '+ 1 x '' , trái với giả thiết x 0 là phương án
2 2
cực biên của (I). Vậy hệ {a 1,a 2,...,a k } độc lập tuyến tính.
“Điều kiện đủ”: giả thiết hệ {a 1,a 2,...,a k } độc lập tuyến tính.
Giả sử x0 không là phương án cực biên của (I). Khi đó ∃x ′, x ′′ ∈ D, x ′ ≠ x ′′
sao cho x 0 = 1 x ′ + 1 x ′′ . Dễ dàng thấy rằng (n −k ) thành phần cuối cùng của x′
2 2
và x ′′ cũng bằng 0, còn các thành phần khác là không âm. Vậy ta có:
Ax 0 = ∑n=1 x j0a j = ∑k=1 x j0a j = b
j j
Ax ′ = ∑n=1 x ′a j = ∑k=1 x ′a j = b
j j j j
Khoa Công nghệ thông tin - ĐHTN 14
Thân Quang Khoát
Ax ′′ = ∑n=1 x ′′ j = ∑k=1 x ′′ j =b
j ja j ja
k k k
⇒ ∑ j =1 x j0a j = ∑ j =1 x ′a j = ∑ j =1 x ′a j
j j′
nhưng do hệ {a 1,a 2,...,a k } độc lập tuyến tính nên x j0 = x ′ = x ′′, (j = 1,k ) . Mà theo
j j
nhận xét trên thì x j0 = x ′ = x ′′= 0, (j = k +1,n) . Vậy ta có x 0 = x ′ = x ′′ . Điều này
j j
mâu thuẫn với giả thiết x ′ ≠ x ′′ . Do đó x 0 là phương án cực biên. ■
Ví dụ: xét miền D được xác định như sau
⎧3x 1 + x 2 + 2x 3
⎪ =5
⎪
⎪
⎪2x 1 + x 2 + 3x 3
⎪ =5
⎪
⎨2x
⎪ 1 + x 3 + 2x 4 = 9
⎪
⎪
⎪x ≥ 0, i = 1,4
⎪ i
⎪
⎩
Ta thấy x 0 = (1; 0; 1; 3)t là một phương án của D. Có J +(x 0) = {1; 3; 4} và
các véctơ cột {a j | j ∈J +(x 0)} tương ứng là: a 1 = (3, 2, 2)t, a 3 = (2, 3, 1)t, a 4 =
(0, 0, 2)t chúng lập thành hệ độc lập tuyến tính. Vậy x 0 = (1; 0; 1; 3)t là một
phương án cực biên.
Dễ dàng kiểm tra được rằng vectơ x 1 = (0;5;0; 92)t cũng là một phương án
cực biên. Tuy nhiên x = (5 ; 15 ; 5 ; 47)t là một phương án của bài toán, nhưng lại
8 8 8 16
không là phương án cực biên của nó.
4.3. Cơ sở của một phương án cực biên
Giả sử x 0 ∈ D = {x ∈ℜn Ax = b, x ≥ 0} là một phương án cực biên, rank(A) = m ,
Card (J +(x 0)) = k (số thành phần dương của x 0 là k ). Khi đó hệ {a j, j ∈J +(x 0)}
là độc lập tuyến tính, suy ra k ≤ m .
Nếu k < m thì ta luôn có thể bổ xung thêm (m −k ) véctơ cột khác của A
để được một hệ véctơ độc lập tuyến tính cực đại gồm đủ m véctơ, nghĩa là ta
tìm được tập gồm đủ m chỉ số J = {j1, j2, ..., jm}, J ⊃ J +(x 0) sao cho hệ
{a j
: j ∈J } là độc lập tuyến tính. Còn nếu k = m thì ta đặt J = J +(x 0) .
Bộ môn Khoa Học Cơ Bản 15
Bài Giảng môn Tối Ưu Hoá
Cơ sở của phương án cực biên: ta gọi hệ véctơ {a j : j ∈J } nói trên là một cơ sở
của phương án cực biên x 0 . Đôi khi ta còn gọi tắt J là cơ sở của x 0 .
Định nghĩa: một phương án cực biên x 0 là không suy biến nếu có đúng m
thành phần dương, tức là Card (J +(x 0)) = m . Ngược lại thì gọi là suy biến.
Ví dụ: Đối với ví dụ trên thì rank(A) = 3 .
- Phương án cực biên x 0 = (1; 0; 1; 3)t có cơ sở là J = J +(x 0) = {1; 3; 4} .
Do đó nó là phương án cực biên không suy biến.
- Phương án cực biên x 1 = (0;5;0; 92)t có J +(x 1) = {2; 4} nên nó là
phương án cực biên suy biến. Ta có thể lấy một cơ sở của nó là
J = J +(x 1)∪{3} = {2; 4; 3} .
Bài toán QHTT gọi là không suy biến nếu mọi phương án cực biên của nó
không suy biến. Rõ ràng là nếu một phương án là không suy biến thì nó chỉ có
một cơ sở duy nhất. Như vậy nếu bài toán QHTT là không suy biến thì số cơ sở
nhiều nhất là C n (vì lấy m véctơ từ n véctơ), do đó số phương án cực biên của
m
bài toán QHTT nhiều nhất cũng chỉ là C n . Vậy số các phương án cực biên là
m
hữu hạn.
Khoa Công nghệ thông tin - ĐHTN 16
Thân Quang Khoát
Chương 2. THUẬT TOÁN ĐƠN HÌNH
§1. MỞ ĐẦU
1.1. Bài toán
Ta xét bài toán QHTT dạng chính tắc sau:
f (x ) = c tx → Min
⎧Ax = b
⎪ (I)
⎪
⎨
⎪x ≥ 0
⎪
⎩
trong đó c, x ∈ℜn, b ∈ℜm, A lµ ma trËn cÊp m×n
Hiện nay đã có rất nhiều các thuật toán khác nhau giải bài toán (I). Ta có
thể liệt kê ra một số như sau:
- Thuật toán đơn hình (do Dantzig đề xuất).
- Các phương pháp điểm trong (do Karmarkar đề xuất).
- Các phương pháp Ellipsoid (do Khachian đề xuất).
Trong đó các phương pháp Điểm trong và phương pháp Ellipsoid là các
phương pháp có độ phức tạp tính toán là đa thức, còn phương pháp Đơn hình thì
không. Tuy nhiên trong thực tế tính toán thì người ta thấy rằng, phương pháp
đơn hình là rất hiệu quả, đồng thời nó cũng là thuật toán dễ hiểu và dễ thực hiện.
Một trường hợp đặc biệt là khi chúng ta xét những bài toán QHTT trong
không gian 2 chiều hoặc 3 chiều thì chúng ta có thể dùng phương pháp hình học
khá hữu hiệu để giải.
1.2. Phương pháp Hình Học
Ta xét trong không gian 2 chiều với bài toán dạng chuẩn tắc:
f (x ) = c1x 1 +c2x 2 → Min
với các điều kiện: ai1x 1 +ai2x 2 ≥bi , i = 1,m
Ký hiệu: D = {x = (x 1, x 2) ai1x 1 +ai2x 2 ≥bi , i = 1,m}
Ta biết rằng mỗi một bất phương trình tuyến tính ai1x 1 +ai2x 2 ≥bi xác định
Bộ môn Khoa Học Cơ Bản 17
Bài Giảng môn Tối Ưu Hoá
một nửa mặt phẳng. Như vậy tập D là giao của m nửa mặt phẳng sẽ là một đa
giác lồi trên mặt phẳng.
Phương trình c1x 1 +c2x 2 = α khi α thay đổi sẽ xác định trên mặt phẳng các
đường thẳng song song với nhau.
Định nghĩa: Với mỗi một giá trị của α thì đường thẳng c1x 1 +c2x 2 = α
được gọi là một đường mức.
Với mỗi điểm x = (x 1, x 2) ∈ D sẽ nằm trên đường mức có giá trị mức là
c1x 1 +c2x 2 = α . Như vậy bài toán đặt ra có thể phát biểu như sau: Trong số các
đường mức cắt tập D , hãy tìm đường mức có giá trị mức α nhỏ nhất.
Ta thấy rằng nếu dịch chuyển các đường mức song song các đường mức
theo hướng véctơ pháp tuyến của chúng c = (c1, c2) thì giá trị của mức sẽ tăng,
nếu dịch chuyển theo hướng ngược lại thì giá trị mức sẽ giảm. Vì vậy chúng ta
có thể giải bài toán đặt ra theo cách như sau: Bắt đầu từ một đường mức cắt D ,
ta dịch chuyển đường mức theo hướng ngược với hướng véctơ c = (c1, c2) cho
đến khi nào việc dịch chuyển tiếp theo làm cho đường mức không cắt D nữa thì
dừng. Các điểm của D nằm trên đường mức này sẽ là các lời giải cần tìm, còn
giá trị mức chính là giá trị tối ưu của bài toán.
Ví dụ: Giải bài toán QHTT sau
f (x ) = x 1 −x 2 → min
⎧−x 1 −x 2 ≥−7
⎪ (1)
⎪
⎪
⎪−x 1 + x 2 ≥−2
⎪ (2) (D)
⎪
⎨
⎪2x 1 + x 2 ≥ 2
⎪ (3)
⎪
⎪x ≥ 0, x ≥ 0
⎪1
⎪
⎩ 2
Để giải bài toán này bằng phương pháp hình học thì trước tiên ta phải biểu
diễn miền D trên mặt phẳng toạ độ. Sau đó ta xác định một đường mức cắt miền
D, chẳng hạn: x 1 −x 2 = 0 . Cuối cùng ta sẽ dịch chuyển đường mức theo hướng
giảm (dựa vào véctơ pháp tuyến c = (1,−1) ) để tìm ra đường mức có mức nhỏ
nhất cắt miền D.
Khoa Công nghệ thông tin - ĐHTN 18
Thân Quang Khoát
x2
x1
Ta thấy miền D của bài toán chính là đa giác ABIJK. Khi dịch chuyển
đường mức theo hướng véctơ −c thì điểm I chính là điểm cuối cùng mà đường
mức cắt miền D. Vì vậy I chính là điểm cực biên tối ưu.
Do I là giao điểm của đường thẳng (1) với Ox 2 nên toạ độ điểm I chính là
nghiệm của hệ pt:
⎧−x 1 −x 2 =−7 ⎧x 1 = 0
⎪ ⎪
⎪
⎨ ⇒⎪
⎨
⎪x 1 = 0
⎪ ⎪x 2 = 7
⎪
⎩ ⎩
Vậy x * = (0; 7) là phương án tối ưu và f (x *) =− 7
§2. THUẬT TOÁN ĐƠN HÌNH
2.1. Tư tưởng của thuật toán đơn hình
Xét bài toán QHTT dạng chính tắc:
f (x ) = c tx → Min
⎧Ax = b
⎪ (I)
⎪
⎨
⎪x ≥ 0
⎪
⎩
Bộ môn Khoa Học Cơ Bản 19
