Bài giảng quy hoach tuyến tính

1

 Bài toán v

ận t

ải

3.1 Bài toán v

ận t

ải

Ta g

ọi vect

ơ

C

ần v

ận chuy

ển hàng hoá từ

m kho (

đ

i

ểm phát)

Pi,

i=1,2,…,

m đến

n n

ơi tiêu th

ụ (

đ

i

ểm thu)

Tj,

j=1,2,…,

n.

Lượng hàng có

ở m

ỗi kho

Pi là

ai,

i=1,2,…,

m. Lượng hàng

c

ần

ở m

ỗi n

ơi tiêu th

ụ

Tj là

bj,

j=1,2,…,

n. Chi phí v

ận

chuy

ển 1 đơn v

ị hàng từ kho

Pi đến n

ơi tiêu th

ụ

Tj là

cij,

i=1,2,…

m,

j=1,2,…,

n. Cho bi

ết t

ổng lượng hàng

ở các kho

b

ằng t

ổng lượng hàng c

ần tiêu th

ụ.

Hãy l

ập k

ế ho

ạch v

ận chuy

ển hàng hoá sao cho t

ổng

chi phí là nh

ỏ nh

ất và đảm b

ảo yêu c

ầu thu phát.

2

 Bài toán v

ận t

ải

G

ọi

xij là lượng hàng c

ần v

ận chuy

ển t

ừ

đ

i

ểm phát

Pi đến

đ

i

ểm thu

Tj,

xij

 0.

T

ổng chi phí v

ận chuy

ển là:

f =

c11

x11 +

c12x12 + … +

cmnxmn hay

f = 

cijxij

Lượng hàng v

ận chuy

ển

đi t

ừ kho

Pi,

i=1,2,…,

m:

xi1 +

xi2 + … +

xin =

ai hay

xij =

ai ,

i=1,2,…,m.

Lượng hàng v

ận chuy

ển đến n

ơi tiêu th

ụ

Tj,

j=1,2,…,

n:

x

1j +

x

2j + … +

xmj =

bj hay

xij =

bj ,

j=1,2,…,n.

Do lượng hàng phát ra b

ằng lượng hàng thu vào nên ta có:



ai =



bj ,

i=1,2,…,

m,

j=1,2,…,

n