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

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

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

* 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 X_ij là số tấn xe chạy rỗng từ điểm B_j về A_i

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

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

Có m loại đất A₁, A₂,…,A_m với diện tích sử dụng tương ứng là a₁, a₂,…,a_m (ha). Dự định để trồng n loại cây b₁, b₂,…,b_n. Nếu trồng loại cây j trên đất i sẽ cho năng suất là N_ij (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

* 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à a_ij (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 X_ij 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 B₁, B₂,…,B_n 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à b₁, b₂,…,b_n. Còn a₁, a₂,…,a_m 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 q_ij

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

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

Dạng bài toán này bị khuyết biến X_iojo . Ta đưa thêm biến giả q_iojo với q_iojo=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 a_ij đượ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ị: 10³đ):

	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; P_ij là năng suất thiết bị i được bố trí trên cầu tàu j.
• Gọi x_ij là thiết bị xếp dỡ i đuợc bố trí tại vị trí thứ j.
• x_ij = 0 nếu i không được bố trí tại j.
• x_ij = 1 nếu i được bố trí tại j.
• Mô hình bài toán.

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:

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

+ 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:

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

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

3. 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à T_i ( ngày/tàu). Năng suất vận chuyển của tàu i trên tuyến j là P_ij (tấn km/tàu – ngày). Tổng khối lượng hàng trên tuyến j là Q_j (tấn). Lãi của tàu i trên tuyến j là L_ij. Số tàu kiểu i là K_i (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 x_ij là thời gian khai thác của tàu i trên tuyến j.

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 ( m³) đượ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à C_j . Hệ số chất xếp U_j (m³/tấn). Lập kế hoạch xếp hàng tối ưu.
• Lập bài toán:

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

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:

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

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

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

p₁,p₂: 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

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

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

I_m : 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).

J_c: 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.

J_m: 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.

C^c_ijr: 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.

C^m_ijr: 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

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

Q_jr: 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).

Trong đó:

x_ij: 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

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

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

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

N_i: 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, P₁,P₂….P_m trong đó P là thiết bị chính tiền phương; còn P₁,P₂….P_m 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,N₁,……N_m.