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

Bài giảng Bài toán vận tải cung cấp đến người học một số phương pháp giải các bài toán vận tải trong quy hoạch tuyến tính. Mời các bạn cùng tham khảo để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Bài toán vận tải BAØI TOAÙN VAÄN TAÛI 1 Cij D1 Xác ñịnh Xij ñể TC minS1 Các dữ liệu : • Các ñiểm nguồn (Si) D2 và khả năng cung cấp của từng ñiểm nguồn.S2 • Các ñiểm ñích (Dj) và nhu cầu của từng ñiểm D3 ñích.S3 • Chi phí vận chuyển từ ñiểm nguồn i ñến ñiểm ñích j. D4 2 1Ví duï : Moät doanh nghieäp coù ba kho chöùa haøng vôùi khaû naêng cung caáp töøngkho laø 120, 140 vaø 100 saûn phaåm/ngaøy. Giaû söû haøng ngaøy haøng phaûi ñöôïc vaänchuyeån ñeán 4 ñieåm baùn leû vôùi nhu caàu laø 100, 60, 80 vaø 120 saûn phaåm. Tìmphöông aùn vaän chuyeån toái öu (Toång chi phí vaän chuyeån beù nhaát) Bieát raèngchi phí vaän chuyeån moät ñôn vò saûn phaåm giöõa caùc kho vaø ñieåm baùn leû cho ôûbaûng sau : Kho Ñieåm baùn leû Toång cung 1 2 3 4 1 5 7 9 6 120 2 6 7 10 5 140 3 7 6 8 1 100 Toång caàu 100 60 80 120 360 3 CAÙC KYÙ HIEÄUÑeå thuaän tieän cho vieäc thieát laäp moâ hình, ta söû duïng moät soá kyù hieäu sau :m : Soá ñieåm nguoànn : Soá ñieåm ñíchsi : Khaû naêng cung caáp cuûa ñieåm nguoàn thöù i (i = 1, 2, …, m)dj : Nhu caàu nhaän cuûa ñieåm ñích thöù j (j = 1, 2, …, n)xij : Löôïng haøng hoaù chuyeån töø ñieåm nguoàn thöù i ñeán ñieåm ñích thöù j .Cij : Chi phí vaän chuyeån haøng hoaù töø ñieåm nguoàn thöù i ñeán ñieåm ñích thöù j . 4 2 MOÂ HÌNH TOÅNG QUAÙT Ñieåm nguoàn Ñieåm ñích Toång cung 1 2 … n 1 C11 C12 … C1n S1 x11 x12 … x1n 2 C21 C22 … C2n S2 x21 x22 … x2n … … … … … … … … … … m Cm1 Cm2 … Cmn Sm xm1 xm2 … xmn Toång caàu d1 d2 … dn m n Z = ∑ ∑ i= 1 j= 1 xij.cij ⇒ Min n ∑ j= 1 xij = si (i = 1,2,..., m) m ∑ i= 1 xij = dj (j = 1,2,..., n) 5 xij ≥ 0 PHÖÔNG PHAÙP GIAÛI BÖÔÙC 1 : TÌM LÔØI GIAÛI BAN ÑAÀU. BÖÔÙC 2 : CAÛI THIEÄN NGHIEÄM BAN ÑAÀU CHO TÔÙI KHI ÑAÏT ÑÖÔÏC ÑIEÅM TOÁI ÖU.6 3 TÌM LÔØI GIAÛI BAN ÑAÀU 1-PHÖÔNG PHAÙP GOÙC TAÂY BAÉC 2-PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT 3-PHÖÔNG PHAÙP VAM 7 PHÖÔNG PHAÙP GOÙC TAÂY BAÉC (The Northwest Corner Method) Choïn oâ ôû goùc taây baéc ...