Bài toán vận tải cân bằng thu phát

1. Baøi toaùn vaän taûi caân baèng thu phaùt

1.1 Khaùi nieäm

1.1.1 Moâ hình thöïc teá

Moät doanh nghieäp coù 30 taán haøng trong kho q.4

vaø 50 taán haøng trong kho Taân Bình, muoán chôû 12

taán cöûa haøng q.1, 28 taán ra q.3, 40 taán ra Taân

Bình. Chi phí vaän chuyeån (chuïc ngaøn/taán haøng):

Cöûa haøng

Kho

q.1 q.3 q.TB

q.4 4 6 9

q.TB 7 5 1

Vaän chuyeån sao cho toång chi phí thaáp nhaát?

Coù 2 kho vaø 3 cöûa haøng. Goïi xij laø soá taán haøng chôû

töø kho i sang cöûa haøng j. xij ≥ 0 (i 1, 2; j 1, 3) = = .

Toång chí phí vaän chuyeån (yeâu caàu cöïc tieåu):

f(X) = 4x11 + 6x12 + 9x13 + 7x21 + 5x22 + x23 → min

Do toång soá haøng trong kho (80) baèng toång soá haøng

caùc cöûa haøng caàn nhaän (Caân baèng thu phaùt -

CBTP) neân moãi kho phaûi phaùt heát vaø moãi cöûa

haøng phaûi nhaän ñuû:

Kho 1 phaùt heát haøng: x11 + x12 + x13 = 30

Kho 2 phaùt heát haøng: x21 + x22 + x23 = 50

Cöûa haøng 1 nhaän ñuû haøng: x11 + x21 = 12

Cöûa haøng 2 nhaän ñuû haøng: x12 + x22 = 28

Cöûa haøng 3 nhaän ñuû haøng: x13 + x23 = 40

Vaäy ta coù baøi toaùn QHTT sau:

f(X) = 4x11 + 6x12 + 9x13 + 7x21 + 5x22 + x23 → min

x11 + x12 + x13 = 30

x21 + x22 + x23 = 50

x11 + x21 = 12

x12 + x22 = 28

x13 + x23 = 40



















xij ≥ 0 (i 1, 2; j 1, 3) = =

1.1.2 Toång quaùt hoaù

Coù m kho haøng, kho i coù ai ñôn vò haøng.

Coù n cöûa haøng, haøng j caàn nhaän bj vò haøng.