Bài toán đối ngẫu

TThhss. .NgNguuyyeeãnãn CCooânângg TrTrí

Copyright 2001

Ths. Nguye

ã

n Coâng Trí

Copyright 2001

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

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

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

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

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

NGAÃU TRONG BAØI TOAÙN QHTT (Xem)

5. BAØI TAÄP (Xem)

BAØI TOAÙN QUY HOAÏCH

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

CHÖÔNG 2

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

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.

Ñ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ù.

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á.

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

Xeùt baøi toaùn QHTT (P) döôùi daïng chính taéc

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 ctx

0

.

Goï

ïi x = (x1

, x2

,... , xn

)

n

, vôù

ùi x 0 sao cho

Ax b 0

Baøi toaùn töông ñöông:

THAØNH LAÄ

ÄP BAØI TOAÙ

ÙN ÑOÁ

ÁI NGAÃU

( ) min

0.

t

P

f x c x

P Ax b I

x

( , ) min

0

.

t t

m

L x y c x y b Ax

P x II

y R

Goïi g(y) laø haøm muïc tieâu cuûa baøi toaùn (II), ta coù

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.

Ta tìm caän döôùi lôùn nhaát Max{g(y)}, thaät vaäy

g(y) = min{ctx + yt(b Ax)}, vôùi x 0.

= min{ctx + ytb y

tAx}, vôùi x 0.

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

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

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

Xeùt

Vaäy ta ñöôïc

g(y) = ytb

Suy ra baøi toaùn ñoái ngaã

ãu coù daïng

Hay baøi toaùn töông ñöông

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

t

t

t x 0

0 c 0

min c

c 0

t

t

t

khi y A

y A x

khi y A

( ) max ( ) max

0

. .

t t

t t t t

m m

g y y b g y y b

D c y A y A c

y R y R

( ) max

.

t

t

m

g y y b

D A y c

y R

Ví duï 2.1.

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

ãu cuûa baøi toaùn QHTT sau ñaây

laø baøi toaùn

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

1 4 5

1 3 5

2 5

234

( ) 2 8 6 min

2 4

2 4

2 3 13

0 1,5 j

f x x x x

x x x

x x

x x x

x j

1 2 3

1

2 3

1 3

3

1 2

( ) 4 4 13 max

2 2

2 0

2 0

3 8

6

D

f y y y y

y

y y

y y

y

y y

›ÿJL“Ÿ ÓÊ fiflH× Ã—flG“ O—_× “Ÿfl]À

£££££££££££££££££££££££££££££££££££££££££££££££ ££££££ £££££££

ø­Ú “¹´ßª=² ›±>²¹ ÃÆ3

££££££££££££££££££££££££££££££

¸¨¨°ÊÒÒ²½¨Æ·Ú½±Ú½½

Nguyeãn Coâng Trí

PDF created with pdfFactory Pro trial version www.pdffactory.com