Chương 6
Một số Bài toán đặc biệt
có liên quan đến
Quy Hoạch Tuyến Tính
2
C6. Một số Bài toán đặc biệt
có liên quan đến QHTT
1. Bài toán vận tải
(Transportation Problem)
2. Bài toán phân công
(Assignment Problem)
3. Bài toán dòng chảy tối đa
(Maximum Flow Problem)
4. Bài toán đường đi ngắn nhất
(Shortest Path Problem)
3
1. Bài toán vận tải
(Transportation Problem)
1.1. Thiết lập Bài toán vận tải (Transportation Problem)

Các điểm nguồn (Sources) (i) và Khả năng cung cấp của từng điểm nguồn (Supply) (s
i
).

Các điểm đích (Destinations) (j) và Nhu cầu của từng điểm đích (Demand) (d
j
).

Chi phí vận chuyển cho 1 đơn vị hàng hóa từ Điểm nguồn đến Điểm đích (c
ij
).

j
2
1
s
1
s
2
s
i
s
m
d
1
d
2
d
n
(c
mn
, x
mn
)
(c
11
, x
11
)
Điểm nguồn
Điểm đích
(c

=≥
=≤
∑
∑
=
=
∑ ∑
= =
≥
m
1i
n
1j
ji
ds
Điều kiện:
6
1. Bài toán vận tải (tt3)

Dạng cân bằng (Balanced Model) của Bài toán vận tải
∑∑
= =
=
m
1i
n
1j
ijij
xc Min Z
ji,0x

khả năng cung cấp hàng ngày là 120, 140 và 100 sản phẩm. Giả sử hàng
ngày phải được vận chuyển đến 4 điểm bán lẻ với nhu cầu là 100, 60, 80,
120 sản phẩm. Bài toán đặt ra là xác định PA vận chuyển để tốn ít chi phí
nhất nếu chi phí vận chuyển 1 đơn vị hàng hóa giữa các kho trung chuyển
và điểm bán lẻ được cho trong bảng sau:
Kho
Điểm bán lẻ
1 2 3 4
1 5 7 9 6
2 6 7 10 5
3 7 6 8 1
8
1. Bài toán vận tải (tt5)
Bài toán QHTT được thiết lập:
Min 5x
11
+ 7x
12
+ 9x
13
+ 6x
14
+ 6x
21
+ 7x
22
+ 10x
23
+ 5x
24

32
+ x
33
+ x
34
= 100
x
11
+ x
21
+ x
31
= 100
x
12
+ x
22
+ x
32
= 60
x
13
+ x
23
+ x
33
= 80
x
14
+ x

m
1i
n
1j
ji
ds
∑ ∑
= =
<
m
1i
n
1j
ji
ds
∑ ∑
= =
+
−=
m
1i
n
1j
ji1n
dsd
∑ ∑
= =
+
−=
n

12
x
13
x
14
120
2
x
21
x
22
x
23
x
24
140
3
x
31
x
32
x
33
x
34
100
Tổng cầu 100 60 80 120 360
5
6
7 6

cầu của điểm đích đang xét đã được thỏa mãn trước khi chuyển
sang 1 cột mới (tức là 1 điểm đích mới sẽ được xem xét).
14
1. Bài toán vận tải (tt11)
VD: Xét VD 1, nghiệm ban đầu của VD 1 xác định theo pp góc Tây Bắc
Kho
Điểm bán lẻ
Tổng cung
1 2 3 4
1 100 20 120
2 40 80 20 140
3 100 100
Tổng cầu 100 60 80 120 360
5
6
7 6
7
7 9
10
8 1
5
6
C
Tây Bắc
= 100*5 + 20*7 + 40*7 + 80*10 + 20*5 + 100*1 = 1.920
15
1. Bài toán vận tải (tt12)
1.2.2. Phương pháp chi phí bé nhất (The Minimal Cost Method)
Nguyên nhân chủ yếu là do pp góc Tây Bắc không hề lưu ý đến Chi phí
vận chuyển giữa các điểm nguồn và các điểm đích (c

10
8 1
5
6
C
Chi phí bé nhất
= 100*5 + 20*9 + 60*7 + 60*10 + 20*5 + 100*1 = 1.900
17
1. Bài toán vận tải (tt14)

Trước tiên ô (3,4) được xét do là ô có chi phí thấp nhất: giá trị vận chuyển
được gán trong ô này bằng với khả năng cung cấp tối đa của kho 3. Sau khi
gán giá trị cho ô (3,4), kho 3 hết khả năng cung cấp và do vậy các ô (3,1),
(3,2) và (3,3) sẽ không được xem xét tiếp.

Ô có chi phí nhỏ nhất kế tiếp được xét là các ô (1,1) và (2,4): giá trị vận
chuyển tối đa gán được cho các ô này là 100 và 20. Sau khi gán, điểm bán
lẻ 1 và 4 đã được cấp đủ nhu cầu và do vậy các ô (2,1) và (1,4) sẽ bị loại bỏ
trong bước xem xét tiếp theo.

Trong các ô còn lại: (1,2), (1,3), (2,2), (2,3); hai ô (1,2) và (2,2) có cùng chi
phí vận chuyển đơn vị nhỏ nhất là 7. Tuy nhiên, lượng vận chuyển tối đa có
thể gán được cho ô (1,2) chỉ là 20, trong khi lượng vận chuyển tối đa có thể
gán được cho ô (2,2) là 60. Vì vậy, ô (2,2) được chọn để gán giá trị trong
bước này. Sau khi gán, điểm bán lẻ 2 đã được cấp đủ nhu cầu và do vậy ô
(1,2) bị loại bỏ.

Trong hai ô còn lại là (1,3) và (2,3), các giá trị của lượng hàng vận chuyển
duy nhất có thể gán được phải là 20 và 60 theo thứ tự đó.
18

phí vận chuyển nhỏ nhất. Các giá trị xác định được biểu diễn chênh lệch về
chi phí VT giữa con đường VT tốt nhất và con đường VT tốt thứ 2 trên từng
hàng/cột. Đây cũng chính là chi phí cơ hội do không chọn con đường tốt
nhất trên từng hàng/cột.
2. Xác định hàng hoặc cột ứng với chi phí cơ hội lớn nhất.
3. Phân bổ tối đa lượng hàng có thể vận chuyển được trong ô có chi phí vận
chuyển nhỏ nhất ứng với hàng/cột đã chọn trong B2.
4. Loại bỏ hàng đã dùng hết khả năng cung cấp hoặc cột đã được thỏa mãn
toàn bộ nhu cầu sau sự phân bổ trong B3. Đánh dấu X vào các ô trống của
hàng/cột bị loại bỏ.
5. Tính toán lại các chi phí cơ hội trong B1 ứng với bảng VT đã loại bỏ các
hàng/cột đề cập đến trong B4.
6. Quay lại B2 và thực hiện lặp lại các B2 – 5 cho đến khi nhận được 1 lời giải
ban đầu.
21
1. Bài toán vận tải (tt18)
PP xấp xỉ Vogel
VD 5: Xét VD 1, nghiệm ban đầu xác định theo pp xấp xỉ Vogel được
thực hiện theo trình tự sau:
Kho
Điểm bán lẻ
Tổng cung
1 2 3 4
1 120
2 140
3 X X X 100 100
Tổng cầu 100 60 80 120 360
5
6
7 6

6
1* 0 1 1
1*
1
23
1. Bài toán vận tải (tt20)
PP xấp xỉ Vogel
VD 5: (tt2)
Kho
Điểm bán lẻ
Tổng cung
1 2 3 4
1 100 X 120
2 X 20 140
3 X X X 100 100
Tổng cầu 100 60 80 120 360
5
6
7 6
7
7 9
10
8 1
5
6
0 1 1
1
2*
24
1. Bài toán vận tải (tt21)

1 100 X 20 X 120
2 X 60 60 20 140
3 X X X 100 100
Tổng cầu 100 60 80 120 360
5
6
7 6
7
7 9
10
8 1
5
6
#
#
#
Tổng chi phí VT ứng với lời giải ban đầu này là:
C
VAM
= 100*5 + 20*9 + 60*7 + 60*10 + 20*5 + 100*1 = 1.900