Cách giải bài toán quy hoạch tuyến tính bài toán vận tải

QUY HOẠCH TUYẾN TÍNH CHƯƠNG 3. BÀI TOÁN VẬN TẢI

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [651.29 KB, 15 trang ]

QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

CHƯƠNG 3. BÀI TỐN VẬN TẢI
1

Bài tốn cân bằng

2

Phương án cực biên

3

Thuật tốn thế vị

4

Một số trường hợp đặc biệt

1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT
1.1. Lập mơ hình bài tốn:
Có một loại hàng cần được chun chở từ hai
kho [trạm phát] P1 và P2 tới ba nơi tiêu thụ [trạm thu]
T1, T2, T3 . Lượng hàng có ở hai kho và lượng hàng
cần ở ba nơi tiêu thụ cũng như số tiền vận chuyển một
đơn vị hàng từ mỗi kho đến các nơi tiêu thụ được cho
ở bảng sau:

1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT


THU
PHÁT
P1
30 tấn
P2
75 tấn

T1
35 tấn

T2
25 tấn

T3
45 tấn

5

2

3

2

1

1

Tìm phương án vận chuyển thỏa yêu cầu về thu
phát sao cho chi phí vận chuyển bé nhất.


Nguyễn Hoàng Tuấn soạn thảo

1


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT
1.2. Bài tốn cân bằng:
Giả sử có m kho là nơi phát hay cung cấp hàng
hoá, kho thứ i chứa ai đơn vị hàng hố [i = 1,2,..,m];
có n nơi tiêu thụ hay nhận hàng hoá, nơi nhận thứ j
cần bj đơn vị hàng hố [j = 1,2,..,n].
Giá tiền hay cước phí vận chuyển một đơn vị
hàng hóa từ kho thứ i đến nơi nhận thứ j là cij đơn vị
tiền tệ.
Bài toán được gọi là cân bằng nếu tổng lượng
m
n
phát = tổng lượng thu:
ai b j
i 1

j 1

1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT


Bài toán vận tải thường cho dưới dạng bảng sau:
Thu

b1

b2



bj

.

bn

Phát
a1

c11

c12

c1 j

c1n

a2

c21


c22

c2 j

c2n


ai

ci 1

ci 2

cij

cin


am

cm 1

cm 2

cmj

cmn

u cầu bài tốn: tìm cách phân bổ lượng hàng vận
chuyển xij từ trạm phát i đến trạm thu j thỏa:


1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT

Tổng chi phí vận chuyển thấp nhất
m n
f cij xij min
[1.2]
i 1 j 1

Tổng lượng hàng phát đi
n
xij ai i 1, m

[1.3]

Tổng lượng hàng nhận về
m
xij b j j 1, n

[1.4]

j 1

i 1

Một phương án bài toán [bộ xij thỏa 1.3 và 1.4] có
dạng ma trận nên cũng gọi là ma trận phương án.

Nguyễn Hoàng Tuấn soạn thảo


2


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT
Ví dụ: Xét lại bài toán vận tải đã biết ở trên
THU
PHÁT
P1
30 tấn
P2
75 tấn

T1
35 tấn

T2
25 tấn

T3
45 tấn

5

2

3


2

1

1

bài toán vận tải cân bằng thu phát

1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT
1.3. Tính chất:
Bài tốn có tập phương án khác rỗng và ln có
phương án tối ưu.
Ma trận cước phí có hạng = m + n 1.

2. PHƯƠNG ÁN CỰC BIÊN
2.1. Ơ chọn, ơ loại:

§2

Ta viết [i ; j] là ô dòng i và cột j của bảng.
Những ô trong bảng có lượng hàng phân phối xij > 0
gọi là ô chọn. Ngược lại, những ô có lượng hàng phân
phối xij = 0 gọi là ơ loại.

Nguyễn Hồng Tuấn soạn thảo

3



QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

2. PHƯƠNG ÁN CỰC BIÊN
2.2. Tập ô đường đi:
Tập ô đường đi [gọi tắt đường đi] là tập hợp
các ô trong bảng thỏa có một và chỉ một ơ khác cũng
thuộc đường đi nằm trên cùng dịng hoặc cùng cột
với nó, gọi là hai ơ liên tiếp.
Nhận xét: Trên một dịng hay cột của đường đi
có khơng q hai ơ.

2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 1.











2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 2.











Nguyễn Hoàng Tuấn soạn thảo

4


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

2. PHƯƠNG ÁN CỰC BIÊN
2.3. Chu trình:
Một đường đi khép kín được gọi là một chu trình.
Ví dụ 1.












2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 2.













2. PHƯƠNG ÁN CỰC BIÊN
2.4. Tính chất:
Xét bảng vận tải có m dịng và n cột.
a] Tập ơ chọn khơng là chu trình có khơng q [m
+ n 1] ơ.
b] Tập ơ chọn khơng là chu trình có đủ [m + n 1]
ơ. Ta thêm vào tập ơ này một ơ loại bất kì thì ơ này
cùng với một số ơ chọn đã có sẽ tạo thành chu trình
duy nhất đi qua nó.

