BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH_ Chương 2: Bài toán vận tải

Chia sẻ: lethom1229

Vòng là tập hợp các ô đứng vị trí là đỉnh của một đường gấp khúc kín có các cạnh song song với dòng và cột của bảng, trong đó mỗi ô đều nằm cùng hàng chỉ với một ô đứng trước nó, đồng thời nằm cùng cột chỉ với một ô đứng sau nó...Một hệ vectơ điều kiện {Aij ; (i, j) Î K} của bài toán vận tải là độc lập tuyến tính khi và chỉ khi tập hợp các ô thuộc K không tạo thành vòng. Vì số vectơ {Aij} độc lập tuyến tính cực đại trong bài...

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH_ Chương 2: Bài toán vận tải

Trường Đại học kinh tế kỹ thuật công
nghiệp
Bộ môn khoa học cơ bản


BÀI GIẢNG
QUY HOẠCH TUYẾN TÍNH
Chương 2: Bài toán vận tải
TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
BỘ MÔN KHOA HỌC CƠ BẢN




BÀI GIẢNG


QUY HOẠCH TUYẾN TÍNH
CHƯƠNG II:

BÀI TOÁN VẬN TẢI

2.1. Dạng của bài toán vận tải
2.2. Xây dựng phương án cực biên
2.3. Phương pháp thế vị giải bài toán vận tải
2.4. Bài toán không cân bằng thu phát
2.1. Dạng của bài toán vận tải
Ai (i =1,…m): các trạm phát
Bj (j = 1,…n): các trạm thu
ai: lượng hàng hoá có ở trạm phát Ai
bj: lượng hàng hoá yêu cầu ở trạm thu Bj
cij: chi phí vận chuyển một đơn vị hàng hoá từ trạm phát

