NHỮNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

CH

NG I

ƯƠ

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

Ạ

Ế

1.1/ M T S VÍ D D N Đ N BÀI TOÁN QUY HO CH TUY N TÍNH: Ộ Ố Ụ Ẫ Ạ Ế Ế

1.1.1. Bài toán v n chuy n: ể ậ

ạ ầ ậ ấ ạ ả ậ ớ T i sân bay Tân S n Nh t có nhu c u v n chuy n 1200 hành khách và 120 t n ấ ể ơ ể s có 2 lo i máy bay có th s d ng v i kh năng v n chuy n ể ử ụ ả ử ằ ỗ hàng b ng máy bay. Gi c a m i lo i nh sau: ạ ủ ư

Máy bay lo i A: 01 máy bay có th ch 150 hành khách và 20 t n hàng v i chi phí ể ở ấ ớ ng ng 240 tri u đ ng. t ươ ứ ồ ạ ệ

ấ ạ ớ ở Máy bay lo i B: 01 máy bay ch có th ch 180 hành khách và 16 t n hàng v i chi ể ở ng ng là 220 tri u đ ng. phí t ươ ứ ệ ồ

ậ ươ ỏ ng án s d ng s máy bay m i lo i sao cho ph i th a ử ụ ạ ả ố ỗ mãn yêu c u v n chuy n v i t ng chi phí ít nh t. Hãy l p mô hình tìm ph ể ớ ổ ầ ậ ấ

L p mô hình: ậ

ạ ạ ng máy bay lo i A ng máy bay lo i B ệ ồ

= 1200 = 120 Z = 240 x1 + 220x2 150 x1 + 180x2 20 x1 + 16 x2 x1,x2 ≥ 0 : ự ế

1 là s l G i xọ ố ượ G i xọ 2 là s l ố ượ T ng chi phí (tri u đ ng): ổ Đ m b o v hành khách: ả ề ả Đ m b o v hàng hóa: ả ề ả Đ m b o th c t ả ả i bài toán:

Gi ả

min (*) Z = 240 x1 + 220x2 ﬁ

180

1200

150

x 1 +

x 2 =

x 1

x 2

120 )

(

16 = j

1, 2

(cid:236) (cid:239) (cid:237) (cid:239) ‡ (cid:238)

Gi ng trình trên Z = 1580  x1 = 2, x2 = 5 thay x1 và x2 vào (* ) ﬁ i h ph ả ệ ươ

: 1.1.2/ Bài toán kh u ph n th c ăn ẩ ứ ầ

% theo ử ụ ứ ạ ạ ỷ ệ Đ nuôi m t lo i gia súc ng ng P : kh i l ộ ể ng các ch t dinh d ấ ố ượ ưỡ ườ 1, P2 có trong các lo i th c ăn nh sau ạ i ta s d ng 3 lo i th c ăn A, B, C. T l ứ ư

Th c ănứ Ch tấ dinh d ngưỡ

A B C P1 20 10 10 P2 10 10 20

Yêu c u trong kh u ph n th c ăn c a lo i gia súc này: ứ ủ ạ ầ ẩ ầ

ả ề ấ ấ ng P ng P ấ ấ ưỡ ưỡ

ng th c ăn c n mua sao - Ch t dinh d - Ch t dinh d - Giá 1kg th c ăn A,B,C t ứ Yêu c uầ : Hãy l p mô hình bài toán xác đ nh kh

1 ph i có ít nh t là 70g và nhi u nh t là 80g 2 có ít nh t là 90g ấ ng ng là 2.000đ, 1.000đ, 2.000đ ươ ứ ượ

ối l ậ ị ứ ầ cho t ng chi phí ít nh t. ổ ấ

L p mô hình bài toán : ậ

ng ng là s g th c ăn A, B, C c n mua G i xọ 1, x2, x3 t ươ ứ ứ ầ ố

1 + x2 + 2x3

- T ng chi phí Z = 2x ổ

- Hàm l ng ượ ng các ch t dinh d ấ ưỡ

P1: 0,2x1 + 0,1x2 + 0,1x3 thu c [ 70,80] (g) ộ

(

1, 2,3

= j

‡ P2: 0,1 x1 + 0,1x2 + 0,2 x3 ≥ 90 (g) )

Bài toán: Tìm xj (j= 1,2,3) sao cho

min Z = 2x1+ x2 + 2x3 ﬁ

700

800

x 1 x 1 +

2 2

900

x 1 2 xxx , 2 1

‡ (cid:236) (cid:239) £ (cid:239) (cid:237) ‡ (cid:239) (cid:239) ‡ (cid:238)

ng đ ờ ả ể ả ữ ế ườ ả ưỡ ố ơ ng c p I không nh h n 20% t ng chi u dài đ ị ử ng, trong đó s km đ ượ ổ ủ ề ấ ng nh a A ự ẻ ng đ c s n k ườ ượ ơ ủ c s n k v ch c a ẻ ạ ơ 1.1.3/ Bài toán th i gian thi công ng n nh t: ấ ắ Đ đ m b o hoàn thành k ho ch, đ n v s a ch a và b o d ơ ạ c n g p rút hoàn thành 50km s n v ch m t đ ặ ườ ạ ấ ầ v ch c a đ ỏ ơ ạ đ ườ ấ ườ ng c p II và c p III. ị ấ ơ ỉ ề ệ ể gian hoàn thành 1km đ ấ Đ n v A ch có 1 dây chuy n ( ng ng c p I, II, III t ườ Đ nh m c ti n s n cho 1km đ ườ ề ơ ứ ị ể ờ i, máy) đ làm vi c này. Trong khi đ th i ườ ng ng là 12 ngày, 8 ngày và 6 ngày. ươ ứ ng c p I, II, III t ấ ứ ệ ng ng là 30, 20 và 15 tri u ệ ệ i ch còn 120 (tri u ươ ờ ớ ỉ đ ng, trong khi kinh phí dành cho công vi c này trong th i gian t ồ đ ng). ồ Hãy l p mô hình xác đ nh chi u dài s n k v ch cho m i c p đ ơ ẻ ạ ị ổ ng sao cho t ng ỗ ấ ườ ề th i gian th c hi n là ng n nh t, đ ng th i đ m b o v kinh phí mua s n. ơ ồ ả ề ờ ả ậ ự ệ ắ ấ ờ

L p mô hình: ậ ng ng c p đ G i xọ 1, x2, x3 là chi u dài (km) d đ nh th c hi n trong t ự ị ự ề ệ ươ ứ ấ ườ ạ ng lo i I, II, III khi đó.

ụ

1, x2, x3 0‡

t y u: x M c tiêu th i gian: Z = ờ ng: Yêu c u kh i l ố ượ ầ Yêu c u ch ng lo i: ạ ủ ầ Yêu c u kinh phí ầ Đi u ki n t ệ ấ ế ề Bài toán:

1, x2, …, xn) sao cho

