Bài toán vận tải mở rộng
GV : Phạm Thị Hoài
1 / 49
Viện Toán ứng dụng và Tin học Trường Đại học Bách khoa Hà Nội
Nội dung chính 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
2 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán không cân bằng thu phát
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
3 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Bài toán đặt ra cung lớn hơn cầu
m X
n X
Tức là:
i=1
j=1
ai > bj
m X
n X
Mô hình bài toán:
i=1
j=1
n X
min f (x) = (1) cijxij
j=1 m X
v.đ.k. i = 1, · · · , m xij ≤ ai,
j = 1, · · · , n xij = bj,
i=1 xij ≥ 0,
4 / 49
i = 1, · · · , m, j = 1, · · · , n.
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Phương pháp giải
m X
n+1 X
Ta chỉ cần thêm vào điểm thu giả với cước phí tại các ô đó đều là 0. Bài toán với m điểm phát và n+1 điểm thu là :
i=1
j=1
n+1 X
min f (x) = (2) cijxij
j=1 m X
v.đ.k. i = 1, · · · , m xij = ai,
j = 1, · · · , n + 1 xij = bj,
i=1 xij ≥ 0,
m X
n X
i = 1, · · · , m, j = 1, · · · , n + 1.
i=1
j=1
5 / 49
Với bn+1 = ai − bj
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1
Xét Bài toán không cân bằng thu phát được cho bởi bảng vận tải dưới đây
bj 80 70 100 90 ai
6 5 3 1 100
9 7 5 8 160
6 / 49
2 9 4 6 140
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1(tiếp)
Ta thêm trạm thu giả n+1=5 với yêu cầu là b5 = 400 − 340 = 60 và đặt c15 = c25 = c35 = 0.
bj 80 70 100 90 60 ai
6 5 3 1 0 100
9 7 5 8 0 160
7 / 49
2 9 4 6 0 140
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1(tiếp)
vj −4 −2 0 0 1
bj ui 80 70 100 60 90 ai
8 / 49
6 5 3 1 0 − + 100 0 −10 −5 −5 40 60 9 7 5 8 0 + − 160 7 −6 70 40 50 7 2 9 4 6 0 140 6 −3 80 60 1 6
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1(tiếp)
vj 3 7 5 1 0
bj ui 80 70 100 90 60 ai
9 / 49
6 5 3 1 0 0 100 −3 2 2 90 10 9 7 5 8 0 0 160 −6 −7 70 40 50 2 9 4 6 0 −1 140 −3 −6 −1 80 60
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1(tiếp)
vj −2 1 5 3 1
bj ui 80 70 100 90 60 ai
10 / 49
6 5 3 1 0 100 0 −5 −2 0 10 90 9 7 5 8 0 160 2 −6 −5 70 30 60 2 9 4 6 0 140 1 −3 −4 −1 80 60
Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Ví dụ 1.1(tiếp)
Bảng tương ứng với phương án cực biên tối ưu x∗ của bài toán:
x∗ = 0 0 80 0 70 30 60 0 10 90 0 0 0 60 0
Trở lại bài toán ban đầu, ta có phương án vận chuyển tối ưu là
xopt = 0 0 80 0 70 30 60 0 10 90 0 0
11 / 49
với giá trị tối ưu là f (xopt) = 1160.
Bài toán không cân bằng thu phát
Cầu lớn hơn cung
Cầu lớn hơn cung Bài toán
m X
n X
Tức là:
i=1
j=1
ai < bj
m X
n X
Mô hình bài toán:
i=1
j=1
n X
min f (x) = (3) cijxij
j=1 m X
v.đ.k. i = 1, · · · , m xij = ai,
j = 1, · · · , n xij ≤ bj,
i=1 xij ≥ 0,
12 / 49
i = 1, · · · , m, j = 1, · · · , n.
Bài toán không cân bằng thu phát
Cầu lớn hơn cung
Phương pháp giải
m+1 X
n X
Ta chỉ cần thêm vào điểm phát giả với cước phí tại các ô đó đều là 0. Bài toán với m+1 điểm phát và n điểm thu là :
i=1
j=1
n X
min f (x) = (4) cijxij
j=1 m+1 X
v.đ.k. i = 1, · · · , m + 1 xij = ai,
j = 1, · · · , n xij = bj,
i=1 xij ≥ 0,
n X
m X
i = 1, · · · , m + 1, j = 1, · · · , n.
j=1
i=1
13 / 49
Với am+1 = bj − ai
Bài toán vận tải với ràng buộc bất đẳng thức
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
14 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán vận tải với ràng buộc bất đẳng thức
Bài toán
m X
n X
Trong thực tế, nhiều mô hình bài toán vận tải có dạng:
i=1
j=1
n X
min f (x) = (5) cijxij
j=1 m X
v.đ.k. i = 1, · · · , m xij ≤ ai,
j = 1, · · · , n xij ≥ bj,
i=1 xij ≥ 0,
15 / 49
i = 1, · · · , m, j = 1, · · · , n.
Bài toán vận tải với ràng buộc bất đẳng thức
Định lý tồn tại nghiệm
Định lý 1
m X
n X
Bài toán vận tải có phương án tối ưu khi và chỉ khi tổng lượng phát không bé hơn tổng lượng thu, nghĩa là
i=1
j=1
16 / 49
(6) ai ≥ bj
Bài toán vận tải với ràng buộc bất đẳng thức
Phương pháp giải
m X
n X
Trường hợp 1: Ta có
i=1
j=1
ai = bj,
tức bài toán thỏa mãn điều kiện cân bằng thu phát.
m X
n X
Trường hợp 2: Ta có
i=1
j=1
ai > bj,
17 / 49
tức tổng lượng phát lớn hơn tổng lượng thu.
Bài toán lập kho hàng
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
18 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán lập kho hàng
Bài toán
Giả sử một tập đoàn gồm m nhà máy sản xuất một loại hàng hóa với sản lượng tương ứng
19 / 49
là ai, i = 1, ..., m và họ đã sản xuất sẵn nold kho chứa hàng với trữ lượng là b1, b2, ..., bnold. Người ta định xây dựng nnew kho mới. Bài toán đặt ra là mỗi kho mới phải được thiết kế để chứ bao nhiêu hàng và tìm phương án vận chuyển hết hàng từ m nhà máy đến n = nold + nnew kho sao cho chi phí vận chuyển là nhỏ nhất với giả thiết các kho mới có thể chứa được lượng hàng không hạn chế. Cho biết cước phí vận chuyển một đơn vị hàng từ nhà máy i đến kho j là cij; i = 1, ..., m; j = 1, ..., n.
Bài toán lập kho hàng
Phương pháp giải
Phương pháp giải
m X
Ta có thể dể dàng đưa bài toán về dạng vận tải cầu vượt cung bằng việc đặt:
i=1
bj = ai, ∀j = nold + 1, ..., nold + nnew
n X
m X
Do đó, ta chỉ cần thêm điểm phát giả với lượng phát:
j=1
i=1
ai am+1 = bj −
20 / 49
và cm+1,j = 0; ∀j = 1, ..., n.
Bài toán lập kho hàng
Phương pháp giải
Phương pháp giải
m+1 X
n X
Khi đó bài toán ban đầu tương đương với bài toán sau:
i=1
j=1
n X
min f (x) = cijxij
j=1 m+1 X
v.đ.k. i = 1, · · · , m + 1 xij = ai,
j = 1, · · · , n xij = bj,
i=1 xij ≥ 0,
21 / 49
i = 1, · · · , m + 1, j = 1, · · · , n.
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1
Một liên hợp nhà máy sản xuất xi măng và đã có 3 kho. Họ dự định xây thêm 2 kho nữa (với lượng chứa tùy ý) sao cho 5 kho này có thể chứa hết xi măng cần chuyển ra khỏi các nhà máy. Thông tin về lượng phát, lượng thu được cho ở dưới. Hãy xác định trữ lượng hai kho cần xây dựng và phương án vận chuyển sau khi có hai kho này sao cho tổng chi phí vận chuyển là nhỏ nhất.
bj 75 65 80 270 270 ai
1 9 8 10 2 80
2 4 10 9 4 100
9 3 2 5 2 90
22 / 49
0 0 0 0 0 490
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1(tiếp)
3 X
Bài toán có m = 3, nold = 3, nnew = 2 và n = nold + nnew = 5.
i=1
5 X
3 X
Gán lượng thu b4 = b5 = ai = 270. Đặt điểm phát (m + 1) = 4 với lượng phát:
j=1
i=1
a4 = bj − ai = 490
23 / 49
và các cước phí c4j = 0 với ∀j = 1, 5 Giải bài toán với 4 điểm phát và 5 điểm thu: Dùng phương pháp cực tiểu chi phí tìm điểm cực biên, ta thu được: f (x0) = 940
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1(tiếp)
vj 1 5 4 10 10
bj ui 75 65 80 270 270 ai
24 / 49
10 1 9 8 2 − + 80 0 −4 −4 75 5 8 2 4 10 9 4 −1 100 −2 −7 55 45 5 9 3 2 5 2 −2 90 −10 10 80 3 6 0 0 0 0 0 + − −10 490 −9 −5 −6 220 270
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1(tiếp)
vj 0 2 2 2 2
bj ui 75 65 80 270 270 ai
25 / 49
1 9 8 10 2 80 0 −1 −7 −6 −8 80 2 4 10 9 4 100 2 −8 −7 75 25 0 9 3 2 5 2 90 0 −9 −3 −5 80 10 0 0 0 0 0 −2 490 −2 40 0 270 180
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1(tiếp)
Dễ thấy các ∆ ≤ 0 nên x∗ = là phương án tối ưu của bài toán bổ
3 X
0 0 75 25 0 0 40 0 0 0 80 0 80 0 0 0 0 10 270 180 sung.
i=1
3 X
Ta có: x∗ i4 = 0 tức là không cần thiết để xây dựng kho thứ tư.
i=1
Tương tự x∗ i5 = 90 nên kho năm cần chứa 90 đơn vị hàng hóa.
Sau khi đã xây dựng hai kho này, phương án vận chuyển tối ưu là:
26 / 49
xopt = 0 0 75 25 0 0 0 80 0 0 0 0 80 0 10
Giá trị tối ưu của bài toán là f (xopt) = 590.
Bài toán lập kho hàng
Ví dụ 3.1
Ví dụ 3.1(tiếp) Chú ý
Để ý rằng trong bảng cuối còn có ô có giá trị 4 = 0 và ô đó không thuộc G(x∗) do đó phương án x∗ không phải phương án cực biên tối ưu duy nhất của bài toán mở rộng.
vj 0 2 2 2 2
bj ui 75 65 80 270 270 ai
27 / 49
1 9 8 10 2 80 0 −1 −7 −6 −8 80 2 4 10 9 4 100 2 −8 −7 75 25 0 9 3 2 5 2 90 0 −9 −3 −5 80 10 0 0 0 0 0 −2 490 −2 40 0 270 180
Bài toán vận tải có ô cấm
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
28 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán vận tải có ô cấm
Bài toán vận tải có ô cấm
Trong thực tế, có trường hợp không thể vận chuyển hàng từ điểm phát i đến điểm thu j.
Khi đó (i, j) là ô cấm Có nhiều lý do về việc cấm vận từ điểm phát i đến điểm thu j:
i) Không có đường vận chuyển từ i → j hoặc có nhưng không thích hợp
ii) Một trạm thu nào đó ưu tiên nhận đủ yêu cầu( TH tổng lượng thu lớn hơn lượng phát)
29 / 49
iii) Do trạm phát nào đó chuyển lượng hàng ít hơn khả năng cung cấp của nó hoặc hàng để tồn kho (TH tổng lượng phát lớn hơn tổng thu)
Bài toán vận tải có ô cấm
Phương pháp giải
Phương pháp giải
Sử dụng phương pháp cực tiểu chi phí
* Đặt cij = M , trong đó (i,j) là ô cấm, M là giá trị lớn có thể là +∞ tượng trưng cho cước phí rất cao
* Nếu PATU của bài toán có ô cấm có thành phần xij > 0 tại ô cấm (i,j) thì bài toán không có PATU
30 / 49
* Nếu PATU của bài toán có ô cấm có thành phần xij = 0 tại tất cả ô cấm (i,j) thì bài toán có PATU
Bài toán vận tải có ô cấm
Ví dụ 4.1
Ví dụ 4.1
Đề bài
Một công ty có ba nhà máy cung cấp sản phẩm của họ cho bốn nhà kho. Công suất hàng tháng của các nhà máy lần lượt là 120, 200 và 180 đơn vị. yêu cầu hàng tháng của các kho lần lượt là 100, 140, 110 và 120. Chi phí vận chuyển đơn vị như sau:
31 / 49
Nhà máy I II III Nhà kho P Q R 30 - 15 12 24 - - 15 25 S 20 15 20
Bài toán vận tải có ô cấm
Ví dụ 4.1
Ví dụ 4.1 (tiếp)
3 X
4 X
Giải.
i=1
j=1
Bài toán có m = 3 và n = 4. Vì ai = 500 > bj = 470 nên ta thêm trạm thu giả T là
32 / 49
nơi thu gom các sản phẩm dư thừa sau khi phát, với lượng thu là: b5 = 30. Không vận chuyển từ I đến Q tức (1, 2) là ô cấm, nên đặt cước phí c12 = M . Tương tự, không có đường đi từ II đến P và III đến R nên c21 = c33 = M Sử dụng phương pháp cực tiểu chi phí xác định được phương án cực biên xuất phát và các số liệu tính toán theo thuật toán thế vị tương ứng với nó ở bảng sau:
Bài toán vận tải có ô cấm
Ví dụ 4.1
Ví dụ 4.1(tiếp)
vj 7 10 10 5 0
bj ui 140 110 120 100 30 ai
15 − M
−23
−10
15 30 20 0 M + − 0 120
90
30
20 − M
−14
24 12 15 0 M 5 200
90
110
5
13 − M
25 15 20 0 M − + 10 180
30
10
140
10
33 / 49
Bài toán vận tải có ô cấm
Ví dụ 4.1
Ví dụ 4.1(tiếp)
vj 15 15 17 20 0
15
30
20
0
M
bj ui 100 140 110 120 30 ai
15 − M
−13
0 120
100
0
20
24
12
15
0
M
10 − M
−14
−5
−5 200
110
90
25
15
20
0
M
17 − M
10
0 180
140
30
10
34 / 49
Bài toán vận tải có ô cấm
Ví dụ 4.1
Ví dụ 4.1(tiếp)
Như vậy, phương án tối ưu của bài toán ban đầu là:
Từ bảng, sau 1 lần điều chỉnh phương án, ta nhận được phương án cực biên tối ưu x∗ ở Bảng 0 x∗ = 0 110 90 0
Kho P nhận đủ 100 đơn vị từ nhà máy I, kho Q nhận đủ 140
xopt = 100 0 0 100 0 0 0 0 140 0 0 140 20 0 30 10 0 0 110 90 30 0
35 / 49
đơn vị từ nhà máy III, kho R nhận đủ 110 đơn vị từ nhà máy II, kho S nhận đủ 120 đơn vị, trong đó 90 đơn vị từ nhà máy II, 30 đơn vị từ nhà máy I. Và nhà máy I thừa 20 đơn vị, nhà máy III thừa 10 đơn vị.
Bài toán vận tải dạng max
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
36 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán vận tải dạng max
Bài toán vận tải dạng max Mô hình bài toán
m X
n X
i=1
j=1
n X
max f (x) = cijxij
j=1 m X
v.đ.k. i = 1, · · · , m xij = ai,
i=1
j = 1, · · · , n xij = bj,
37 / 49
i = 1, · · · , m, j = 1, · · · , n. xij ≥ 0,
Bài toán vận tải dạng max
Phương pháp giải
Phương pháp giải
Do thỏa mãn điều kiện cân bằng thu phát nên ta giải bài toán về dạng min với hàm f 0 = −f hoặc giải trực tiếp như sau:
* Xây dựng phương án cực biến xuất phát từ x0 bằng phương pháp góc Tây Bắc hoặc
phương pháp cực đại chi phí, tức ưu tiên phân một lượng hàng lớn nhất có thể vào ô (i0, j0) sao cho ci0j0 là lớn nhất trong các chi phí ứng với các ô đang cần xem xét * Việc xác định các thế vị tương ứng bài toán tìm min, tức giải hệ
ui + vj = cij∀(i, j) ∈ G(x0)
* Tính các đại lượng
38 / 49
∆ij = ui + vj − cij∀(i, j) /∈ G(x0)
Bài toán vận tải dạng max
Phương pháp giải
Phương pháp giải(Tiếp)
? Kiểm tra điều kiện tối ưu
If ∆ij ≥ 0 với mọi (i, j) /∈ G(x0)
Then dừng thuật toán (x0 là phương án tối ưu)
Else (tức ∃∆ij < 0 với ((i, j) /∈ G(x0)) ta chọn ô (is, js) là ô điều chỉnh ứng với
∆isjs = min{∆ij < 0 | (i, j) /∈ G(x0)
39 / 49
Sau đó xác định chu trình điều chỉnh và xây dựng phương án cực biên x0 mới giống như với bài toán min.
Bài toán vận tải dạng max
Ví dụ 5.1
Ví dụ 5.1
Đề bài Giải bài toán vận tải (P T max) với vecto lượng phát, vecto lượng thu và ma trận chi phí như sau: a = (50, 70, 80)T , b = (40, 60, 100)T
C = 9 8 5 4 6 1 8 4 2
Bảng 2.7.1 biểu diễn các thông tin tương ứng với phương án cực biên xuất phát x0
Giải: được xác định theo "cực đại chi phí" và f (x0) = 920.
40 / 49
Bài toán vận tải dạng max
Ví dụ 5.1
Ví dụ 5.1
vj 9 8 3
bj ui 40 60 100 ai
9 5 8 + − 50 0 10 -2 40
4 1 6 + − −2 70 50 20 3
41 / 49
8 2 4 −1 80 3 80 0 Bảng 2.7.1
Bài toán vận tải dạng max
Ví dụ 5.1
Ví dụ 5.1(tiếp)
vj 11 10 5
bj ui 40 60 100 ai
9 8 5 50 0 2 2 50
4 6 1 −4 70 3 60 10
42 / 49
8 4 2 −3 80 40 3 40 Bảng 2.7.3
Bài toán vận tải dạng max
Ví dụ 5.1
Ví dụ 5.1(tiếp)
Bảng 2.7.3 có ∆ij > 0 nên
x2 = 0 0 40 0 50 60 10 40 0
43 / 49
là phương án tối ưu của bài toán với giá trị tối ưu là fmax = f (x0) = 1020
Bài toán phân việc
Nội dung 1 Bài toán không cân bằng thu phát
Cung lớn hơn cầu Cầu lớn hơn cung
2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1
4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1
5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1
6 Bài toán phân việc
44 / 49
Thuật toán Hungarian Ví dụ 6.1
Bài toán phân việc
Bài toán phân việc
Bài toán đặt ra
Giả sử có n người và n công việc. Để giao cho người i, i ∈ {1, ..., n}, làm công việc j, j ∈ {1, ..., n}, cần một chi phí là cij. Vấn đề là cần tìm phương án để phân công cho người nào làm việc gì (mỗi người chỉ làm một việc, mỗi việc chỉ cho một người làm) sao cho tổng chi phí là nhỏ nhất.
n X
n X
Mô hình toán học của bài toán này là:
i=1
j=1
n X
minf (x) = cijxij
j=1 n X
v.d.k. i = 1, 2, ...n xij = 1,
45 / 49
j = 1, 2, ...n xij = 1,
j=1 xij ∈ {0, 1},
i = 1, ..., n.j = 1, ..., n
Bài toán phân việc
Thuật toán Hungarian
Thuật toán Hungarian
Bước 1. Chọn giá trị chi phí nhỏ nhất ở mỗi hàng.
ci,min = min{cij|j ∈ 1, n}, i = 1, n
ij − ci,min
ij = cold cnew
Bước 2. Giảm chi phí mỗi hàng đi giá trị chi phí nhỏ nhất
Bước 3. Làm tương tự với các cột chưa có giá trị chi phí nào bằng 0.
46 / 49
Bước 4. Thuật toán kết thúc khi tất cả các hàng và các cột đều có ít nhất một giá trị chi phí bằng 0. Khi đó sự phân công công việc được đặt ở các vị trí giá trị chi phí 0 thì bài toán sẽ đạt min.
Bài toán phân việc
Ví dụ 6.1
Ví dụ 6.1
Đề bài: Một nhà máy có 3 máy tự động thực hiện đồng thời các công việc. Bảng chi phí thực hiện công việc của các máy như sau:
Công việc
47 / 49
Máy 2 7 10 13 1 5 14 15 3 9 12 16 I II III
Bài toán phân việc
Ví dụ 6.1
Ví dụ 6.1 (tiếp)
Bước 1: Chọn giá trị chi phí nhỏ nhất ở mỗi hàng.
Công việc
Máy 2 7 10 13 1 5 14 15 3 9 12 16 I II III
Bước 2: Giảm chi phí mỗi hàng đi giá trị chi phí nhỏ nhất.
Công việc
48 / 49
Máy 2 2 0 0 1 0 4 2 3 4 2 3 I II III
Bài toán phân việc
Ví dụ 6.1
Ví dụ 6.1(tiếp)
Cột của máy 3 vẫn chưa có giá trị chi phí nào bằng 0 nên lặp lại với cột 3:
Công việc
Máy 2 2 0 0 3 4 2 3 1 0 4 2 I II III
Công việc
Máy 2 2 0 0 3 2 0 1 1 0 4 2 I II III
49 / 49
Bước 3: Sự phân công được đặt ở tại các giá trị chi phí bằng 0. Từ đó, ta phân: máy 1 làm công việc I, máy 2 làm công việc III, máy 3 làm công việc II. Tổng chi phí là: 5 + 12 + 13 = 30.
