BÀI TOÁN ỨNG DỤNG của bài TOÁN vận tải

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (165.08 KB, 12 trang )

CHƯƠNG 3: CÁC BÀI TOÁN ỨNG DỤNG
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 Ai → Bj (i = 1, m, j= 1, n ). Cự ly
từ Ai → Bj là lij (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 Xij là số tấn xe chạy rỗng từ điểm Bj về Ai
m

n

f ( x ) = ∑∑lij .xij →min
i =1 j =1

n

x
∑
j=
1

ij

m

x
∑
i=
1

ij

=ai

(i = 1, m)

=b j

( j = 1, 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à a 1, a2,…,am (ha). Dự
định để trồng n loại cây b 1, b2,…,bn. 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à aij (i = 1, m, j= 1, n ). 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
m

n

f ( x ) = ∑∑ai .xij →max
i =1 j =1

m

x

∑
i=
1

ij

n

x
∑
j=
1

ij

=1
=1

xij = 0 hoặc = 1, ∀i, j
4. Bài toán bố trí cán bộ theo chức vụ công tác.
1

* 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
m

n

f ( x ) = ∑∑qij .xij →max
i =1 j =1

n

x
∑
j=
1

ij

m

x
∑

ij

i=
1

=ai

(i = 1, m)

=b j

( j = 1, n)

xij ≥ 0, ∀i, 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 jo. Khi
đó hệ ràng buộc của bài toán như sau:
n

x
∑
j=
1

ij

=ai

n

x
∑
j=
1

io j

( i ≠ io)

=aio ( i = io)

Và:
m

x
∑
i=
1

ij

m

x
∑
i=
1
i ≠i o

ij

=b j
=b j 0

(j ≠ jo)
(j = jo)

Dạng bài toán này bị khuyết biến X iojo. 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
2

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
B
C
D
E
F
G

0,8
0,8
0,7
–

0,9
0,8
0,7
0,8
0,7
–

0,6
0,7
0,8
0,9
0,7
–

0,4
0,5

0,6
0,7
0,6
0,8
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
3

– 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đ):
A
B
C

D
8
12

15

E
13
9
12

F
7
15
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
Đi
A
A
B
D
D
E
E
E

Loại hàng

Đến
D
B
C
A
E
A
B
C

Kim khí
Kim khí
Than
Quặng
Gỗ
Gỗ
Đá
Đá

Khối lượng

Số phương tiện vận

(103T)
120
90
180
60

30
130
50
50

chuyển (103T)
120
90
180
60
30
130
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

B
295
0

C

235
252
0

D
126
195
170
0

E
147
180
186
128
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.
4

–

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.
m

n

i =1

j =1

f ( x) = ∑ .∑ Pij .xij → max

m

∑x

ij

= 1( j = 1, n)

ij

= 1(i = 1, m)

i =1
n

∑x
j =1

B: Giải bài toán vận tải trên máy tính.
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:
m

n

∑ .∑ d .x
i =1

j =1

ij

ij

≤d

Ma trận vào máy tính:
2. Bài toán vận tải hạn chế về khả năng thông qua.
m

n

i =1

j =1

f ( x) = ∑ .∑ Cij .xij → min
n

∑x

ij

= ai (i = 1, m)

ij

= b j ( j = 1, n)

j =1
m

∑x

i =1

0 ≤ xij ≤ qij (i = 1, m; j = 1, n)
Với qij là khả năng thông qua của loại hàng i trên tuyến j.
Ma trận vào máy tính:
5

III: Bài toán phân phối.
1. Phát biểu bài toán.
1 xí nghiệp vận tải có m loại tàu (phương tiện) với số lượng mỗi loại là
tuyến. Khối lượng kế hoạch trên tuyến j là

ai (i = 1, m)

hoạt động trên n

b j ( j = 1, n) .

Biết năng suất loại tàu ( phương tiện) i trên tuyến j là Pij. Chi phí cho phương tiện i trên tuyến j trong
suốt thời gian khai thác là Cij.
Hãy lập kế hoạch bố trí phương tiện sao cho hiệu quả nhất.
2. Lập bài toán.
Gọi số phương tiện i hoạt động trên tuyến là xij.
Hàm mục tiêu:
m

n

i =1

j =1

f ( x) = ∑ .∑ Cij .xij → min
n

∑x
j =1

ij

≤ ai (i = 1, m)

m

∑ P .x
i =1

ij

ij

= (≥)b j ( j = 1, n)

xij ≥ 0∀(i = 1, m; j = 1, n)
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:
Năng suất vận chuyển (tấn/tàu)
Chi phí (106đ/T)

Số phương
Kiểu tàu
HP – SG
HP – QNi HP – QNh
1
2
3
tiện ( tàu)
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 của 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:
a. 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).
6

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.
b. 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.
m

