Qui hoạch Toán học - Chương 4: Bài toán vận tải
BTVT” với hàm mục tiêu cực đại
Có mô hình giống BTVT, nhưng hàm mục tiêu cực đại.
• Dấu hiệu tối ưu: ∆ ≥ ∀ ij 0, ( , ) i j
• Chọn ô
• Nếu có ô cấm , thay , với là số dương
rất lớn.
• Chọn ô có lớn nhất phân phối trước.
( , ) i j * *
∆ = ∆ ∆ < i j * * min{ : 0} ij ij
( , ) i j c M ij = − M
cij
30 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1004 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Qui hoạch Toán học - Chương 4: Bài toán vận tải, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 4
BÀI TOÁN VẬN TẢI
20/6/2012 1MaMH: C01019 Chương 4: Bài toán vận tải
NỘI DUNG
1. Bài toán vận tải dạng tổng quát
1.1 Phát biểu bài toán vận tải (BTVT)
1.2 Đặt bài toán vận tải dưới dạng bảng
1.3 Các tính chất của bài toán vận tải
2. Thuật toán thế vị
2.1 Tiêu chuẩn tối ưu
2.2 Thuật toán
3. Các trường hợp đặc biệt của BTVT
20/6/2012 2MaMH: C01019 Chương 4: Bài toán vận tải
Bài toán vận tải dạng tổng quát
1. Phát biểu bài toán
Có m điểm phát với lượng phát tương ứng
phát hàng đến n điểm thu với
lượng thu tương ứng
x
,iS
, 1,..., ;ia i m= ,jT
, 1,..., .jb j n=
với: là cước phí vận chuyển 1 đơn vị hàng từ
điểm phát đến điểm thu
là lượng hàng được vận chuyển từ đến
20/6/2012 3MaMH: C01019 Chương 4: Bài toán vận tải
: :ij
iji i j jcS a T b→
ijc
, 1,...,iS i m= , 1,...,jT j n=
ijx iS
1,..., ; 1,..., .i m j n= =
,jT
Bài toán vận tải dạng tổng quát
Vấn đề: Lập kế hoạch vận chuyển như thế nào để
tổng cước phí vận chuyển là bé nhất? Biết rằng
hàng hóa có thể vận chuyển từ một điểm phát bất
kỳ đến một điểm thu bất kỳ.
20/6/2012 4MaMH: C01019 Chương 4: Bài toán vận tải
Bài toán vận tải dạng tổng quát
Mô hình bài toán có dạng:
1 1
( ) min
, 1,...,
n m
ij ij
j i
n
f X c x
x a i m
= =
= →
= =
∑∑
∑
20/6/2012 5MaMH: C01019 Chương 4: Bài toán vận tải
1
1
, 1,...,
0, 1,..., ; 1,...,
ij i
j
m
ij j
i
ij
x b j n
x i m j n
=
=
= =
≥ = =
∑
Bài toán vận tải dạng tổng quát
Điều kiện cân bằng thu phát:
1 1
m n
i j
i j
a b
= =
=∑ ∑
20/6/2012 6MaMH: C01019 Chương 4: Bài toán vận tải
Bài toán vận tải dạng tổng quát
2. Đặt bài toán dưới dạng bảng
T1 : b1 Tj : bj Tn : bn
S1 : a1
c11 c1j c1n
Thu
Phát
... ...
11x 1 jx 1nx
20/6/2012 7MaMH: C01019 Chương 4: Bài toán vận tải
Si : ai
ci1 cij cin
Sm : am
cm1 cmj cmn
⋮
⋮
......
......
1ix ijx inx
1mx mjx mnx
Bài toán vận tải dạng tổng quát
Định nghĩa 1 Một tập hợp các ô thỏa mãn tính chất:
• 2 ô liên tiếp cùng nằm trên cùng 1 hàng hay 1 cột;
• 3 ô liên tiếp không cùng nằm trên cùng 1 hàng hay 1
cột
được gọi là một dây chuyền.
Một dây chuyền khép kín được gọi là một chu trình.
20/6/2012 8MaMH: C01019 Chương 4: Bài toán vận tải
Bài toán vận tải dạng tổng quát
Định nghĩa 2
Những ô có được gọi là ô chọn, những ô
còn lại được gọi là ô loại.
0ijx >
Định nghĩa 3 Một phương án (PA) mà các ô chọn
không tạo thành chu trình đgl PA cơ bản (PACB).
Một PACB đủ (m + n – 1) ô chọn đgl PACB không
suy biến.
20/6/2012 9MaMH: C01019 Chương 4: Bài toán vận tải
Bài toán vận tải dạng tổng quát
3. Các tính chất của BTVT
i. BTVT cân bằng thu phát luôn luôn có PATƯ.
ii. Trong 1 PACB bất kỳ, tổng số ô chọn luôn nhỏ
hơn hoặc bằng tổng số điểm phát và thu trừ đi 1.
(Số ô chọn ).
iii. Với PACB có đủ ô chọn, thì với 1 ô loại
bất kỳ sẽ tạo thành một chu trình duy nhất với một
số ô chọn.
20/6/2012 10MaMH: C01019 Chương 4: Bài toán vận tải
( 1)m n≤ + −
( 1)m n+ −
Thuật toán thế vị
1. Tiêu chuẩn tối ưu
Xét BTVT cân bằng thu phát
1 1
( ) min
m n
ij ij
i j
f x c x
= =
= →∑∑
20/6/2012 11MaMH: C01019 Chương 4: Bài toán vận tải
1
1
, 1,...,
, 1,...,
0, 1,..., ; 1,...,
n
ij i
j
m
ij j
i
ij
x a i m
x b j n
x i m j n
=
=
= =
= =
≥ = =
∑
∑
Thuật toán thế vị
Bài toán đối ngẫu của bài toán trên:
1 1
( , ) max
, 1, ; 1, .
m n
i i j j
i j
i j ij
g u v a u b v
i mu v c j n
= =
= + →
= =+ ≤
∑ ∑
20/6/2012 12MaMH: C01019 Chương 4: Bài toán vận tải
Thuật toán thế vị
Định lý 1
PA của BTVT là PATƯ khi và chỉ khi tìm
được các số thỏa mãn:
( )ijX x=
, , 1, ; 1,i ju v i m j n= =
, ( , )u v c i j+ ≤ ∀
20/6/2012 13MaMH: C01019 Chương 4: Bài toán vận tải
, ( , ) ( ),
( ) {( , ) : 0}
i j ij
i j ij
ij
u v c i j G X
G X i j x
+ = ∀ ∈
= >
Thuật toán thế vị
2. Thuật toán thế vị
- Bước 1 (Bước khởi tạo)
Tìm PACB xuất phát theo nguyên tắc phân
phối tối đa:
0 0( )ijX x=
Giả sử cần phân phối cho ô (i,j). Lượng hàng tối đa
có thể phân phối là
Sau đó, điều chỉnh lại các yêu cầu:
20/6/2012 14MaMH: C01019 Chương 4: Bài toán vận tải
min{ , }ij i jx a b=
i i ij
j j ij
a a x
b b x
′ = −
′ = −
Thuật toán thế vị
• Nếu , thì loại dòng i.
• Nếu , thì loại cột j.
• Nếu , thì loại cả dòng i và cột j.
0ia′ =
0jb′ =
0i ja b′ ′= =
20/6/2012 15MaMH: C01019 Chương 4: Bài toán vận tải
Thuật toán thế vị
Ví dụ 1
30 60 46 25
50 4 7 12 7
bj
ai
19
x
20/6/2012 16MaMH: C01019 Chương 4: Bài toán vận tải
70 5 9 6 1
41 8 2 9 1
41
x
19
51
Thuật toán thế vị
Ta được bảng mới thu gọn.
Lặp lại hai phép toán trên với bảng mới thu gọn
đến khi yêu cầu của điểm phát và điểm thu được
thỏa mãn.
Các ô được phân phối có những ô còn lại
có
20/6/2012 17MaMH: C01019 Chương 4: Bài toán vận tải
0,ijx >
0.ijx =
Thuật toán thế vị
Dựa vào nguyên tắc phân phối tối đa và cách thức
chọn ô ưu tiên phân phối, xét 3 phương pháp:
i. Phương pháp góc Tây Bắc: ô đầu tiên được chọn
để phân phối là ô ở vị trí góc Tây Bắc (ô (1,1)).
ii. Phương pháp cực tiểu cước phí: ô đầu tiên được
chọn để phân phối là ô có cước phí bé nhất.
iii. Phương pháp Fogel: trên mỗi hàng, cột chọn ra
hai ô có cước phí bé nhất (bé nhì), lấy hiệu số
của chúng. Ô có cước phí bé nhất tương ứng ở
hàng, cột có hiệu số lớn nhất sẽ là ô đầu tiên
được chọn để phân phối.
20/6/2012 18MaMH: C01019 Chương 4: Bài toán vận tải
Thuật toán thế vị
Nếu PACB tìm được có đủ ô chọn, thì
sang Bước 2.
Ngược lại, thêm vào ô nào đó một lượng hàng
sao cho:
( 1)m n+ −
( , )i j
0ijx =
• đủ số
• và ô này không tạo thành chu trình với các ô
chọn.
→ Bước 2.
20/6/2012 19MaMH: C01019 Chương 4: Bài toán vận tải
( 1)m n+ −
( , )i j
Thuật toán thế vị
- Bước 2 (Bước lặp)
Ở đầu bước lặp đã có PACB đủ ô chọn.
i. Xác định các thế vị
( 1)m n+ −
, , 1, ; 1,i ju v i m j n= =
, ( , ) ( )i j iju v c i j G X+ = ∀ ∈
Chọn u1 = 0.
ii. Tính các ước lượng theo công thức:
20/6/2012 20MaMH: C01019 Chương 4: Bài toán vận tải
, ( , )ij i j iju v c i j∆ = + − ∀
Thuật toán thế vị
iii. Kiểm tra tiêu chuẩn tối ưu
Nếu thì PA đang xét là PATƯ. Ngược
lại, chuyển sang iv.
iv. Chọn ô là ô có ước lượng dương lớn
nhất:
0, ( , )ij i j∆ ≤ ∀
* *( , )i j
Khi đó, ô sẽ tạo nên một chu trình duy nhất
với một số ô chọn.
→ Ô sẽ là ô chọn ở bảng mới.
20/6/2012 21MaMH: C01019 Chương 4: Bài toán vận tải
* *
max{ : 0}ij iji j∆ = ∆ ∆ >
* *( , )i j
* *( , )i j
Thuật toán thế vị
Đặt tên chu trình là K. Đánh dấu +, - xen kẽ vào
các ô thuộc K, bắt đầu từ ô mang dấu +.
Đặt :
= { những ô mang dấu +}
* *( , )i j
K +
= { những ô mang dấu -}
20/6/2012 22MaMH: C01019 Chương 4: Bài toán vận tải
K −
Thuật toán thế vị
Tiến hành điều chỉnh PA ta có PA mới
với
( ),ijX x=
( ),ijX x=
( , ) ,
( , ) ,
ijx i j K
x x i j Kθ +
∉
= + ∈
trong đó,
→ Ô là ô loại ở bảng mới.
Thay X bởi và lặp lại Bước lặp.
20/6/2012 23MaMH: C01019 Chương 4: Bài toán vận tải
( , ) ,
ij ij
ijx i j Kθ −
− ∈
0 0
min{ : ( , ) }i j ijx x i j Kθ −= = ∈
0 0( , )i j
X
Thuật toán thế vị
30 60 46 25
50 4 7 12 7
30 20
ai
bj
u1= 0
-8 -1
20/6/2012 24MaMH: C01019 Chương 4: Bài toán vận tải
70 5 9 6 1
41 8 2 9 1
16
24
25+
-
-
+
v2= 7
u2= 2
v3= 4
u3= -5
v4= 6v1= 4
1
-9 -10
746
24θ =
Thuật toán thế vị
Ví dụ 2 (tt)
30 60 46 25
50 4 7 12 7
30 20
ai
bj
u1= 0
-1 -1
20/6/2012 25MaMH: C01019 Chương 4: Bài toán vận tải
70 5 9 6 1
41 8 2 9 1
2446
1
v2= 7
u2= -5
v3= 11
u3= -5
v4= 6v1= 4
-6
-9 -3
-7
40
Thuật toán thế vị
Vì nên
PATƯ
0, ( , )ij i j∆ ≤ ∀
*
30 20 0 0
0 0 46 24
0 40 0 1
X
=
Giá trị tối ưu:
20/6/2012 26MaMH: C01019 Chương 4: Bài toán vận tải
*( ) 4 30 7 20 6 46 24 2 40 1
641.
f X = × + × + × + + × +
=
Các trường hợp đặc biệt của BTVT
i. BTVT không cân bằng thu phát
a. Phát > Thu:
1 1
m n
i j
i j
a b
= =
>∑ ∑
→ Đưa về BTVT cân bằng thu phát
→ Thêm một điểm thu giả, lượng hàng tương ứng
20/6/2012 27MaMH: C01019 Chương 4: Bài toán vận tải
1
1 1
;
m n
n i j
i j
b a b+
= =
= −∑ ∑ ( 1) 0, 1 .,i nc i m+ = ∀ =
Các trường hợp đặc biệt của BTVT
b. Phát < Thu
→ Đưa về BTVT cân bằng thu phát
1 1
m n
i j
i j
a b
= =
<∑ ∑
→ Thêm một điểm phát giả, lượng hàng tương ứng
20/6/2012 28MaMH: C01019 Chương 4: Bài toán vận tải
1
1 1
;
n m
m j i
j i
a b a+
= =
= −∑ ∑ ( 1) 0, 1 .,m jc j n+ = ∀ =
Các trường hợp đặc biệt của BTVT
ii. BTVT có ô cấm
Ô cấm: ô không được nhận hàng.
Giả sử ô là ô cấm.
→ Thay , với là số dương rất lớn.
( , )i j
ijc M= M
20/6/2012 29MaMH: C01019 Chương 4: Bài toán vận tải
Các trường hợp đặc biệt của BTVT
iii. “BTVT” với hàm mục tiêu cực đại
Có mô hình giống BTVT, nhưng hàm mục tiêu cực đại.
• Dấu hiệu tối ưu: 0, ( , )ij i j∆ ≥ ∀
• Chọn ô
• Nếu có ô cấm , thay , với là số dương
rất lớn.
• Chọn ô có lớn nhất phân phối trước.
20/6/2012 30MaMH: C01019 Chương 4: Bài toán vận tải
* *( , )i j
* *
min{ : 0}ij iji j∆ = ∆ ∆ <
( , )i j ijc M= − M
ijc
Các file đính kèm theo tài liệu này:
- quyhoachtuyentinhchuong_3_2981.pdf