Bài giải Quy hoạch tuyến tính - Phạm Đỗ Lộc

hứng minh mệnh đề sau : 
C là tập lồi nếu và chỉ nếu : (u1, u2, , uk ∈ C; 1 2, ,... kaα α ∈ R
+ : 
1
1
k
i
i
α
=
=∑ ) → 
1
k
i i
i
uα
=
∑ ∈ C. (*) 
Giải : Chứng minh bằng phương pháp quy nạp. 
• Khi k = 2, thì với mọi u1, u2 ∈ C, 1 2,α α∀ ≥ 0 và 1 2α α+ = 1. Thì : 
2
1
i i
i
uα
=
∑ = 1 1 2 2u uα α+ ∈ C ( do C là tập lồi). 
• Giả sử (*) đúng khi k = n, nghĩa là : với mọi u1, u2, , un ∈ C, tồn tại 1 2, ,..., naα α ∈ R
+ 
 và 
1
1
n
i
i
α
=
=∑ . Khi đó 
1
n
i i
i
uα
=
∑ ∈ C ( 1 1 2 2 ... n nu u uα α α+ + + ∈ C ). 
• Bây giờ ta chứng minh (*) cũng đúng khi k = n + 1. 
Với mọi u1, u2, , un, un+1 ∈ C thì tồn tại 1 2 1, ,..., ,n nα α α α + ∈ R
+ và 1 2 1... 1n nα α α α ++ + + + = , 
đặt θ = 1 2 ... nα α α+ + + → 1 1nα θ+ = − . 0θ∀ ≥ 
Khi đó 
1
1
n
i i
i
uα
+
=
∑ = 
1
n
i i
i
uα
=
∑ + 1 1n nuα + + = 
1
n
i i
i
uαθ
θ=
∑ + 1(1 ) nuθ +− 
DoLoc Pham 
Đặt 
1
n
i i
i
uu α
θ=
=∑ → 
1
1
n
i i
i
uα
+
=
∑ = 1(1 ) nu uθ θ ++ − ∈ C 
• Ngược lại. hiển nhiên đúng ( theo định nghĩa tập lồi ) 
Bài 16. Chứng minh tập lồi đa diện là tập lồi, là tập đóng. 
Giải : 
• Tập lồi đa diện là tập lồi. ( chứng minh ở trên ) 
Do giao của hữu hạn tập đóng là tập đóng, nên để chứng minh M là tập đóng ta chỉ cần 
chứng minh nửa không gian đóng là tập đóng. Nửa không gian đóng có dạng : 
H = {u ∈ Rn: ,a u α≥ } nên M { }
1
: ,
n
n
i i
i
u R a u c
=
∈ ≥ 
• Lấy u bất kỳ ∈ H ta có : ,a u c≤ → c - ,a u ≥ 0 
Đặt ( ) ,, ( ) c a ud u
a
α
−
= ≥ r ta sẽ chứng minh B(u, r)  H = ∅ , 
nghĩa là 0 0( , ) &u B u r u H∃ ∈ ∈ . u0 ∈ H → 0,a u c≥ 
Vì u0 ∈ B(u,r) nên ||u0 – u|| ≤ r ⇔ ||u0 – u|| ≤ 
,c a u
a
−
 ⇔ ||a|||| u0 – u|| ≤ c - ,a u 
 ⇔ 0,a u u− ≤ c - ,a u 
 ⇔ 0,a u - ,a u ≤ c - ,a u 
 → 0,a u ≤ c → u0 không thuộc H, điều này mâu thuẫn 
với giả thuyết ban đầu, nên B(u, r)  H = ∅ 
Vậy H là tập đóng. 
Bài 17. 
a. Chứng minh rằng điểm trong của tập lồi đa diện không thể là điểm cực biên. 
b. Điểm cực biên của tập lồi đa diện là điểm biên. Điều ngược lại có đúng không ? 
Giải : 
DoLoc Pham 
a. Lấy x0 ∈ Rn và M ⊂ Rn, điểm x0 gọi là điểm trong của M nếu tồn tại r > 0 sao cho: 
 B(x, r) ⊂ D 
b. Điểm x0 gọi là điểm biên của M nếu B(x0 , r) ∩ M ≠ ∅ . 
Bài 18. Chứng minh mệnh đề sau : Cho M là tập lồi đa diện, u ∈ M, u là điểm cực biên của M 
nếu và chỉ nếu không tồn tại a, b thuộc về M sao cho : 
[ ] { }0 , \ ,
a b
u a b a b
≠
 ∈
