zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: AN TON | Ngày: | Loại File: DOC | Số trang:4

Báo xấu

875
lượt xem 233
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết về bài tóan vận tải

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: m n Z = ∑∑ cij xij → min(max) i =1 j =1 m Trong đó: ∑x i =1 ij = b j , j = 1, n ∆ rs d n ∑x j =1 ij = ai , i = 1, m xij ≥ 0, ∀i, j Chứng minh: bằng cách đặt ai b j với d = ∑ ai = ∑ b j xij = d Dễ thấy Z ≥ 0 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 - u1 ,- u2 ,…,- um và vào cột 1,2…n một lượng - v1 ,- v1 ,…,- vn , tức là thay thế cij bởi c 'ij = cij − ui − v j Chứng minh: Ta có m n f ( x) = ∑∑ cij xij i =1 j =1 m n Đặt F ( x) = ∑∑ (cij − ui − v j )xij i =1 j =1 m n F ( x) = ∑∑ (cij − ui − v j )xij i =1 j =1 m n m n n m = ∑∑ cij xij − ∑∑ ui xij − ∑∑ v j xij i =1 j =1 i =1 j =1 j =1 i =1 m n = f ( x) − ∑ ui ai − ∑ v j bi i =1 j =1 = f ( x) + A 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 c 'ij = 0 ⇔ cij − ui − v j = 0 với mọi ô chọn xij ≠ 0 để F(x)=0, khi đó. m n f ( xij ) = ∑ ui ai + ∑ v j b j ( biểu thức đối ngẫu của bài tóan đối ngẫu của i =1 j =1 f ( xij ) )
Suy ra (( xij )) chính là giá trị tối ưu của bài tóan vì f (( xij )) = f D (ui , v j ) với i = 1, m , j = 1, n • 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 ui và n ẩn v j (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 ui , v j thỏa ui + v j = cij 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 ∆ ij = ui + v j − cij = −(cij − ui − v j ) được gọi là lượng kiểm tra • Nhận xét: sở dĩ đổi ∆ ij = ui + v j − cij là vì khi giải để dễnhớ rằng bài tóa vận tải → min , ∆ ij ≤ 0 với các ô lọai → đó là phương án tối ưu, còn bài tóan vận tải → max , ∆ ij ≥ 0 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 ∆ ij ≤ 0 ∀ ô lọai thì PACB đang xét là PATƯ + Nếu ∆ ij ≥ 0 , thì có thể tìm được một PACB khác tốt hơn PACB hiện có và f ( x) = f ( x 0 ) − ∆ ij d (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 ∆ ij ≤ 0 , ∀ ô lọai (i,j) thì PA là PATƯ. Ta lập hai bài tóan tương đồng nhau (I) và (II)  f ( x ) = ∑∑ cij xij  ( I )  AX = B X ≥ 0   F ( x ) = ∑∑ ∆′ xij = ∑∑ (cij − ui − v j ) xij ij  ( II )  AX = B X ≥ 0  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ỳ F ( X 0 ) = ∑∑ ∆′ xij = ∑∑ ∆′ xij + ∑∑ ∆′ xij ij 0 ij 0 ij 0 ( i , j ) ochon ( i , j ) o _ loai (i,j) là ô chọn ⇒ ∆′ = 0 F(X)=0 ij (I,j) là ô lọai ⇒ x ij = 0 0
Với X là phương án ⇒ x ij ≥ 0 , ∀ (i.j) 0 ∆′ ≥ 0( ∆ij ≤ 0), ∀i, j ij ⇒ F ( X ) = ∑∑ xij ∆′ ≥ 0 ij ⇒ F(X ) ≥ F(X 0) 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 ∆ ij > 0 , thì có thể tìm được một PACB khác tốt hơn PACB hiện có và f ( x) = f ( x ) − ∆ ij d . 0 Chứng minh: Gọi (r,s) là ô lượng kiểm tra ∆′ > 0 rs ⇔ crs − ur − vs > 0 ⇔ −crs + ur + vs < 0 ⇔ ∆ rs < 0 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 ô ( r,s ) , ( r, k ) , (l , k ), (l , s) + − + − Vì ( r, k ) , (l , k ) , (l , s ) là ô chọn nên crk = ur + vk clk = ul + vk cls = ul + vs ⇒ crk + cls = ur + vk + ul + vs (1) (r,s) là ô lọai nên ∆ rs = ur + vs − crs ⇒ crs = ur + vs − ∆ rs ⇒ crs + cls = ul + vs + ur + vs − ∆ rs (2) Từ (1),(2) ⇒ (crk + cls )− (crs + cls ) = ∆ rs > 0 − + V V Suy ra chi phí V lớn hơn V một lượng là ∆ rs − + Tổng quát ta có ∑ cij − ∑ cij = ∆ rs > 0 ( i , j )∈V − ( i , j )∈V + • Nhận xét: Vậy, cjở một đơn vị hàng bên V − thì chi phí lớn hơn V + một lượng là ∆ rs dương. Do đó nếu chuyển bớt d đơn vị hàng bên V − sang V + thì chi phí sẽ giảm là ∆ rs d . Vậy ta có tổng quát f ( x) = f ( x 0 ) − ∆ ij d 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.

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.