1.2/ Đ NH NGHĨA VÀ CÁC D NG BÀI TOÁN QUY HO CH TUY N TÍNH Ạ Ế Ạ ị ạ ạ ổ

min

j xc

= 1

ﬁ (max) (1) Ị 1.2.1/ Đ nh nghĩa: Bài toán quy ho ch tuy n tính d ng t ng quát: tìm (x ế n f (x) = c1x1+ c2x2 + cnxn = (cid:229)

V i đi u ki n ề ệ ớ

œ=

1, 2,..,

)(2)

a x ij

b i ( i

= 1

= j

(1, 2,..., )(3)

0 0 Tùyý

(cid:236) £ Ø ø (cid:239) Œ (cid:229) (cid:239) Œ œ (cid:239) Œ œ ‡ (cid:239) º ß (cid:237) ‡ Ø ø (cid:239) Œ œ (cid:239) £ Œ œ (cid:239) Œ œ (cid:239) º ß (cid:238)

do + Các bi g i là các h s t ệ ố ự ọ

+ Các cj g i là h s hàm m c tiêu ( h s ) ệ ố ệ ố ụ ọ

+ aij g i là h s các ràng bu c chung ệ ố ộ ọ

+ f(x) g i là hàm m c tiêu ụ ọ

+ H (*) g i là h ràng bu c ộ ệ ệ ọ

(2) g i là ràng bu c chung (có m ràng bu c) ọ ộ ộ

(3) g i là ràng bu c bi n (có n ràng bu c) ế ọ ộ ộ

- M t ph ộ

ng án (P.A) n u x th a (*) t p h p t t c các ợ ấ ả ế ậ ỏ ng án g i là mi n ràng bu c kí hi u là D ph Vector x = (x1, x2, … xn) g i là ph ề ươ ươ ệ ọ ộ ọ

opt

ươ f (min f) ho c c c đ i (max f) g i là ph ủ ng án làm cho hàm m c tiêu đ t c c ti u ( ng v i bài toán tìm min c a ạ ự ể ng án t ươ ặ ự ạ ớ c ký hi u là x ệ ứ i u đ ố ư ượ ụ ọ

Nghĩa là:

BT min: " x ˛ D : f (x) ‡ BT max: " x ˛ D : f (x) £ f (xopt) f (xopt)

Gi ả i bài toán quy ho ch tuy n tính là tìm các ph n t ế t ầ ử ố ư i u (n u có) ế ạ

ng đ ng nhau n u chúng có chung ế ọ ươ ươ ế i u. ph n t + Hai bài toán quy ho ch tuy n tính g i là t ạ t ầ ử ố ư

M nh đ : ề Quan h gi a max f và min f ệ ữ ệ

)( xf

max

= -

g x ( )

f x

( ) min

x D

(cid:222) (cid:236) (cid:222) (cid:236) (cid:239) ˛ (cid:237) (cid:237) (cid:219) ˛ (cid:238) (cid:239) (cid:238)

1.2.2/ Bi u di n bài toán quy ho ch tuy n tính d i d ng ma tr n: ế ể ễ ạ ướ ạ ậ

G iọ

...

a 12

a 1

Ø ø

Œ œ

a 11 a 21 ...

Œ œ

a mn

a m 1

º ß

là ma tr n ậ c p m*n các h s các ệ ố ấ ràng bu c chung ộ

x1 … , CT = (c1, c2, …,cn) X = xn

B = …. bm Lúc đó bài toán quy ho ch tuy n tính đ c phát bi u ế ạ ượ ể

Tìm x = ( x1, x2, …, xn) sao cho

f(x) = CT x ﬁ min (max)

th a mãn: ỏ

A.X  B

X ≥ 0 ; trong  ≥ ≤ =

ế ổ ủ ế ạ ắ 1.2.3/ Các d ng c a bài toán quy ho ch tuy n tính và các quy t c bi n đ i. ạ 1.2.3.1: D ng chính t c ạ ắ

ﬁ

)

f x ( )

( min max

c x j

(cid:229)

1, 2...,

)

a x ij

b i ( i

(cid:236) (cid:229) (cid:239) (cid:237)

(cid:239) ‡

(

)

j x

= j

1, 2,...,

(cid:238)

Ta nh n xét r ng, b t kỳ bài toán quy ho ch tuy n tính nào cũng có th đ a v ể ư ề ế ạ ấ ằ d ng chính t c nh các quy t c bi n đ i sau: ạ ậ ắ ắ ờ

ổ • N u ràng bu c có d ng : ế ộ ế ạ n

xa ij

b i

‡ (cid:229)

j ng : n

thì ta đ a v d ng t ng đ ư ề ạ ươ ươ

xa ij

b i

= 1

- (cid:229)

nx + ‡

1 0 •

v i ớ là n ph ) ụ

ẩ N u ràng bu c có d ng : ộ ế ạ

£ (cid:229)

a x ij

b i

= 1

j ng n

thì ta đ a v d ng t ng đ ư ề ạ ươ ươ

+ =

xa ij

x n

b i

= 1

(cid:229)

nx + ‡

1 0

v i ớ là n ph ) ụ ẩ

Chú ý:

- H s c a n ph trong hàm m c tiêu f(x) là 0. ệ ố ủ ẩ ụ ụ

j’ : xj’ = - xj (xj’ ≥ 0)

