1. Trang Chủ
  2. Toán học
  3. Bài tập quy hoạch tuyến tính

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

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.... NHÓM I 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

Thể loại Tài liệu miễn phí Toán học

Số trang 92

Ngày tạo 8/29/2018 5:03:38 PM +00:00

Loại tệp PPT

Kích thước

Tên tệp

Tải Bài tập quy hoạch tuyến tính (.pptx) Tải Bài tập quy hoạch tuyến tính (.pdf)

Xem mẫu

  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ổ đề :
nguon tai.lieu . vn
Toán học Môi trường Vật lý Sinh học Địa Lý Hoá học Nông - Lâm - Ngư Cơ khí - Chế tạo máy Tiếng Anh phổ thông Khoa học ứng dụng Nông - Lâm Kiến thức tổng hợp Giáo dục học Xã hội học