Xem mẫu
- Chương 3 BÀI TOÁN ĐỐI NGẪU
Mục đích yêu cầu
Ở chương 2, ta đã xét bài toán quy hoạch tuyến tính min-max như là hai bài toán
tách biệt. Nhưng thật sự đối với mỗi bài toán min luôn luôn tồn tại bài toán max tương
ứng và ngược lại. Bài toán quy hoạch ban đầu được gọi là bài toán gốc còn bài toán
tương ứng của nó được gọi là bài toán đối ngẫu.
Trong nhiều trường hợp, nhờ Lý thuyết đối ngẫu mà các vấn đề phức tạp trong khi
giải bài toán gốc sẽ trở nên đơn giản và dễ dàng hơn thông qua giải bài toán đối ngẫu
của nó. Ta sẽ luôn tìm được phương án tối ưu của bài toán đối ngẫu từ phương án của
bài toán gốc và ngược lại.
Mục tiêu của chương là:
- Giúp ta hiểu rõ về bài toán đối ngẫu, ý nghĩa kinh tế của bài toán đối ngẫu, sự
cần thiết phải đưa về bài toán đối ngẫu.
- Xét mối quan hệ giữa bài toán gốc và bài toán đối ngẫu từ đó có những phương
pháp tìm ra phương án tối ưu nhanh hơn.
Kiến thức chuẩn bị
Để học tốt chương sinh viên cần: nắm vững các chương trước và thành thạo các
phép tính.
- 56 -
- 3.1 Khái niệm
3.1.1 Bài toán đối ngẫu của bài toán dạng chính tắc
Định nghĩa: Cho bài toán gốc (P):
n
f ( x ) = ∑ c j x j → min (max) (3.1.1)
j =1
n
∑a
j =1
ij x j = bi i = 1, m (3.1.2)
x j ≥ 0, j = 1, n (3.1.3)
Bài toán (D) sau đây được gọi là bài toán đối ngẫu của nó:
m
g ( y ) = ∑ bi yi → max ( min) (3.1.4)
i =1
m
∑a
i =1
ij yi ≤ (≥ ) c j ( j = 1, n ) (3.1.5)
y i tùy ý dấu ( i = 1, m ) (3.1.6)
Nhận xét
- Hàm mục tiêu của (P) f ( x ) → min thì hàm mục tiêu của (D) g ( y ) → m ax và
ngược lại.
- Các ràng buộc ở bài toán (D) đều là bất đẳng thức " ≤ " nếu f ( x ) → m ax
(hoặc " ≥ " nếu f ( x ) → min )
- Số ẩn của bài toán này là số ràng buộc của bài toán kia và ngược lại.
- Các hệ số cj và các số hạng tự do bi ở hai bài toán đối ngược nhau.
- Ma trận hệ số các ràng buộc ở hai bài toán là chuyển vị của nhau. Hàng i
n
trong ma trận A = (aij ) mxn xác định ràng buộc thứ i của bài toán gốc ∑a x
j =1
ij j = bi , còn
cột j trong ma trận A xác định ràng buộc thứ j của bài toán đối ngẫu:
m
∑a
i =1
ij yi ≤ ( ≥ ) c j .
Ví dụ 1: Bài toán gốc: f ( x ) = 2 x1 + 4 x 2 + 3 x 3 → m in
x1 + 2 x 2 + x 3 = 2
x 2 + 3 x3 = 5
x j ≥ 0, j = 1, 3
- 57 -
- Bài toán đối ngẫu của bài toán này là:
g ( y ) = 2 y1 + 5 y 2 → m ax
y1 ≤ 2
2 y1 + y 2 ≤ 4
y + 3y ≤ 3
1 2
y1 , y2 tùy ý.
3.1.2 Bài toán đối ngẫu của bài toán dạng tổng quát
Quy tắc lập bài toán đối ngẫu được cho bởi bảng sau:
Bài toán gốc P (D) Bài toán đối ngẫu D (P)
n m
Hàm mục tiêu f ( x ) = ∑ c j x j → max Hàm mục tiêu g ( y ) = ∑ bi yi → min
j =1 i =1
n
≤ ≥
Ràng buộc thứ i: ∑ aij x j ≥ bi , i = 1, m Ẩn thứ i: yi ≤ 0, i = 1, m
j =1
= tùy ý
≥ m
≥
Ẩn thứ j: x j ≤ 0, j = 1, n
Ràng buộc thứ j: ∑ aij yi ≤ c j , j = 1, n
i =1
tùy ý =
Nhận xét: Bài toán đối ngẫu của bài toán đối ngẫu chính là bài toán gốc. Vì vậy
người ta nói cặp bài toán gốc – đối ngẫu là cặp bài toán đối ngẫu nhau.
Cách nhớ
max → min Ẩn → Ràng buộc(cùng dấu) Ràng buộc → Ân (ngược dấu)
min → max Ẩn → Ràng buộc (ngược dấu) Ràng buộc → Ân (cùng dấu)
Ví dụ 2: Tìm bài toán đối ngẫu của bài toán
f ( x ) = 2 x1 + 3 x 2 − x 3 + x 4 → m ax
2 x1 − x 2 − x 3 + x 4 ≤ 5 (1)
x1 + x 2 + 2 x 3 + x 4 = 7 (2 )
5 x + x + 3 x + x ≥ 20 (3)
1 2 3 4
x1 , x 2 ≥ 0, x 3 ≤ 0 x4 tùy ý.
Bài toán đối ngẫu của bài toán này là:
- 58 -
- g ( y ) = 5 y1 + 7 y 2 + 2 0 y 3 → m in (do f ( x) → max )
2 y1 + y 2 + 5 y 3 ≥ 2 ( do x1 ≥ 0)
− y + y + y ≥ 3 (d o x2 ≥ 0 )
1 2 3
− y1 + 2 y 2 + 3 y 3 ≤ − 1 ( d o x 3 ≤ 0)
y1 + y 2 + y 3 = 1 ( d o x 4 tù y ý 0 )
y1 ≥ 0 (do ràng buộc (1) ≤ ), y2 tùy ý (do ràng buộc (2) = ), y3 ≤ 0
(do ràng buộc (3) ≥ ),
Ví dụ 3: Tìm bài toán đối ngẫu của bài toán
f ( x ) = 2 x1 + x 2 − x 3 → m in
x1 − x 2 + 2 x 3 = 1
x1 − x 2 − 3 x 3 ≥ 2
x + x − 2x ≤ 3
1 2 3
x1 ≥ 0, x 2 ≤ 0 , x3 tùy ý.
Bài toán đối ngẫu là:
g ( y ) = y1 + 2 y 2 + 3 y 3 → m ax
y1 + y 2 + y 3 ≤ 2
− y1 − y 2 + y 3 ≥ 1
2 y1 − 3 y 2 − 2 y 3 = − 1
y2 ≥ 0, y3 ≤ 0
? Lập bài toán đối ngẫu của bài toán sau:
f ( x ) = 2 x1 + x 2 − 8 x 3 → m ax
7 x1 + 4 x 2 + 2 x 3 ≤ 2 8
3 x1 − x 2 + 3 x 3 = 10
2 x + 3 x − x ≥ 15
1 2 3
x1 ≥ 0, x 2 ≥ 0
3.2 Quan hệ giữa bài toán gốc và bài toán đối ngẫu
3.2.1 Các định lý đối ngẫu
Định lý 1: Với cặp bài toán P và D, chỉ xảy ra một trong ba trường hợp sau:
1. Cả hai đều không có phương án.
2. Cả hai đều có phương án, lúc đó cả hai cùng có phương án tối ưu và giá trị
hàm mục tiêu đối với phương án tối ưu bằng nhau.
- 59 -
- 3. Một trong hai bài toán không có phương án, còn bài toán kia có phương án.
Khi đó bài toán có phương án sẽ không có phương án tối ưu và hàm mục
tiêu của nó không bị chặn.
Hệ quả 1: Nếu một trong hai bài toán có phương án tối ưu thì bài toán kia cũng có
phương án tối ưu.
Hệ quả 2: Điều kiện cần và đủ để hai phương án x * của (P) và y * của (D) tối ưu là:
f ( x*) = g ( y*)
Định lý 2: (Độ lệch bù yếu). Điều kiện cần và đủ để phương án x * của (P) và y * của
(D) tối ưu là:
∗ m
x j ∑ aij yi − c j = 0 (j = 1, n)
∗
(3.1.7)
i =1
y ∗ a x∗ − b = 0 (i = 1, m)
n
i ∑ ij j i (3.1.8)
j =1
Chú ý: Nếu trong các tích trên nếu thừa số này khác 0 thì thừa số kia bằng 0.
3.2.2 Tìm P.A.T.Ư của bài toán đối ngẫu qua P.A.T.Ư của bài toán gốc.
Giả sử bài toán gốc có phương án tối ưu x∗ = ( x1∗ , x2∗ ,...xn∗ ) và giải được bài toán
đối ngẫu. Theo định lý 2, ta có
m
Nếu x*j > 0 thì ∑a y
i =1
*
ij i = cj .
n ( > ,< )
Nếu thay x * vào ràng buộc của bài toán gốc mà xẩy ra ∑ aij x*j ≠ bi (đẳng
j =1
thức thật sự) thì y = 0 .
*
i
Từ đây ta được hệ phương trình, giải hệ này ta tìm được nghiệm tối ưu của bài
toán đối ngẫu.
Nhận xét:
Tìm P.A.T.Ư của bài toán gốc qua P.A.T.Ư của bài toán đối ngẫu ta tiến hành
tương tự.
Ví dụ 4: Bài toán gốc
f ( x ) = 2 x1 + x 2 + x 3 + 4 x 4 → m ax
5 x1 + x 2 + x 3 + 6 x 4 = 5 0
− 3 x1 + x 3 + 2 x 4 ≥ 16
4 x + 3 x + x ≤ 23
1 3 4
x j ≥ 0, j = 1, 4
- 60 -
- Có phương án tối ưu là x∗ = (0,14, 6, 5), f ( x∗ ) = 40 . Viết bài toán đối ngẫu và tìm
phương án tối ưu của bài toán đối ngẫu.
Giải
Bài toán đối ngẫu: g ( y ) = 5 0 y1 + 1 6 y 2 + 2 3 y 3 → m in
5 y1 − 3 y 2 + 4 y 3 ≥ 2 (1)
y ≥1 (2 )
1
y1 + y 2 + 3 y 3 ≥ 1 (3)
6 y1 + 2 y 2 + y 3 ≥ 4 (4 )
y1 tuỳ ý, y2 ≤ 0, y3 ≥ 0
Tìm phương án tối ưu của bài toán đối ngẫu:
x2∗ = 14 > 0 ⇒ y1∗ = 1 (theo (2))
x3∗ = 6 > 0 ⇒ y1∗ + y2∗ + 3 y3∗ = 1 (theo (3))
x4∗ = 5 > 0 ⇒ 6 y1∗ + 2 y2∗ + y3∗ = 4 (theo (4))
6 2
Giải hệ trên ta tìm được: y1∗ = 1, y2∗ = − , y3∗ =
5 5
6 2
Vậy phương án tối ưu là y ∗ = 1, − ,
5 5
6 2
với g ( y*) = 50.1 + 16. − + 23. = 40 = f ( x∗ )
5 5
Ví dụ 5: Bài toán gốc
f ( x ) = 2 x1 + 5 x 2 + 4 x 3 + x 4 − 5 x 5 → m in
x1 − 6 x 2 − 2 x 4 − 9 x 5 = 3 2
1 3
2 x 2 + x 3 + x 4 + x 5 = 30
2 2
3 x 2 + x 5 ≤ 3 6
x j ≥ 0, j = 1,5
Có phương án tối ưu là x∗ = (32, 0,30, 0, 0), f ( x∗ ) = 184 . Viết bài toán đối ngẫu và
tìm phương án tối ưu của bài toán đối ngẫu.
Giải
Bài toán đối ngẫu của nó là:
g ( y ) = 3 2 y1 + 3 0 y 2 + 36 y 3 → m ax
- 61 -
-
y ≤ 2
1
− 6 y1 + 2 y 2 + 3 y3 ≤ 5
y2 ≤ 4
1
− 2 y1 + y2 ≤ 1
2
3
− 9 y1 + y2 + y3 ≤ − 5
2
y1 , y2 tuỳ ý, y3 ≤ 0
Tìm phương án tối ưu của bài toán đối ngẫu:
Thứ nhất: x1∗ = 32 > 0 ⇒ y1∗ = 2
x3∗ = 30 > 0 ⇒ y2∗ = 4
Thứ hai: Thay x∗ = (32, 0,30, 0, 0) vào ràng buộc thứ 3 ta có
3 x2 + x5 − 36 = −36 < 0 . Nên y3∗ = 0
Vậy phương án tối ưu là y ∗ = ( 2, 4, 0 )
với g ( y*) = 32.2 + 30.4 + 36.0 = 184 = f ( x∗ )
? Tìm phương án tối ưu của bài toán đối ngẫu, biết rằng bài toán gốc có phương
án tối ưu là x∗ = (1/ 5, 0,9 / 10), f ( x∗ ) = 12 .
f ( x ) = 15 x1 + 8 x 2 + 1 0 x 3 → m ax
− 3 x1 + 2 x 2 + 4 x 3 ≤ 3
2 x1 − x 2 + 2 x 3 ≤ 4
−4 x − 5 x + 2 x ≥ 1
1 2 3
x j ≥ 0, j = 1,3
Ví dụ 6: Bài toán gốc
f ( x ) = 5 2 x1 + 6 0 x 2 + 3 6 x 3 → m in
x1 ≥ 3 2
2 x1 + 4 x 2 + 3 x 3 ≥ 6
4 x1 + 2 x 2 ≥ 4
x ≥ −2
2
x 3 ≥ 3
x j tùy ý ( j = 1,3 )
- 62 -
- a) Viết bài toán đối ngẫu của bài toán trên.
b) Tìm phương án tối ưu của bài toán gốc biết P.A.T.Ư của bài toán đối ngẫu là
34 22 310
y ∗ = 0, , , 0, 2 và g ( y* ) = .
3 3 3
Giải
Bài toán đối ngẫu của nó là:
g ( y ) = 3 2 y1 + 6 y 2 + 4 y 3 − 2 y 4 + 3 y 5 → m ax
y1 + 2 y 2 + 4 y 3 = 5 2
4 y 2 + 2 y 3 + y 4 = 60
3 y + y = 36
2 5
yi ≥ 0 i = 1,5
Tìm phương án tối ưu của bài toán gốc
34
Thứ nhất: y2∗ = > 0 ⇒ 2 x1 + 4 x2 + 3 x3 = 6
3
22
y3∗ = > 0 ⇒ 4 x1 + 2 x2 = 4
3
y5∗ = 2 > 0 ⇒ x3 = 3
Thứ hai: Mọi ràng buộc trong bài toán đối ngẫu đều là phương trình nên không
cho ta điều gì về x j
11
x1 = 6
2 x1 + 4 x2 + 3 x3 = 6
5
Giải hệ phương trình 4 x1 + 2 x2 = 4 ⇒ x2 = −
x = 3 3
3 x3 = 3
11 5
Vậy phương án tối ưu của bài toán gốc là x∗ = , − , 3
6 3
11 5 310
với f ( x*) = 52. + 60. − + 36.3 = = g ( y∗ )
6 3 3
3.3 Ý nghĩa bài toán đối ngẫu
Một bài toán quy hoạch tuyến tính gốc được lập nên từ những vấn đề của sản xuất và
kinh doanh, khi đó mọi tham số ( aij ,bi ,c j ) , ẩn số, hàm mục tiêu, các ràng buộc đều
chứa đựng những nội dung rõ rệt về kinh tế. Khi chuyển sang bài toán đối ngẫu đôi lúc
- 63 -
- ta sẽ khó có thể giải thích ý nghĩa kinh tế của các yếu tố trong bài toán đối ngẫu. Tuy
nhiên không phải vì vậy mà bài toán đối ngẫu không có tầm quan trọng to lớn.
Theo các khái niệm trên ta thấy: giải được một trong hai bài toán coi như đã
giải được bài toán kia. Vì vậy nếu gặp bài toán khó giải thì rất có thể bài toán đối ngẫu
sẽ dễ giải hơn.
Ví dụ 7: Bài toán sau.
f ( x ) = ∑ c j x j → min
∑ aij x j ≥ bi ( i = 1,m )
xj ≥0 ( j = 1,n )
Giả thiết c j ≥ 0 ( j = 1,n )
Nếu giải trực tiếp, ta cần đưa vào m ẩn phụ với hệ số -1, rồi lại thêm m ẩn giả với hệ số
1 mới đưa về dạng chuẩn để giải bằng thuật toán đơn hình. Còn nếu đưa về bài toán
đối ngẫu:
g( y ) = ∑ bi yi → max
∑ aij y i ≤ cj ( j = 1,n )
yi ≥ 0 ( i = 1,m )
thì chỉ cần đưa m ẩn phụ vời hệ số 1 là có ngay bài toán dạng chuẩn để giải.
Ngoài ra người ta còn chứng minh được: khi đã có phương án tối ưu của bài toán đối
ngẫu, tức là ở bảng ∆ j ≥ 0 ∀j . Lúc đó x* ( ∆m +1 , ∆m + 2 ,...,∆m + n ) chính là phương
án tối ưu của bài toán gốc. (Trong đó ∆m + j là ước lượng của ẩn phụ ym + j ).
Bẳng lý thuyết của bài toán đối ngẫu người ta đã đưa ra các thuật toán giải một số bài
toán quan trọng trong kinh tế như “phương pháp thế vị” giải bài toán vận tải và
phương pháp “ Điều chỉnh nhân tữ” giải bài toán sản xuất đồng bộ.
- 64 -
- BÀI TẬP CHƯƠNG 3
1. Lập bài toán đối ngẫu của các bài toán sau:
f ( x ) = 2 x1 + x 2 − x 3 → m in
x − x + 2x = 1 f ( x ) = − x1 + x 2 + x 3 → m ax
1 2 3 x − 3x + x ≥ 4
1 2 3
a) x1 − x 2 − 3 x 3 ≥ 2 b)
2 x + x 2 − 2 x3 ≥ 1
x + x − 2x ≤ 3 1
1 2 3
x ≥ 0, j = 1, 3
x1 ≥ 0, x 2 ≤ 0 j
2. Lập bài toán đối ngẫu của các bài toán sau:
f ( x ) = 2 x1 + 3 x 2 − 2 x 3 + 4 x 5 → m in
x + x + 3x ≥ 7
2 4 5
a) 4 x1 + 2 x 3 + x 5 = 3
x − 3 x + x + x ≤ 10
1 3 4 5
x1 ≥ 0, x 2 , x 3 ≤ 0, x 4 , x 5 ∈ R
f ( x ) = 2 5 x1 + 20 x 2 + 3 0 x 3 → m ax
3 x1 + x 2 + x 3 ≤ − 1 2
x1 + x 2 + x 3 ≤ − 8
b)
x + 2 x 2 + 2 x3 ≤ − 1 2
1
2 x1 + 3 x 2 + x 3 ≤ − 9
x j ≤ 0, j = 1, 3
3. Cho bài toán gốc:
f ( x ) = 2 7 x1 + 50 x 2 + 1 8 x 3 → m ax
x + 2x + x ≤ 2
1 2 3
− 2 x1 + x 2 − x 3 ≤ 4
x + 2 x − x ≤ −2
1 2 3
x1 , x 2 ∈ R , x 3 ≤ 0
a) Lập bài toán đối ngẫu
b) Giải bài toán đối ngẫu và suy ra kết quả của bài toán gốc.
4. Tìm phương án tối ưu của bài toán đối ngẫu. Biết bài toán gốc có phương án tối ưu
là x∗ = (0, 7 / 2,1) và có dạng:
f ( x ) = 1 2 x1 + 8 x 2 + x 3 → m in
- 65 -
-
x1 + 2 x 2 + x 3 = 8
2 x1 + 2 x 2 + 3 x 3 ≤ 10
3
2 x1 + 3 x 2 + x 3 = 1 2
2
x j ≥ 0, j = 1,3
5. Cho bài toán gốc
f ( x ) = − 2 x1 + x 2 + x 4 → m in
x1 + x 2 − x 3 ≤ 1 5
x1 + x 2 + x 3 + x 4 = 27
2 x − x − x ≤ 18
1 2 3
x j ≥ 0, j = 1, 4
Có phương án tối ưu là X ∗ = (15, 0,12, 0) , f ( X ∗ ) = −30
Viết bài toán đối ngẫu và tìm phương án tối ưu của bài toán đối ngẫu.
6. Cho bài toán (P)
f ( x ) = 3 x1 + x 2 + 2 x 3 + 3 x 4 + 2 x 5 + 4 x 6 → m in
2 x1 + x 3 + x 4 + 2 x 6 = 5
3 x1 + x 2 + 2 x 4 + x 6 = 1 1
x + 2x + x + x = 5
1 4 5 6
x j ≥ 0, j = 1, 6
Kiểm tra tính tối ưu của phương án x = (5 / 2, 7 / 2, 0, 0,5 / 2, 0) của bài toán (P).
7. Cho bài toán gốc
f ( x ) = x1 + 2 x 2 + 3 x 3 + 3 x 4 → m ax
2 x1 + x 2 + x 3 + 2 x 4 ≤ 2 0
x1 + 2 x 2 + 3 x 3 + 4 x 4 = 1 8
2 x + x + 2 x + x ≥ 16
1 2 3 4
x j ≥ 0, j = 1, 4
a) Giải bài toán trên bằng phương pháp đơn hình.
b) Viết bài toán đối ngẫu và tìm phương án tối ưu của bài toán đối ngẫu.
- 66 -
- Chương 4 BÀI TOÁN VẬN TẢI. BÀI TOÁN THẾ VỊ
Mục đích yêu cầu
Bài toán vận tải là bài toán quan trọng nhất trong các bài toán quy hoạch tuyến
tính. Thuật ngữ bài toán vận tải thường được hiểu là bài toán vận chuyển sao cho cước
phí nhỏ nhất.
Trong chương này, sinh viên cần nắm vững các nội dung sau:
- Nhận biết dạng bài toán vận tải cân bằng thu phát và các dạng đặt biệt khác (như
không cân bằng thu phát, bài toán vận tảii ô cấm, bài toán vận tải có hàm mục tiêu
max) để từ đó đó ra phương pháp giải phù hợp.
- Biết cách đặt bài toán dưới dạng bảng.
- Thành thạo phương pháp chi phí bé nhất đề tìm phương án cơ bản ban đầu cho
bài toán vận tải.
- Nắm vững thuật toán “Quy 0 cước phí các ô chọn” và phương pháp thế vị để
tìm phương án tối ưu cho bài toán vận tải.
Kiến thức chuẩn bị
Để học tốt chương này sinh viên cần nắm vững: phương pháp đơn hình, phương
pháp đối ngẫu, nhận dạng và phân tích đúng các trường hợp.
- 67 -
- 4.1 Bài toán vận tải cân bằng thu phát (bài toán cổ điển)
4.1.1 Thiết lập bài toán
Giả sử có m địa điểm A1, A2,..., Am cung cấp một loại hàng hóa (xi măng, sắt,
thép,…) với khối lượng lần lượt là a1 , a2 , …, am . Cùng lúc đó có n địa điểm tiêu thụ
hàng hóa đó là B1, B2,..., Bn với khối lượng yêu cầu lần lượt là b1 , b2 ,…, bn (đơn vị
khối lượng tính bằng tấn).
Gọi Ai là trạm phát hàng thứ i ( i = 1, m )
B j là trạm thu hàng thứ j ( i = 1, n )
Giả sử chi phí chuyên chở một tấn hàng từ Ai đến B j là cij đồng. Ma trận
C = ( cij ) gọi là ma trận cước phí.
mxn
Hãy lập kế hoạch vận chuyển hàng hóa sao cho tổng chi phí vận tải thấp nhất
và thỏa mãn yêu cầu thu-phát.
(Để đơn giản, ta giả thiết tổng lượng hàng cần phát đi ở các trạm phát bằng
m n
tổng lượng hàng thu về ở các trạm thu ∑ ai = ∑ b j . Điều kiện này gọi là cân bằng
i =1 j =1
thu phát)
Mô hình bài toán vận tải
Đặt xij là số tấn hàng chuyển từ trạm phát Ai đến trạm thu B j
m n
Tổng chi phí vận tải: f ( x) = ∑∑ cij xij → min (4.1.1)
i =1 j =1
n
(1) Trạm phát, phát hết hàng: ∑x
j =1
ij = ai , i = 1, m (4.1.2)
m
(2) Trạm thu, thu đủ hàng: ∑x i =1
ij = b j , ( j = 1, n) (4.1.3)
(3) Yêu cầu trạm phát và trạm thu được thỏa
m n
∑ a = ∑b
i =1
i
j =1
j (cân bằng thu phát) (4.1.4)
(4) Hiển nhiên xij ≥ 0 (i = 1, m; j = 1, n) . (4.1.5)
Từ các phân tích trên, ta có mô hình bài toán vận tải (BTVT) như sau:
m n
f ( x) = ∑∑ cij xij → min (4.1.6)
i =1 j =1
- 68 -
- n
∑x
j =1
ij = ai (i = 1, m) (4.1.7)
m
∑x
i =1
ij = b j ( j = 1, n) (4.1.8)
m n
xij ≥ 0; cij ≥ 0; ai > 0; b j > 0; ∑ ai = ∑ b j (4.1.9)
i =1 j =1
Một ma trận X = ( xij )mxn thỏa (4.1.7), (4.1.8) và (4.1.9) gọi là một phương án,
thỏa thêm (4.1.6) gọi là phương án tối ưu.
4.1.2 Đặt bài toán dưới dạng bảng
Bài toán vận tải là bài toán QHTT nên có thể dùng thuật toán đơn hình để giải.
Nhưng do tính chất đặc biệt của bài toán vận tải, nên ta có thể có một phương pháp
giải đơn giản và hiệu quả hơn.
Trước hết ta trình bày bài toán dưới dạng bảng:
Thu Bj b1 b2 … bn
Phát Ai
c11 c12 c1n
A1
x11 x12 x1n
c21 c22 c2n
A2
x21 x22 x2n
…
cm1 cm2 cmn
am
xm1 xm2 xmn
Mô tả bảng vận tải
- Mỗi hàng đặc trưng cho một trạm phát và mỗi cột đặc trưng cho một trạm thu.
- Mỗi ô nằm trên hàng i và cột j đặc trưng cho tuyến đường từ Ai đến B j gọi
là ô (i, j )
+ Chi phí vận chuyển: cij được ghi ở góc bên trái của ô (i, j ) .
+ Lượng hàng hóa cần vận chuyển: xij được ghi ở góc bên phải của ô (i, j ) .
- Một ô được gọi là ô treo nếu nó là ô duy nhất trên dòng hay cột.
- 69 -
- - Những ô ứng với xij > 0 trong Bảng vận tải được gọi là ô chọn. Những ô còn
lại được gọi là ô loại. Ô chọn đặc trưng cho tuyến đường có vận tải.
- Một dãy các ô chọn, trong đó 3 ô liên tiếp không nằm trong cùng 1 dòng hay
một cột được gọi là một dây chuyền.
(i1 , j1 )(i1 , j2 )(i2 , j2 )...(ik −1 , jk )(ik , jk )
(Số ô trong một dây chuyền là một số chẵn, không nhỏ hơn 4)
- Một dây chuyền khép kín được gọi là một vòng (lưu ý: tổng số ô trên vòng
luôn là số chẵn và ít nhất là 4 ô)
(i1 , j1 )(i1 , j2 )(i2 , j2 )...(ik −1 , jk )(ik , jk )(ik , j1 )
Ví dụ 1
- Các ô chọn có dấu “x”, tạo thành dây chuyền; hình 2 tạo thành một vòng.
- Hình 1, ô (3,1) là ô treo; hình 2, không có ô treo.
x x
X x x x
x x
x x x x
(hình 1) (hình 2)
Định nghĩa
- Một phương án mà các ô chọn không tạo thành vòng gọi là P.A cơ bản.
- Một phương án cơ bản có đủ m + n − 1 ô chọn gọi là P.A cơ bản không suy biến,
nếu ít hơn m + n − 1 ô chọn gọi là P.A cơ bản suy biến.
4.1.3 Các tính chất
4.1.3.1 Tính chất 1
Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu.
ai b j aib j ∑b j
Thật vậy: Đặt xij = ; xij ≥ 0 và ∑x =∑ =ai j
= ai
∑a i
i j
ij
j ∑a
i
i ∑a
i
i
aib j ∑a i
∑x =∑ =b j i
= bj
∑a ∑a
ij
i i i i
i i
Vậy bài toán có phương án.
- 70 -
- Ngoài ra f ( x) = ∑∑ cij xij ≥ 0
i j
Bài toán vận tải có phương án và hàm mục tiêu luôn bị chặn dưới nên nó có
phương án tối ưu.
4.1.3.2 Tính chất 2
Trong một phương án cơ bản bất kỳ, số ô chọn không bao giờ vượt quá tổng số
các trạm phát và các trạm thu trừ đi một.
Ký hiệu: α số ô chọn thì α ≤ m + n − 1 .
4.1.3.3 Tính chất 3
Với một phương án cơ bản có đủ m + n − 1 ô chọn thì một ô loại bất kỳ được
đưa vào P.A sẽ tạo nên một vòng duy nhất với một số ô chọn.
Chú ý: Trường hợp P.A cơ bản suy biến, ta có thể bổ sung một số ô loại sao cho
P.A cơ bản có m + n − 1 ô chọn. Các ô loại được bổ sung này gọi là các “ô chọn 0”.
Ví dụ 2: Trong bảng dưới đây có tập F gồm m + n − 1 = 4 + 3 − 1 = 7 ô chọn không chứa
vòng có đánh dấu “x”.
Ô (4, 4) của bảng không thuộc F.
Khi bổ sung ô (4, 4) vào F ta sẽ có vòng duy nhất: (1, 3) (1, 4) (4, 4) (4, 3)
X x x x
x
X
x (4,4)
4.2 Thuật toán thế vị giải bài toán vận tải cân bằng thu phát
4.2.1 Lập phương án cơ bản ban đầu
Áp dụng phương pháp chi phí bé nhất cho trường hợp cân bằng thu phát
m n
Bước 1: Kiểm tra ∑ ai = ∑ b j (cân bằng thu phát)
i =1 j =1
(4.2.1)
Bước 2: Chọn ô đầu tiên có cước phí vận chuyển bé nhất (i, j).
- 71 -
- ai
Bước 3: Chọn xij như sau: xij = min(ai , b j ) = b j (4.2.2)
a = b
i j
- Nếu xij = ai thì trạm phát i đã phát hết hàng, xóa hàng i của bảng và số
lượng thu còn lại tại trạm thu j chỉ còn là b j − ai ;
- Nếu xij = b j thì trạm thu j đã nhận đủ hàng, xóa cột j của bảng và số
lượng phát còn lại tại điểm phát i là ai − b j .
- Nếu xij = ai = b j thì trạm phát i và trạm thu j đều phát và nhận đủ hàng,
xóa hàng i và cột j của bảng.
Bước 4: Trong bảng còn lại với số hàng và số cột ít hơn, ta lại tiếp tục phân
phối như trên cho đến khi hết hàng.
Bước 5: Kiểm tra lại các ô chọn
- Nếu m + n − 1 = “số ô chọn” là P.A C.B của bài toán.
- Nếu m + n − 1 ≠ “số ô chọn” thì ta bổ sung thêm một số “ô chọn 0” cho
đủ m + n − 1 ô không tạo thành vòng.
Ví dụ 3: Tìm phương án cơ bản ban đầu của bài toán vận tải với các số liệu sau đây:
5 4 1
(cij ) = 3 2 6 ; (ai ) = ( 50 40 70 ) ; (b j ) = ( 80 20 60 ) .
7 9 11
m n
Giải: Ta thấy: ∑ ai = ∑ b j = 160 (cân bằng thu phát)
i =1 j =1
Ta đặt bài toán dưới dạng bảng:
bj 80 20 60
ai
5 4 1
50
3 2 6
40
7 9 11
70
- 72 -
- Thứ tự phân phối như sau:
Ô (1,3) được phân vào 50. Hàng 1 bị xóa, cột 3 còn cần 10.
Ô (2,2) được phân vào 20. cột 2 bị xóa, hàng 2 còn 20.
Ô (2,1) được phân vào 20. Hàng 2 bị xóa, cột 1 còn cần 60.
Ô (3,1) được phân vào 60. cột 1 bị xóa, hàng 3 còn 10.
Ô (3,3) được phân vào 10. Hết hàng.
bj 80 20 60
ai
5 4 1
50
50
3 2 6
40
20 20
7 9 11
70
60 10
Ta thấy có 5 ô chọn và m + n − 1 = 3 + 3 − 1 = “số ô chọn” nên chúng tạo thành
một phương án cơ bản không suy biến.
Phương án cơ bản ban đầu là:
0 0 50
X = 20 20 0
60 0 10
4.2.2 Thuật toán “Quy 0 cước phí các ô chọn”
Định lý: Nếu ta cộng vào hàng i và cột j của ma trận cước phí C = ( cij )mxn một số tuỳ ý
ri (i = 1, m) và sj ( j = 1, n) , ta sẽ có bài toán vận tải mới với ma trận cước phí
C ' = ( cij' ) (c
'
ij = cij + ri + s j ) tương đương với bài toán ban đầu.
mxn
Thuật toán: gồm 3 bước:
Bước 1: Quy 0 cước phí các ô chọn
- Xác định được một phương án cơ bản ban đầu. (xem mục 4.3.1)
- 73 -
- - Với m + n − 1 ô chọn, ta cộng vào hàng i và cột j của ma trận cước phí
C = ( cij ) một số tuỳ ý ri (i = 1, m) và sj ( j = 1, n) sao cho ma trận cước phí mới
mxn
C’ thỏa cij' = 0 (tức ri + s j + cij = 0 ).
Bước 2: Kiểm tra tính tối ưu
1. Sau khi quy 0 cước phí các ô chọn, nếu các ô loại đều có cước phí ≥ 0
thì phương án đang xét là tối ưu.
2. Sau khi quy 0 cước phí các ô chọn, nếu có ít nhất một ô loại có cước
phí < 0 thì phương án đang xét không phải tối ưu. Ta chuyển sang bước 3.
Bước 3: Xây dựng phương án mới tốt hơn
1. Chọn ô đưa vào: Ô đưa vào là ô (i*,j*) có cước phí âm nhỏ nhất.
2. Tìm vòng điều chỉnh: Bổ sung (i*,j*) vào m + n − 1 ô chọn ban đầu sẽ
xuất hiện vòng duy nhất, gọi là vòng điều chỉnh V.
3. Phân ô chẵn lẻ của vòng điều chỉnh V: Ta đánh số thứ tự các ô của
vòng V bắt đầu từ ô (i*,j*). Khi đó, V phân thành hai lớp:
VC: các ô có số thứ tự chẵn
VL: các ô có số thứ tự lẻ
4. Chọn ô đưa ra và lượng điều chỉnh:
- Tính giá trị nhỏ nhất trong 2 ô chẵn : min(c21 , c33 )
- Ô nào có phân ít hàng nhất làm ô đưa ra, còn lượng hàng ở ô
này là lượng điều chỉnh.
5. Lập phương án mới: Phương án mới được tính như sau:
- Ô có thứ tự chẵn được bớt đi lượng điều chỉnh
- Ô có thứ tự lẻ được cộng thêm lượng điều chỉnh
- Ô ngoài vòng điều chỉnh không thay đổi.
Ví dụ 4: Giải bài toán vận tải được cho trong ví dụ trên.
Bước 1: Quy 0 cước phí các ô chọn
- Phương án cơ bản ban đầu của bài toán (xem ví dụ 3)
- Ta thấy:
- 74 -
- bj 80 20 60
ai
5 4 1
50 r1 = 6
50
3 2 6
40 r2 = 0
20 20
7 9 11
70 r3 = −4
60 10
s1 = −3 s2 = −2 s3 = −7
Các giá trị ri và s j cộng vào phải thoả hệ phương trình:
1 + r1 + s3 = 0
3 + r + s = 0
2 1
2 + r2 + s2 = 0 (I)
7 + r + s = 0
3 1
11 + r3 + s3 = 0
Cho r2 = 0 , giải hệ (I) ta được kết quả trong bảng trên.
Áp dụng công thức cij' = cij + ri + s j ta có ma trận cước phí mới sẽ là:
8 8 0
50
0 0 -1
20 20
0 3 0
60 10
Bước 2: Kiểm tra tính tối ưu
Phương án chưa tối ưu vì còn ô loại (2, 3) có cước phí −1 < 0 . Ta chuyển sang
bước 3.
Bước 3: Xây dựng phương án mới tốt hơn
1. Chọn ô đưa vào: Ô loại (2, 3) là ô được đưa vào
(do (2, 3) có cước phí −1 < 0 nhỏ nhất)
- 75 -
nguon tai.lieu . vn