Giải : Ta có u ∈ extM → M\{u} là tập lồi. 
Giả sử tồn tại a, b ∈ M : 
[ ]
, ,
,
a b u a u b
u a b
≠ ≠ ≠
 ∈
• a M
a u
∈
 ≠
 → a ∈M\{u} 
• b M
b u
∈
 ≠
 → b ∈ M\{u} 
→ [a, b] ⊂ M\{u} mà u ∈ [a, b], nghĩa là [a, b] = (1 )a bα α+ − ⊂ M\{u}, điều này vô lý, 
do đó tồn tại a, b. 
Ngược lại : Giả sử tồn tại a, b ∈ M : 
[ ],
a b
u a b
≠
 ∈
 Giả sử u ∉ extM → M\{u} không là tập lồi. 
 Nghĩa là tồn tại a, b ∈M\{u} nhưng [a, b] ⊄ M\{u} (*) 
 Mà a ∈M\{u} ⊂ M\{u} & b ∈ M\{u} ⊂ M\{u} → [a, b] ⊂ M\{u} (**) 
 Từ (*) & (**) ta thấy mâu thuẫn, do đó u ∈ extM 
Bài 23. Cho M là một tập lồi đa diện, a là một điểm nào đó. Đặt a + M = { u + a : u ∈M } 
a. ( a + M ) có phải là tập lồi đa diện hay không ? 
b. Giả sử u là điểm cực biên của M, điểm ( a + u ) có phải là điểm cực biên của tập (a + M) 
hay không ? 
Giải : 
a. M = { u ∈Rn : Au ≥ b } 
DoLoc Pham 
Xét a + M = { a + u | u ∈ M } 
Lấy w ∈ a + M ⇒ u M∃ ∈ , w = a + u. 
Ta có Aw = A( a + u ) = Aa + Au ≥ Aa + b . Đặt b Aa b= + . 
Đặt S = { w ∈Rn |Aw = b }. Ta cần chứng minh a + M ⊂ S. 
• Ta có a + M ⊂ S ( hiển nhiên ) 
• Chứng minh S⊂ a + M. 
b. Giả sử u ∈ extM. Đặt A = { a } → A là tập lồi 
→ M\{u0} là tập lồi. → A + M\{u0} là tập lồi. 
Ta có A + M\{u0} = a + M\{u0} nên a + M\{u0} cũng là tập lồi. 
Mà a + M\{u0} = { a + u : u ∈ M\{u0}} → a + M\{u0} = ( a + M )\{ a + u0 } 
→ ( a + M )\{ a + u0 } là tập lồi. 
PHƯƠNG PHÁP TÌM ĐIỂM CỰC BIÊN CỦA TẬP LỒI ĐA DIỆN 
1. Trường hợp M nR∈ ( n = 1, 2, 3 ): Ta có thể xác định các điểm cực biên thông qua các 
biểu diễn hình học, quan sát mô tả các tập điểm của M trên hình vẽ. 
2. Trường hợp tổng quát. 
a. Định lý  Điều kiện cần và đủ để một điểm là điểm cực biên của tập lồi đa diện: 
Cho { }: .nM u R Au b= ∈ ≥ . Với A là ma trận cấp m n× , b là ma trận cấp 1m× 
Ta có u M∈ , u là điểm cực biên của M khi và chỉ khi 1 2, ,..., ni i i∃ ∈ { }1,2,...,m sao cho 
• Hệ i1 i2{ , ,..., }ina a a là hệ độc lập tuyến tính. 
• u là nghiệm của hệ khi : 
,
1,
ij ija u b
j n
 =

=
trong đó ai là hàng thứ i của ma trận A, bi là số hàng thứ i của vector b ∈ Rm. 
b. Mệnh đề . Số điểm cực biên của tập lồi đa diện là hữu hạn và ≤ nmC với m là số cột, n 
là số hàng của ma trận. 
Ví dụ : 1 3 4( ) 2 5 minf x x x x= + + → 
1 3 4
2 3 4
5
2 1
0, 1,4j
x x x
x x x
x j
 + + =
 − + =
 ≥ =
Ma trận các hệ số ràng buộc là : A = 1 0 1 1
0 1 1 2
 
 − 
