Bài Toán Ứng Dụng Của Bài Toán Vận Tải

0
8996
bai toan ung dung cua bai toan van tai 1
QUẢNG CÁO
Vài Phút Quảng Cáo Sản Phẩm


Bài Toán Ứng Dụng

(Lưu ý: Một số dạng dưới đây được thiết kế để giải bằng máy tính)

Mọi ý kiến đóng góp xin gửi vào hòm thư: [email protected]

Tài liệu liên quan: Bài Tập Thuế Giá Trị Gia Tăng và Tiêu Thụ Đặc Biệt (có lời giải)


I. Bài Toán Ứng Dụng Của Bài Toán Vận Tải

1. Bài toán điều xe

bai toan ung dung cua bai toan van tai

* Có 1 kế hoạch vận chuyển hàng aij từ  trạm phát Ai → Bj (i = , j=  ). Cự ly từ Ai → Bj là lij (km). Tìm phương án điều xe sao cho có hiệu quả nhất.

Quảng Cáo

* Cần lưu ý: sau khi giao hàng xe phải chạy rỗng từ kho giao hàng về kho phát hàng. Nếu gọi 1 Tkm xe không tương ứng với xe 1 Tấn chạy rỗng trên đoạn đường 1 km thì kế hoạch điều xe là tối ưu nếu tổng số tấn km xe không là min.

Gọi Xij là số tấn xe chạy rỗng từ điểm Bj về Ai

Giải như hình trên!

2. Bài toán phân phối đất trồng

Có m loại đất A1, A2,…,Am với diện tích sử dụng tương ứng là a1, a2,…,am (ha). Dự định để trồng n loại cây b1, b2,…,bn. Nếu trồng loại cây j trên đất i sẽ cho năng suất là Nij (Tạ/ha). Lập kế hoạch phân phối đất trồng sao cho tổng thu nhập là cao nhất.

3. Bài toán phân công lao động

bai toan ung dung cua bai toan van tai

* Xí nghiệp X có m công nhân làm việc trên n máy. Tỷ lệ sản phẩm tốt của công nhân i trên máy j là aij (i = , j=  ). Hãy lập kế hoạch phân công đứng máy sao cho tổng tỷ lệ sản phẩm tốt của xí nghiệp trong 1 kỳ kế hoạch là lớn nhất.

* Gọi Xij là phương án công nhân i làm việc trên máy j

Giải như hình trên.

4. Bài toán bố trí cán bộ theo chức vụ công tác

* Có n vị trí công tác B1, B2,…,Bn còn thiếu cán bộ và số cán bộ còn thiếu tại các vị trí này là b1, b2,…,bn. Còn a1, a2,…,am là số cán bộ được đào tạo ra trường theo các chuyên môn khác nhau hay cán bộ mới chuyển đến chưa bố trí công tác. Khi phân công công tác cho cán bộ có thể xảy ra 2 trường hợp:

Trường hợp 1:1 cán bộ thuộc 1 chuyên ngành nào đó thích ứng nhất với công việc của ngành đó và có thể công tác ở một số ngành liên quan.

Trường hợp 2: Có cán bộ chỉ công tác ở 1 vị trí nhất định mà không công tác được ở các vị trí khác.

Đánh giá mức độ phù hợp của cán bộ i với công việc loại j người ta dung chỉ số thích ứng qij

* Gọi Xij là số cán bộ loại i được phân đến vị trí j

bai toan ung dung cua bai toan van tai

* Với bài toán ở trường hợp (2): Giả sử cán bộ io không phù hợp với công việc loại jo. Khi đó hệ ràng buộc của bài toán như sau:

bai toan ung dung cua bai toan van tai

Dạng bài toán này bị khuyết biến Xiojo . Ta đưa thêm biến giả qiojo với qiojo=M ( M là 1 số dương đủ lớn ). Đây là dạng bài toán vận tải có ô cấm.

Lưu ý: Nếu là bài toán min thì tham số ở ràng buộc aij được lấy bằng M

Nếu trong phương án tối ưu các biến giả (tại ô cấm) bằng 0 thì đó là phương án tối ưu của bài toán ban đầu. Còn nếu có biến giả nhận giá trị dương thì bài toán gốc không có phương án tối ưu.

Ví dụ:  Một công ty X có kế hoạch tuyển dụng lao động như sau:

  • 1 phó phòng marketing
  • 1 trợ lý kinh doanh
  • 2 nhân viên kinh doanh
  • 2 bảo vệ cơ quan

