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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

179
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 min S1 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 1
Ví duï : Moät doanh nghieäp coù ba kho chöùa haøng vôùi khaû naêng cung caáp töøng kho laø 120, 140 vaø 100 saûn phaåm/ngaøy. Giaû söû haøng ngaøy haøng phaûi ñöôïc vaän chuyeå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ìm phöông aùn vaän chuyeån toái öu (Toång chi phí vaän chuyeån beù nhaát) Bieát raèng chi 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àn n : Soá ñieåm ñích si : 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 laøm oâ xuaát phaùt. Cung caáp toái ña töø khaû naêng cuûa moät ñieåm nguoàn cho caùc ñieåm ñích theo thöù töï töø traùi sang phaûi. Neáu nguoàn i ñaõ heát thì chuyeån sang nguoàn i+1. Ñaùp öùng toái ña nhu caàu cuûa moät ñieåm ñích töø caùc nguoàn theo thöù töï öu tieân töø treân xuoáng döôùi. Nhu caàu j ñaõ ñuû thì chuyeån sang nhu caàu j+1. Kho (i) Ñieåm baùn leû (j) Toång cung 1 2 3 4 1 5 7 9 6 120 100 20 2 6 7 10 5 140 40 80 20 3 7 6 8 1 100 100 Toång caàu 100 60 80 120 360 8 4
PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT (The Minimal Cost Method) : Öu tieân choïn oâ coù chi phí thaáp nhaát ñeå ñaùp öùng toái ña khaû naêng cuõng nhö nhu caàu. Loaïi boû caùc oâ cuûa ñieåm nguoàn hoaëc ñieåm ñích ñaõ heát khaû naêng cuõng nhö nhu caàu. Xaùc ñònh laïi oâ coù chi phí thaáp nhaát trong caùc oâ coøn laïi vaø tieáp tuïc phaân boå gioáng nhö caùc böôùc treân. Kho Ñieåm baùn leû Toång 1 2 3 4 cung 1 5 7 9 6 120 100 X 20 X 2 6 7 10 5 140 X 60 60 20 3 7 6 8 1 100 X X X 100 Toång caàu 100 60 80 120 360 9 PHÖÔNG PHAÙP XAÁP XÆ VOLGEL - VAM (The Volgel’s Approximation Method) ÖÙng vôùi moãi haøng vaø coät cuûa baûng, xaùc ñònh ñoâï cheânh leäch giöõa hai oâ coù chi phí vaän chuyeån beù nhaát vaø beù nhì. Xaùc ñònh haøng hay coät coù cheânh leäch Max. Phaân boå toái ña löôïng haøng coù theå vaøo oâ coù chi phí beù nhaát vaø loaïi boû caùc oâ coøn laïi trong haøng hoaëc coät ñaõ choïn ôû böôùc treân. Thöïc hieän laëp laïi caùc böôùc treân cho caùc oâ coøn laïi. Chuù yù : Khi xuaát hieän chi phí cô hoäi Max ôû nhieàu haøng hoaëc coät khaùc nhau, thì choïn haøng (coät) coù chöùa oâ coù nhu caàu (khaû naêng) cao nhaát . 10 5
Theo ví duï treân, ta coù : Kho Ñieåm baùn leû Toång 1 2 3 4 cung 1 5 7 9 6 120 1 2 6 7 10 5 140 1 3 7 6 8 100 1 100 X X X 5 Toång caàu 100 60 80 120 360 1 1 1 4 11 Kho Ñieåm baùn leû Toång 1 2 3 4 cung 1 100 5 7 9 6 120 1 2 6 7 10 5 140 X 1 3 7 6 8 1 100 X X X 100 Toång caàu 100 60 80 120 360 1 0 1 1 Kho Ñieåm baùn leû Toång cung 1 2 3 4 1 5 7 9 6 120 100 X 1 2 6 7 10 5 140 X 20 2 3 7 6 8 1 100 X X X 100 Toång caàu 100 60 80 120 360 12 0 1 1 6
Kho Ñieåm baùn leû Toång 1 2 3 4 cung 1 5 7 9 6 120 100 X X 2 2 6 7 10 5 140 60 3 X 20 3 7 6 8 1 100 X X X 100 Toång caàu 100 60 80 120 360 0 1 Kho Ñieåm baùn leû Toång cung 1 2 3 4 1 5 7 9 6 120 100 X 20 X 2 6 7 10 5 140 X 60 60 20 3 7 6 8 1 100 X X X 100 Toång caàu 100 60 80 120 360 13 CAÛI THIEÄN NGHIEÄM BAN ÑAÀU CHO TÔÙI KHI ÑAÏT ÑÖÔÏC ÑIEÅM TOÁI ÖU. 14 7
Böôùc 1 : Tính toaùn chæ soá caûi tieán Iij cho caùc oâ roång (oâ khoâng coù phaân boå haøng). Coù hai phöông phaùp xaùc ñònh : 1- Phöông phaùp duyeät tuaàn töï : ÖÙng vôùi moät oâ roång naøo ñoù, veõ ñöôøng ñi kín noái oâ roång naøy vôùi caùc oâ ñaõ gaùn giaù trò ban ñaàu baèng caùc ñöôøng naèm ngang vaø thaúng ñöùng (Voøng). Gaùn daáu cho caùc oâ trong ñöôøng ñi baét ñaàu töø oâ roång coù daáu döông (+), caùc oâ keá tieáp ñoåi daáu (daáu aâm -). Tính caùc chæ soá Iij = Toång ñaïi soá caùc Cij trong ñöôøng ñi ñang xeùt vôùi daáu ñaõ ñöôïc gaùn ôû böôùc treân. 15 Ví duï : Baèng phöông phaùp goùc taây baéc, ta coù phöông aùn ban ñaàu nhö sau : Kho Ñieåm baùn leû Toång Xeùt oâ roång 1 2 3 4 cung (1,3) : 1 5 - 7 +9 6 120 100 20 2 6 7 10 5 140 40+ 80 - 20 3 7 6 8 1 100 100 Toång 100 60 80 120 360 caàu Luùc ñoù : I13 = + 9 -10 + 7 - 7 = -1 16 8
2- Phöông phaùp theá vò : Goïi ui (i = 1,2,…,m) ; vj (j =1,2,…n) laø caùc bieán öùng vôùi caùc ñieåm nguoàn i vaø ñieåm ñích j, Taïi caùc oâ khoâng roång ta coù ñaúng thöùc : cij – (ui +vj) = 0 Döïa vaøo caùc phöông trình töông öùng vôùi caùc oâ khoâng roång, ta coù theå xaùc ñònh ñöôïc caùc giaù trò ui vaø vj Taïi caùc oâ roång, tính caùc chæ soá caûi tieán Iij = cij – (ui + vj). Chuù yù : - Thoâng thöôøng ngöôøi ta gaùn giaù trò u1 = 0 vaø töø ñoù tính caùc giaù trò ui, vj coøn laïi. - Sau moãi böôùc laëp, tính laïi caùc ui, vj vaø Iij . 17 Ví duï : Baèng phöông phaùp goùc taây baéc, ta coù phöông aùn ban ñaàu nhö sau : Kho Ñieåm baùn leû Toång 1 (v1) 2 (v2) 3 (v3) 4 (v4) cung 1 (u1) 5 7 9 6 120 0 100 20 2 (u2) 6 7 10 5 140 0 40 80 20 3 (u3) 7 6 8 1 100 -4 100 Toång caàu 100 60 80 120 360 5 7 10 5 Vôùi u1 = 0 → v1 = c11 – u1 = 5 – 0 = 5 ; v2 = c12 – u1 = 7 – 0 = 7 Vôùi v2 = 7 → u2 = c22 – v2 = 7 – 7 = 0 Vôùi u2 = 0 → v3 = c23 – u2 = 10 – 0 = 10 ; v4 = c24 – u2 = 5 – 0 = 5 Vôùi v4 = 5 → u3 = c34 – v4 = 1 – 5 = -4 18 9
Tính caùc chæ soá caûi tieán Iij cuûa caùc oâ roång : Iij = cij – (ui + vj) Kho Ñieåm baùn leû Toång 1 (v1) 2 (v2) 3 (v3) 4 (v4) cung 1 (u1) 5 - 7 + 9 6 120 0 100 20 I13 = -1 I14 = 1 2 (u2) 6 + 7 - 10 5 140 I21 = 1 40 80 20 0 3 (u3) 7 6 8 1 100 I31 = 6 I32 = 3 I33 = 2 100 -4 Toång caàu 100 60 80 120 360 5 7 10 5 19 Böôùc 2 : kieåm tra daáu hieäu toái öu vaø phaân boá laïi haøng : Neáu caùc chæ soá Iij cuûa caùc oâ roång ñeàu khoâng aâm, phöông aùn hieän haønh laø toái öu. Neáu toàn taïi moät hay moät soá chæ soá Iij cuûa oâ roång naøo ñoù aâm, phöông aùn hieän taïi chöa toái öu. Ta choïn chæ soá Iij beù nhaát vaø ñieàu chænh löôïng haøng ñaõ phaân boå cho caùc oâ coù lieân quan theo nguyeân taéc sau : * Xaùc ñònh xij min trong caùc oâ ñöôïc gaùn daáu tröø (-). * Bôùt ñi moät löôïng xij min cho caùc oâ gaùn daáu tröø. * Coäng theâm moät löôïng xij min cho caùc oâ gaùn daáu coäng (+). 20 10
Trong ví duï treân, oâ (1,3) coù I13 = -1 < 0 ⇒ Chöa thoûa ñieàu kieän toái öu. Tieán haønh phaân boå laïi löôïng haøng vaän chuyeån cho caùc oâ nhö sau : * Giaù trò ñieàu chænh = min (x12,x23) = 20 * Giaù trò caùc oâ môùi laø : x12 = 20 – 20 = 0 x13 = 0 +20 = 20 x23 = 80 – 20 = 60 x22 = 40 + 20 = 60 Ta ñöôïc baûng sau : Kho Ñieåm baùn leû Toång cung 1 2 3 4 3 4 1 5 _ 7 + 9 6 120 Z * = ∑∑ cij.xij = 1900 100 0 20 i =1 j =1 2 6 + 7 _ 10 5 140 60 60 20 3 7 6 8 1 100 100 Toång caàu 100 60 80 120 360 Tieáp tuïc laøm cho caùc oâ roång coøn laïi cho tôùi khi khoâng coøn chæ soá Iij < 0 thì döøng laïi. Phöông aùn cuoái cuøng naøy laø phöông aùn toái öu. 21 Baøi 1 : Moät coâng ty coù ba kho chöùa haøng vôùi khaû naêng cung caáp töøng kho laø 15, 75 vaø 20 taán nguyeân lieäu / ngaøy. Coâng ty coù 4 phaân xöôûng saûn xuaát vôùi vôùi nhu caàu nguyeân lieäu cho töøng phaân xöôûng laø 5 ; 35 ; 15 vaø 55 taán / ngaøy. Chi phí vaän chuyeån moät taán nguyeân lieäu töø kho i ñeán phaân xöôûng j cho ôû ma traän sau : 10 5 15 11    cij = 12 7 9 20   8 10 14 16    Yeâu caàu : Xaùc ñònh phöông aùn vaän chuyeån toái öu. (Z = 1325) 22 11
Baøi 2 : Moät coâng ty baùch hoaù coù ba cöûa haøng coù nhu caàu veà moät loaïi haøng töông öùng laø 45, 90 vaø 110 taán. Coâng ty ñaõ ñaët mua loaïi haøng ñoù ôû boán xí nghieäp vôùi khaû naêng cung öùng laø 40, 75, 60, 70 taán. Cöôùc vaän chuyeån (ngaøn ñoàng/taán) töø xí nghieäp i ñeán cöûa haøng j cho ôû ma traän sau : 12 10 10     4 5 8  cij =  3 8 6    8 8 12    Laäp keá hoaïch vaän chuyeån haøng töø caùc xí nghieäp ñeán caùc cöûa haøng sao cho toång chi phí vaän chuyeån laø thaáp nhaát. (Z = 1680) 23 Ta có thể sử dụng phần mềm QM ñể tìm nghiệm : • Khởi ñộng phần mềm QM và di chuyển con trỏ ñến phần mềm thích hợp (Transportation). • Có thể ñánh ký tự E ñể chọn. 24 12
Ta ñược giao diện Transportation : • Chọn New (N) và khai báo các thông số cần thiết. • Có thể sử dụng các số liệu của ví dụ 1. 25 • Chọn Run (R) ñể giải 26 13
• Dùng phím mủi tên lên, xuống ñể xem kết quả. 27 BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU VAØ PHAÙT Ta phaân bieät hai tröôøng hôïp : - Tröôøng hôïp toång phaùt lôùn hôn toång thu : Ñöa baøi toaùn veà daïng caân baèng thu phaùt baèng caùch theâm moät traïm thu giaû coù nhu caàu baèng phaàn cheânh leäch cuûa phaàn phaùt vaø phaàn thu. - Tröôøng hôïp toång phaùt nhoû hôn toång thu : Ñöa baøi toaùn veà daïng caân baèng thu phaùt baèng caùch theâm moät traïm phaùt giaû coù khaû naêng cung baèng phaàn cheânh leäch cuûa phaàn thu vaø phaàn phaùt. Gaùn chi phí vaän chuyeån ñôn vò töø moïi ñieåm nguoàn thöïc ñeán ñieåm ñích giaû hay ñieåm nguoàn giaû ñeán ñieåm ñích thöïc baèng 0. Xaùc ñònh phöông aùn xuaát phaùt vaø phöông aùn toái öu gioáng nhö baøi toaùn caân baèng thu phaùt. 28 14
Ví duï : Moät coâng ty caàn vaän chuyeån moät loaïi haøng töø boán kho chöùa haøng ñeán ba cöûa haøng. Soá löôïng haøng coù ôû caùc kho laø 150, 100, 145 vaø 100. Nhu caàu haøng hoùa ôû caùc cöûa haøng laø 140, 150 vaø 180. Giaù cöôùc vaän chuyeån ñôn vò haøng hoùa töø kho i ñeán cöûa haøng j cho ôû ma traän sau : 5 4 6   8 5 9 cij =  11 6 12    9 7 13   Tìm phöông aùn vaän chuyeån toái öu. 29 Do toång cung = 495 > toång caàu = 470. Do ñoù, ta caàn taïo theâm traïm thu giaû coù nhu caàu = 495 – 470 = 25 vaø gaùn cho caùc oâ giaû naøy coù cöôùc phí vaän chuyeån baèng 0 : Kho Cöûa haøng Toång cung B1 B2 B3 B4 A1 5 4 6 0 150 A2 8 5 9 0 100 A3 11 6 12 0 145 A4 9 7 13 0 100 Toång caàu 140 150 180 25 495 30 Phương pháp giải 15
Ví duï : Moät coâng ty caàn vaän chuyeån moät loaïi haøng töø ba kho chöùa haøng ñeán boán cöûa haøng. Soá löôïng haøng ôû caùc kho laø 80, 70 vaø 50. Nhu caàu cuûa caùc cöûa haøng laø 100, 50, 30 vaø 70. giaù cöôùc vaän chuyeån ñôn vò haøng hoùa töø kho i ñeán cöûa haøng j cho ôû ma traän sau :  3 5 6 5   cij =  4 5 7 8   3 4 4 3   Tìm phöông aùn vaän chuyeån toái öu. 31 Do toång cung = 200 < toång caàu = 250. Do ñoù, ta caàn taïo theâm traïm phaùt giaû coù khaû naêng phaùt = 250 – 200 = 50 vaø gaùn cho caùc oâ giaû naøy coù cöôùc phí vaän chuyeån baèng 0 : Kho Cöûa haøng Toång cung B1 B2 B3 B4 A1 3 5 6 5 80 A2 4 5 7 8 70 A3 3 4 4 3 50 A4 0 0 0 0 50 Toång caàu 100 50 30 70 250 32 Phương pháp giải 16