Bài toán vận tải

     
Mở đầu

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

Bạn đang xem: Bài toán vận tải


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

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

*

Đối với bài toán vận tải người ta thường ký 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)

vào trường hợp các nguồn phát ko chuyển hết sang các nút cầu do đã đủ nhu cầu thì câu hỏi vận tải được gọi là câu hỏi vận tải mở. Có thể đưa một việc vận tải mở về một việc 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 bằng thu phạt

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 mặt hàng với khối lượng tương ứng là a1, a2,....,am. Mặt hàng được cung cấp đế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í chăm 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 để :

- những điểm phân phát đều phát hết hàng

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

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

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

vì tổng lượng mặt hàng phát đi từ mỗi điểm phạt Ai đến mọi điểm thu Bj bằng lượng mặt hàng phát từ Ai đề nghị :

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 kích cỡ 8 ital "in" =a rSub kích thước 8i " " ( i="1,2," "." "." "." ",m" )

bởi tổng lượng sản phẩm thu được tại mỗi điểm thu Bj từ mọi điểm phạt Ai bằng lượng mặt hàng cần thu tại Bj đề xuất :


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

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

*

Với những phân tích bên trên ta có quy mô của việc như sau :

*

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

Một ma trận X=m.n thỏa (2) với (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 câu hỏi vận tải

bao gồm thể giải câu hỏi vận tải theo phong cách của quy hoạch tuyến tính. Tuy nhiên do tính chất đặc biệt của vấn đề vận tải cần 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 bày bài toán vận tải dưới dạng bảng như sau :

*

trong bảng mỗi sản phẩm mô tả một điểm phát, mỗi cột mô tả một điểm thu, mỗi ô mô 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 cơ mà hai ô liên tiếp nằm trong cùng một sản phẩm hoặc một cột, ba ô liên tiếp không cùng nằm bên trên 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 trong một dây chuyền 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 việc 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 chu trình được gọi là phương án cơ bản.

Một phương án bao gồm đủ m+n-1 ô chọn được gọi là ko suy biến, bao gồm ít hơn m+n-1 ô chọn được gọi là suy biến. Vào 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 tất cả lượng hàng bằng 0 để phương án cơ bản trở thành không suy biến


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

Xét bài toán vận tải bao 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 ô gồm cước giá tiền nhỏ nhất (r,s) ( gọi là ô chọn). Lúc đó : nếu điểm phạt r đã phát hết hàng thì xóa sản phẩm 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 đủ sản phẩm thì xóa cột s của bảng cùng số lượng phân phát còn lại tại điểm phân phát r là ar-bs

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

những ô chọn trong quy trình phân phối, sẽ không 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 việc đang xét :

1- Phân vào ô (1,3) 50 . Sản phẩm (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) đôi mươi . Cột (2) bị xóa . Hàng (2) cò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 . Mặt hàng (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 . Hàng (3) còn vạc 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

Đã 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 sản phẩm i với cột j của ma trận cước phí C= một số tùy ý ri và sj thì việc vận tải mới với ma trận cước chi phí mới C"= thì phương án tối ưu của bài toán này cũng là phương án tối ưu của việc kia cùng ngược lại.

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


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

sau khoản thời gian xác định được phương án cơ bản gồm m+n-1 ô chọn, người ta cộng vào mỗi hàng i cùng mỗi cột j của ma trận cước mức giá C= một số ri cùng sj sao cho ma trận cước giá tiền 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

các 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 { { { { kích cỡ 12alignl stack left lbrace 1+r rSub size 81 +s rSub form size 83 =0 # right none left lbrace 3+r rSub form size 82 +s rSub form size 81 =0 # right none left lbrace 2+r rSub size 82 +s rSub size 82 =0 # right none left lbrace 7+r rSub kích cỡ 83 +s rSub kích 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ả trên

Ma trận cước giá thành 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 khoản thời gian quy 0 cước phí những ô chọn nếu : những ô loại đều 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 sang trọng 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- kiếm tìm ô đưa vào.

Ô đưa vào là ô loại (i*,j*) có cước phí tổn nhỏ nhất với trở thành ô chọn

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

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

Xem thêm: Top 12 Mẫu Phân Tích Bài Chiều Tối Của Hồ Chí Minh Hay Nhất, Phân Tích Bài Thơ Chiều Tối Của Hồ Chí Minh

Chu trình điều chỉnh được tì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 quy 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 quy trình điều chỉnh V bắt đầu từ ô (i*,j*). Lúc đó chu trình điều chỉnh V được chia thành hai lớp :

VC : những ô có số thứ tự chẵn.

VL : các ô bao gồm số thứ tự lẻ.

4- search ô đưa ra và lượng điều chỉnh.

vào số các ô 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 mặt hàng xrs ở ô đưa ra gọi là lượng điều chỉnh.

vào 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 bí quyết thêm hoặc bớt lượng điều chỉnh trên chu trình điều chỉnh như sau :

Ô tất cả thứ tự chẵn bị bớt đi lượng điều chỉnh.

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

Ô ngoài chu trình điều chỉnh không cầm đổi

vào ví dụ này ta thấy những ô trong chu trình điều chỉnh gồm sự nắm đổ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 buộc phải 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

cù về giai đoạn 1.


Giai đoạn 1 : Quy 0 cước giá tiền ô 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 phí 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 phí tổn là :

1.50+3.10+2.20+6.10+7.70=670

lúc 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 mức giá là :

1.50+3.20+2.20+7.60+11.10=680


Các bài toán được đưa về vấn đề vận tải

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

a- bài toán bổ nhiệm

Giả sử tập hợp S gồm m người cùng tập hợp D gồm n công việc (chức vụ). Cước giá tiền 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). Bài toán đặt ra là tìm giải pháp chia mỗi người đúng một việc làm sao cho cước phí bổ nhiệm là nhỏ nhất.

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

*

thì việc trở thành :

*

do mỗi người nhận đúng 1 việc nên :

*

bởi mỗi việc chỉ giao đến một người nên :

*

Đây là bài toán vận tải nhưng bao gồm thêm yêu cầu là những biến xij chỉ lấy giá bán trị 0 hoặc 1.

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

b- câu hỏi vận tải với cung ít hơn cầu

Xét một vấn đề một vấn đề 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 nhưng 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 ko thể đáp ứng đủ nhu cầu dj mang lại mỗi nút j=1→n vì vậy ràng buộc tất cả dạng bất đẳng thức thay bởi là đẳng thức. Vậy :

*

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

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

lúc này người ta đưa cấp dưỡng một nút cung giả (m+1) với nguồn cung là

*

và cước phí tương ứng là

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

Khi đó ta nhận được một câu hỏi vận tải (đóng)

*

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

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

*

Ghi chú :

Với bài toán vận tải mở, nguồn chuyển không hết sang các nhu cầu, người ta tất cả thể tính thêm cước phí tổn lưu kho ở mỗi nguồn mang đến mỗi đơn vị sản phẩm là ci (n+1) (i=1→m) . Hoàn toàn tương tự như trên, khi đưa câu hỏi này về việc vận tải (đóng) bằng phương pháp 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 tất cả đường cấm

Đây là vấn đề vận tải nhưng không phải mỗi nguồn đều tất cả cung nối với mọi đích. Nghĩa là có đường cấm. Cách đưa về việc vận tải là sử 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 các cung không cấm, tức là những cung (i,j), i∈S, j∈D và câu hỏi có thêm điều kiện

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

ta đưa việc có các yêu cầu

*
(*)

về việc vận tải bằng bí quyết đặ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 = { form size 12 overline c rSub size 8 ital "ij" =alignl stack left lbrace c rSub form size 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 xem là số lớn hơn mọi số gặp phải khi tính toán.

Xét câu hỏi với cước phí mới như trên như sau :

*
(**)

thì ta có :

Định lý :

Giả sử x=m.n kích thước 12x rSup size 8* = < x rSub kích cỡ 8 ital "ij" rSup size 8* > rSub kích cỡ 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 thước 12x rSub form size 8 ital "ij" rSup kích cỡ 8* =0" " forall ( "i,j" ) notin E thì x kích cỡ 12x rSup form size 8* là phương án vận chuyển tối ưu của câu hỏi vận tải gồm đường cấm (*)

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

Xem thêm: Giải Bài Tập Trang 84, 85 Sgk Toán 8 Tập 2 Hay Nhất, Giải Bài Tập Trang 84, 85 Sgk Toán 8 Tập 2

d- câu hỏi vận tải kèm chế biến trung gian

Giả sử rằng trong quy mô vận tải bao gồm 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 lúc đến điểm cầu. Giả sử 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 chi phí vận chuyển một đơn vị phân phối sản phẩm từ i đến λ là ciλ" form size 12 c sup " rSub kích cỡ 8iλ và chuyển một đơn vị sản phẩm từ λ đến j là ciλ"" kích cỡ 12 c sup "" rSub size 8iλ . Bài toá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 sao cho cước phí nhỏ nhất.

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