Sau khi phỏng vấn, có số người có các bằng cấp sau được nhận vào:

  • Bằng đại học kinh tế 3 người: Hà, Kiên, Hùng – {A, B, C}
  • Bằng cao đẳng kinh tế 2 người: Linh, Dương – {D, E}
  • Bằng PTTH 2 người: Khánh, Tâm – {F, G}

Biết chỉ số thích ứng công việc được kiểm tra bằng trắc nghiệm như sau:

Tên Phó phòng Trợ lý Nhân viên
kinh doanh
Bảo vệ
A 0,8 0,9 0,6 0,4
B 0,8 0,8 0,7 0,5
C 0,7 0,7 0,8 0,6
D 0,8 0,9 0,7
E 0,7 0,7 0,6
F 0,8
G 0,8

Biết thêm vị trí phó phòng không thể sử dụng cán bộ chưa tốt nghiệp đại học. Vị trí trợ lý không thể sử dụng cán bộ chưa tốt nghiệp cao đẳng. Hãy lập kế hoạch bố trí cán bộ vào các vị trí phù hợp nhất.

5. Bài toán ứng dụng của bài toán vận tải trong VTB

* Bài toán bố trí tàu vận chuyển hàng về cảng cần loại hàng phù hợp

Cho 1 xí nghiệp vận chuyển 1 kế hoạch vận chuyển hàng như sau:

Cần vận chuyển hàng từ – cảng A với khối lượng 9.000T than, 6.000T quặng

– cảng B với khối lượng 3.000T clinke

– cảng C với khối luợng 7.000T than, 1.000T clinke

tới cảng nhận hàng là D, E, F biết:

– Cảng D cần nhận 8.000T than hoặc quặng, 1.000T clinke

– Cảng E cần nhận 12.000T than, 2.000T quặng hoặc clinke

– Cảng F cần nhận 3.000T loại nào cũng được

Chi phí vận chuyển giữa các cảng như sau (đ.vị: 103đ):

D E F
A 8 13 7
B 12 9 15
C 15 12 10

 

Bài tập lập sơ đồ hoạt động tối ưu cho đội tàu

Công việc vận chuyển hàng theo 1 kế hoạch cho trước có thể được tiến hành theo nhiều sơ đồ khác nhau ( hành trình vận doanh liên tục ) vấn đề đặt ra là hãng lập sơ đồ chạy tàu tối ưu theo 1 tiêu chuẩn nào đó. Thông thường đối với vận tải người ta thường chọn chỉ tiêu là tổng số tấn km (tấn hải lý) phương tiện chạy rỗng là tối ưu (ít nhất). Việc tối ưu theo tiêu chuẩn này thường dẫn đến hiệu quả là năng suất hoạt động của phương tiện cao hoặc hệ số lợi dụng trọng tải là lớn nhất.

Ví dụ: 1 công ty vận tải có kế hoạch vận chuyển như sau:

Nơi Loại hàng Khối lượng

(103T)

Số phương tiện vận chuyển (103T)
Đi Đến
A D Kim khí 120 120
A B Kim khí 90 90
B C Than 180 180
D A Quặng 60 60
D E Gỗ 30 30
E A Gỗ 130 130
E B Đá 50 50
E C Đá 50 50

Hãy lập kế hoạch chạy tàu tối ưu ( sơ đồ hoạt động tối ưu ) biết cự ly vận chuyển:

A B C D E
A 0 295 235 126 147
B 0 252 195 180
C 0 170 186
D 0 128
E 0

Giải:

Bài toán bố trí thiếp bị xếp dỡ trên cầu tàu:

  • Có m thiết bị xếp dỡ và n cầu tàu với điều kiện là 1 thiết bị xếp dỡ chỉ làm việc ở 1 vị trí xếp dỡ sao cho năng suất toàn bộ thiết bị trên cầu tàu là Max; Pij là năng suất thiết bị i được bố trí trên cầu tàu j.
  • Gọi xij là thiết bị xếp dỡ i đuợc bố trí tại vị trí thứ j.
  • xij = 0 nếu i không được bố trí tại j.
  • xij = 1 nếu i được bố trí tại j.
  • Mô hình bài toán.

bai toan ung dung cua bai toan van tai

II. Các dạng khác của bài toán vận tải trong vận tải biển.

1. Bài toán hạn chế về số phương tiện.

Có các thông số như bài toán vận tải cổ điển, nhưng cho thêm điều kiện hạn chế về số phương tiện:

+ dij là số tấn phương tiện để chở hết 1 đơn vị hàng từ Ai → Bj.

+ d là tổng số tấn phương tiện hiện có.

→có thêm điều kiện về số tấn phương tiện:
bai toan ung dung cua bai toan van tai

2. Bài toán vận tải hạn chế về khả năng thông qua.

bai toan ung dung cua bai toan van tai

