Bai toan van tai

Ta có thể thấy rằng dùng phương pháp tọa độ 1 chiều hay 2 chiều về thực chất đều là phương pháp lấy trọng tâm. Tuy đã có xét đến lượng vận chuyển những chưa xét chi phí vận chuyển. Chi phí vận chuyển không những phụ thuộc vào lượng vận chuyển mà còn phụ thuộc vào phương thức vận chuyển (Sắt, thủy, bộ, hàng không,…), chất lượng đường giao thông và cự ly vận chuyển nghĩa là phụ thuộc vào cước vận chuyển
Mặt khác tại địa điểm định phí, biến phí cũng khác nhau. Do đó cần xem xét vấn đề 1 cách toàn diện hơn có xét đến chi phí sản xuất cộng với chi phí vận chuyển.
Ta có thể dùng bài toán vận tải để giải quyết vấn đề này, từ phương pháp này ta có thể tìm vị trí đặt xí nghiệp, nhà máy sao cho cực tiểu các chi phí vận tải đến xí nghiệp , chi phi sản xuất liên quan đến vị trí, chi phí vận tải liên quan tới các điểm tiêu thụ.
Cách giải bài toán vận tải:
Công Ty Vixang cần mở thêm 1 cửa hàng mới, công ty hiện có 2 địa điểm 3, 4 để chọ lựa với Các chi phí vận chuyển cho mỗi tháng là cho như sau:


Cửa hàng 1
Cửa hàng 2
Cửa hàng 3
Cửa hàng 4

Cơ sở sản xuất A
3
4
5
3

Cơ sở sản xuất B
6
7
8
7

Cơ sở sản xuất C
9
10
11
5

Mức sản xuất và tiêu thụ trong mỗi tháng là:
Cơ sở sản xuất A : 60
Cơ sở sản xuất B : 70
Cơ sở sản xuất C : 50
Cửa hàng 1: 50
Cửa hàng 2: 60
Cửa hàng 3: 70
Cửa hàng 4: 70
Giải:
Gọi i là các cơ sở sản xuất (i= A, B, C)
ai : mức sản xuất của nhà máy i
J la các cửa hàng ( J= 1, 2, 3, 4)
bj mức tiêu thụ của cửa hàng J
cịj : chi phí vận chuyển từ cơ sở I đến cửa hàng j
ta có mô hình giải toán sau:
minf=
Cij xij

= ai (i= A, B, C)

= bj (j = 1, 2, 3, 4)
xij ≥ 0

Phương án đầu có thể lập theo 1 trong các phương pháp sau:
Góc tây bắc
Cmin
Foghen

Ta sử dụng bài toán vận tải cho 2 địa điểm 3, 4

Dùng cho địa điểm 3:
Chọn phương án ban đầu:



50
60
70

60
3
50
4
10
5
-

70
6
-
7
50
8
20

50

9
-
10
-
11
50



Sau khi đã có phương án đầu, Ta tiến hành phương pháp thế vị để kiểm tra tính tối ưu.
Ui – Thế vị của hàng i
Vj - thế vị của cột j
Công thức tính:
ui + vj = cij đối với các ô chọn (ô có xij > 0). Cho 1 ui hoặc vj nào đó bằng 0 rồi suy ra các ui, vj khác

Dùng thế vị tính ui, vj và ∆



50
60
70

60
3
50
4
10
5
0

70
6
0
7
50
8
20

50

9
0
10
0
11
50


V1= 3 V2= 4 V3= 5
Kiểm tra các ô loại (ô có xij = 0) theo công thức
∆ij = ui + vj – cij
Nếu mọi ∆ij ≤ 0 phương án tối ưu

Vì mọi ∆ij ≤ 0 nên phương pháp vận chuyển trên là tối ưu
Chi phí vận chuyển là: 3*50 + 4*10 + 7*50 + 8*20 + 11*50 = 1250

Đối với địa điểm 4:

Chọn phương án ban đầu:





50
60
70

60
3
50
4
10
3
-

70
6
-
7
50
7
20

50

9
-
10
-
5
50



Dùng thế vị tính ui, vj và ∆ij



50
60
70

60
3
50
4 -
10
3 +
1

70
6
0
7 +
50
7 -
20

50

9
-5
10
-5