intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chương 3: Bài toán vận tải - bài 4

Chia sẻ: Lê Văn Nhứt | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
1.540
lượt xem 346
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'chương 3: bài toán vận tải - bài 4', kinh tế - quản lý, kinh tế học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: Bài toán vận tải - bài 4

  1.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 1  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Để giải BTVT không cân bằng thu-phát, ta lập thêm trạm thu phụ nếu BT có tổng phát lớn hơn tổng thu hay lập thêm trạm phát phụ nếu BT có tổng thu lớn hơn tổng phát sao cho BT trở về dạng BTVT đóng. Khi đó, ta giải BT như một BTVT đóng bình thường. Tuy nhiên, ta cần chú ý ba điểm quan trọng sau: @ Cước phí tại các ô phụ đều bằng 0. @ Khi lập PACBXP, ta ưu tiên phân phối hàng vào các ô chính trước, sau đó mới tới phân vào các ô phụ. @ Sau khi tìm được PATU của BT có lập thêm trạm phụ, ta loại bỏ lượng hàng được phân vào trạm phụ để đưa ra PATU của BT gốc. 2 1
  2.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Ví dụ 1: Giải bài toán vận tải cho ở bảng sau: 3  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Ta nhận thấy rằng tổng lượng hàng có ở các trạm phát là 415 đơn vị; trong khi đó, tổng lượng hàng cần thu tại các trạm thu là 340 đơn vị. Như vậy, bài toán này có dạng là bài toán có tổng phát lớn hơn tổng thu; cho nên ta lập một trạm thu phụ B6 với lượng hàng cần thu là 75 đơn vị để đưa bài toán trên về bài toán vận tải đóng. 4 2
  3.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 5  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 6 3
  4.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) x 7  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 8 4
  5.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Và tại bảng VT này, tất cả các HSUL đều không dương cho nên đây là PATU của BTVT phụ. Bỏ qua trạm thu phụ, ta có PATU của BT gốc như sau:  0 0 0 10 0     0 0 45 0 35  x  0 25 70 0 0 0     25 0 40 0 0    f ( x 0 )  1440. 9  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Ví dụ 2: Giải bài toán vận tải cho ở bảng sau: 10 5
  6.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 11  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) 12 6
  7.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 1. BTVT không cân bằng thu-phát (BTVT mở) Tại bảng VT cuối cùng, các HSUL đều không dương cho nên BT phụ có PATU. Để tìm PATU của BT gốc, ta loại hàng A5. Khi đó, PATU & giá trị HMT của BT gốc đạt được là:  0 0 0 80 50     25 0 85 0 0  x0   75 0 0 0 0     50 45 0 0 0    f ( x 0 )  1605. 13  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Trong thực tế, có một số tuyến đường không thể vận chuyển hàng đi qua được: cầu phá bị hư, đường sá hư hỏng hoặc đang cấm tải, cự ly quá xa không thể phát hàng đúng thời gian yêu cầu, hoặc nếu đến thì hàng sẽ bị hư hỏng, phương tiện phục vụ trên tuyến không có hoặc không đạt chất lượng để phục vụ, kế hoạch VT phải đảm bảo cho một số trạm phát phát hết hàng hoặc trạm thu thu đủ hàng trong khi không cân bằng thu-phát, v.v… Những ô trong bảng VT đặc trưng cho những tuyến đường như trên được gọi là “ô cấm”. 14 7
  8.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Để giải BTVT có ô cấm, ta cho cước phí cij tại các ô cấm là một số dương rất lớn M và sau đó tiến hành giải BT bình thường. Trong quá trình giải BTVT “M”, ta cần chú ý 3 điểm sau: @ Khi lập PACBXP, ta ưu tiên phân phối hàng vào các ô bình thường trước, sau đó mới phân phối hàng vào các ô cấm. @ HSUL cùng dấu với hệ số của M trong hệ số đó. @ Nếu trong PATU của BTVT “M” mà các ô cấm đều có lượng hàng bằng 0 thì PA đó cũng là PATU của BT gốc. Còn nếu tồn tại ít nhất một ô cấm là ô chọn thì BTVT không có PA. 15  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Ví dụ 1: Cho bài toán vận tải như ở bảng sau: Trong đó, trạm thu B4 cần thu đủ hàng để giao cho khách hàng nếu không sẽ bị đền hợp đồng với số tiền phạt khá lớn. Giải bài toán trên. 16 8
  9.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Từ bảng VT trên, ta thấy rằng tổng lượng hàng có ở các trạm phát là 280 đơn vị; trong khi, tổng như cầu ở các trạm thu là 330 đơn vị. Như vậy, ta cần lập thêm một trạm phát phụ A5 với lượng hàng cần phát là 50 đơn vị để đưa về BTVT đóng. Tuy nhiên, do B4 cần thu đủ hàng cho nên 4 trạm phát chính phải đảm bảo phát đủ lượng hàng cho trạm này. Do đó, trạm phát phụ không thể phát cho trạm B4 và ô (5,4) trở thành ô cấm.17  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 18 9
  10.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 19  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 20 10
  11.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm  BTVT gốc có PATU với trị số HMT đạt được như sau:  50 0 5 45     0 0 60 0  x  0 0 0 0 75     0 45 0 0    f ( x 0 )  3790. 21  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Ví dụ 2: Cho bài toán vận tải như ở bảng sau: Giải BTVT với các thông tin thêm như sau: - Trạm A2B6 không qua được do cầu đang được sửa chữa. - Nếu VC hàng từ trạm A4B4 thì hàng sẽ bị hư hỏng nặng. - Tuyến từ trạm A1B3 không có phương tiện phù hợp. 22 11
  12.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 23  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 24 12
  13.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 25  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Sau lần cải tiến thứ nhất, các HSUL trên các ô đều không dương cho nên PA cải tiến là PATU của bài toán “M”. Trong PA đó, tất cả các ô cấm đều có lượng hàng bằng 0 cho nên PA đó cũng chính là PATU của BTVT gốc. Vậy BTVT đã cho có PATU và trị HMT đạt được như sau:  60 0 0 0 50 0     0 0 80 70 0 0  x0   0 0 0 20 15 40     0 50 0 0 0 85    f ( x 0 )  6025. 26 13
  14.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Tuy nhiên, HSUL của hai ô loại (2,1), (4,3) bằng 0 cho nên PA trên đây không phải là PATU duy nhất của BT. Để tìm PATU khác của BT, ta đưa một trong hai ô trên vào hệ thống ô chọn và tiếp tục giải BT: 27  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 28 14
  15.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Với lần điều chỉnh phương án thứ nhất, ta thấy các hệ số ước lượng của các ô trong bảng vận tải đều không dương. Cho nên, ta có thêm một phương án tối ưu của bài toán ngay trong lần điều chỉnh này.  45 0 0 0 65 0     15 0 80 55 0 0  x1   0 0 0 35 0 40     0 50 0 0 0 85    Trong PATU của BT ở lần điều chỉnh thứ nhất, ta thấy HSUL của ô loại (4,3) bằng 0, cho nên BT còn PATU khác. 29  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm 30 15
  16.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 2. Bài toán vận tải có ô cấm Trong bảng VT ở lần điều chỉnh thứ hai này, tất cả các HSUL đều không dương cho nên ta có PATU sau:  45 0 0 0 65 0     15 0 45 90 0 0  x2   0 0 0 0 0 75     0 50 35 0 0 50     Bài toán đã cho có 3 PATU: x0, x1 và x2. 31  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT Kinh nghiệm giải toán: Nếu có nhiều hơn 1 chẵn có lượng hàng bé nhất (ô đưa ra) mà trong đó: + Có “Ô cấm” thì nên chọn “Ô cấm” đưa ra. + Các ô này có cước phí khác nhau thì ta nên chọn ô có cước phí cao nhất đưa ra. 32 16
  17.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại n m f ( x)   cij xij  max i 1 j 1 m x j 1 ij  ai n x i 1 ij  bj xij  0, (i  1, n, j  1, m) 33  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại Việc giải BTVT dạng này cũng tương tự như việc giải một BTVT bình thường. Tuy nhiên, ta cần chú ý 3 điểm sau: @ Khi lập PACBXP thì ta ưu tiên phân phối tối đa vào các ô có cij lớn nhất. @ Điều kiện TU của BT là các HSUL đều phải không âm. @ Ô được đưa vào hệ ô chọn là ô có HSUL âm nhỏ nhất. 34 17
  18.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại + Ví dụ 1: Một tổ đánh mộng của một cty sản xuất đồ gỗ XK có 4 loại máy đánh mộng: 5 máy M1, 4 máy M2, 8 máy M3 và 8 máy M4. Để vận hành các máy này, tổ này có 3 nhóm CN có tay nghề khác nhau: N1 có 10 người, N2 có 7 người và N3 có 8 người. Với chi tiết A của một SP, năng suất ngày của từng công nhân thuộc các nhóm khi vận hành các máy trên được thống kê như sau: Biết rằng, mỗi máy chỉ do 1 CN vận hành. Hãy phân CN vào các máy sao cho sản lượng 1 ngày đạt được là tối đa. 35  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại Giải: Ta lập PACBXP của bài toán dựa vào nguyên tắc phân phối tối đa vào các ô có năng suất cao nhất như sau: 36 18
  19.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại 37  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại  Ta có PATU & trị số HMT của BT như sau: 0 1 8 1 x 0   0 0 0 7  f ( x 0 )  1173. 5 0   3 0 38 19
  20.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại Ví dụ 2: Một HTX nông nghiệp có vùng đất canh tác A1, A2, A3 lần lượt có diện tích tương ứng: 500 ha, 800 ha và 700 ha. HTX định trồng 5 loại cây B1, B2, B3, B4 và B5 với diện tích tương ứng là 200 ha, 350 ha, 400 ha, 500 ha và 550 ha. Theo khảo sát, sau khi thu hoạch, lợi nhuận BQ mỗi loại cây trồng trên mỗi vùng đất được cho ở bảng sau: Chú ý: Loại cây B4 không trồng được trên vùng đất A2. Hãy lập kế hoạch để trồng các loại cây trên sao cho LN sau thu hoạch là max. 39  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 4. GIẢI BÀI TOÁN VẬN TẢI ĐẶC BIỆT 3. Bài toán “vận tải” có hàm mục tiêu cực đại Giải: Ta để ý đây là BT có ô cấm; cho nên, tại ô (2,4) ta cho LN BQ là một số âm vô cùng (-M, với M là một số dương vô cùng lớn). Và tới đây, ta giải BT có ô cấm bình thường: Ô (3,3) có HSUL âm nhỏ nhất, cho nên ô (3,3) được chọn đưa vào hệ thống ô chọn. 40 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2