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

Đây là giáo trình về Qui hoạch tuyến tinh mà tác giả Lê Văn Phi đã soạn và giảng cho sinh viên Toán Kinh tế Đại học Kinh tế Tp. HCM từ năm 1981 đến 2002. Giáo trình được tu chỉnh và xuất bản trong cuốn "Qui hoạch tuyến tinh và ứng dụng trong kinh tế" được Nhà Xuất bản Giáo dục ấn hành năm 2004.
Nội dung trích xuất từ tài liệu:
Bài 5: Bài toán vận tảiLý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ CHƯƠNG 5 : BÀI TOÁN VẬN TẢI§1 Mô hình bài toán vận tải cổ điển1.1 Đặt bài toán Bài toán : Một xí nghiệp vận tải nhận hợp đồng vận tải một loạihàng (ví dụ : Xi măng) từ m trạm phát hàng, ký hiệu là Gi, i = 1, 2, …, m,đến n trạm nhận hàng, ký hiệu Nj, j = 1, 2, …, n. Biết rằng ở trạm giaoGi có ai đơn vị hàng (tấn, tạ, m3 v.v…) cần phải được chuyển đi và trạmnhận Nj cần phải nhận được đủ bj đơn vị hàng, (để đơn giản cách trìnhbày, ta giả thiết 1 đơn vị = 1 tấn) ; chi phí vận tải trọn gói tính cho mộttấn hàng từ trạm Gi đến trạm Nj là cij, i = 1, 2, …, m ; j = 1, 2, …, n. Xinghiệp cần tìm phương án vận tải, tức là phải xác định sẽ vận chuyển từGi đến Nj bao nhiêu tấn hàng, sao cho :1) Hàng cần chuyển đi ở mỗi trạm phát Gi sẽ dược chuyển đi hết, i = 1, 2, …, m ;2) Khối lượng hàng được yêu cầu ở trạm nhận N j sẽ được chuyển đến đủ, j = 1, 2, …, n;3) Tổng chi phí vận tải là ít nhất.1.2 Các giả thiết Để cho bài toán vận tải có thể giải được bằng các phương pháp củaLý thuyết qui hoạch tuyến tính cần có các giả thiết sau đây23 :GT1 : Tổng khối lượng hàng phải chuyển đi ở các trạm phát hàng phảibằng với tổng khối lượng hàng chuyển đến các trạm nhận hàng ; tức là m n ∑ a i = ∑ b j 24 (1.1) i =1 j=1GT2 : Hàng được nêu ở đây phải là đồng nhất, tức là cùng loại và chấtlượng như nhau.25GT3 : Có thể vận tải hàng từ bất kỳ một trạm phát G i đến bất kỳ một trạm nhận Nj.23 Bài toán vận tải với các giả thiết này được gọi là bài toán vận tải cổ điển.24 Điều kiện (1.1) được gọi là điều kiện cân bằng và do vậy mô hình bài toán vận tải sau đây gọi là bài toán vận tải đóng.25 Điều kiện này ngăn ngừa các nhu cần vận tải đặc biệt Lê Văn Phi, Khoa Toan – Thông kê, Trường Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 128Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́GT4 : Khối lượng hàng vận tải từ một trạm phát Gi đến một trạm nhận Nj là không hạn chế.GT5 : Tổng chi phí vận tải tỉ lệ (phụ thuộc tuyến tính) với khối lượng vận tải. Trên thực tế người ta có nhiều cách khắc phục khi các giả thiết từ 1đến 4 không thỏa mãn. Tuy nhiên, nếu giả thiết GT5 không thỏa mãn thìkhông thể ứng dụng các phương pháp sẽ trình bày trong chương này đểgiải bài toán vận tải.1.3 Mô hình toán học của bài toán vận tải cổ điển Với các giả thiết trên đây, mô hình toán học của bài toán vận tải cổđiển có thể được trình bày như sau : Gọi xij là số tấn hàng mà xí nghiệp sẽchuyển từ trạm phát Gi đến trạm nhận Nj, i = 1, 2, …, m ; j = 1, 2, …, n ; Zlà tổng chi phí vận tải. xij i jTa có mô hình toán học như sau :Tìm m× n số thực xij , i = 1, 2, …, m ; j = 1, 2, …, n thỏa mãn các điềukiện : n ____  ∑ x ij = a i ,i = 1, m  j=1 m ____  ∑ x = b , j = 1, n  i =1 ij  j (1.2) ____ ____ x ij ≥ 0,i = 1, m;1, n m n Z = ∑ ∑ cij x ij → min i =1 j=1Dễ thấy rằng khi ai, bj, cij, i = 1, 2, …, m ; j = 1, 2, …, n, cho trước thì bàitoán (1.2) là bài toán QHTT cho ở dạng chuẩn gồm m+n ràng buộc vàm× n biến số. Một ma trận X gồm các số thực xij không âm thỏa mãn m+nràng buộc được gọi là phương án vận tải. Một phương án vận tải chotổng chi phí vận tải thấp nhất được gọi là phương án vận tải tối ưu (haynói gọn là phương án tối ưu). Ký hiệu Lê Văn Phi, Khoa Toan – Thông kê, Trường Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 129Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ 0    ...  0  a1      1 ← i  ...  0  am    ____ ___ P =   ; Pij =  ...  ;i = 1, m, j = 1, n (1.3)  b1  0  ...      b  1 ← m+ j  n   0  ...    0Khi đó bài toán vận tải (5.2) có thể viết dưới dạng :  ∑∑P x m n = P  i =1 j=1 ij ij  ____ ___  x ≥ 0,i = 1, m, j = 1, n (1.4)  ij m n Z = ∑ ∑ cij x ij → min i =1 j=1Dễ thấy rằng ma trận hệ số của bài toán (5.4) có dạng : A = [P11, P12, …, P1n, P21, P22, …, P2n, …, Pm1, Pm2, …, Pmn] = 1 1 1 ... 1 0 0 ... 0 ... 0 0 ... 0   2 0 0 ... 0 1 1 ... 1 ... 0 0 ... 0 ...  ... ... ... ... ... ... ... ... ... ... ... ... ...    m 0 0 ... 0 0 0 ... 0 ... 1 1 ... 1 = (1.5) m +1 1 0 ...