, 
DoLoc Pham 
A có 4 vector cột A1 = 
1
0
 
 
 
, A2 = 
0
1
 
 
 
, A3 = 
1
1
 
 − 
, A4 = 
1
2
 
 
 
. b = 5
1
 
 
 
Số hệ con ĐLTT của của A là nmC = 
4!
2!(4 2)!−
 = 6. 
→ có 6 hệ con ĐLTT của A là {A1, A2}, {A1, A3}, {A1, A4},{A2, A3},{A2,A4}, {A3, A4} 
Giải các hệ con. 
Hệ 1 biểu diễn có dạng : 1 2
1 2
0 5
0 1
x x
x x
+ =
 + =
 → u1 = ( 5, 1, 0, 0 ) 
Hệ 2 biểu diễn có dạng : 1 3
1 3
5
0 1
x x
x x
+ =
 − =
→ u2 = ( 6, 0, -1, 0) 
Tương tự tìm được u3 = (
9
2
, 0, 0, 1
2
),u4 = ( 0, 6, 5, 0 ),u5 = ( 0, - 9, 0, 5 ), u6 = ( 0, 0, 3, 2 ) 
Bài toán có tập phương án khác rỗng 
Hàm mục tiêu bị chặn dưới bởi 5 vì với mọi ui ≥ 0 thì f(ui) ≥ 5 
Tập phương án { u1, u3, u4, u6 } 
Giá trị của các phương án cực biên là f(u1) = 10, f(u3) = 
23
2
, f(u4) = 5, f(u6) = 13. 
Vậy với u4 = ( 0, 6, 5, 0 ) thì f(u4) = 5 là giá trị nhỏ nhất. 
B1. Kiểm tra xem M 0≠ và bị chặn. 
B2. Tìm Ma trận các hệ số ràng buộc A , b ? 
B3. Tìm các hệ con độc lập tuyến tính ≤ nmC 
B4. Tìm các tập điểm của M. 
B5. Thay các M vào f(x), so sánh các giá trị, tìm giá trị tối ưu, từ đó suy ra PATU. 
Chương 2. NGHIỆM CỦA BÀI TOÁN QHTT 
1. Một số tính chất của QHTT. 
Cho QHTT ở dạng chuẩn tắc : 
, min
.
0
c u
Au b
u
 →

≥
 ≥
 (TT1) 
Gọi M là tập phương án của (TT1), M0 là tập phương án tối ưu của (TT1) 
Mệnh đề 1. M là tập lồi đa diện, do đó nó là tập lồi, là tập đóng. 
Mệnh đề 2. M0 là tập lồi đa diện, do đó nó là tập lồi, là tập đóng. 
Chứng minh : 
• M0 = ∅ nó là tập lồi ( hiển nhiên ) 
• 0M ≠ ∅ thì tồn tại 0u là phương án tối ưu và 0,c u là giá trị tối ưu. 
{ }0 0: , ,M u M c u c u α= ∈ = = = { }: ,nM u R c u α∈ = 
DoLoc Pham 
Hay { } { }0 : , : ,n nM M u R c u u R c uα α= ∈ ≥ ∈ ≤  . 
Nghĩa là M0 là giao của các tập lồi đa diện. 
Mệnh đề 3. Nếu 0M ≠ ∅ thì M0 có vô số phần tử hoặc có một phần tử. 
Chứng minh : Giả sử M0 có 2 phần tử là u1 và u2 thì 1 2 0( , )u u M∆ ⊂ 
Mà 1 2 1 2( , ) (1 )u u u uα α∆ = + − , [ ]0,1α ∈ lại có vô số phần tử. 
2. Điều kiện có nghiệm. 
Định lý 1. Nếu M ≠ ∅ và M bị chặn thì 0M ≠ ∅ 
Chứng minh: Do hàm f là hàm liên tục trên tập đóng và bị chặn trên Rn thì hàm số sẽ có 
giá trị lớn nhất và bé nhất trên tập đó, nghĩa là tồn tại các số { }min ( ) , :f u c u u M= ∈ và 
{ }max ( ) , :f u c u u M= ∈ 
Định lý 2. Xét bài toán (TT1) và giả sử M ≠ ∅ nên 0M ≠ ∅ hàm : ,f u c u là hàm bị 
chặn dưới trong M. 
Chứng minh: vì 0M ≠ ∅ nên tồn tại 0u M∈ và 0( )f u α= sao cho 0( ) ( )f u f u≥ hay 
( )f u α≥ , u M∀ ∈ , Rα∀ ∈ . Nên f là hàm bị chặn dưới. 
Định lý 3. Xét (TT1). Nếu 0M ≠ ∅ thì 0M extM ≠ ∅ ( nếu bài toán có nghiệm thì có thể 
tìm nghiệm trong các phương án cực biên ) 
Hệ quả. Nếu 0M ≠ ∅ thì { } { }min , : min , :c u u M c u u extM∈ = ∈ 
Chứng minh: Ta có { } { }min , : min , :c u u M c u u extM∈ ≤ ∈ do extM M⊂ 
Giả sử 0 0u M extM∃ ∈  ⇒ 0, :c u u extM∈ và { } 0min , : ,c u u M c u∈ = 〈 〉 
Do 0u extM∈ ⇒ { }0, min , :c u c u u extM〈 〉 ≤ ∈ 
3. Thuật toán tìm phương án tối ưu. 
 Kiểm tra 0M ≠ ∅ nếu đúng thì dừng. 
 Xác định tập các phương án cực biên của M là extM 
 Xác định tập { }, :c u u extM∈ 
 Tính { }min , :c u u extM α∈ = 
 Kết luận về giá trị tối ưu. 
 Ví dụ . f(x) = 4x1 + 5x2 + 7x3 → min 
1 2 3
1 2 3
1 2 3
3 6
2 3 14
, , 0
x x x
x x x
x x x
+ + =
 + + =
 ≥
Ma trận các hệ số ràng buộc là : A = 3 1 1
1 2 3
 
 
 
, 
DoLoc Pham 
Các vector cột của A là : A1 = 
3
1
 
 
 
, A2 = 
1
2
 
 
 
, A3 = 
1
3
 
 
 
, b = 6
14
 
 
 
Số hệ con ĐLTT của hệ là : 23C = 3 → có 3 hệ con ĐLTT của A là :{A1, A2},{A1, A3},{A2, A3} 
Giải các hệ con. 
Hệ 1 có dạng : 1 2
1 2
3 6
2 14
x x
x x
+ =
 + =
 → u1 = (
2
5
− ,
36
5
, 0 ) 
Hệ 2 có dạng : 1 3
1 3
3 6
3 14
x x
x x
+ =
 + =
 → u2 = (
1
2
, 0, 9
2
) 
Hệ 3 có dạng : 2 3
2 3
6
2 3 14
x x
x x
+ =
 + =
 → u3 = ( 0, 4, 2 ) 
Bài toán có tập phương án khác rỗng và hàm mục tiêu bị chặn dưới bởi không ( với mọi xi ≥ 0 ) 
thì f(x) ≥ 0. 
Tập phương án là { u2, u3 } 
Giá trị hàm mục tiêu tại các ui là f(u2) = 
67
2
, f(u3) = 34. 
Vậy phương án tối ưu là u2 = (
1
2
, 0, 9
2
), giá trị tối ưu là f(u2) = 
67
2
. 
BIẾN ĐỔI DẠNG CỦA BÀI TOÁN QHTT 
1. Khi gặp ràng buộc dạng : 
1
n
ij j i
j
a x b
=
≤∑ ta đưa vào ẩn phụ xn+i ≥ 0 để biến về phương trình 
1
n
ij j n i i
j
a x x b+
=
+ =∑ . 
2. Khi gặp ràng buộc dạng 
1
n
ij j i
j
a x b
=
≥∑ ta đưa vào ẩn phụ xn+i ≥ 0 để biến về phương trình 
1
n
ij j n i i
j
a x x b+
=
− =∑ . 
3. Khi gặp ẩn xj ≤ 0, ta đổi biến xj = - xj’ với xj’ ≥ 0. 
4. Khi gặp ẩn xj tùy ý, ta đổi biến xj = xj’ – xj” với xj’ , xj” ≥ 0. 
DoLoc Pham 
Kết luận : Khi tìm được phương án tối ưu của bài toán dạng chính tắc, ta chỉ cần thay các 
ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ tìm được phương án tối ưu của bài toán. 
Bài 24, 25. Hãy xác định tập các điểm cực biên của các tập lồi đa diện xác định bởi hệ sau : 
1 2 3
1 2 3
1 2 3
2 3
15
, , 0
x x x
x x x
x