Quy hoạch Tuyến tính

Chia sẻ: nvcuong198

1.1.1 Bài toán lập kế hoạch sản xuất Bài toán: Một cơ sở sản xuất dự tính sản xuất hai loại sản phẩm A và B. Các sản phẩm được chế tạo từ ba loại nguyên liệu I,II,III.

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Quy hoạch Tuyến tính

Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




M cl c

Chương 1. Bài toán quy ho ch tuy n tính 3
1.1. M t vài bài toán th c t ........................ 3
1.1.1 Bài toán l p k ho ch s n xu t . . . . . . . . . . . . . . . . 3
1.1.2 Bài toán v n t i . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Bài toán quy ho ch tuy n tính . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 D ng t ng quát . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 D ng chính t c và d ng chu n t c . . . . . . . . . . . . . . . 6
1.3. ý nghĩa hình h c và phương pháp đ th ............... 8
1.4. Bài t p chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Chương 2. Tính ch t c a t p phương án và t p phương án t i ưu c a
bài toán quy ho ch tuy n tính 14
2.1. T p h p l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2. Tính ch t c a t p phương án và t p phương án t i ưu c a bài toán
quy ho ch tuy n tính . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3. Tính ch t c a quy ho ch tuy n tính d ng chính t c . . . . . . . . . 16
2.4. Bài t p chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Chương 3. Phương pháp đơn hình và các thu t toán c a nó 21
3.1. Cơ s lí lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2. Thu t toán đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Thu t toán đơn hình . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 B ng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . 24

1
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


3.2.4 Trư ng h p bài toán suy bi n . . . . . . . . . . . . . . . . . 27
3.2.5 Tìm phương án c c biên và cơ s ban đ u . . . . . . . . . . 27
3.3. Bài t p chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Chương 4. Bài toán quy ho ch tuy n tính đ i ng u và thu t toán đơn
hình đ i ng u 42
4.1. Bài toán quy ho ch tuy n tính đ i ng u . . . . . . . . . . . . . . . 42
4.2. Thu t toán đơn hình đ i ng u . . . . . . . . . . . . . . . . . . . . . 47
4.2.1 Cơ s lí lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.5 Thu t toán đơn hình đ i ng u . . . . . . . . . . . . . . . . . 49
4.3. V n đ tìm phương án c c biên xu t phát c a bài toán đ i ng u . . 54
4.4. V n đ h u t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5. Bài t p chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Chương 5. Bài toán v n t i và thu t toán th v 68
5.1. Bài toán v n t i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2. Các Tính ch t c a bài toán v n t i . . . . . . . . . . . . . . . . . . 69
5.2.1 Chu trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3. V n đ tính các ư c lư ng . . . . . . . . . . . . . . . . . . . . . . . 70
5.4. M t s phương pháp xây d ng phương án c c biên ban đ u . . . . 73
5.5. Thu t toán th v . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6. Tiêu chu n t i ưu. Bài toán đ i ng u c a bài toán v n t i . . . . . 77
5.6.1 Tiêu chu n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.2 Bài toán đ i ng u c a bài toán v n t i . . . . . . . . . . . . 78




2
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




Chương 1.

BÀI TOÁN QUY HO CH TUY N
TÍNH


1.1. M t vài bài toán th c t
1.1.1 Bài toán l p k ho ch s n xu t

Bài toán: M t cơ s s n xu t d đ nh s n xu t hai lo i s n ph m A và B . Các
s n ph m đư c ch t o t ba lo i nguyên li u I, II và III. S lư ng d tr c a t ng
lo i và s lư ng t ng lo i nguyên li u c n dùng đ s n xu t ra m t s n ph m đư c
cho b ng b ng sau:


Lo i Nguyên li u Nguyên li u c n dùng đ s n xu t m t đơn v s n ph m
Nguyên li u d tr A B
I 18 2 3
II 30 5 4
III 25 1 6




Hãy l p quy ho ch s n su t đ thu đư c ti n lãi là l n nh t, bi t r ng ti n lãi thu
đư c khi bán m t s n ph m A là 3 tri u đ ng, m t s n ph m B là 2 tri u đ ng.
Ta xây d ng mô hình toán h c cho bài toán trên: G i x, y theo th t
là s s n ph m A, B c n s n xu t theo k ho ch. Khi đó, ti n lãi thu đư c là:

Z = 3x + 2y (tri u đ ng )



3
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Nh ng ràng bu c v nguyên li u d tr , đó là:

2x + 3y ≤ 18 (Ràng bu c v nguyên liêu I)

5x + 4y ≤ 30 (Ràng bu c v nguyên liêu II)

x + 6y ≤ 25 (Ràng bu c v nguyên liêu III)

Ngoài ra, còn các ràng bu c t nhiên là x, y ≥ 0. Vì s đơn v s n ph m không th
âm. Như v y, b ng ngôn ng toán h c, bài toán có th phát bi u như sau: Tìm x
và y sao cho t i đó bi u th c Z = 3x + 2y đ t giá tr l n nh t, v i các ràng bu c:

 2x + 3y 18






 5x + 4y 30

(1.1.1)
x + 6 y 25







 x 0, y 0

Bài toán t ng quát c a bài toán trên là: Hãy tìm véc tơ x = (x1 , x2 , . . . , xn )
n
cj xj → max v i các ràng bu c :
sao cho hàm f (x) =
j =1

n


aij xj bi , i = 1...m



j =1


 xj 0, j = 1..n



1.1.2 Bài toán v n t i

Bài toán. C n v n chuy n hàng t hai kho (tr m phát) P1 và P2 t i ba nơi tiêu
th (tr m thu) T1 , T2 , và T3 . B ng dư i đây cho bi t cho bi t s lư ng hàng v n
chuy n cùng v i cư c phí v n chuy n m t đơn v hàng t m i kho t i m i nơi tiêu
th tương ng.




Hãy l p l p k ho ch v n chuy n th a mãn yêu c u bài toán sao cho chi phí
v n chuy n là nh nh t.

4
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ta xây d ng mô hình toán h c cho bài toán trên.
G i xij là lư ng hàng hóa c n v n chuy n t Pi đ n Tj , (i = 1..2vj = 1..3) thì
ta có mô hình toán h c bài toán là:
Tìm X = (xij ) sao cho: f = 5x11 + 2x12 + 3x13 + 2x21 + x22 + x23 −→ min v i
các ràng bu c:

x
 11 +x12 +x13 = 30




x21 +x22 +x23 = 75







 x11 +x21 = 35

(1.1.2)
x12 +x22 = 25






x13 +x23 = 45







x 0, i = 1..2, j = 1..3

ij


Bài toán t ng quát c a bài toán v n t i.
Bài toán có m tr m phát, lư ng phát là ai , i = 1, ..., m, n tr m thu, lương thu
tương ng là bj , j = 1, ..., n; cij là cư c phí, xij là lư ng hàng v n chuy n t tr m
phát th i đ n tr m thu j . Khi đó, bài toán có mô hình toán h c như sau: Tìm
m n
cij xij → min v i các ràng bu c:
x = (xij ) sao cho f =
i=1 j =1

n

xij = ai , i = 1, ..., m



j =1


m

(1.1.3)
xij = bj , j = 1, ..., n
i=1





xij 0, i = 1, ..., m, j = 1, ..., n




1.2. Bài toán quy ho ch tuy n tính
1.2.1 D ng t ng quát

Bài toán quy ho ch tuy n tính là bài toán tìm bi n (ho c phương án) th a mãn
các ràng bu c sao cho làm hàm m c tiêu đ t c c đ i ho c c c ti u. V i c hàm
m c tiêu và các ràng bu c đ u tuy n tính theo bi n.
Nh n xét, max(z ) = − min(−z ). Do đó, quy ho ch tuy n tính là:



5
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Tìm x = (x1 , · · · , xn ) sao cho
n
cj xj → min (1)
f (x) =
j =1
  


n  

  

 bi , i ∈ Ik , k = 1, 2, 3 (2)
aij 

(1.2.4)

  


 j =1  
=

 




 0, j ∈ Nl , l = 1, 2 (3)

x 
j




Trong đó, véc tơ x th a các ràng bu c (2) và (3) đư c g i là phương án. Phương
án là hàm m c tiêu f (x) đ t giá tr c c tr theo yêu c u đư c g i là phương án t i
ưu. Gi i quy ho ch tuy n tính là tìm phương án t i ưu c a bài toán.


1.2.2 D ng chính t c và d ng chu n t c

• Quy ho ch tuy n tính d ng chính t c là quy ho ch tuy n tính d ng
n
cj xj → min (1)
f (x) =
j =1
n


aij = bi , i = 1, · · · , m (2)



j =1


0, j = 1, 2 , · · · ,n (3)
 xj



• D ng ma tr n c a quy ho ch tuy n tính d ng chính t c

f (x) = cT x → min (1)
Ax = b (2)
x 0 (3)

Trong đó, c, x là véc tơ c t c a Rn , b là véc tơ c t c a Rm . A là ma tr n c p
n×m

• Nh n xét: M i quy ho ch tuy n tính đ u đưa đư c v d ng chính t c. Th t
v y, n u Ai x ≥ bi (ho c Ai x ≤ bi ) thì ta ch n bi n bù xn+i đưa v d ng
Ai x − xn+i = bi (ho c Ai x + xn+i = bi ).

6
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Khi xj ≤ 0 (ho c xj ∈ R) thì ta thay xj = −xj (ho c xj = x+ x− ) mà
jj

xj , x+ , x− là các bi n không âm.
j j

Ví d 1. Đưa bài toán sau v d ng chính t c

f (x) = 5x1 + 2x2 − 4x3 → max

 4x1 +7x2 +x3 3




−x −2x −1
x
1 2 3


 2x1 +3x2 +6x3 = 11


x1 0, x2 0

Bài gi i


Ta ch n bi n bù x4 , x5 cho cho ràng bu c th nh t, th hai. Ch n n ph
x+ , x− và thay x3 = x+ − x− cho s không mang d u c a x3 .
3 3 3 3

T đó, ta đưa bài toán sau v d ng chính t c như sau:

−f (x) = −5x1 − 2x2 + 4x3 → min

−x4 = 3
 4x1 +7x2 +x3




−x −2x +x5 = −1
x
1 2 3


 2x1 +3x2 +6x3 = 11


0, j = 1, 2, 4, 5; x∗ 0, ∗ = +, −
xj 3


• D ng ma tr n c a quy ho ch tuy n tính d ng chu n t c :

f (x) = cT x → min (1)
Ax b (2)
x 0 (3)

• Khi đưa t d ng chu n t c v chính t c ta ch c n thêm bi n bù cho các ràng
bu c.




7
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


1.3. ý nghĩa hình h c và phương pháp đ th
Xét quy ho ch tuy n tính hai n

f (x) = −2x1 + x2 → min

x
 1 +2x2 2 (1)




 2x1 −3x2 6 (2)




4x +5x2 20 (3)
1



 x1 0 (4)






x2 0 (5)



Sau đây ta đây ta đưa ra cách gi i hình h c bài toán (phương pháp đ th ). Trư c
h t ta bi u di n hình h c t p phương án (Hình 1).
Trên m t ph ng t a đ 0x1 x2 , các ràng bu c đư c bi u di n b i các n a m t
ph ng . Giao c a chúng là t p phương án c a bài toán. T p phương án bài toán
là ngũ giác ABCDE .




T p các đi m (x1 , x2 ) sao cho hàm m c tiêu nh n giá tr m : −2x1 + x2 = m,
là đư ng th ng, đư c g i là đư ng m c (v i m c là m). Khi m thay đ i cho ta h
đư ng th ng song song, có véc tơ pháp tuy n v = (−2, 1).
Khi cho m gi m d n ta th y đi m cu i cùng mà đư ng m c (m) còn c t
t p phương án là đ nh A. A là giao đi m c a đư ng th ng (2) và (3) nên A =
(45/11, 8/11).

8
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp

45 8
V y, x∗ = là phương án t i ưu và fmin = f (x∗) = 82/11.
,
11 11
Nhân xét

+ Trong trư ng h p t p phương án khác r ng mà không có v trí gi i h n thì
bài toán có hàm m c tiêu không b ch n

+ Phương pháp đ th có th áp d ng cho trư ng h p nhi u bi n nhưng ch có
hai ràng bu c cư ng b c.



1.4. Bài t p chương 1
Bài 1.1. M t cơ s s n xu t có th làm đư c hai lo i hàng I và hàng II, t nguyên
li u A và B. Tr lư ng các nguyên li u A và B hàng ngày có đư c theo th t là
6 và 8 đơn v . Đ s n xu t m t đơn v hàng I c n 2 đơn v nguyên li u lo i A và
3 đơn v nguyên li u lo i B; s n xu t m t đơn v hàng II c n 1 đơn v nguyên li u
lo i A và 4 đơn v nguyên li u lo i B. Giá bán m t đơn v hàng I và hàng II theo
th t là 7 và 5 đơn v ti n t . Qua ti p th đư c bi t, trong m t ngày nhu c u tiêu
th hàng II không quá 2 đơn v ; nhu c u hàng I hơn hàng II không quá 1 đơn v .
V n đ đ t ra là c n s n xu t m i ngày bao nhiêu đơn v hàng m i lo i đ doanh
thu l n nh t.
Hãy thi t l p mô hình toán h c cho bài toán đó?

Bài 1.2. M t máy bay có tr ng t i M . Có n lo i hàng hóa c n x p lên máy bay
đó. M i đơn v lo i j có kh i lư ng là aj và giá cư c phí là bj , (j = 1n). C n x p
lên máy bay m i lo i hàng bao nhiêu đơn v đ t ng cư c phí thu đư c là nhi u
nh t.
Hãy thi t l p mô hình toán h c cho bài toán đó?

Bài 1.3. Gi s m t nhà máy c n phân công cho m phân xư ng cùng s n xu t
m t lo i máy có n chi ti t khác nhau, trong đó m i máy c n kj chi ti t th
j (j = 1, . . . , n).aij là s chi ti t th j mà phân xư ng th i có th s n xu t trong
m t đơn v th i gian.


9
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Hãy l p mô hình toán h c bài toán xác đ nh s đơn v th i gian c n dành s n
xu t chi ti t j c a phân xư ng i trong m t đơn v th i gian?

Bài 1.4. Dùng đ nh nghĩa, ch ng t x∗ là phương án t i ưu c a các bài toán sau

(a) f (x) = 84x1 + x3 → min

 2x1 + x2 + x3 5




x1 − x2 + x3 1



4x1 − x3 −3



x1 0

x∗ = (0, 2, 3)

(b) f (x) =x2 +x4 → min

 −x1 +2x2 +x3 +x4 = 1




−2x1 +x2 +x3 +x4 = 2



3x2 + 2x4 = 3



x1 0

x∗ = (0, −1, 0, 3)

(c) f (x) = x1 +x4 → max

 x1 +x2 +x3 +x4 =1




x +x +3x +2x 4
1 2 3 4


 −x1 +x2 +9x3 +4x4 = 16


x1 0

x∗ = (0, 1, 3, −3)
Bài 1.5. Ch ng t r ng các bài toán sau có t p phương án khác r ng nhưng hàm
m c tiêu không b ch n.




10
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