j không ràng bu c v d u ta thay b ng hi u c a 2 bi n không, t c là

- N u bi n x ế j ≤ 0 thì ta thay b ng xằ ế

ế ệ ủ ề ấ ứ ế ằ ộ - N u bi n x ế đ t ặ

xj = xj’ - xj’’ v i xớ j’ ≥ 0, xj’’ ≥ 0

i hàm m c tiêu theo các Đây không ph i là bi n ph nên ph i tính l ế ụ ả ả ạ ụ bi n m i. Chú ý r ng:ằ ớ ế Các ví d : đ a các bài toán QHTT sau v d ng chính t c ụ ư ề ạ ắ

min 1/ f(x) = -2x1 +3x2 - 2x3 ﬁ

x 1

3 3

- (cid:236) (cid:239) (cid:237)

x 1 ,

3 xxx 1 2

(cid:239) ‡ (cid:238)

1, x2, x3 ≥ 0

Ví d 1 này là d ng chính t c vì x y ra d u = và x ụ ả ấ ạ ắ

2 x

x 3 x 3

‡ - (cid:236) 2/ f(x) = x1 + x2 + x3 - 2x4 ﬁ x (cid:239) max 2 = - - (cid:237)

x 1 x 5 1 ,

xxxx , 2 1

(cid:239) £ (cid:238)

1, x2, x3, x4 ≤0

Gi i Ví d 2: VD2 không ph i là chính t c vì vi ph m 2 ch : ≥ 2; x ả ụ ắ ạ ả ỗ

- - (cid:236)

axmﬁ Ta có: f(x) = x1 + x2 + x3 - 2x4 + 0 . x5 = x 2 2 x 2

x 1 x 5 1

x 3 x 3

x 5 = 3 x1 = - x1’ ; x2 = -x2’ ; x3 = -x3’, x4 = -x4’ (v i xớ 1’, x2’, x3’, x4’ ≥ 0) Ta thay x1, x2, x3, x4 vào (1)

(1) (cid:237) - - (cid:238)

(cid:236)

-+ x x x ' '2' 1 2 3 ++ x '5 x 1 2

= x 2' 5 = x 3'3' 3

(cid:237) - (cid:238)

Tìm x1, x2, x3, x4, x5, x1’, x2’, x3’, x4’ (x5 là n ph ) ụ ẩ

3/ f(x) = - x1 + 2x2 +1/3 x3 - 2x4 ﬁ min

Tìm x1, x2, x3, x4

- - (cid:236)

x 3 x 4

x 2 x 2 3 +

= 2/142

(cid:239) - £ - (cid:239) (cid:237)

(cid:239)

x 1 x 2 x x 1 3 xxxx , 1 2 4

(cid:239) ‡ (cid:238)

i VD3 : VD3 này không ph i chính t c vì vi ph m ả ạ m t ch là ≤ -2 ắ ỗ ộ ả

min Gi f (x) = -x1 + 2x2 + 1/3 x3 - 2x4 + 0 . x5 ﬁ

- - (cid:236)

x 3 x 4

7 =+ x 5

= 2/142

(cid:239) - (cid:239) (cid:237)

x 1 x 2 x 1

x 2 x 2 3 ++ x 3

(cid:239)

(cid:239) (cid:238)

Tìm x1, x2, x3, x4, x5 ≥0, (x5 là n ph ) ụ ẩ

4/ f(x) = x1 + 3x2 -2x3 ﬁ min

Tìm x1, x2, x3, x2’, x2’’, x3’, x4, x5

-+ x 2

£ (cid:236)

x 1 2

x 7 3 =+ x 3

x 2

x 2 +

x 2

x 3

x 1

(cid:239) - - (cid:239) (cid:237) ‡ - (cid:239)

x 1

x 3

(cid:239) £ ‡ (cid:238)

ả ư ữ ề ạ ờ ồ ể ư ề ươ c c ng thêm n ph x c tr đi m t n ph ả ng trình v ph ấ ượ ộ ộ i bài 4: Đ đ a bài toán trên v d ng chính t c, ta ph i đ a nh ng ràng bu c ắ ng trình, đ ng th i m i n s ph i không âm. Có nghĩa là ràng ọ ẩ ố ụ ụ 4 ≤ 0, ràng bu c th 3 đ ộ ả ứ ộ ẩ ượ ừ ẩ Gi b t ph ươ ấ bu c th nh t đ ứ ộ x5 ≥ 0

Thay x3 = - x3’ (x3’ ≥ 0)

1 + 3x3 + 2x3’ ﬁ min

x2 = x2’-x2’’(x2 ≥0, x2’’ ≥0)

v y bài toán tr thành f(x) = x ở ậ

x '2 3

(cid:236)

=+ x 4 =

x 1 2

++ x 2 4

(cid:239) - - - (1) (cid:237)

x 1 +

x 2 +

12 =

x 3 x '8 3

x 5

x x 1 Thay x2 vào (1) ta có

(cid:239) - (cid:238)

+

=

- (cid:236)

3

7 '

x 2

(cid:239)

x 4 =

- - - (cid:237)

x 1 2

x 2

(cid:239)

+ + x x '2'' 2 3 + x ''4'4 2 +

x 1 +

12 =

- -

4

(cid:238)

x 1

x 3 x '8''3'3 x x 10 2 3 2 x1, x2’, x2’’, x3’ ≥ 0; x4, x5 ≥ 0 (x4, x5 là n ph ) ụ

x 5 ẩ

1.2.3.2/ D ng chu n (chu n t c ) ạ ẩ ẩ ắ : ế ẩ ạ ạ ắ ạ ỏ Bài toán quy ho ch tuy n tính là d ng chu n BT QHTT d ng chính t c th a các đi u ki n sau: ệ ề

- Các bi bên v ph i c a các ràng bu c chung ≥ 0 - M i ràng bu c chung có bi n c s t ế ả ủ ộ ỗ ế ơ ở m t ràng bu c chung và h s là 0 ứ các ràng bu c còn l i. ộ ế ơ ở ươ ở ệ ố ng ng. Bi n c s là bi n có h s là ế ơ ế ạ (T c là các bi n c ứ ộ +1 ệ ố ộ ở ộ ậ ơ ị s s t o thành m t ma tr n đ n v ). ộ ở ẽ ạ - Các bi n không c s ( không ph i là bi n c s ) g i là bi n t do ế ơ ở ọ ơ ở ế ự ế ả

