CÁCH GIẢI BÀI TOÁN VẬN TẢI

     
Mở đầu

việc vận tải là việc quan trọng nhất trong số bài toán quy hoạch tuyến tính. Người ta tổng kết rằng 85% những bài toán quy hoạch tuyến tính gặp vào ứng dụng là việc vận tải hoặc mở rộng của nó. Thuật ngữ vấn đề vận tải thường được hiểu là việc vận chuyển làm thế nào để cho cước mức giá nhỏ nhất.

Bạn đang xem: Cách giải bài toán vận tải


Các khái niệm cơ bản

việc vận tải được tế bào tả như là một vấn đề về loại dữ liệu gồm tập hợp những nút N được tạo thành hai phần rời nhau : những nút nguồn S và những nút đích D, tức là :

*

Đối với việc vận tải người ta thường ký kết hiệu

ham ∈ S là nguồn phân phát ở nút i(i=1→m)

dj ∈ D là nhu cầu thu của nút j (j=1→n)

trong trường hợp những nguồn phát ko chuyển hết sang những nút cầu vì đã đủ nhu cầu thì việc vận tải được gọi là bài toán vận tải mở. Tất cả thể đưa một việc vận tải mở về một câu hỏi vận tải (đóng) bằng biện pháp thêm vào một nút cầu giả thứ (n+1) với nhu cầu được xác định như sau : 

*


Bài toán vận tải cân nặng bằng thu vạc

Thiết lập bài xích toán

gồm m nơi A1, A2,....,Am cung cấp một loại sản phẩm với khối lượng tương ứng là a1, a2,....,am. Sản phẩm được cung cấp mang đến n nơi B1, B2,...., Bn với khối lượng tiêu thụ tương ứng là b1, b2,....,bn.

Cước phí chuyên chở một đơn vị mặt hàng từ điểm phân phát Ai đến điểm thu Bj là cij .

Hãy lập kế hoạch vận chuyển từ mỗi điểm vạc đến mỗi điểm thu từng nào hàng để :

- các điểm phạt đều phát hết hàng

- các điểm thu đều nhận đủ hàng

- Tổng cước chi phí phải trả là ít nhất

Gọi xij là lượng sản phẩm chuyển từ điểm phát Ai đến điểm thu Bj , xij ≥ 0 .

vì chưng tổng lượng sản phẩm phát đi từ mỗi điểm vạc Ai đến mọi điểm thu Bj bằng lượng hàng phát từ Ai bắt buộc :

x i1 + x i2 + . . . . + x in = a i ( i = 1,2, . . . ,m ) kích thước 12x rSub kích thước 8i1 +x rSub size 8i2 + "." "." "." "." +x rSub size 8 ital "in" =a rSub kích thước 8i " " ( i="1,2," "." "." "." ",m" )

do tổng lượng hàng thu được tại mỗi điểm thu Bj từ mọi điểm phân phát Ai bằng lượng sản phẩm cần thu tại Bj nên :


x 1j + x 2j + . . . . + x mj = b ji ( j = 1,2, . . . , n ) kích cỡ 12x rSub kích cỡ 81j +x rSub size 82j + "." "." "." "." +x rSub kích thước 8 ital "mj" =b rSub form size 8 ital "ji" " " ( j="1,2," "." "." "." ", n" )

Để tổng cước giá thành là không nhiều nhất cần phải có :

*

Với những phân tích bên trên ta có mô hình của vấn đề như sau :

*

Phương án - Phương án tối ưu

Một ma trận X=m.n thỏa (2) và (3) được gọi là phương án, thỏa thêm (1) được gọi là phương án tối ưu.


Dạng bảng của bài toán vận tải

có thể giải bài toán vận tải theo phong cách của quy hoạch tuyến tính. Tuy vậy do tính chất đặc biệt của bài toán vận tải buộc phải người ta nghĩ ra một thuật toán hiệu quả hơn. Trước tiên người ta trình diễn bài toán vận tải dưới dạng bảng như sau :

*

vào bảng mỗi sản phẩm mô tả một điểm phát, mỗi cột tế bào tả một điểm thu, mỗi ô tế bào tả một tuyến đường đi từ một điểm phát tới một điểm thu.

Dây chuyền - Chu trình

Một dãy các ô của bảng mà hai ô liên tiếp nằm trong cùng một sản phẩm hoặc một cột, tía ô liên tiếp không cùng nằm trên một mặt hàng hoặc một cột được gọi là một dây chuyền. Ta thấy rằng hai ô liền nhau vào một dây chuyền tất cả chỉ số sản phẩm hoặc chỉ số cột bằng nhau

*

Ô chọn - Ô loại

Giả sử ma trận X=m.n (i=1,2,...,m) (j=1,2,...,n) là một phương án của câu hỏi vận tải.

Những ô trong bảng tương ứng với xij >0 được gọi là ô chọn, những ô còn lại được gọi là ô loại.

Phương án cơ bản

Một phương án mà những ô chọn ko tạo thành một quy trình được gọi là phương án cơ bản.

Một phương án tất cả đủ m+n-1 ô chọn được gọi là ko suy biến, tất cả ít hơn m+n-1 ô chọn được gọi là suy biến. Trong trường hợp suy biến người ta chọn bổ sung vào phương án cơ bản một số ô loại gồm lượng hàng bằng 0 để phương án cơ bản trở thành ko suy biến


Giải việc vận tải

Xét việc vận tải gồm số lượng phát, số lượng thu với ma trân cước giá thành ở dạng bảng như sau :

80 20 60
50 5 4 1
40 3 2 6
70 7 9 11

LẬP PHƯƠNG ÁN CƠ BẢN BAN ĐẦU

Phương án cơ bản ban đầu được xác định bằng biện pháp ưu tiên phân phối nhiều nhất vào ô có cước tổn phí nhỏ nhất (r,s) ( gọi là ô chọn). Khi đó : nếu điểm phân phát r đã vạc hết sản phẩm thì xóa hàng r của bảng cùng số lượng cần thu tại điểm s chỉ còn là một bs-ar ; nếu điểm thu s đã nhận đủ hàng thì xóa cột s của bảng và số lượng phạt còn lại tại điểm phân phát r là ar-bs

Bảng mới thu được tất cả kích thước giảm đi. Tiếp tục phân phối như trên cho đến lúc hết hàng.

các ô chọn trong quá trình phân phối, sẽ ko chứa chu trình, là một phương án cơ bản. Nếu phương án cơ bản suy biến, chưa đủ m+n-1 ô, thì bổ sung thêm một số " ô chọn 0 "

Áp dụng vào vấn đề đang xét :

1- Phân vào ô (1,3) 50 . Hàng (1) bị xóa . Cột (3) còn thu 60-50=10

80 20 10
0 5 4 1 50
40 3 2 6
70 7 9 11

2- Phân vào ô (2,2) 20 . Cột (2) bị xóa . Mặt hàng (2) còn phân phát 40-20=20

80 0 10
0 5 4 1 50
20 3 2 20 6
70 7 9 11

3- Phân vào ô (2,1) trăng tròn . Sản phẩm (2) bị xóa . Cột (1) còn thu 80-20=60

60 0 10
0 5 4 1 50
0 3 20 2 20 6
70 7 9 11

4- Phân vào ô (3,1) 60 . Cột (1) bị xóa . Sản phẩm (3) còn phân phát 70-60=10

0 0 10
0 5 4 1 50
0 3 20 2 20 6
10 7 60 9 11

5- Phân vào ô (3,3) 10. Hết hàng.

0 0 0
0 5 4 1 50
0 3 20 2 20 6
0 7 60 9 11 10

Đã bao gồm 5 ô được chọn, chúng tạo thành một phương án cơ bản ko suy biến do số ô bằng với m+n-1=3+3-1.


THUẬT TOÁN "QUY 0 CƯỚC PHÍ CÁC Ô CHỌN"

Định lý

Nếu cộng vào mặt hàng i và cột j của ma trận cước phí C= một số tùy ý ri và sj thì bài toán vận tải mới với ma trận cước phí mới C"= thì phương án tối ưu của vấn đề này cũng là phương án tối ưu của vấn đề kia với ngược lại.

Thuật toán "Quy 0 cước phí những ô chọn" gồm bố giai đoạn.


Giai đoạn 1 : Quy 0 cước phí các ô chọn

sau khi xác định được phương án cơ bản có m+n-1 ô chọn, người ta cộng vào mỗi hàng i và mỗi cột j của ma trận cước chi phí C= một số ri với sj làm sao để cho ma trận cước chi phí mới C" tại các ô chọn thỏa c"ij=cij+ri+sj=0.

Tiếp tục ví dụ bên trên ta thấy :

5 4 1 50 r1=6
3 20 2 20 6 r2=0
7 60 9 11 10 r3=-4
s1=-3 s2=-2 s3=-7

những giá trị cộng vào phải thỏa hệ phương trình :


1 + r 1 + s 3 = 0 3 + r 2 + s 1 = 0 2 + r 2 + s 2 = 0 7 + r 3 + s 1 = 0 11 + r 3 + s 3 = 0 { { { { size 12alignl stack left lbrace 1+r rSub kích thước 81 +s rSub size 83 =0 # right none left lbrace 3+r rSub size 82 +s rSub form size 81 =0 # right none left lbrace 2+r rSub form size 82 +s rSub size 82 =0 # right none left lbrace 7+r rSub kích thước 83 +s rSub kích thước 81 =0 # right none left lbrace "11"+r rSub kích thước 83 +s rSub kích thước 83 =0 # right no lbrace

Chọn r2=0 , giải hệ ta được kết quả bên trên

Ma trận cước tổn phí mới thu được là :

8
8 0 50
0 20 0 20 -1
0 60 3 0 10


Giai đoạn 2 : Kiểm tra tính tối ưu sau khi quy 0 cước phí các ô chọn nếu : các ô loại đều bao gồm cước tầm giá ≥ 0 thì phương án đang xét là tối ưu, ngược lại thì chuyển quý phái giai đoạn 3

vào ví dụ này ta chuyển thanh lịch giai đoạn 3.


Giai đoạn 3 : Xây dựng phương án mới tốt hơn

1- tìm ô đưa vào.

Ô đưa vào là ô loại (i*,j*) gồm cước giá thành nhỏ nhất và trở thành ô chọn

trong ví dụ này là ô (2,3).

2- Tìm quy trình điều chỉnh.

Xem thêm: Đồng Hồ Guou Của Nước Nào ? Giá Bao Nhiêu ? Chất Lượng Thế Nào ?

Chu trình điều chỉnh được tìm kiếm bằng bí quyết bổ sung ô (i*,j*) vào m+n-1 ô chọn ban đầu, khi đó sẽ xuất hiện một quy trình duy nhất, gọi là chu trình điều chỉnh V .

vào ví dụ này chu trình điều chỉnh là :

V : (2,3) (3,3) (3,1) (2,1) (2,3)

3- Phân ô chẵn lẻ cho chu trình điều chỉnh.

Đánh số thứ tự các ô trong chu trình điều chỉnh V bắt đầu từ ô (i*,j*). Lúc đó quy trình điều chỉnh V được tạo thành hai lớp :

VC : các ô có số thứ tự chẵn.

VL : các ô tất cả số thứ tự lẻ.

4- tìm kiếm ô đưa ra cùng lượng điều chỉnh.

trong số các ô tất cả thứ tự chẵn chọn ô (r,s) được phân phối ít sản phẩm nhất làm cho ô đưa ra, trở thành ô loại. Lượng hàng xrs ở ô đưa ra gọi là lượng điều chỉnh.

trong ví dụ này ô đưa ra là ô (3,3), lượng điều chỉnh là 10.

5- Lập phương án mới.

Phương án mới có được bằng giải pháp thêm hoặc bớt lượng điều chỉnh trên quy trình điều chỉnh như sau :

Ô gồm thứ tự chẵn bị bớt đi lượng điều chỉnh.

Ô bao gồm thứ tự lẻ được cộng thêm lượng điều chỉnh.

Ô ngoài quy trình điều chỉnh không nỗ lực đổi

trong ví dụ này ta thấy những ô trong chu trình điều chỉnh bao gồm sự cố kỉnh đổi như sau :

Ô (2,3) được thêm 10 trở thành 10

Ô (3,3) bị bớt 10 trở thành 0

Ô (3,1) được thêm 10 trở thành 70

Ô (2,1) bị bớt 10 yêu cầu trở thành 10

khi đó phương án mới là :

8 8 0 50
0 10 0 20 -1 10
0 70 3 0

con quay về giai đoạn 1.


Giai đoạn 1 : Quy 0 cước tầm giá ô chọn
8 8 0 50 r1=-1
0 10 0 20 -1 10 r2=0
0 70 3 0 r3=0
s1=0 s2=0 s3=1

Ma trận cước mức giá mới là :

7
7 0 50
0 10 0 20 0 10
0 70 3 1

Giai đoạn 2 : Kiểm tra tính tối ưu

Đây là phương án tối ưu

80 20 60
50 5 4 1 50
40 3 10 2 20 6 10
70 7 70 9 11

Với cước tầm giá là :

1.50+3.10+2.20+6.10+7.70=670

khi sử dụng phương án ban đầu

80 20 60
50 5 4 1 50
40 3 20 2 20 6
70 7 60 9 11 10

thì cước giá tiền là :

1.50+3.20+2.20+7.60+11.10=680


Các việc được đưa về câu hỏi vận tải

có nhiều câu hỏi thực tế tất cả tính chất không phải là ’’vận tải ’’ nhưng có mô hình toán học là việc vận tải. Một số vấn đề như vậy là :

a- câu hỏi bổ nhiệm

Giả sử tập hợp S gồm m người với tập hợp D gồm n công việc (chức vụ). Cước mức giá của việc bổ nhiệm người i∈S vào việc j∈D là cij (i=1→m , j=1→n). Việc đặt ra là tìm biện pháp chia mỗi người đúng một việc làm sao cho cước giá thành bổ nhiệm là nhỏ nhất.

Người ta đặt biến (biến trên dòng) như sau :

*

thì câu hỏi trở thành :

*

bởi vì mỗi người nhận đúng 1 việc nên :

*

vì chưng mỗi việc chỉ giao mang đến một người nên :

*

Đây là việc vận tải nhưng tất cả thêm yêu thương cầu là các biến xij chỉ lấy giá chỉ trị 0 hoặc 1.

vấn đề bổ nhiệm cũng có khi được gọi là vấn đề chọn (Choice Problem). Nhiều câu hỏi thực tế đa dạng có mô hình toán học là việc bổ nhiệm, chẳng hạn như vấn đề phân bố hoả lực vào mục tiêu cần tiêu diệt.

b- vấn đề vận tải với cung ít hơn cầu

Xét một việc một việc vận tải với S là tập hợp m nút cung với D là tập hợp n nút cầu mà tổng nguồn cung nhỏ hơn tổng nhu cầu, tức là

*

Trong trường hợp này tất nhiên không thể đáp ứng đủ nhu cầu dj cho mỗi nút j=1→n cho nên ràng buộc tất cả dạng bất đẳng thức thay vì chưng là đẳng thức. Vậy :

*

Người ta thường đưa vấn đề này về vấn đề vận tải (đóng) theo một trong nhị trường hợp sau đây :

1.Trường hợp thứ nhất là có tính đến sự thiệt hại bằng tiền lúc thiếu một đơn vị mặt hàng hoá ở nút cầu j là rj (j=1→n)

hôm nay người ta đưa cung ứng một nút cung giả (m+1) với nguồn cung là

*

và cước giá thành tương ứng là

c(m+1) j = rj (j=1→n)

Khi đó ta nhận được một vấn đề vận tải (đóng)

*

2.Trường hợp thứ nhì là ko kể đến sự thiệt hại vày thiếu mặt hàng ở nút cầu

Lúc này ta cũng đưa về bài toán vận tải (đóng) như trên, nhưng vì kế bên đến sự thiệt hại buộc phải mục tiêu sẽ là

*

Ghi chú :

Với bài toán vận tải mở, nguồn chuyển ko hết sang những nhu cầu, người ta có thể tính thêm cước tổn phí lưu kho ở mỗi nguồn đến mỗi đơn vị sản phẩm là ci (n+1) (i=1→m) . Trọn vẹn tương tự như trên, lúc đưa vấn đề này về việc vận tải (đóng) bằng bí quyết thêm vào nút cầu giả (n+1) thì hàm mục tiêu trở thành

*

Như vậy ta chỉ cần xét việc vận tải (đóng)

*

c- bài toán vận tải bao gồm đường cấm

Đây là vấn đề vận tải nhưng không phải mỗi nguồn đều bao gồm cung nối với mọi đích. Nghĩa là gồm đường cấm. Biện pháp đưa về vấn đề vận tải là dùng phương pháp M-lớn, tức là phương pháp phạt như sau :

Gọi E là tập những cung không cấm, tức là những cung (i,j), i∈S, j∈D và bài toán có thêm điều kiện

xij=0 với (i,j)∉E

ta đưa câu hỏi có các yêu cầu

*
(*)

về vấn đề vận tải bằng biện pháp đặt cước vận chuyển mới như sau :

c ij nÕu ( i,j ) ∈ E M nÕu ( i,j ) ∉ E c ¯ ij = { size 12 overline c rSub form size 8 ital "ij" =alignl stack left lbrace c rSub kích thước 8 ital "ij" " ""nÕu " ( "i,j" ) in E # right none left lbrace "M nÕu " ( "i,j" ) notin E # right no lbrace

Ở đây M là một số rất lớn, được coi là số lớn hơn mọi số gặp phải lúc tính toán.

Xét việc với cước phí tổn mới như trên như sau :

*
(**)

thì ta có :

Định lý :

Giả sử x=m.n form size 12x rSup kích cỡ 8* = < x rSub form size 8 ital "ij" rSup form size 8* > rSub form size 8m "." n là phương án vận chuyển tối ưu của (**) thì khi đó :

1. Nếu xij=0∀(i,j)∉E kích cỡ 12x rSub size 8 ital "ij" rSup kích thước 8* =0" " forall ( "i,j" ) notin E thì x kích cỡ 12x rSup kích thước 8* là phương án vận chuyển tối ưu của việc vận tải tất cả đường cấm (*)

2. Nếu tồn tại xkl∉E kích thước 12x rSub kích cỡ 8 ital "kl" notin E cơ mà xkl>0 size 12x rSub form size 8 ital "kl" >0 thì việc vận tải tất cả đường cấm (**) không có nhiệm chấp nhận được.

Xem thêm: Hướng Dẫn Vẽ Biểu Đồ Tuần Tự, Với Staruml (Draw Sequence Diagram With Staruml)

d- bài toán vận tải kèm chế biến trung gian

Giả sử rằng trong mô hình vận tải tất cả một số điểm nguồn, tức là điểm sản xuất, cho ra một số sản phẩm cần phải chế biến trước khi đến điểm cầu. Giả sử tất cả λ=1→k điểm chế biến với khả năng chế biến là aλ đơn vị sản phẩm tương ứng. Gọi cước phí vận chuyển một đơn vị bán sản phẩm từ i đến λ là ciλ" kích cỡ 12 c sup " rSub kích thước 8iλ cùng chuyển một đơn vị sản phẩm từ λ đến j là ciλ"" form size 12 c sup "" rSub size 8iλ . Vấn đề đặt ra là lập kế hoạch vận chuyển tất cả các sản phẩm qua chế biến đến tất cả những điểm cầu thế nào cho cước giá thành nhỏ nhất.

Gọi xiλj là lượng sản phẩm từ i qua λ rồi qua j, ta cần search x=< xiλj>mkn sao cho :