Bài giảng Lý thuyết tối ưu

Phan Lê Na

Khoa Công ngh Thông tin ệ



Trư ng Đ i h c Vinh ạ ọ ờ

 M c ụ đích:

Cung c p cho sinh viên m t s ph

i bài toán t

ộ ố

ấ

ương pháp gi

ả

ố ưu: Phương pháp

đơn hình, Phương pháp đơn hình đ i ng u, Ph

ẫ

ố

ương pháp Phân ph i. ố



TÀI LI U THAM KH O

Ả

Ệ

1. Nguy n Đ c Nghĩa,

ứ

ễ

T i ố ưu hoá, NXB GD 2002

2. Bùi Minh Trí-Bùi Th Tâm,

Lý thuy t Quy ho ch

ế

ạ

ế , NXB KH&KT 2002

Tuy n tính ế

ế

ầ

ệ Các phương pháp T i ố

3. Bùi Th Tâm-Tr n Vũ Thi u, ưu hoá, NXB KH&KT 2002

Lý thuy t Quy ho ch Tuy n tính

,

ầ

ế

ạ

4. Tr n Xuân Sinh, NXB SP 2003

5. Phan Lê Na, Giáo trình Lý thuy t T i

ế ố ưu, ĐH Vinh

2000

N i dung

ộ

Chương 0: M ở đ uầ

Chương 1: Phương pháp đơn hình

ố ẫ

Chương 2: Phương pháp đơn hình đ i ng u

Chương 3: Phương pháp phân ph iố



CHƯƠNG 0 M Ở Đ UẦ

 Đ i tố ư ng nghiên c u ứ ợ Xây d ng mô hình toán h c cho ự ọ

bài toán t i ố ưu th c tự ế  Bài toán qui ho ch toán ạ

h cọ Các bư c xây d ng ự ớ

 Phân lo i bài toán quy ạ M t s mô hình th c t ộ ố ự ế

 

ho ch toán h c ọ ạ

Đ1. Đ i tố ư ng nghiên c u

ứ

ợ

1. Bài toán quy ho ch toán h c ọ

n) đ hàm f(X)

ể đ t c c tr khi ạ ự ị

ề ệ

ạ Tìm vectơ X*=(x*1,x* 2,….,x* đi u ki n: tho mãn ả gi(X)≤0

‡ xj 0, X=(xj), j=1,2,3,…

n) đ ể đ t Max f(X) ho c

ạ ặ

C thụ ể: Tìm vectơ X*=(x*1,x*2,…,x* Min f(X) (1) khi tho mãn:



‡ ả gi(X) ≤ 0 (2) đk xj 0, X=(xj), j=1,2,3,… (3)

ọ ạ

ọ ề ề ệ

ả ương án

ậ ọ ương án

£  Bài toán (1), (2), (3) g i là bài toán quy ho ch toán h c ọ  Hàm f(X) g i là hàm m c tiêu ụ ọ  Đi u ki n (2) (3) g i là đi u ki n ràng bu c ộ ệ  Vectơ X=(xj ) tho mãn đk ràng bu c g i là 1 ph ộ ọ ‡ 0} g i là t p ph  T p ậ D= {X=(xj) | gi(x) ≤ 0, xj f(X) " X˛ D  Vectơ X* tho mãn f(X) " X˛ D

f(X*)‡ ả ho c f(X*) ặ ương án t ọ

i bài toán quy ho ch là t g i là ph ọ  Gi ả i ố ưu, f(X*) g i là giá tr t ạ ìm phương án t ị ố ưu. i i ố ưu X* và giá tr ị

i ố ưu f(X*). t

2. Phân lo i bài toán quy ho ch toán h c.

ọ

ạ

đi u ki n ràng bu c ụ ề ệ

ự ạ  D a vào tính ch t c a hàm m c tiêu và ấ ủ ọ ủ ư ng tên g i c a các bài toán ờ ộ đ phân ể ể ệ đư c th hi n ợ

lo i bài toán. Thông th trong đi u ki n bài ra. ệ ề

i, Quy ạ ạ ồ

Ví d ụ : Quy ho ch tuy n tính, Quy ho ch phi tuy n, Quy ho ch l ế ế ạ ương, Quy ho ch nguyên… ho ch toàn ph ạ

ạ

đi u ki n ràng bu c là các hàm tuy n tính ề ế ộ

Khi hàm m c tiêu và các ụ thì bài toán đã cho là bài toán quy ho ch tuy n tính (qhtt). ệ ạ ế

i ộ ị ế ạ ọ ố ớ ố ưu đ i v i t

Trong đó quy ho ch tuy n tính có m t v trí quan tr ng hoá.

ự

ọ

i ố t

Đ 2. Xây d ng mô hình toán h c cho bài toán ưu th c tự ế

1. Các bư c xây d ng mô hình toán h c cho các

ọ

ớ bài toán t

ự i ố ưu th c tự ế

đ nh tính cho v n ị ấ đ ề đ t raặ

b Bư c1ớ : Xây d ng mô hình Bư c2ớ : Xây d ng mô hình toán h c ọ ọ đ kh o sát cho bài toán Bư c3ớ : S d ng công c toán h c ự ự ử ụ ể ả ở ư c 2ớ

(cid:222) ị

b ụ Đưa ra các tính ch t, ấ đ nh lý và thu t toán ậ đư c Bư c 4ớ : Phân tính đánh giá k t qu thu ế ả ớ ợ ở ư c 3 so v i mô hình ớ

th c tự ế

2. Vi t mô hình toán h c m t s mô hình th c t ế ộ ố ự ế ọ

Ví du1: M t xí nghi p s n xu t 2 s n ph m A và B t ấ

ệ ả lãi, l t t l ả ự ữ ừ các nguyên li u ệ ừ ẩ các nguyên li u I, II cho theo ệ ư ng d tr t ợ ế ỷ ệ

Lãi

D trự ữ

ộ I , II . Bi b ng sau: ả

Hãy thi t l p k ho ch s n xu t sao cho có t ng s lãi l n nh t? ế ậ ế ạ ấ ả ấ ố ớ ổ

Gi i:ả

ẩ ả ương ng c a A, B ủ ứ G i xọ 1,x2 là lư ng s n ph m t ợ

Mô hình toán h c:ọ Max (3x1+5x2)

‡ x1 + 3x2 £ đk 2x1 + 3x2 £ x1, x2 0, X=( x1, x2)

m nguyên li u. ả ẩ ấ ệ ả ừ ệ

ộ t:ế

nguyên li u th i ứ ừ ả ẩ ứ

lãi trên 1 l ỷ ệ ị ả đơn v s n ph m th j. ứ ẩ : Bài toán t ng quát ổ M t xí nghi p s n xu t n s n ph m, t Bi  a ij là s n ph m th j, t ệ  b i là lư ng nguyên li u d tr th i ệ ữ ữ ứ ợ  c j là t

t l p k ho ch s n xu t sao cho có t ng s lãi là l n nh t? ế ậ ế ạ ả ấ ấ ố ớ ổ

Hãy thi

i:ả

ả ẩ th j.ứ Gi G i ọ xj là s lố ư ng s n ph m ợ

Cj xj)

Mô hinh toán h c:ọ n Max(f(X) = (cid:229) j=1 n (cid:229) aij xj £ b i , i=1,2,…,m

0 , X=(xj) , j= 1,2,…,n

đk j =1 xj ‡

ộ ạ

ầ ớ 2 kho d n 2 ừ

ợ ế ừ đơn v hàng t ị ư ng hàng c n thi ầ ợ đ a ị đi m tiêu th . ụ ể đ a ị đ n các các kho ế ế ở đi m bán cho t ể

Kho

Đ a ị đi mể

x11 3 x21 2

x12 4 x22 5

Ví d 2ụ : C n chuy n m t lo i hàng t ể t cế ư c phí v n chuy n trên 1 Bi ể ậ đi m bán, l kho và l ư ng hàng ở ể theo b ng sau: ả

ch c phân ph i hàng sao cho phát h t thu ế đ , nhủ ưng có t ng ổ ổ ứ

Hãy t ố cư c phí là nh nh t? ớ ấ ỏ

ij là lư ng hàng chuy n t

j -> i ể ừ ợ

iả : Gi G i xọ Mô hình toán h c:ọ f(X) = Min ( 3x11 + 4x12+ 2x21 + 5x22)

x11 + x12 = 7 x21 + x22 = 13 đk x11 + x21 = 5

x12 + x22 = 15 xij ‡ 0 , X=(xij) , i=1,2, j=1,2

n kho đ n m ế đ a ị đi m bán . ể ạ ậ ể ừ

i kho th j ứ ạ

i • ạ đ a ị đi m bán th i ứ ể

• ể đơn v hàng chuy n kho j ể ị đ a ị

Bài toán t ng quát: ổ C n v n chuy n m t lo i hàng t ầ ộ t: ế Bi aj là lư ng hàng t • ợ bi là lư ng hàng t ợ cij là cư c phí v n chuy n trên 1 ậ ớ đi m bán i ể

ổ ư c phí là nh nh t ? ấ ỏ ớ

=> Hãy phân ph i lố ư ng hàng sao cho t ng c ợ

i:ả

kho j -> i ể ừ ợ

Gi G i xọ ij là lư ng hàng chuy n t Mô hình toán h c :ọ Min ( f(X) = (cid:229)

cij xij ) i,j (cid:229) xij = aj

đk

xij , aj ,bi ≥ 0 , X=(xij), i =1,m j =1,n

(cid:229) xij = bi

CHƯƠNG 1 PHƯƠNG PHÁP ĐƠN HÌNH

 Bài toán qui ho ch tuy n ế ạ Công th c s gia hàm m c tiêu. ứ ố ụ

tính d ng chính t c ắ ạ Tiêu chu n t ẩ ố ưu. i

 Gi i bài toán qhtt 2 bi n ả ế Thu t toán ậ đơn hình.

b ng ph ằ ương pháp hình

Tìm phương án c c biên xu t ự ấ

h cọ

phát trong trư ng h p t ng quát. ợ ổ ờ

 Tính ch t c a bài toán ủ ấ

Câu h i và bài t p áp d ng ụ ỏ ậ

qhtt

thu t toán ậ đơn hình.

 Bài t p áp d ng các tính ụ ậ



ch tấ

Đ1. Bài toán qui ho ch tuy n tính d ng chính t c ắ

ế

ạ

n Min ( f(X) = (cid:229)

cj xj )

1. Bài toán quy ho ch tuy n tính d ng t ng quát ổ ế ạ ạ

aij xj

, = ) bi i=1,2,3…m

n j =1 ( ‡ (cid:229) đk

j =1 xj

0 , X=(xj), j=1,2,…n



‡

ạ ế

‡ 0 Ví d ụ : Cho bài toán quy ho ch tuy n tính. Min ( x1 – x2 + x3 ) 2x1 - x3 ‡ đk x2 + 2x3 £ x1 , x2 , x3

ạ

ế

cj xj )

2. Bài toán quy ho ch tuy n tính d ng chính t c ắ n Min ( f(X) = (cid:229) n j=1 (cid:229)

aij xj = bi , i = 1,2,3…, m

đk j=1 xj

0 , X=(xj) , j = 1,2,3,…,n

‡

Ví d :ụ Max ( x1 – 2x2 + x3)

- x1 + 3x2 = 5 đk x2 - 3x3 = 2 x1 , x2 , x3 ‡

ổ

đưa bài toán qhtt d ng t ng

ổ

ạ

3. Các phép bi n ế đ i tuy n tính ế quát v d ng chính t c ắ

ề ạ

‡ ‡ 0, i = 1,m ẩ bi thi` thêm n ph x ụ n+i aij x j

ề ạ

aij x j - xn+i = bi, i = 1,m

£ ‡ 0, i = 1,m ẩ aij x j bi thi` thêm n ph x ụ n+i

ề ạ

aij x j + xn+i = bi , i = 1,m

n # N u ế (cid:229) j=1 đưa bài toán v d ng: n (cid:229) j=1 n # N u ế (cid:229) - j=1 đưa bài toán v d ng: n (cid:229) j=1

- ‡

i x - # N u t n t ấ ị đ t: ặ

- xk

+, xk - vào hàm m c tiêu và

ế ồ ạ k chưa xác đ nh rõ d u thì - , xk 0

- xk

ụ đi u ki n ràng ệ ề xk = xk Thay xk = xk

bu cộ

ề ạ ắ

Ví du 1: Đưa v bài toán QHTT d ng chính t c: Min (x1 – 2x2 + x3 )

‡ 2

‡ 0 2x1 - x3 x2 + x3 = 4 x1 , x2 , x3

‡ Gi 0, đưa bài toán v d ng chính t c: ề ạ ắ i:ả Thêm n ph x ụ 4 ẩ

Min ( x1 - 2x2 + x3)

‡ 0 2x1 - x3 - x4 = 2 đk x2 + x3 = 4 x1 , x2 , x3 , x4

ạ

Ví du 2: đưa v bài toán QHTT d ng chính t c ắ ề Min ( x1 + 2x2 - x3)

‡ 1

‡ 0 x1 - 2x2 Đk x2 + 2 x3 = 2 3 -x1 + x3 x1 , x2 , x3

Gi i:ả Thêm n ph x ẩ 0, đưa bài toán v d ng chính t c: ề ạ ắ ụ 4 , x5 ‡

Min ( x1 + 2x2 - x3)

‡ 0 x1 - 2x2 - x4 = 1 Đk x2 + 2 x3 = 2 -x1 + x3 + x5 = 3 x1 , x2 , x3 , x4 , x5

ẩ ụ đích đưa đi u ki n b t ệ ấ đ ng ẳ ề

n+i = 0

th c v Chú ý: n ph nh m m c ẳ ụ ằ ứ ứ ề đ ng th c và có h s hàm m c tiêu c ệ ố ụ

Ví d 3ụ : đưa bài toán v d ng chính t c: ắ

ề ạ Min ( x1 - x2 - x3)

£ 2

‡

‡ 0 2x1 - x3 Đk x2 + 2 x3 = 3 1 x1 - 2x3 x1 , x3

- ‡ 0

Gi 0, ẩ i:ả - Thêm n ph x

2 = x2

- , x2

+ x2

đ t xặ

+ + x2

ụ 4 ,, x5 ‡ + - x2 ề ạ Min ( x1 - x2 đưa bài toán v d ng chính t c: ắ - x3)

-, x3,, x4, x5

+ , x2

‡ 0 2x1 - x3 + x4 = 2 + 2 x3 = 3 + - x2 Đk x2 x1 - 2x3 - x5 = 1 x1 , x2

t bài toán quy ho ch tuy n tính d ng chính t c trong ế ạ ạ ắ

Ví d 4ụ : Vi ờ ế ợ ổ trư ng h p t ng quát. Cho ví d minh ho . ạ ụ

ổ đưa bài toán v ề

t c các phép bi n ụ ắ ể đ i ổ

Ví d 5ụ : Nêu các phép toán bi n ế đ i tuy n tính ế d ng chính t c. Cho 1 ví d minh ho t ạ ấ ả ạ trên.

4. Các d ng vi ạ ế t bài toán QHTT d ng chính t c ắ ạ

D ng 1ạ : n

Min ( f(X) = (cid:229) cj xj )

j=1

n j=1 (cid:229) aij xj = bi , i = 1,2,3…m

Đk

‡ xj 0 , X=(xj), j = 1,2,3,…n

: D ng ma tr n ậ ạ

 D ng 2ạ A = ( aij ) m x n

]

b1 x1 b = b2 X = x2 C = [c1 … cn : :

bm xn

ậ

V y: Min (f(X) = C X) đk AX = b X ‡ 0

ạ

 D ng 3ạ : D ng Vect ơ: C = (c1 … cn) X = (x1 … xn) b = (b1 … bm) Aj = (a1j , a2j , … , amj)

=> Min (f(X) = )

đk x1A1 + x2A2 + … + xnAn = b X ‡ 0, X=(xj ), j =1,n

i bài to n QHTT 2 bi n b ng ph

ế

ằ

ương

Đ2 Gi ỏ ph p h nh h c ọ

ả ỏ ỡ

i bài toán QHTT b ng ph

ả

ằ

ương pháp hình h cọ

Ví d 1ụ : Gi Max ( 3x + 5y )

8 4 3

2x + y £ Đk y £ x £ x , y ‡

Gi

i:ả

x = 3

(3,5)

(2,4)

y = 4

3x + 5y =15

=> X* = (2,4) , f(X*) = 3*2 + 5*4 =26

Bài toán t ng quát: ổ i bài toán Gi

ả

ương pháp hình h c: ọ

Đk a1i x + a2i y £ x, y ‡

ự

1i x + a2i y = bi

ị

Bư c1ớ : D ng các ờ Bư c 2ớ : Xác đ nh mi n ph ề Bư c 3ớ : D ng ự đư ng ờ

đư ng th ng a ẳ ương án ứ

ị

đ nh m c ax + by = f o

ờ i

fo = BSCNN (a,b) ế đư ng m c ax + by = f ứ ờ ế

ề

n(a,b) đ tìm Max, t nh ti n theo chi u ng ị

Bư c 4ớ : T nh ti n ị ể

o theo đư ng pháp tuy n ế ợ ạ đ tìm Min ể

ư c l

QHTT b ng ph ằ Max (ax + by)

i bài toán b ng ph

ả

ằ

ương pháp hình h cọ

Ví d 2ụ : Gi Max (x + 5y)

12 3 3

2x + 3y £ Đk y £ x £ x , y ‡ 0

x = 3

(1,5)

2x+3y=12

y=3

x+5y=5

ả X* = (3/2 , 3) f(X*) = 3/2 + 5*3 = 33/2

K t qu : ế

Ví d 3ụ : Gi

ả

ương pháp hình h cọ

i bài toán b ng ph ằ Max (-3x1 + x2 )

8 6

-2x1 + x2 £ Đk x1 - 2 x2 £ x1, x2,

‡

x2 (0,8)

(-3,1)

2 = 6

1 -

=8 + x2 -2x1

ả X* = (0,8), f(X*) = -3*0 + 8 = 8

=-3 +x2 -3x1 K t qu : ế

i bài toán b ng ph ả ằ ương pháp hình h cọ

Ví d 4ụ : Gi

2 2 5

a) Max (-x1 + x2 ) b) Min (-x1 + x2 )

-2x1 + x2 £ Đk x1 - 2 x2 £ x1 + x2 £ x1, x2,

‡

ế

ả a) X1* = (1,4) => Max (-x1 + x2 ) = 3 K t qu : b) X2* = (4,1) => Min (-x1 + x2 ) = -3

Ví d 5ụ : Max (-x1 + x2 )

2 8

-2x1 + x2 £ Đk -x1 + 2 x2 £ x1, x2,

ả X1* = (4/3, 14/3) => Max (-x1 + x2 ) = 10/3

K t qu : ế

‡

Đ 3 Tính ch t c a bài toán QHTT

ấ ủ

i tích l

i:

ệ

ề ả

ồ

ộ ố i:

1.M t s khái ni m v gi  T h p l ổ ợ ồ Cho x1,, x2,…, xn ˛

X = l

1x1 + l

2x2 + … + l

nxn ,, 0 £

j = 1

£ l 1 (cid:229) l

i. j=1 h p l ổ ợ ồ ễ ư i d ng t ớ ạ

l £ 1

đi m trong t p l i thì nó ậ ồ ế ậ ồ

đư c g i là bi u di n d ể ợ ọ  T p h p l i: ậ ợ ồ ậ ồ  " x,y ˛ i L là t p l T p L đư c g i là t p l ợ ọ ậ ch a ứ đo n th ng n i gi a 2 ố ẳ ạ L =>l x + (1- l )y ˛ L, 0 £ i n u vi c ch a 2 ể ứ ệ đi m ể đó ữ

ể ể ễ ư i ớ

ể

i c a các Là đi m không th bi u di n d đi m nào trong t p ậ đó. 1,, x2,…, xn ˛ Rn. T p h p t ợ ấ ậ đa ọ đi m ể đã cho g i là

 Đi m c c biên (Đ nh): ể ự ể ỉ d ng t h p l i th c s c a 2 ạ ổ ợ ồ ự ự ủ  Đa di n l ệ ồ : Cho các đi m x i ể c các đi m X là t h p l ổ ợ ồ ủ ể ả i. di n l ệ ồ

ọ ệ

i: ể ệ ồ

j =1 , 0£

j £

l l l 1.

{ x1,, x2,…, xn} g i là h sinh. ễ đa di n l Bi u di n n n jxj , (cid:229) X ˛ D: X = (cid:229) " j=1 j=1

2. Tính ch t c a bài toán QHTT.

ấ ủ

Xét bài toán QHTT: Min( f(X) = C X )

đk AX = b X ‡ 0

i. Tính ch t 1ấ : T p ph ậ ương án c a bài toán QHTT là t p l ậ ồ ủ

Đ nh nghĩa : Đi m c c biên c a t p ph ị ủ ậ ự ương án bài toán QHTT g i là ọ

phương án c c biên. ể ự

£ ọ ố ự ị ặ ế $ Phương án X=(xj) g i là b ch n n u s th c q sao cho x j

" j=1..n.

T p ph ậ ị ặ ế " ương án đư c g i là b ch n n u ợ ọ phương án đi u b ch n. ề ị ặ

Ví d 1ụ : Xét bài toán QHTT Min (x1 - x2 - x3) 3x1 - 7x2 + 3x3 + x4 = 2 (1) -x1 + 2x2 – x3 = 1 (2) 2x1+ x2 + 2x3 = 6 (3)

‡ 0 x1 , x2 , x3 , x4

Ch ng minh r ng: T p ph ằ ứ ậ ương án b ch n. ị ặ

i:ả

ớ ế ớ ế

£ 12 " j=1..4 => đpcm

ớ

£ ế ớ ế 39, "

Gi  Cách 1: Nhân 4 v i pt (2), c ng v v i v ta có: ộ x1 + 2x2 + x3 + x4 = 12, xj  Cách 2: Nhân 6 v i pt (3) , c ng v v i v ta có: ộ 14x1 + x2 + 14x3 + x4 = 39, xj j=1..4. => đpcm

ế ậ

ủ

i thì có ít nh t 1 ph

Tính ch t 2ấ : N u t p ph ấ

ương án c a bài toán QHTT là ương án c c biên là ph ự

đa ương án

di n l ệ ồ i ố ưu. t

Tính ch t 3ấ : N u bài toán QHTT có ph

ế

ương án t

i ố ưu thì có ít

nh t 1 ph

ấ

ương án c c biên là ph ự

ương án t

i ố ưu

vectơ c t Aộ

ứ

 các Tính ch t 4ấ : Phương án X =(xj) là phương án c c biên ự j >0 là đ c l p tuy n tính. ế ộ ậ ớ

j tương ng v i các x

a) Đi m X = (0,8/5 ,11/5 , 33/5 ) có ph i là ph

0 Ví d 2ụ : Xét bài toán QHTT Min ( x1 - x2 - x3 ) 3x1 - 7x2 + 3x3 + x4 = 2 đk -x1 + 2x2 - x3 = 1 2x1+ x2 + 2x3 = 6 x1 , x2 , x3 , x4 ‡

ể ả ương án c c ự

}. biên không? Ti`m pacb tương ng v i c ứ ớ ơ s ở {A1 A2 A4

iả :

ương án không? ả ể

ương án X ta có : x2,, x3 , x4 > 0 nên

}

Gi  Ki m tra xem X có ph i là ph Ta có: 3*0 - 7*8/5 + 3*11/5 + 33/5 = 2 - 0 + 2*8/5 – 11/5 = 1 2*0 + 8/5 + 2*11/5 = 6 => X là phương án  T i phạ => Xét cơ s ở {A2 A3 A4

-7 3 1

} đ c l p tuy n tính => X là pacb.

ộ ậ

ế

=> {A2 A3 A4

Ta có: | A2 A3 A4 | = 2 -1 0 = 5 „ 1 2 0

} là đ c l p tuy n tính?

b) Ki m tra ể

ộ ậ

ế

{A1 A2 A4

3 -7 1

Ta có: | A1 A2 A4 | = -1 2 0 = -5 „ 2 1 0

ộ ậ

}đ c l p tuy n tính => x ế

ề

1, x2, x4 > 0 và x3 =0 ệ ương

ộ

tri`nh:

=>{A1 A2 A4 Thay x3 =0 vào đi u ki n ràng bu c ta có h ph ệ 3x1 - 7x2 + x4 = 2 x1 = 11/5 -x1 + 2x2 = 1 => x2 = 8/5 2x1+ x2 = 6 x4 = 33/5

Pacb X= (11/5 , 8/5 , 0 , 33/5).

j) là phương án c c biên? ương án.

: Ki m tra X =(x ể ổ ự

j>0 thì xét {Aj } có đ c l p tuy n tính hay

T ng quát Bư c 1ớ : Ki m tra X là ph ể Bư c 2ớ : T i X có x ạ ộ ậ ế

không?

Bư c 3ớ : K t lu n. ế ậ

i ố ạ đ dộ ương c a pacb có t ủ ố đa không quá s phố ương

H qu : trình đ c l p tuy n tính. ệ ả S to ế ộ ậ

S phố ương án c c biên c a bài toán QHTT là h u h n. ữ ạ ự ủ

đ m to ủ ạ đ dộ ương g i là ph ọ ương án c c biên ự

đư c g i là không suy bi n n u t t c ế ế ấ ả ợ ọ

Khái ni m:ệ Phương án c c biên có ự không suy bi n.ế Bài toán quy ho ch tuy n tính ạ ế các phương án c c biên ự đ u không suy bi n. ề ế

‡ Ví d 1ụ : Xét bài toán QHTT: x1 + x2 + x3 = 4 Đk x1 – x2 =0 0 x1 , x2 , x3

ạ đ dộ ương mà có 2 pt.

X1=(1,1,2) là phương án. X2=(0,0,4) là pacb suy bi n vì có 1 to ế X3=(2,2,0) là pacb không suy bi n vì có 2 to ế ạ đ dộ ương và cũng có

ệ

2 phương trình đi u ki n. X4=(3,3,-2) không ph i là ph ề ả ương án.

ế ương án t i ố ưu khác nhau

Tính ch t 5ấ : N u bài toán QHTT có 2 ph i ố ưu. thì bài toán có vô s phố ương án t

Gi ứ ả ử 1,X2 là 2 patư và X1 „ s X X2.

l £ 1. )X2, 0 £

i ố ưu nên f(X1) = Min f(X),

Ch ng minh: Ta xét Y= l X1 + (1 - l Vì X1, X2 là phương án t f(X2) = Min f(X)=> f(X1) = f(X2). => f(Y)= l = l f(X1) + (1 - l f(X 2 + (1 - l ) f(X2) ) f(X2)

= f(X2) = Min f(X) => Y là patư => đcpcm

Tính ch t 6ấ : Đi u ki n c n và ề ể ương án

đ ủ đ bài toán QHTT có ph . ˘ ệ ầ i ố ưu là hàm m c tiêu b ch n và t p ph t ương án „ ị ặ ụ ậ

Ví d 2ụ : Xét bài toán QHTT Max (2x1 + 3x2 )

4x1 + 2x2 + x3 = 5 đk x1 + 3x2 = 1 xj ‡ 0, j =1,2,3

a) Tìm t t c các ph ự b) CMR bài toán có phương án t c) Tìm phương án t

ấ ả

ương án c c biên. i ố ưu. ị ố ưu. i i ố ưu và giá tr t

} a)

1 x2 >0 và x3= 0.

} là đ c l p tuy n tính => x ộ ậ ế

+ Xét {A1 A2 Ta có: 4 2 | A1 A2 | = = 10 „ 1 3 Nên {A1 A2 Thay vào đi u ki n ràng bu c ta có: ệ ề ộ

4x1 + 2x2 = 5 x1 + 3x2 = 1

Suy ra: x1 = 13/10 và x2 = -1/10 <0 (Lo i)ạ

1 x3 >0 và x2= 0.

} là đ c l p tuy n tính=> x ộ ậ ế

} + Xét {A1 A3 Ta có: 4 1 | A1 A3 | = = -1 „ 1 0 Nên {A1 A3 Thay vào đi u ki n ràng bu c ta có: ệ ề ộ

4x1 + x3 = 5 x1 = 1

Suy ra: x1 = 1 và x3 = 1 => Pacb X=(1 , 0 , 1)

2 x3 >0 và x1= 0.

} là đ c l p tuy n tính=>x ộ ậ ế

} + Xét {A2 A3 Ta có: 2 1 | A2 A3 | = = -3 „ 3 0 Nên {A2 A3 Thay vào đi u ki n ràng bu c ta có: ệ ề ộ

2x2 + x3 = 5 3x2 = 1

Suy ra: x2 = 1/3 và x3 = 13/3 => Pacb X=(0 , 1/3 , 13/3)

ấ ả

Suy ra: đã cho là: T t c các pacb c a bài toán ủ }. X1 = (1 , 0 , 1) là pacb v i cớ ơ s ở {A1 A3 }. X2 = (0 , 1/3 , 13/3) là pacb v i cớ ơ s ở {A2 A3

b) T câu a) ta có X1=(1 , 0 , 1) là pacb => T p ph ừ ậ ương án là

„ .

˘ M t khác: ặ T phừ ương trình x1 + 3x2 = 1 => x1 = 1 - 3x2.Thay vào

hàm m c tiêu ta có: ụ

£ 2 f(X) = 2x1 + 3x2 = 2(1 - 3x2) + 3x2 = 2 - 3x2

do x2 ‡

0. Nên theo t/c 6 => đpcm.

ụ

c) Thay các pacb vào hàm m c tiêu , ta có: f(X1) = 2*0 + 3*1/3 =1 f(X2) = 2*1+3*0 =2 Vì f(X1) < f(X2) => f(X*) = f(X2) =2 và X*=(1 , 0 , 1)

Ví d 3ụ : Xét bài toán QHTT

Min ( x2 – x4 - 3x5 )

‡ x1 + 2x2 - x4 + x5 = 1 đk - 4x2 + x3 + 2x4 - x5 = 2 3x2 + x5 + x6 = 5 xj 0 , j = 1, 6

ể

ả ớ ơ s ở { A2 A4 A5 ị ặ

 Đi m (0 , 5/3 ,4 , 7/3 , 0 , 0) có ph i là pacb?  Tìm pacb ng v i c ứ  CMR t p ph ương án b ch n ? ậ  CMR bài toán có phương án t i ố ưu ?

ương án? ể

ậ ương án .

a) # Ki m tra X = (0 , 5/3 ,4 , 7/3 , 0 , 0) là ph 0 + 2*5/3 -7/3 +0 =1 - 4*5/3 + 4 + 2*7/3 -0 =2 3*5/3 +0 +0 =5 V y X là ph 2 , x3 , x4 > 0 # T i X, ta có : x ạ } => xét cơ s ở { A2 A3 A4 2 0 -1 | A2 A3 A4 | = -4 1 2 = 3 „ 3 0 0

(cid:222) } là đ c l p tuy n tính => X là pacb. ộ ậ ế { A2 A3 A4

}

2 , x4 , x5 > 0 và

(cid:222) } là đ c l p tuy n tính => x b) Xét { A2 A4 A5 2 -1 1 | A2 A4 A5 | = -4 2 -1 = -3 „ 3 0 1 ộ ậ ế

{ A2 A4 A5 x1= x3 = x6 = 0

ộ ề ệ ệ ương trình :

Thay vào đi u ki n ràng bu c ta có h ph 2x2 - x4 + x5 = 1 -4x2 + 2 x4 - x5 = 2 3x2 + x5 = 5

x2= 1/3 => x4 = 11/3 x5 = 4

Suy ra pacb ng v i c } là: ứ ớ ơ s ở { A2 A4 A5

X = (0 , 1/3 , 0 , 11/3 , 4 , 0).

c) C ng v v i v c a 3 ph ế ớ ế ủ ương trình trong đi u ki n ràng ề ệ

ộ bu c, ta có: ộ

£ j = 1..6 8 "

x1 + x2 + x3 + x4 + x5 + x6 = 8 => xj => đpcm

£ £ 8 ừ d) T câu c) ta có x 2

và t câu a) => T p ph ừ ậ 8 => f(X) = x2 - x4 - 3x5 ˘ ương án „ => đpcm

3. Công th c s gia hàm m c tiêu

ứ ố

ụ

ở ương pháp đơn hình:

ự ậ ủ ậ

i ố ưu thì có ít nh t 1 ấ i ố ưu.

3.1 Cơ s lý lu n c a ph D a vào 2 nh n xét sau: ương án t # N u bài toán QHTT có ph ế ương án t phương án c c biên là ph ự # S phố ương án c c biên c a bài toán QHTT là h u h n. ủ ữ ạ ự

đo n:ạ ậ ự

đi u ki n t i ự ệ ố ưu đ i v i ph ự

ế đi u ki n t ấ ố ớ ế đúng đó là phương án t ương án c c biên m i và ki m tra ự ể ớ ương án c c biên i ố ưu, N u sai thì xây ệ ố ưu i ề

(cid:222) Xây d ng thu t toán đơn hình g m 2 giai ồ Gđ1: Tìm phương án c c biên xu t phát. Gđ2: Ki m tra ề ể xu t phát. N u ấ d ng ph ự đ i v i ph ố ớ ương án này.

 Xét bài toán QHTT Min (f(X) = CX)

đk AX = b X ‡ 0

Trong đó ma tr n A ch a ma tr n ậ đơn v ị ứ ậ

1 0 E = 0 1 m x n

ề

‡

0 j =1,2,3,4 ấ

Ví d 1ụ : Xét bài toán QHTT v i ớ đi u ki n ệ x1 - 2x4 = 2 x2 + x4 = 4 x3 - x4 = 1 xj Tìm pacb xu t phát. Gi i:ả

1 A2 A3 ) => T p ch s ỉ ố

ậ ị

Tacó : Ma tr n ậ đơn v E = (A J= {1,2,3}=>x1 = b1= 2, x2 = b2= 4 , x3 = b3= 1, x1 =0 => pacb xu t phát (2 , 4 , 1 , 0). ấ

ổ ấ

j ) , T p ch s c

ỉ ố ơ s Jở ậ T ng quát - Tìm ma tr n ậ đơn v E = (A : Tìm pacb xu t phát: ị

j )

- Pacb xu t phát X = (x ấ

˛ J ế

ˇ J ế bi N u j xj = 0 N u j

ự ạ

Ví d 2ụ : Hãy t ậ cho 1 ví d v bài toán QHTT d ng chính t c, trong ví d ụ ế ắ t pacb xu t phát t ừ ấ ậ đơn v . Vi ứ ị

ụ ề đó ma tr n A ch a ma tr n đó.

3.2 Công th c s gia hàm m c tiêu: ứ ố ụ

j ) là pacb

Gi s X = (x ả ử

k˛

f(X) = (cid:229) Ck xk

f( Xj ) = (cid:229) k˛

Ck xkj

k˛

=> Bi u th c trên g i là công th c s gia hàm m c tiêu. ọ

Đ t ặ D j = f(Xj) - Cj = (cid:229) Ck xkj - Cj

ứ ố ứ ụ ể

3.3 B ng ả đơn hình

(j ˛ J)

C1 Cn xj Cj …..

B ngả Cơ sở

A1 An

D D f(X)

‡

j t

0 , j=1,4 i pacb xu t phát. ấ ạ

Ví d 1ụ : Cho bài toán QHTT Min (x1 - 2x2 - 3x3 ) 3x1 +x3 = 6 đk -2x1 +x2 = 1 x1 + x4 = 3 xj Tính D Gi iả :

3 A2 A4), J= {3,2,4}.

Ta có ma tr n ậ đơn v E = (A ị

(cid:222)

(cid:222) ấ

x3 = 6 , x2 = 1 , x4 = 3, x1 = 0 Pacb xu t phát X = (0 , 1 , 6 , 3) Ta có : C1 = 1, C2 = -2, C3 = -3 , C4 = 0

L p b ng

ậ ả đơn hình:

B ngả Cơ sở xj Cj

1 A1 -2 A2 -3 A3 0 A4

6 1 3 -3 -2 0 3 -2 1 0 1 0 1 0 0 0 0 1 A3 A2 A4

-6 0 0 0

‡ 0 , j=1,4

j t

Ví d 2ụ : Cho bài toán QHTT Min (-2x1 + x2 - x3 ) - 3x2 + x3 = 1 Đk x1 + 2x2 = 7 x2 + x4 = 2 xj Tính D i pacb xu t phát. ấ ạ

iả :

3 A1 A4) , J= {3,1,4}

Gi Ta có ma tr n ậ đơn v E = (A ị

(cid:222)

(cid:222) ấ

x3 = 1 , x1 = 7 , x4 = 2, x2 = 0 Pacb xu t phát X = (7 , 0 , 1 , 2). Ta có : C1 = -2, C2 = 1, C3 = -1 , C4 = 0

L p b ng

Cơ sở B ngả

ậ ả đơn hình: xj

-2 A1 1 A2 -1 A3 0 A4

1 7 2 -1 -2 0 0 1 0 -3 2 1 1 0 0 0 0 1 A3 A1 A4

: (Tiêu chu n t

0 -2 0 0

i pacb X = (x

Đ nh lý1 ị N u t ế ạ

0 thi` X là phương án t

i ố ưu

ẩ ố ưu) i j) có m i ọ D

‡ 0 , j=1,4 Ví d 3ụ : Cho bài toán QHTT Min (x1 + 2x2 - x4 ) x1 + 2 x2 = 5 Đk x2 + x4 = 2 - x2 + x3 = 1 xj

ả ư không?

1 A4 A3) , J= {1,4,3}

Ki m tra pacb xu t phát có ph i là pat ấ ể Gi iả : Ta có ma tr n ậ đơn v E = (A ị

(cid:222)

(cid:222) ấ

x1 = 5 , x3 = 1 , x4 = 2, x2 = 0 Pacb xu t phát X = (5 , 0 , 1 , 2). Ta có : C1 = 1, C2 = 2, C3 = 0 , C4 = -1

L p b ng

ả

ậ

đơn hình:

B ngả Cơ sở xj Cj

1 A1 2 A2 0 A3 -1 A4

5 2 1 1 -1 0 1 0 0 2 1 -1 0 0 1 0 1 0 A1 A4 A3

0 -1 0 0

0 j = 1,4

ạ

ấ

(cid:222) T i pacb xu t phát X = (5,0,1,2) thì (cid:222) Đây là phương án t

i ố ưu

D £

ương pháp đơn hình ằ

‡ Ví d 3ụ : Cho bài toán QHTT b ng ph Min (x1 + x2 + x3 ) - x1 + x2 + 2 x3 = 2 đk => x1 - x3 + x5 = 3 2x1 + x3 + x4 = 4 0 , j=1,5 xj

i:ả

2 A5 A4) , J= {2,5,4}

Gi Ta có ma tr n ậ đơn v E = (A ị

(cid:222)

(cid:222) x2 = 2 , x5 = 3 , x4 = 4, x1= x3 = 0 Pacb xu t phát X = (0 , 2 , 0 , 4 , 3) ấ

Ta có : C1 = 1, C2 = 1, C3 = 1 , C4 = 1

L p b ng

ả

ậ

đơn hình

B ngả

xj Cj

C ơ sỏ

2 3 4 I 1 0 0 A2 A5 A4

1 4 3 1 0 0 1 A1 -1 1 2 -2 -1/2 1/2 5/2 1 A2 1 0 0 0 1/2 1/2 -1/2 1 A3 2 -1 1 1 1 0 0 0 A4 0 0 1 0 0 0 1 0 A5 0 1 0 0 0 1 0 A3 A5 A4

-3/2 -1/2 0 0 0

(cid:222) T i b ng II ạ ả

" D £ 0 , nên X* = (0,0,1,3,4)

(cid:222) f(X*) = 1

4. Thu t toán ậ

đơn hình

j ) , J , Cj

ấ

" £ D 0 không ? ể

$ £ 0 ? D ư c 2ớ p > 0 , " xip

j => Ak vào cơ sở

ư c 3ớ

Bư c 0ớ : Tìm pacb xu t phát X = (x Bư c 1ớ : Tính D Ki m tra N u ế đúng => X là patư N u sai sang B ế Bư c 2ớ : Ki m tra ể N u ế đúng => Bài toán không có patư. N u sai sang B ế k = Max D Bư c 3ớ : Ch n ọ D

x

quay

ầ ử

=

Lk là ph n t

Min

x

x x

=> AL cơ s , xở

’ ) theo quy t c.ắ

Bư c 4ớ : Xây d ng pacb X ự

’ =(xj ớ

X : = X’ (Tr l i B ở ạ ư c 1)

ả i bài toán tìm Min và ch ỉ

Chú ý: Phương pháp đơn hình gi ợ xét các đ i lạ ư ng d ương

B t ắ đ uầ

Thu t toán: ậ

Gán A,b,C,X

(

n ),1

Tính

n ),1

£ D " X0là patư

x ik

£ $

Bài toán không có patư

max

">D :0 - A, k

=D k

raA l

(cid:221) D

min

, xd X’

xik

x i x ik

x l x lk

X:=X’

‡ 0 , j=1,6 Ví d 5ụ : Cho bài toán QHTT Min (x1 - x2 + x3 + x4+ x5 – x6) x1 + x4 + 6 x6 = 9 Đk 3x1 + x2 - 4 x3 + 2x6 = 2 x1 +2x3 + x5 + 2x6 = 6 xj

a) b) ứ ể

j t

c) S d ng ph S d ng ph ph i là pat S d ng ph i 2 pacb. ử ụ ử ụ ả ử ụ ương pháp đơn hình tìm 2 pacb. ương pháp đơn hình ki m tra pacb th 2 có ư không? ương pháp đơn hình tính D ạ

d) Gi i bài toán b ng ph ả ằ ương pháp đơn hình.

ự

ấ

ư ng ờ

5. Tìm phương án c c biên xu t phát trong tr h p t ng quát

ợ ổ

Ví d 1:ụ Cho bài toán QHTT

Min ( x1 - 2x2 + x3 )

‡ 2 2x1 - x3

£ 5 Đk - x1 + 2x2 + x3

‡ 0 , j=1,3 xj

Đưa bài toán v d ng chính t c. ề ạ ắ

‡ 0 , đưa bài toán v d ng chu n ề ạ ẩ ẩ iả : Thêm 2 n ph x ụ 4 x5

Gi t cắ Min ( x1 - 2x2 + x3 )

2x1 - x3 - x4 = 2

Đk - x1 + 2x2 + x3 + x5 = 5

•Tìm pacb xu t phát c a bài toán trên.

‡ 0 , j =1,5 xj

ủ ấ

‡ 0, v i T>0 tuỳ ý ớ đưa bài toán v d ng ề ạ t o x ả ạ 6

Thêm n gi ẩ t o: gi ả ạ

Min ( x1 - 2x2 + x3 + T x6 )

2x1 - x3 - x4 + x6 = 2

Đk - x1 + 2x2 + x3 + x5 = 5

‡ 0 , j=1,6 xj

6 A5) , J = {6,5}

(cid:222) x6 = 2 , x5 = 5 , x1 = x2 = x3 = x4 = 0

(cid:222) Pacb xu t phát là: X = (0 , 0 , 0 , 0 , 5 , 2).

Ta có : Ma tr n ậ đơn v E = (A ị

ấ

Ví d 2ụ : Cho bài toán QHTT

Min ( - x1+ 2x2 - x3 )

x1 - 2 x2 + x3 = 1

Đk - x1 + x2 + 2 x3 = 4

‡ 0 , j =1,3 xj

Vi t pacb xu t phát. ế ấ

‡ 0, v i T > 0 tuỳ ý, đưa bài ẩ ớ ả ạ 4 x5 t o x

iả : Thêm 2 n gi giả t o:ạ

ề ạ

Gi toán v d ng Min ( - x1+ 2x2 - x3 + Tx4 + Tx5 )

x1 - 2 x2 + x3 + x4 = 1

Đk - x1 + x2 + 2 x3 + x5 = 4

‡ 0 , j =1,5 xj

4 A5) , J = {4,5}

(cid:222) x4 = 1 , x5 = 4 , x1 = x2 = x3 = 0

(cid:222) Pacb xu t phát là: X = (0 , 0 , 0 , 1 , 4).

Ta có : Ma tr n ậ đơn v E = (A ị

ấ

ổ

: Cho bài toán QHTT

T ng quát n Min ( f(X) = (cid:229)

cj xj )

j =1

n j =1 (cid:229) aij xj = bi , i = 1,2,3…, m

Đk

‡ xj 0 , X=(xj) , j = 1,2,3,…,n

ij) m x n chưa ch a ma tr n 0, v i T >0 tuỳ ý ,

ứ ị

ẩ ậ đơn v E. đưa bài toán ớ Trong đó, ma tr n A = (a n+i ‡

ậ t o x ả ạ t o. ả ạ Thêm n gi v d ng gi ề ạ

n n Min ( f(X) = (cid:229) xn+i)

cj xj + T (cid:229) n j=1 j=1 (cid:229) aij xj + xn+i = bi , i = 1,m

‡ Đk j=1 xj 0 , X=(xj) , j = 1,n+m

(cid:222) Nh n xét ậ : n gi ẩ ả ạ t o nh m m c ằ ạ ậ đơn

v v i h s c a hàm m c tiêu c ị ớ ệ ố ủ ụ ụ đích t o ra ma tr n n+i =T.

Ví d 3ụ : Cho bài toán QHTT

Min (2x1 - x2 - 3x3 )

‡ 0 , j =1,4 2x1 + x2 - x3 = 3 Đk x1 - x2 + 2 x3 + x4 = 7 x1 - x2 - x3 = 1 xj

t pacb xu t phát. ế ấ

iả :

‡ 0 v i T >0 tuỳ ý. Ta ớ đưa bài toán

Gi Thêm 2 n gi ẩ v d ng gi ề ạ t o x ả ạ 5 x6 t o ả ạ

Min (2x1 - x2 - 3x3 + Tx5 + T x6 )

‡ 0 , j =1,6 2x1 + x2 - x3 + x5 = 3 Đk x1 - x2 + 2 x3 + x4 = 7 x1 - x2 - x3 + x6 = 1 xj

ị ậ

(cid:222) Ma tr n ậ đơn v E = ( A 5 A4 A6 ) => T p ch s ỉ ố J= {5,4,6}=> x5 = 3, x4= 7 , x6 = 1, x1 = x2 = x3 =0 => pacb xu t phát (0, 0 ,0 , 7 , 3 , 1). ấ

Ví d 4ụ : Cho bài toán QHTT

Min (2x1 + x2 - 3 x4 )

‡ 0 , j =1,4 - x1 - x3 + x4 = 1 Đk 2x1 + x2 + x3 - x4 = 6 x1 - x3 + x4 = 4 xj

j t

Tính D ạ i pacb xu t phát ? ấ

i:ả

‡ 0 v i T >0 tuỳ ý . Ta ớ đưa bài

ả ạ 5 x6 t o x t o Gi Thêm 2 n gi ẩ toán v d ng gi ề ạ

ả ạ Min (2x1 + x2 - 3 x4 + T x5 + T x6)

‡ 0 , j =1,6 - x1 - x3 + x4 + x5 = 1 Đk 2x1 + x2 + x3 - x4 = 6 x1 - x3 + x4 + x6 = 4 xj

5 A2 A6 ) => T p ch s Ma tr n ậ đơn v E = ( A ỉ ố J= {5,2,6}=> x5 = 1, x2= 6 , x6 = 4, x1 = x3 = x4 =0 => pacb xu t phát (0, 6 ,0 , 0 , 1 , 4 )

ị ậ

ấ

Ta có b ng ả

đơn hình như sau :

2 1 0 -3 T T

xj Cj

B nả g Cơ sở A6 A1 A2 A3 A4 A5

-2T+1

2T+2

1 6 4 T 1 T -1 2 1 0 1 0 -1 1 -1 1 -1 1 1 0 0 0 0 1 A5 A2 A6

0 0 0 0

j > 0 , " j < 0 , " j

Nh n xét ậ D  N u ế a  N u ế a Max D D a

ờ

ợ đã bi

t trế ư c ớ đây.

: j + b j = Ta j >0 => D j < 0 => D j  Max a j>0 a j >0 j = 0 => Đưa v trề ư ng h p

VÝ d ô 4: Gi¶i bµi to¸n b»ng ph¬ng ph¸p ®¬n h×nh

Min (2x1 - 3x2 )

‡ 0 , j =1,4 2x1 + x2 - x3 = 4 §k x1 + x3 + x4 = 2 2x1 + 2x3 = 1 xj

iả :

‡ 0 v i T >0 tuỳ ý . Ta ớ đưa bài toán v ề

Gi Thêm 2 n gi ẩ d ng gi ạ

t o x ả ạ 5 t o ả ạ Min (2x1 - 3x2 + T x5 )

‡ 2x1 + x2 - x3 = 1 Đk x1 + + x3 + x4 = 2 2x1 +2x3 + x5 = 1 0 , j =1,5 xj

2 A4 A5 ) => T p ch s ỉ ố

ị ậ

Ma tr n ậ đơn v E = ( A J= {2,4,5}=> x2 = 4, x4= 2 , x5 = 1, x1 = x3 =0 => pacb xu t phát (0, 4 ,0 , 2 , 1) ấ

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

B ngả

Cơ sở

I -3 0 T 4 2 1 A2 A4 A5

-3 0 0 9/2 3/2 1/2 2 A1 2 1 2 2T-8 3 0 1 -3 A2 1 0 0 0 1 0 0 0 A3 -1 1 2 2T+3 0 0 1 0 A4 0 1 0 0 0 1 0 T A5 0 0 1 0 1/2 -1/2 1/2 A2 A4 A3

-3/2-T

-27/2

-11 0 0 0

X*=(0,9/2,1/2.3/2,0) , f(X*)=-27/2

ị

Đ nh lý 4 1) N u X* là pat

ớ

: V i T >0 tuỳ ý ta có: ư c a bài toán ả ạ

đã cho thì X* = (X* , 0) là ủ ế

patư c a bài toán d ng gi ủ ạ

n+i >0 thì

2) N u X* là pat t o có x t o. ạ ế ư c a bài toán d ng gi ủ ả ạ

bài toán đã cho không có patư.

Câu h i ôn t p: ỏ ậ

Vi ế t bài toán qhtt d ng t ng quát. Cho ví d minh ho . ạ ụ ổ ạ

t bài toán qhtt d ng chính t c trong tr Vi ế ạ ắ ư ng h p t ng quát. ợ ổ ờ

Cho ví d minh ho . ạ ụ

Nêu các phép bi n ế đ i tuy n tính ổ ế đưa bài toán qhtt t ng quát v ề ổ

d ng chính t c. Cho 1 ví d minh ho các phép bi n ụ ế đ i trên. ổ ắ ạ ạ

i bài toán qhtt 2 bi n b ng ph Nêu các bư c gi ớ ả ế ằ ương pháp hình

h c.ọ

Vi t bài toán qhtt d ng gi t o trong tr ế ạ ả ạ ư ng h p t ng quát. Cho ợ ổ ờ



ví d minh ho . ạ ụ

Nêu cơ s lý lu n c a ph ậ ủ ở ương pháp đơn hình.

Phân bi ệ ẩ t n ph và n gi ụ ẩ ả ạ t o. Cho ví d minh ho . ạ ụ

Cho ví d bài toán qhtt d ng chính t c, trong ụ ạ ắ đó ma tr n A ch ậ ưa

ch a ma tr n t ph ậ đơn v . Vi ứ ị ế ương án c c biên xu t pháp c a ví ự ủ ấ

d này. ụ

đo n xây d ng thu t toán Hãy ch ra các giai ỉ ự ạ ậ đơn hình.



Gi i bài toán b ng ph ả ằ ương pháp đơn hình.

Ố

Ẫ

CHƯƠNG 2 PHƯƠNG PHÁP ĐƠN HÌNH Đ I NG U

 Bài toán qui ho ch tuy n ế ạ Công th c s gia hàm m c tiêu. ứ ố ụ

tính d ng chính t c ắ ạ Tiêu chu n t ẩ ố ưu. i

 Gi i bài toán qhtt 2 bi n ả ế Thu t toán ậ đơn hình.

b ng ph ằ ương pháp hình

Tìm phương án c c biên xu t ự ấ

h cọ

phát trong trư ng h p t ng quát. ợ ổ ờ

 Tính ch t c a bài toán ủ ấ

Bài t p áp d ng thu t toán ụ ậ ậ đơn

qhtt

hình.

 Bài t p áp d ng các tính ụ ậ



ch tấ

Đ1 C p bài toán

ặ

đ i ng u không ẫ

ố

đ i x ng ố ứ

ạ ế

cjxj )

a jị xj = bi , i = 1..m (1)

ề

Xét bài toán quy ho ch tuy n tính: n Min(f(x)= (cid:229) j=1 n (cid:229) j=1 Đi u ki n: ệ xj >= 0, j=1..n

ố

Bài toán đ i ng u c a bài toán trên: ẫ ủ m Min (g(y)= (cid:229) bi yi)

(cid:229) i=1 m Đi u ki n: ề ệ aij yj ≤ cj , j= 1..n (2)

i=1

ạ ế

ệ ề

t bài toán đã cho . đ i x ng c a bài toán ủ ố ứ

ế i:ả

b At = -1 2

ố

ệ ề

Ví d 1ụ : Cho bài toán quy ho ch tuy n tính Min(2x1 – x3) x1 – x2 + x3 = 4 Đi u ki n: -x 1 + 2x2 – x3 = 1 xj ≥ 0, j=1..3 đ i ng u không Vi ẫ ố Gi 1 -1 1 1 -1 A= (cid:222) -1 2 -1 1 -1 đ i x ng: Bài toán đ i ng u không ố ứ ẫ Max (g(Y) = 4y1 + 4y2 ) y1 – y2 ≤ 2 đi u ki n: -y 1 + 2y2 ≤ 0 y1 - y2 ≤ -1

ạ ế

ề ệ Ví d 2:ụ Cho bài toán quy ho ch tuy n tính Min( -2x1 + x2) x1 - x2 = 1 1 + 3x3 = 3 Đi u ki n: -x

t bài toán đ i ng u không ẫ ố

ế i:ả

ề ệ

xj ≥ 0, j= 1..3 đ i x ng. Vi ố ứ Gi Max(g(Y) = y1 + 3y2) y1 - y2 ≤ -2 1 ≤ 1 đi u ki n: -y 3y2 ≤ 0

Nh n xét: ậ

i ư c l ợ ạ

ế ố ẩ ủ ố đi u ki n c a bài toán kia ệ ủ

- N u hàm f(X) tìm Min thì hàm g(Y) tìm Max và ng - S n c a bài toán này là s - Ma tr n c a 2 bài toán là chuy n v c a nhau ề ể ị ủ ậ ủ

V i m i ph Tính ch t 1:ấ ọ ớ ương án X, Y ta có f(X) ≥ g(Y).

ứ

(cid:229) aij yi xj cjxj ≥ (cid:229)

((cid:229)

i=1

= g(Y) => f(X) ≥ g(Y)

Ch ng minh: n n m f (X)= (cid:229) j=1 j=1 i=1 m n = (cid:229) a j ị xj ) yi i=1 j=1 m = (cid:229) bi yi

*, Y*

ủ ả

là phương án c a bài toán Tính ch t 2:ấ N u Xế và bài toán đ i ng u không đ i x ng tho mãn ề ố ứ ẫ ố f(X*) = g(Y*) thì X* , Y* là các phương án t các bài toán tương ng trên.

đã cho đi u ki n ệ i ố ưu c a ủ

ứ

Ch ng minh: Xét X*,Y theo tính ch t 1:ấ f(X*) ≥ g(Y), " Y g(Y*) = f(X*) => g(Y*) ≥ g(Y) " Y

=> Y* là phương án t i ố ưu Xét X*,Y* theo tính ch t 1:ấ f(X) ≥g(Y*)=f(X*) " X => f(X) ≥ f(X*) => X* là phương án t i ố ưu.

N u m t trong 2 bài toán có ph ộ i ố ưu thì

ương án t i ố ưu, đ ng th i Min(f(X))= ờ ồ

Tính ch t 3:ấ ế bài toán kia cũng có phương án t Max(g(Y)).

i ố ưu <=> CX* = BY*

ệ ả H qu : X*, Y* là phương án t

ệ

* ) là t

i ph i ố ưu <=> T n t ồ ạ ương án

* > 0

ả

* = cj n u xế j

* =0 n u ế (cid:229)

ai j y i

* < cj

ặ ai j y i

Tính ch t 4ấ : (Tính l ch bù): Phương án X* = (xj i ố ưu t Y* =(yi* ) tho mãn: m (cid:229) i=1 m ho c: x j i=1

Ch ng minh: ứ

*, Y* là phương án t

Theo tính ch t 2 và 3: X ấ i ố ưu (cid:219)

f(X*) = g(Y*)

* - (cid:229)

= (cid:229)

n m * - (cid:229) bi yi cj xj

* ) yj

* )

= (cid:229)

* ( cj - (cid:229)

( (cid:229) ai j xj

(cid:222) f(X*) - g(Y*) = (cid:229) j=1 i=1 n m n cj xj j=1 i=1 j=1 n m ai j yi xj j=1 i=1

= 0

(cid:219) xj =0

ai j yji

m cj = (cid:229) i=1

Ví d 1ụ : Cho bài toán quy ho ch tuy n tính: ế ạ

Min(x2 – x4 – 3 x5)

ệ ề

x1 + 2x2 - x4 + x5 = 1 2 + x3 +2x4 - x5 = 2 Đi u ki n: - 4x 3x2 +x5 + x6 = 5

xj ≥ 0, j=1..6

đi m X=(0,1/3, 0, 11/3, 4, 0) có ể

ể i ố ưu?

S d ng tính l ch bù ki m tra ử ụ ệ ương án t ph i là ph ả i:ả Gi •Ki m tra X là ph ương án: ể 0 + 2*1/3 – 11/3 +4 =1 -4*1/3 +0+2*11/3 – 4 = 2 3*1/3 + 4 + 0 = 5

(cid:222) X là phương án.

t bài toán ế đ i x ng: ố ứ

•Vi đ i ng u không ẫ ố Max( g(Y) = y1 + 2y2 +3y5 ) y1 ≤ 0 (1) 2y1 - 4y2 + 3y3 ≤ 1 (2) y2 ≤ 0 (3) -y1 + 2y2 ≤ -1 (4) y1 - y2 + y3 ≤ -3 (5) y3 ≤ 0 (6)

2 , x4 , x5 > 0 . Theo tính l ch bù thi`(2),(4),(5)

ệ ạ

T i X ta có x x y tra d u =. Ta có h : ệ ấ ả 2y1 - 4y2 + 3y3 = 1 y1 = -19/3 -y1 + 2y2 = -1 (cid:219) y2 = -11/3 y1 - y2 + y3 = -3 y3 = -1/3

Y=(-19/3, -11/3, -1/3 ) tho mãn các ả đi u ki n còn l ệ ề i c a h ạ ủ ệ

ậ

phương tri`nh • Tính f(X) = - 46/3 • g(Y) = - 46/3 • f(X) = g(Y) • K t lu n: ế • X =(0, 1/3, 0, 11/3, 4, 0 ) là phương án t i ố ưu.

S d ng tính l ch bù ki m tra X= (x

ương án t

i ố

ể

ệ

ạ

ử ụ

j) có ph i là ph ả

ương án

ỗ

đ i x ng. ố ứ ả

ề

ằ

ấ

i ả

đ i ng u không ẫ ệ

j > 0 thì đi u ki n j x y ra d u b ng

h ệ

i. So sánh

đi u ki n còn l ệ

ề

ạ

ả

ể

f(X)

ế

(cid:222)

D ng 2:

ương án c c biên xu t phát X =

ự

ấ

ạ

i ố ưu Y* khi bi

t phế

ương án

ương án t

D ng 3: ạ i ố t

ệ ừ ư c 2 ớ b

đén bư c 3.ớ

D ng 4:

ạ

i ố ưu X*.

t bài toán

ế

ố

D ng 1: ưu? Bư c 1: Ki m tra X là ph ớ ể Bư c 2: Vi t bài toán ế ớ Bư c 3: T i X có x ạ ớ Y = (yi) Bư c 4: Ki m tra Y có tho mãn các ớ và g(Y) Bư c 5: K t lu n ậ ớ S d ng tính l ch bù ki m tra ph ể ệ ử ụ (xj) có ph i là ph i ố ưu ? ương án t ả đ n bế ư c 5.ớ ệ ừ ư c 2 ớ b Th c hi n t ự S d ng tính l ch bù, tìm ph ệ ử ụ ưu X. Th c hi n t ự Cho phương án t Bư c 1: Vi Bư c 2: Thay Y=(y

ệ

ấ

j =0.

ớ ớ ề

ệ

i ố ưu Y* , tìm phương án t đ i x ng đ i ng u không ố ứ ẫ * ) vào đi u ki n j x y ra d u “< ” thì x ề ả i *. i h tìm X ả ệ

Thay vào đi u ki n bài ra gi

ạ ế

Ví d 2:ụ Cho bài toán qui ho ch tuy n tính. Min(x2 - x4 - 3x5) x1 + 2x2

- x4 + x5 = 1 Đk: - 4x2 + x3 + 2x4 – x5 = 2 + x5 + x6 = 5

3x2 xj ≥ 0, j =1..5

S d ng tính l ch bù: ử ụ ệ

ương án c c biên xu t phát có ph i là ph ấ ự ả ương án

i ố ưu Y*(-19/3,-11/3,-1/3). Tìm phương án t i ố

i ố ưu X* =(0,1/3,0,11/3,4,0).tìm phương án t i ố ưu

a) Ki m tra ph ể t i ố ưu b) Cho phương án t ưu X*. c) Cho phương t Y*.

Gi i:ả

1A3A6} => j = {1,3,6}

ị

ấ ự

đ i x ng ố ứ

1,x3,x6 > 0. theo tính l ch ệ

a)Ta có ma tr n ậ đơn v : E = {A (cid:222) x1=1, x3=2, x6=5 => phương án c c biên xu t phát (1,0,2,0,0,5) Bài toán đ i ng u không ẫ ố Max(y1 + 2y2 + 5y3) y1 ≤ 0 (1) 2y1 - 4y2 + 3y3 ≤ 1 (2) y2 ≤ 0 (3) -y1 + 2y2 ≤ -1 (4) y1 - y2 + y3 ≤ -3 (5) y3 ≤0 (6) ương án c c biên xu t phát có: x ự ấ

T i phạ bù.

1 = 0

(cid:222) (1), (3), (6) X y ra d u “=” y ấ ả

y2 = 0 => Y(0,0,0) y3 = 0

ỏ đi u ki n (4),(5) ệ ề

ự ả ương án t i ố

Y không th a mãn => Phương án c c biên xuát phát không ph i là ph ưu.

ẫ đ i x ng. ố ứ

b) Bài toán đ i ng u không ố Max(y1 + 2y2 + 5y3) y1 ≤ 0 (1) 2y1 - 4y2 + 3y3 ≤ 1 (2) y2 ≤ 0 (3) -y1 + 2y2 ≤ -1 (4) y1 - y2 + y3 ≤ -3 (5) y3 ≤ 0 (6)

ề

-11/3

Y* =(-19/3,-11/3,-1/3) thay vào đi u ki n: ệ < 0 -19/3 2*(-19/3) – 4(-11/3) + (-1/3) = 1 < 0 = - 1 -(-19/3) + 2(-11/3) -19/3 – (-11/3) + (-1/3) = -3 -1/3 < 0

ả ạ

ệ thay vào h :ệ

x2=1/3 = 2 => x4=11/3

x5=4

T i (1), (3), (6) x y ra d u “<” theo tính l ch bù: ấ Ta có: x1=0, x3=0,x6=0 x1 + 2x2 - x4 + x5 = 1 -4x2 + x3 + 2x4 - x5 3x2 + x5 + x6 = 5 xj ≥ 0, j =1.. 6

=> X* = (0, 1/3, 0, 11/3, 4, 0)

có x2,x4,x5 > 0

c) T i X* ạ

ệ ả ấ

ta có: theo tính l ch bù => (2), (4), (5) x y ra d u “=”

=-1 =>

y1 = - 19/3

y2 = - 11/3

2y1 - 4y2 + 3 y3 = 1 -y1 + 2y2 y1 - y2 + y3 =-3 y3 = - 1/3

=> Y* = (-19/3, -11/3, -1/3)

Đ2 C p bài toán

ặ

đ i ng u không ẫ

ố

đ i ố x ng.ứ

Cho bài toán quy ho ch tuy n tính: ế ạ

Min(f(X)= (cid:229) cjxj )

aijxj ≥ bi, i=1..m

n (cid:229) j=1

xj ≥ 0, j = 1..n

Bài toán đ i ng u ẫ đ i x ng. ố ứ ố

biyi )

ề aij ≤ cj , j=1..n

Max(g(Y) = (cid:229) i=1 m (cid:229) Đi u ki n: ệ i=1

Ví d 1:ụ Cho bài toán quy ho ch tuy n tính: ế ạ

Min(x1 -2x2 - x4) -x1 + x3 - x4 ≥ 2 x2 - x3 + x4 ≥ 5 2 x1 + x2 - x4 ≥ 1 xj ≥ 0, j=1..4

Bài toán đ i ng u ố

ẫ đ i x ng: ố ứ Max( g(Y) = 2y1 + y2 + y3) Đi u ki n ệ ề

-y1 + y3 ≤ 1 y2 + y3 ≤ -2 y1 - y2 ≤ 0 -y1 + y2 - y3 ≤-1

t bài toán ế đ i ng u ố ẫ đ i x ng d ng t ng quát. ạ ố ứ ổ

Ví d 2:ụ Vi Cho ví d minh ho . ạ ụ

C p bài toán ậ ẫ đ i x ng có ố ứ đ y ầ đ 4 ủ

đ i ng u Nh n xét: ố ặ đ i ng u không tính ch t c a c p bài toán ẫ ố ấ ủ ặ đ i x ng. ố ứ

Ví d 3:ụ Cho bài toán quy ho ch tuy n tính: ế

ạ Min(3x1 + 3 x2 + x 3 – x4)

Đi u ki n: -x ề ệ 2x1 + x2 – x3 - 2x4 ≥ 1 1 + x2 + x3 - x4 ≥ 2

xj ≥ 0, j = 1..4

t phế ương án t i ố ưu Y* =(1,2). Tìm phương án t i ố ưu

Bi X*.

Gi i:ả

ẫ đ i x ng: ố ứ

Ta có bài toán đ i ng u không ố Max (y1 + 2 y2)

Đk:

2y1 - 2y2 ≤ 3 y1 + y2 ≤ 3 - y1 + y2 ≤ 1 -2y1 - y2 ≤ -1

ệ

Thay Y* = (1,2) vào h trên: 2*1 – 2*2 < 3 1 + 2 = 3 -1 + 2 = 1 -2*1 – 2 < -1

ề ệ ả

ệ đ u ta có: ầ ấ ề ệ Do đi u ki n (1) và (4) x y ra d u <. Theo tính l ch bù thì x1 = 0 và x4 =0 . Thay vào đi u ki n ban

x2 – x3 =1 x2 = 3/2 (cid:222) x3 = 1/2 x2 + x3 =2

(cid:222) X* = (0, 3/2 , 1/2 , 0).

ở

ậ ủ

ương pháp đơn hình đ i ố

Đ3 Cơ s lý lu n c a ph ng uẫ

3.1 M i liên h gi a bài toán đã cho và bài toán đ i ng u. ệ ữ ố ố ẫ

Min ( f(X) = CX) AX = b Đk: X > 0

Bài toán đ i ng u c a bài toán trên: ẫ ủ ố Max (g(Y) = BY ) Đk: AY < C

*, Y* là phương án c a bài toán

ủ

*) = g( Y*) thì X*, Y* là phương án t

• N u Xế ẫ đã cho và bài toán đ i ố i ố ưu

• T n t i N u phế ương án X* là t i ố ưu (cid:219) ồ ạ

i ố ưu Y* tho mãn:

TY* = C)

• • ng u tho mãn: f(X ả c a bài toán trên. ủ (Tính l ch bù) ệ phương án t ATY* < C n u Xế (ho c: Xặ ả *= 0 * > 0 n u Aế

J G i B là ma tr n c a phép bi n ậ ủ ế đ i Cổ ọ

* =(cj) ,j ˛ ương ng ứ $

ương án c c biên Y thì t ự phương án

N u có ph ế c c biên X: ự

j ≤ 0

(cid:219) D Y = C* B-1

b X là phương án t

BY = C* (cid:222) BY = b (cid:222) X = B-1

i ố ưu.

bài toán không có phương án t i ố xj ≥ 0 (cid:222) xi k ≥ 0 (cid:222)

xây d ng ph ự ương án c c biên m i. ự ớ •X = (xj) : " • $ xk < 0 , " ưu • $ xk , $ xi k < 0 (cid:222)

Ví d 1:ụ

Gi i bài toán b ng ph ả ằ ương pháp đơn hình đ i ố

ng u.ẫ

Đk x2 - x3 - x4 + x5 = 1 xj ≥ 0, j= 1..5

Min(x3 + x4 + x5) -x1 + x3 - x4 + 2x5 = 2

Gi i:ả

ương đương:

Đưa bài toán v bài toán t ề Min(x3 + x4 + x5) x1 - x3 + x4 - 2 x5 = -2 Đk: x2 - x3 - x4 + x5 = 1

ị

(cid:222) xj ≥ 0, j=1..5 Ma tr n ậ đơn v E =(A1, A2), J= {1,2} x1 = -2, x2 = 1, x3 = 0, x4 = 0 ,x5 = 0

ự

Phương án c c biên xu t phát: X = (-2, 1, 0, 0, 0) ấ c1= 0, c2 = 0, c3 = 1, c4 = 1, c5 =1

L p b ng ậ ả đơn hình:

0 0 1 1

Xj Cj B¶n g C¬ së A3

A1 A2 A4 A5

-2 0 1 0 -1 1 -2

1 0 0 1 -1 -1 1 A1 A2

0 0 -1 -1 -1 I

1 1 -1/2 0 1/2 -1/2 1

0 0 1/2 1 -3/2 -1/2 0 A5 A2

II 1 -1/2 0 -1/2 -3/2 0

" T i b ng II có ạ ả xj ≥ 0

(cid:222) X* = (0, 0, 0, 0, 1)

f(X*) = 1.

i bài toán tìm min và ả

Chú ý: Phương pháp đơn hình đ i ngãu gi ố đ i lạ ư ng âm. ch xét các ợ ỉ

j + Cj ), j ˛

J- t p ch s ban ỉ ố ậ đ u, giá tr l y ầ ị ấ ở

2 + C2 ) = (-1/2 + 0 , 0 + 0) = (-1/2, 0)

* = (-2)*(-1/2) + 0 = 1.

•Tính Y* = (D b ng cu i. ả Y* = (D

* + y2

ố 1 + C1, D g(Y* ) = - 2y1

* = C*B-1 có tương ng X

N u t i ph ị ương án c c biên Y ự ứ

Đ nh lý 1: = B-1 b mà " i ố ưu. ế ạ xj ≥ 0 thì X*, Y* là phương án t

* = C*B-1 có tương ng ứ

N u t ị ế ạ ương án c c biên Y ự

i ố i ph xk < 0 và " xkj ≥ 0 thì bài toán không có phương án t

Đ nh lý 2: X = B-1 b, mà $ ưu.

* = C*B-1 có tương ng ứ

N u t ị ế ạ

ự ương án c c ự i ph xk < 0 , $ ương án c c biên Y ự xpk < 0 thì có th xây d ng ph ể

Đ nh lý 3: X = B-1b mà $ biên m iớ

ố

ương án c c biên ự

ẫ . đơn hình đ i ng u 3.2 Thu t toán ậ Bư c 0:ớ Tìm E = (Aj) ma tr n ậ đơn v J, Ph ị xu t phát ấ

X = (xj) Bư c 1ớ : Tính D

" ể

j Ki m tra N u ế đúng (cid:222) N u sai thì sang B

i ố ưu

xj ≥ 0 ? X là phương án t ư c 2ớ

$ ế Bư c 2ớ : Ki m tra ể xk < 0, " xkj > 0 ?

i ố ưu

N u ế đúng Bài toán không có phương án t N u sai sang B ư c 3ớ ế

j = xp (cid:222)

j D

Ch n Min x ọ Ap ra cơ sở

Aq vào cơ sở

Bư c 3:ớ xj < 0 D Min = (cid:222) xpj< 0 xpj xpq

quay. ầ ử xpq là ph n t

’ theo quy t c ắ đã

Xây d ng ph ự ương án c c biên m i X ự ớ

bi tế

X = X’ tr l ở ạ ư c 1.ớ i B

i bài toán b ng ph ả ằ ương pháp đơn hình đ i ố

Ví d 2ụ : Gi ng uẫ

Đk

Min(x1 – x2 + x3 + x4 + x5) 2x1 + x3 - x4 + 3x5 = 6 x1 + x4 - x6 = 3 4x1 + x2 - x4 +2 x5 = 5 xj ≥ 0, j=1..6

Gi i:ả

ương đương: ề

Đưa bài toán v bài toán t Min(x1 – x2 + x3 + x4 + x5 ) 2x1 + x3 - x4 + 3x5 = 6 x1 - x4 + x6 = -3 Đk:

4x1 + x2 - x4 + 2 x5 = 5 xj ≥ 0, j =1..6

3A6A2), J={3,6,2}

ị

x1 = 0 , x2 = 5 x3 = 6 , x4 = 0 , x5 = 0, x6 = -3 Phương án c c biên xu t phát X = (1, 5, 6, 0, 0, -3) ấ ự

Ma tr n ậ đơn v : E =(A (cid:222) (cid:222) c1 = 1, c2 = -1, c3 = 1, c4 =1, c5 =1, c6 = 0.

L p b ng ậ ả đơn hình:

-1

C¬ së

B¶n g

-1

-3

-1

A3 A6 A2

-3

-1

A3 A4 A2

-2

-1

f(X*)= 4

" T i b ng 2 ta có X*=(0, 8, 9, 3, 0, 0) ạ ả xj ≥ 0 (cid:222)

3 + C3 , D

6+ C6,,

2 + C2)

D f(X*) = 4 Y* = ( D

* + 5y3

(cid:222) = (0 + 1, -1 + 0, 0 + (-1)) = (1, -1, -1) * - 3y2 g(Y* ) = 6y1

= 6*1 -3*(-1) + 5(-1)

= 4.

Câu h i ôn t p: ỏ ậ

Vi t c p bài toán qhtt đ i ng u ế ặ ẫ đ i x ng d ng t ng quát. Cho ví ố ứ ổ ố ạ

d minh ho . ạ ụ

Vi t c p bài toán đ i x ng d ng t ng quát. Cho ế ặ đ i ng u không ẫ ố ố ứ ổ ạ

ví d minh ho . ạ ụ

Cho ví d minh ho v c p bài toán đ i ng u ạ ề ặ ụ ẫ đ i x ng (ho c ố ứ ố ặ

không đ i x ng). Nêu nh n xét v c p bài toán ố ứ ề ặ ậ đ i ố đ i ng u (ho c ố ẫ ặ



đ i x ng). ố ứ

Nêu các giai đo n xây d ng thu t toán ự ạ ậ đơn hình đ i ng u. ố ẫ

đã cho và bài toán đ i ng u. Nêu m i liên h gi a bài toán qhtt ệ ữ ố ố ẫ

Nêu cơ s lý lu n c a ph ậ ủ ở ương pháp phân ph iố



Gi i bài toán b ng ph ả ằ ương pháp đơn hình đ i ng u. ố ẫ

Bài t pậ

Bài 1: Cho bài toán qui ho ch tuy n tính ạ

ế Min(3x1+4x2+2x3+x4+5x5)

ề

‡ 0,j=1..8

ự

j. ương án c c biên xu t phát và các giá tr c ấ

ủ ặ ể ệ



x1 -2x2 -x3 + x4 + x5+x 6 = -3 -x1 –x2 -x3 + x4 + x5 +x 7 = -2 đi u ki n ệ x1 +x2 - 2x3+2x4 -3x5 +x 8 = 4; xj t phế a.Vi b.B ng tính l ch bù c a c p bài toán ằ X=(0,0,3,0,0,0,1,10) có ph i là ph ị đ i ng u, hãy ki m tra i ố ưu? ẫ ố ương án t ả

ủ ố

i i ố ưu c a bài toán i ố ưu X* và giá tr t đ i ng u. B ng ằ ẫ ị ố ưu f(X*) ệ

ả ử ệ ăn b n sn.txt ch a các s nguyên là ma tr n A ứ ậ ả

ố ương trình làm các công vi c sau: ệ ậ

ậ ậ

c.Cho Y*=(-2,0,0) là phương án t ương án t tính l ch bù hãy tìm ph c a bài toán trên. ủ d. Gi s có t p v c a bài toán trên. L p ch ủ -Đ c d li u t ọ ữ ệ ừ ệ -Tính và in ra các ij t t p vào ma tr n A, In ma tr n A. i pacb xu t phát. ấ ạ



i câu a,b,c. Bài 2: L p chậ ương trình gi ả

Bài 3: Gi i bài toán qui ho ch tuy n tính b ng ph ả ế ằ ạ ương pháp

đơn hình đ i ng u: ố ẫ

Min(x3+x4+x5)

ệ ề x2 -x3 -x4+ x5 = 6

x1 -x3 +x4 -2x5= -10 Đi u ki n xj ‡ 0, j=1..5.

i bài toán b ng ph ương trình gi ả ằ ương pháp đơn hình

Bài 4: L p chậ đ i ng u. ẫ ố

CHƯƠNG 3 PHƯƠNG PHÁP PHÂN PH IỐ

 Bài toán v n t i ậ ả Cơ s lý lu n c a ph ậ ủ ở ương pháp

phân ph iố  Tính ch t c a bài toán ủ ấ

v n t i ậ ả Thu t toán phân ph i ố ậ

 Bài toán v n t ậ ả i d ng ạ Câu h i và Bài t p áp d ng ụ ỏ ậ

b ngả thu t toán phân ph i. ố ậ

tìm  Các phương pháp

phương án c c biên xu t ự ấ



phát

Đ1. Bài toán v n t

i.

ậ ả

t ộ ạ ế

ầ ợ ừ ợ

ế ể

n kho v m n C n v n chuy n m t lo i hàng t ơi tiêu th . Bi ề ể ậ ụ j, lư ng hàng c n tiêu th t i kho th j là a lư ng hàng t ụ ạ đi m i là i ầ ứ ạ ể bi. Ci j là cư c phí v n chuy n trên 1 đơn v hàng t j -> i. ừ ị ể ậ ớ đ , sao cho có ch c v n chuy n hàng sao cho phát h t thu Hãy t ủ ổ ứ ậ ư c phí v n chuy n là Min. t ng c ớ ổ ể ậ

ể ợ

Mô hình toán h c:ọ G i xọ ij là lư ng hàng chuy n j -> i Min(f(X) = (cid:229) C j ị xi j)

i,j

xi j = aj

xi j = bj

(cid:229) i =1 Đk: (cid:229) j =1

xi j , bi, aj ≥ 0

Nh n xét:

i là mô hình bài toán quy ho ch tuy n ậ ả

i b ng ph ạ

ế ạ ương pháp đơn ương trình. Nên ta ph i ả

ậ Mô hình bài toán v n t tính d ng chính t c nên có th gi ể ả ằ ắ hình nhưng có có m + n n và m + n ph ẩ tìm thu t toán hi u qu h i. ả ơn đ gi ể ả ệ ậ

Đ2. Tính ch t c a bài toán v n t

i.

ấ ủ

ậ ả

Tính ch t 1:ấ Bài toán v n t cân b ng thu phát. i có ph i ố ưu (cid:219) ằ

ương án t ậ ả Nghĩa là: n m

(cid:229)

aj = (cid:229) bi j =1 i =1

: Ch ng minh

ứ * Gi i có ph ương án t i ố ưu: ả ử

(cid:229) (cid:222) (cid:229) s bài toán v n t xi = aj ậ ả x ij = (cid:229)

(cid:222) (cid:229) aj (1) i i,j j (cid:229) bj (2) xi j = bi x ij = (cid:229)

(cid:222) T (1) và (2) (cid:229) ừ bj

i i,j i aj = (cid:229) j i i ố ưu (cid:219) * Bài toán có phương án t ương án khác r ngỗ

-T p ph ậ - f(X) b ch n ị ặ

(cid:229) j=1

ajbi X = (xij) : xij = ≥ 0 n

ajbi

(cid:229) bi aj i i

(cid:229)

xij = n = = aj

(cid:229)

I (cid:229) aj aj j=1 i

(cid:229)

ajbi bi

(cid:229) aj j j

(cid:229)

xij = = = bi

i n n (cid:229) aj (cid:229) j=1 j=1

(cid:229)

i ố ưu.

(cid:222) X = (xi j) là phương án t

f(X) = (cid:229) cij xij

bi = L

i,j aj = (cid:229) (cid:229) j i

Ta có: (cid:229) aj = L

jị = c

xi j = (cid:229) i,j j x jị < L Đ t Max c

ci j xi j ≤ n*m*c*L

(cid:222) ặ (i,j) f(X) = (cid:229) i,j (cid:222) đpcm. f(X) b ch n ị ặ

Tính ch t 2:ấ

H phệ ương trình:

(cid:229) x jị = aj

(cid:229) xi j = bi

Có m + n – 1 phương trình đ c l p tuy n tính. ộ ậ ế

H qu : i có s to ậ ả ự ủ ố ạ đ ộ

ệ ả Phương án c c biên c a bài toán v n t dương t i ố đa là m + n -1.

Đ3. Bài toán v n t

ậ ả ạ

ả i d ng b ng.

Ví d 1:ụ

aj bi

3 1

\ 2

\ 3

2 1

4 2

\ 1

\ 3

3 4

8 2

Cho bài toán v n t i d ng b ng: ậ ả ạ ả

ậ ả ạ

aj bi

2 2

\ 0

6 1

\ 3

10+k

Ví d 2:ụ Cho bài toán v n t a. Tìm k đ bài toán có ph ể b. Tìm m t phộ ự i d ng b ng: ả ương án t i ố ưu. ương án c c biên xu t phát. ấ

i:ả a. Bài toán có phương án t i ố ưu :

8 + 9 + 10 + k = 6 + 7 + 17 + 10 k = 13

b.T ng quát: ổ

T i O(i,j) : ạ

j ừ đén i

j ặ đơn v hàng t ị ừ đ n ế - x jị là lư ng hàng t ợ - ci j là cư c phí ho c ớ

ợ

N u xế i j > 0 thì O(i,j) đư c ch n ọ xi j =0 thì O(i,j) b lo i. ị ạ

Khái ni m chu trình: ệ M t t p ứ ự đư c ch n c a b ng ọ ủ ả ợ

các ô ế ợ ọ ả ộ đi u ề

ộ ậ đư c s p th t ợ ắ ậ ả đư c g i là m t chu trình n u tho mãn các i v n t ki n sau: ệ

- Hai ô đư c ch n n m trên cùng m t hàng hay m t ằ ộ ộ ợ ọ

c t.ộ

- Ô đ u tiên và ô cu i cùng n m trên m t hàng hay m t ằ ầ ố ộ ộ

c t.ộ

- Không có 3 ô nào n m trên m t hàng hay m t c t. ộ ộ ằ ộ

Tính ch t 3:ấ

ự ương án c c biên khi và ch ỉ

Phương án bài toán v n t ậ ả khi các ô đư c ch n không l p thành chu trình. ợ i là ph ậ ọ

Đ4. Các phương pháp tìm pacb xu t phát.

ấ

ả ương án c c ự

i d ng b ng. Tìm ph ậ ả ạ ương pháp góc Tây b c và tính c ắ ư c ớ

aj bi

8 1

\ 9

\ 8

5 2

1 7

\ 1

\ 3

6 4

10 5

4.1 Phương pháp góc Tây B cắ . Ví d 1:ụ Cho bài toán v n t biên xu t phát theo ph ương án này. phí t ấ i phạ

Các bư c tìm ph ớ ương án c c biên xu t phát: ự ấ

ợ

ố đa vào ô góc Tây B cắ ố ả ăng phân ph i sau

Bư c 1:ớ Bư c 2:ớ đó tr l Phân ph i lố ư ng hàng t “Xoá ” các hàng, các c t h t kh n i B i ộ ế i. ạ ở ạ ư c 1 v i các ô còn l ớ ớ

Ví d 2:ụ Cho bài toán v n t

i d ng b ng: ể ạ ậ ớ ương án c c biên xu t ự ấ

aj bi

5 2

7 3

2 6

\ 9

\ 2

6 4

\ 3

\ 8

10 5

ả ậ ả ạ i ph Tính cư c phí v n chuy n t phát theo phương pháp góc Tây B c.ắ

Cư c phí v n chuy n: 5*2 +7*3 + 2*6 + 4*6 + 10*5 = 117 ể ậ ớ

ố

4.2 Phương pháp góc Cư c phí t ớ Ví d 1:ụ Cho bài toán v n t ậ ả ạ

i ố ưu?

ợ ở ư c phí v n chuy n t ậ

câu a, tính c ấ ự i ể ạ ương pháp cư c phí ớ

6 6

4 4

10 10

aj aj bi bi

7 7

\ \ 10 10

4 4 2 2

3 3 4 4

8 8

6 6 1 1

\ \ 8 8

2 2 3 3

K K

\ \ 15 15

\ \ 9 9

5 5 5 5

i thi u toàn b ng. i thi u. ể i d ng b ng. ả ương án t a. Tìm k đ bài toán có ph ể b. V i k tìm đư c ớ ớ phương án c c biên xu t phát theo ph t ố ể ả

Các bư c tìm ph ớ ương án c c biên xu t phát: ự ấ

i ợ ố đa vào ô có cư c phí bé ớ

ế

Bư c 1ớ : Phân ph i lố ư ng hàng t nh t.ấ Bư c 2ớ : “Xoá” các hàng các c t vào h t kh n sau đó tr l ả ăng phân ph i ố i. ộ đ i v i các ô còn l ố ớ ở ạ ư c 1 ớ i B ạ

i d ng b ng: Ví d 2:ụ Cho bài toán v n t

Tính cư c phí v n chuy n t ớ ấ ậ ả ạ ậ

aj bi

3 1

\ 15

\ 4

\ 10 4 1

5 3

3 2

\ 5

5 7

i thi u toàn b ng. ể ạ phát theo phương pháp cư c phi t ớ ương án c c biên xu t ự ả ể ả i ph ố

Cư c phí: 3*1 + 4*1 + 5*3 + 3*2 + 5*7 = 63 ớ

4.3 PHƯƠNG PHÁP VAUGEN.

aj bi

i d ng b ng: Ví d 1ụ : Cho bài toán v n t ậ ả ạ ả

\ 7

\ 9

3 5

4 3

2 4

3 6 1

\ 6

\ 4

8 1

1 1

3 3 4 1 3 1 1 3

Các bư c tìm ph ớ ương án c c biên xu t phát: ự ấ

Bư c 1ớ : V i m i hàng và m i c t tính ỗ ộ ỗ ớ

ớ ấ

ố ư ng hàng t ợ đ chênh ộ đ ộ ộ ố đa cho ô i

ư c phí bé nh t, ch n hàng hay c t có l ch c a 2 c ủ ọ ệ chênh l ch l n nh t, phân ph i l ấ ớ ệ có cư c phí bé nhát.

ớ Bư c 2:ớ

ph i sau đó tr l i B ố “Xoá” các hàng các c t h t kh n ả ăng phân i. ở ạ ư c 1 v i nh ng ô còn l ạ ớ ộ ế ữ ớ

aj bi

i d ng b ng: Ví d 2:ụ Cho bài toán v n t ậ ả ạ ả

7 1

\ 8

3 9

\ 5

5 2

6 2

\ 4

9 3

\ 6

7 1

0 0 1 1 4 2 1 2 1

i pacb xu t phát theo ph ạ ấ ương pháp Vaugen:

ớ

Tính cư c phí t ớ Cư c phí: 7*1 + 5*2 + 3*9 + 6*2 + 9*3 =83

Đ5. Cơ s lý lu n c a ph

ậ ủ

ở

ương pháp phân ph i.ố

ậ ả

Xét bài toán v n t Min(f(x) = (cid:229) i: ci i xi j )

i,j

(cid:229) xi j = aj

i ĐK: (cid:229) xi j = bi

j x jị , aj , bi ≥0, i=1..m

j = 1..n

ố

Bài toán đ i ng u c a bài toán trên: ẫ ủ Max(g(u,v) = (cid:229) aj uj + (cid:229) bivi) Đk: uj + vi ≤ ci j

i j = uj + vi – ci j ợ

i j = 0

Đ t ặ D đư c chon T i O(i,j) ạ Xét D i các ô b lo i. i j t ị ạ ạ i tìm u j , vi: Gi ả i các ô t ạ ọ ợ

ộ ẫ ụ ố

j + vi = ci j đư c ch n u i ố đa m + n – 1 phương trình, s n H phệ ương trình trên có t m+n. Do đó có vô s nghi m ph thu c l n nhau. Ta ch c n ệ i j các ô b lo i. Đ cho m t b nghi m ị ạ ộ ộ ch n uọ

D ố ẩ ỉ ầ đơn gi n ả ể

ằ ệ đ tính ể j , vi nào đó b ng 0.

i d ng b ng. ậ ả ạ

i j t

Tính D i pacb xu t phát theo ph Ví d 1:ụ Cho bài toán v n t ạ ấ ả ương pháp góc Tây B c.ắ

aj bi

7 1

3 2

\ 3

u1= 1 u2= 2 u3=0 18

\ 3

2 4

9 2

v1=0

\ 4

\ 5

9 4

v2=2

v3=4

- Tìm phương án c c biên xu t phát theo ph ự ấ ương pháp

góc Tây B c.ắ

i j

- Tìm uj , vi - Tính D

ị

i j ≤ 0 thì X là

jị ) có "

(Tiêu chu n t Đ nh lý 1: i ph N u t ế ạ phương án t ẩ ố ưu) i ương án c c biên X = (x ự i ố ưu.

pq > 0 thì có th xây

N u t ị ể

Đ nh lý 2: d ng ph ự i pacb X =(x ế ạ ương án c c biên m i X ự ớ D i j) $ ’ = (x’i j).

i bài toán b ng ph Ví d 2ụ : Gi ả ằ ương pháp Phân ph i.ố

u1= 6 u2= 5 u3 = 7 u4=2 (I)

3 \ 3

4 7

5 2

v1=0

3 5

v2= -5

8 1

-4 \ 4

-9 \ 6

5 2

v3= -4

-6 \ 9

\-7 5

7 1

0 \ 2

ương pháp cư c phí ớ

ể ả

i các ô b lo i. ị ạ ạ i:ả - Tìm phương án c c biên xp theo ph ự i thi u toàn b ng. t ố - Tìm uj ,vi - Tính D i j t

Chon ô(1,1 ) vào chu trình. L p chu trình V = {(1,1),(1, 3),(2,3),(2,1)} ậ

L C L C

i j = x13 = 4

VL = {(1,1),(2,3)} VC = {(1,3), (2,1)}

Ch n Minx ọ (i,j)˛ VC

.

u1= 3 u2= 5 u3 =4 u4=2 (II)

v1=0

4 3

--3 \ 7

5 2

3 5

v2= -2

4 1

-6 \ 6

-1 \ 4

9 2

v3=-4

-9 \ 9

-3 \

-7 \ 5

7 1

i j ≤ 0

" T i b ng 2: D ạ ả

F(X*) = 4*3 + 3*5 + 5*2 + 4*! + 9*2 +7*1 = 66 G(U,V) = (g(3,5,4,2),(0,-2,-4)) =66

ố : Thu t toán phân ph i ậ

i j) theo 1

ự ấ

t.ế

i j t

i các ô b lo i. ị ạ ạ Bư c 0ớ : Tìm phương án c c biên xu t phát X= (x phương pháp đã bi Bư c 1ớ : Tìm uj , vi . Tính D

i j ≤ 0 ?

" D

Ki m tra ể N u ế đúng X là phương án t i ố ưu.

pq Ô(p,q) vào chu trình

D N u sai sang b ế Bư c 2ớ : Max ư c 2.ớ i j = D

L,VC .

i j > ≥0 L p chu trình V, V i j = xrs Ch n Min x ọ (i,j) ˛ VC

D ậ

ương án c c biên m i X ớ

’ = (x’i j) ế ế ế

˛ Xây d ng ph ự ự xi j n u (i,j) x’i j = x jị + xrs n u (i,j) xi j – xrs n u (i,j) ˇ V VL vC

X= X’ tr l ở ạ ư c 1.ớ i B

Câu h i ôn t p: ỏ ậ

Vi t mô hình toán h c c a bài toán v n t i d ng t ng quát. Cho ế ậ ả ạ ọ ủ ổ

ví d minh ho bài toán v n t i d ng b ng. ậ ả ạ ụ ạ ả

Vi t c p bài toán đ i ng u c a bài toán v n t i trong tr ế ặ ẫ ủ ậ ả ố ư ng ờ

h p t ng quát. Cho ví d bài toán v n t i d ng b ng 2x2. Vi t bài ậ ả ạ ợ ổ ụ ả ế

đó. toán đ i ng u c a bài toán ẫ ủ ố

Nêu các tính ch t c a bài toán v n t i. ậ ả ấ ủ

Nêu đi u ki n ề ệ đ xây d ng ph ự ể ương án c c biên m i X’. Công ự ớ

th c tính ph ph ứ ương án c c biên m i X’ t ự ớ ừ ương án c c biên X. ự



Gi i bài toán b ng ph ả ằ ương pháp phân ph i.ố

Bài t pậ

Bài 1: Gi s ả ử đã có t p Mta.txt, Mtb.txt, Mtc.txt ch a các s ố ứ ệ

ậ ả ủ ậ ương trình đ c d ọ ữ nguyên là aij, bi, cj c a bài toán v n t i. L p ch

li u t t p vào các m ng a,b,c và in ra màn hình các m ng đó. ệ ừ ệ ả ả

Ki m tra pacb xu t phát theo ph i thi u toàn ể ấ ương pháp cư c t ớ ố ể

b ng có ph i là pat ả ả ư?



i bài toán v n t i. Bài 2: L p chậ ương trình gi ả ậ ả

Bài giảng Lý thuyết tối ưu - Phan Lê Na