Ví d 1:ụ Xem xét bài toán sau đây đã chu n t c không, tìm ph ẩ ắ ươ ng án c b n ban ơ ả đ uầ

min f = x1 + 2x2 + x3 + x4 ﬁ

(cid:236) -

7(1) =

5(2)

x 1 x 2 2

x 2 + x 3

(cid:239) (cid:237)

= x 3 + x 4 (1,2,3, 4)

= j

(cid:239) ‡ (cid:238)

j ≥0

Bài toán này là d ng chu n t c vì ph ạ ẩ ắ ươ ộ ng trình (1,2) đ u x y ra d u b ng, ràng bu c ề ả ấ ằ bi n xế

- H s hàm m c tiêu : c1 = 1, c2 = 2, c3 = 1, c4 = 1 ệ ố ụ

: m = 2 - Ràng bu c chung ộ

- Ràng bu c bi n ế : n = 4 ộ

- H s ràng bu c chung : a11 = 1, a12 = 1, a13 = 1, a21 = 0, a22 = 1, a23 = 1, a24 = 1 ệ ố ộ

1 = 7, b2 = 5

- Các h s t do: b ệ ố ự

Ta có h s ma tr n ệ ố ậ A = x1 x2 x3 x4

1 1 -1 0

0 2 1 1

do Ta có x1, x4 là bi n c s ế ơ ở ; x2, x3 là bi n t ế ự

ng án c b n ban đ u ơ ả ầ : x2 = x3 = 0 thay vào (1) và (2) c a h trên ta ủ ệ ng án c b n ban đ u x = (7,0,0,5) đ c x V y ph ươ ậ 1 = 7, x4 = 5. Ph ươ ơ ả ầ ượ

Ví d 2ụ :

min f(x) = x2 - x5 ﬁ

1(1)

- (cid:236)

3(2)

x 1 x 3 2 x 2

x 2 + x 3 x

2(3)

+ 2

+ 4

(cid:239) - (cid:239) (cid:237) - (cid:239)

= x 5 = - x 5 = x 5 = j

(1, 2,...,5)

(cid:239) ‡ (cid:238)

Đây ch a ph i là bài toán d ng chu n: ư ẩ ạ ả

i = -3 nên ta nhân 2 v v i -1

Ph ng trình trên có h s t do b ươ ế ớ

x 5

ệ ố ự = - (cid:236)

)1(1 =

2 +

)2(3

x 1 3

(cid:239) - - (cid:239)

)3(2

2 x

(cid:237) - (cid:239)

x 3 x 4 =

x 5 x 5 )5,1(

2 ;0

(cid:239) ‡ (cid:238)

- H s hàm m c tiêu : c1 = 1, c2 = -1 ệ ố ụ

: m = 3 - Ràng bu c chung ộ

- Ràng bu c bi n ế : n = 5 ộ

11 = 1, a12 = 1, a13 = 1, a14 = 1, a15 = -2, a21 = 0, a22 = -3,

- H s ràng bu c chung: a ệ ố ộ

a23 = 1, a24 = 0, a25 = -1, a31 = 0; a32 = -2, a33 = 0, a34 = 1, a35 = 1

1 = 1, b2 = 3, b3 = 2

j≥0

- Các h s t do: b ệ ố ự

- Ràng bu c bi n: x ộ ế

Ta có h s ma tr n: ệ ố ậ

A =

x1 1 0 0 x2 1 -3 -2 x3 0 1 0 x4 0 0 1 x5 -2 -1 1

Ta có x1, x3, x4 là bi n c s ế ơ ở

x4 = 2

x3 = 3

x1 =1

x2, x5 là bi n t ế ự Thay x2 = x5 = 0 vào (3) ﬁ Thay x2, x5 = 0 vào (2) ﬁ Thay x2, x5 = 0 vào (1) ﬁ V y ph ơ ả ươ ậ ng án c b n ban đ u là: x = (1,0,3,2,0) ầ

1.3/ Gi ng pháp hình h c ả i bài toán quan h tuy n tính 2 bi n b ng ph ế ế ằ ệ ươ ọ :

Trong tr i b ng ph ng pháp hình ế ể ả ằ ươ : ng h p bài toán QHTT có 2 bi n ta có th gi ườ h c, ta áp d ng k t qu sau đây ế ọ ợ ả ụ

c> m t mi n là t p t ề

ườ ề ề ặ ẳ ộ 1/ Đ ng th ng ax + by = c chia m t ph ng t a đ thành 2 mi n, m t mi n là t p ậ ẳ : ax + by < t c đi m M(x,y) th a ax + by t c các đi m M(x,y) ể ọ ộ ậ ấ ả ỏ ộ t ấ ả ể c

˛m ứ

´ ng th ng ax + by = m, ậ ng m c (t ứ ươ là t p h p các đ ẳ ợ ườ ng ng v i giá tr c a m c m) ( đ ườ ứ ị ủ ớ ng th ng song song ng m c có ứ ườ ọ 2/ Cho đ ẳ v i nhau mà ta g i là đ ườ ớ pháp vector n = (a,b))

N u ta duy chuy n m t đ ế ộ ườ ẳ ọ ng ộ ườ tăng, ẳ ng m c) đ n m t đ ế ứ ng ng c a m ứ ị ươ ủ ng ng c a m th ng khác trong h còn theo h ng th ng trong h (m t đ ộ ườ ể ọ theo h ngướ c a vector n =(a,b) thì giá tr t ủ ượ ạ thì giá tr t i c l ị ươ ứ gi mả . ủ ướ ng ng

gi i bài toán ta áp d ng Trong th c hành ự ả ụ :

+ V pháp vector n = (a,b) chính là vector OC v i C(a,b). V đ ẽ ườ ớ ng m c (d) ứ đi qua O ^ v i vector n. ẽ ớ

+ D ch chuy n song song các đ ng m c theo h ị ườ ng ng ứ ẽ ứ ớ ứ ướ ướ c l ượ ạ ị ng vector n = (a,b) thì giá tr ớ i m c s gi m ( ng v i ứ ẽ ả ứ ể m c s tăng ( ng v i bài toán fmax) và theo h bài toán fmin)

ể ế ệ ng m c cu i cùng này là l i gi + D chị ừ ế ố ể ứ ể ằ ờ chuy n (d) cho đ n khi nào vi c d ch chuy n ti p theo không làm (d) ị c t D n a thì d ng. Khi đó các đi m OFD n m trên đ ả i ườ ữ ắ c n tìm. ầ

max Ví d 1ụ : f(x) = 2x1 + x2 ﬁ

‡ (cid:236)

x 1 + x 1

x 2 x 2 2

x 2

(cid:239) - £ (cid:239) (cid:237) - £ (cid:239)

x 1 x x , 1 2

Xopt = (4,5), fmax = 13

(cid:239) ‡ (cid:238)

Ví d 2ụ : Cũng nh VD 1 nh ng fmin ư ư

Đs: X0pt1 = (0,2), Xopt2 = (1,0), fmin = 2

min

- ‡ (cid:236) Ví d 3ụ : f(x) = 3x1 + 4x2 ﬁ x 2 (cid:239) - ‡ (cid:237)

x 2 0

x 1 + x 1 x y , 1 1

D = q , bài toán vô nghi mệ

(cid:239) ‡ (cid:238)

max Ví d 4ụ : f(x) = 3x1 + 4x2 ﬁ

x 2

- ‡ (cid:236)

(cid:239) - £ (cid:237)

x 2 0

x 1 + x 1 x y , 1 1

i bài toán b ng ph

ng pháp hình h c ta xét

ể ể

ủ

ệ

ả

ằ

ươ

ọ

(cid:239) ‡ (cid:238)

1, P2 cùng s n xu t 2 lo i s n ph m A, B. S ẩ 1, P2 nh sau:

ưở ả ố ấ c s n xu t ra và chi phí m i gi

Đ hi u rõ h n ý nghĩa c a vi c gi ơ sau đây: ví d th c t ụ ự ế Ví d (5): ộ ụ đ n v s n ph m các lo i đ ẩ ị ả ơ

M t công ty có 2 phân x ạ ượ ả ạ ả ho t đông P ạ ng P ấ ư ờ ỗ

Phân x ng 1 Phân x ng 2

ả ả ẩ ẩ

S n ph m A S n ph m B Chi phí ưở 250 100 600.000 ưở 250 200 1.000.000

c yêu c u đ t hàng là 5.000 đ n v s n ph m A và 3.000 đ n v ậ ượ ị ả ẩ ặ ầ ơ ơ ị Công ty nh n đ s n ph m B. ẩ ả

Hãy tìm cách phân ph i th i gian cho m i phân x ờ ố ỗ ưở ỏ ng ho t đ ng sao cho th a ạ ộ mãn yêu c u đ t hàng và chi phí ít nh t. ấ ặ ầ

1, P2 ho t đ ng.

t là s gi c n b trí cho P G i xọ 1, x2 l n l ầ ượ ố ờ ầ ố ạ ộ

n đ

ng pháp đ n hình ng pháp đ n hình ´ ˛ 1.4/ Ph ơ ươ 1.4.1/ C s c a ph ươ ơ ở ủ i: T p G T p l ậ ậ ồ : ơ c g i là t p l ượ ọ ậ ồ ế i n u 2 đi m x, y thu c G thì c đo n [x, ộ ể ả ạ y] cũng thu c Gộ

T p l i: ậ ồ

Không là t p l i: ậ ồ

Đi m c c biên ự ể

ượ ọ ẳ c g i là đi m c c biên c a G n u trong G không m t đo n th ng ế ự ủ ể ạ ộ nào nh n x là đi m trong. Đi m x ể ậ : ˛ G đ ể

1, A2, A3 ta g i chúng là ph ọ

Tr l ự ụ ấ ươ ng ở ạ án c c biên (pacb) ( ph ng án c s , ph ng án c b n). i ví d ** ta th y D có 3 đi m c c biên A ơ ả ơ ở ể ươ ươ ự

i toán quan ể ả ươ ủ h tuy n tính ta ch c n xét trên t p h u h n các ph ệ : Vì tính quan tr ng c a ph ọ ậ ữ ạ ỉ ầ Nh n xét ậ ế ng án c c biên ta th y đ gi ấ ự ng án c c biên. ự ươ

C s c a ph ng pháp đ n hình : ơ ở ủ ươ ơ

ể ỉ ầ ươ ng án t ấ ầ

c l p l ượ ậ ạ ươ ể i ch ng nào còn có kh ng án c b n là h u h n nên sau m t s ữ ể ấ ươ ng án t c ph i u c a bài t p quan h tuy n tính ta ch c n xét nh ng ữ ế ậ ệ o nào đó. Ta tìm cách ng án c b n ban đ u x ơ ả ươ ộ i u thì ta tìm cách chuy n sang m t ng án t ả ừ ộ ố ạ i u c a bài toán ho c s k t lu n vì ậ ơ ả ố ư ủ ặ ẽ ế ượ Đ tìm ph ủ ố ư ươ m t ph ng án c b n. Xu t phát t ph ơ ả ừ ộ đánh giá nó. N u nó ch a ph i là ph ư ế ố ư ươ ả ớ 1 t t h n. Quá trình này đ ng án c b n m i x ph ơ ả ố ơ năng th c hi n s di chuy n y và vì s ph ố ệ ự ự c l p ho c s thu đ h u h n b ươ ặ ẽ ữ ạ ướ ặ hàm m c tiêu không b ch t. ị ặ ụ

Ta gi s bài toán đang d ng (chu n- fmin) ả ử ở ạ ẩ

)(

min

=(cid:229)

j xa

= 1

ﬁ

)

a x ij