Ai (i = 1,.,m) đến trạm thu Bj (j = 1, 2,..., n) (cij > 0)
xij: lượng hàng hoá vận chuyển từ trạm phát Ai đến
trạHãy thành lập một phương án vận chuyển hàng hoá
m
sao cho đáp, ứng ≥ ầy ∀ủ j) cầu của các trạm thu bằng
đ 0 ( đ i, yêu
thu Bj xij
tất cả hàng hoá có ở các trạm phát với tổng chi phí vận
chuyển là nhỏ nhất.
( )
Tìm bộ giá trị { xij } i = 1, m; j = 1, n sao cho:
m n
f ( x) = ∑ ∑ cij xij ⇒ min (1)
i =1 j =1


(i = 1, m)
n

∑x = ai (2)
ij
j =1


( j = 1, n)
m

∑x = bj (3)
ij
i =1

(i = 1, m; j = 1, n)
xij ≥ 0 ( 4)
m n

∑ a = ∑b
Nếu thì bài toán vận tải cân bằng thu phát
i j
i =1 j =1
Mô tả bài toán dưới dạng bảng:

Thu b1 b2 …… bn
Phát
a1 c11 c12 …… c1n

a2 c21 c22 …… c2n

….. ….. …… …… ……

am cm1 cm2 …… cmn


Giao của hàng i và cột j gọi là ô (i, j) đặc trưng cho
đoạn đường nối trạm phát Ai và trạm thu Bj , ở ô này ghi
Một số khái
niệm:
Vòng: Là một tập hợp các ô đứng vị trí là đỉnh của một
đường gấp khúc khép kín có các cạnh song song với các
dòng và các cột của bảng, trong đó mỗi ô đều nằm cùng
hàng (cùng cột) chỉ với một ô đứng trước nó, đồng thời
nằm cùng cột (cùng hàng) chỉ với một ô đứng sau nó.
Một hệ vectơ điều kiện {Aij ; (i, j) ∈ K} của bài toán
vận tải là độc lập tuyến tính khi và chỉ khi tập hợp các ô
thuộc K không tạo thành vòng.
Vì số vectơ {Aij} độc lập tuyến tính cực đại trong bài
toán là m + n – 1 nên số tối đa các ô không tạo thành vòng
trong bảng m hàng và n cột cũng là m + n – 1.
Phương án cực biên: x = {xij} là phương án cực biên khi
và chỉ khi tập hợp các ô (i, j) tương ứng với các thành phần
dương của phương án không tạo thành vòng. Một phương án
cực biên có tối đa m + n – 1 thành phần dương.
Tập hợp m + n – 1 ô không tạo thành vòng bao hàm tập ô
tương ứng với các thành phần dương của phương án cực biên
x (xij > 0) gọi là tập ô cơ sở nó, ký hiệu là S.
Ô (i, j)∈S gọi là ô cơ sở, (i, j)∉S gọi là ô phi cơ sở.
Một ô phi cơ sở bất kỳ bao giờ cũng tạo thành một vòng duy
nhất với các ô cơ sở.
Một phương án cực biên không suy biến chỉ có một tập ô cơ
sở duy nhất, đó chính là tập ô tương ứng với các thành phần
dương của phương án.
Một phương án cực biên suy biến có nhiều tập ô cơ sở khác
nhau, phần chung của chúng là tập ô ứng với các thành phần
dương.
2.2. Xây dựng phương án cực biên
Khi xác định được xịj = α , ta nói là đã phân phối cho ô (i, j)
một lượng hàng là α.
Nguyên tắc phân phối tối đa: Lấy ô (i, j) bất kỳ của
bảng và phân phối cho nó một lượng hàng tối đa có thể,
nghĩa là đặt xij = min{ai ,bj}. Ba trường hợp có thể xảy ra:
- xij = ai , yêu cầu của trạm phát thỏa mãn, loại hàng i ra
khỏi bảng, đồng thời sửa lại yêu cầu của trạm thu: b’j = bj
- ai x = b , yêu cầu của trạm thu thỏa mãn, loại cột j ra
- ij j
khỏi bảng, đồng thời sửa lại yêu cầu của trạm phát: a’i = ai
- bj x = a = b ,yêu cầu của cả trạm thu và phát đều thỏa
- ij i j
mãn, loại đồng thời hàng i và cột j ra khỏi bảng.
Quá trình tiếp tục cho tới khi yêu cầu của mọi trạm thu và
phát đều thoả mãn.
Các ô được phân phối có xij > 0, đặt xij = 0 với những ô
không được phân phối
Khi đó sẽ thu được một phương án cực biên của bài toán.
Nếu số ô được phân phối là m + n – 1 thì phương án cực
biên thu được là không suy biến, tập ô được phân phối chính
là tập ô cơ sở.
Nếu số ô được phân phối nhỏ hơn m + n – 1 thì phương án
cực biên tương ứng là suy biến. Để có được một tập ô cơ sở
cần phải bổ sung, ô bổ sung có xij= 0 và không tạo thành
vòng với những ô cơ sở đã có, bổ sung cho tới khi đủ m + n –
1 ô.
Với những ô bổ sung khác nhau ta sẽ được các tập ô cơ sở
Sử dụng nguyên tắc phân phối tối đa, tuỳ thuộc vào cách
ưu tiên phân phối ta có những phương pháp khác nhau để
xây dựng phương án cực biên:

- Phương pháp tây-bắc: Luôn ưu tiên phân phối cho ô
nằm ở góc tây bắc của bảng.

- Phương pháp chi phí nhỏ nhất (đường gần): Luôn ưu
tiên phân phối cho ô có cij nhỏ nhất trong bảng.

- Phương pháp Fogels: Luôn ưu tiên phân phối cho ô có
cij nhỏ nhất nằm trên hàng hoặc cột có hiệu số giữa chi phí
nhỏ nhì và chi phí nhỏ nhất là lớn nhất.
Phương pháp chi phí nhỏ nhất:

Thu 30 20 25 35 40
Phát
30 13 7 6 2 12
x x x
x [30]
20 5 1 10 5 11
x
x x x
[20]
40 10 5 3 7 14
[0] x [5] [35]
x x
60 6 3 2 11 10
x
[30] [25] [5]
x
2.3. Phương pháp thế vị giải bài toán vận
tải: chuẩn tối ưu:
Tiêu
Điều kiện cần và đủ để phương án x = {xij} của bài toán vận
tải tối ưu là tồn tại một hệ thống số {ui, vj} thoả mãn:
a) vj – ui ≤ cij (∀i,j)
b) vj – ui = cij nếu xij > 0
ui, vj gọi là các thế vị hàng và cột.
Có thể xem ui là giá trị của một đơn vị hàng hoá ở nơi sản
xuất Ai, còn vj là giá trị của nó tại nơi tiêu thụ Bj.
Điều kiện b) có nghĩa là trong mọi phương án vận chuyển tối
ưu nếu hàng hoá được đưa từ trạm phát Ai đến trạm thu Bj thì
giá trị của nó tại nơi tiêu thụ Bj phải bằng giá trị tại nơi sản
xuất Ai cộng thêm chi phí vận chuyển cij .
Điều kiện a) có nghĩa là chênh lệch của giá trị hàng hoá giữa
nơi tiêu thụ và nơi sản xuất bất kỳ đều không vượt quá chi phí
Thuật toán của phương pháp thế vị:
Giả sử đã biết một phương án cực biên x với tập ô cơ sở S.
Bước 1: Xây dựng hệ thống thế vị {ui ,vj}:
Lấy một hàng i bất kỳ, cho nó một thế vị ui tùy ý. Các
thế vị còn lại được xác định theo quy tắc:
- Nếu hàng i đã có ui và (i, j)∈S thì thế vị của cột j được
tính bởi: vj = ui + cij .
- Nếu cột j đã có vj và (i, j)∈S thì thế vị của hàng i được
tính bởi: ui = vj − cij .
Quá trình tiếp tục cho tới khi xác định được toàn bộ
hệ thống thế vị
ước 2: Kiểm tra tiêu chuẩn tối ưu:
Tính đại lượng ∆ịj = vj – ui – cij đối với các ô phi cơ sở
((i, j) ∉ S).
-Nếu ∆ịj ≤ 0, ∀(i, j)∉S thì phương án tương ứng là tối
ưu. ếu tồn tại ∆ịj > 0, (ta gọi đó là các ô vi phạm) thì phải
-N
điều chỉnh phương án.
Bước 3: Điều chỉnh phương án:
Giả sử max ∆ ij = ∆ rk , ô (r, k) được lấy làm ô điều chỉnh.
∆ ij >0