III. Bài Toán Phân Phối

bai toan ung dung cua bai toan van tai3. Ma trận vào máy tính.

Ví dụ 1: 1 công ty vận tải có khối lượng hàng cần vận chuyển từ HP đến SG 100.000 tấn; HP – Quảng Ninh : 8.000 tấn và từ HP – Quy Nhơn : 20.000 tấn. Biết các thông số sau:

Kiểu tàu Năng suất vận chuyển (tấn/tàu) Chi phí (106đ/T) Số phương tiện ( tàu)
HP – SG HP – QNi HP – QNh 1 2 3
1 5000 3000 4000 190 128 180 8
2 8000 2000 5000 212 165 185 4

Lập phương án bố trí tàu sao cho vận chuyển hết khối lượng hàng hoá yêu cầu hiệu quả nhất. Viết ma trận vào máy tính.

IV. Ứng dụng bài toán phân phối trong vận tải biển

1. Bài toán bố trí tàu đạt lợi nhuận cao nhất

  1. Phát biểu bài toán:

Xí nghiệp vận tải X có m kiểu tàu hoạt động trên n tuyến. Thời gian khai thác trong năm của tảu I trên các tuyến là Ti ( ngày/tàu). Năng suất vận chuyển của tàu i trên tuyến j là Pij (tấn km/tàu – ngày). Tổng khối lượng hàng trên tuyến j là Qj (tấn). Lãi của tàu i trên tuyến j là Lij. Số tàu kiểu i là Ki (i=1→m). Lãi bình quân trong ngày ( USD or đ/ tàu – ngày).

Lập phương án bố trí đội tàu của xí nghiệp sao cho vận chuyển hết khối lượng hàng hoá yêu cầu đạt hiệu quả cao nhất.

2. Lập bài toán.

Gọi xij là thời gian khai thác của tàu i trên tuyến j.

bai toan ung dung cua bai toan van tai

Ví dụ: Lập phương án bố trí tàu sao cho vận chuyển hết khối lượng hàng hoá yêu cầu và hiệu quả nhất biết:

Kiểu tàu Năng suất (1000T/tàu-ngày) Lãi (1000USD/tàu-ngày) Tổng thời gian khai thác (ngày/tàu) Số tàu (chiếc)
Tuyến 1 Tuyến 2 Tuyến 1 Tuyến 2
1 1,0 2,0 0,5 0,8 200 2
2 1,5 1,5 0,7 1,0 150 3
ΣQj 500.103(T) 100.103(T)

 

2. Bài toán tận dụng tối đa sức chở của tàu biển

  • 1 tàu có trọng tải thực chở D (tấn), dung tích W ( m3) được chọn để chở n loại hàng với giá cước vận chuyển loại hàng j ( j=1→m) là Cj . Hệ số chất xếp Uj (m3/tấn). Lập kế hoạch xếp hàng tối ưu.
  • Lập bài toán:

Gọi xij là khối lượng loại hàng j cần xếp xuống tàu:

bai toan ung dung cua bai toan van tai 3. Bài toán phân bổ tàu biển, tàu sông, tàu biển pha sông va tàu chở sà lan trong hệ thống vận tải Bắc – Nam của Việt Nam.

  1. Phát biểu bài toán: bài toán tương tự như bài toán 1 trong trường hợp kinh doanh độc lập.
  2. Lập bài toán:
  • Nếu kinh doanh độc lập:

xij là số chuyến tàu loại i khai thác trên tuyến j.

bai toan ung dung cua bai toan van tai

  • Nếu kinh doanh cả hệ thống:

bai toan ung dung cua bai toan van tai

Với m: dấu hiệu chỉ tàu biển

l: dấu hiệu chỉ tàu chở sà lan

c: dấu hiệu chỉ tàu pha sông biển

p1,p2: dấu hiệu chỉ tàu sông ở phía bắc và phía nam

