Bài giảng Phương pháp tối ưu trong kinh tế: Chương 2 - Nguyễn Phương

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:26

Thêm vào BST

Báo xấu

2
lượt xem 1
download

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

Bài giảng "Phương pháp tối ưu trong kinh tế - Chương 2: Bài toán vận tải" cung cấp cho người đọc các nội dung: Mô hình bài toán vận tải; phương pháp giải bài toán vận tải; sử dụng Excel giải bài toán vận tải, một số ứng dụng của bài toán vận tải. Mời các bạn cùng tham khảo 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 Phương pháp tối ưu trong kinh tế: Chương 2 - Nguyễn Phương

Chương 2 BÀI TOÁN VẬN TẢI NGUYỄN PHƯƠNG Khoa Khoa Học Dữ Liệu trong Kinh Doanh Trường Đại Học Ngân Hàng TPHCM Blog: https://nguyenphuongblog@wordpress.com Email: nguyenphuong0122@gmail.com 1
NỘI DUNG 1. Mô hình bài toán vận tải 2. Phương pháp giải bài toán vận tải 3. Sử dụng Excel giải bài toán vận tải 4. Một số ứng dụng của bài toán vận tải - Bài toán phân công lao động - Bài toán xe không - Bài toán vận tải có ô cấm - Bài toán bố trí cây trồng 5. Bài tập 2
1. MÔ HÌNH BÀI TOÁN VẬN Ví dụ 1: TẢI Công ty lương thực An Bình cần vận chuyển gạo từ các kho A1, A2, A3 đến các đại lý B1, B2, B3, B4. Cho biết chi phí vận chuyển gạo (ngàn đồng/tấn) từ các kho đến kho đến các đại lý trong bảng sau B1 B2 B3 B4 A1 100 20 200 110 A2 120 70 90 200 A3 20 140 160 180 Hãy lập mô hình bài toán vận chuyển gạo từ kho tới các đại lý sao cho tổng chi phí vận chuyển thấp nhất. Biết rằng các kho A1, A2, A3 có trữ lượng gạo là 15, 25, 5; đại lý B1, B2, B3, B4 có nhu cầu nhập 5, 15, 15, 10 (tấn). 3
Gọi xij là khối lượng gạo vận chuyển từ kho Ai đến đại lý Bj . Khi đó, ta có mô hình bài toán: f ( x) = 100 x11 + 20 x12 + 200 x13 + 110 x14120 x21 + 70 x22 + 90 x23 + 200 x24 + 20 x31 + 140 x32 + 160 x33 + 180 x34 min x11 + x12 + x13 + x14 = 15 x21 + x22 + x23 + x24 = 25 x31 + x32 + x33 + x34 = 5 x11 + x21 + x31 = 5 x12 + x22 + x32 = 15 x13 + x23 + x33 = 15 x11 + x24 + x34 = 10 xij 0, i = 1,3; j = 1, 4 4
NỘI DUNG BÀI TOÁN VẬN TẢI Giả sử cần vận chuyển một loại hàng hóa (xi măng, sắt thép, ...) từ m điểm cung cấp (trạm phát), ký hiệu là A1, A2, ..., Am đến n điểm tiêu thụ (trạm thu), ký hiệu là B1, B2, ..., Bn, biết rằng a) Số lượng hàng có ở các trạm phát A1, A2, ..., Am lần lượt là a1, a2,..., am b)Số lượng hàng cần ở các trạm thu B1, B2, ..., Bn lần lượt là b1, b2,..., bn. c)Chi phí vận chuyển một đơn vị hàng hóa từ trạm phát Ai đến trạm thu Bj là cij. Hãy lập kế hoạch vận tải hàng hóa sao cho tổng chi phí vận tải thấp nhất và thỏa mãn yêu cầu thu – phát. 5
MÔ HÌNH BÀI TOÁN VẬN TẢI Đặt xij là số lượng hàng cần vận chuyển từ trạm phát Ai đến m n trạm thu Bj. Z= Ta có tổng chi phí vận tải: cij xij min i =1 j =1 n i) Trạm phát, phát hết hàng: xij = ai , i = 1, m m j =1 ii) Trạm thu, thu đủ hàng: xij = b j , j = 1, n i =1 iii) Yêu cầu trạm phát, trạm thu được thỏa m n ai = bj (đk cân bằng thu – phát). i =1 j =1 6
MÔ TẢ BÀI TOÁN VẬN TẢI DƯỚI DẠNG BẢNG T a ï th u Bj B1 r m B2 Bn b 1 b 2 b n T a ï p h a ù Ai r m t A1 c 11 c 12 c 1 n a 1 x 11 x12 x 1 n A2 c 21 c 22 c 2 n a 2 x 21 x22 x 2 n Am c m 1 c m 2 c m n a m x m 1 x m 2 x m n 7
(1) Ký hiệu (i, j) là ô trên dòng i và cột j. (2) Chi phí vận chuyển cij được ghi ở góc trên bên trái của ô (i, j), lượng hàng cần vận chuyển xij được ghi ở góc dưới bên phải của ô (i, j) biểu diễn tuyến đường vận chuyển từ trạm phát Ai đến trạm thu Bj. (3) Những ô ứng với xij > 0 trong BẢNG VẬN TẢI được gọi là ô chọn, những ô khác gọi là ô loại. (4) Một dãy các ô chọn, trong đó 3 ô liên tiếp không nằm trên cùng một dòng hay một cột thì được gọi là một dây chuyền. (5) Một dây chuyền khép kín được gọi là một chu trình hay một vòng. 8
(6) Một ma trận (xij) là một P.A của BTVT nếu nó thoả hệ ràng buộc. Một P.A (xij) làm cực tiểu hàm mục tiêu thì (xij) là P.A.T.Ư. của bài toán. (7) Một P.A của BTVT không tạo thành chu trình (vòng) thì được gọi là Phương án cực biên hay Phương án cơ bản (P.A.C.B). (8) Một P.A.C.B của BTVT có đủ m+n-1 ô chọn thì được gọi là P.A.C.B không suy biến, nếu có ít hơn m+n-1 ô chọn được gọi là P.A.C.B suy biến. Ví dụ: Hình 2.1 Hình 2.2 Hình 2.3 Hình 2.4 Hình 2.5
CÁC TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI TÍNH CHẤT 1: Bài toán vận tải luôn luôn có phương án tối ưu. TÍNH CHẤT 2: Với một phương án bất kỳ, số ô chọn của phương án không vượt quá tổng số trạm phát và trạm thu. ≤ m + n –1 (với là số ô chọn của P.A) TÍNH CHẤT 3: Với một phương án có đủ m+n–1 ô chọn thì với một ô loại bất kỳ được đưa vào phương án sẽ tạo thành chu trình và chu trình này là duy nhất. TÍNH CHẤT 4: Nếu lượng cung ai và lượng cầu bj là số nguyên thì bài toán có lời giải nguyên. 10
PHƯƠNG PHÁP CHI PHÍ BÉ NHẤT TÌM PHƯƠNG ÁN CƠ BẢN ĐẦU TIÊN Nguyên tắc: ưu tiên phân phối tối đa vào ô có chi phí bé nhất của bảng cho đến khi các trạm phát phát hết hàng và các trạm thu nhận đủ hàng. Các bước thực hiện: Bước 1: Tìm ô có cước phí thấp nhất trong bảng và phân phối tối đa vào ô đó (nếu có Bước 2: Điều chỉnh lại lượng hàng tại trạm phát và trạm thu đã giao nhận hàng. Sau đó, bỏ đi các ô nằm trên trạm phát đã hết hàng hay trạm thu đã nhận đủ hàng bằng cách ghi lượng hàng 0 vào các ô đó. Quay lại bước 1, tiếp tục thực hiện quá trình gồm 2 bước trên cho các ô còn lại cho đến khi các trạm phát phát hết hàng và trạm thu nhận đủ hàng thì ta được một PACB của bài toán. 11
Ví dụ: B1: B2: 40 B3: 30 20 A1: 30 1 3 5 A2:25 5 4 2 A3: 35 8 5 4 B1: 5 B2: 15 B3: 15 B4: 15 A1: 15 10 2 20 11 A2: 25 12 7 9 20 A3: 5 2 14 16 18 12
PHƯƠNG PHÁP GÓC TÂY – BẮC TÌM PHƯƠNG ÁN CƠ BẢN ĐẦU TIÊN Nguyên tắc: ưu tiên phân phối tối đa vào ô ở phía trên và bên trái (phía tây – bắc) của bảng cho đến khi trạm phát phát hết hàng và các trạm thu nhận đủ hàng Các bước thực hiện: Bước 1: Phân phối tối đa vào ô ở phía tây – bắc của bảng, ô (1,1). Bước 2: Điều chỉnh lại lượng hàng tại trạm phát 1 và trạm thu 1. Sau đó, bỏ đi các ô nằm trên trạm phát đã hết hàng hay trạm thu đã nhận đủ hàng bằng cách ghi lượng hàng 0 vào các ô đó. Quay lại bước 1, tiếp tục thực hiện quá trình gồm 2 bước trên cho các ô còn lại cho đến khi các trạm phát phát hết hàng và trạm thu nhận đủ hàng thì ta được một PACB của bài toán 13
Ví dụ: B1: B2: 40 B3: 30 20 A1: 30 1 3 5 A2:25 5 4 2 A3: 35 8 5 4 B1: 25 B2: 25 B3: 10 B4: 15 A1: 10 10 2 20 11 A2: 30 12 7 9 20 A3: 20 2 14 16 18 14
2. PHƯƠNG PHÁP GIẢI BÀI TOÁN VẬN TẢI Bước 1. Lập bảng vận tải toán thế vị) (thuật (1) Kiểm tra điều kiện cân bằng thu – phát. (2) Xác định P.A.C.B (bằng phương pháp chi phí bé nhất). (3) Kiểm tra P.A.C.B có suy biến hay không - Nếu P.A.C.B. suy biến: thêm vào ô (i,j) bất kỳ với xij = 0, không tạo thành chu trình. - Nếu P.A.C.B không suy biến, chuyển sang [2] Bước 2. Kiểm tra tính tối ưu của bài toán (1)Tìm hệ thống thế vị: ui + vj = cij với mọi (i,j) là ô chọn. Do đó: vj = cij - ui và ui = cij - vj trong đó ô (i,j) là ô chọn. Chọn ui = 0 tại dòng bất kỳ. (2) Đặt ij = ui + vj – cij - Nếu ij ≤ 0 với mọi i,j: ta có P.A.T.Ư. 15
Bước 3. Xác định vòng điều chỉnh (1) Chọn ô vào: Max ij ( ij > 0) (2) Chọn ô ra - xác định vòng điều chỉnh (vòng tạo bởi ô vào và các ô chọn đã có). - ô vào sẽ được đánh dấu (+). Xen kẻ dấu (-) và dấu (+) trên vòng điều chỉnh. - lượng điều chỉnh q = min{xij/ (i,j) có dấu (-)} Bước 4. Xác định P.A.C.B mới xij + q da�+); u( xij = xij − q da�−); u( xij kho� da� ng u. Quay về bước [2]. Sau một số bước lặp hữu hạn, bài toán có phương án tối 16
Ví dụ: B1: B2: 40 B3: 30 20 A1: 30 1 3 5 A2:25 5 4 2 A3: 35 8 5 4 B1: 5 B2: 15 B3: 15 B4: 15 A1: 15 10 2 20 11 A2: 25 12 7 9 20 A3: 5 2 14 16 18 17
MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN VẬN TẢI 1. Bài toán phân công lao động: Ví dụ: Một xí nghiệp vận tải cần phân phối 4 xe (có trọng tải như nhau) từ các điểm đậu xe đến 4 nơi có hàng để thực hiện một hợp đồng vận tải. Khoảng cách (km) từ mỗi điểm đậu xe đến một điểm có hàng cho trong bảng sau: B1 B2 B3 B4 A1 8 8 8 8 A2 8 9 10 11 A3 8 12 10 13 A4 8 11 10 12 Hãy tìm cách phân phối xe sao cho tổng số km xe chạy là ít nhất.hình: Mô Gọi xij là số xe phân phối từ điểm Ai đến điểm Bj. xij = 0 khi không chọn phân phối xe trên tuyến Ai đến Bj 18 x = 1 khi chọn phân phối xe trên tuyến A đến B
Ví dụ: Một phân xưởng có 2 công nhân nữ và 3 công nhân nam. Phân xưởng có một máytiện loại I và 2 máy tiện loại II, 2 máy tiệnloại III. Năng suất công nhân đứng trênmỗi loại máy được cho trong bảng (đơn vịlà chi tiết/ngày): Máy I: 1 Máy II: 2 Máy III: 2 Nữ: 2 10 8 7 Nam: 3 8 9 11 Hãy tìm phương án phân công đứng máy để cuối ngày thu được nhiều sản phẩm nhất. 19
2. Bài toán xe không (cực tiểu hóa tổng tấn.km xe không) -Các bài toán vận tải đã khảo sát được xem xét dưới góc độ chủ hàng đi thuê xe để chở hàng. -Xem xét bài toán dưới góc độ chủ xe: để thực hiện hợp đồng đã ký kết, ngoài những tuyến đường xe chảy có tải thì có những tuyến đường xe chạy không tải đến địa điểm lên hàng. -Vấn đề đặt ra: tối thiểu số tấn X km xe chạy không tải, điều đó có nghĩa là giảm thiểu được nhiên liệu và các chi phí khác liên quan Loại hàng độnglượng xe. Trọng tải xe Địa điểm đến hoạt Số của Địa điểm lên hàng (tấn) xuống hàng Ví dụ: Một xí nghiệp vận tải phải thực hiện kế hoạch vận A1 Xi măng 100 tấn 100 B1 chuyển: 50 tấn 50 B2 A2 Gạch 20.000 viên 10 B1 100.000 viên 50 B3 A3 Đá 70 m3 100 B4 Sắt 80 tấn 80 B2