Tìm vòng V tạo bởi ô điều chỉnh với các ô cơ sở. Trên
vòng đánh dấu lẻ chẵn các ô với ô điều chỉnh (r, k) là ô lẻ.
Ký hiệu Vl , Vc tương ứng là tập ô lẻ, chẵn trên vòng.
Xác định q = min {xij} , (i, j) ∈ Vc .
Thực hiện phép biến đổi trên vòng:
 xij , (i, j ) ∉ V

xij =  xij − q , (i, j ) ∈ Vc
'


xij + q , (i, j ) ∈ Vl

Kết quả của quá trình biến đổi ta được phương án cực
biên mới x’ tốt hơn x.
Sau điều chỉnh ô điều chỉnh trở thành ô cơ sở, ô ứng với
q sẽ trở thành ô phi cơ sở.

Đối với x’ quay trở lại bước 1, quá trình lặp lại sau một
số hữu hạn bước sẽ tìm được phương án cực biên tối ưu.
Ví dụ 1: Giải bài toán vận tải sau:


Thu 76 62 88 45 40
Phát
79 10 19 9 6 8

102 13 11 8 7 4

70 12 17 10 5 3

60 12 18 18 7 9
Dùng phương pháp chi phí nhỏ nhất xây dựng phương án
cực biên xuất phát:

