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

Bài giảng Tối ưu: Chương 2 - ThS. Trần Thị Thùy Nương

Chia sẻ: Bfvhgfff Bfvhgfff | Ngày: | Loại File: PDF | Số trang:27

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

Nội dung trình bày trong chương 2 Tối ưu hóa rời rạc thuộc bài giảng Tối ưu nhằm trình bày về bài toán tối ưu hóa rời rạc (tối ưu tổ hợp), bài toán ba lô (bài toán cái túi), bài toán Quy hoạch (QH) nguyên tuyến tính Thuật toán Gomory, phương pháp nhánh cận Land – Doig.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tối ưu: Chương 2 - ThS. Trần Thị Thùy Nương

  1. Chương 2 TỐI ƯU HÓA RỜI RẠC 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1
  2. NỘI DUNG 1. Bài toán tối ưu hóa rời rạc (tối ưu tổ hợp) 2. Bài toán ba lô (bài toán cái túi) 3. Bài toán Quy hoạch (QH) nguyên tuyến tính 4. Thuật toán Gomory 5. Phương pháp nhánh cận Land – Doig 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 2
  3. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Định nghĩa Bài toán tối ưu hóa rời rạc xác định trên tập hữu hạn S, và f : S → ℝ. s * ∈ S : f (s ) = min{f (s )}. * s∈S 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 3
  4. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Tối ưu hóa rời rạc dựa vào: • Quy hoạch tuyến tính • Lý thuyết đồ thị • Lý thuyết về độ phức tạp tính toán 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 4
  5. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Một số ví dụ về bài toán tối ưu rời rạc: • Bài toán tìm đường đi ngắn nhất • Bài toán ba lô • Bài toán người du lịch 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 5
  6. BÀI TOÁN BA LÔ(Knapsack problem) Bài toán: Có một tập hợp gồm n loại đồ vật khác nhau có trọng lượng và giá trị sử dụng tương ứng là aj và cj , j = 1,…,n. Bài toán đặt ra là cần lựa chọn một tập hợp các đồ vật để cho vào một ba lô sao cho tổng giá trị sử dụng của chúng là lớn nhất và tổng trọng lượng không được vượt quá tải trọng b cho trước của ba lô. 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 6
  7. BÀI TOÁN BA LÔ(Knapsack problem) Xét bài toán ba lô 0 – 1 Một đồ vật j có thể được chọn để bỏ vào ba lô hoặc là không. Gọi x j := 1 khi đồ vật j được chọn, và x j := 0 khi đồ vật j không được chọn, 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 7
  8. BÀI TOÁN BA LÔ(Knapsack problem) Mô hình bài toán ba lô 0 – 1 : n max f ( x ) = ∑ c j x j j =1 n ∑ a j x j ≤ b  j =1  x ∈ {0,1}, j = 1,..., n  j 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 8
  9. BÀI TOÁN QH NGUYÊN (Integer Programming – IP ) Là bài toán quy hoạch trong đó tất cả hoặc một phần các biến chỉ nhận giá trị nguyên. + QH nguyên hoàn toàn (Pure Integer Programming) + QH nguyên bộ phận (Mixed Integer Programming) 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 9
  10. BÀI TOÁN QH NGUYÊN Mô hình bài toán QH nguyên tuyến tính n f (x) = ∑c x j =1 j j → min  n  ∑ aij x j = bi , i = 1, m  j =1  (IP )  x j ≥ 0, j = 1, n   x j nguyê n, j = 1, n   10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 10
  11. THUẬT TOÁN GOMORY Trước hết, giải bài toán nới lỏng (LP) n f (x) = ∑c x j =1 j j → min  n  ∑ aij x j = bi , i = 1, m (LP )  j =1  x ≥ 0, j = 1, n  j 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 11
  12. THUẬT TOÁN GOMORY Không mất tính tổng quát, giả sử PATƯ của (LP) có dạng: x * = ( x1, x2 ,..., xm ,0,...,0). Khi đó, hệ ràng buộc của (LP) có dạng: x1 ′ ′ ′ + a1( m+1) xm+1 + ... + a1n xn = b1   x2 ′ ′ + a2(m+1) xm+1 + ... + a2n xn = b2 ′  ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯  ′ ′ xm + am(m+1) xm+1 + ... + amn xn = bm ′  10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 12
  13. THUẬT TOÁN GOMORY Nếu các bi ′ , i = 1, m đều là số nguyên thì xi , i = 1, m cũng là nghiệm của (IP). Ngược lại, giả sử có bi ′ nào đó chưa nguyên. Ta xét ptr ràng buộc tương ứng: xi + ai′( m +1) xm +1 + ... + ain xn = bi′ ′ (1) 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 13
  14. THUẬT TOÁN GOMORY  ′ ′ Đặt aij = [aij ] + α ij , j = m + 1,..., n  bi′ = [bi′] + β i  (α ij ≥ 0, 0 < β i < 1) n (1) ⇒ xi + ∑ ([a′ ] + α ij ij )x j = [bi ′ ] + βi , i = 1 m , j = m +1 n n xi − [bi′ ] + ∑ [a′ ]x ij j = βi − ∑ α x ,i = 1,m ij j (2) j =m+1 j =m+1 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 14
  15. THUẬT TOÁN GOMORY Vế trái (2) sẽ là số nguyên nếu x * là PA cnđ của (IP), do đó vế phải (2) cũng phải là số nguyên, tức là: n β i − ∑ α ij x j nguyên (3) j = m +1 Mặt khác  x j ≥ 0,   ′ ′ α ij = aij − [aij ] ≥ 0, j = m + 1,..., n  nên n βi − ∑α j = m +1 ij x j ≤ βi (3′) 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 15
  16. THUẬT TOÁN GOMORY n (3),(3′) ⇒ β i − ∑α j = m +1 ij x j ≤ 0 (0 < β i < 1) n Hay − ∑α j = m +1 ij x j ≤ −βi (4) Thêm biến bù xn +1 vào (4), n − ∑α j = m +1 ij x j + x n +1 = − β i (5) 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 16
  17. THUẬT TOÁN GOMORY Bổ sung RB (5) vào bảng đơn hình. Khi dó, bảng mới này vừa không đảm bảo RB dấu của biến, vừa chưa nguyên. Tiếp theo, áp dụng thuật toán đơn hình đối ngẫu để nhận được PATƯ. 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 17
  18. PP NHÁNH CẬN LAND – DOIG Xét bài toán QH nguyên có dạng n f (x) = ∑c j =1 j x j → m ax  n  ∑ a j x j ≤ b i , i = 1,..., m  j =1  ( IP0 )  x j ≥ 0, j = 1,..., n   x j nguy ê n , j = 1,..., n   với a j , bi , c j là các số nguyên cho trước i = 1m; j = 1n , , 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 18
  19. PP NHÁNH CẬN LAND – DOIG Đặt   n  D0 := x ∈ ℝ : ∑ aj x j ≤ bi , i = 1 m, x j ≥ 0, nguyên, j = 1 n  n , ,...,   j =1  Các bước giải bài toán Bước 1: giải bài toán nới lỏng (LP0), với   n   x ∈ ℝ n : ,...,  nl D0 :=   ∑ a j x j ≤ bi , i = 1 m, x j ≥ 0, j = 1 n ,    j =1   10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 19
  20. PP NHÁNH CẬN LAND – DOIG 0 0 Giả sử (LP0) có PATƯ x và giá trị tối ưu f (x ) . 0 0 Nếu x nguyên thì dừng lại. Lúc đó, x cũng là PATƯ của (IP0). Ngược lại, chuyển sang Bước 2. 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 20
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