LÝ THUYẾT VỀ BÀI TÓAN VẬN TẢINguyễn Minh ĐứcBà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ó...