intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chương 3: Bài toán vận tải - bài 3

Chia sẻ: Lê Văn Nhứt | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
588
lượt xem 206
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'chương 3: bài toán vận tải - bài 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: Bài toán vận tải - bài 3

  1.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 1) Cơ sở toán học Với bài toán vận tải dạng tổng quát (P): n m f ( x)   cij xij  min i 1 j 1 m x j 1 ij  ai n x i 1 ij  bj xij  0, (i  1, n, j  1, m) 1  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 1) Cơ sở toán học Ta có bài toán đối ngẫu (D) tương ứng như sau: n m g (u , v)   ai ui   b j v j  max i 1 j 1 ui  v j  cij i  1, n; j  1, m Và các cặp ràng buộc đối ngẫu của (P) & (D) có dạng: xij  0 và ui  v j  cij i  1, n; j  1, m 2 1
  2.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ   1) Cơ sở toán học Giả sử, (P) có PACB không suy biến: x  x ij 0 0 Khi đó, theo định lý độ lệch bù yếu, để x là PATU của bài 0 toán (P) thì phải tồn tại một phương án u , v  của (D): i j ui  v j  cij x ij  0 0  ui  v j  cij x 0ij  0 i  1, n; j  1, m Đây là tiêu chuẩn tối ưu của PA x0. 3  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ   1) Cơ sở toán học Giả sử, (P) có PACB không suy biến: x  x ij 0 0 Khi đó, theo định lý độ lệch bù yếu, để x là PATU của bài 0 toán (P) thì phải tồn tại một phương án u , v  của (D): i j ui  v j  cij x ij  0 0  ui  v j  cij x 0ij  0 i  1, n; j  1, m Đây là tiêu chuẩn tối ưu của PA x0. ui, vj lần lượt được gọi là thế vị dòng & thế vị cột  ij  ui  v j  cij : hệ số ước lượng. 4 2
  3.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 2) Nội dung thuật toán Với xij0  0 ta có đẳng thức ui  v j  cij  ở các ô chọn, nếu biết ui thì sẽ xác định được vj; và ngược lại, nếu biết vj thì sẽ xác định được ui. Từ hệ u , v  vừa tìm được, nếu tất cả các cặp u , v  i j i j đều thoả mãn hệ ràng buộc (D) thì x0 là PATU của (P); Ngược lại, nếu tồn tại ít nhất 1 HSUL  ij  ui  v j  cij  0 thì x0 chưa là PATU. 5  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 3) Điều chỉnh phương án khi tồn tại HSUL dương Tìm giá trị lớn nhất của  ij để xác định ô được đưa vào hệ thống ô chọn; giả sử là ô (i0,j0).  Từ ô này, ta tìm vòng điều chỉnh.  Trên vòng điều chỉnh, ta đánh vị trí chẵn/ lẻ của các ô chọn, xuất phát từ ô (i0,j0) được đánh vị trí lẻ.  Ô chẵn với lượng hàng q nhỏ nhất là ô được chọn đưa ra khỏi hệ thống ô chọn và q lúc này được gọi là lượng hàng điều chỉnh. 6 3
  4.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 3) Điều chỉnh phương án khi tồn tại HSUL dương PACB mới   x*  xij* của bài toán được xác định theo qui tắc sau: + Nếu ô (i,j) là ô chẵn trên vòng điều chỉnh: xij*  xij0  q + Nếu ô (i,j) là ô lẻ trên vòng điều chỉnh: xij*  xij0  q + Nếu ô (i,j) là ô không nằm trên vòng điều chỉnh: x ij*  x ij0 7  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 4) Các bước giải BTVT bằng thuật toán thế vị 8 4
  5.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ 5.1) Ví dụ 1: Ta xét lại ví dụ trong PP FOGELS và tiến hành đánh giá tính tối ưu của PACB XP như sau: 9  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ Ta nhận thấy rằng tất cả các HSUL của các ô loại đều âm cho nên PACB xuất phát của BT là PATU. Và giá trị tối ưu của hàm mục tiêu đạt được là: f ( x 0 )  5  40  3  25  7  15  5  35   2  35  6  15  2  60  835 10 5
  6.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ 5.2) Ví dụ 2: Giải bài toán vận tải sau: 11  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ Trước hết, ta lập PACBXP của BT bằng PP CP bé nhất và ta được bảng vận tải như sau: 12 6
  7.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ Từ bảng VT này, ta có tổng cộng 8 ô chọn không tạo thành vòng và như vậy, đây là PACB XP không suy biến. 13  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ Ta tiến hành điều chỉnh PA để có PACB mới tốt hơn: 14 7
  8.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5) Một số ví dụ Từ bảng VT mới này, ta tính lại các HSL của các ô loại và nhận thấy rằng tất cả các HSUL đều không dương cho nên PACB mới này là PACB TU của BTVT. Vậy, phương án tối ưu của bài toán là:  30 0 10 20 0     0 45 30 0 0  x   0  0 0 40 0 0    0 50   0 0 65 Giá trị hàm mục tiêu đạt được là: f ( x 0 )  4030 15  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 5.3) Ví dụ 3: Giải bài toán vận tải sau: 16 8
  9.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ PACBXP của BT được thể hiện qua bảng VT sau: Ta nhận thấy đây là PACB không suy biến; 17  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 18 9
  10.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 19  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ 20 10
  11.  CHƯƠNG 3- BÀI TOÁN VẬN TẢI BÀI 3. GIẢI BTVT ĐÓNG BẰNG THUẬT TOÁN THẾ VỊ Tại bảng VT mới này, các HSUL đều không dương, cho nên thuật toán kết thúc. Tuy nhiên, HSUL của ô (4,5) bằng 0 cho nên bài toán có nhiều PATU. Vậy, một trong những PATU của BT là:  0 0 0 0 0 110     30 0 0 15 50 0  x0   0 0 0 70 0 5     0 45 80 0 0 10    f ( x 0 )  5830 21 11
ADSENSE

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.

 

Đồng bộ tài khoản
2=>2