f (x) = 3x1 −x2 → max

x1 +x2 2





 −x1 +x2 2
(a) 

 x −2x

2
1 2

x1 0, x2 0

f (x) = x1 −x2 → min

 2x −x −2
1 2




2x1 +x2 2

(b) 

x1 −3x2

3


x1 0, x2 0


Bài 1.6. Tìm phương án t i ưu c a bài toán sau:

f (x) = −x1 − 2x2 − 2x3 +6x4 → min

 −2x +2x =5
1 2





 −x1 +2x2 −x3 +x4 10




−x −2x2 = −2
+3x4
1



−5x4 −13
 2x1 +x3





−2x3

2x2 =5





Bài 1.7. Ch ng t r ng, đ i v i các bài toán sau, m i phương án đ u là phương
án t i ưu:
f (x) = −3x2 +2x3 −x4 → min

 −5x1 +4x2 −x3 +3x4 = −7
(a)
 −4x −7x +6x
3 −x4 =8
1 2




11
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


f (x) = 100x1 + 70x2 − 30x3 → max

−8x2 −9x3 −19
 x1




(b) −3x −4x = −13
x
1 2 3


 2x1 +5x2 +3x3 = −15


x1 0
Bài 1.8. Gi i b ng phương pháp đ th các bài toán sau:
f (x) = −x1 + x2 → min

 −2x1 +x2 2




−2x2
x1 2
(a) 


x1 +x2 5
 

x1 0, x2 0

f (x) = x1 − 3x2 → max

 4x1 +3x2 12




(b) −x +x 5
1 2



 x1 +5x2 6


x1 0,
Bài 1.9. Đưa bài toán v d ng chính t c:
f (x) = x1 + x2 → max

 2x + x 1
1 2

(a)  x1 − x2 0


x1 0, x2 0

f (x) = x1 + x2 → min

(b)  0 x1 3


−5
 x2





12
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Bài 1.10. Cho bài toán
f (x) = x1 + x2 → min

 2x + x 3
1 2

 λx1 + x2 2


x1 0, x2 0

Tìm t t c giá tr c a sao sao cho

(a) T p phương án là r ng.

(b) T p phương án khác r ng nhưng hàm m c tiêu không b ch n.

(c) Bài toán có phương án t i ưu duy nh t .

(d) Bài toán có vô s phương án t i ưu.

Bài 1.11. Cho quy ho ch tuy n tính

f (x) = 4x1 + 8x2 + x3 − 6x4 → min

 2x1 +2x2 +3x3 +3x4 50




4x +8x +2x3 +3x4 = 80
1 2



 4x1 +4x2 +x3 +2x4 = 40


xj 0, j = 1..4


(a) Ch ng minh m i phương án c a bài toán đ u có x1 = x4 = 0.

(b) Xác đ nh t p phương án. T đó tìm phương án t i ưu c a bài toán đã cho.




13
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




Chương 2.

TÍNH CH T C A T P PHƯƠNG ÁN
VÀ T P PHƯƠNG ÁN T I ƯU C A
BÀI TOÁN QUY HO CH TUY N
TÍNH


2.1. Tph pl i
Đ nh nghĩa 2.1.1 (T h p l i). Gi s x1 , x2 , . . . , xm là các đi m c a Rn . Đi m
m
x đư c g i là t h p l i c a các đi m y n u t n t i λi 0, i = 1, .., m, λi =
i=1
m
λi xi
1 sao cho x =
i=1
Trong trư ng h p x là t h p l i c a hai đi m x1 , x2 ta thư ng vi t

x = λx1 + (1 − λ)x2 , 0 λ 1

T p h p các đi m là t h p l i c a hai đi m x1 , x2 đư c g i là đo n th ng n i
hai đi m y. Khi đó, hai đi m x1 , x2 g i là đ u mút, các đi m còn l i c a đo n
th ng g i là đi m trong c a đo n th ng y.

Đ nh lý 2.1.2 (Tính ch t b c c u c a t h p l i). Đi m x là t h p l i c a
các đi m xj , j = 1, .., m và m i đi m xj là t h p l i c a các đi m y i , i = 1, .., k .
Khi đó x là t h p l i c a các đi m y i , i = 1, .., k .

Đ nh nghĩa 2.1.3 (T p l i). T p L ⊂ Rn đư c g i là t p l i n u L ch a hai
đi m nào đó thì nó ch a c đo n th ng n i hai đi m đó.
T p r ng và t p đơn t đư c coi như t p l i.

14
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Đ nh lý 2.1.4 (Tính ch t t p l i).

(a) Giao c a các t p l i là t p l i.

(b) N u L là t p l i thì nó ch a m i t h p l i c a h u h n đi m c a t p đó.

Đ nh nghĩa 2.1.5 (Đi m c c biên c a t p l i). Đi m x0 c a t p l i L đư c
g i là đi m c c biên c a t p l i y n u nó không là đi m trong c a đo n th ng
n i hai đi m phân bi t trong L, t c là không t n t i trong L hai đi m phân bi t
x1 , x2 sao cho x0 = λx1 + (1 − λ)x2 , 0 < λ < 1.

Đ nh nghĩa 2.1.6 (Đa di n l i và t p l i đa di n).

(a) T p L g m các đi m là t h p l i c a các đi m xi , i = 1, .., m cho trư c đư c
g i là đa di n l i sinh b i h đi m đó xi .

(b) Giao c a m t s h u h n các n a không gian trong Rn đư c g i là t p l i đa
di n.

Ngư i ta ch ng minh đư c r ng, m t t p l i đa di n không r ng và gi i n i là
m t đa di n l i.



2.2. Tính ch t c a t p phương án và t p phương
án t i ưu c a bài toán quy ho ch tuy n tính
Đ nh lý 2.2.1 (Tính l i c a t p phương án).

(a) T p các phương án c a bài toán quy ho ch tuy n tính là t p l i.

(b) T p các phương án t i ưu c a bài toán quy ho ch tuy n tính là t p l i.

Đ nh lý 2.2.2 (Phương án c c biên).

(a) N u t p phương án c a bài toán quy ho ch tuy n tính không r ng và là đa
di n l i thì bài toán đó có ít nh t m t phương án c c biên là phương án t i
ưu.

15
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(b) Gi s x là m t đi m c a P = {x ∈ Rn : bi , i = 1, . . . , m}, trong đó
Ai x
Ai là ma tr n dòng th i c a ma tr n A c n × m. Khi đó, x là đi m c c
biên c a P khi và ch khi th a mãn v i d u b ng đ i v i n b t phương trình
đ c l p tuy n tính trong m b t phưng trình Ai x bi , i = 1..m.



2.3. Tính ch t c a quy ho ch tuy n tính d ng
chính t c
Đ nh lý 2.3.1 (Đi u ki n c a phương án c c biên). Gi s x0 = (x10 , x20 , . . . , xn0 )
là phương án khác 0 c a bài toán quy ho ch tuy n tính d ng chính t c, v i t p phưng
án
P = x ∈ Rn : x1 A1 + x2 A2 + ... + xn An = b; x 0.

Khi đó, x0 là phương án c c biên c a t p P khi và ch khi h véc tơ liên k t v i
nó, t c là h H (x0 ) = Aj : xj 0 > 0 đ c l p tuy n tính.

H qu 2.3.2 (Tính h u h n c a phương án c c biên). S phương án c c
biên c a bài toán quy ho ch tuy n tính d ng chính t c là h u h n.

Đ nh lý 2.3.3 (Phương án c c biên t i ưu). N u bài toán quy ho ch tuy n
tính d ng chính t c có phương án t i ưu thì nó có ít nh t m t phương án c c
biên t i ưu.

Đ nh lý 2.3.4 (Đi u ki n có phương án t i ưu). Đi u ki n c n và đ đ bài
toán quy ho ch tuy n tính có phương án t i ưu là t p phương án khác r ng và hàm
m c tiêu b ch n.



2.4. Bài t p chương 2
Bài 2.1. Ch ng minh các bài toán sau có phương án t i ưu

(a) f (x) = 3x1 + 2x2 + x3 → max



16
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


 x1 + x2 + x3 = 1
 x −x +x =1
1 2 3

xj 0, j = 1, . . . , 3

(b) g (x) = x1 + x2 + x3 → min

 −x1 + x2 + x3 1




−x − x − x 1
1 2 3



 −x1 − x2 + x3 1



(c) ϕ(x) = 3x1 − x2 → min

 2x1 + 5x2 10




2x + x 6
1 2



 x1 + 2x2 2


x1 0, x2 0
Bài 2.2. Ch ng minh r ng hình tròn trong R2 là m t t p l i.

Bài 2.3. Gi s x là đi m c a t p l i L. Ch ng minh r ng x là đi m c c biên c a
L khi và ch khi L \ {x} là t p l i.

Bài 2.4. Trên R2 , cho hai đi m A(2, 1) và B (3, 4) và h b t phương trình v i
m-tham s 
 2x − y m−2




x − 3y m+3



2 − 3m
 x+y


Tìm t t c các giá tr c a m sao cho m i đi m thu c đo n th ng AB đ u là nghi m
c a h đã cho.

Bài 2.5. Cho hai t p l i đa di n X = {x ∈ Rn : Ax 0} , trong đó A là
b, x
ma tr n c n × m và Y = {(x, y ) : x ∈ Rn , y ∈ Rm , Ax − y = b, x 0}.
0, y
Ch ng minh r ng x là đi m c c biên c a X thì (x, y ) là đi m c c biên c a Y , đó
y = Ax − b và ngư c l i.




17
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Bài 2.6. Tìm t t c các đi m c c biên c a các t p l i cho b i h sau

 x +x 2
1 2





 x1 − 3x2 3

(a)
 −3x + x 6
1 2





x 0, x 0

1 2


 2x + x + 3x + 2x + 4x 10
1 2 3 4 5




x1 + 3x2 + 2x3 + x4 + 3x5 = 5
(b)



xj 0, j = 1, .., 5



Bài 2.7. Trên R2 cho các đi m O(0, 0), A(0, 2), B (1, 3), C (2, 0).

(a) Vi t h ràng bu c cho quy ho ch tuy n tính nh n t giác OABC làm t p
phưng án.

(b) V i giá tr nào c a tham s λ thì B là phương án t i ưu c a bài toán quy
ho ch tuy n tính có t p phương án là OABC và hàm m c tiêu f (x) = x − 2y −→
min

(c) Tìm mi n giá tr c a hàm s g (x) = x − 2y trên OABC .

Bài 2.8. Cho quy ho ch tuy n tính

f (x) = 2x1 + λx2 → max

 −x1 + x2 3




x + 2x 12
1 2


 3x1 − x2 15


x1 0, x2 0
(a) Đ i v i m i giá tr c a λ hãy tìm phương án t i ưu c a bài toán đã cho.

(b) V i giá tr nào c a λ thì giá tr t i ưu hàm m c tiêu nh nh t.

Bài 2.9. Tìm t t c các đi m c c biên c a các t p l i đư c xác đ nh b i các h sau

 2x1 − 3x2 6




(a) 4x1 + 5x2 20



x1 0



18
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



−x3
x1 +2x4 = 1





(b) −2x4 = 2
x1 +x2 +4x3



x1 0 j = 1, ..., 4



Bài 2.10. Ch ng t các bài toán sau có phương án c c biên nhưng hàm m c tiêu
không b ch n.
f (x) = −x1 − 2x2 − 2x3 + 6x4 → max

−2x1 + 2x2 = 5






 −x1 + 2x2 − x3 + x4 10

(a)



−x1 − 2x2 + 3x4 = −2



2x1 + x3 − 5x4 −13






2x2 − 2x3 = 5




f (x) = −4x1 + x2 − x3 + 5x4 → min

 2x =4
1




(b)

 6x1 −2x2 6


−7
x3






x3 +5x4 = −12



Bài 2.11. Cho quy ho ch tuy n tính

f (x) = x1 + x2 → max


ax + bx 1
1 2

x 0, x2 0
1

Tìm t t c các giá tr tham s a, b sao cho

(a) T p phương án khác r ng.

(b) Bài toán đã cho có phương án t i ưu.

(c) Hàm m c tiêu không b ch n.

Bài 2.12. Đ i v i m i bài toán sau, ch ng t r ng, x∗ là phương án c c biên t i ưu.



19
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(a) (x) = 4x1 −6x2 +3x3 → min
f
 −2x +4x −x3 0
1 2





 3x1 −5x2 +2x3 1




−x1 −2x3 −2



−3x2 +x3 2






−x2 −2

x1


x∗ = (2, 1, 0)
f (x) = x2 +2x3 −2x4 −2x5 → max

−2x1 +3x2 +x3 x5 = 4






(b)  4x1 −5x2

+3x4 −x5 = −6


x1 +2x2 +2x3 −x4 = 3







xj 0 , j = 1, .., 5



x∗ = (1, 2, 0, 0, 0)

Bài 2.13. Cho quy ho ch tuy n tính

f (x) = x1 +x2 → max

 2x1 −2x2 −1






x2 0



−1
x1 +2x2







−x1 +4x2 3



2 1 71
Trong các đi m x1 = (−1, 0), x2 = − , − , x3 = (−7, −1), x4 = − , − ,
3 6 99
đi m nào là phương án c c biên, phương án t i ưu c a bài toán đã cho?




20
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




Chương 3.

PHƯƠNG PHÁP ĐƠN HÌNH VÀ CÁC
THU T TOÁN C A NÓ


3.1. Cơ s lí lu n
Xét bài toán quy ho ch tuy n tính d ng chính t c

f (x) = cT x → min (1)

Ax = b (2)

x 0 (3)

V i A là ma tr n m × n, b ∈ Rm , c và x ∈ Rn , trong đó, A có h ng là m
(m ≤ n). Bài toán quy ho ch là không suy bi n, t t c phương án c c biên c a nó
đ u có s thành ph n dương b ng m và x∗ = (x01 , x02 , · · · , x0n ) là m t phương án
c c biên. Ký hi u J0 = {j : x0j > 0}. H véc tơ Aj : j ∈ J0 đ c l p tuy n tính,
cho nên các véc tơ Ai , i = 1, .., n đ u bi u th duy nh t qua cơ s Aj : j ∈ J0

Ai = xij Aj , i = 1,..,n (4)
j ∈J


N u g i B là ma tr n có các c t là Aj , j ∈ J0 và đ t xi = (xij ) ∈ Rm , j ∈ J0
thì Ai = Bxi hay xi = B −1 Ai , i = 1, ..., n.
N u đ t x0 = (x0 ) ∈ Rm , c0 = (c0 ) ∈ Rm v i j ∈ J0 thì f (x0 ) = cT x0 =
j j 0

c0 x0j , Bx0 = b.
j
j ∈J0


Đ nh nghĩa 3.1.1 (Ư c lư ng). Ta g i ∆i = c0T xi − ci , i = 1, . . . , n là ư c
lư ng c a bi n xi (hay c a véc tơ Ai ) ng v i cơ s J0 .



21
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Đ nh lý 3.1.2 (D u hi u t i ưu). N u phương án c c biên x∗ c a quy ho ch
0, i = 1, . . . , n thì x∗ là phương án t i ưu c a bài toán
tuy n tính có ∆i
(1),(2),(3).
Ch ng minh.