Nguyễn Hồng Tuấn soạn thảo

5



QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 2.4. Xét bài tốn vận tải có 3 dịng, 4 cột với
một phương án có 3 + 4 1 = 6 ô chọn:











2. PHƯƠNG ÁN CỰC BIÊN
2.5. Phương án cực biên:
Phương án cực biên trong bài tốn vận tải là
phương án có tập ơ chọn của nó khơng chứa chu
trình.

2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 2.4. Xét phương án trong bài toán vận tải cho
bởi bảng sau:
30

80
45
55

40

50

5

7

5

7

4

12

2

1

30

40

Nguyễn Hoàng Tuấn soạn thảo


3

60
2

35
15

9

50
10

6

6


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

2. PHƯƠNG ÁN CỰC BIÊN
2.6. Phương pháp thành lập
2.6.1. Nguyên lý phân bổ tối đa ô chọn.
Phân bổ lượng hàng nhiều nhất có thể cho ơ đã được
chọn xij = min{ai ; bj}, có hai trường hợp sau:
Trạm thu nhận đủ hàng thì tạm xố trạm này và ghi
nhớ lượng hàng thừa ở nơi phát.
Trạm phát chuyển hết hàng thì tạm xóa trạm phát

này và ghi nhớ lượng hàng còn thiếu ở nơi thu.

2. PHƯƠNG ÁN CỰC BIÊN
2.6. Phương pháp thành lập
2.6.2. Nguyên tắc chọn ô phân bổ.
Ba cách:
- Góc Tây Bắc: từ trên xuống dưới và từ trái qua phải
ô đầu tiên [1;1] dễ nhớ nhưng phương án tìm
được kém [f cách xa f tối ưu]
- Ơ có cước phí nhỏ nhất dễ nhớ, phương án vừa
- Ơ chọn Fogel khó nhưng phương án tìm được
tốt [f rất gần f tối ưu], thực hiện như sau:

2. PHƯƠNG ÁN CỰC BIÊN
+ Bước 1: Tính hiệu số giữa hai ơ có cước phí nhỏ
nhất của mỗi dịng và mỗi cột của ma trận cước phí.
+ Bước 2: Ơ được chọn là có ơ cước phí nhỏ nhất
của dịng hay cột có hiệu số này lớn nhất.
Hai nguyên tắc này phối hợp xen kẽ nhau và lặp lại
đến khi ta được phương án hoàn chỉnh.

Nguyễn Hoàng Tuấn soạn thảo

7


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI


2. PHƯƠNG ÁN CỰC BIÊN
Ví dụ 2.6. Thành lập một phương án cực biên của bài
tốn vận tải sau:
j

30

40

50

60

i
80

1

5

7

2

45

5

7


4

9

55

12

2

3

6

3. THUẬT TỐN THẾ VỊ
1: Thành lập phương án cực biên ban đầu
§BƯỚC
3
[xuất phát] theo Nguyên lý phân bổ tối đa với các ô
chọn phân bổ bằng các phương pháp: góc Tây Bắc,
cước phí thấp nhất, Fogel,
BƯỚC 2: Xét dấu hiệu tối ưu của phương án.
Tìm các biệt số dịng ui và biệt số cột vi của phương
án bằng cách giải hệ phương trình ơ chọn:

ui

vj

cij


3. THUẬT TỐN THẾ VỊ
BƯỚC 2: Xét dấu hiệu tối ưu của phương án.
Hệ này chứa [m + n] ẩn nhưng chỉ có nhiều nhất
[m + n 1] phương trình có một ẩn được chọn
trước làm tham số kĩ thuật giải: cho ẩn mà
hàng/cột của nó có nhiều ơ chọn nhất bằng 0.
Tính các ước lượng cho các ô loại:
ui v j cij
ij
Nếu mọi 0 phương án đang xét tối ưu.
Ngược lại, nếu có > 0 phương án khơng tối ưu
Bước 3

Nguyễn Hồng Tuấn soạn thảo

8


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.1. Xét khả năng tối ưu của phương án trong
bảng vận tải sau:
j

30


i
80

1

45

55

40

50

60

5

7

2

5

7

4

9

12


2

3

30

50

35

10
6

40

15

3. THUẬT TOÁN THẾ VỊ
Ví dụ 3.2. Xét khả năng tối ưu của phương án trong
bảng vận tải sau:
30
80

40

1

50


60

5

7

2
9

30

50

45

5

7

4

55

12

2

3

45

6

40

5

10

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.3. Xét khả năng tối ưu của phương án trong
bảng vận tải sau :
j

30

i
1

40

50

60

5

7

2


7

4

9

2

3

80
20
5

60

45
10
12

35
6

55
40

Nguyễn Hoàng Tuấn soạn thảo

15


9


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