n

i =1

j =1

f ( x ) = ∑K i .∑Lij .xij →max
n

∑x
j =1

ij

≤ Ti (i =1, m)

m

∑K .P .x
i =1

i

ij

ij

= QJ ( j =1, n)

xij ≥ 0∀i =1, m; j =1, n
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
1
2
ΣQj

Năng suất (1000T/tàu-ngày)
Tuyến 1
Tuyến 2
1,0
2,0
1,5
1,5
500.103(T)
100.103(T)

Lãi (1000USD/tàu-ngày)

Tuyến 1
Tuyến 2
0,5
0,8
0,7
1,0

Tổng thời gian khai

Số tàu

thác (ngày/tàu)
200
150

(chiếc)
2
3

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

f ( x) = ∑ C j .x j → max
j =1

n
x j ≤D
∑

j =1

n
x j .u j ≤w

∑
j =1

x ≥0∀=
j
1, n
 j


7

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.
a. 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.
b. 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.

m

n

i =1

j =1

f ( x) = ∑ .∑ ( Fij − Cij ).xij → max
Có m kiểu tàu hoạt động trên n tuyến.
tij là thời gian khai thác 1 chuyến của tàu i trên tuyến j.
Ti là tổng thời gian trong năm của tàu i.
Fij và Cij là thu nhập và chi phí của tàu loại i trên tuyến j.
Pij năng suất vận chuyển 1 chuyến của tàu i trên tuyến j.
Qj khối lượng vận tải kế hoạch trên tuyến j.

n
∑tij .xij ≤ Ti (i =1, m)
 j =1
m
 P .x ≤ Q ( j =1, n)
∑ ij ij j

 i =1
 Nếu kinh doanh cả hệ thống;

f = ∑. ∑ C m ij .x m ij +
i∈Im

j∈Jm

∑ .∑ C

i∈I p1

j∈Jp1

p1
ij

.x p1ij +

+ ∑ .∑ C l ij .x l ij + ∑. ∑ C cij .x c ij → min
i∈I l

j∈Jl

i∈I c

j∈Jc

ĐKRB:

∑ .∑ q

i∈Im

m

j∈Jm

ij

.x mij + ∑. ∑ q c ij .x c ij + ∑ .∑ q l ij .x l ij ≥ Q j

∑ .∑ q

i∈Im

j∈Jm

i∈I c

m
ij

.x m ij −

j∈Jc

i∈I l

∑ .∑ q

p1
ij

i∈I p1

j∈Jp1

j∈Jl

.x p1ij = 0

8

∑ .∑ C

i∈I p 2

j∈Jp 2

p2
ij

.x p 2ij

∑ .∑ q

i∈Im

j∈Jm

∑t

m
ij

j∈Jm

∑t

c

j∈Jc

∑t

j∈Jp1

j∈Jl

.x mij −

∑ .∑ q

i∈I p 2

j∈Jp 2

p2
ij

.x p 2ij = 0

.x m ij ≤ Ti m (i ∈ I m )

.x p1ij ≤ Ti p1 (i ∈ I p1 )

p2
ij

j∈Jp 2

∑t

ij

c
c
.
x
≤
T
ij
ij
i (i ∈ I c )

p1
ij

∑t

m

l
ij

.x p 2ij ≤ Ti p 2 (i ∈ I p 2 )

.x l ij ≤ Ti l (i ∈ I l )

xijm ≥ 0∀i ∈ I m, j ∈ J m
xijc ≥ 0∀i ∈ I c, j ∈ J c
xijl ≥ 0∀i ∈ I l, j ∈ J l
xij p1 ; xij p 2 ≥ 0∀i ∈ I … j ∈ J …
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:
a. Đặ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
9

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.
b. Mô hình bài toán


F = ∑ ∑
r∈R 
i∈I c

∑C
j∈J c

c
ijr

.x c ijr + ∑
i∈I m

∑ (C

j∈J m

m
ijr

)

+ [ E ] .k m ijr .x mijr

} → min(1)

ĐKRB:

∑ q c ijr .x c ijr + ∑ q mijr .x m ijr ≥ Q jr
 i∈Ic
i∈I m

∑ t c ijr .x c ijr ≤ T c ir

Với

x c ijr ≥ 0(i ∈ I c ; j ∈ J c ; r ∈ R )
x m ijr ≥ 0(i ∈ I m ; j ∈ J m ; r ∈ R )

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.
10

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).
m

n

f ( x) = ∑∑ Cij .xij → min
i =1 j =1

m
∑ Pij .xij = G j ( j = 1.n)
 i =1
 n
ĐK ∑ xij ≤ N i (i = 1, m)
 j =1
 x ≥ 0∀i = 1, m; j = 1, n
 ij

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.
b. 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.
Một chu kỳ thao tác của thiết bị chính là Tck phút; thời gian các thiết bị khác xử lý 1 chu trình khai thác
của thiết bị chính là tij ( i = 1, m; j = 1, n ).
Thời gian tác nghiệp trong ca là TTNca
11

Hãy xây dựng quy trình công nghệ đạt hiệu quả cao nhất.

–

Lập mô hình:

Gọi số chu trình để phục vụ kho j của thiết bị chính là xj
n

f = ∑ x j → max
j =1

 n
T TN ca
∑ x j ≤
TCK
 j =1

 n
TN
ĐKRB: ∑ tij .x j ≤ T ca .N i (i = 1, m)
 j =1
 x ≥ 0∀i, j
 ij



12

ij = ai ( i = 1, m ) = b j ( j = 1, 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 quy hoạnh sử dụng tương ứng là a 1, a2, …, am ( ha ). Dựđịnh để trồng n loại cây b 1, b2, …, bn. Nếu trồng loại cây j trên đất i sẽ cho hiệu 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 thao tác trên n máy. Tỷ lệ loại sản phẩm tốt của côngnhân i trên máy j là aij ( i = 1, m, j = 1, n ). Hãy lập kế hoạch phân công đứng máy sao chotổng tỷ suất mẫu sản phẩm tốt của xí nghiệp sản xuất trong 1 kỳ kế hoạch là lớn nhất. * Gọi Xij là giải pháp công nhân i thao tác trên máy jf ( x ) = ∑ ∑ ai. xij → maxi = 1 j = 1 i = ijj = ij = 1 = 1 xij = 0 hoặc = 1, ∀ i, j4. Bài toán sắp xếp cán bộ theo chức vụ công tác làm việc. * Có n vị trí công tác làm việc B1, B2, …, Bn còn thiếu cán bộ và số cán bộ còn thiếu tại những vị trínày là b1, b2, …, bn. Còn a1, a2, …, am là số cán bộ được huấn luyện và đào tạo ra trường theo những chuyênmôn khác nhau hay cán bộ mới chuyển đến chưa sắp xếp công tác làm việc. Khi phân công công táccho cán bộ hoàn toàn 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 việc làm củangành đó và hoàn toàn có thể công tác làm việc ở 1 số ít ngành tương quan. Trường hợp 2 : Có cán bộ chỉ công tác làm việc ở 1 vị trí nhất định mà không công tác làm việc được ở cácvị trí khác. Đánh giá mức độ tương thích của cán bộ i với việc làm loại j người ta dung chỉ số thích ứngqij * Gọi Xij là số cán bộ loại i được phân đến vị trí jf ( x ) = ∑ ∑ qij. xij → maxi = 1 j = 1 j = ijiji = = ai ( i = 1, m ) = b j ( j = 1, n ) xij ≥ 0, ∀ i, j * Với bài toán ở trường hợp ( 2 ) : Giả sử cán bộ i o không tương thích với việc làm loại jo. Khiđó hệ ràng buộc của bài toán như sau : j = ij = aij = io j ( i ≠ io ) = aio ( i = io ) Và : i = iji = i ≠ i oij = b j = b j 0 ( j ≠ jo ) ( j = jo ) Dạng bài toán này bị khuyết biến X iojo. 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 MNếu trong giải pháp tối ưu những biến giả ( tại ô cấm ) bằng 0 thì đó là giải pháp tốiưu của bài toán khởi đầ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 thương mại – 2 nhân viên cấp dưới kinh doanh thương mại – 2 bảo vệ cơ quanSau khi phỏng vấn, có số người có những bằng cấp sau được nhận vào : – Bằng ĐH kinh tế tài chính 3 người : Hà, Kiên, Hùng – { A, B, C } – Bằng cao đẳng kinh tế tài chính 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 việc làm được kiểm tra bằng trắc nghiệm như sau : TênPhó phòngTrợ lýNhân viênkinh doanhBảo vệ0, 80,80,70,90,80,70,80,70,60,70,80,90,70,40,50,60,70,60,80,8 Biết thêm vị trí phó phòng không hề sử dụng cán bộ chưa tốt nghiệp ĐH. 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 sắp xếp cán bộ vàocác vị trí tương thích 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 sắp xếp tàu luân chuyển hàng về cảng cần loại hàng phù hợpCho 1 nhà máy sản xuất luân chuyển 1 kế hoạch luân chuyển hàng như sau : Cần luân chuyển hàng từ – cảng A với khối lượng 9.000 T than, 6.000 T quặng – cảng B với khối lượng 3.000 T clinke – cảng C với khối luợng 7.000 T than, 1.000 T clinketới cảng nhận hàng là D, E, F biết : – Cảng D cần nhận 8.000 T than hoặc quặng, 1.000 T clinke – Cảng E cần nhận 12.000 T than, 2000 T quặng hoặc clinke – Cảng F cần nhận 3.000 T loại nào cũng đượcChi phí luân chuyển giữa những cảng như sau ( đ. vị : 103 đ ) : 121513121510B ài tập lập sơ đồ hoạt động giải trí tối ưu cho đội tàuCông việc luân chuyển hàng theo 1 kế hoạch cho trước hoàn toàn có thể được triển khai theo nhiều sơ đồ khác nhau ( hành trình dài vận doanh liên tục ) yếu tố đặ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 so 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ệnchạy rỗng là tối ưu ( tối thiểu ). Việc tối ưu theo tiêu chuẩn này thường dẫn đến hiệu suất cao là hiệu suất hoạtđộng của phương tiện đi lại cao hoặc thông số tận 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 luân chuyển như sau : NơiĐiLoại hàngĐếnKim khíKim khíThanQuặngGỗGỗĐáĐáKhối lượngSố phương tiện đi lại vận ( 103T ) 1209018060301305050 chuyển ( 103T ) 1209018060301305050H ãy lập kế hoạch chạy tàu tối ưu ( sơ đồ hoạt động giải trí tối ưu ) biết cự ly luân chuyển : 295235252126195170147180186128G iải : Bài toán sắp xếp 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 kèm theo là 1 thiết bị xếp dỡ chỉ thao tác ở 1 vị trí xếp dỡsao cho hiệu suất hàng loạt thiết bị trên cầu tàu là Max ; Pij là hiệu suất thiết bị i được sắp xếp trêncầu tàu j. Gọi xij là thiết bị xếp dỡ i đuợc sắp xếp tại vị trí thứ j.xij = 0 nếu i không được sắp xếp tại j.xij = 1 nếu i được sắp xếp tại j. Mô hình bài toán. i = 1 j = 1 f ( x ) = ∑. ∑ Pij. xij → max ∑ xij = 1 ( j = 1, n ) ij = 1 ( i = 1, m ) i = 1 ∑ xj = 1B : Giải bài toán vận tải trên máy tính. 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 đi lại. Có những thông số kỹ thuật như bài toán vận tải cổ xưa, nhưng cho thêm điều kiện kèm theo hạn chế về số phương tiện đi lại : + dij là số tấn phương tiện đi lại để chở hết 1 đơn vị chức năng hàng từ Ai → Bj. + d là tổng số tấn phương tiện đi lại hiện có. → có thêm điều kiện kèm theo về số tấn phương tiện đi lại : ∑. ∑ d. xi = 1 j = 1 ijij ≤ dMa trận vào máy tính : 2. Bài toán vận tải hạn chế về năng lực trải qua. i = 1 j = 1 f ( x ) = ∑. ∑ Cij. xij → min ∑ xij = ai ( i = 1, m ) ij = b j ( j = 1, n ) j = 1 ∑ xi = 10 ≤ xij ≤ qij ( i = 1, m ; j = 1, n ) Với qij là năng lực trải qua của loại hàng i trên tuyến j. Ma trận vào máy tính : III : Bài toán phân phối. 1. Phát biểu bài toán. 1 nhà máy sản xuất vận tải có m loại tàu ( phương tiện đi lại ) với số lượng mỗi loại làtuyến. Khối lượng kế hoạch trên tuyến j làai ( i = 1, m ) hoạt động giải trí trên nb j ( j = 1, n ). Biết hiệu suất loại tàu ( phương tiện đi lại ) i trên tuyến j là Pij. giá thành cho phương tiện đi lại i trên tuyến j trongsuốt thời hạn khai thác là Cij. Hãy lập kế hoạch sắp xếp phương tiện đi lại sao cho hiệu suất cao nhất. 2. Lập bài toán. Gọi số phương tiện đi lại i hoạt động giải trí trên tuyến là xij. Hàm mục tiêu : i = 1 j = 1 f ( x ) = ∑. ∑ Cij. xij → min ∑ xj = 1 ij ≤ ai ( i = 1, m ) ∑ P.. xi = 1 ijij = ( ≥ ) b j ( j = 1, n ) xij ≥ 0 ∀ ( i = 1, m ; j = 1, n ) 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 luân chuyển từ HP đến SG 100.000 tấn ; HP – QuảngNinh : 8.000 tấn và từ HP – Quy Nhơn : 20.000 tấn. Biết những thông số kỹ thuật sau : Năng suất luân chuyển ( tấn / tàu ) Ngân sách chi tiêu ( 106 đ / T ) Số phươngKiểu tàuHP – SGHP – QNi HP – QNhtiện ( tàu ) 500030004000190128180800020005000212165185L ập giải pháp sắp xếp tàu sao cho luân chuyển hết khối lượng hàng hoá nhu yếu hiệu suất cao nhất. Viết matrận vào máy tính. IV : Ứng dụng của bài toán phân phối trong vận tải biển. 1. Bài toán sắp xếp tàu đạt doanh thu cao nhất : a. 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 giải trí trên n tuyến. Thời gian khai thác trong năm của tảu Itrên những tuyến là Ti ( ngày / tàu ). Năng suất luâ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 trung bình trong ngày ( USD or đ / tàu – ngày ). Lập phương án sắp xếp đội tàu của nhà máy sản xuất sao cho luân chuyển hết khối lượng hàng hoá nhu yếu đạthiệu quả cao nhất. b. Lập bài toán. Gọi xij là thời hạn khai thác của tàu i trên tuyến j. i = 1 j = 1 f ( x ) = ∑ K i. ∑ Lij. xij → max ∑ xj = 1 ij ≤ Ti ( i = 1, m ) ∑ K. P.. xi = 1 ijij = QJ ( j = 1, n ) xij ≥ 0 ∀ i = 1, m ; j = 1, nVí dụ : Lập phương án sắp xếp tàu sao cho luân chuyển hết khối lượng hàng hoá nhu yếu và hiệu quảnhất biết : Kiểu tàuΣQjNăng suất ( 1000T / tàu-ngày ) Tuyến 1T uyến 21,02,01,51,5500. 103 ( T ) 100.103 ( T ) Lãi ( 1000USD / tàu-ngày ) Tuyến 1T uyến 20,50,80,71,0 Tổng thời hạn khaiSố tàuthác ( ngày / tàu ) 200150 ( chiếc ) 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ướcvậ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 : f ( x ) = ∑ C j. x j → maxj = 1  nx j ≤ D  j = 1  nx j. u j ≤ w  j = 1 x ≥ 0 ∀ = 1, n  j3. Bài toán phân chia tàu biển, tàu sông, tàu biển pha sông va tàu chở sà lan trong mạng lưới hệ thống vận tảiBắc – Nam của Nước Ta. a. Phát biểu bài toán : bài toán tựa như như bài toán 1 trong trường hợp kinh doanh thương mại độc lập. b. Lập bài toán : Nếu kinh doanh thương mại độc lập : xij là số chuyến tàu loại i khai thác trên tuyến j. i = 1 j = 1 f ( x ) = ∑. ∑ ( Fij − Cij ). xij → maxCó m kiểu tàu hoạt động giải trí trên n tuyến. tij là thời hạn khai thác 1 chuyến của tàu i trên tuyến j. Ti là tổng thời hạn trong năm của tàu i. Fij và Cij là thu nhập và ngân sách của tàu loại i trên tuyến j. Pij hiệu suất luân chuyển 1 chuyến của tàu i trên tuyến j. Qj khối lượng vận tải kế hoạch trên tuyến j.  n  ∑ tij. xij ≤ Ti ( i = 1, m )  j = 1  m  P.. x ≤ Q. ( j = 1, n ) ∑ ij ij j  i = 1  Nếu kinh doanh thương mại cả mạng lưới hệ thống ; f = ∑. ∑ C m ij. x m ij + i ∈ Imj ∈ Jm ∑. ∑ Ci ∈ I p1j ∈ Jp1p1ij. x p1ij + + ∑. ∑ C l ij. x l ij + ∑. ∑ C cij. x c ij → mini ∈ I lj ∈ Jli ∈ I cj ∈ JcĐKRB : ∑. ∑ qi ∈ Imj ∈ Jmij. x mij + ∑. ∑ q c ij. x c ij + ∑. ∑ q l ij. x l ij ≥ Q. j ∑. ∑ qi ∈ Imj ∈ Jmi ∈ I cij. x m ij − j ∈ Jci ∈ I l ∑. ∑ qp1iji ∈ I p1j ∈ Jp1j ∈ Jl. x p1ij = 0 ∑. ∑ Ci ∈ I p 2 j ∈ Jp 2 p2ij. x p 2 ij ∑. ∑ qi ∈ Imj ∈ Jm ∑ tijj ∈ Jm ∑ tj ∈ Jc ∑ tj ∈ Jp1j ∈ Jl. x mij − ∑. ∑ qi ∈ I p 2 j ∈ Jp 2 p2ij. x p 2 ij = 0. x m ij ≤ Ti m ( i ∈ I m ). x p1ij ≤ Ti p1 ( i ∈ I p1 ) p2ijj ∈ Jp 2 ∑ tijijiji ( i ∈ I c ) p1ij ∑ tij. x p 2 ij ≤ Ti p 2 ( i ∈ I p 2 ). x l ij ≤ Ti l ( i ∈ I l ) xijm ≥ 0 ∀ i ∈ I m, j ∈ J mxijc ≥ 0 ∀ i ∈ I c, j ∈ J cxijl ≥ 0 ∀ i ∈ I l, j ∈ J lxij p1 ; xij p 2 ≥ 0 ∀ i ∈ I … j ∈ J … Với m : tín hiệu chỉ tàu biểnl : tín hiệu chỉ tàu chở sà lanc : tín hiệu chỉ tàu pha sông biểnp1, p2 : tín hiệu chỉ tàu sông ở phía bắc và phía nam4. Bài toán tối ưu hoá tăng trưởng đội tàu trên cơ sở sử dụng hiệu suất cao đội tàu hiện có của mình : a. Đặt vấn đềNgành vận tải biển là 1 mạng lưới hệ thống kinh tế tài chính rất phức tạp. Hệ thống vận tải biển được cấu trúc từ cáctiểu mạng lưới hệ thống sau : đội tàu, cảng, nhà máy sản xuất đóng mới, bộ phận đáp ứng định mức hàng hoá. Trong đó đội tàu là phần trọng tâm hầu hết. Cho nên việc tăng trưởng đội tàu có ý nghĩa quan trọngvì nó giúp cho việc luân chuyển hàng hoá của chính công ty cũng như để xuất khẩu dịch vụ vậntải. Trong nền kinh tế tài chính quốc tế lúc bấy giờ, sự tăng trưởng của khoa học kỹ thuật và sự tăng trưởng của thôngtin có tác động ảnh hưởng lớn đến sự tăng trưởng của ngành vận tải biển. Các bài toán KT – XH của VTB đòihỏi ta phải xử lý 1 lượng thông tin khổng lồ mới hoàn toàn có thể tìm thấy 1 giải pháp tối ưu tronghàng trăm nghìn giải pháp hoàn toàn có thể xảy ra. Nếu những công ty VTB chỉ dựa vào kế hoạch công tácthì không hề tìm được giải pháp tối ưu. Sự vận dụng những quy mô toán kinh tế với sự giúp sức củamô hình đội tàu giúp những cán bộ khai thác tìm được lời giải tối ưu cho những bài toán kinh tế tài chính về tốiưu hoá tăng trưởng đó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áchcó hiệu suất cao có 1 ý nghĩa cấp bách trong hàng loạt ngành hàng hải và trong tổng thể những công ty vận tảibiển. Mục tiêu của bài toán tối ưu hóa tăng trưởng đội tàu là tìm ra chủng loại tàu cần bổ xung cho tươnglai, vốn góp vốn đầu tư cho từng năm để tăng trưởng đội tàu sao cho bảo vệ luân chuyển hết khối lượnghàng hoá trên toàn bộ những tuyến mà công ty đã khai thác với hiệu suất cao kinh tế tài chính cao nhất. so với bàitoán tối ưu hoá tăng trưởng đội tàu trong tương lai trên cơ sở sử dụng hiệu suất cao đội tàu hiện có tadùng chỉ tiêu hiệu suất cao là min ngân sách. giá thành biến hóa tổng hợp trong trường hợp này được tính như sau : + Ngân sách chi tiêu khấu hao ( gồm cả ngân sách khấu hao với tàu cũ khai thác trong tương lai ). + Chi tiêu khai thác tàu mới trong tương lai ( không tính ngân sách khấu hao ). + Phần tịch thu vốn góp vốn đầu tư cho những tàu cần bổ xung trong tương lai. b. Mô hình bài toán   F = ∑  ∑ r ∈ R   i ∈ I c ∑ Cj ∈ J cijr. x c ijr + ∑ i ∈ I m ∑ ( Cj ∈ J mijr + [ E ]. k m ijr. x mijr } → min ( 1 ) ĐKRB :  ∑ q c ijr. x c ijr + ∑ q mijr. x m ijr ≥ Q jr  i ∈ Ici ∈ I m  ∑ t c ijr. x c ijr ≤ T c irVớix c ijr ≥ 0 ( i ∈ I c ; j ∈ J c ; r ∈ R ) x m ijr ≥ 0 ( i ∈ I m ; j ∈ J m ; r ∈ R ) Trong đó : r : là chỉ số năm lập kế hoạch r = 1 → RR : là tập hợp số năm lập kế hoạchi : là chỉ số loại tàu vận tải biểnj : là chỉ số tuyến vận tảiIc : là tập hợp hay số lượng hay những kiểu tàu cũ đang khai thác. Im : là tập hợp hay số lượng những kiểu tàu mới ( tất cả chúng ta định đưa vào thị trường để bổ xung trong tươnglai ). Jc : tập hợp hay sốlượng những sơ đồ công nghệ tiên tiến mà trên đó những tàu VTB cũ hoàn toàn có thể khai thác được. 10J m : là số lượng những sơ đồ công nghệ tiên tiến mà trên đó những tàu VTB mới hoàn toàn có thể khai thác được. Ccijr : ngân sách khai thác trong 1 chuyến đi của tàu cũ i trên tuyến j trong năm r. Cmijr : ngân sách 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 rTcir : thời hạn trong năm của tàu cũ i hoàn toàn có thể khai thác được trong năm rQjr : khối lượng luân chuyển 1 chuyến đi của tàu i trên tuyến j trong năm r [ E ] : thông số hiệu suất cao góp vốn đầu tư của ngành VTB5. Một số bài toán tối ưu cho nhà máy sản xuất xếp dỡ. a. Bài toán phân phối thiết bị xếp dỡ vào vị trí thao tác ( vận dụng cho thiết bị xếp dỡ có năng lực dịchchuyển ). f ( x ) = ∑ ∑ Cij. xij → mini = 1 j = 1  m  ∑ Pij. xij = G j ( j = 1. n )  i = 1  nĐK  ∑ xij ≤ N i ( i = 1, m )  j = 1  x ≥ 0 ∀ i = 1, m ; j = 1, n  ijTrong đó : xij : số TBXD loại i thao tác tại vị trí ji : chỉ số loại thiết bị xếp dỡj : chỉ số vị trí làm việcPij : hiệu suất hàng loạt của 1 TBXD i khi thao tác tại jCij ; ngân sách khai thác của 1 TBXD i khi thao tác tại jGij : lượng hàng cần xếp dỡ trong kỳ kế hoạchNi : số lượng TBXD kiểu i. b. Bài toán thiết kế xây dựng tiến trình công nghệ tiên tiến ship hàng cho kho đạt hiệu suất cao 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 những loại thiết bị là P., P1, P2 …. Pm trong đó P. là thiết bị chínhtiền phương ; còn P1, P2 …. Pm là thiết bị Giao hàng cho những kho 1 → N với số lượng thiết bị tương ứng làN, N1, … … Nm. Một chu kỳ luân hồi thao tác của thiết bị chính là Tck phút ; thời hạn những thiết bị khác giải quyết và xử lý 1 quy trình khai tháccủa thiết bị chính là tij ( i = 1, m ; j = 1, n ). Thời gian tác nghiệp trong ca là TTNca11Hãy kiến thiết xây dựng quá trình công nghệ tiên tiến đạt hiệu suất cao cao nhất. Lập quy mô : Gọi số quy trình để ship hàng kho j của thiết bị chính là xjf = ∑ x j → maxj = 1  nT TN ca  ∑ x j ≤ TCK  j = 1  nTNĐKRB :  ∑ tij. x j ≤ T ca. N i ( i = 1, m )  j = 1  x ≥ 0 ∀ i, j  ij12

Source: https://mindovermetal.org
Category: Ứng dụng hay