b i ( i

= 1

(cid:236) (cid:229) (cid:239) (cid:237)

j x

b i

(cid:239) ‡ ‡ (cid:238)

1.4.2/B ng đ n hình ả ơ

c1 c2 ..... cm cm+1 cs ...... cn

Hệ số x1 x2 ... xm xm+1 xs ..... xn H nệ ẩ cơ b nả P.án cơ b nả

x1 b1 c1 a11 a12 a1n

x2 b2

c2 .... ... ..... cr xr br ar1 ar2 arm arn

.... ..... ...... cm xm bm am1 am2 amm amm+1 amn

1m+

m n+

D D D D D f(x) f(xo)

Trong n n ta có ẩ

x1, x2, ..., xm : các n c b n ẩ ơ ả

ơ ả

0) = c1b1+ .....+cmbm ứ

)

D = j

a a j ij

= ( c i i

= 1

xm+1, ..,xn : các n không c b n. ẩ 0) đ c tính nh sau: f(x ư c tính b ng công th c sau đ ượ ằ Giá tr c a f(x ượ ị ủ Các h s ki m tra ệ ố ể n - (cid:229)

Chú ý r ng ằ 1=2=…m =0. 1.4.3/ Thu t toán đ n hình chi ti t ậ ơ ế : (sau khi có b ng đ n hình) ả ơ

B i u c a ph ng án : c 1ướ : - Ki m tra tính t ể ố ư ủ ươ

ng án t ng ng là t i u - N u ế j < 0 v i m i j (j=1,n) thì ph ọ ớ ươ ươ ứ ố ư

- Ng c l i i (có ít nh t 1) c 2 j > 0 thì chuy n sang b ượ ạ : n u t n t ế ồ ạ ấ ể ướ

B c 2ướ :

ộ j >0 mà v i m i a trên c t x ộ j

" =1,m) nghĩa là m i ph n t ọ ij ≤ 0 ( ọ ầ ử c ng. Ng ng thu t toán. K t lu n bài toán không gi i đ ả ượ ậ ế

ế đ u không d ề - N u có m t ươ ớ ậ ừ

c 3 - N u v i m i ế ớ ỗ j > 0 đ u có ít nh t m t a ộ ij > 0 thì chuy n sang b ề ể ấ ướ

B c 3ướ : ( ch n n đ a vào, n đ a ra kh i h n c b n) ỏ ệ ẩ ơ ả ọ ẩ ư ẩ ư

- n xẨ s là n đ a vào n u ẩ ư ế s = max{j >0}.

- n đ a ra x r br Ẩ ư

bi =l min ) = (ars 0‡

ais ars

r ( ng v i n đ a ra) ớ ẩ

ộ s ( ng v i n đ a vào) và dòng x ớ ẩ ư ứ ư ứ rs >0). Ph n t g i là ph n t ọ ầ ử rs n m trên c t x a ằ tr c ( l u ý r ng a ư ầ ử ụ ằ

Sau khi xác đ nh đ c n đ a vào và đ a ra ta chuy n sang b c 4. ị ượ ầ ư ư ể ướ

B t h n) c 4ướ : (C i ti n ả ế : tìm ph ươ ng án c b n m i t ơ ả ớ ố ơ

Xây d ng b ng đ n hình m i t ng ng v i h n c b n m i thu đ c t ớ ệ ẩ ứ ượ ừ ệ ẩ h n ơ c b ng cách thay x ự ả ướ ằ ớ ươ ơ ả r b i xở s ( trên c t h s ta thay c ớ r b i cở s) ộ ệ ố c b n tr ơ ả

s (m i đ

r cho ars

c dòng x c đ a vào) ta chia dòng x - Đ thu đ ể ượ ớ ượ ư

còn l i b ng 0, s = 0. ả ử

còn l - B ng đ n hình m i ơ Các ph n t ầ ử ớ : Trên dòng xs cũ thì ars = 1 các phân t i (k c dòng ạ ạ ằ j) ta tính theo quy t c hình ch nh t ữ ậ ể ả ắ

jk (cũ) ark. ajs ars

ajk (m i) = a ớ

C t k ộ ark c t sộ ars Dòng r chia

nhân

Dòng j zjk? ajs

c 1 -> b c 2->b c 3-> ướ ướ b ứ ự ướ i yêu c u bài toán. c 1 i b Sau đó quay l ạ ướ C ti p t c ch y thu t toán nh trên theo th t ư ứ ế ụ ậ ạ c 1->,,,vv. Và tr l c 4->b b ả ờ ướ ướ ầ

Ví d 1: Gi ụ ả ế min i bài toán quan h tuy n tính sau: ệ f(x) = 6x1 + x2 + x3 + 3x4 + x5 - 7x6 + 6x7 ﬁ

x +

x 6 +

2 x

4 4

x 1 x 2 1 +

x 6 =

x 1

x (

)

4 j

5 7,1

- - (cid:236) (cid:239) - - - (cid:239) (cid:237) - (cid:239) (cid:239) ‡ (cid:238)

0 = (0,3,9,0,2,0,0) có các

Bài toán có d ng chu n v i ph ng án c b n ban đ u x ạ ẩ ầ n c b n x ơ ả ớ 2, x3, x5 (n=7, m=3) ta có b ng đ n hình. ươ ả ơ ẩ ơ ả

P.án H sệ ố H nệ ẩ

6 x1 1 x2 1 x3 3 x4 1 x5 -7 x6 6 x7

1 1 1

0) = C1b1 + c2b2 + c3b3 = 1.3 + 1.9 + 1.2 = 14

cơ b n ả x2 x3 x5 f(x) 3 9 2 14 -1 -2 4 -5 1 0 0 0 0 1 0 0 -1 -4 2 -6 0 0 1 0 [1] 2 -3 7 1 -1 0 -6

V i f(xớ 2 = 3 = 5 = 0 (vì x2, x3, x5 là n c b n) ẩ ơ ả

2 = 1 * 1 + 1 * 0 + 1 * 0 - 1 = 0 4 = 1 * (-1) + 1 * (-4) + 1*2 - 3 = - 6

6 = 1*1+1*2+1*(-3) - (-7) = 7 7 = 1*1+1*(-1) + 1*0 -6 = -6

ả ơ ơ b t đ u dùng thu t toán đ n ắ ầ ậ hình v i b ướ

c 1 6 = 7 > 0 chuy n sang b ướ ể

c 3 c 2 6 > 0 có a16, a26 > 0 chuy n sang b ể

Ta đã có đ y đ thông tin trên b ng đ n hình, nên ta ớ ướ ắ ầ B ấ B B ví d này ch có ướ j >0, tuy nhiên 6 ầ ủ c b t đ u là b c 1ướ : Ta th y có c 2ướ : Ta th y ấ c 3ướ : Ch n n đ a vào ta đi tìm các c t có ọ ẩ ư ộ ở ụ ỉ

min

3 9 ; 1 2 c đóng khung a

(cid:236) (cid:252) (cid:237) (cid:253) suy ra x2 là n c b n b lo i kh i h n c b n ph n t ị ạ ỏ ệ ẩ ơ ả ẩ ơ ả ầ ử 16 = 1 a (cid:238) (cid:254) > 0 nên x6 là n đ a vào. ẩ ư Ch n n đ a ra : ọ ẩ ư Ta có : a16 =1, a26 = 2, (a16, a26 >0) 3 1

rs = a16 = 1 chuy n sang b

đ c 4 ượ ể ướ

B c 4ướ : Xây d ng b ng đ n hình m i ớ ự ả ơ

P.án H sệ ố H nệ ẩ

6 X1 1 X2 1 X3 3 X4 1 X5 -7 X6 6 X7

-7 1 1

cơ b n ả X6 X3 X5 f(x) 3 3 11 -7 -1 0 1 2 1 -2 3 -7 0 1 0 0 -1 -2 -1 1 0 0 1 0 1 0 0 0 1 -3 3 -13

6 v i h s c a x c 4.

i 8*4 = 32 đ i l ng trong ằ ầ ạ ạ ượ Ta thay x2 b ng x ớ ớ ệ ố ủ 6 là -7 ta c n tính l ứ ướ b ng m i theo các công th c trong b ả

Sau khi tính toàn b các giá tr trong b ng đ n hình m i ta quay l c 1: Ta ả ơ ớ ị i b ạ ướ

c 2. ộ th y ấ 1 > 0; 4 > 0 suy ra b ướ

t c a T i ạ 4 = 1 > 0 có t ấ ả 14, a24, a34 suy ra ng ng thu t toán. ừ ậ

K t lu n bài toán đã cho không có ph ng án t i u: ế ậ ươ ố ư

Ví d 2: Gi ụ ả ế i bài toán quan h tuy n tính sau: ệ min f(x) = x1+ 4x2 - x3 - x4 + x5 + 3x6 ﬁ

1 =

x +

2 x

x 1 x 1 +

2 +

4 x 5 =

(

3 x 2 3 + )

x =

x 1 x

3 6,1

- (cid:236) (cid:239) - (cid:239) (cid:237) (cid:239) (cid:239) ‡ (cid:238)

0 = (0,0,0,1,2,5)

4, x5, x6 ( n = 6, m = 3)

Bài toán có d ng chu n , v i ph ng án c b n ban đ u x ạ ẩ ớ ươ ơ ả ầ

Các n c b n x ẩ ơ ả

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

P.án H sệ ố

-1 1 3

0) = c1b1 + c2b2 + c3b3 = (-1) * 1 + 1 * 2 + 3 * 5 = 16

H nệ ẩ c b n ơ ả x4 x5 x6 f(x) 1 2 5 16 1 x1 2 2 1 2 4 x2 -1 [4] 2 7 -1 x3 5 -2 1 -3 -1 x4 1 0 0 0 1 x5 0 1 0 0 3 x6 0 0 1 0

V i f(xớ

4 = 5 = 6 = 0 (vì x4, x5, x6 là n c b n) ẩ ơ ả

1 = (-1) * 2 + 1 * 2 + 3 * 1 - 1 = - 2 + 2 + 3 - 1 = 2

2 = (-1) * (-1) + 1 * 4 + 3 * 2 - 4 = 1 + 4 + 6 - 4 = 7

3 = ( -1) * 5 + 1 * (-2) + 3 * 1 - (-1) = - 5 -2 + 3 + 1 = - 3

ả ắ ầ ậ ơ hình v i b ầ ủ c đ u là b c 1. ướ

c 2 ướ ể

c 3 2 >0 và có a22 và a32 >0 chuy n sang b ướ ể Ta đã có đ y đ thông tin trên b ng đ n hình, nên ta b t đ u dùng thu t toán đ n ơ ớ ướ ầ B B B : c 1ướ : Có 2 = 7 > 0 chuy n sang b c 2ướ : Ta th y có ấ c 3ướ : Ch n n đ a vào ọ ẩ ư

bài này có 2 > 0 nên x2 là n đ a vào - Ta đi tìm các c t ộ j >0; tuy nhiên ở ẩ ư

: Ta có a22 = 4, a32 = 2 (a22, a32 > 0) - Ch n n đ a ra ọ ẩ ư

g = min

2 4

5 2

2 4

(cid:252) (cid:236) (cid:253) (cid:237) ﬁ x5 là n c b n b lo i kh i h n c b n ỏ ệ ẩ ơ ả ẩ ơ ả ị ạ (cid:254) (cid:238)

rs = a22 = 4 chuy n sang b

Ph n t c đóng khung a c 4 ầ ử 22 = 4 đ a ượ ể ướ

B c 4ướ : Xây d ng đ n hình m i ớ ự ơ

P.án H sệ ố H nệ ẩ

1 X1 4 X2 -1 X3 -1 X4 1 X5 3 X6

-1 4 3

13 và a33 > 0 ﬁ

cơ b n ả X4 X2 X6 F(x) 3/2 ½ 4 25/2 5/2 ½ 0 -3/2 0 1 0 0 9/2 -1/2 2 1/2 1 0 0 0 ¼ ¼ -1/2 -7/4 0 0 1 0

3 là n đ a vào ẩ ư

ọ ẩ ư ch n xọ (cid:252) (cid:236) ﬁ (cid:253) (cid:237) - Ch n n đ a vào: ta có g = min a x4 là n đ a ra. ph n t - Ch n n đ a ra: ọ ẩ ư ẩ ư ầ ử 13 là ph n tầ ử (cid:254) (cid:238) 3 > 0; l ạ 6 4 18 2 i có a 6 18

đóng khung; v y aậ rs = a13 = 9/2

P.án H sệ ố H nệ ẩ

1 X1 4 X2 -1 X3 -1 X4 1 X5 3 X6

-1 4 3

cơ b n ả X3 X2 X6 f(x) 1/3 2/3 10/3 37/3 5/9 7/9 -10/9 -16/9 0 1 0 0 1 0 0 0 2/9 1/9 -4/9 -1/9 1/18 5/18 -11/18 -16/9 0 0 1 0

1= (-1) * 5/9 + 4 * 7/9 + 3 * (-10)/9 - 1= - 16/9

4= - (-1) * 2/9 + 4 * 1 /9 +3 * (-4/9) - (-1) = - 1/9

,0,0,

opt =

2 3

1 3

10 3

5= (-1) * 1/18 + 4 * 5/18 + 3 * (-11/18) - 1 = - 16/9 (cid:246) (cid:230) (cid:247) (cid:231) V y bài toán có ph n t i u là x ; f(min) =37/3 t ầ ử ố ư ậ ł Ł

ﬁ min)

Chú ý : Bài toán d ng chu n f ẩ max. ạ

ư ề ạ ẩ

Cách 1 : ( gián ti pế : đ a v d ng chu n f BT1 f ﬁ Max  g=-f ﬁ min BT2 X ˛ D

(cid:219) t x cũng là ph n t i u c a bài toán t N u xế ầ ử ố ư ủ ầ ử ố ư ủ 2. Và giá tr c a hàm m c tiêu là f i u c a bài t p 1 ậ max = - gmin. D X ˛ opt là ph n t ụ ị ủ

Cách 2: (Tr c ti p) ự ế

ﬁ d ng f Thu t toán cũng gi ng nh thu t toán ố ậ ậ ở ạ min. Ch thay đ i ỉ ổ

B c 1: i u ố ư ư N u ế j ≥ 0 " ướ

ng ng thu t toán k t lu n bài toán ng án là t aij ≤ 0 (cid:222) j thì ph ươ ộ j < 0 mà " ừ ế ậ ậ ế B không gi N u có m t c. c 2: ướ i đ ả ượ

c 3: Ch n n đ a vào: B s = min j, j < 0 ( n đ a vào n c b n là n có j ọ ẩ ư ẩ ơ ả ẩ ư ẩ ướ âm bé nh t) ấ

Ví d :ụ max f = - x1 + 4x2 + 2x3 - x4 (cid:222)

x 1

x 3

x 1

(cid:236) - (cid:239) (cid:237)

(

= )

x =

4 4,1

(cid:239) ‡ (cid:238)

1 + 4x2 + 2x3 - x4

ﬁ Gi i: f = -x min ả

x 1

x 3

x 1

(cid:236) - (cid:239) (cid:237)

(

= )

x =

4 4,1

(cid:239) ‡ (cid:238)

1= - 1; c2 = 4; c3 = 2; c4 = - 1

- H s m c tiêu: c ệ ố ụ

1 = 4, b2 = 7

- H s t do: b ệ ố ự

- Ràng bu c chung m = 2 ộ

11 = 2, a12 = - 1, a13 = 1, a21 = 3, a22 = 1, a23 = 1

- Ràng bu c bi n n = 4 ộ ế

ệ ố ủ ộ

min ﬁ min

- H s c a các ràng bu c chung: a x1 - 4x2 - 2x3 + x4 ﬁ G = - f ﬁ fmax = - gmin (x0) = (0,0,4,7)

P.án H sệ ố H nệ ẩ

1 X1 -4 X2 -2 X3 1 X4

-2 1 3

cơ b n ả X3 X4 f(x) -2 4 7 -1 -1 1 -1 1 0 0 0 1 0

1 j 2 3 4

gmin = - 50 Đáp s : xố opt c a bài toán II : x = (0,7,11,0), ủ

Cách 2: Tính tr c ti p ự ế

H sệ ố ệ ẩ ơ H n c b n ả

2 -1

P.án c b n ơ ả 4 7 1 X3 X4 F(x) -1 X1 2 3 2 4 X2 -1 1 -7 2 X3 1 0 0 -1 X4 0 1 0

2 4

11 7 50 X3 X2 f(x) 5 3 23 0 1 0 1 0 0 1 0 7

(cid:222) fmax = 50 xopt = (0,7,11,0) ;

1.5/ Thu t toán đ n hình gi i bài toán QHTT d ng t ng quát ơ ậ ả ổ ạ

Khi xây d ng thu t toán đ n hình ta gi thi ự ậ ơ ả ế t m t ph ộ ẩ ạ ả i ta c n m t thu t toán gi i đ ế ẩ t là đã bi ế ự ế ườ ươ không ph i bài toán quan h ậ ơ ả ng án c b n ệ ả ượ c ầ ộ t c là bài toán có d ng chu n. Tuy nhiên trong th c t ứ tuy n tính nào cũng có d ng chu n. Đó là lý do ng ạ bài toán QHTT d ng t ng quát. ạ ổ

1.5.1/ Đ a bài toán QHTT d ng t ng quát v d ng chu n (bài toán M) ề ạ ư ẩ ạ ổ

i ≥ 0) không có ngay ph

N u bài toán QHTT (d ng chính t c, b ế ươ ắ vào đ có ngay ph ng án c b n ban ơ ả ng án c b n ban đ u. Bài toán có ộ ố ế ơ ả ươ ể ầ ả g i là bài toán (M). ạ đ u thì ta thêm m t s bi n gi ầ bi n gi ế ả ọ

Ví d :ụ Cho bài toán g c (p)

ố f = x1 - 2x2 +3x3 + x4 ﬁ min

x 1

x 3

(cid:236)

(cid:239) - - (cid:237)

(

)

5 =

x 1 x

x 3 4,1

(cid:239) ‡ (cid:238)