Lý thuyết về bài tóan vận tải

Tài liệu tham khảo Lý thuyết về bài tóan vận tải, môn học tối ưu hóa. Biên soạn: Nguyễn Minh Đức. | LÝ THUYẾT VỀ BÀI TÓAN VẬN TẢI Nguyễn Minh Đức 1) 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 2) Đị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. 3) 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 4) Đị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: a) 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 , () 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) b) 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.

Bấm vào đây để xem trước nội dung
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.