4. Bài toán tối ưu hoá phát triển đội tàu trên cơ sở sử dụng hiệu quả đội tàu hiện có của mình.

  1. Đặt vấn đề
  • Ngành vận tải biển là 1 hệ thống kinh tế rất phức tạp. Hệ thống vận tải biển được cấu tạo từ các tiểu hệ thống sau: đội tàu, cảng, xí nghiệp đóng mới, bộ phận cung ứng định mức hàng hoá. Trong đó đội tàu là phần trọng tâm chủ yếu. Cho nên việc phát triển đội tàu có ý nghĩa quan trọng vì nó giúp cho việc vận chuyển hàng hoá của chính công ty cũng như để xuất khẩu dịch vụ vận tải.
  • Trong nền kinh tế thế giới hiện nay, sự phát triển của khoa học kỹ thuật và sự phát triển của thông tin có ảnh hưởng lớn đến sự phát triển của ngành vận tải biển. Các bài toán KT- XH của VTB đòi hỏi ta phải giải quyết 1 lượng thông tin khổng lồ mới có thể tìm thấy 1 phương án tối ưu trong hàng trăm nghìn phương án có thể xảy ra. Nếu các công ty VTB chỉ dựa vào kế hoạch công tác thì không thể tìm được phương án tối ưu. Sự áp dụng các mô hình toán kinh tế với sự giúp đỡ của mô hình đội tàu giúp các cán bộ khai thác tìm được lời giải tối ưu cho các bài toán kinh tế về tối ưu hoá phát triển đóng tàu VTB trong tương lai dựa trên cơ sở sử dụng đội tàu cũ hiện có 1 cách có hiệu quả có 1 ý nghĩa cấp bách trong toàn bộ ngành hàng hải và trong tất cả các công ty vận tải biển.
  • Mục tiêu của bài toán tối ưu hóa phát triển đội tàu là tìm ra chủng loại tàu cần bổ xung cho tương lai, vốn đầu tư cho từng năm để phát triển đội tàu sao cho đảm bảo vận chuyển hết khối lượng hàng hoá trên tất cả các tuyến mà công ty đã khai thác với hiệu quả kinh tế cao nhất. đối với bài toán tối ưu hoá phát triển đội tàu trong tương lai trên cơ sở sử dụng hiệu quả đội tàu hiện có ta dùng chỉ tiêu hiệu quả là min chi phí.
  • Chi phí biến đổi tổng hợp trong trường hợp này được tính như sau:

+ Chi phí khấu hao (gồm cả chi phí khấu hao với tàu cũ khai thác trong tương lai).

+ Chi phí khai thác tàu mới trong tương lai ( không tính chi phí khấu hao).

+ Phần thu hồi vốn đầu tư cho các tàu cần bổ xung trong tương lai.

2. Mô hình bài toán

bai toan ung dung cua bai toan van tai

Trong đó:

r: là chỉ số năm lập kế hoạch r=1→R

R: là tập hợp số năm lập kế hoạch

i: là chỉ số loại tàu vận tải biển

j: là chỉ số tuyến vận tải

Ic: là tập hợp hay số lượng hay các kiểu tàu cũ đang khai thác.

Im : là tập hợp hay số lượng các kiểu tàu mới ( chúng ta định đưa vào thị trường để bổ xung trong tương lai).

Jc: tập hợp hay sốlượng các sơ đồ công nghệ mà trên đó các tàu VTB cũ có thể khai thác được.

Jm: là số lượng các sơ đồ công nghệ mà trên đó các tàu VTB mới có thể khai thác được.

Ccijr: chi phí khai thác trong 1 chuyến đi của tàu cũ i trên tuyến j trong năm r.

Cmijr: chi phí khai thác trong 1 chuyến đi của tàu mới loại i trên tuyến j trong năm r

Tcir: thời gian trong năm của tàu cũ i có thể khai thác được trong năm r

Qjr: khối lượng vận chuyển 1 chuyến đi của tàu i trên tuyến j trong năm r

[E]: hệ số hiệu quả đầu tư của ngành VTB

5. Một số bài toán tối ưu cho xí nghiệp xếp dỡ.

a. Bài toán phân phối thiết bị xếp dỡ vào vị trí làm việc (áp dụng cho thiết bị xếp dỡ có khả năng dịch chuyển).

bai toan ung dung cua bai toan van tai

Trong đó:

xij: số TBXD loại i làm việc tại vị trí j

i: chỉ số loại thiết bị xếp dỡ

j: chỉ số vị trí làm việc

Pij: năng suất toàn bộ của 1 TBXD i khi làm việc tại j

Cij; chi phí khai thác của 1 TBXD i khi làm việc tại j

Gij: lượng hàng cần xếp dỡ trong kỳ kế hoạch

Ni: số lượng TBXD kiểu i.

  1. Bài toán xây dựng quy trình công nghệ phục vụ cho kho đạt hiệu quả cao nhất.

– Phát biểu bài toán:

Để dỡ hàng từ tàu lên n kho, cảng sử dụng các loại thiết bị là P, P1,P2….Pm trong đó P là thiết bị chính tiền phương; còn P1,P2….Pm là thiết bị phục vụ cho các kho 1→N với số lượng thiết bị tương ứng là N,N1,……Nm.

bai toan ung dung cua bai toan van tai

LEAVE A REPLY

Please enter your comment!
Please enter your name here

LEAVE A REPLY

Please enter your comment!
Please enter your name here