Bài giảng Tối ưu hóa: Chương 2 - ThS. Nguyễn Công Trí

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

CHÖÔNG 2

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU

BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH ÑOÁI NGAÃU

1. CAÙCH THAØNH LAÄP BAØI TOAÙN QUY HOAÏCH

(Xem)

TUYEÁN TÍNH ÑOÁI NGAÃU

Muïc ñích vaø yù nghóa

Ths. Nguyeãn Coâng Trí

(Xem)

2. CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU

(Xem)

3. THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU

 Vôùi baøi toaùn QHTT, baøi toaùn goác, kyù hieäu laø P (Primal), chuùng ta coù theå thieát laäp baøi toaùn QHTT khaùc, baøi toaùn ñoái ngaãu, kyù hieäu laø D (Dual), sao cho töø lôøi giaûi cuûa baøi toaùn naøy ta coù theå thu thaäp ñöôïc thoâng tin veà lôøi giaûi cuûa baøi toaùn kia.

Copyright 2001

4. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI

NGAÃU TRONG BAØI TOAÙN QHTT

(Xem) Ths. Nguyeãn Coâng Trí

(Xem)

5. BAØI TAÄP

 Ñeå coù thoâng tin caàn thieát veà baøi toaùn goác, coù theå nghieân cöùu treân baøi toaùn ñoái ngaãu cuûa noù.

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Goïi g(y) laø haøm muïc tieâu cuûa baøi toaùn (II), ta coù

 Hôn nöõa, khi phaân tích ñoàng thôøi caû hai baøi toaùn goác vaø ñoái ngaãu, chuùng ta coù theå ruùt ra caùc keát luaän coù giaù trò veà maët toaùn hoïc laãn veà maët yù nghóa kinh teá.

min

x ( )







  I

Xeùt baøi toaùn QHTT (P) döôùi daïng chính taéc t   c x g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0.



    

≤ ctx + yt(b – Ax), vôùi x ≥ 0.

 Neáu x laø P.A cuûa baøi toaùn (I) thì b – Ax = 0 vaø

g(y) ≤ ctx. Vaäy g(y) laø moät caän döôùi baát kyø cuûa haøm muïc tieâu.

Vôùi x = (x1, x2,...…, xn)n, b = (b1, b2,...…, bm)m Giaû söû baøi toaùn (P) coù P.A.T.U laø xopt vaø goïi x0 laø moät P.A cuûa baøi toaùn (P), ta coù ctxopt ≤ ctx0. Goïi x = (x1, x2,...…, xn)n, vôùi x ≥ 0 sao cho  Ta tìm caän döôùi lôùn nhaát Max{g(y)}, thaät vaäy Ax – b  0

L x y ( ,



)



t y b Ax

min

  









g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0. = min{ctx + ytb – ytAx}, vôùi x ≥ 0. Baøi toaùn töông ñöông: t c x = min{ytb + (ct – ytA)x}, vôùi x ≥ 0.

x   y R

0 m .

    

= ytb + min{ (ct – ytA)x}, vôùi x ≥ 0.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU 0

khi







Xeùt

  t y A x



khi





t y A t y A

   

f x ( )

 8

 6





x 4

Ví duï 2.1. Baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT sau ñaây min

  min c  x 0 Vaäy ta ñöôïc





x 3

x 1 x 1





x 5 x 5 x 5

 2





x 2 x 2

x 3

x 4

max

g y ( )

t   y b

g y ( )

t   y b

max





1,5











y ( )





t y A m

t  y A c m

y 3

        laø baøi toaùn

 y R

    

 

max 2

4 2

y 1 y 1

     Hay baøi toaùn töông ñöông t   y b

g y ( )

max

  2

 

0 0

y 1

t A y





y 3 y 3 y 3

 c m



 

8 6

y 1

 y R

         

    

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Baøi toaùn goác (P)

g(y) = ytb Suy ra baøi toaùn ñoái ngaãu coù daïng

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.2. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT

f x ( )







min



max

x ( )

min

x 2

y ( )





max

Baøi toaùn ñoái ngaãu (D)

 1

  x 4  2

y 1  3

 2



x 4

Baøi toaùn ñoái ngaãu Df   y 3 y 3



 3



x 1    3

2   

  



3 2





  1

x 2 x 2 x 2

x 3 x 3 x 3 x 3

x 4

x 1 x 1 x 1



a y ij i

a x ij

b i i





  2

 1





1, 2

y 1 y 1 y 1 y 1

       

        

        



y 1

Haøm muïc tieâu   c x j  1 j Raøng buoäc thöù i Haøm muïc tieâu  b y y ( ) i i Raøng buoäc thöù j



 3



  1  3   4 2   2   

x 1



x 2



 3  2

y 3 y 3 x 4

  khoâng raøng buoäc

    

    

AÅn thöù I

    

 2  

 

2 1, 3,

  

y 1 y

 

0 0

y 3 y 3 y 3 y 3  0   1   2   3   4

y 1 y 1 x 2 x 2

0, x 1 x 1

VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7

AÅn thöù j      Caùc caëp ñoái ngaãu y 2 y 2 x 3 x 3

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.3. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.4. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT  3

m in

f x (







)

x 1

f x

 ( ) 2



max

x 2

  x 3

 ( ) 28 y





min

y 1

y 3

 4

 2



 3

 2



1 2

2 5

1 0

0 1

  

  

  

  

x 1 x x

     

    



 3



  3

3 2

3  

 

10 15

x 1 x 2 x 2 x 2

x 1 x 1 x 1

x 3 x 3 x 3





1, 3

 3



  8

Df y 7 1 y 1 y 1





1, 2

       

2 0,





y 1

y 3

      

y 1

Baøi toaùn ñoái ngaãu



)

  y 2



 2



x 1

y 1

 3

  

x 2

x 1 x 2 x 3

y 1



  

  

0, 0, 0, x 1

y 1 1 0 0 1 1 2

4 3 8

    

4 3 8 2, 5,

    

y 1 y

 

0 0

Baøi toaùn ñoái ngaãu max 5 ( Caùc caëp ñoái ngaãu  3

y  y 2  x 3  2 x 3

x 2





     y

     1, 2

 7 2

4 4   3

 2  

y 3 y 3  

 28, 15,

1 0 0

 

2 y 3 y 3 y 3 0   1   2   3   4

0, x 1 x 1

y 1 y 1 x 2 x 2

y 2 x 3 x 3

y 1 y 3

CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU

THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.5. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT f x ( )

max



  x 2

Caùc raøng buoäc ñoái ngaãu   1   2   3   4   5



(

)

m i n

x 1



Baøi toaùn ñoái ngaãu y   ÑÒNH LYÙ 1. Neáu moät trong hai baøi toaùn ñoái ngaãu nhau coù P.A.T.Ö thì baøi toaùn kia cuõng coù P.A.T.Ö vaø giaù trò haøm muïc tieâu cuûa chuùng baèng nhau.

  

  

x 1 1 0 0 1 1 2

4 3 8

1 0

0 1

1 2

2 5

    

  

  

  

  

y y y

    

     





     x

     1, 2





HEÄ QUAÛ 1.

0 

1, 3 

y 1

x 1







x 1

2  

0 0

 

y 1 y

3 4, 3,

Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái ngaãu nhau coù phöông aùn toái öu laø moãi baøi toaùn coù ít nhaát moät phöông aùn. Raøng buoäc ñoái ngaãu  HEÄ QUAÛ 2.







2 y

  1   2   3   4   5

x 1

Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái ngaãu nhau khoâng coù P.A.T.Ö laø moät baøi toaùn coù P.A coøn baøi toaùn kia khoâng coù P.A.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU

CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU ÑÒNH LYÙ 2.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ YEÁU)

opt, x2

opt), Yopt = opt, ..., xn opt) laàn löôït laø P.A.T.Ö. cuûa baøi

opt, y2

opt), Yopt = opt, ..., xn opt) laàn löôït laø P.A.T.Ö. cuûa baøi

opt, y2

ÑÒNH LYÙ 3.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ MAÏNH)



opt a y ij i

Neáu caëp baøi toaùn ñoái ngaãu nhau coù P.A.T.Ö. thì toàn taïi moät caëp phöông aùn sao cho trong caùc caëp ñoái ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu ñaúng thöùc thì raøng buoäc kia xaûy ra vôùi daáu baát ñaúng thöùc ngaët. Nghóa laø, vôùi Xopt = (x1 opt, ..., ym (y1 toaùn goác vaø baøi toaùn ñoái ngaãu, ta coù

opt a y ij i

 1

    



opt = 0 thì toàn taïi n

 Neáu xj

opt  0 (> hoaëc <).



opt = 0

 thì toàn taïi yi

a x ij

opt j

a x ij

opt j

b i



opt > 0 thì ,   n  b i

 1

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

 Neáu  Neáu Ñieàu kieän caàn vaø ñuû ñeå caëp baøi toaùn ñoái ngaãu laø trong caëp raøng buoäc ñoái nhau coù P.A.T.Ö. ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu baát ñaúng thöùc ngaët (“>” hoaëc “<“) thì raøng buoäc kia xaûy ra vôùi daáu ñaúng thöùc. Nghóa laø, vôùi Xopt = (x1 opt, ..., ym (y1 toaùn goác vaø baøi toaùn ñoái ngaãu, ta coù m   Neáu xj thì yi

f x

 ( ) 4



min

x 1

x 2

Ví duï 2.6. Cho baøi toaùn QHTT

1 0 1 0 1 2

  

2     5  

  

  x 3 x 1 x 2 x 3

     

    





(1) (2) (3)

1,3 coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø yopt = (2, 3) vaø f(yopt) = 19. Haõy tìm P.A.T.Ö cuûa baøi toaùn treân. Baøi toaùn ñoái ngaãu y  ( ) 2

max

y   2





  x 2

x 3



 

2 5

1 0 1 0 1 2

x 2

x 3 x 2 3

  

  

  

2     5  

0 x 2 x 3

    

     



y 1 1 0 0 1

y 1 y 2

  

  

1 2

Caùc caëp raøng buoäc ñoái ngaãu x1 ≥ 0 vaø y1 ≤ 4 x2 ≥ 0 vaø y2 ≤ 3 x3 ≥ 0 vaø y1 + 2y2 ≤ 8 Thay yopt = (2, 3) vaøo caùc raøng buoäc Töø (1): y1 = 2 < 4  x1 = 0 (ñònh lyù 2). Thay x1 = 0 vaøo hpt cuûa baøi toaùn goác

    

    

4     3     8  

Vaäy, P.A.T.Ö cuûa baøi toaùn goác laø xopt= (0,1,2) vaø f(xopt) = fD(yopt) = 19.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU





f x ( )

max

2 





 

 4

x 3

3 x

 

2 x

 

16 23





1, 4

Ví duï 2.7. Cho baøi toaùn QHTT   x x 4 1  x 1 x 3 1 x 1

(1) (2) (3) (4) (5) (6)

m i n

1 6

2 3







)

Df y 5



2 y



3 2











2 0 ;





3 0

Coù P.A.T.Ö laø xopt = (0,14, 6, 5) vaø f(xopt) = 54. Haõy tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu. Baøi toaùn ñoái ngaãu 5 0 (

         

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

Max

Caùc caëp raøng buoäc ñoái ngaãu x1 ≥ 0 vaø 5y1 – 3y2 + 4y3 ≥ 2 ≥ 2 x2 ≥ 0 vaø y1 x3 ≥ 0 vaø y1 + y2 + 3y3 ≥ 1 x4 ≥ 0 vaø 6y1 + 2y2 + y3 ≥ 4 + x3 + 2x4 ≥ 16 vaø y2 ≤ 0 -3x1 + 3x3 + x4 ≤ 23 vaø y3 ≥ 0 4x1 Thay xopt = (0, 14, 6, 5) vaøo caùc raøng buoäc Töø (2): x2 = 14 > 0  y1 = 2. Töø (3): x3= 6 > 0  y1 + y2 + 3y3 = 1 Töø (4): x4= 5 > 0  6y1 + 2y2 + y3 = 4 Giaûi heä phöông trình treân, ta coù y1 = 2; y2 = -23/5; y3 = 6/5. Vaäy, P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø yopt= (2, -23/5, 6/5) vaø fD(yopt) = 54.

x 2



x 4

Ví duï 2.8. Cho baøi toaùn QHTT   x f x ( ) 3

   x 1 3  

 

5 3

x 2 x 2





x 1 x 1 x 1

x 3

x 4

 ( ) 5 y

min

1. Kieåm tra tröïc tieáp, ta thaáy X, Y, vaø T laø P.A cuûa baøi toaùn. Vì Z khoâng thoûa maõn caùc raøng buoäc neân Z khoâng laø P.A cuûa baøi toaùn.

y 1

  y 3





1, 4

 3

       3  

y 3

2  

y y

y 1 y 1

  1  2  1  0

 

y 1 0;

y 3  y 3  0



y 1

y 3

2. Baøi toaùn ñoái ngaãu  Df

Ta coù 7 caëp raøng buoäc ñoái ngaãu Xeùt caùc vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), Z = (-4, 2, 0, 10) vaø T = (1, 2, 1, 2). Vectô naøo laø P.A.T.Ö. cuûa baøi toaùn? Caùch giaûi. 1. Kieåm tra caùc vectô coù phaûi laø P.A hay khoâng? 2. Vieát baøi toaùn ñoái ngaãu, 3. Kieåm tra caùc P.A coù phaûi laø P.A.T.Ö.?

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

Deã daøng kieåm tra vectô X*= (0, 2, 1) thoûa caùc raøng buoäc cuûa baøi toaùn ñoái ngaãu.

Hôn nöõa, fD(X*)= f(X)= 8 neân X laø P.A.T.Ö. cuûa baøi toaùn goác. x1 ≥ 0 vaø y1 + y2 – 3y3 ≥ -1 ≥ 2 x2 ≥ 0 vaø 3y1 + y2 y3 ≥ 1 x3 ≥ 0 vaø x4 ≥ 0 vaø – y1 + y3 ≥ 0 x1 + 3x2 x1 + x2  Do Y = (2, 1, 8, 0) laø P.A cuûa baøi toaùn goác vaø (1) (2) (3) (4) (5) (6) (7) – x4 ≤ 5 vaø y1 ≥ 0 ≤ 3 vaø y2 ≥ 0 + x4 ≤ 2 vaø y3 ≥ 0 + x3 f(X) = f(Y)= 8 neân Y cuõng laø P.A.T.Ö.

 Vôùi T = (1, 2, 1, 2), ta coù f(T)= 4  fmax = 8 Vaäy T khoâng phaûi laø P.A.T.Ö. maø T chæ laø phöông aùn cuûa baøi toaùn.

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

f x





min



-3x1 3. Kieåm tra X, Y, T laø P.A.T.Ö  Giaû söû X = (3, 0, 11, 0) laø P.A.T.Ö cuûa baøi toaùn. Töø (1): x1 = 3 > 0  y1 + y2 – 3y3 = -1 Töø (3): x3=11 > 0  y3 = 1 Töø (5): 3 + 0 + 0 + 0 = 3 < 5  y1 = 0 Giaûi heä phöông trình, ta ñöôïc X*= (0, 2, 1).

x 1

x 2 2 1 1

 ( ) 6 y



max

y 1

  y 3

3 0 2



1 2 5

D 2 3 1

x 1 x 2 x 3

y 1

    

    

6     2     5  

    

    

1 0 2







4 y 5



max

1,3   ( ) 6 y f

0 Baøi toaùn ñoái ngaãu

y 1

  y 3

1 2 5

2 y 3

    

    

    

    

    

    

    

    





1,6

D 2 3 1 1 0 2

y 1 y



10 8

1 2 5

2 y 3

    

    

    

    

    

    

Ví duï 2.9. Giaûi baøi toaùn QHTT  x ( ) 10 3 Ñöa baøi toaùn veà daïng chính taéc baèng caùch theâm 3 aån phuï y4 ≥ 0, y5 ≥ 0, y6 ≥ 0





1,3

Ví duï 2.10

Ta thaáy baøi toaùn cuõng coù daïng chuaån. Söû duïng thuaät giaûi ñôn hình

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

0 4y

0 5y

 1

2 2

 1

1

HEÄ P.A AÅN HEÄ P.A AÅN

3 1 7

3 3 4

0 6y 0 0 1 0

5 2 3y 2y 2 0 1 5 0 5 0

6 1y 1 0 0 0

SOÁ 6 5 0 SOÁ 0 0 0

GHI CHUÙ

0 4y 1 0 0 0 1

2 2y 3 0 2 2 3

5 3y 1 2 5 5 1

2 3 

2  1

 1

6 0 0



  x opt

x opt

2 3

0 6y 0 0 1 0 0 0 1 0

2 7

0 5y 0 1 0 0 0 1 0 0

6 1y 2 1 1 6 1 0 0 0

2 2

C.B 1y 4 3y 2 6y 5   f x 34

3 0 0 0

x     1 4  x     2 5     x  3

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU GHI CHUÙ. Chuùng ta cuõng coù theå söû duïng quy taéc sau ñaây ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu: y 1

c 1 c 2

C.B 4y 10 5y 8 6y 19   f x 0 1y 5 5y 3 6y 14   f x 30 Baøi toaùn coù P.A.T.Ö yopt=(4, 0, 2) vaø f(yopt)= 34. P.A.T.Ö cuûa baøi toaùn goác laø   0 x  b  1 4    0 x  b  2 5     x b  3 6

y opt

   1    2 

   m

c m

       

+ 2y3 ≤ 8 y1 y1 + 2y2 + 5y3 ≤ 19

(1) (2) (3) (4) (5) (6)

Caùch 2: duøng ñònh lyù ñoái ngaãu x1 ≥ 0 vaø 2y1 + 3y2 + y3 ≤ 10 x2 ≥ 0 vaø x3 ≥ 0 vaø 2x1 + x2 + x3 ≥ 6 vaø y1 ≥ 0 + 2x3 ≥ 2 vaø y2 ≥ 0 3x1 x1 + 2x2+ 5x3 ≥ 5 vaø y3 ≥ 0 Ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu yopt= (4,0,2) Töø (3): 4 +20 + 52 = 14 < 19  x3 = 0. Töø (4): y1 = 4 > 0  2x1 + x2 + x3 = 6 Töø (6): y3= 2 > 0  x1 + 2x2 + 5x3 = 5 Giaûi heä phöông trình, ta coù PA.T.Ö cuûa baøi toaùn goác laø xopt = (7/3, 4/3, 0) vaø f(xopt) = 34. Vôùi caùc aån cô baûn xj (j = 1, 2, ...…, m) trong P.A.C.B ñaàu tieân laäp thaønh ma traän ñôn vò caáp m töông öùng vôùi caùc j trong baûng cuoái cuøng. Trong Ví duï 2.9, aån cô baûn ñaàu tieân cuûa baøi toaùn ñoái ngaãu laø y4, y5 vaø y6 thì P.A.T.Ö cuûa baøi toaùn goác (ñoái ngaãu cuûa baøi toaùn ñoái ngaãu) laø Xopt = (7/3, 4/3, 0) vaø f(Xopt) = 34.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU

Ñuùng

bi ≥ 0,i?

j ≤ 0,j?

LAÄP BAÛNG ÑÔN HÌNH ÑOÁI NGAÃU

Sai

Ñuùng

P.A.T.Ö

aij  0,j? Sai

XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI Aån ra : 

x i

BAØI TOAÙN KHOÂNG COÙ P.A.T.Ö

Min b i  0i b



Aån vaøo :



Min a 0ij a ij

KEÁT THUÙC THUAÄT GIAÛI THUAÄT GIAÛI ÑÔN HÌNH

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU  Do Lemke G.E ñeà xuaát naêm 1954. Ñaây laø thuaät giaûi ñôn hình ñöôïc aùp duïng vaøo baøi toaùn ñoái ngaãu nhöng ñeå tìm P.A.T.Ö cho baøi toaùn goác.  Thuaät giaûi ñôn hình ñoái ngaãu xuaát phaùt töø moät “phöông aùn giaû” thoûa caùc raøng buoäc chính cuûa baøi toaùn (nghieäm ñuùng Ax = b) nhöng khoâng thoaû ñieàu kieän raøng buoäc veà daáu (x  0), nghóa laø baûng ñôn hình ñaàu tieân khoâng coù phaàn töû döông trong doøng muïc tieâu (doøng cuoái) nhöng laïi coù phaàn töû aâm trong coät phöông aùn.  Thuaät giaûi naøy thöôøng ñöôïc aùp duïng khi chöa bieát P.A.C.B naøo cuûa baøi toaùn goác nhöng laïi coù saün moät P.A.C.B cuûa baøi toaùn ñoái ngaãu.

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU

BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP LAØ HÖÕU HAÏN

Heä soá AÅn C.B

P.A 10 x1 –2 –6 8 x2 –1 19 x3 –1 0 x4 1 0 x5 0 0 x6 0 0

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï 2.10. Giaûi baøi toaùn QHTT trong Ví duï 2.9 baèng thuaät giaûi ñôn hình ñoái ngaãu. Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù baøi toaùn daïng chính taéc nhö sau 

 ( ) 10

min

f x





0 –2 0 –2 –3 1 0 0

x 2

x 3





–2 –5 0 –5 –1 0 1 0

x 4

x 2

 2  3

  2



  6   2

x 5

0 0 –10 –8 –19 0 0



 2

 5



  5

x 1 x 1 x 1 x 1

x 2

x 3 x 3 x 3

x 6

3 1 ½ ½ –½ 0 0 10





1, 6

7 0 3/2 –½ –3/2 1 0 0

        

–2 0 –3/2 9/2 –½ 0 1 0

30 0 –3 –14 –5 0 0 x4 x5 x6 f(x) x1 x5 x6 f(x) Xuaát phaùt töø phöông aùn giaû X = (0,0,0,–6,–2,–5). Ta coù baûng ñôn hình ñoái ngaãu nhö sau

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

y 1

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU GHI CHUÙ. Ñoái vôùi thuaät giaûi ñôn hình ñoái ngaãu, ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu Yopt, ta coù    bieåu thöùc sau

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU 0 8 Heä soá x6 x2 1/3 0

AÅn C.B

c 1 c 2

y 2

P.A 10 x1 1 0 x4 –2/3 19 x3 2 0 x5 0 7/3 10

y opt

   

5 0 0 4 –2 1 1 0

c m

       

4/3 0 1 1/3 0 –2/3 8 –3

   Trong Ví duï 2.10, aån cô baûn ñaàu tieân cuûa baøi toaùn ñoái ngaãu laø x4, x5 vaø x6 thì

34 0 0 –4 0 –2 x1 x5 x3 f(x) –23



     

    

y opt

  

     ( 4) 0 4 0 0 0      ( 2) 0 2

y 1 y 2 y 3

c 4 c 5 c 6

y 1 y y 3

    

Vaäy, P.A.T.Ö cuûa baøi toaùn laø xopt = (7/3, 4/3, 0) vaø f(xopt) = 34.

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU

P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Yopt = (4, 0, 2) vaø f*(Yopt) = 34.

f x ( )









Min

x 3

x 4

  x 5

x 2 

x 1 x 1

Heä soá AÅn C.B Ví duï 2.11. Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây

2 4



x 2 x 2

x 4



x 6

 2 

2     4



     

2 4 2 6

x 2

x 3 x 3 x 3

x 5 x 5 x 5 x 5

x 7





1, 7

         

2 –1 0 0

THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU P.A 2 –4 1 –1 2 0 0 x1 x2 x3 x4 x5 x6 x7 –2 1 –2 0 0 –2 0 0 x1 4 –4 0 1 1 –1 0 0 x4 0 2 0 –1 1 0 0 2 x6 0 x7 1 0 4 0 1 1 6 0 –4 –2 0 –5 0 0 f(x) 0 1 –10 –2 –2 0 0 0 6 x1 0 –4 –1 –1 1 0 0 4 x5 0 –4 1 –1 0 1 0 6 x6 x7 –10 0 17 5 4 0 0 1 f(x) 20 0 –24 –7 –5 0 0 0

2 –1 0 0 Do a4j  0, j = 1,..., 7 neân baøi toaùn treân khoâng coù P.A.T.Ö. Xuaát phaùt töø phöông aùn giaû X = (–2,0,0,–4,0,2,6). Ta coù baûng ñôn hình ñoái ngaãu

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT

1. TÌM PHÖÔNG AÙN TOÁI ÖU MÔÙI KHI COÙ THEÂM RAØNG BUOÄC VAØO BAØI TOAÙN (XEM)

f x

 ( ) 15





Min

2. TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ

x 2 4



x 3  2



160



 3



140

x 1 x 1 x 1

x 2 x 2

x 3 x 3

(XEM)

PHÖÔNG TRÌNH TUYEÁN TÍNH BAÈNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG





1,3

      

3. YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN QUY

(XEM)

HOAÏCH TUYEÁN TÍNH ÑOÁI NGAÃU

Ví duï 2.12. a) Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi toaùn quy hoaïch tuyeán tính sau ñaây

MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU

b) Neáu theâm moät raøng buoäc nöõa x1 + x2 + x3  60 vaøo baøi toaùn treân, tìm phöông aùn toái öu cuûa baøi toaùn môùi.

Heä Soá AÅn C.B x2

MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù baøi toaùn daïng chính taéc nhö sau

f x

 ( ) 15





Min

 3

x 2  4

x 3  2



 

160

x 4

0 0 0 x4 1 0 0



 2

 3

 

140



x 1 x 1 x 1

x 2 x 2

x 3 x 3

x 5





1,5

      

12 0

12 10 0 P.A 15 12 10 x5 x3 x1 0 x4 –160 –3 –4 –2 x5 –140 –1 –2 –3 1 0 –15 –12 –10 0 f(x) 40 ¾ 1 ½ –¼ 0 x2 –½ 1 –60 ½ 0 –2 x5 –4 0 –3 0 f(x) 480 –6 0 –3/8 ¼ 25 7/8 1 x2 1 ¼ –½ –¼ 0 30 x3 –2 –2 0 0 f(x) 600 –7 a) Xuaát phaùt töø phöông aùn giaû X = (0, 0, 0, –160, –140. Ta coù baûng ñôn hình ñoái ngaãu P.A.T.Ö laø xopt = (0, 25, 30) vaø f(xopt) = 600.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU

MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT

Heä AÅn P.A 15 12 10 0 0 0

soá C.B

25 12 x1 7/8 x2 1 x3 0 x5 x4 –3/8 ¼ x6 0

30 10 –¼ 0 1 ¼ –½ 0

–60 0 –1 –1 –1 0 0 1

600 x2 x3 x6 f(x) –7 0 0 –2 –2 0

25 12 7/8 1 0 –3/8 ¼ 0

30 10 –¼ 0 1 ¼ –½ 0

–5 0 0 –3/8 0 –1/8 –¼ 1

MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU

x2 x3 x6 f(x) 0 0 600 –7 –2 –2 0 b) Do xopt = (0, 25, 30) khoâng thoûa raøng buoäc x1 + x2 + x3  60 neân xopt khoâng phaûi laø phöông aùn cuûa baøi toaùn môùi. Ñeå xöû lyù raøng buoäc môùi naøy, ta ñöa raøng buoäc baát ñaúng thöùc veà raøng buoäc ñaúng thöùc baèng caùch theâm aån phuï x6  0, ta ñöôïc –x1 – x2 – x3 + x6 = –60. Söû duïng baûng cuoái cuøng trong caâu a) vaø ñöa raøng buoäc môùi –x1 – x2 – x3 + x6 = –60 vaøo baûng treân. Löu yù aån x6 laø aån cô baûn trong baøi toaùn môùi, coøn x4 vaø x5 laø aån cô baûn trong baøi toaùn cuõ neân trong ma traän heä soá cuûa baøi toaùn môùi ta coäng doøng 1 vaø doøng 2 vaøo doøng 3 ñeå vectô coät öùng vôùi x4 vaø x5 laø caùc vectô ñôn vò.

P.A Heä soá AÅn C.B

12 20 15 x1 ½ 12 10 x3 x2 0 1 0 0 x4 x5 –½ 0 0 x6 1

min



TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH Tìm nghieäm khoâng aâm cuûa heä phöông trình tuyeán tính AX = b, X  0 (1), trong ñoù A laø ma traän mn, bm coù theå quy veà giaûi baøi toaùn quy hoaïch tuyeán tính

g j

   f x M x 

 1

10 40 ½ 0 1 ½ 0 –2

 AX X



0 20 3/2 0 0 ½ 1 –4

  2 0







x2 x3 x5 f(x) 0 0 –1 0 640 –8 –4

opt = (0, 20, 40) vaø f(x/

opt) = 640.

opt), opt = 0, j thì xopt laø nghieäm cuûa baøi toaùn j  0 thì baøi toaùn (1)

X  Baøi toaùn (2) luoân luoân coù P.A.T.Ö vì (0,b) laø moät P.A vaø haøm muïc tieâu bò chaën [f(x)  0].  Giaû söû P.A.T.Ö cuûa baøi toaùn treân laø (xopt, xg neáu xg (1). Ngöôïc laïi neáu toàn taïi xg voâ nghieäm.

P.A.T.Ö laø x/

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Xeùt baøi toaùn goác laø baøi toaùn khaåu phaàn thöùc aên





Thöùc aên

 2 

 

 

4 2

9 4

TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH Ví duï 2.1.Tìm nghieäm khoâng aâm cuûa heä phöông trình tuyeán tính  3 x 2 x 2 x 2

x 3 x 3 x 3

x 1 x 1 x 1

    

Min



( )

1 2 ... j ... n Chaát dinh döôõng (%)

x 5  3







x 4



x 5

2  

4   2



 

9 4

  f x M x 4 x 1 x 1 x 1

x 2 x 2 x 2

x 3 x 3 x 3

x 6





1, 6

        

Ta coù theå quy baøi toaùn treân veà baøi toaùn QHTT    x 6

Möùc dinh döôõng toái thieåu b1 b2 ... bi ... bm

YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU

... a1n a11 a12 ... a1j ... a2n a21 a22 ... a2j ... ... ... ... ... ... ... ain ... aij ai1 ai2 ... ... ... ... ... ... am1 am2 ... amj ... amn ... cn ... cj c1 c2 1 2 ... i ... m Giaù moät ñôn vò thöùc aên Giaûi baøi toaùn treân, ta ñöôïc P.A.T.Ư laø (xopt, xg opt) = (3, 1, 2, 0, 0, 0). Vaäy nghieäm khoâng aâm cuûa heä phöông trình tuyeán tính treân laø x = (3, 1, 2).



min









 f x



c x 2 2

c x n n

c x 1 1









a x 2 2 i

a x in n

a x 1 1 i

b i



YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Goïi xj (j = 1, 2, ..., n) laø soá ñôn vò thöùc aên trong moãi böûa, ta coù moâ hình baøi toaùn QHTT nhö sau      x  j Baøi toaùn ñoái ngaãu

laø giaù baùn moät vieân thuoác boå coù chöùa









max





b y 2

b y 1 1

b y m m









a y 1 1 j

a y mj m

a y 2 j





y i

     Chaát dinh döôõng thay theá: nhaø saûn xuaát thuoác boå töông öùng vôùi caùc chaát dinh döôõng treân.

leäch buø yeáu,

Goïi yi chaát dinh döôõng i (i = 1, 2, ..., m). Ngöôøi chaên nuoâi seõ phaûi löïa choïn:  Mua thuoác boå, neáu a1jy1 + a2jy2 +... + anjyn < cj. Vì giaù thuoác boå reû hôn vaø luùc naøy xj = 0 (ñònh lyù ñoä leäch buø yeáu).  Mua thöùc aên, theo ñònh lyù ñoä neáu yi > 0 thì ai1x1 + ai2x2 + … + ainxn = bi, Nghóa laø, neáu giaù moät vieân thuoác boå khaù cao thì ngöôøi chaên nuoâi seõ mua caùc loaïi thöùc aên sao cho thoaû nhu caàu toái thieåu cuûa chaát dinh döôõng. Vaäy, khi phaân tích caëp baøi toaùn ñoái ngaãu nhau chính laø phaân tích tính T.Ö cuûa töøng baøi toaùn.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

BAØI TAÄP CHÖÔNG 2



f x ( )

 4

 3

 2



min

LAÄP BAØI TOAÙN ÑOÁI NGAÃU

 2





 1

1.a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT

[1b]

2 

  5

 3 

  3

 

8 4

x 2 x 2 x 2 x 2



x 3 x 3 x 3 x 3 0,



x 4 x 4 x 4 x 4 0



x 1

x 3

x 4

      

[2] [1a] Th.s Nguyeãn Coâng Trí SÖÛ DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU

y ( )



 8

 4



max

[4]

[3]

[6]

 2





 2



 5



 4

 3 

  3

 

 3 2

y 1 y 1 y 1 y 1 y 1

[7a]

[7b]

2 y 2 y 2 y 2 y 2 0,



y 3 y 3 y 3 y 3 y 3 0



y 3

x 1 x 1 x 1 x 1 0, Baøi toaùn ñoái ngaãu  Df          

BAØI TAÄP CHÖÔNG 2



f x ( )



x 1

3    2

 5 2  

 4 2  

  



 

x 2 x 2



x 1 x 1 x 1 x 1

2. Chöùng minh baøi toaùn QHTT sau ñaây truøng vôùi baøi toaùn ñoái ngaãu cuûa noù (Baøi toaùn töï ñoái ngaãu).

x 4 x 4 x 4 x  4  0

x 3 x 3 x 3 x 3 0,

2  

 

x 4

x 2

x 3

      

  x 3   x 3   x 3 

min 1  1   1



y ( )

x 1 x 1 0,

 

 x 2  0



x 1

x 2

x 3

      

 8 

 

min 2

 9 

 2

2  

 



3 4

  2





y 2 y 2 y 2 y 2 y 2

2 

y 1 y 1 y 1 y 1 y 1 0,

y 3 y 3 y 3 y 3 y  3  0

y 1

y 3

1.b) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT x max 2 x 10 2 x 8 2 x 2 0,

Baøi toaùn ñoái ngaãu          

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

BAØI TAÄP CHÖÔNG 2





min

y ( )

y   3

y 1





f x  ( ) 2

max

x 1

x   4



 5

y 1 y 3 1

2 





x 1

4 x





4 

  

 2

4 1 1

y 2

y y 3 y 3



 x

2 x











1, 4

3. Cho baøi toaùn QHTT sau ñaây:

a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân.

BAØI TAÄP CHÖÔNG 2





f x  ( ) 5

min

b) Giaûi baøi toaùn goác, suy ra lôøi giaûi cuûa baøi a) Baøi toaùn ñoái ngaãu b) Giaûi baøi toaùn goác, ta ñöôïc P.A.T.Ö laø xopt = (1, 0, 3/4, 0), fmax= 11/4 Caùc caëp ñoái ngaãu y 1 x1  0 vaø y1  2 (1) y x2  0 vaø 3y1 – 5y2 + y3  4 (2) x3  0 vaø + 4y3  1 (3) x4  0 vaø y1 – 2y2 + y3  1 (4) -5x2 – 2x4 ≤ 3 vaø y2  0 (5) Giaûi hpt (1), (3) vaø (5), ta ñöôïc toaùn ñoái ngaãu. yopt = (2, 0, 1/4) vaø fD(yopt)= 11/4

x 2

x 3



f x  ( ) 12

min







 3

x 2

2 





5. Cho baøi toaùn QHTT x  1

 2

x   5 x  4 x 4

 

4 



  2

 4   1

4 x 3 x 3 x 3

x 5 x 5 x 5

x 1 x 1 x 1

x 2



2 





2,5





x 1 x 1 x 1

4. Cho baøi toaùn QHTT sau ñaây: x x   3 1 2





1,3

a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân.

a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. b) Phaân tích caùc tính chaát (P.A.C.B suy bieán hay khoâng suy bieán) cuûa vectô X = (0, 1, 0, 2, 0).

b) Giaûi baøi toaùn ñoái ngaãu, suy ra lôøi giaûi cuûa

baøi toaùn goác. c) Cho bieát X laø P.A.T.Ö cuûa baøi toaùn goác vaø f(X) = 5. Tìm P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu.

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

BAØI TAÄP CHÖÔNG 2





y ( )

max

y   3

a) Baøi toaùn ñoái ngaãu

f x



max

Df b) Kieåm tra tröïc tieáp, ta





y 2  4

x 3

  x 4

y 2

x 2  3







x 4

6. Cho baøi toaùn QHTT   ( ) 3



3 

 

  9  15

y 3 y 3 y 3

thaáy X = (0, 1, 0, 2, 0) laø P.A

2 2

2   2

 3  3



 

60 32

x 1 x 1 x 1 x 1

x 2 x 2 x 2

x 3 x 3 x 3

x 4



vaø X thoûa 5 raøng buoäc chaët,



1, 4

 2 

 

7 6

 2

y 2 y 2 y 2

deã daøng kieåm tra hpt raøng

 Cho caùc vectô:





y 1 y 1 y 1 y 1 y 1 y 1 0,

y 3 0

y 1

y 3

buoäc coù haïng khaùc 5,

neân X khoâng laø P.A.C.B.

X = (-1, 2, 3, 4); Y = (0, 2, 1, 3); Z = (0, 0, 0, 8), T = (14, 0, 0, 1); S = (18, 2, 0, 0)

BAØI TAÄP CHÖÔNG 2

c) Chæ ra 6 caëp ñoái ngaãu, töø ñoù aùp duïng ñònh lyù ñoái ngaãu, ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Yopt = [(y3 – 9)/3, (y3 + 12)/6, y3], vôùi y3 ≥ 0, y1 ≤ 0. Trong caùc vectô treân, vectô naøo laø phöông aùn toái öu cuûa baøi toaùn? Haõy giaûi thích.

1. Kieåm tra tröïc tieáp X, Y khoâng phaûi laø phöông aùn. Caùc vectô Z, T, S laø caùc phöông aùn vì chuùng thoûa caùc raøng buoäc cuûa baøi toaùn.







y ( )



min

2  3

2   2

y y

3  7

 3





 4



y 3 y 3 y 3 y 3 y 3

 (1)  (2)  (3)  (4)

2 



+ 4y3 = –2

(5)

3. Kieåm tra tính toái öu cuûa caùc phöông aùn  Xeùt phöông aùn Z = (0, 0, 0, 8), giaû söû Z laø P.A.T.Ö. cuûa baøi toaùn goác, ta coù f(Z) = –16. Töø (4): z4 = 8  2 y1 Töø (5): 2x1 – 3x2 – x3 + 2x4 = 16 < 30  y1 = 0 = 0 < 60  y2 = 0 Töø (6): 2x1 – 2x2 + 3x3 P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu seõ laø Z*= (0, 0,–½), nhöng Z* khoâng thoûa raøng buoäc cuûa baøi toaùn ñoái ngaãu neân Z* khoâng theå laø P.A.T.Ö. Vaäy, Z khoâng theå laø P.A.T.Ö. cuûa baøi toaùn goác.  Töông töï, giaû söû T = (14, 0, 0, 1) laø P.A.T.Ö. cuûa baøi toaùn goác ta coù f(T) = 40. (6) 2. Baøi toaùn ñoái ngaãu y Df 30  Caùc caëp raøng buoäc ñoái ngaãu 1  y x1 ≥ 0 vaø 2y1 + 2y2 + 2y3 ≥ 3  1  y  x2 ≥ 0 vaø –3y1 – 2y2 – 2y3 ≥ –7 1  y  x3 ≥ 0 vaø – y1 + 3y2 – 3y3 ≥ 1 1  y 1 x4 ≥ 0 vaø 2 y1 + 4y3 ≥ –2  y y 0 0,  1 2x1 – 3x2 – x3 + 2x4 ≤ 30 vaø y1 ≥ 0 ≤ 60 vaø y2 ≥ 0 2x1 – 2x2 + 3x3

ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2

BAØI TAÄP CHÖÔNG 2

f x ( )







 2



min



 2





 2







7. a) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, töø ñoù suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu







x 1 x 1 x 1 x 1 0,



x 2 x 2 x 2 x 2 0,

x 3 x 3 x 3 x 3 0,



x 4 x 4 x 4 x 4 0



x 3

x 4

x 1

x 2

      

Töø (1): t1 = 14  2y1 + 2y2 + 2y3 = 3 Töø (4): t4 = 1  2 y1 + 4y3 = –2 = 28 < 60  y2 = 0 Töø (6): 2x1 – 2x2 + 3x3 Giaûi heä phöông trình treân, ta coù P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu seõ laø T*= (4, 0,–5/2).

Deã daøng kieåm tra T* thoûa caùc raøng buoäc cuûa baøi toaùn ñoái ngaãu neân T* laø P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu. Hôn nöõa, fD(T*) = f(T) = 40 Vaäy, T laø P.A.T.Ö. cuûa baøi toaùn goác.

BAØI TAÄP CHÖÔNG 2

7. b) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, töø ñoù

suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu

f x ( )





 6

 3



max

x 3

x 4