Thu 76 62 88 45 40
Phát
79 10 19 9 6 8
[64] [15]
x x x
102 13 11 8 7 4
[14] [88]
x x x
70 12 17 10 5 3
[30] [40]
x x x
60 12 18 18 7 9
x x x
[12] [48]
Cho u4 = 0, lần lượt tính các thế vị hàng và cột khác:
12 15 8
18 6
Thu 76 62 88 45 40
Phát
79 10 19 9 6 8
2
[64] [15]
102 13 11 8 7 4
7
[14] [88]
70 12 17 10 5 3
3
[30] [40]
60 12 18 18 7 9
0
[12] [48]
Tính đại lượng ∆ịj = vj – ui – cij đối với các ô phi cơ sở
12 15 8
18 6
Thu 76 62 88 45 40
Phát
79 10 19 9 6 8
2
[64] [15]
+4
102 13 11 8 7 4
7
[14] [88]
70 12 17 10 5 3
3
[30] [40]
+2
60 12 18 18 7 9
0
[12] [48] +1
max ∆ ij = ∆13 = +4 , ô (1, 3) được lấy làm ô điều chỉnh.
∆ ij > 0
12 15 8
18 6
Thu 76 62 88 45 40
Phát
(*) 19 *6
79 10 9 8
2
[64] [15]
+4
(*) 7
102 13 11 *8 4
7 [14] [88]
70 12 17 10 5 3
3
[30] [40]
+2
(*) 18
* 18
60 12 7 9
0
[12] [48] +1
Xác định q = min {88, 48, 64} = 48. Thực hiện phép biến
đổi đối với các ô trên vòng, ta được phương án mới:
12 11 8
14 6
Thu 76 62 88 45 40
Phát
* 19 (*) 8
79 10 9 6
2
[16] [48] [15]
102 13 11 8 7 4
3
[62] [40]
70 12 17 10 5 3
3
[30] [40]
(*) 18 *9
60 12 18 7
0
[60] +1
q = min {15, 60} = 15, điều chỉnh ta được phương án mới:

12 11 7
14 5
Thu 76 62 88 45 40
Phát
79 10 19 9 6 8
2
[31] [48]
102 13 11 8 7 4
3
[62] [40]
70 12 17 10 5 3
2
[30] [40]
60 12 18 18 7 9
0
[45] [15]
Sau khi xây dựng hệ thống thế vị và kiểm tra tiêu chuẩn
tối ưu ta thấy: ∆ij ≤ 0 ∀(i, j)∉S .
Phương án tương ứng là tối ưu.
Giá trị tối ưu của hàm mục tiêu là:
f(x*) = 10.31 + 9.48 + 11.62 + 8.40 + 5.30 + 3.40 + 12.45
+ 7.15 = 2659.
Trường hợp suy biến:
Trường hợp suy biến thì q có thể bằng 0.
Khi q = 0 vẫn thực hiện thuật toán một cách bình thường,
nghĩa là ô điều chỉnh sẽ trở thành ô cơ sở với tư cách là
ô bổ sung, còn ô tương ứng với q sẽ trở thành ô phi cơ
sở.
Kết quả điều chỉnh không làm thay đổi phương án cực
biên mà chỉ chuyển từ tập ô cơ sở này sang tập ô cơ sở
khác.
Ví dụ 2: Giải bài toán vận tải sau:


Thu 95 80 65 35 95
Phát
110 7 6 14 9 13

100 10 2 9 8 10

60 5 5 9 6 12

100 14 3 12 4 18
Dùng phương pháp chi phí nhỏ nhất xây dựng phương án
cực biên xuất phát:

Thu 95 80 65 35 95
Phát
110 7 6 14 9 13
[35] x x [75]
x
100 10 2 9 8 10
[80] [20]
x x x
60 5 5 9 6 12
x x x x
[60]
100 14 3 12 4 18
x [45] [35] [20]
x
Xác định hệ thống thế vị và kiểm tra tiêu chuẩn tối ưu
12 12 4
5 18
Thu 95 80 65 35 95
Phát
110 7 6 14 9 13
5
[35] [75]
100 10 2 9 8 10
3
[80] [20] +5
60 5 5 9 6 12
7
[60]
100 14 3 12 4 18
0
[45] [35] [20]
+2
lấy ô (2, 5) làm ô điều chỉnh
max ∆ ij = ∆ 25 = 5
∆ ij > 0

12 12 4
5 18
Thu 95 80 65 35 95
Phát
110 7 6 14 9 13
5
[35] [75]

(*)
100 10 2 9 8 10 *
3 [80] [20] +5
60 5 5 9 6 12
7
[60]
(*)
100 14 3 12 4 18
*
0
[45] [35] [20]
+2
q = min {20 ; 20} = 20 ứng với ô (2, 3) và (4, 5).
Loại ô (4, 5) ra khỏi tập ô cơ sở được phương án mới:
7 5 12 4 13
Thu 95 80 65 35 95
Phát
110 7 6 14 9 13
0
[35] [75]