3. THUẬT TOÁN THẾ VỊ
BƯỚC 3: Cải tiến phương án cực biên mới tốt hơn.
Đưa ơ loại có ước lượng lớn nhất bổ sung thành ô
chọn của phương án ô này kết hợp với một số ô
chọn đã có trong phương án tạo thành chu trình K
duy nhất đi qua nó.
Đánh dấu âm/dương +/ xen kẽ cho chu trình K
này. Bắt đầu từ ơ chọn mới bổ sung mang dấu + đến
hết. Sau đó chia chu trình K thành hai tập ô sau:
K+ = {ô [i ; j] mang dấu +}
K = {ô [i ; j] mang dấu }

3. THUẬT TOÁN THẾ VỊ
BƯỚC 3: Cải tiến phương án cực biên mới tốt hơn.
Xác định lượng hàng điều chỉnh:
q = min{xij, với [i ; j] ϵ K}
Xây dựng phương án cực biên mới từ phương án
cực biên cũ đang có như sau:

xij q;[i, j ] K

xij xij q;[i, j ] K


x
;[i, j ] K
ij

3. THUẬT TOÁN THẾ VỊ
Ví dụ 3.5. Từ phương án này, hãy tìm phương án tối
ưu của bài tốn.
j

30

i
80

1

45

55

40

50

60

5

7


2

5

7

4

9

12

2

3

30

50

35

40

Nguyễn Hồng Tuấn soạn thảo

10
6

15


10


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.6. Từ phương án này, hãy tìm phương án tối
ưu của bài tốn.
30
80

40

1

50

60

5

7

2
9

30


50

45

5

7

4

55

12

2

3

45
6

40

5

10

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.7. Từ phương án này, hãy tìm phương án tối

ưu của bài tốn.
j

30

i

40

1

5

50
7

60
2

80
30

40

10

5

7


4

12

2

3

9

45
40

5
6

55
55

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.8. Giải bài toán vận tải với phương án cực
biên ban đầu được cho trong bảng sau:
30
90
70
40

50

3


80

2

5

4

1

3

7

4

30

40
1

20
50

Nguyễn Hoàng Tuấn soạn thảo

40
6


20
2

5
40

11


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

3. THUẬT TỐN THẾ VỊ
Ví dụ 3.9. Giải bài tốn vận tải:
50
80
20
60

40

70

5

5

12


7

9

11

4

2

3

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
4.1. Phương án suy biến.
Phương án suy biến là phương án có ít hơn
[m + n 1] ơ chọn.
Cách giải bài tốn vận tải có phương án cực biên
ban đầu suy biến: bổ sung thêm các ơ loại bất kì của
bảng làm ơ chọn giả [lượng hàng phân bổ xij = 0] cho
đủ [m + n 1] ô chọn và đảm bảo không tạo thành
chu trình phương án cực biên khơng suy biến
tiếp tục giải bằng thuật toán thế vị.

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
Ví dụ 4.1.1. Giải bài tốn bảng vận tải từ phương án
vận chuyển ban đầu sau:
j

40


i
1

100

60

2

4

2

4

5

4

1

2

50
3

80
40

40

1

70
20

50
5

100
100

Nguyễn Hoàng Tuấn soạn thảo

12


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
Ví dụ 4.1.2. Giải bài tốn vận tải với phương án ban
đầu sau:
25
10
30
20

25


10

5

3

5

7

6

8

10
25
3

5
2

2
20

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
4.2. Bài tốn vận tải khơng cân bằng thu phát
Hướng giải quyết: Thêm vào các trạm phát/thu giả
có cước phí = 0 để chuyển bài tốn thành cân bằng.
Trường hợp phát > thu thêm trạm thu giả bn+1
với lượng hàng = Σphát Σthu

Trường hợp phát < thu thêm trạm phát giả
am+1 với lượng hàng = Σthu Σphát

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
Ví dụ 4.2. Giải bài tốn vận tải khơng cân bằng thu
phát cho bởi bảng vận tải sau:
j

40

50

80

i
90

6

1

1

40

5

7

4


70

4

11

3

Nguyễn Hoàng Tuấn soạn thảo

13


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
4.3. Bài tốn có ơ cấm
Vì một lí do nào đó, có một nơi phát khơng thể
chuyên chở hàng đến một nơi nhận được.
Phương pháp giải: xóa cấm và gán cước phí giả =
. Tiếp tục giải bài toán bằng thuật toán thế vị đã học.

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
Ví dụ 4.3. Giải bài tốn vận tải có ơ cấm cho bởi bảng
sau:
j


100

i
80
70
150

6

65
5

10
9

8

95

40

11

10

5

7

7


4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
4.4. Bài toán lợi nhuận lớn nhất
Bài toán vẫn giải bằng thuật toán thế vị như trên
nhưng với nguyên tắc chọn ô chọn ngược lại: ô chọn
là ơ có lợi nhuận lớn nhất.

Nguyễn Hồng Tuấn soạn thảo

14


QUY HOẠCH TUYẾN TÍNH

CHƯƠNG 3. BÀI TỐN VẬN TẢI

4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT
Ví dụ 4.4. Giải bài tốn vận tải lợi nhuận lớn nhất sau:
j

70

i

55

85

60


6

5

11

10

10

6

5

7

9

8

7

4

90
80
100

Nguyễn Hoàng Tuấn soạn thảo


15



Video liên quan

Chủ Đề