Question

Answer 1

Bài 1

Gọi xij là lượng hàng chuyển từ nơi phát i đến nơi thu j.
Hai ô có M là đường cấm nên:
x13 = 0, x44 = 0.

Tổng phát = 71 + 40 + 18 + 26 = 155
Tổng thu = 53 + 47 + 25 + 30 = 155

Bài toán cân bằng.

Một phương án tối ưu là:
x11 = 53, x12 = 6, x13 = 0, x14 = 12
x21 = 0, x22 = 15, x23 = 25, x24 = 0
x31 = 0, x32 = 0, x33 = 0, x34 = 18
x41 = 0, x42 = 26, x43 = 0, x44 = 0

Kiểm tra:
Hàng 1: 53 + 6 + 12 = 71
Hàng 2: 15 + 25 = 40
Hàng 3: 18
Hàng 4: 26

Cột 1: 53
Cột 2: 6 + 15 + 26 = 47
Cột 3: 25
Cột 4: 12 + 18 = 30

Vậy thỏa mãn đúng cung và cầu.

Chi phí nhỏ nhất:
Zmin = 53.1 + 6.13 + 12.9 + 15.0 + 25.5 + 18.2 + 26.3
Zmin = 53 + 78 + 108 + 0 + 125 + 36 + 78
Zmin = 478

Kết luận bài 1:
Phương án tối ưu là
(53, 6, 0, 12)
(0, 15, 25, 0)
(0, 0, 0, 18)
(0, 26, 0, 0)
và chi phí vận tải nhỏ nhất là 478.

Answer 2

Bài 2

Tổng phát = 28 + 21 + 32 = 81
Tổng thu = 34 + 19 + 21 + 29 = 103

Vì 81 < 103 nên bài toán chưa cân bằng.
Thêm một nơi phát giả có lượng phát:
103 - 81 = 22

Chi phí từ nơi phát giả đến các nơi thu đều bằng 0.

Khi đó ta có thêm hàng giả:
(22; 0, 0, 0, 0)

Một phương án tối ưu là:
x11 = 28, x12 = 0, x13 = 0, x14 = 0
x21 = 0, x22 = 0, x23 = 21, x24 = 0
x31 = 0, x32 = 19, x33 = 0, x34 = 13
x41 = 6, x42 = 0, x43 = 0, x44 = 16

Trong đó hàng 4 là nơi phát giả.

Kiểm tra:
Hàng 1: 28
Hàng 2: 21
Hàng 3: 19 + 13 = 32
Hàng 4: 6 + 16 = 22

Cột 1: 28 + 6 = 34
Cột 2: 19
Cột 3: 21
Cột 4: 13 + 16 = 29

Chi phí nhỏ nhất:
Zmin = 28.5 + 21.1 + 19.3 + 13.6 + 6.0 + 16.0
Zmin = 140 + 21 + 57 + 78 + 0 + 0
Zmin = 296

Kết luận bài 2:
Sau khi thêm nơi phát giả 22 đơn vị, phương án tối ưu là
(28, 0, 0, 0)
(0, 0, 21, 0)
(0, 19, 0, 13)
(6, 0, 0, 16)
và chi phí vận tải nhỏ nhất là 296.