Bài tập quy hoạch tuyến tính

Chia sẻ: Lưu Hoàng Em Hoàng Em | Ngày: | Loại File: PPT | Số trang:92

0
1.256
lượt xem
333
download

Bài tập quy hoạch tuyến tính

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

Một dạng bài toán đăch biệt của bài toán QHTT có nhiều ứng dụng trong thực tế là bài toán vận tải, sẽ được nghiên cứu trong chương này. Về mặt lý thuyết bài toán vận tải cũng là một bài toán QHTT nên chúng ta có thể dùng phương pháp đơn hình để giải, Tuy nhiên nếu dùng thuật toán đơn hình như trong chương 2 khối lượng tính toán sẽ rất lớn và phức tạp vì ẩn số quá nhiều....

Chủ đề:
Lưu

Nội dung Text: Bài tập quy hoạch tuyến tính

  1. NHÓM I
  2. BÀI TOÁN VẬN TẢI THÀNH LẬP BÀI TOÁN ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ XÂY DỰNG PACB ĐẦU TIÊN PHƯƠNG PHÁP THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT BÀI TOÁN VẬN TẢI CÓ Ô CẤM TRƯỜNG HỢP SUY BIẾN
  3. BÀI TOÁN VẬN TẢI Một dạng đặc biệt của bài toán QHTT có nhiều ứng dụng trong thực tế là Bài toán vận tải, sẽ được nghiên cứu trong chương này. Về mặt lý thuyết, bài toán vận tải (đã được giới thiệu khái niệm trong đoạn 1.2) cũng là một bài toán QHTT, nên chúng ta cũng có thể dùng phương pháp đơn hình để giải. Tuy nhiên, nếu dùng thuật toán đơn hình như trong chương 2, khối lượng tính toán sẽ rất lớn và phức tạp vì số ẩn quá nhiều. Do có một số đặc điểm riêng, nên người ta xây dựng các phương pháp giải riêng đơn giản hơn, nhanh hơn cho bài toán vận tải. Chương này vẫn dùng ký hiệu: I = {1, 2, …, m} và J = {1, 2, …, n}.
  4. BÀI TOÁN VẬN TẢI 4.1. THÀNH LẬP BÀI TOÁN
  5. BÀI TOÁN VẬN TẢI 4.1.1 Bài toán vận tải cân bằng thu phát m n Ta có ∑ pi = ∑ tj i =1 j =1 (4.1.1)
  6. BÀI TOÁN VẬN TẢI m n z = f ( X ) = ∑∑ cij xij → min i =1 j =1  n ∑ xij = pi i ∈I  j =1 m ∑ xij = t j j∈J  i =1  xij ≥ 0, i ∈I , j ∈ J  
  7. BÀI TOÁN VẬN TẢI 4.1.2 Bài toán không cân bằng thu phát gọi là bài toán dạng mở: m n m n ∑ pi < ∑ tj, và ∑ pi > ∑ tj i =1 j =1 i =1 j =1 m n 4.1.2.1 Trường hợp 1: ∑ pi < ∑ tj i =1 j =1
  8. BÀI TOÁN VẬN TẢI m n z = f ( X ) = ∑∑ cij xij → min i =1 j =1  n ∑ xij = pi i = 1, m  j =1 m ∑ xij ≤ t j j = 1, n  i =1  x ≥ 0, i = 1, m, j = 1, n  ij 
  9. BÀI TOÁN VẬN TẢI 4.1.3 Định lý tồn tại: 4.2 ĐẶC ĐIỂM CỦA BÀI TOÁN VTCĐ m n z = f ( X ) = ∑∑ cij xij → min i =1 j =1  n ∑ xij = pi i ∈I  j =1 m ∑ xij = t j j∈J  i =1  xij ≥ 0, i ∈I , j ∈ J  
  10. BÀI TOÁN VẬN TẢI
  11. BÀI TOÁN VẬN TẢI 1 1 ... 1 0 0 ... 0 ... 0 0 ... 0  0 0 ... 0 1 1 ... 1 ... 0 0 ... 0 ÷  ÷  ... ... ... ... ... ... ... ... ... ... ... ... ... ÷  ÷ A = 1 1 ... 1 0 0 ... 0 ... 1 1 ... 1 ÷ 1 0 ... 0 1 0 ... 0 ... 1 0 ... 0 ÷  ÷ 0 1 ... 0 0 1 ... 0 ... 0 1 ... 0 ÷ 0 0 ... 1 0 0 ... 1 ... 0 0 ... 1 ÷  
  12. BÀI TOÁN VẬN TẢI 4.2.1 Định lý :
  13. BÀI TOÁN VẬN TẢI Thật vậy, với các số thực 2 ,..., α m , λ1 ,..., λn thỏa: α α 2 H 2 + α 3 H 3 + ... + α m H m + λ1H m +1 + λ2 H m+ 2 + +... + λn H m+ n = 0mn chúng ta có ngay λ1 = λ2 = ... = λn = 0 và α 2 + λ1 = 0, α 3 + λ1 = 0,..., α m + λ1 = 0 từ đó,α 2 = α 3 = ... = α m = 0 Do đó, r(A) = m + n - 1.
  14. BÀI TOÁN VẬN TẢI
  15. BÀI TOÁN VẬN TẢI 4.3 PHƯƠNG ÁN CỰC BIÊN CỦA BÀI TOÁN VTCĐ 4.3.1 Mô tả bài toán VTCĐ dưới dạng bảng :
  16. BÀI TOÁN VẬN TẢI Thu ti … tj … tn phát p1 c11 c1j c1n … … ci1 cij cin pi (x ) ij … … cm1 cmj cmn pm … …
  17. BÀI TOÁN VẬN TẢI
  18. BÀI TOÁN VẬN TẢI 4.3.2 Định nghĩa :
  19. BÀI TOÁN VẬN TẢI 4.3.3 Bổ đề :

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản