›
›

Bài giảng Tin học trong quản lý xây dựng - Chương 5: Bài toán vận tải - Đỗ Thị Xuân Lan

pdf 67 trang ngocly 2910
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học trong quản lý xây dựng - Chương 5: Bài toán vận tải - Đỗ Thị Xuân Lan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tin_hoc_trong_quan_ly_xay_dung_chuong_5_bai_toan_v.pdf

Nội dung text: Bài giảng Tin học trong quản lý xây dựng - Chương 5: Bài toán vận tải - Đỗ Thị Xuân Lan

  1. Chương 5 BÀI TOÁN VẬNTN TẢI Tin học trong quản lý
  2. NỘI DUNG 1. Giới thiệu 2. Giải bài toán vận tải kín bằng phương pháp thế vị 3. Bài toán vận tải hở 4. Bài toán vận tải cực đại hàm mục tiêu 5. Bài toán vậntn tảivi vớikhi khả năng lưu thông và khả năng chuyên chở bị giới hạn 6. Giải bài toán vận tải bằngqg qu y hoạch tuyến tính 7. Bài toán vận tải qua các trạm trung gian ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  3. Chương 5. Bài toán vận tải GIỚI THIỆU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  4. GIỚITHII THIỆU Là dạng đặcbiệtcủa bài toán quy hoạch tuyến tính. Giảiquyếtvấn đề phân phối hàng hoá từ một sốđịa điểm cung cấp(điểm nguồn) đếnmộtsố địa điểmtiêuthụ (điểm đích) sao cho: Tổng chi phí ít nhất. Cự ly vậnchuyểnnhỏ nhất. Hay tổng tiềnlời là nhiềunhất. Áp dụng để xác định vị trí đặt nhà kho, cửa hàng hay nhà xưởng mới khi xem xét một số phương án vềđịa điểmxâydựng. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  5. Chương 5. Bài toán vận tải GIẢI BÀI TOÁN VẬN TẢI KÍN BẰNG PHƯƠNG PHÁP THẾ VỊ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  6. Giải bài toán vận tải kín bằng ph ương pháp th ế vị Bài toán vậntảikíncótổng lượng cung cấp từ các điểm nguồn bằng tổng lượng tiêu thụởcác điểm đích. Các bước giảimột bài toán vậntảikín: Bước1 Bước2 Bước3 1. Thiết lập bài 3. Kiểm tra điều toán vận tải ở kiện tối ưu và dạng bảng nhằm 2. Xác định lời giải cải thiện lời giải tóm tắt dữ liệu khả dĩ ban đầu. ban đầu cho của bài toán và đến khi đạt theo dõi trình tự được điềukiu kiện tính toán tối ưu. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  7. Ví dụ 5.1. Tổng công ty xây dựng XaToCo có 3 cơ sở sản xuất đá dăm (A1, A2, A3))g và 3 công trường xây dựng (B1, B2, B3). Công suất sản xuất đá hàng tuần của các cơ sở lần lượt là 50, 60, 70m3. Nhu cầutiêuthu tiêu thụ đá hàng tuầncn củabaa ba công trường lầnlượt là 40, 85, 55m3. 3 50m 3 Cơ sở A1 Công trường B1 40m 60m3 Cơ sở A2 Công trường B2 85m3 70m3 Cơ sở A3 Công trường B3 55m3 Khả nănggg cung cấp Luồng v ận chuyển Nhu cầu tiêu thụ Điểm nguồn Điểm đích ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  8. Chi phí vận chuyển 1m3 đá từ các cơ sở sản xuất đá đến các công trường tiêu thụ đá không phụ thuộc vào khối lượng đá vận chuyển như sau (đơn vị tính 10.000 đồng): B1 B2 B3 A1215 A2 3 4 3 A3466 Hãy xác định phương án vận chuyển đá từ nơi cung cấp đến nơi tiêu thụ để tổng chi phí vận chuyển là th©2010ấp củnha ĐỗấTht.ị Xuân Lan , GVC. Ths.
  9. Bước 1: Thiếtlập bài toán vậntải ở dạng bảng Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 Khả năng cung cấp giới hạn của 215 cơ sở A1 A1 50 343 Lượng hàng vận A2 60 chuyển từ điểm nguồn đến điểm 466 đích tương ứng A3 70 (từ A2 đến B3) Nhu cầu 40 85 55 180 tiêu thụ Tổng lượng cung cấp và tiêu thụ Nhu cầu tiêu thụ của công trường B2 Cước phí vận chuyển một m3 đá từ nơi cung cấp A3 đến công trường B1 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  10. Bước 2: Xác định lời giải khả dĩ ban đầu Các phương pháp thường được dùng là: Phương pháp góc tây bắc. Phương pháp số nhỏ nhất trong bảng . Phương pháp xấpxỉ Vogel. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  11. Phương pháp góc tây b ắc Bắt đầu phân phốilượng hàng vận chuyển từ ô trên cùng bên trái theo quy tắc sau: Tậndụng tối đakhả năng cung cấp củamỗi điểm nguồntương ứng với mỗi dòng trước khi chuyển sang dòng tiếp theo. Đáp ứng tối đa nhu cầucủamỗi điểm đích tương ứng với mỗi cột trước khi chuyển sang cộttiếp theo. Đảmbảotậndụng hếtkhả năng cung cấpvàđáp ứng đủ nhu cầu tiêu thụ. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  12. Phương pháp góc tây b ắc Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 A1 50 40 10 X 343 A2 60 X 60 X 466 A3 70 X 15 55 Nhu cầu 40 85 55 180 tiêu thụ Có nghĩa là vận chuyển 15m3 đá từ cơ sở sản xuất đá A3 đến công trường B2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  13. Phương pháp góc tây b ắc Lộ trình Lượng vận Đơngián giá Tổng cước phí chuyển vận chuyển TừĐến A1 B1 40 2 80 A1 B2 10 1 10 A2 B2 60 4 240 A3 B2 15 6 90 A3 B3 55 6 330 Tổng cước phí: 750 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  14. Phương pháp số nhỏ nhất trong bảng Tìm lời giải ban đầu gần tối ưu hơn cho bài toán vậntn tải theo quy tắc sau: •Ưu tiên phân phốichoôcógiátrị nhỏ nhất •Loạibỏ dòng tương ứng với điểmnguồn đã hếtkhả năng cung cấphaycộttương ứng với điểm đích đã được đáp ứng đủ nhu cầutiêu thụ.Xácđịnh lạiôcógiá trị nhỏ nhất để tiếp tục ưu tiên phân phối. •Thựchiệnlặplại hai bướctrênchođếnkhi tận dụng hết khả năng cung cấp của các điểm nguồnvàđáp ứng đủ nhu cầutiêuthụ củacác điểm đích. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  15. Phương pháp số nhỏ nhất trong bảng Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 A1 50 X 50 X 343 A2 60 40 X 20 466 A3 70 X 35 35 Nhu cầu 40 85 55 180 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  16. Phương pháp số nhỏ nhất trong bảng Lộ trình Lượng vận Đơn giá Tổng cướcphí chuyển vận chuyển TừĐến A1 B2 50 1 50 A2 B1 40 3 120 A2 B3 20 3 60 A3 B2 35 6 210 A3 B3 35 6 210 Tổng cước phí: 650 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  17. Phương pháp x ấppx xỉ Vogel Bước 3. Phân phối tối đa lượng hàng có th ể vận chuyểnnchoôcóchi cho ô có chi Bước 4. Loại phí vận chuyển nhỏ nhất ứng với bỏ dòng dã tận dòng hoặc cột đã chọn. dụng hết khả Bước2c 2. Xác định dòng năng cung cấp hoặc cột có chi phí cơ hội hay cột đã lớn nhất được đáp ứng đủ nhu cầu tiêu Bước 1. Xác định chênh thụ. lệch chi phí vận tải giữa hai Bước 5. Tính toán ô có chi phí thấp nhất ứng lại chi phí cơ hội Bước6c 6. Trở lại cho bảng vận tải vớimỗi dòng và cột. bước 2 và thực hiện sau khi đã loại bỏ dòng hay cột ở lặp lại các bước trên bước 4. cho đếnnkhit khi tận dụng hết khả năng cung cấp ©2010và đ cápủa Đ ỗứThngị Xuân đủ Lan , GVC. Ths. nhu cầu tiêu thụ
  18. Bước 1. Xác định chênh lệch chi phí vận tải giữa hai ô có chi phí thấp nhất ứng với mỗi dòng và cột. Bước2c 2. Xác định dòng hoặccc cột có chi phí cơ hộiil lớnnnh nhất Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 A1 50 1 343 A2 60 0 466 A3 70 2 Nhu cầu 40 85 55 180 tiêu thụ 1 3 2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  19. Bước 3. Phân phối tối đa lượng hàng có thể vận chuyển cho ô có chi phí vận chuyển nhỏ nhất ứng với dòng hoặc cột đã chọn. Bước 4. Loạibi bỏ dòng hếtkht khả năng cung cấp hay cột đã đáp ứng đủ nhu cầu tiêu thụ. Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 1 A1 X 50 X 50 343 A2 60 0 466 2 A3 70 Nhu cầu 40 85 55 180 tiêu thụ 1 1 3 2 2 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  20. Bước 5. Tính toán lại chi phí cơ hội cho bảng vận tải sau khi đã loại bỏ dòng hay cột ở bước4. Bước 6. Trở lại bước 2 Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 1 A1 X 50 X 50 343 0 1 A2 55 60 466 2 2 A3 X 70 Nhu cầu 40 85 55 180 tiêu thụ 1 1 3 2 2 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  21. Bước 6. Trở lại bước 2 và thực hiện lặp lại các bước trên cho đến khi tậndụng hết khả năng cung cấp và đáp ứng đủ nhu cầutiêuu tiêu thụ Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 215 1 A1 X 50 X 50 343 0 1 A2 X 5 55 60 466 2 2 A3 40 30 X 70 Nhu cầu 40 85 55 180 tiêu thụ 1 1 3 2 2 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  22. Tổng vận chuyển của mẫu phân phối này được tính như sau: Lộ trình Lượng Đơn giá Tổng cước vận vận phí TừĐến chuyển chuyển A1B250150 A2 B2 5 4 20 A2 B3 55 3 165 A3 B1 40 4 160 A3 B2 30 6 180 Tổng cước phí: 575 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  23. Bước 3. Kiểm tra điều kiện tối ưu và cải thiện lời giải ban đầu cho đến khi đạt được điều kiện tối ưu. Bước1 Bước2 Bước3 1. Thiết lập bài toán vận tải ở 3. Kiểm tra điều dạng bảng nhằm 2Xá2. Xác địnhhl lời kiệntn tối ưuvàu và tóm tắt dữ liệu giải khả dĩ ban cải thiện lời giải của bài toán và đầu. ban đầu cho theo dõi trình tự đến khi đạt tính toán được điều kiện tối ưu. Áp dụngpg phươnggp phá p thế vị (phương ppppháp phân phối cải tiến) để tìm lời giải tối ưu cho bài toán vận tải không suy biến từ lời giải khả dĩ ban đầu. Bài toán vậntn tải không suy biếnkhisn khi số ô được phân phối hàng vận chuyển (số ô chọn) bằng với tổng số dòng và số cột (tổng số điể©2010m ngu của ĐỗồThnị Xuân và Lan đ , GVC.iểm Ths. đích) trừ cho một.
  24. Bước 3. Kiểm tra điều kiện tối ưu và cải thiện lời giải ban đầu cho đến khi đạt được điều kiện tối ưu n là số cột vj là giá trị thế vị v v3 vi v1 2 (số điểm đích) của cột j (j = 1 n ) Công trường ui là giá trị thế u Cơ sở sản i B Bn Khả năng vị của dòng i xuất đá B1 (i =1 m)1 m) 2 1 5 A1 u1 50 50 số ô chọn bằng 334433 m + n – 1. u 2 A 40 20 60 446666 u Am Gọi m là số 3 35 35 70 dòng (số điểm Nhu cầu nguồn) 40 85 55 180 tiêu thụ xij là lượng hàng được phân phốivàoôi vào ô ij cij là chi phí vận chuyển đơnnv vị ô ij ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  25. Bước 3. Kiểm tra điều kiện tối ưu và cải thiện lời giải ban đầu cho đến khi đạt được điềukiu kiện tối ưu Bước 4. Tính toán chỉ số cảitiếnIij cho mỗiô loại Bước 3. Giảihi hệ phương ttìrình htê trên bằng công thứcIij = cij -ui -vj Bước5.NếucIij củamọiôloạilà Bước 2. Gán u = 0 không âm thì lời 1 giảihiện hành là tối ưu. Nếucógiátrị I ij Bước 1. Để tính toán các âm thì chọnôcó giá trị thế vị, gán ui + vj = cij Iij âm nhỏ nhất để điềuchỉnh cho các ô chọn. Có (m+n+ n – lượng hàng vận 1) ô chọn nên có (m + n - 1) chuyển Bước 6. Xác định lại phương trình bảng vậnnt tải và quay trở lại bước 1. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  26. Lầnlậpthứ 1: Bước 1 > Bước 2 > Bước 3 > Bước4 v v vi v1 2 3 v1 =1= 1 v2 =1= 1 v3 =1= 1 Công trường Cơ sở sản ui Khả năng xuất đá B1 B2 B3 215 u1 A1 I = 2 -0 -1 = 150 I = 5 -0 -1 = 4 50 u1 = 0 11 13 u1 +v+ v2=1 u + v =3343 u + v =3 u2 A2 2 1 2 3 60 40I = 4 -2 -1 = 1 20 u2 = 2 22 u 466u + v =6 u3+ v3=6 3 A3 3 2 70 I = 4 -5 -1 = -2 35 35 u3 = 5 31 Nhu cầu 40 85 55 180 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  27. Lầnlậpthứ 1: Bước 1 > Bước 2 > Bước 3 > Bước 4 Bước 1 Bước 2 Bước 3 Bước 4 Thiết lập các Tính toán ch ỉ số phương tìtrình Tìm ra được: cải tiến cho mỗi ô cho các ô u = 0 1 loại chọn: u2 = 2 Iij = cij -ui –vj u1 + v2 = 1 Gán u1 = 0 u3 = 5 I11 = 2 - 0 - 111 = 1 u2 + v1 = 3 v1 = 1 I13 = 5 - 0 - 1 = 4 u2 + v3 = 3 v2 = 1 I22 = 4 - 2 - 1 = 1 u3 + v2 = 6 v3 = 1 I31 = 4 - 5 - 1 = -2 u3 +v+ v3 =6= 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  28. Lầnlậpthứ 1: Bước5 Nếu chỉ số cải tiến Iij của mọi ô loại là không âm thì lời giảihii hiện hành là tối ưu. Nếu cóiátó giá trị Iij âthìhâm thì chọn ôóô có Iij âm nhỏ nhất để điều chỉnh lượng hàng vận chuyển: •Vẽ một tứ giác khép kín qua ô loạicóIij âm nhỏ nhất và 3 ô chọnkhácbằng những đường ngang bằng và thẳng đứng và nhận các ô này là đỉnh củatứ giác • Bắt đầu đánh d ấucu cộng (+) vào ô loại, đánh dấutru trừ (-) và cộng (+) xen kẽ vào các ô trên đỉnh của tứ giác vừa vẽ. •Xác định lượng hàng vận chuyển nhỏ nhất xij min được phân p hối ở cáôác ô được gádán dấu trừ (-). Lượng hàng vận chuyển ở các ô được gán dấucộng (+) sẽ đượccộng thêm một lượng xij min. Lượnggg hàng vận chuyển ở các ô được gán dấu trừ (-) sẽ được trừ đi một lượng xij min. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  29. Bắt đầu đánh dấu cộng Lần(+) lậ vàop th ô loứạ 1:i, đ ánhBướ dấcu 5 Chỉ số cải tiến I31 của ô (A3B1) có giá trừ (-)vàc) và cộng (+) xen kẽ trị âm nên mẫu phân phốichi chưaatho thoả vào các ô trên đỉnh của tứ điềukiện tối ưu. Thực hiện cải tiến giác vừa vẽ. nghiệm bằng cách vẽ vòng kín qua ô Lượng hàng vận (A3B1),(A3B3), (A2B3) và (A2B1) chuyểnnhỏ nhất v vi v1 v2 3 xij min được Cơ sở Công trường Khả phân phối ở cácu sản xuất i năng ô được gán dấu đá B1 B2 B3 trừ (-) là 215 min (x ,x) = 21 33 u1 A1 I =1= 1 50 I =4= 4 50 min(35, 40) = 35. 11 50 13 34355 Lượng hàng vận u2 A2 5 60 40- 20+ tải được phân I22 = 1 phối lại ở các ô là: 466 x21 = 40 - 35 = 5 A3 70 u3 35+ 35 35- x23 = 20 + 35 = I31 = -2 55 Nhu cầu 40 85 55 180 x31 = 0 + 35 = 35 tiêu thụ x33 = 35 - 35 = 0
  30. Lầnlậpthứ 2: Bước 1 > Bước 2 > Bước 3 > Bước4 v v vi v1 2 3 v = -1 1 v2 = 1 v3 = -1 Công trường Cơ sở sản u Khả năng i xuất đá B1 B2 B3 215 u1 = 0 u 1 A1 50 50 I11 = 2 - 0 - (-1) = 3u1 +v+ v2=1 I13 = 5 - 0 - (-1) = 6 343 u = 4 u2 2 A2 55560 u + v =3 I = 4 -4 -1 = -1 2 1 22 u2+ v3=3 466 u3 = 5 u 3 A3 35 35 70 u + v =4 3 1 u3+ v2=6 I33 = 6 -5 -(-1) = 2 Nhucầu 40 85 55 180 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  31. Lầnlậpthứ 2: Bước 1 > Bước 2 > Bước 3 > Bước4 Bước 1 Bước 2 Bước 3 Bước 4 Thiết lập các Tính toán chỉ số phương trình Tìm ra được: cải tiến cho mỗi ô cho các ô u1 = 0 loại chọn: u2 = 4 Iij = cij -ui –vj u1 +v+ v2 =1= 1 Gán u1 =0= 0 u3 =5= 5 I11 =2= 2 - 0 - (-1) = 3 u2 + v1 = 3 v1 = -1 I13 = 5 - 0 - (-1) = 6 u2 + v3 = 3 v2 = 1 I22 = 4 - 4 - 1 = -1 u3 + v1 = 4 v3 = -1 I33 = 6 -5 -(-1) = u3 + v2 = 6 2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  32. Lần lập thứ 2: Bước 5 Bắt đầu đánh dấu cộng (+) Chỉ số cải tiến I22 của ô (A2B2) có vào ô loại, đánh dấu trừ (-) giá trị âm nên mẫu phân phối chưa và cộng (+) xen kẽ vào các ô thoả điềukiện tối ưu. Thực hiện cải trên đỉnh của tứ giác vừa vẽ. tiến nghiệm bằng cách vẽ vòng kín qua ô (A2B2),(A2B1), (A3B1) v à Lượng hàng vận v chuyểnnhỏ nhất vi v1 (A3B2) v2 3 Công trường xij min được Cơ sở sản phânphối ở cácui Khả năng xuất đá B1 B2 B3 ô được gán dấu trừ (-) là 215 min (x , x ) =u1 A1 50 50 21 32 I11 = 3 I13 = 6 min(5, 35) = 5. 343 Lượng hàng vận A2 60 u2 555- +5I = -1 55 tải được phân 22 phối lại ở các ô 466 là: u A3 40+-35 70 3 35 30 I31 = 2 x =5= 5 - 5=05 = 0 21 Nhu cầu x = 0 + 5 = 5 40 85 55 180 22 tiêu thụ x31 = 35 + 5 = 40 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. x32 = 35 - 5 = 30
  33. Lầnlậpthứ 3: Bước 1 > Bước 2 > Bước 3 > Bước4 v = -1 v = 1 v = 0 1 2v 3v vi v1 2 3 Cơ sở Công trường Khả sảnxuất năng ui đá B1 B2 B3 215 u1 = 0 u A1 u + v =1 50 1 1 502 I11 = 2 - 0 - (-1) = 3 I13 = 5 00 -0- 0 = 5 343 u2 = 3 u2 A2 5 55 60 I = 3 - 3 – (-1) = 1 u + v =3 21 u2+ v2=4 2 3 466 u3 = 5u3 A3 40 30 70 u + v =4 3 1 u3+ v2=6 I33 = 6 -5 -0 = 1 Nhu cầu 40 85 55 180 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  34. Lầnlậpthứ 3: Bước 1 > Bước 2 > Bước 3 > Bước4 Bước 1 Bước 2 Bước 3 Bước 4 Thiếtlt lậppcác các Tính toán ch ỉ số phương trình Tìm ra được: cải tiến cho mỗi ô cho các ô u1 = 0 loại chọn: u2 = 3 Iij = cij -ui –vj u1 + v2 = 1 Gán u1 = 0 u3 = 5 I11 = 2 - 0 - (-1) = 3 u2 + v2 = 4 v1 = -1 I13 = 5 - 0 - 0 = 5 u2 + v3 = 3 v2 = 1 I21 = 3 -3 -(-1) = u3 + v1 = 4 v3 = 0 1 u3 + v2 = 6 I33 = 6 - 5 - 0 = 1 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  35. Lầnlậpthứ 2: Bước5 Tất cả các chỉ số cải tiến đều không âm, vậy mẫu phân phối hiện tại đã đạt được điềukiu kiệnnt tối ưu. Cơ sở Công trường Khả sảnxuất năng *Mẫu ppâhân phối đá B1 B2 B3 tối ưu này cũng 215 là mẫu phân phối A1 50 theo phương 50 pháp VAM *Nghiệm ban 343 A2 60 đầu của bài toán 555 vậntải giảibằng phương pháp 466 A3 70 xấpxỉ Volgel 40 30 thường rấtgần Nhu cầu với lời giải tối ưu 40 85 55 180 và thậmchí tiêu thụ thường khi cũng ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. là lờigiảitối ưu.
  36. Chương 5. Bài toán vận tải TOÁN VẬN TẢI HỞ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  37. Bài toán v ậntn tảihi hở • Là bài toán có tổng lượng cung cấptp từ các điểm nguồn khác với tổng lượng tiêu thụ ở các điểm đích •Tacóthể áp dụng các thuậttoántrênđể giảinhưng bổ sung thêm điểmcungcấp ảo, hay điểm tiêu thụ ảo -Gán giá trị chi phí vận chuyển đơnvị trên các tuyến đường xuất phát từ các nguồn ảo hay đếncácđiểm đích ảobằng không ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  38. Bài toán v ậntn tảihi hở • Ví dụ 5.2. Xí nghiệp sản xuất vật liệu xây dựng có 3 cơ sở khai thác cát (A1, A2,A3) cung cấp cát thường xuyên cho 3 công trường xây dựng (B1, B2, B3). Công suấtsản xuất cát hàng tuần củacácca các cơ sở lầnln lượt là 55, 45, 50m3. Nhu cầu tiêu thụ cát hàng tuần của ba công trường lần lượt là 35, 25, 70m3. Chi phí vận chuyển 1m cát như sau (x1000đ)t), tìm phương án có tổng chi phí vận chuyển là thấp nhất. B1 B2 B3 A1654 A2 1 2 4 A3323©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  39. Bài toán v ậntn tảihi hở Giải Bổ sung công Tổng lượng trường ảo B có cung cấp nhu cầu tiêu thụ 150m3 20m3 Tổng lượng Cước phí vận tiêu thụ chuyển đến công 130m3 trường ảo B bằng 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  40. Bài toán v ậntn tảihi hở Cơ sở Công trường Khả sảnxuất năng đá B1 B2 B3 B ảo 6540 A1 55 35 20 1240 A2 45 35 10 3230 A3 50 15 35 Nhu cầu 35 25 70 20 150 tiêu thụ Tổng cước phí vận tải = 35(4)+35(1)+10(2)+15(2)+35(3)=330.000đ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  41. Chương 5. Bài toán vận tải BÀI TOÁN VẬN TẢI CỰC ĐẠI HÀM MỤC TIÊU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  42. Bài toán vậntảicực đạihàm mục tiêu 123 Để tránh Tiềnln lời đơnnv vị Tổng ti ềnnl lời nhầm lẫn, biểu diễn bằng tổng cộng thêm 1 bằng giá trị các giá trị giá trị dương ââem xem như tiền lời từng sao cháho các chi phí thiệt tuyến có giá trị là hại khi không phân phối không âm chọn phương vận chuyển không làm án vận đổi nghiệm chuyển ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  43. Bài toán vận tải cực đại hàm mụctiêuc tiêu •Ví dụ 5.3. Công ty vật liệu xây dựng CoVaXa có 3 cơ sở khai thác cát (A1, A2,A3) cung cấp cát thường xuyên cho 3 công trường xây dựng (B1, B2, B3) của công ty xây dựng tổng hợp CoXaTo. Công suất sản xuất cát hàng tuần của các cơ sở lầnln lượtlà 55, 45, 50m3. Nhu cầuutiêuth tiêu thụ cát hàng tuần của ba công trường lần lượt là 35, 45,70m3. Tiền lời cung cấp 1m3 cát từ các cơ sở sản xuất cát đến cááôtc công trường tiêu thụ cát nh ư sau (đơn vị tính 1.000 đồng). Hãy xác định phương án vận chuyển để tổng tiền lời là lớn nhất? B1 B2 B3 A1434 A2122 A3323©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  44. Bài toán vận tải cực đại hàm mục tiêu Cơ sở sản Công trường Khả năng xuất đá B1 B2 B3 121 A1 35 20 55 433 A2 45 45 232 A3 50 50 Nhu cầu 35 45 70 150 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  45. Bài toán vận tải cực đại hàm mục tiêu Lộ trình Lượng Tiềnlời Tổng TừĐến vận chuyển đơnvị tiềnlời A1 B1 35 4 140 A2 B2 45 2 90 A1 B3 20 3 60 A3 B3 50 3 150 TỔNG TIỀN LỜI: 460 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  46. Chương 5. Bài toán vận tải BÀI TOÁN VẬN TẢI VỚI KHẢ NĂNG CHUYÊN CHỞ, KHẢ NĂNG LƯU THÔNG BỊ GIỚI HẠN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  47. Bài toán vận tải với khả năng chuyên ch ở, khả năng lưu thông bị giới hạn • Là bài toán mà việcvc vận chuyểnbn bị giới hạn do đường bị cấm , đang sửa chữa • Để giải bài toán này, ta gán giá trị chi phí trên tuyến đường không vận chuyển đượcmc một giá trị rấtlt lớn (bài toán cực tiểu), một giá trị rất nhỏ (bài toán cực đại) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  48. Bài toán vậntảivớikhả năng chuyên chở, khả năng lưu thông bị giớihạn •Ví dụ 5.4. Tổng công ty xây dựng XaToCo có 3 cơ sở sảnxun xuất đádá dăm(A1, A2, A3) và 3 công trường xây dựng (B1, B2, B3). Công suất sản xuất đá hàng tuần của các cơ sở lần lượt là 50, 60, 70m3. Nhu cầu tiêu thụ đá hàng tuần của ba công trường lầnlượt là 40, 85, 55m3.Chi phí vận chuyển 1m3 đá từ các cơ sở sản xuất đá đến các công trường tiêu thụ đá như sau (đơn vị tính 10. 000đồng): B1 B2 B3 A1 2 1 5 A2343 A3 4 6 6 •Tuyến từ A2 đến B3 chỉ có thể chở 25m3. Phương ©2010án tcốủa Đi ỗưThu?ị Xuân Lan , GVC. Ths.
  49. Bài toán vận tải với khả năng chuyên chở, khả năng lưu thông bị giới hạn • Để hạn chế khả năng lưu thông tuyến A2 đến B3 ta tách điểm tiêu thụ B3 thành B3a, B3b – B3a có nhu cầu tiêu thụ là: 25m3 – B3b có nhu cầutiêuthu tiêu thụ là: 30m 3 • Vì không chở quá 25m3 nên từ A2 đến B3b coi như không có • Giá trị cước phí đơnvn vị củaôta ô tương ứng A2-B3b sẽ có giá trị dương thật lớn để cho lời giải tối ưu cực tiểu hàm mục tiêu không được phân phối. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  50. Bài toán vận tải với khả năng chuyên chở,,kh khả năng l ưu thông bị giới hạn Cơ sở sản Công trường Khả xuất đá B1 B2 B3a B3b năng 2155 A1 50 50 34310 A2 35 25 60 4666 A3 40 30 70 Nhu cầu 40 85 25 30 180 tiêu thụ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  51. Bài toán vận tải với khả năng chêhuyên ch ở, khả năng lưu thông bị giới hạn Lộ trình Lượng Tiềnlời Tổng Từ Đến vận đơnvị tiềnlời chuyển A1 B2 50 1 50 A2 B2 35 4 140 A2 B3 25 3 75 A3 B1 40 4 160 A3 B3 30 6 180 TỔNG CHI PHÍ: 605 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  52. Chương 5. Bài toán vận tải BÀI TOÁN VẬN TẢI GIẢI BẰNG QUY HOẠCH TUYẾN TÍNH ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  53. Bài toán vận tải giải bằng quy hoạch tuyến tíhính • Ví d ụ 5.5. Công ty xây dựng XaDuCo có 3 cơ sở sản xuất đá dăm((,A1, A2, A3) và 4 công trường xây dựng (B1, B2, B3, B4). Công suất sản xuất đá hàng tuần của các cơ sở lần lượt là 50, 55, 70m3. Nhu cầu tiêu thụ đá hàng tuần của bốn công trường lầnnl lượtlà30602040m3t là 30, 60, 20, 40m3. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  54. Bài toán vận tải giải bằng quy hoạch tuyến tíhính Chi phí vận chuyển 1m3 đá từ các cơ sở sản xuất đến các công trường tiêu thụ đá như sau (đơn vị tính 10.000 đồng): B1 B2 B3 B4 A1 15 18 19 13 A2 21 14 15 17 A3 25 12 17 22 Hãy xác định phương án vận chuyển đá từ nơi cung cấp đến nơi tiêu thụ để tổng chi phí vận chuyển là thấp nhất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  55. Bài toán vận tải giải bằng quy hoạch tuyến tíhính Giải bài toán vậntảibằng thuật toán đơnhình bằng cách đặt ẩnsố xij là lượng hàng vận chuyển từđiểm cung cấpiđến điểmtiêuthụ j B1 B2 B3 B4 A1 X11 X12 X13 X14 A2 X21 X22 X23 X24 A3 X31 X32 X33 X34 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  56. Bài toán vận tải giải bằng quy hoạch tuyến tíhính Mô hình toán: •Hàm mục tiêu: Min Z = 15X11 + 18X12 +19X13 + 13X14 + 21X21 + 14X22 + 15X23 + 17X24 + 25X31 + 12X32 + 17X33 + 22X34 •Các ràng buộc Theo điều kiệnnnh nhu cầu tiêu Theo điều kiện về khả năng • thụ cung cấp x11 + x21 + x31 ≥ 30 x11 +x+ x12 +x+ x13 +x+ x14 ≤ 50 x12 + x22 + x32 ≥ 60 x21 + x22 + x23 + x24 ≤ 55 x13 + x23 + x33 ≥ 20 x31 + x32 + x33 + x34 ≤ 70 x14 + x24 + x34 ≥ 40 •Điều kiện biên: xij ≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  57. Bài toán vận tải giải bằng quy hoạch tuyến tíhính • Đáp số: x11 = 30 x14 = 20 x23 = 20 x24 = 20 x32 = 60 Z = 2070 Khốilượng vận Từ cơ sởĐến công chuyển đá (m3 ) trường 30 A1 B1 20 A1 B4 20 A2 B3 20 A2 B4 60 A3 B2 •Tổnggp chi phí vận chuyển là 2.070 (10.000 đồng) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  58. Bài toán vận tải giải bằng qqyuy hoạch tuyến tính Nếu gọi: - m: t ổng số điểm cung cấp(p (điểm nguồn) -n: tổng số điểm tiêu thụ (điểm đích) -si: khả nănggg cung cấp của điểm nguồn thứ i (i = 1, , m) -dj: nhu cầu tiêu thụ của điểm đích j (j = 1, ,n) -cij: chi p hí vận chuyển một đơn vị hàng ho á từ điểm nguồn i đến điểm đích j - xij:l: lượng hàng đượcvc vận chuyểntn từ điểm nguồnin i đến điểm đích j ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  59. Bài toán vận tải giải bằng quy hoạch tuyến tíhính Ta có thể viết dạng quy hoạch tuyến tính của bài toán vậntn tảimi mộtcáchtt cách tổng quát như sau: • Mô hình toán: mn Hàm mục tiêu: MinZ  cijjj xij Ràng buộc: ij 11 Theo điều kiện về khả năng cung cấp n  xsij i j 1 (i = 1, ,m) Theo điều kiện nhu cầu tiêu thụ m  xij d j i 1 (j = 1, , n) Điều kiện biên: xij ≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  60. Chương 5. Bài toán vận tải BÀI TOÁN VẬN TẢI QUA CÁC TRẠM TRUNG GIAN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  61. Bài toán vận tải qua các trạm trung gian Ví dụ 5.6 Công ty sản xuất gạch ốp lát GaCo có hai nhà máy sản xuất gạch ceramic (A1, A2) nằm ở Đồng Nai và Long An , và có 2 nhà kho thành phẩm (T1,T2) ở Gò Vấp và Bình Chánh để có thể cung cấp trực tiếp cho ba cửa hàng phân phối trung tâm (B1, B2, B3) ở Nhà Bè, Phú Nhuận và Quận 5. Hình 5.2 mô tả luồng vận chuyển của tình huốngyg này. CửahàngB1 Nhà Bè Nhà máy A1 Kho T1 Đồng NiNai Gò Vấp CửahàngB2 Phú Nhuận Nhà máy A2 Kho T2 Long An Bình Chánh CửahàngB3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Quận5
  62. Bài toán vận tải qua các trạm trung gian Cước phí vậnchuyểnmột thùng gạch từ nhà máy đến kho và từ kho đếncáccửa hàng được trình bày trong bảng sau (đơnvị tính: 1.000 đồng): Nhà máy Các kho (công suất-thùng gạch) T1 T2 A1(800) 4 7 A2(700) 5 7 Các kho Cáccửa hàng B1(450) B2(350) B3(300) T1 6 4 5 T2 2 3 4 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  63. Bài toán vận tải qua các trạm trung gian Biết rằng nhu cầu tiêu thụ dự kiến ở các cửa hàng B1, B2, B3 lần lượt là 450, 350, 300 thùng. Hãy xác định phương án vận chuyển gạch từ nơi cung cấp đến nơi tiêu thụ để tổng cước phí vận chuyển là nhỏ nhất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  64. Bài toán vận tải qua các trạm trung gian Bài toán được đặt ra là cực tiểu chi phí vận chuyển trong điềukiu kiện ràng buộccsau: sau : 1. Lượng gạch chuyên chở từ nhà máy A1 Đồng Nai không vượt quá 800 thùng 2. Lượng gạchhh chuy ên c hở từ nhà m áy A2 Long An không vượt quá 700 thùng 3. Lượng gạch chuyên chở đến cửa hàng B1 Nhà Bè là 450 thùng 4. Lượng gạch chuyên chở đến cửa hàng B2 Phú Nhuận là 350 thùng 5. Lượng gạch chuyên chở đến cửa hàng B3 Quận 5 là 300 thùng 6. Lượng gạch được chở đến bằng lượng gạch được chở đi từ kho T1 Gò Vấp 7. Lượng gạch được chở đến bằng lượng gạch được chở đi từ kho T2©2010 Bình của Đỗ ThChánhị Xuân Lan , GVC. Ths.
  65. Bài toán vận tải qua các trạm trung gian Các biến quyết định của bài toán là số thùng gạch. Gọi: + D1 = số lượng gạch từ nhà máy A1 đến kho T1 + D2 = số lượng gạch từ nhà máy A1 đến kho T2 + L1 = số lượng gạch từ nhà máy A2 đến kho T1 + L2 = số lượng gạch từ nhà máy A2 đến kho T2 +G+ G1 = số lượng gạch từ kho T1 đến B1 + G2 = số lượng gạch từ kho T1 đến B2 + G3 = số lượng gạch từ kho T1 đến B3 + B1 = số lượng gạch từ kho T2 đến B1 + B2 = số lượng gạch từ kho T2 đến B2 +B+ B3 = số lượng gạch t ừ kho T2 đến B3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  66. Bài toán vận tải qua các trạm trung gian Mô hình quy hoạch tuyến tính của bài toán như sau: -Hàm mục tiêu: 4D1 + 7D2 + 5L1 + 7L2 + 6G1 + 4G2 + 5G3 + 2B1 + 3B2 + 4B3 min - Các ràng buộc: D1 + D2 ≤ 800 L1 + L2 ≤ 700 G1 + B1 = 450 G2 + B2 = 350 G3 + B3 = 300 D1 + L1 = G1 + G2 + G3 D2 + L2 = B1 + B2 + B3 - Điều kiện biên: ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. D1 , D2, L1, L2, G1, G2, G3, B1, B2, B3≥ 0
  67. Bài toán vận tải qua các trạm trung gian Lời giải: Lượng gạch Điểm nguồn Điểm đích D1 650 A1 T1 D2 150 A1 T2 L2 300 A2 T2 G2 350 T1 B2 G3 300 T1 B3 B1 450 T2 B1 Tổnggp chi phí vận chuyển là 9.550 ((gngàn đồng) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.