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

LÝ THUYẾT VỀ BÀI TÓAN VẬN TẢI
Nguyễn Minh Đức

Bài tóan vận tải luôn có phương án tối ưu:



Trong đó:

,



,



Chứng minh: bằng cách đặt


với

Dễ thấy
hay Z bị chặn dưới

Định lý: nếu lầ lượt cộng vào chi phí ở hàng 1,2…m một lượng -
,-
,…,-
và vào cột 1,2…n một lượng -
,-
,…,-
, tức là thay thế
bởi


Chứng minh: Ta có


Đặt



Vậy để tìm min f(x) tức có nghĩa là tìm min của F(x)

Nhận xét1: nhờ định lý trên ta có thể cho
với mọi ô chọn
để F(x)=0, khi đó.

( biểu thức đối ngẫu của bài tóan đối ngẫu của
)
Suy ra
chính là giá trị tối ưu của bài tóan vì
với
,

Nhận xét 2: có m+n-1 ô chọn, nên có m+n-1 phương trình, với m ẩn
và n ẩn
(m+n ẩn). Do đó hệ sẽ có vô số nghiệm, chỉ cần cho một ẩn nào đó một giá trị tùy ý thì sẽ tính được các ẩn còn lại. Vì vậy đây là tiền đề cho phương pháp thế vị sau này.

Phương pháp thế vị
Từ nhận xét trên ta tìm các
,
thỏa
với mọi ô chọn (i,j) được gọi là các thế vị.
Đối với các ô lọai, lượng
được gọi là lượng kiểm tra
Nhận xét: sở dĩ đổi
là vì khi giải để dễnhớ rằng bài tóa vận tải
,
với các ô lọai
đó là phương án tối ưu, còn bài tóan vận tải
,
với các ô lọai
đó là phương án tối ưu, còn bài tóan vận tải

Định lý 3: BTVT ( min
+ Nếu

ô lọai thì PACB đang xét là PATƯ
+ Nếu
, thì có thể tìm được một PACB khác tốt hơn PACB hiện có và

(trong đó d là lượng chúng ta lọai)
Đây là một kiến thức quan trọng của phương pháp thế vị, nó giải thích tại sao chúng ta lại lọai phương án đó, vì phương án tiếp theo sẽ nhỏ hơn phương án cũ.

Chứng minh:
Nếu
,
ô lọai (i,j) thì PA là PATƯ.
Ta lập hai bài tóan tương đồng nhau (I) và (II)





Gọi phương án cơ bản hiện tại là X0 , và X là một phương án bất kỳ




(i,j) là ô chọn

(I,j) là ô lọai


Với X là phương án
,
(i.j)




Vậy X0 là phương án tối ưu của bài tóan (II) nên cũng là PATƯ của bài tóan (I)

Nhận xét: Ở đây nhờ định lý 2 bài tóan tương đồng đã sừ dụng được kỹ thuật rất hay là kỹ thuật quy không để tìm lời giải của bài tóan (II)

Nếu có một lượng kiểm tra
, thì có thể tìm được một PACB khác tốt hơn PACB hiện có và
.

Chứng minh: Gọi (r,s) là ô lượng kiểm tra





Gọi G là tập hợp các ô chọn của X0 ( G có m+n-1) ô
Khi đó sẽ tồn tại một vòng đi qua ô (r,s) (có thể chứng minh dc điều này) thì đánh dấu + vào ô (r,s), đánh dấu – vào ô kế tiếp… cho tới hết vòng V
Giả sử vòng V gồm các ô

Vì
,
,
là ô chọn nên



(1)
(r,s) là ô lọai nên



(2)
Từ (1),(2)

Suy ra chi phí
lớn hơn
một lượng là

Tổng quát ta có



Nhận xét: Vậy, cjở một đơn vị hàng bên
thì chi phí lớn hơn
một lượng là
dương. Do đó nếu chuyển bớt d đơn vị hàng bên
sang
thì chi phí sẽ giảm là
. Vậy ta có tổng quát


Từ đây, ta suy ra với một số hữu hạn bước như trên ta sẽ tìm được một PA x*
Là nhỏ nhất.