Xét phương án b t kì y = (yi ), ta có:
n n n
i j
xij yi .)Aj ; b = x0j Aj (do (4))
b= yi .A = yi ( xij .A ) = (
j ∈J0 j ∈J0 i=1 j ∈J0
i=1 i=1
n
⇒ x0j = xij yi . j = 1, 2, ..., n (5)
i=1

0 (∀i) suy ra c0T xi
T ∆i ci . Do đó, ta đư c:
n n
(c0T xi )yi
f (y ) = c i yi
i=1 i=1
n
= ( xij cj )yi
i=1 j ∈J0
n
= ( xij yi )cj
j ∈J0 i=1

= cj .x0j = f (x0 )
j ∈J0

V y, x0 là phương án t i ưu.

Đ nh lý 3.1.3 (D u hi u hàm m c tiêu không b ch n). N u phương án c c
biên x0 c a quy ho ch tuy n tính mà có j sao cho ∆j > 0 và xj ≤ 0 thì bài toán
(1),(2),(3) có hàm m c tiêu không b ch n.
Ch ng minh.

Ta có:

Ai = xij Aj (∀i) (theo (4))
j ∈J0

Gi


j ∈ J0
xij





di = (dij ) : dij =
−1 j=i



j ∈ J0 ∪ {i}

0 /



22
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Xét véc tơ x(θ) = x0 − θdi (θ ≥ 0), ta có:
n
xj (θ)Aj = (x0j − θx0j )Aj + θAi
j ∈Jo
j =1

x0j Aj + θ(Ai − x0j Aj ) = b + 0 = b.
=
j ∈Jo j ∈J0

Và xji ≤ 0 nên di ≤ 0 mà x0 ≥ 0, cho nên x(θ) ≥ 0 v i m i θ ≥ 0.
Do đó, x(θ) là phương án c a bài toán.
M t khác, ta th y
n
cj (x0j − θxij ) + θci
f x(θ) = c j x j (θ ) =
j ∈J0
j =1

cj x0j + θ (ci ) −
= cj xij
j ∈J0 j ∈J0

= f (x0 ) − θ∆i → −∞ khi θ → +∞ do ∆i > 0.

Do đó, hàm m c tiêu không b ch n.

Đ nh lý 3.1.4 (D u hi u xây d ng đư c phương án t i hơn). N u phương
án c c biên x0 c a quy ho ch tuy n tính t n t i j sao cho ∆j > 0 và xj có ít nh t
m t thành ph n dương thì có th xây d ng đư c phương án t t hơn x0 .
Ch ng minh.

Xét véc tơ x(θ) = x0 − θdi(θ > 0). v i


j ∈ J0
xij





di = (dij ) : dij =
−1 j=i



j ∈ J0 ∪ {i}

0 /


Theo trên, Ax(θ) = b và f (x(θ)) = f (x0 ) − θ∆i < f (x0 ) vì θ > 0 và ∆i > 0.
Tuy nhiên, xji còn có j mà xji > 0 nên không b o đ m cho x(θ) ≥ 0, v i m i
θ > 0.
Giá tr l n nh t c a θ đ có x(θ) ≥ 0 là
x0j x0r
θ0 = min : xij > 0, j = 1, 2, ..., m =
xij xir
B ng cách đ t x = x(θ0 ) đư c phương án m i t t hơn phương án đã cho.

23
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Nh n xét 3.1.5. Ar là véc tơ đưa ra ngoài cơ s (J0 ), còn Ai là véc tơ (vào) cơ s
(J0 ). Vi c ch n véc tơ vào cơ s , thư ng theo quy t c: max {∆i : i = 1, . . . , n} = ∆v
khi đó Av là véc tơ vào cơ s .



3.2. Thu t toán đơn hình
3.2.1 Thu t toán đơn hình

Thu t toán đơn hình đ gi i quy ho ch tuy n tính d ng chính t c khi bi t phương
án c c biên x∗ .

B1. Ki m tra t i ưu.
Xác đ nh: c0 , xi = B −1 Ai , i = 0, 1, . . . , n. Tính ∆i = c0T xi − ci , i = 1, . . . , n.
N u ∆i > 0, ∀i thì x∗ là phương án t i ưu. Thu t toán k t thúc. Ngư c l i,
chuy n sang B2.

B2. Ki m tra hàm m c tiêu bài toán không b ch n.
N u t n t i k : ∆k > 0 và xk ≤ 0 thì bài toán có hàm m c tiêu không b ch n.
Thu t toán k t thúc. Ngư c l i, chuy n sang B3.

B3. Xây d ng phương án c c biên m i t t hơn.

(i) Tìm véc tơ đưa vào cơ s : N u max ∆i : i = 1, . . . , n = ∆v thì Av đư c
ch n đưa vào cơ s .
x0i x0r
thì ta ch n Ar
(ii) Tìm véc tơ đưa ra cơ s : N u min : xvi > 0 =
xvi xv.r
đưa ra cơ s .

(iii) Xây d ng phương án c c biên m i ( ng v i cơ s v a xác đ nh m i).
B ng phép bi n đ i dòng, ngư i ta g i là phép xoay, ta có phương án
c c biên m i. Chuy n tr l i B1.


3.2.2 B ng đơn hình

Thu t toán đơn hình thư ng đư c bi u di n dư i d ng b ng. M i bư c ng v i
m t phương án c c biên là m t b ng đơn hình.

24
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


M i b ng đơn hình g m 3 + n c t: c t c0 , c t th hai ghi các véctơ trong cơ s ,
c t th ba ghi x0 . Dòng trên cùng ghi véctơ h s hàm m c tiêu c, dòng th hai
ghi các véctơ xj mà các thành ph n c a nó đư c ghi vào c t tương ng. Dòng cu i
cùng ghi f = f (x) và các ∆j , j = 1, . . . , n mà các giá tr c a nó đư c tính ngay
trên b ng đơn hình này.

• f (x) = c0T x0 : Tích vô hư ng c a c0 và x0 .

• ∆j = c0T xj − cj : Tích vô hư ng c a c0 và xj tr đi cj .

Sau khi tính các ư c lư ng ta ti n hành ki m tra tính t i ưu, tính không b
ch n c a hàm m c tiêu. N u th a m t trong hai tính ch t trên thì thu t toán k t
thúc, còn không thì ta xây d ng phương án c c biên m i, tương ng v i b ng đơn
hình m i.
Đ xây d ng b ng đơn hình ti p theo, ta l n lư t làm các vi c sau:

(I) Tìm c t xoay: N u phương án chưa th a tính t i ưu thì c t (v ) ng v i véc
tơ đưa vào cơ s Av là c t xoay.

(II) Tìm dòng xoay: Theo quy t c tìm véc tơ đưa ra cơ s , n u tìm đư c véc tơ
đưa ra là Ar thì dòng r là dòng xoay.

(III) Th c hi n phép xoay: Ta có dòng Ar c a ma tr n A là dòng xoay, c t Av
c a ma tr n A là c t xoay,thì (xvr ) g i là ph n t tr c. Khi đó, ta xây d ng
đư c b ng đơn hình m i b ng phép xoay.

T b ng đơn hình, ta l p b ng ti p theo như sau:

• Trên dòng xoay thay Ar b i Av sau đó th c hi n phép xoay.

• Chia m i ph n t c a dòng xoay cho ph n t c a tr c xvr , như v y s 1 xu t
hi n t i v trí tr c.

• Đ tính dòng i m i i ∈ J \ {r}, ta l y dòng i c tr đi tích c a dòng xoay đã
bi n đ i v i ph n t n m giuao gi a hai dòng đang tính và c t xoay (k c
dòng ư c lư ng).

25
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ví d 3.2.3. Gi i bài toán quy ho ch tuy n tính sau:


f (x) = x1 −x2 +2x3 −2x4 −3x6 → min
−x6
x1 +x3 +x4 =2
x2 +x4 +x6 = 12
4x3 +2x4 +x5 +3x6 =9

xj 0, j = 1, ..., 6

Gi i

Bài toán có d ng chu n t c.

C 0 Cơ 1 -1 2 -2 0 -3
x0 x1 x2 x3 x4 x5 x6
s
A1
1 2 1 0 1 1 0 -1
A2
-1 12 0 1 0 1 0 1
A5
0 9 0 0 4 2 1 3
(2)
f -10 0 0 -1 0 1
A4 2 1 0 1 1 0 -1
A2 10 -1 1 -1 0 0 2
A5 5 -2 0 2 0 1 5
(3)
f -14 -2 0 -3 0 0
A4 3 0.6 0 1.4 1 0.2 0
A3 8 -0.2 1 -1.8 0 -0.4 0
A6 1 -0.4 0 0.4 0 0.2 1
f -17 -0.8 0 -42 0 -0.6 0


Ta th y ngay phương án phương án c c biên x∗ = (2, 12, 0, 0, 9, 0) tương ng
v i cơ s {A1 , A2 , A5 }.




26
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


3.2.4 Trư ng h p bài toán suy bi n

Trư ng h p bài toán suy bi n, đ tránh xoay vòng ta có th s d ng quy t c Blac
đ ch n véc tơ vào cơ s :

Av là véc tơ vào n u v = min{i : ∆i > 0}.

Tuy nhiên, xoay vòng hi n g p.


3.2.5 Tìm phương án c c biên và cơ s ban đ u

Thu t toán đơn hình g c, áp d ng gi i quy ho ch tuy n tính khi đưa d ng chính
t c, có s n cơ s đơn v và phương án c c biên. Tuy nhiên không ph i lúc nào cũng
g p may như v y. Trong trư ng h p đó, ta phài tìm cách đưa v d ng có th áp
d ng thu t toán đơn hình mà tìm ra phương án c c biên xu t phát. M t trong
nh ng cách đó là dùng bi n gi s đư c trình bày dư i đây, có hai d ng: Hai pha
và đánh thu .
Thu t toán đơn hình hai pha
Bài toán g c, bài toán b tr
Gi s c n gi i bài toán (mà ta s g i là bài toán g c):

 f (x) = cT x → min




Ax = b




x 0


b 0

Tương ng v i bài toán g c, ta l p bài toán b tr sau:

 F (x, w) = xn+1 + xn+2 + ..... + xn+m → min




Ax + w = b




x 0; W 0



Trong đó, wT = (xn+1 , xn+2 , . . . , xn+m ) và xn+i là các bi n thêm vào, g i là bi n
gi i = 1, 2, .., m. Các véc tơ An+i là các véc tơ đơn v gi i = 1, 2, . . . , m.

27
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


M i liên h bài toán g c và bài toán b tr
G i t p phương án bài toán g c và b tr là P và P .
Ta th y, x ∈ P khi và ch khi (x, 0) ∈ P ; x là phương án c c biên bài toán g c
khi và ch khi (x, 0) là phương án c c biên bài toán b tr .
Xét bài toán b tr .

+ P = ∅ vì (0, b) ∈ P và F (x, w) ≥ 0. Do đó, bài toán b tr luôn có phương
án t i ưu.

+ Bài toán b tr có d ng chính t c, có s n cơ s đơn v và phương án c c biên
nên áp d ng phương pháp đơn hình g c đ gi i. Tìm đư c phương án cưc
biên t i ưu là (x, w) = (x1 , . . . , xn , xn+1 , . . . , xn+m ). Hãy xét hai trư ng h p
w = 0 và w = 0.

* w = 0, suy ra, t n t i xn+i > 0. Khi đó, bài toán g c có t p phương án
P = ∅.
Th t v y, n u t n t i x ∈ P thì (x, 0) ∈ P và F (x, 0) = 0 và t i xn+i > 0
thì Fmin = F (x, w) > 0 > F (x, 0) vô lí. Do đó, P = ∅.

* w = 0. T c là m i bi n gi b ng 0, khi đó, x là phương án c c biên c a
bài toán g c.
Lúc w = 0 thì Fmin = F (x, w) = 0 và (x, 0) là phương án c c biên c a
bài toán b tr nên là phương án c c biên c a bài toán g c.

Thu t toán hai pha.
Pha 1. Tìm phương án c c biên cho bài toán g c.

(i) L p bài toán b tr . L p bi n gi ng cho nh ng véc tơ đơn v còn thi u.

(ii) Gi i bài toán b tr , áp d ng phương pháp đơn hình đ gi i, tìm Fmin .
N u Fmin = 0 thì t p P = ∅. D ng.
N u Fmin = 0 thì tìm đư c x∗ là phương án c c biên cho bài toán g c chuy n
sang pha 2.

Pha 2. Tìm phương án c c biên t i ưu, áp d ng phương pháp đơn hình đ gi i.

28
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ví d 3.2.6. Gi i quy ho ch tuy n tính

f (x) = 2x1 + 6x2 − 5x3 + x4 + 4x5 → min

 x1 −4x2 +2x3 −5x4 +9x5 = 3




−3x3 +4x4 −5x5 = 6
x2



−x3 −x5 = 1
x2 +x4



xj 0, j = 1, .., 5

Gi i

Ta đưa vào hai bi n gi là x6 , x7 cho các ràng bu c th (2) và (3). Khi đó, ta đư c
bài toán b tr sau.

F (x) = x6 + x7 → min

 x1 −4x2 +2x3 −5x4 +9x5 = 3




−3x3 +4x4 −5x5 + x6 = 6
x2



−x3 −x5 + x7 = 1
x2 +x4



xj 0, j = 1, .., 7

Các b ng đơn hình gi i bài toán trên là




29
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


V y, phương án t i ưu x = (14, 0, 16, 31, 0) và fmin = 7.

Nh n xét 3.2.7.

+ Nh p s li u lúc đ u h s xi c a F là 0 n u nó là bi n, còn bi n gi là 1.

+ Pha 1. K t thúc sau 3 bu c l p, d u hi u t i ưu bài toán b tr xu t hi n,
trong cơ s không có bi n gi . Ta tìm đư c phương án c c biên cho bài toán
g c.

+ Pha 2. Ta ph i tính ư c lư ng tương ng phương án tìm đư c.

Ví d 3.2.8. Gi i quy ho ch tuy n tính.

f (x) = 7x1 + x2 − 4x3 → min

 −6x1 +4x2 +5x3 −20




x +2x2 x3 = 8
1



−x3 −8
 3x1 +2x2


xj 0, j = 1, 2, 3

Gi i

Ta ch n bi n bù x4 , x5 ta đưa bài toán d ng chính t c v i b ≥ 0 như sau.

f (x) = 7x1 + x2 − 4x3 → min

−4x2 −5x3 + x4 = 20
 6x1




x +2x x3 = 8
1 2



 −3x1 −2x2 +x3 − x5 = 8


xj 0, j = 1, 2, 3, 4, 5

Ti p t c ch n bi n gi x6 , x7 , ta có bài toán b tr sau.

F (x) = x6 + x7 → min

−4x2 −5x3 + x4 = 20
 6x1




x +2x x +x =8
1 2 3 6



 −3x1 −2x2 +x3 − x5 + x7 = 8


xj 0, j = 1, 2, 3, 4, 5, 6, 7

30
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ta có b ng đơn hình sau:

C0 Cơ 0 7 1 -4 0 0
x0 x1 x2 x3 x4 x5
s
A4
0 20 6 -4 -5 1 0
A6
1 8 1 2 1 0 0
A7
1 8 -3 2 1 0 -1
F 16 -2 4 2 0 -1
A4
0 36 8 0 -3 1 1
A2
1 4 0.5 1 0.5 0 0
A7
0 0 -4 0 0 0 -1
F 0 -4 0 0 0 -1
f 4 -6.5 0 4.5 0 0
A4 60 11 6 0 1 1
A3 8 1 2 1 0 0
A7 0 -4 0 0 0 -1
f -32 -11 -9 0 0 0


V y, phương án t i ưu x = (0, 0, 8) và fmin = −32.

Nh n xét 3.2.9. Bư c 2 k t thúc pha 1, tuy cơ s còn bi n gi nhưng giá tr b ng
là 0. Do đó, ta tìm đư c phương án c c biên suy bi n cho bài toán g c.

Thu t toán đánh thu (Thu t toán bài toán(M)).
Bài toán M-l n
Ta có th k t h p hai pha c a phương pháp hai pha thành m t nh phương
pháp đánh thu vào bi n gi . T bài toán xu t phát d ng chính t c, ta l p bài
toán M-l n như sau.

F (x, w) = cT x + M (xn+1 , xn+2 , ..., xn+m ) → min

 Ax + w = 0


x 0, w 0




31
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Trong đó w = (xn+1 , xn+2 , . . . , xn+m ), xn+1 , xn+2 , . . . , xn+m g i là các bi n gi .
M là s dương r t l n (l n hơn b t c s nào c n so sánh). ng v i m i bi n gi
thì có h s hàm m c tiêu c a nó là M , như là s đánh thu vào bi n gi .
M i liên h bài toán g c và bài toán M-l n



Đ nh lý 3.2.10 (Quan h gi a bài toán g c và M -l n). Xem bài toán g c và
bài toán M -l n tương ng thì

(a) N u bài toán g c có phương án thì m i phương án c c biên t i ưu c a bài toán
M-l n ph i có w = 0.

(a) N u bài toán g c có phương án t i ưu x thì bài toán M-l n ph i có ít phương
án t i ưu (x, 0) và ngư c l i.

Nh n xét 3.2.11. Như v y, đ gi i bài toán g c, ta có th gi i bài toán M-l n
tương ng. Khi bài toán M-l n không có phương án ho c có phương án c c biên
t i ưu (x, w).


V i w = 0 thì bài toán g c không có phương án nào c ; n u nó có phương án
t i ưu d ng (x, 0) thì x là phương án t i ưu bài toán g c.

Thu t toán đánh thu

(i) L p bài toán M -l n. L p bi n gi ng cho nh ng véc tơ đơn v còn thi u.
L p b ng đơn hình xu t pháp: Các ư c lư ng có d ng ∆i = αi + βi M nên
tách ra hai dòng. Dòng trên là αi , dòng dư i là βi . Ta có th b c t bi n gi
không l p.

(ii) Áp d ng phương pháp đơn hình gi i.
Khi gi i, so sánh các ư c lư ng ∆i = αi + βi M , ta áp d ng theo quy t c:

(a) ∆i < 0 n u βi < 0 ho c (βi = 0 và αi < 0).

(b) ∆i > 0 n u βi > 0 ho c (βi = 0 và αi > 0).

32
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(c) ∆i < ∆j n u βi < βj ho c (βi = βj và αi < αj ).

D u hi u bài toán g c có t p phương án r ng là phương án t i ưu c a bài
toán M -l n là (x, w) mà w = 0 ho c Fmin (x, w) == α0 + β0 M mà β0 = 0.

Ví d 3.2.12. Gi i quy ho ch tuy n tính sau:

f (x) = −3x1 + x2 + 3x3 − x4 → min

−x3
 x1 +2x2 +x4 = 2




−6x2 +3x3 +3x4 = 9
2x
1



−x2 −x4 = 6
 x1 +x3


xj 0, j = 1, 2, 3, 4

Gi i

Ta ch n bi n gi x5 , x6 , x7 , ta có bài toán M-l n tương ng sau

F (x) = −3x1 + x2 + 3x3 − x4 + M (x5 + x6 + x7 ) → min

−x3
 x1 +2x2 +x4 + x5 = 2




−6x2 +3x3 +3x4 + x6 = 9
2x
1



−x2 −x4 + x7 = 6
 x1 +x3


xj 0, j = 1, 2, 3, 4, 5, 6, 7

Ta có các b ng đơn hình.

C0 Cơ 0 -3 1 3 -1
x0 x1 x2 x3 x4
s
A5
M 2 1 2 -1 1
A6
M 9 2 -6 3 3
A7
M 6 1 -1 1 -1
F 0 3 -1 -3 1
17 4 -5 3 3
A1 2 1 2 -1 1
A6 5 0 -10 5 1
A7 4 0 33 -3 2 -2
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



F -6 0 -7 0 -2
9 0 -13 7 -1
A1 3 1 0 0 1.2
A3 1 0 - 21 0.2
A7 2 0 1 0 -2.4
F -6 0 -7 0 -2
2 0 1 0 -2.4
A1 3 1 0 0 1.2
A3 5 0 0 1 -4.6
A2 2 0 1 0 -2.4
F 8 0 0 0 -18.8
0 0 0 0 0


V y, nghi m t i ưu bài toán x = (3, 2, 5, 0) và fmin = 8.

Ví d 3.2.13. Gi i quy ho ch tuy n tính

f (x) = 2x1 − 2x2 + 3x3 → min

 2x1 + 2x2 − x3 1
 x − x − 3x 1
1 2 3

xj 0, j = 1, 2, 3

Gi i

G i hai bi n bù x4 , x5 , đưa bài toán v d ng chính t c và x6 là bi n gi , ta có
bài toán M -l n sau.

F (x) = 2x1 − 2x2 + 3x3 + M x6 → min

2x1 + 2x2 − x3 + x4 = 1

 x − x − 3x − x + x = 1
1 2 3 5 6

xj 0, j = 1, 2, 3, 4, 5, 6

Ta có các b ng đơn hình sau:

34
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



C0 Cơ 0 2 -2 3 0 0
x0 x1 x2 x3 x4 x5
s
A4
0 1 2 2 -1 1 0
A6
M 1 1 -1 -3 0 -1
F 0 -2 2 -3 0 0
1 1 -1 -3 0 -1
A1 0.5 1 1 -0.5 0.5 0
A6 0.5 0 -2 -2.5 -0.5 -1
F 1 0 4 -4 1 0
0.5 0 -2 -2.5 -0.5 -1

V y, bài toán đã cho có t p phương án r ng. Do bài toán M -l n có phương
án t i ưu x = (0.5, 0, 0, 0, 0, 0.5) có bi n gi x6 = 0.5 > 0.



3.3. Bài t p chương 3
Bài 3.1. Cho bài toán quy ho ch tuy n tính:

3x1 + 2x2 + 5x3 − 2x4 → min (3.3.1)

+7x3 −3x4
 x1 =7




xj ≥ 0, j = 1, 2, 3, 4, 5. (3.3.2)
x2 −2x3 +x4 =1



−x4 +x5 = 16
3x3





(a) Tìm phương án c c biên x ng v i cơ s A3 , A4 , A5 .

(b) Đ i v i phương án c c biên x hãy tính các ư c lư ng ∆j , j = 1, 2, 3, 4, 5. T
đó suy ra tính t i ưu c a x.

Bài 3.2. Gi i các bài toán quy ho ch sau b ng thu t toán đơn hình (tên g i chung
cho thu t toán đơn hình g c, thu t toán hai pha, thu t toán bài toán M và c
thu t toán đơn hình đ i ng u)



35
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(a) f (x) = 3x1 + 2x2 + 5x3 − 2x4 → min

+7x3 −3x4
 x1 =7




x2 −2x3 +x4 =1



3x3 −x4 +x5 = 16


xj ≥ 0, j = 1, 2, 3, 4, 5.

(b) f (x) = 3x1 + 3x2 + 2x3 + 7x4 → max

 3x1 +2x2 +x3 +3x4 +2x5 ≤ 15

+x5 ≤ 19
 x +2x +x +4x
1 2 3 4
xj ≥ 0, j = 1, 2, 3, 4, 5.

(c) f (x) = x1 − 2x2 → min

 −x1 +x2 ≤ 2
 x −2x ≤ 3
1 2
x1 ≥ 0, x2 ≥ 0.

(d) f (x) = 2x1 + 4x2 + x3 + x4 → max

+x4 ≤ 4
 x1 +3x2




≤3
2x1 +x2



x2 +4x3 +x4 ≤ 3


xj ≥ 0, j = 1, 2, 3, 4

(e) f (x) = −3x2 + 2x4 + 2x6 → min

 x1 +5x4 +x5 +2x6 = 10




−x4
x2 +x5 =3



x3 −5x4 −3x5 +8x6 =1


xj ≥ 0, j = 1, 2, 3, 4, 5, 6.

(f) f (x) = −x1 + x2 − x3 − x4 + 2x5 + 2x6 → min

 x1 +x2 +x3 +x4 = 10




−x3 +2x4 +x5
x2 =0



2x2 +x3 +8x4 +x6 = 30


xj ≥ 0, j = 1, 2, 3, 4, 5, 6.

(g) f (x) = x1 + x2 + x3 → min


36
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


−x4 −2x6 = 5
 x1




+2x4 −3x5 x6
x2 =3



+x3 +2x4 −5x5 +6x6 = 5


xj ≥ 0, j = 1, 2, 3, 4, 5, 6.

(h) f (x) = x2 − 3x4 + x5 + 6x6 → min

−x4 −2x6 = 7
 x1




x2 +x3 4x5 7x6 = 9



x2 3x6 = 4


xj ≥ 0, j = 1, 2, 3, 4, 5, 6.
Xu t phát t phương án c c biên x = (1, 4, 3, 0, 0, 0)

(i) f (x) = −5x1 + x2 − 2x3 + 5x4 → max

−x2 ≤7
 x1 +2x3




+3x3 −3x4 ≤ 9
2x1 +x2



3x1 −2x2 +x3 ≤ 30
+x4


xj ≥ 0, j = 1, 2, 3, 4.

(j) f (x) = −11x1 + 3x2 − x3 + 11x4 → min

−x2 +4x3 −3x4 ≤ 5
 x1




−2x −2x ≤4
x
1 3 4


 2x1 −x2 −x3 +x4 ≤ 6

xj ≥ 0, j = 1, 2, 3, 4.

Bài 3.3. Gi i và bi n lu n bài toán sau theo tham s t:
f (x) = 2x1 + tx2 + x3 → min

+8x2 −2x3 ≤ 1
 6x1




−8x ≤3
2x +x
1 2 3



 −x1 −5x2 +x3 ≤2

xj ≥ 0, j = 1, 2, 3.

Bài 3.4. Gi i bài toán sau xu t phát t phương án c c biên x = (1, 2, 0, 3)
f (x) = 2x1 − x2 − 15x3 + 4x4 → max



37
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


+2x2 −x3
 x1 x4 =8




−x −x4 = −2
+x +x3
1 2



 3x1 −x2 +4x3 +x4 = 4

xj ≥ 0, j = 1, 2, 3, 4.

Bài 3.5. Cho bài toán quy ho ch

f (x) = −x1 + x2 − 2x3 − 3x4 + 4x5 → min

−4x4 +3x5 ≤ 34
3x2






−2x5 = 24
 x1 +4x2 +x4


+2x4 −3x5 ≤ 12
7x2




1 1


− x5 = 5
x2 +x3


2 2
xj ≥ 0, j = 1, 2, 3, 4, 5.




(a) Hãy gi i bài toán trên b ng thu t toán đơn hình.

(b) Hãy gi i bài toán đã cho khi có thêm ràng bu c f (x) ≥ −106.

Bài 3.6. Cho bài toán v i tham s t

f (x) = −x1 + x3 − tx4 → min

 −x +x 12x −2tx4 +4x5 =9
1 2 3





+8x3 +(1 − t)x4 +2x5
 2x1 = 14


+(t − 1)x4 −3x5 = 4
x
1


1 1


− x5 = 5
x2 +x3


2 2
xj ≥ 0, j = 1, 2, 3, 4, 5.




(a) Bi t r ng x là m t phương án c c biên ng v i cơ s A1 , A2 , A5 . Hãy l p
b ng đơn hình ng v i x.



38
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(b) T b ng đơn hình v a l p đư c, hãy tìm t p t t c các giá tr c a t sao cho
x là phương án t i ưu.

(c) Gi i bài toán đã cho khi t = 1 và t = 3.

Bài 3.7. Gi i các bài toán quy ho ch tuy n tính sau b ng thu t toán hai pha

(a) f (x) = 2x1 + 6x2 − 5x3 + x4 + 4x5 → min

 x1 −4x2 +2x3 −5x4 +9x5 = 3




x2 −3x3 +4x4 −5x5 = 6



x2 −x3 +x4 −x5 = 1


xj ≥ 0, j = 1, 2, 3, 4, 5.

(b) f (x) = 7x1 + x2 − 4x3 → min

 −6x1 +4x2 +5x3 ≥ −20




x1 +2x2 +x3 =8



3x1 −2x2 −x3 ≤ −8


xj ≥ 0, j = 1, 2, 3.

(c) f (x) = −x1 + 3x3 − x4 → min

−x3 +2x4 = 1
 x1




−2x4 = 2
2x +x +4x
1 2 3



 3x1 +x2 +3x3 =3


xj ≥ 0, j = 1, 2, 3, 4.

(d) f (x) = x1 − 2x2 + 3x3 → min

 2x1 +x2 +3x3 = 2




2x +3x2 4x3 = 1
1



−x2 +3x3 ≤ 4
 x1

xj ≥ 0, j = 1, 2, 3.

(e) f (x) = 2x1 + x2 − x3 − 4x4 → max




39
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


 2x +2x −x ≤ 1
1 2 3





 x1 +3x2 +x3 ≤ −2


 3x1 +4x2 −x3 ≤ 3





≥0
x


3

Bài 3.8. Gi i các bài toán sau b ng thu t toán M :

(a) f (x) = 4x1 + 5x2 − 2x3 → min

x2 +x3 ≤ 6
 x1




3x2 −x3 = 1
2x1



x1 +2x2 −x3 = 0


xj ≥ 0, j = 1, 2, 3.

(b) f (x) = x1 + x2 − x3 → min

−x2
 2x1 +x3 = 2




−x
4x +2x =1
1 2 3



 x1 +2x2 −4x3 ≤ 4


xj ≥ 0, j = 1, 2, 3.

(c) f (x) = x1 − 3x2 → max

 4x1 +3x2 ≤ 12




−x1 ≤5
+x2



≤6
x1 +5x2


x1 ≥ 0.

(d) f (x) = −3x1 + 2x2 → max

x1 −tx2 ≤ 1

 −x +x2 ≥ 1
1
xj ≥ 0, j = 1, 2, 3, 4
(Bi n luân theo tham s t > 0).

(e) f (x) = 5x1 − x2 + x3 − 10x4 + 7x5 → max

 3x1 −x2 −x3 =4




−x
x +x +x4 =1
1 2 3



 2x1 +x2 +2x3 +x5 = 7



40
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


xj ≥ 0, j = 1, 2, 3, 4, 5.

(f) f (x) = x4 − x5 → max

−x3 −x4 x5 ≥0
2x2






+2x3 −x4 +x5 ≥ 0
2x1



−2x2 −x4 +x5 ≥ 0
x
1




x +x2 +x3 =1

1
xj ≥ 0, j = 1, 2, 3, 4, 5.

(g) f (x) = −3x1 + x2 + 3x3 − x4 → min

+2x2 −x3
 x1 +x4 =0




−2x
2x +3x +3x =9
1 2 3 4



 x1 −x2 +2x3 −x4 = 6

xj ≥ 0, j = 1, 2, 3, 4.




41
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




Chương 4.

BÀI TOÁN QUY HO CH TUY N
TÍNH Đ I NG U VÀ THU T TOÁN
ĐƠN HÌNH Đ I NG U


4.1. Bài toán quy ho ch tuy n tính đ i ng u
Đ nh nghĩa 4.1.1 (Bài toán đ i ng u). Cho các bài toán quy ho ch tuy n tính:

f (x) = cT x → min g (x) = bT y → max
 
 AT x bi ; i ∈ M1 0 , i ∈ M1
 yi
i
 

 
 
AT x b ;i ∈ M 0, i ∈ M
y
i 2 i 2
i
 
 
T
(a)  Ai x = bi ; i ∈ M3 (b)  yi ∈ R , i ∈ M3

 
 y T AJ
0 ; j ∈ N1 cj , j ∈ N1
 xj
 
 
 
 
y T AJ
0 ; j ∈ N2 cj , j ∈ N2
xj
 
 
 
y T AJ = cj , j ∈ N3
 
xj ∈ R; j ∈ N3
 


Ngư i ta g i bài toán (a) là bài toán g c và (b) là bài toán đ i ng u.
Trong đó AT là véc tơ dòng i c a ma tr n A, Aj là véc tơ c t j c a ma tr m A.
i

M i ràng bu c b t đ ng th c c a bài toán này ng v i m t bi n trong ràng
bu c v d u c a bài toán kia, g i là c p ràng bu c đ i ng u. Đ ng th i các chi u
c a b t đ ng th c có quan h v i nhau th hi n b ng sau:




42
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Góc min max Đ i ng u
∈R
= bi
Ràng bu c ≤ bi ≤0 Bi n
≥ bi ≥0
≥0 ≤ ci
≤0 ≥ ci Ràng bu c
Bi n
∈R = ci

Ví d 4.1.2. Xét quy ho ch tuy n tính bên trái và bài toán đ i ng u bên ph i,
các bài toán sau:
g (y ) = 5y1 + 6y2 + 4y3 → max f (x) = x1 + x2 + 3x3 → min
 
 −x1 +3x2  −y1 +2y2
=5 1
 
 
 
 
(a) (b)
−x2 − y2
2x1 +3x3 6 3y1 1
 
 
 
x3 4 3y2 +y3 = 3
 
 

y2 0, y3 0 x1 0, x2 0

Nh n xét 4.1.3. Quan h đ i ng u gi a các bài toán quy ho ch tuy n tính có
tính ch t đ i x ng.

Đ nh lý 4.1.4 (Đ i ng u y u). N u x, y l n lư t là phương án c a bài toán quy
ho ch tuy n tính g c và đ i ng u thì g (y ) ≤ f (x).
Ch ng minh.

Ta đ t

ui = yi (AT x − bi ), i = 1, . . . , m
i
(4.1.1)
vj = (cj − y T Aj )xj , j = 1, . . . , n

Theo đ nh nghĩa bài toán đ i ng u, thì yi và AT x − bi cùng d u, cj − y T Aj và
i

xj cùng d u. Do đó, ui ≥ 0 và vj ≥ 0 v i m i i, j .
Ta có
m
ui = y T Ax − y T b;
i=1
n
vj = cT x − y T Ax;
j =1


43
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


vj = cT x − y T b = f (x) − g (y ) ⇒ g (y )
Do đó, 0 ui + f (x)
i j

H qu 4.1.5. Gi s x, y là phương án c a bài toán g c và đ i ng u. N u f (x) =
g (y ) thì x, y l n lư t là phương án t i ưu c a bài toán g c và đ i ng u.
Ch ng minh.

Đ i v i m i x, y là phương án bài toán g c và đ i ng u thì g (y ) ≤ f (x) =
g (y ) ≤ f (x). Ch ng t tính t i ưu c a x, y.

Đ nh lý 4.1.6 (Đ i ng u m nh). M t c p bài toán đ i ng u, n u bài toán này
có phương án t i ưu thì bài toán kia cũng có phương án t i ưu và giá tri t i ưu c a
chúng b ng nhau.
Ch ng minh.

Gi s bài toán g c có phương án t i ưu. Do đó bài toán d ng chính t c tương
T ∧−1
0
x0 c0
v i ma tr n cơ s B . Khi đó, y =
ng nó có phương án t i ưu là B là
phương án c a bài toán đ i ng u. G i x0 là phương án t i ưu bài toán g c thu
đư c t x0 . Ta có:

g (y 0 ) = y 0T b = (c0T B −1 )b = c0T x0 = f (x0 )

V y, y 0 là phương án t i ưu bài toán đ i ng u.

Đ nh lý 4.1.7 (S t n t i phương án). Đ i v i c p bài toán g c-đ i ng u c a
quy ho ch tuy n tính ch có m t trong ba trư ng h p sau x y ra:

(i) C hai cùng có t p phương án r ng.

(ii) C hai cùng có phương án t i ưu và giá tr hàm m c tiêu c a chúng b ng
nhau.

(iii) Bài toán này có hàm m c tiêu không b ch n, còn bài toán kia có t p phương
án r ng
Ch ng minh.

Theo đ nh lí đ i ng u m nh, ta có (ii). N u không có (ii) thì x y ra (i) ho c
(iii).
Theo đ nh lí đ i ng u y u, thì có (iii). B ng ví d ch ra có (i).

44
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Đ nh lý 4.1.8 (Đ l ch bù). Gi s x và y là phương án c a bài toán g c-đ i
ng u tương ng. Khi đó, x và y là t i ưu khi và ch khi

yi (AT x − bi ) = 0 ∀i (4.1.2)
i


cj − y T AJ xj = 0 ∀j (4.1.3)

Ch ng minh.

vj = cT x − y T b = f (x) − g (y ) và x, y là c p phương án t i
Ta có 0 ui +
i j
ưu thì f (x) = g (y ). Khí đó, ui = 0 và vj = 0 v i m i i, j . Do đó

yi (AT x − bi ) = 0 ∀i (4.1.4)
i


cj − y T A J x j = 0 ∀j (4.1.5)

Đ nh lý đư c ch ng minh.

Ví d 4.1.9. Ki m tra tính t i ưu c a phương án x∗ = (2, 0, 1, −2, 3) c a bài toán
quy ho ch tuy n tính.

f (x) = −4x1 + 9x2 + 16x3 − 8x4 − 20x5 → min

−x3
 5x1 +4x2 +3x4 +x5 5




−x +4x3 −2x4 −5x5 −9
+2x
1 2



 −x1 −2x2 −x3 +2x4 +3x5 = 2


xj 0, j = 1, 2, 3

Gi i

G i y = (y1 , y2 , y3 ) là phương án bài toán đ i ng u tương ng x∗ .
Ta có A1 x∗ = 6 > 5, A2 x∗ = −9, A3 x∗ = 2 nên y1 = 0. M t khác, xét x∗ ta
có x∗ , x∗ , x∗ , x∗ khác 0 nên
1345
 
 
−4 
 −1 −1      

 
 4 −1  y2
    16
y = 4
  2

⇔
  = 

  
 −2 2   −8
 y3  y3 = 0


  
   
−5 3 −20

45
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


và f (x∗ ) = −36, g (y ) = −36.
V y, x∗ là phương án t i ưu.

Ví d 4.1.10. Cho bài toán quy ho ch tuy n tính

f (x) = 6x1 + 2x2 + 7x3 + 8x4 − 5x5 − 9x6 → min

 −2x1 −x3
+x2 +3x4 +2x5 7




−3x2 +2x3 +4x4 −x5 − 3x6 −8



−2x2 +4x3 −3x4 −5x5 − 3x6 = −22
x1



xj 0, j = 1, 2, 3, 4, 5, 6




(a) Ch ng t x∗ = (0, 0, 9, 0, 8, 6), y ∗ = (3, 1, 2) tương ng là phương án t i ưu
c a bài toán đã cho và bài toán đ i ng u c a nó.

(b) Tìm t p phương án t i ưu c a bài toán đã cho.

Gi i

(a) Xét x∗ , ta th y x∗ ≥ 0 v i m i j .
j

A1 x∗ = 7, A2 x∗ = −8, A3 x∗ = −22. Nên x∗ là phương án và f (x∗) = −31.
Tương t , xét y ∗ , ta th y yi ≥ 0 v i m i i.




AT y ∗ = −4 ≤ 6, AT y ∗ = −4 ≤ 2, AT y ∗ = 7 ≤ 7
1 2 3

AT y ∗ = 7 ≤ 8, AT y ∗ = −5 ≤ −5, AT y ∗ = −9 ≤ −9
4 5 6


Do đó, y ∗ là phương án và g (y ∗ ) = −31.
V y x∗ , y ∗ tương ng là phương án t i ưu c a bài toán đã cho và bài toán đ i
ng u c a nó.
(b) Tìm t p phương án t i ưu c a bài toán đã cho.
G i x(xi ) là phương án t i ưu bài toán đã cho tương ng y ∗ .
T AT y ∗ = −4 < 6, AT = −4 < 2, AT = 7 < 8 mà ta l i có x1 = x2 = x4 = 0
1 2 4




46
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




f (x) = 7x3 − 5x5 − 9x6 = −31







−x3 + 2x5 ≥ 7





2x3 − x5 − 3x6 ≥ −8



4x − 5x − 3x = −22

3 5 6





xj ≥ 0, =; j = 3, 5, 6



x3 − 2x6 = −3







−x5 + x6 = −2





⇒ −x3 + 2x5 ≥ 7
 


2x − x − 3x ≥ −8

3 5 6





x ≥ 0, =; j = 3, 5, 6

j


x3 = −3 + 2t







x = 2 + t
5



x = t
6





t ≥ 3/2




V y, t p phương án t i ưu c a bài toán đã cho là T = {(0, 0, −3 + 2t, 0, 2 + t, t) :
t ≥ 3/2}



4.2. Thu t toán đơn hình đ i ng u
Thu t toán đơn hình đ i ng u là thu t toán đơn hình áp d ng vào gi i bài toán
đ i ng u c a quyb ho ch tuy n tính đã cho nhưng các bư c ti n hành l i đư c
di n t trên bài toán g c. Sau đây ta tìm hi u n i dung c a thu t toán đơn hình
đ i ng u.




47
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


4.2.1 Cơ s lí lu n

D u hi u t i ưu.
Ta xét bai toán d ng chính t c

f (x) = cT x −→ min (4.2.6)

Ax = b (4.2.7)

x≥0 (4.2.8)

và bài toán đ i ng u c a nó

g (y ) = bT y −→ max

AT y ≤ c

Trong đó A là ma tr n c m × n và A có h ng là m. B = {Aj : j ∈ JB } là m t cơ

T j
y A = c ; j ∈ J
j

s c a ma tr n A. B đư c g i là cơ s đ i ng u n u ,t c
T j
y A ≤ C ; j ∈ J
/B
j

là t n t i phương án c c biên y ng v i cơ s B c a bài toán đ i ng u.
Nh n xét.

• Ta có y T = c0T B −1 , suy ra y T Aj = (c0T B −1 )Aj = c0T (B −1 Aj ) = c0T xj =
∆j + cj v y B là cơ s đ i ng u khi và ch khi ∆j ≤ 0, ∀j .


khi j ∈ jB
x = x
j 0j
• Gi phương án. Đ t x0 = B −1 b = (x0j ), j ∈ jB và x =
khi j ∈ jB

x = 0 /
j

Ta g i x là gi phương án c a bài toán g c thì đó là phương án c c biên t i ưu.
T đó ta có d u hi u t i ưu sau.

Đ nh lý 4.2.2 (D u hi u t i ưu). B là cơ s đ i ng u c a quy ho ch tuy n
tính. N u x0 = B −1 b ≥ 0 thì y là phương án t i ưu c a bài toán đ i ng u và gi
phương án x là phương án t i ưu c a bài toán g c.

Đ nh lý 4.2.3 (D u hi u t p phương án r ng). N u t n t i j ∈ Jb sao cho
x0j < 0 và xji ≥ 0 v i m i i thì bài toán đ i ng u có hàm m c tiêu không b ch n.
Cho nên bài toán g c có t p phương án r ng.

48
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Đ nh lý 4.2.4 (D u hi u phương án c c bi n t t hơn). N u t n t i j sao
cho x0j < 0, đ ng th i v i t n t i i sao cho xji < 0 thì có th xây d ng đư c
phương án c c biên cho bài toán đ i ng u t t hơn.


4.2.5 Thu t toán đơn hình đ i ng u

Gi s đã có s n m t cơ s đơn v là cơ s đ i ng u c a bài toán (4.2.1), (4.2.2), (4.2.3).
Ta l p b ng đơn hình gi ng như thu t toán đơn hình g c theo các bư c sau:
Bư c 1. Đ t xj = Aj , (j = 0, 1, . . . , n), tính ∆j = ct xj − cj , j = 1, 2, . . . , n và
ct0 x0 .
Chuy n sang bư c 2.
Bư c 2. N u x0 ≥ 0 thì gi phương án x là phương án t i ưu và k t thúc thu t
toán.
N u trái l i chuy n sang bư c 3.
Bư c 3. N u t n t i i ∈ J0 sao cho x10 < 0 và xij ≥ 0 v i m i j = 1, 2, . . . , n thì
k t lu n t p phương án là r ng.
N u trái l i thì ch n ∆s0 = min{x10 : i ∈ J0 } và gi s

∆k ∆k
θ= = min : xsj < 0 (4.2.9)
xsk xsk

Chuy n sang bư c 4.
Bư c 4. Th c hi n phép quay xung quanh ph n tr c xsk ta thu đư c gi phương
án m i, coi nó như gi phương án ban đ u r i quay l i bư c 2.

Chú ý 4.2.6. B ng đơn hình đư c l p như trong thu t toán đơn hình g c, ch
c t x0 không ghi f (x) như
khác nhau ch , t i v trí ghi giá tr hàm m c tiêu
trư c mà là g (y ), riêng b ng đã xu t hi n d u hi u t i ưu thì hai giá tr nói trên
trùng nhau.




49
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ví d 4.2.7. Gi i bài toán

f (x) = 4x1 + 6x2 + 5x3 + 3x4 → min

x1 + x2 + 3x3 + 2x4 ≥ 5

x1 + 4x2 + 2x3 + x4 ≥ 3

xj ≥ 0, j = 1, 2, 3, 4.

Gi i

Đưa vào hai n bù không âm x5 , x6 ta đư c h ràng bu c m i.

 −x1 −x2 −3x3 −2x4 +x5 = −5
 −x −4x −2x −4x +x6 = −3
1 2 3 4

xj ≥ 0, j = 1, 2, 3, 4, 5, 6.

Các ràng bu c c a bài toán đ i ng u là:

t
yA1 = −y1 − y2 ≤ 4 t
yA2 = −y1 − 4y2 ≤ 6
t
yA3 = −3y1 − 2y2 ≤ 5 t
yA4 = −2y1 − y2 ≤ 3
t
yA5 = −y1 ≤ 4 t
yA6 = y2 ≤ 0



Ta th y ngay y = (0, 0) là phương án c c biên c a bài toán đ i ng u vì d
= đ i v i hai ràng bu c đ c
th y nó là phương án, ngoài ra còn th a mãn d u
l p tuy n tính cu i cùng; cơ s đ i ng u tương ng là cơ s đơn v g m hai vectơ
A5 , A6 . ng v i cơ s đó là gi phương án x = (0, 0, 0, 0, −5, −3). Các k t qu tính
toán đư c th hi n trên các b ng đơn hình dư i đây.
bư c l p đ u tiên ta th y x0 = (−5, −3) < 0, min(x50 , x60 ) = min(−5, −3) =
−5. Do dó A5 ra kh i cơ s . Vì

−4 −6 −5 −3
∆j ∆4
min : x5j < 0 = min , , , = (4.2.10)
−1 −1 −3 −2
x5j x54

nên đưa A4 vào cơ s thay A5 . Th c hi n phép quay xung quanh ph n t tr c
x54 = −2 ta có bư c l p th hai.

50
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


bư c cu i, ta th y x0 = (1, 1) > 0, t đó ta thu đư c phương án t i ưu
x∗ = (0, 0, 1, 1).

c0 Cơ x0 x1 x2 x3 x4 x5 x6
s 4 6 5 3 0 0
A5 (-5) (-2)
0 -1 -1 -3 1 0
A6
0 -3 -1 -4 -2 -1 0 1
0 -4 -6 -5 -3 0 0
A4
3 5/2 1/2 1/2 3/2 1 -1/2 0
A6 (-1/2) -1/2 -7/2 (-1/2)
0 0 -1/2 1
15/2 -5/2 -9/2 -1/2 0 -3/2 0
A4
3 1 -1 -10 0 1 -2 3
A3
5 1 1 7 1 0 1 -2
8 -2 -1 0 0 -1 -1

Ví d 4.2.8. Cho bài toán

f (x) = x1 + 10x2 + 8x3 → min

− x1 + 2x2 + 3x3 = 1

x1 + x2 + 2x3 = 1

xj ≥ 0, j = 1, 2, 3.

(a) Hãy tìm t t c các cơ s đ i ng u. Trong các cơ s đ i ng u đó, cơ s nào
là cơ s t i ưu c a bài toán đã cho và khi đó hãy xác đ nh phương án t i ưu.
(b) Xu t phát t cơ s đ i ng u không ph i là cơ s t i ưu, gi i bài toán đã
cho b ng thu t toán đơn hình đ i ng u.

Gi i




51
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


(a) Bài toán đ i ng u

f (x) = y1 + y2 → max

− y1 + y2 ≤ 1

2y1 + y2 ≤ 10

y1 + 2 y 2 ≤ 8

xj ≥ 0, j = 1, 2, 3.
   
−1 2 1
A1 =   , A2 =   A2 , A3 =   và h {A3 , A1 } đ u đ c l p
Các h
0 1 2
tuy n tính.

• Xét h {A1 , A2 }:
  
t 1  
−y + y = 1
 yA = c y = 3
1 1 2 1

⇐⇒ ⇐⇒ (4.2.11)
t 2  
 yA = c 2y + y = 10 y = 4
2 1 2 2



Vectơ (3, 4) không th a mãn ràng bu c (3) nên h {A1 , A2 } không ph i là cơ
s đ i ng u.

• Xét h {A1 , A3 }:
  
t 1  
− y + y = 1
 yA = c y = 2
1 1 2 1

⇐⇒ ⇐⇒ (4.2.12)
t 3  
 yA = c y + 2 y = 8 y = 3
3 1 2 2



Vectơ (2, 3) th a mãn ràng bu c (2) nên h {A1 , A2 }là cơ s đ i ng u.
Ta tìm phương án tương ng: Các thành ph n cơ s c a gi phương án đư c
xác đ nh b i h x1 A1 + x3 A3 = b, t c là h :
 
 
−x + x = 1 x = −1/3
1 3 1
⇐⇒ ⇐⇒ (4.2.13)
 
x + 2 x = 1 x = 2/3
1 3 2


trong gi phương án có thành ph n âm nên {A1 , A3 } không ph i là cơ s t i
ưu c a bài toán đã cho.

52
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


• Xét h {A2 , A3 }:
  
t 2  
 yA = c 2y + y = 10 y = 4
2 1 2 1

⇐⇒ ⇐⇒ (4.2.14)
t 3  
 yA = c y + 2 y = 8 y = 2
3 1 2 2


Vectơ (2, 3) th a mãn ràng bu c (1) nên h {A2 , A3 }là cơ s đ i ng u.
Các thành ph n cơ s c a gi phương án đư c xác đ nh b i h x2 A2 + x3 A3 =
b, t c là h
 
 
2x1 + x3 = 1 x1 = 1/3
 
⇐⇒ ⇐⇒ (4.2.15)
 
x + 2 x = 1 x = 1/3
1 3 2

Vì đó là nghi m không âm c a h trên nên x = (0, 1/3, 1/3) là phương án t i
ưu.

(b) Ta s gi i bài toán đã cho b ng thu t toán đơn hình đ i ng u v i cơ s đ i
ng u xu t phát {A1 , A3 }.
Th c hi n phép bi n đ i sơ c p trên các dòng c a ma tr n ràng bu c A đ đưa
m t ma tr n có cơ s đơn v tương ng vơi A1 , A3 .
       
−1 2 1 1 0332 0 1 1 3/2 0 1 1 3/2
→ → →
 
1 −1 0 −1/3
1 121 1121 112 1

Ta có b ng đơn hình sau (đ đơn gi n cách vi t mà v n không làm thay đ i
b n ch t, ta v n dùng các ký hi u như thu t toán đơn hình trư c đây).

c0 x0
cơ 1 10 8
x1 x2 x3
s
A1
8 2/3 0 1 1
A1 -1/3 (-1)
1 1 0
0 -3 0
A3
8 1/3 1 0 1
10 A2 1/3 -1 1 0
6 -3 0 0
11
bư c 2, do x0 ≥ 0 nên suy ra x = 0, , là phương án t i ưu.
33
53
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


4.3. Vnđ tìm phương án c c biên xu t phát
c a bài toán đ i ng u
T lý lu n và các ví d trên đây ta th y r ng, đ ti n hành gi i bài toán (1), (2), (3)
b ng thu t toán đơn hình đ i ng u ta c n ph i bi t m t phương án c c biên c a
bài toán đ i ng u (coi nó là phương án c c biên xu t phát đ ti n hành thu t
toán).
1) Trư ng h p th nh t
Gi i s c n gi i bài toán (đư c g i là bài toán chính):

f (x) =t cx → min

Ax ≥ b

x≥0

trong đó c ≥ 0; A là ma tr n c m × n.
Đưa bài toán trên v bài toán d ng chính t c, nó có d ng:

f (x, w) =t cx → min

− Ax + w = −b

x ≥ 0, w ≥ 0,

trong đó w = (xn+1 , xn+2 , . . . , xn+m ).
Các ràng bu c c a bài toán đ i ng u c a bài toán d ng chính t c là:

t
y (−Aj ) ≤ cj (j = 1, 2, . . . , n)
t
yI i ≤ 0 (i = 1, 2, . . . , m)

D th y r ng y = 0 là phương án c c biên c a bài toán đ i ng u đó, ng v i cơ
s đ i ng u là cơ s đơn v , gi phương án tương ng là x = (0, −b). Xu t phát t
phương án c c biên đó ta ti n hành thu t toán đơn hình đ i ng u đ gi i bài toán
đã cho. 2) Trư ng h p t ng quát
Đ i v i bài toán (1), (2), (3), gi s chưa bi t m t cơ s đ i ng u nào nhưng đã

54
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


bi t m t h đ c l p tuy n tính g m m c t c a ma tr n A, đó là h

H = {A j : j ∈ J 0 } (4.3.16)

Chúng ta xét hai trư ng h p sau đây.
(a) N u bi t đư c r ng h