(*)
100 10 2 9 8 10
*
3
[80] [0] [20]
60 5 5 9 6 12
2 [60] +1
100 14 3 12 4 18
(*)
*
0 [65] [35]
+2
q = min {80 ; 65} = 65 ứng với ô (4, 3).
Loại ô (4, 3) ra khỏi tập ô cơ sở được phương án mới:
6 13
7 5 12
Thu 95 80 65 35 95
Phát
(*)
110 7 6 14 9 13
*
0
[35] [75]

(*)
100 10 2 9 8 10 *
3
[15] [65] [20]

(*)
60 5 5 9 6 12
*
2
[60] +1
100 14 3 12 4 18
2
[65] [35]
q = min {65 ; 75 ; 60} = 60
7 5 12 6 13
Thu 95 80 65 35 95
Phát
110 7 6 14 9 13
0
[95] [15]
100 10 2 9 8 10
3 [15] [5] [80]
60 5 5 9 6 12
3 [60]
100 14 3 12 4 18
2
[65] [35]

∆ij ≤ 0 ∀(i, j)∉S . Phương án là tối ưu: f(x*) = 2610
2.4. Bài toán không cân bằng thu phát:
m n
1. Trường hợp ∑ ai > ∑ b j
i =1 j =1
m n

∑a − ∑b
Lập một trạm thu giả Bn+1 với yêu cầu: n +1 =
b i j
i =1 j =1
chi phí vận chuyển bằng 0

m n

∑ a < ∑b
2. Trường hợp i j
i =1 j =1

n m

∑b − ∑ a
Lập một trạm phát giả Am+1 với yêu cầu: m +1 =
a j i
j =1 i =1
chi phí vận chuyển bằng 0
Ví dụ 3: Giải bài toán vận tải sau:


Thu 78 56 65 51
Phát
85 8 3 5 12

60 4 8 8 10

75 11 15 16 9

80 10 13 18 11
m n

∑a > ∑b
Bài toán không cân bằng thu phát : i j
i =1 j =1


Thêm vào một trạm thu giả với yêu m n
bn +1 = ∑ ai − ∑ b j = 50
cầu:
i =1 j =1

Thu 78 56 65 51 50
Phát
85 8 3 5 12 0

60 4 8 8 10 0

75 11 15 16 9 0

80 10 13 18 11 0
Dùng phương pháp chi phí nhỏ nhất xây dựng phương án
cực biên xuất phát:

Thu 78 56 65 51 50
Phát
85 8 3 5 12 0
x x
[56] [29] x
60 4 8 8 10 0
x
[60] x x x
75 11 15 16 9 0
x x
[51]
[24]
x
80 10 13 18 11 0
[18] [12] [50]
x x
11
10 16 0
18
Thu 78 56 65 51 50
Phát
85 8 3 5 12 0
13
[56] [29]
60 4 8 8 10 0
(*) *
6
[60] +2 +4
75 11 15 16 9 0
2
[24] [51]
80 10 13 18 11 0
(*)
*
0
[18] [12] [50]
+3

q = min {60 ; 12} = 12
12 9 2
14 16
Thu 78 56 65 51 50
Phát
85 8 3 5 12 0
11
[56] [29]
(*)
60 4 8 8 10 0
*
8
[48] [12]
75 11 15 16 9 0
(*) *
0
[24] [51]
+1 +2
80 10 13 18 11 0
* (*)
2 [30] [50]

q = min {50 ; 48 ; 24} = 24
12 14 9 0
10
Thu 78 56 65 51 50
Phát
85 8 3 5 12 0
9
[56] [29]
60 4 8 8 10 0
6
[24] [36]
75 11 15 16 9 0
0
[51] [24]
80 10 13 18 11 0
0
[54] [26]
∆ij ≤ 0 ∀(i, j)∉S . Phương án là tối ưu: f* = 1696
x*35 = 24 ; x*45 = 26 là lượng hàng giữ lại ở trạm phát A3 và A4
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản