QUY HOẠCH TUYẾN TÍNH - BÀI TOÁN VẬN TẢI

Chia sẻ: Nguyễn Văn Quân | Ngày: | Loại File: PPT | Số trang:31

1
1.577
lượt xem
363
download

QUY HOẠCH TUYẾN TÍNH - BÀI TOÁN VẬN TẢI

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

Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình thường nhưng cước phí vận chuyển là M rất lớn rồi giải như trường hợp không có ô cấm.

Chủ đề:
Lưu

Nội dung Text: QUY HOẠCH TUYẾN TÍNH - BÀI TOÁN VẬN TẢI

  1. 1) Giải bài toán vận tải cho bởi bảng vận tải sau: j 40 50 80 30 i 90 2 4 4 2 40 5 7 1 1 70 4 8 3 6
  2. Bước 1: Thành lập một phương án ban đầu. j 40 50 80 30 i 90 2 4 4 2 40 20 30 40 5 7 1 1 40 70 4 8 3 6 30 40
  3. 2 4 4 2 0 R1= x x x 5 7 1 1 -2 x R2= 4 8 3 6 -4 R3= x x 0 0 5 0 s1= s2= s3= s4= x x x -2 -4 1 -2 1 1 0 -3 x -2 0 0 0 x x
  4. 0 0 5 0 x x x 1 1 0 -3 x * 0 0 5 0 x x x (3) (2) -2 0 0 0 x x 1 1 0 -3 (6) x * (1) -2 0 0 0 x x (4) (5)
  5. 0 0 5 0 � 4); (1, 2); � (2, x x x V =� L , (3) (2) � (3,3) � 1 1 0 -3 (6) x * � 4); (3, 2);� (1, (1) V =� C � (2,3) � -2 0 0 0 x x (4) (5)
  6. 0 0 5 0 � 4); (1, 2); � (2, 40 20 30 V =� L , (3) (2) � (3,3) � 1 1 0 -3 (6) * � 4); (3, 2);� (1, 40 (1) V =� C � (2,3) � -2 0 0 0 30 40 (4) (5) xi* j* = min { xij : (i, j ) � } = min { 30,30, 40} C V = 30
  7. 0 0 5 0 xi* j* = 30 40 20 30 (3) (2) 0 0 5 0 1 1 0 -3 40 50 (6) * 40 (1) 1 1 0 -3 -2 0 0 0 * 30 40 10 30 (4) (5) -2 0 0 0 70
  8. 2 4 4 2 40 50 5 7 1 1 10 30 4 8 3 6 70
  9. 2 4 4 2 0 R1= x x 5 7 1 1 x x 0 R2= 4 8 3 6 -2 R3= X* x 0 0 3 1 s1= s2= s3= s4= x x x -2 -4 -1 -1 3 3 0 0 x 0 2 0 3 x x
  10. 2) Giải bài toán vận tải có ô cấm cho bởi bảng vận tải sau: j 65 75 100 i 80 4 2 1 90 3 5 70 6 7 8
  11. Để giải bài toán vận tải có ô cấm ta sẽ xem ô cấm như ô bình thường nhưng cước phí vận chuyển là M rất lớn rồi giải như trường hợp không có ô cấm. j 65 75 100 i 80 4 2 1 M 90 3 5 70 6 7 8
  12. j 65 75 100 j 65 75 100 i i 80 4 2 1 80 4 2 1 80 M 90 3 5 90 3 5 M 65 20 5 70 6 7 8 70 6 7 8 70 Đây là phương án cực biên ban đầu.
  13. 4 2 1 r1= 4 x 3 5 M r2= 0 x x x 6 7 8 r3= M-7 x s1 s2 s3 5 -M+6 0 x -M -5 -3 0 0 0 x x x M-4 0 M-4 x
  14. 5 -M+6 0 x 0 0 0 x x x M-4 0 M-4 5 -M+6 0 x * x 0 0 0 x x x M-4 0 M-4 x
  15. 5 -M+6 0 (1) * x (4) 0 0 0 x x (2) x (3) M-4 0 M-4 5 -M+6 0 x * 80 x 0 0 0 xi* j* = min { xij : (i, j ) �V }= x x x C 5 min { 5,80} = 5 M-4 0 M-4 x
  16. 80 (1) * x (4) x 65 x (3) (2) x 5 20 x 75 5 70 65 25 70
  17. 5 0 0 4 2 1 x x r1= 4 x x 0 0 M-6 3 5 M r2= 0 x x x x 6 7 8 2 0 2 r3= -1 x x s1 s2 s3 Vì M là số dương rất -6 -5 lớn nên ma trận cước phí -3 mới này không âm. Vậy phương án vừa có là tối ưu.
  18. 3) Giải bài toán vận tải không cân bằng thu phát cho bởi bảng vận tải sau: j 40 50 80 i 90 6 1 1 40 5 7 4 70 4 11 3
  19. Để giải quyết vấn đề này ta thêm vào một trạm thu giả mà cước phí vận chuyển đến đều bằng 0. j 40 50 80 30 i 90 6 1 1 0 40 5 7 4 0 70 4 11 3 0
  20. j 40 50 80 30 j 40 50 80 30 i i 90 6 1 1 0 90 6 1 1 0 60 30 40 5 7 4 0 40 5 7 4 0 40 70 4 11 3 0 70 4 11 3 0 40 10 20
Đồng bộ tài khoản