t i
i ∈ J0
A =c
i

t j
A ≤c j ∈ J0
/
j


có nghi m ho c bi t đư c r ng ∆j ≤ 0 v i m i j ( ng v i H ) thì H chính là m t
cơ s đ i ng u.
N u may m n g p trư ng h p trên thì:
Th c hi n phép bi n đ i sơ c p trên các dòng c a ma tr n [A|b] đ thu đư c
ma tr n m i có m c t vectơ đơn v khác nhau tương ng v i cơ s đ i ng u H .
Xu t phát t đó ti n hành thu t toán đơn hình đ i ng u đ gi i bài toán đã cho.
N u H không ph i là cơ s đ i ng u ho c chưa bi t nó có ph i là cơ s đ i
ng u hay không thì ta xét bài toán sau đây mà ta g i là bài toán m r ng.

F (x0 , x) =t cx → min

x0 + xj = M
j ∈J0
/

Ax = b

x ≥ 0, x0 ≥ 0.

trong đó x0 là m t n m i đư c b sung, M là tham s dương đư c coi là r t l n.

Ví d 4.3.1. Gi i bài toán sau b ng thu t toán đơn hình đ i ng u

f (x) = −x1 − 2x2 + x3 → min

− x1 + 4x2 − 2x3 ≤ 6

x1 + x2 + 2x3 ≥ 6

2x1 − x2 + 2x3 = 4

xj ≥ 0, j = 1, 2, 3.

55
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Gi i

Đưa vào hai n bù x4 và x5 ta đư c bài toán d ng chính t c

f (x) = −x1 − 2x2 + x3 → min

− x1 + 4x2 − 2x3 + x4 = 6

x1 + x2 + 2x3 − x5 = 6

2x1 − x2 + 2x3 = 4

xj ≥ 0, j = 1, 2, 3, 4, 5.

Có th th y h g m 3 vectơ A1 , A4 , A5 là đ c l p tuy n tính.
B sung vào bài toán trên m t ràng bu c gi t o ta có bài toán

f (x0 , x) = −x1 − 2x2 + x3 → min

−x1 + 4x2 − 2x3 + x4 = 6
x0 + x2 + x3 = M

x1 + x2 + 2x3 − x5 = 6

2x1 − x2 + 2x3 = 4

xj ≥ 0, j = 0, 1, 2, 3, 4, 5.

B ng cách gi i h Bxj = Aj v i j = 0, 2, 3, ta đư c:

17 3
x0 = (2, 8, −4) x2 = − , ,−
22 2

ho c có th tìm đư c chúng b ng cách th c hi n các phép bi n sơ c p trên các
dòng c a ma tr n.
Vi c tính toán đư c th hi n trên b ng dư i đây. Do các thành ph n c a gi
phương án có d ng pM + q nên c t x0 và h s p trùng nhau.

c0 x0 x0 x1 x2 x3 x4 x5

s M 0 -1 -2 1 0 0
A0 (1)
0 0 1 1 0 1 0 0
-1 A1 2 0 0 1 -1/2 1 0 0
A4
0 8 0 0 0 7/2 -1 1 0
A5
0 -4 0 0 56 -3/2
0 -1 0 1
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



0 0 0 5/2 -2 0 0
-2 A2 0 1 1 0 1 1 0 0
-1 A1 2 1/2 1/2 1 0 3/2 0 0
A4 (-7/2)
0 8 -7/2 0 0 -9/2 1 0
A5
0 -4 3/2 3/2 0 0 1/2 0 1
-5/2 0 0 -9/2 0 0
-2 A2 16/7 0 0 0 1 -2/7 2/7 0
-1 A1 22/7 0 0 1 0 6/7 1/7 0
A0 -16/7
0 1 1 0 0 9/7 -2/7 0
A5 (-10/7)
0 -4/7 0 0 0 0 3/7 0
0 0 0 -9/7 -5/7 0
-2 A2 12/5 0 0 0 1 0 1/5 -1/5
-1 A1 14/5 0 0 1 0 0 2/5 3/5
A0 -14/5
0 1 1 0 0 0 1/10 9/10
A3
1 2/5 0 0 0 0 1 -3/10 -7/10
-36/5 0 0 0 0 -11/10 -9/10


Vì A0 thu c cơ s ng v i phương án t i ưu đó nên phương án t i ưu c a bài
14 12 2
toán ban đ u là x∗ = ,,.
555


4.4. V n đ h u t i ưu
H!H u t i ưu Gi s ta đã gi i xong bài toán

f (x) =t cx → min

Ax = b

x≥0

b ng thu t toán đơn hình và thu đư c phương án t i ưu x ng v i cơ s J0 khi
d u hi u t i ưu đã xu t hi n (m i ư c lư ng đ u không dương). Gi s x0 là vectơ
các thành ph n cơ s c a x và B là ma tr n g m các vectơ trong cơ s t i ưu.

57
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Trong th c t thư ng phát sinh các trư ng h p c n x lí sau đây:
1) Trư ng h p th nh t
Thay đ i v ph i c a h ràng bu c cư ng b c, trư c là b, bây gi là b và ta có
bài toán c n ph i gi i là

f (x) =t cx → min

Ax = b

x≥0

Khi đó không c n gi i bài toán m i t đ u mà ch c n tính x0 = B −1 b. N u
x0 ≥ 0 thì B v n là cơ s t i ưu đ i v i bài toán m i và x0 chính là vectơ các thành
ph n cơ s trong phương án t i ưu c a bài toán m i. N u trái l i, t c là x0 có ít
nh t m t thành ph n âm thì trong b ng đơn hình cu i cùng ta thay x0 b i x0 và
như v y ta có b ng đơn hình xu t phát đ gi i bài toán m i b ng thu t toán đơn
hình đ i ng u.
2) Trư ng h p th hai
m
am+1,j xj ≤ bm+1 , t c là c n gi i
B sung vào bài toán ban đ u ràng bu c
j =1
bài toán m i sau đây:

f (x) =t cx → min

Ax = b
m
am+1,j xj ≤ bm+1
j =1

x≥0

N u x th a mãn ràng bu c b sung thì nó cũng là phương án t i ưu c a bài
toán m i.
Trong trư ng h p ngư c l i, ta s dùng các ràng bu c cư ng b c c a bài toán
ban đ u, có m t dư i d ng tương đương ngay trong b ng đơn hình cu i cùng, đ
kh các n cơ s xj , j ∈ J0 trong ràng bu c b sung:
m
am+1,j xj + xn+1 = bm+1 (4.4.17)
j =1


58
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


trong đó xn+1 là n bù không âm. Sau đó đ t dòng các h s m i c a ràng bu c
b sung vào dòng cu i cùng (t c dòng th m + 1) c a b ng đơn hình cu i cùng.
Và như v y, do các ư c lư ng v n không thay đ i và ∆n+1 = 0 (lưu ý r ng h s
c a n bù xn+1 trong hàm m c tiêu b ng 0) ta có b ng đơn hình xu t phát đ gi i
bài toán m i b ng thu t toán đơn hình đ i ng u.
N u J0 = {1, 2, . . . , m} thì b ng đơn hình xu t phát đó là




59
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



c0 x0 ··· ··· ··· ···
c1 ci cm cj
cơ 0
x1 xi xm xj xn+1
··· ··· ··· ···
s
A1 ··· ··· ··· ···
c1 x10 x1j
1 0 0 0
··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ···
Ai ··· ··· ··· ···
ci xi0 xij
0 1 0 0
··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ···
Am ··· ··· ··· ···
cm xm0 xmj
0 0 1 0
An+1 bm+1 ··· ··· ··· ···
0 xm+1,j
0 1 0 1
··· ··· ··· ∆j ≤ 0 · · ·
0 1 0 0


trong đó:
m
bm+1 = bm+1 − am+1,i xi0 (4.4.18)
i=1
m
xm+1,j = am+1,j − am+1,i xij (j = 1, 2, . . . , n). (4.4.19)
i=1

Nói cách khác là nhân dòng i, (i = 1, 2, . . . , m) c a b ng cu i cùng v i −am+1,j
c ng t t c l i, r i c ng v i h s tương ng c a ràng bu c b sung, k t qu đư c
đ t vào dòng m + 1.

Ví d 4.4.1. Cho bài toán

f (x) = −x1 + 3x2 + x3 + 2x4 + x5 → min

+2x4 −9x5
 x1 +3x2 =5




3x2 −2x3 +2x4 −7x5 ≤ 19



3x2 −3x3 +x5 ≤ 15



xj ≥ 0, j = 1, 2, 3, 4, 5.

(a) Gi i bài toán đã cho.
(b) Gi i bài toán đã cho khi v ph i b = (5, 19, 15) đư c thay b i b = (3, 14, 6).

Gi i

60
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Ta dùng thu t toán hai pha. Đưa vào hai n gi i x6 , x7 ta có bài toán ph

f (x) = −x1 + 3x2 + x3 + 2x4 + x5 → min

+2x4 −9x5
 x1 +3x2 =5




3x2 −2x3 +2x4 −7x5 +x6 = 19



3x2 −3x3 +x5 +x7 = 15



xj ≥ 0, j = 1, 2, 3, 4, 5, 6, 7.

Ta có b ng sau:

c0 x0
cơ -1 3 1 2 1 1 1
x1 x2 x3 x4 x5 x6 x7
b b
s
A1
0 5 1 0 3 2 -9 0 0
A6 19
1 0 3 -2 2 -7 1 0
A7 15 (3)
1 0 -3 0 1 0 1
0 6 -5 2 -6 0 0
A1
0 5 1 0 3 2 -9 0
A6 (2)
1 4 0 0 1 -8 1
A2
0 5 0 1 -1 0 1/3 0
0 0 1 2 -8 0
-1 A1 -5 (-1)
1 1 0 2 0
A4 4
2 2 0 0 1/2 1 -4
A2 2
3 5 0 1 -1 0 1/3
18 0 0 -5 0 -7
A5 5
1 -1 0 -2 0 1
A4 24
2 -4 0 -15/2 1 0
A2 1/3 1/3
3 1 -1/3 0 0
54 -7 0 -19 0 0


Đ i v i bài toán đã cho, bư c 3 đã xu t hi n d u hi u t i ưu v i phương án
t i ưu là x∗ = (1, 5, 0, 2, 0) và f (x) = 18.


61
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


2) Cơ s t i bư c 3 đ i v i bài toán đã cho là {A1 , A4 , A2 }
 
1 2 0
B = [A1 A4 A2 ] =  0 2 3 
 
 
 
003

Đ t x0 = (x1 , x4 , x2 ). Khi đó h x0 = B −1 b tương đương v i B x0 = b và có d ng
  
−5
 x1 +3x4 =3




0

= 14 ⇔ x =  4 
2x4 +3x2 

 

3x2 =6 2




Do x0 có thành ph n âm nên x∗ không ph i là phương án t i ưu c a bài toán
m i và c n ph i ti p t c tính toán.
Đ t x0 vào c t b bư c th 3 r i ti p t c thu t toán đơn hình đ i ng u (chú ý
r ng, ch bi n đ i c t b theo ph n t tr c đã xác đ nh khi gi i bài toán ban đ u).
bư c 4, d u hi u t i ưu đ i v i bài toán m i xu t hi n là x = (0, 1/3, 0, 24, 5)
giá tr t i ưu c a hàm m c tiêu t i x là 54.



4.5. Bài t p chương 4
Bài 4.1. Tìm giá tr t i ưu c a hàm m c tiêu c a các bài toán sau:
n
cj xj → max
(a)
j =1
n
aj xj ≤ β
j =1
xj ≥ 0, j = 1, 2, . . . , n
trong đó β, cj , aj , j = 1, 2, . . . , n là các s dương.
n
jxj → min
(b)
j =1
i
xj ≤ i, i = 1, 2, . . . , n
j =1
xj ≥ 0, j = 1, 2, . . . , n.




62
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Bài 4.2. Ch ng t bài toán sau có hàm m c tiêu không b ch n

f (x) = −4x1 − 2x2 + 3x3 + 5x4 → min

+x2 −4x3 ≥7
x1





−2x1 +3x2 +3x3 −5x4 ≥ 10



2x1 +8x2 −4x3 +6x4 ≥ 16



xj ≥ 0, j = 1, 2, 3, 4.

Bài 4.3. Ch ng minh r ng bài toán {t cx → max : Ax ≤ b, x ≥ 0} có phương án
t i ưu n u b ≥ 0 và ma tr n A có ít nh t m t dòng g m toàn các s dương.

Bài 4.4. Ch ng t r ng x = (0, 1, 0, 3) là phương án t i ưu c a bài toán

f (x) = −x1 − 3x2 + x3 − 2x4 → min

 4x1 +12x2 +4x4 = 24




−x ≥3
x +3x
1 2 3



 4x1 −18x2 +2x3 +3x4 ≥ −33


xj ≥ 0, j = 1, 2, 3, 4.

Bài 4.5. Ki m tra tính t i ưu c a phương án x = (0, 0, 2, −2, 0) c a bài toán:

f (x) = −2x1 + 4x2 − x3 − 2x4 + 2x5 → min

≥ −1
 x1 +2x2 +3x3 +x4




+x3 −5x4 +2x5 ≥5
4x1



−x2 +4x3 +3x4 −2x5
 3x1 =2


x1 ≥ 0, x2 ≥ 0,




63
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Bài 4.6. Bi t r ng phương án t i ưu c a bài toán

f (x) = 15x1 + 10x2 + 6x3 → min

 3x +2x3 = 24
1





 x1 +2x2 +2x3 ≥ 3


+x2 +x3 ≥ 2
x
1





 4x +2x −2x ≥1

1 2 3

x1 ≥ 1, x2 ≥ 0, x3 ≥ 0.

là x = (1, 5/4, 11/4). Hãy tìm phương án t i ưu c a bài toán đ i ng u.

Bài 4.7. Tìm t p phương án t i ưu c a bài toán

f (x) = x1 + x2 + 2x3 − 2x4 − 4x5 → min

 −x +x −3x +2x −2x =8
1 2 3 4 5





 −2x1 −x3 +x4 −x5 ≥ −21


+5x3 −3x4 +2x5
 3x = 25
1





≤ 20
 2x +x4 +4x5

1

xj ≥ 0, j = 1, 2, 3, 4, 5.

bi t r ng y = (1, 0, 1, −1) là phương án t i ưu c a bài toán đ i ng u.

Bài 4.8. Cho bài toán

f (x) = x1 + x2 − x3 → min

≤7
x1 +2x2 +x3






4x1 +3x2 −6x3 ≤9







−x2 −8x3 ≤ −6
2x1





−2x2 ≤2
+x3



 −2x1 −x2 +5x3 ≤1





 −x ≤1

+3x3
1





≤0
x3




64
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




(a) Ch ng t r ng các phương án x = (−4, 6, −1), y = (4/5, 0, 3.5, 0, 0, 1) theo
th t là phương án t i ưu c a bài toán đã cho và bài toán đ i ng u c a nó.

(b) Tìm t p phương án t i ưu c a bài toán đã cho và bài toán đ i ng u c a nó.

Bài 4.9. Cho bài toán

f (x) = 2x1 + 3x2 + 5x3 + 4x4 → max

 x1 +2x2 +3x3 +x4 ≤ 5

+x2 +2x3 +3x4 ≥ 3
x
1

xj ≥ 0, j = 1, 2, 3, 4.

(a) Ch ng t r ng phương án x = (0, 1, 1, 0) là phương án t i ưu c a bài toán
đã cho.

(b) Tìm t t c các phương án t i ưu c a bài toán đã cho th a mãn đi u ki n
c3 + 5x4 = 1.

Bài 4.10. Cho bài toán:

f (x) = 5x1 − 9x2 + 5x3 + 7x4 + 3x5 → min

 2x1 +6x2 −2x3 −2x4 +x5 ≤ −4




+2x3 +4x4 −x5
8x = 20
1



 −x1 −x2 −x5 ≥ −1
+x3


xj ≥ 0, j = 2, 3, 4, 5.

(a) Ch ng t r ng phương án x = (0, 1, 0, 5, 0) là phương án t i ưu c a bài toán
đã cho. Tìm t p phương án t i ưu c a bài toán đ i ng u.

(b) Hãy tìm t t c các phương án t i ưu c a bài toán đã cho có thành ph n th
ba là x3 = 4.




65
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Bài 4.11. Cho bài toán

f (x) = 4x1 + 3x2 − 12x3 + αx4 + βx5 → min

+x5 ≥ b1
 2x1 +5x4




−7x4 −x5 ≥ b2
3x2



−4x3 +2x4 −2x5 ≥ b3



x4 ≥ 0, x5 ≥ 0.

(a) Tìm t t c các phương án c c biên c a bài toán đã cho.

(b) Tìm đi u ki n c n và đ v các tham s α, β đ bài toán đã cho có phương
án t i ưu v i m i b1 , b2 , b3 .

(c) V i giá tr nào c a α, β bài toán đã cho có hàm m c tiêu không b ch n?

Bài 4.12. Cho bài toán

f (x) = x1 + 3x2 − 12x3 + αx4 + βx5 → min

+x5 ≥ b1
 2x1 +5x4




−7x4 −x5 ≥ b2
3x2



−4x3 +2x4 −2x5 ≥ b3



x4 ≥ 0, x5 ≥ 0.




(a) Gi i bài toán đã cho.

(b) Tìm t p phương án t i ưu c a bài toán đã cho.

Bài 4.13. Cho bài toán

f (x) = −4x1 − x2 − 8x3 + 5x4 → min

 x1 +2x2 −2x3 +4x4 = 3

−x4 = 8
 5x +3x +6x
1 2 3

x4 ≥ 0, x5 ≥ 0.

66
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Hãy tìm t t c các cơ s đ i ng u. Trong các cơ s đ i ng u hãy ch ra các cơ s
t i ưu c a bài toán đã cho.




67
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




Chương 5.

BÀI TOÁN V N T I VÀ THU T
TOÁN TH V


5.1. Bài toán v n t i
Trong m c 1.1., ta đã nêu d ng t ng quát c a bài toán v n t i là
m n
→ min
cij xij (1)
i=1 j =1
n
xij = ai , (i = 1, 2, . . . , m) (2)
j =1
m
xij = bj , (i = 1, 2, . . . , n) (3)
i=1
xij ≥ 0, (i = 1, 2, . . . , m, j = 1, 2, . . . , n) (4)

trong đó ai > 0, (i = 1, 2, . . . , m, bj > 0, (j = 1, 2, . . . , n).
Đó là bài toán quy ho ch tuy n tính d ng chính t c nhưng có c u trúc khá đ c
bi t mà ta g i nó là bài toán v n t i c đi n .
m n
Đ ta= ai , b = bj . N u a = b thì bài toán v n t i (1),(2),(3),(4) đư c g i
i=1 j =1
là bài toán cân b ng thu phát..
Kí hi u A là ma tr n ràng bu c và

x = (x11 , . . . , x1n , . . . , x21 , . . . , x2n , . . . , xm1 , . . . , xmn ) ∈ Rmn (5.1.1)

c = (c11 , . . . , c1n , . . . , c21 , . . . , c2n , . . . , cm1 , . . . , cmn ) ∈ Rmn (5.1.2)

Thì bài toán v n t i đư c vi t l i dư i d ng

f (x) =t cx → min

Ax = A0

x ≥ 0.

68
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Trong bài toán v n t i, h Ax = A0 g m m + n phương trình v i n × m n,
trong đó ch có m + n − 1 phương trình đ c l p tuy n tính, m i phương trình là
h qu c a các phương trình còn l i.
Sau này m i phương án ta vi t dư i d ng ma tr n c m × n : x = (xij ). Ta
cũng có ma tr n cư c phí c m × n : c = (cij ).
Như v y, bài toán v n t i đư c coi là đã cho n u bi t vectơ lư ng phát a =
(a1 , a2 , . . . , am ), vectơ lư ng thu b = (b1 , b2 , . . . , bn ) và ma tr n cư c phí c = (cij ).
Ta kí hi u bài toán v n t i đó là a, b, c .

Đ nh lý 5.1.1 (Đi u ki n có phương án t i ưu). Đ bài toán v n t i (1),(2),(3),(4)
có phương án t i ưu, đi u ki n c n và đ là có đi u ki n cân b ng thu phát a = b.



5.2. Các Tính ch t c a bài toán v n t i
5.2.1 Chu trình

M t dãy ô có d ng
(i1 , j1 ), (i1 , j2 ), (i2 , j2 ), · · · , (ik , jk ), (ik , j1 ) hay
(i1 , j1 ), (i2 , j1 ), (i2 , j2 ), · · · , (ik , jk ), (i1 , jk ) đư c g i là m t chu trinh (hai ô k
ti p cùng m n trong m t dòng hay m t c t, ba ô liên ti p không cùng m n trên
m t dòng hay m t c t, ô đ u tiên và ô cu i cùng cũng đư c coi là hai ô liên ti p).
Như v y s ô trong m t chu trình là m t s ch n không nh hơn 4.
T p ô Γ ⊂ U = {(i, j ) : i = 1, 2, . . . , m; j = 1, 2, . . . , n} đư c g i là ch a chu
trình n u như t các ô c a Γ có th l p đư c ít nh t m t chu trình. N u trái l i
thì ta nói Γ không ch a chu trình.



Đ nh lý 5.2.2 (Đi u ki n không ch a chu trình). Đi u ki n c n và đ đ t p
ô Γ ⊂ U không ch a chu trình là h vectơ tương ng v i nó, t c là h {Aij : (i, j ) ∈
Γ}, đ c l p tuy n tính.

H qu 5.2.3 (S ô t i đa không ch a chu trình). N u b ng v n t i g m m
dòng và n c t thì t p ô không ch a chu trình có t i đa là n + m − 1 ô.

69
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Đ nh lý 5.2.4 (Chu trình duy nh t). Gi s b ng v n t i g m m dòng và n
c t, E là t p ô g m m + n − 1 ô không ch a chu trình, (i, j ) là m t ô c a b ng
không thu c E . Khi đó F = E ∪ {i, j } có m t chu trình duy nh t qua ô (i, j ).

Đ nh lý 5.2.5 (D u hi u t p không ch a chu trình). Gi s F là m t t p
g m m + n ô ch a chu trình duy nh t V và (i, j ) ∈ V . Khi đó t p ô E = F \ {(i, j )}
s không ch a chu trình.

Đ nh lý 5.2.6 (Đi u ki n c c biên). Phương án x = (xij ) c a bài toán v n t i
(1),(2),(3),(4) là phương án c c biên khi và ch khi t p ô ch n tương ng v i nó,
t c là t p ô

H (x) = {(i, j ) : xij > 0} (5.2.3)

không ch a chu trình.

Đ nh lý 5.2.7 (Đi u ki n ch a ít nh t m t chu trình). T p ô không r ng Γ ⊂
U s ch a ít nh t m t chu trình n u trong m i dòng và m i c t c a b ng v n t i
ho c là không có ô nào c a Γ, ho c có ít nh t hai ô c a Γ.



5.3. V n đ tính các ư c lư ng
Gi s b ng cách nào đó ta đã tìm đư c phương án c c biên x = (xij ) c a bài toán
v n t i v i t p ô ch n H (x) g m m + n − 1 ô (k c ô ch n-không) không ch a chu
trình. Theo thu t toán đơn hình đ xét tính t i ưu c a x ta ph i tìm đư c các ư c
lư ng ∆ij ng v i m i vectơ Aij ngoài cơ s c a x, t c là ng v i m i ô lo i (i, j ).
Chúng ta d dàng ch ng minh đư c

cij −
∆ij = cij (5.3.4)
c
(i,j )∈V l
(i,j )∈V


trong đó, V c và V l theo th t là t p h p các ô mang s hi u ch n l c a V .

Ví d 5.3.1. Bài toán v n t i và phương án c c biên x ban đ u c a nó đư c cho
b i b ng

70
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




trong đó các cư c phí ghi góc trên bên trái m i ô, các thành ph n cơ s c a
phương án c c biên x ban đ u đư c ghi góc đ i di n (các thành ph n phi cơ s
b ng 0). Có 9 ô lo i là các ô (1, 3), (1, 4), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 2), (4, 4).
Ta hãy l p b ng tính ∆ij v i Aij ngoài cơ s , t c là v i các ô lo i (i, j ). Trư c
h t ta hãy tính ∆32 . T p ô g m ô (3, 2) và các ô ch n ch a chu trình duy nh t g m
6 ô, đư c th hi n b i đư c th hi n b i đư ng nét đ t trên b ng. Các ô này cùng
v i s hi u c a nó và cư c phí tương ng là

Ô trong chu trình (3,2) (3,4) (2,4) (2,1) (1,1) (1,2)
S hi u 1 2 3 4 5 6
cij 30 16 18 68 40 15

Theo công th c (5.3.4) ta có

∆32 = 16 − 18 + 68 − 40 + 15 − 30 = 11




71
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


Tương t ta cũng tính đư c

∆13 = 40 − 30 + 13 − 35 = −12,

∆14 = 40 − 68 + 18 − 100 = −100,

∆22 = 68 − 40 + 15 − 51 = −8,

∆23 = 68 − 30 + 13 − 53 = −2

∆31 = 16 − 18 + 68 − 120 = −54

∆33 = 16 − 18 + 68 − 30 + 13 − 150 = −101

∆42 = 30 − 40 + 15 − 54 = −49

∆44 = 30 − 68 + 18 − 80 = −100

Vi c tính các ư c lư ng theo công th c (5.3.4) là khá đơn gi n nh hình nh tr c
quan c a khái ni m chu trình, nhưng s đơn gi n hơn n u ta ng d ng đ nh lý
dư i đây

Đ nh lý 5.3.2 (Phương pháp đơn gi n xác đ nh các ư c lư ng). N u ta thay
ma tr n cư c phí c = (cij ) b i ma tr n c = (cij ), trong đó cij = cij + ri + sj , t c
m i ô c a dòng i v i cùng m t s ri , c ng vào cư c
là n u ta c ng vào cư c phí
m i ô c a c t j v i cùng m t s sj thì s đư c m t bài toán v n t i m i
phí
tương đương v i bài toán v n t i ban đ u (theo nghĩa hai bài toán có chung t p t p
phương án t i ưu).

Đ nh lý 5.3.3 (D u hi u t i ưu). Gi s x = (xij ) là m t phương án c c biên
c a bài toán v n t i v i t p ô ch n H (x) và cij = 0 v i m i ô (i, j ) ∈ H (x) (t c là
đã quy-không các ô ch n).

(a) N u cij ≥ 0 v i m i ô (i, j ) ∈ H (x) thì x là phương án t i ưu c a bài toán.
/

(b) N t n t i ô (i, j ) ∈ H (x) sao cho cij < 0 thì ta có th xây d ng đư c phương
/
án c c biên x t t hơn x, n u x không suy bi n (nói chung x không x u hơn
x).



72
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


5.4. Mts phương pháp xây d ng phương án
c c biên ban đ u
Dư i đây ta nêu ra ba phương pháp, đó là phương pháp góc tây b c, phương pháp
c c ti u theo b ng và phương pháp Vaugen. Đ i v i b ng v n t i g m m dòng và
n c t, vi c tìm t p ô ch n g m m + n − 1 ô không ch a chu trình đư c ti n hành
b ng phương pháp quy n p theo m + n là t ng s dòng và c t c a b ng v n t i.
N u m + n = 2 thì b ng g m m t ô duy nh t. Do đi u ki n cân b ng thu phát
nên a1 = b1 . Đ i v i c ba phương pháp y đi u ch n ô (1,1) và đ t x11 = a1 . Đó
là phương án c c biên vì A11 = 0và rõ ràng có n + m − 1 = 1 ô ch n không ch a
chu trình.
Gi s đã bi t cách xây d ng phương án c c bi n ban đ u theo c ba phương
pháp v i b ng có m + n ≤ k − 1, khi đó đ i v i b ng mà m + n = k ta s ti n hành
như sau:
N u as ≤ bt thì xst = as và xóa ngay dòng s; bt đư c thay b i bt = bt − as .
N u as > bt thì xst = bt và xóa ngay c t t; as đư c thay b i as = as − bt .
Sau khi xóa đi, ta đư c b ng m i g m m + n = k − 1, trên đó đã xây d ng đư c
phương án c c biên (theo gi thuy t qui n p) v i t p ô ch n H g m n + m − 1 = k − 2
ô. D th y r ng H ∪ {s, t} là t p g m k − 1 ô ch n (đ i v i b ng m i) không ch a
chu trình, b i vì n u trái l i thì chu trình t ph i qua ô (s,t) nhưng đi u này không
th đư c vì dòng s c t t đã b xóa. Như v y, v i b ng mà m + n = k ta xây d ng
đư c phương án c c biên v i t p ô ch n H ∪ {s, t} g m k − 1 ô.
Như v y, m i b ng hình thành trong quá trình phân ph i (k c b ng đ u
tiên) sau khi phân ph i t i đa vào ô (s,t) nào đó ta xóa ch m t dòng ho c m t c t
đ đư c m t b ng m i.
Vi c ch n ô (s, t) là ng u nhiên, nhưng ta thư ng dùng các phương pháp sau:

(1) Phương pháp góc tây b c : (s,t) là góc trên bên trái c a b ng ( m i bư c).

(2) Phương pháp c c ti u theo b ng (s, t) là ô sao cho cst = min cij trong đó c c
ti u đư c ch n theo ô (i,j) c a b ng ( m i bư c).

73
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




B ng 5.4.1: Phương pháp tây b c




B ng 5.4.2: Phương pháp Vaugen


(3) Phương pháp Vaugen V i m i dòng và m i c t ta đi u tính hi u c a cư c phí
th p th nhì và th p th nh t (ta g i hi u đó là đ chênh l ch c a dòng hay
c t đó). Ch n dòng (hay c t) có đ chênh l ch l n nh t. Trên dòng (hay c t)
đã ch n ta s ch n ô (s,t) có cư c phí th p nh t.

Ví d 5.4.1. Dư i đây là các phương án c c biên ban đ u tìm đư c b ng phương
pháp góc tây b c và phương pháp Vaugen.




74
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


5.5. Thu t toán th v
Phương pháp đã nêu trên đây đ tìm phương án t i ưu c a bài toán v n t i v i
các bư c c th sau đây đư c g i là thu t toán th v .
Bư c 1. Tìm phương án c c biên ban đ u x = (xij ).
Bư c 2. Quy-không các ô ch n. N u cij ≥ 0 v i m i ô (i, j ) c a b ng thì k t
thúc vi c tính toán và k t lu n x là phương án t i ưu. N u trái l i, t c là t n t i
ô (i,j) sao cho cij < 0 thì ch n cst = min{cij : cij < 0} và chuy n sang bư c 3.
Bư c 3. L p chu trình V đi qua ô (s,t) và s ô xác đ nh nào đó c a H (x).
Tính

θ = min{xij : ij ∈ V c }. (5.5.5)

chuy n sang bư c 4.
Bư c 4. Xây d ng x = (xij ) theo công th c

n u(i, j ) ∈ V l

xij + θ





xij = (5.5.6)
n u(i, j ) ∈ V c
xij − θ



n u(i, j ) ∈ V

x
 ij


cho x đóng vai trò c a x và quay l i bư c 2.

Ví d 5.5.1. Gi i bài toán v n t i a, b, c v i vectơ lư ng phát a = (100, 400, 230)
vectơ lư ng thu b = (320, 180, 110, 120) và ma tr n cư c phí
 
5 3 16 9
 
c = 5 3 7 8
 
 
1 8 12 10

Gi i

B ng phương pháp góc tây b c ta thu đư c phương án c c biên đ u tiên suy bi n,
trong đó có m t ô-ch n-không, đó là ô (2,3) (sau khi phân ph i t i đa l n th bao
v i x22 = 180, n u xóa dòng 2 thì ô-ch n-không là ô (3,2)).

75
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




76
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp




T đó ta có phương án t i ưu
 
0 100 0 0
x∗ =  90
 
80 110 120
 
 
230 0 0 0

v i giá tr t i ưu c a hàm m c tiêu là

f ∗ = 110.3 + 90.5 + 80.3 + 110.7 + s120.8 + 230.1 = 2950.



5.6. Tiêu chu n t i ưu. Bài toán đ i ng u c a bài
toán v n t i
5.6.1 Tiêu chu n t i ưu

Gi s x = (xij ) là m t phương án c a bài toán v n t i (1),(2),(3),(4).
Theo 4.1.6 thì đi u ki n c n và đ đ phương án x là phương án t i ưu c a bài
toán v n t i là t n t i vectơ

y = (u, v ) = (u1 , . . . , um , v1 , . . . , vm ) ∈ Rm+n (5.6.7)

77
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


sao cho

y t Aij ≤ cij n u xij = 0

y t Aij = xij xij > 0

Do tính ch t đ c bi t c a vectơ Aij nên ta có

y t Aij = ui + vj (i = 1, 2, . . . , m; j = 1, 2, . . . , n) (5.6.8)

T đó suy ra r ng:
Đi u ki n c n và đ đ phương án x = (xij ) là phương án t i ưu c a bài toán
(1),(2),(3),(4) là t n t i các s ui v i i = 1, 2, . . . , m và vj v i j = 1, 2, . . . , n sao
cho

ui + vj ≤ cij xij = 0

ui + vj = cij xij > 0



N u x là phương án t i ưu c a bài toán v n t i (1),(2),(3),(4) thì y = (u, v ) là
phương án t i ưu c a bài toán đ i ng u.


5.6.2 Bài toán đ i ng u c a bài toán v n t i

Bài toán v n t i là bài toán quy ho ch tuy n tính d ng chính t c. Chú ý đ n
(5.6.8), bài toán đ i ng u c a nó d ng
m n
bj vj → max
ai ui +
i=1 j =1

ui + vj ≤ cij (i = 1, 2, . . . , m, j = 1, 2, . . . , n)

T đi u ki n c n và đ đ bài toán v n t i (1),(2),(3),(4) nh n phương án x
làm phương án t i ưu nêu trên, ta rút ra k t lu n:
N u (r, s) = (r1 , . . . , rm , s1 , . . . , sn ) là m t h th ng th v ng v i phương án
t i ưu thì

(−r, −s) = (−r1 , . . . , −rm , −s1 , . . . , −sn )

là phương án t i ưu c a bài toán đ i ng u.

78
Ch m c
Đ Cân b ng thu phát, 68
Đánh thu , 31 C p ràng bu c đ i ng u, 42
Đ i ng u, 42 Cơ s ban đ u, 27
Đ i ng u m nh, 44 Ch a chu trình, 69
Đ i ng u y u, 43 Chu trình, 69
Đ chênh l ch, 74
D
Đ l ch bù, 45
D ng chính t c, 6
Đa di n l i, 15
D ng chu n t c, 6
Đi m c c biên, 15
H
Đo n th ng, 14
Hai pha, 28
Ư
Ư c lư ng, 21 M
Ma tr n cư c phí, 69
B
Bài toán g c, 42 P
Bài toán m r ng, 55 Phương án c c biên, 15
Bài toán quy ho ch, 3 Phương pháp đ th , 8
Bài toán v n t i, 68 Phương pháp c c ti u theo b ng,
Bài toán v n t i đ i ng u, 78 73
B ng đơn hình, 24 Phương pháp góc tây b c, 73
B tr , 27 Phương pháp Vaugen, 74
BT l p k ho ch s n xu t, 3
S
BT QHTT t ng quát, 5
S phương án c c biên, 16
BT v n t i, 4
Suy bi n, 27
C

79
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp


T
Tính l i, 15
T p l i, 14
T p l i đa di n, 15
T h p l i, 14
Thu t toán đơn hình, 24, 35, 47
Thu t toán th v , 75

V
V n t i c đi n, 68




80
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp



DANH SÁCH Đ NH LÝ
2.1.2. Tính ch t b c c u c a t h p l i
2.1.4. Tính ch t c a t p l i
2.2.1. Tính l i c a t p phương án
2.2.2. Tính l i c a t p phương án
2.3.1. Đi u ki n là phương án c c biên
2.3.3. Phương án c c biên t i ưu
2.3.4. Đi u ki n có phương án t i ưu
3.1.2. D u hi u t i ưu
3.1.3. D u hi u hàm m c tiêu không b ch n
3.1.4. D u hi u xây d ng đư c phương án t i hơn
3.2.9. Quan h gi a bài toán g c và M -l n
4.1.4. Đ i ng u y u
4.1.6. Đ i ng u m nh
4.1.7. S t n t i phương án
4.1.8. Đ l ch bù
5.1.1. Đi u ki n có phương án t i ưu
5.2.2. Đi u ki n không ch a chu trình
5.2.4. Chu trình duy nh t
5.2.5. Chu trình duy nh t
5.2.6. Đi u ki n c c biên
5.2.7. Đi u ki n ch a ít nh t m t chu trình
5.3.2. Phương pháp đơn gi n xác đ nh các ư c lư ng
5.3.3. D u hi u t i ưu (bài toán v n t i)




81
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản