Bài toán vận tải

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

Copyright 2001

Ths. Nguye

ã

n Coâng Trí

Copyright 2001

BAØI TOAÙN VAÄN TAÛI

1. BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT (Xem)

2. CAÙC TÍNH CHAÁT VAØ TIEÂU CHUAÅN TOÁI ÖU CUÛA

BAØI TOAÙN VAÄN TAÛI (Xem)

3. CAÙC PHÖÔNG PHAPÙ TÌM PHÖÔNG AÙN CÖÏC

BIEÂN ÑAÀU TIEÂN CUÛA BAØI TOAÙN VAÄN TAÛI (Xem)

4. THUAÄT GIAÛI THEÁ VÒ CHO BAØI TOAÙN VAÄN TAÛI (Xem)

5. CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI (Xem)

6. BAØI TAÄP (Xem)

CHÖÔNG 3

NOÄI DUNG BAØI TOAÙN VAÄN TAÛI

Giaû söû caàn vaän chuyeån moät loaïi haøng hoùa (xi

maêng, saét theùp, ...) t öø m ñieåm cung caáp (traïm

phaùt), kyù hieäu laø A1

, A2

, ..., Am ñeán n ñieåm tieâu

thuï (traïm thu), kyù hieäu laø B1

, B2

, ..., Bn

, bieát raèng

(1) Soá löôïng haøng coù ôû caùc traïm phaùt A1

, A2

, ...,

Am laàn löôït laø a1

, a2

,..., am

(2) Soá löôïng haøng caàn ôû caùc traïm thu B1

, B2

, ...,

Bn

laàn löôït laø b1

, b2

,..., bn

.

(3) Chi phí vaän chuyeån moät ñôn vò haøng hoùa töø

traïm phaùt Ai ñeán traïm thu Bj

laø cij.

Haõy laäp keá hoaïch vaän taûi haøng hoùa sao cho

toång chi phí vaän taûi thaáp nhaát vaø thoûa maõ

õn yeâ

âu

caàu thu phaùt.

BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT

MOÂ HÌNH BAØI TOAÙ

ÙN VAÄ

ÄN TAÛI

Ñaët xij laø

ø soá

á löôïng haøng caà

àn vaän chuyeå

ån töø traïm

phaù

ùt Ai ñeá

án traïm thu Bj

.

Ta coù toång chi phí vaän taûi:

(1) Traïm phaùt, phaùt heát haøng:

(2) Traïm thu, thu ñuû haøng:

(3) Yeâu caàu traïm phaùt, traïm thu ñöôïc thoûa

(ñk caân baèng thu phaùt).

BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT

1 1

min

m n

ij ij

i j

Z c x

1

, 1,

n

ij i

j

x a i m

1

, 1,

m

ij j

i

x b j n

1 1

m n

i j

i j

a b

Vaäy, moâ h ình toaùn cuûa baøi toaùn vaän taûi (BTVT)

daïng toång quaùt nhö sau:

Tìm {xij} sao cho:

BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT

1 1

1

1

1 1

min

, 1,

, 1,

0; 0; 0; 0;

m n

ij ij

i j

n

ij i

j

m

ij j

i

m n

ij ij i j i j

i j

Z c x

x a i m

x b j n

x c a b a b

BAØI TOAÙN VAÄN TAÛI DÖÔÙI DAÏNG BAØI TOAÙN QHTT

khai trieån BTVT vaø xeáp heä raøng buoäc döôùi daïng

heä m + n phöông trình cuûa m n bieán nhö sau

Kyù hieäu Am+n,m n ma traän heä soá cuûa hpt treân.

XT = (x11 x12 ... x1n x21 x22 ... x2n ... xm1 xm2 ... xmn) laø

vectô coät goàm m n thaønh phaàn; C = (c11 c12

... c1n c21 c22 ... c2n cm1 cm2 ... cmn) laø vectô doøng

goàm m n thaønh phaàn; bT = (a1 a2

... am b1 b2

... bn

)

laø vectô coät goàm m+ n thaønh phaàn.

BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT

11 12 1 1

21 22 2 2

1 2

11 21 1 1

12 22 2 2

1 2

n

n

m m mn m

m

m

n n mn n

x x x a

x x x a

x x x a

x x x b

x x x b

x x x b

BTVT vieát döôùi daïng vectô vaø ma traän nhö sau

Moät vectô X thoûa (*) vaø (**) goïi laø phöông aùn.

Moät P.A ñaït cöïc tieåu thì goïi laø P.A.T.Ö cuûa BTVT.

Moät phöông aùn X ñöôïc goïi laø P.A.C.B khi caùc

vectô coät Aj cuûa ma traän heä soá A öùng vôùi caùc

thaønh phaàn xij > 0 laø ñoäc laäp tuyeán tính.

Moät P.A.C.B cuûa BTVT coù nhieàu nhaát laø m + n

1 thaønh phaàn döông. Neáu moät P.A.C.B cuûa BTVT

coù ñuùng m + n 1 thaønh phaàn döông thì ñöôïc

goïi laø khoâ

âng suy bieán. Ngöôïc laïi, ñöôïc goïi laø

phöông aùn cöïc bieân suy bieán.

BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT

min

*

0 **

T

z C X

AX b

X

›ÿJL“Ÿ ÌÊ fiflH× Ã—flG“ fl\“ ÃflE×

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

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

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

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

Nguyeãn Coâng Trí

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