intTypePromotion=3

Các định lý cơ bản về cặp bài toán đối ngẫu 2016

Chia sẻ: Tran Xuan Trung | Ngày: | Loại File: PPT | Số trang:33

0
306
lượt xem
38
download

Các định lý cơ bản về cặp bài toán đối ngẫu 2016

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

Đây là tài liệu cung cấp về mối quan hệ giữa các bài toán đối ngẫu thông qua các định lý, các hệ quả, các ví dụ và bài tập điển hình. Giúp người đọc nắm rõ được kiến thức về bài toán đối ngẫu, mời các bạn tham khảo

Chủ đề:
Lưu

Nội dung Text: Các định lý cơ bản về cặp bài toán đối ngẫu 2016

  1. §2 Các định lý cơ bản về cặp bài toán đối ngẫu 1. Mối quan hệ giữa cặp bài toán đối ngẫu 2. Ứng dụng của bài toán đối ngẫu: 2. 1. Tìm PATƯ của bài toán đối ngẫu 2. 2. Chứng tỏ tính tối ưu của một phương án 2. 3. Giải bài toán có dạng đặc biệt.
  2. Mối quan hệ giữa cặp bài toán đối ngẫu f (x) = c1x1 + c 2 x 2 + ...... + c n x n Min (Max) a11x1 + a12 x 2 + ...... + a1n x n = b1 .................................................... a m1x1 + a m2 x 2 + ...... + a mn x n = b m xj 0 ∀j = 1, n Bài toán đối ngẫu: g(y) = b1y1 + b 2 y 2 + ...... + b m y m Max (Min) a11 y1 + a 21y 2 + ...... + a m1 y m c1 ( c1 ) .................................................... a1n y1 + a 2n y 2 + ...... + a mn y m cn ( cn )
  3. Mối quan hệ giữa cặp bài toán đối ngẫu Mối quan hệ giữa hai bài toán được thể hiện trong các định lý sau: Định lý 1: Đối với cặp bài toán đối ngẫu bao giờ cũng chỉ xẩy ra một trong 3 trường hợp sau: - Cả hai bài toán đều không có phương án. - Cả hai bài toán đều có phương án, lúc đó cả hai bài toán đều có PATƯ và giá trị hàm mục tiêu của chúng bằng nhau - Một trong 2 bài toán không có phương án, bài toán kia có phương án, khi ấy bài toán có phương án sẽ không có PATƯ.
  4. Mối quan hệ giữa cặp bài toán đối ngẫu Hệ quả 1: Nếu một trong 2 bài toán đối ngẫu có PATƯ thì bài toán kia cũng có PATƯ
  5. Mối quan hệ giữa cặp bài toán đối ngẫu Hệ quả 2: x0, y0 là hai phương án của bài toán (I), (I’), khi đó x0, y0 là PATƯ khi và chỉ khi f(x0) = g(y0) Chứng minh: Điều kiện cần: Được suy từ định lý trên Điều kiện đủ: Gọi x’ là phương án bất kì của bài toán (I), khi đó ta có: n n � m �, m �n �0 f (x ') = � jx ,j c �� ijyi � j = � a 0 x � � ijx j �i � a , y j =1 j = 1 �=1 i � i = 1 �=1 j � m = bi y = g(y ) = g(x ) 0 i 0 0 i =1
  6. Mối quan hệ giữa cặp bài toán đối ngẫu Hay x0 là PATƯ. Mặt khác do f(x0) = g(y0) nên theo định lý trên y0 cũng là PATƯ. Định lý 2: (Tiêu chuẩn tối ưu) Hai phương án của cặp bài toán đối ngẫu là PATƯ khi và chỉ khi với mỗi cặp ràng buộc đối ngẫu nếu một ràng buộc thõa mãn với dấu bất đẳng thức thực sự thì ràng buộc kia thõa mãn với dấu bằng. Chứng minh:
  7. Mối quan hệ giữa cặp bài toán đối ngẫu x0 = (x01, x02 , ... , x0n) và y0 = (y01, y02, ... , y0m) lần lượt là PATƯ cua bài toán (I) và (I’) Xét đẳng thức: m n g(y 0 ) − f (x 0 ) = � i .y i0 − � j .x 0 b c j i =1 j =1 m �n �0 n = �� ij .x j � i − � j .x j � a 0 .y c 0 i =1 � 1 j= � j =1 n � m �0 n = �� ij .yi0 � j − � j .x 0 � a .x c j j =1 � 1 i= � j =1 n � m �0 = �� ij .yi − c j � j � a 0 .x j =1 � 1 i= �
  8. Mối quan hệ giữa cặp bài toán đối ngẫu Do x0, y0 là PATƯ khi và chỉ khi: n � m �0 g(y ) − f (x ) = � � ij .y i − c j � j = 0 0 0 � a 0 .x j =1 � 1 i= � Điều kiện cần: x0, y0 là PATƯ nên: � m n �0 g(y ) − f (x ) = � � ij .y i − c j � j = 0 0 0 � a 0 .x j =1 � 1 i= � m Mặt khác ta có: a ij .y 0 i c j và x 0 j 0 ∀j = 1, n i =1 m Vì vậy: - Nếu x j > 0 thì: 0 a ij .y = c j 0 i i =1 m - Nếu a ij .y < c j 0 i thì x0j = 0 i =1
  9. Mối quan hệ giữa cặp bài toán đối ngẫu Điều kiện đủ: Hiển nhiên được suy ra từ bất đẳng thức trên Định lý 3: (Tiêu chuẩn tối ưu phát biểu cho cặp bài toán đối ngẫu tổng quát) Điều kiện cần và đủ để 2 phương án x0, y0 của cặp bài toán đối ngẫu tối ưu là trong mỗi cặp ràng buộc đối ngẫu nếu ràng buộc này thõa mãn với dấu bất đẳng thức thực sự thì ràng buộc kia thõa mãn với dấu bằng.
  10. Ứng dụng của bài toán đối ngẫu 2.1 Tìm PATƯ của bài toán đối ngẫu PP 1: Nhờ tiêu chuẩn tối ưu nên khi ta biết được PATƯ của một trong cặp bài toán đối ngẫu thì ta dễ dàng tìm được PATƯ của bài toán còn ạ lVíi.dụ 1: Cho bài toán QHTT sau: f (x) = 3x1 + 4x 2 + x 3 min −3x1 + 2x 2 − 4x 3 15 2x1 − x 2 − 5x 3 8 4x1 + 2x 2 + 2x 3 10 x1 0; x 2 0; x 3 0 Cho biết bài toán trên có PATƯ là x0 = (7, 0, -9). Hãy lập và giải bài toán đối ngẫu của bài toán trên.
  11. Tìm PATƯ của bài toán đối ngẫu Giải: Bài toán đối ngẫu là: f(x) = 15y1 + 8y2 + 10y3 → Max Các ràng buộc: -3y1 + 2y2 + 4y3 ≤ 3 2y1 - y2 + 2y3 ≤ 4 -4y1 - 5y2 + 2y3 ≤ 1 Trong đó: y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 Do bài toán đối ngẫu có phương án tối ưu là x0 = (7, 0, -9) nên theo định lí độ lệch bù yếu ta có: -3y1 + 2y2 + 4y3 = 3 (1) -4y1 -5y2 + 2y3 = 1 (2)
  12. Tìm PATƯ của bài toán đối ngẫu Mặt khác khi thay phương án x0 vào các ràng buộc của bài toán gốc ta thấy ràng buộc thứ ba thõa mãn không chặt nên: y2 = 0 (3) Từ hệ phương trình (1), (2), (3) ta dễ dàng suy ra nghiệm là y0 = (1/5, 0, 9/10) ta thấy nghiệm này thõa mãn hai ràng buộc còn lại của bài toán đối ngẫu nên nó là PATƯ của bài toán đối ngẫu. bài toán đối ngẫu có phương án tối ưu Vậy là: y0 = (1/5, 0, 9/10) và g(y0) = 12.
  13. Tìm PATƯ của bài toán đối ngẫu Phương pháp 2: (Sử dụng bảng đơn hình) Để vận dụng PP này ta dùng thuật toán đơn hình để giải (I), khi đó PATƯ của bài toán (I’) s ẽ là: yi = cj + ∆ j i = 1, 2, …. , m cj, ∆ j là hệ số tương ứng với ẩn cơ sở xj của phương trình thứ i trong bảng đơn hình đầu tiên. ∆ j là hệ số trong bảng đơn hình cuối cùng ứng với PATƯ. Lưu ý: Trong bảng đơn hình đối với bài toán (I) cần phải đưa vào cột đơn hình ứng với ẩn giả
  14. Tìm PATƯ của bài toán đối ngẫu Ví dụ: Cho bài toán QHTT : f(x) = x1 + 2x2 + 3x3 + 3x4 → Max Các ràng buộc: 2x1 + x2 + x3 + 2x4 ≤ 20 x1 + 2x2 + 3x3 + 4x4 = 18 2x1 + x2 + 2x3 + x4 ≥ 16 Trong đó: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 a. Hãy giải bài toán. b. Hãy viết bài toán đối ngẫu và chỉ ra PATƯ của bài toán đối ngẫu.
  15. Tìm PATƯ của bài toán đối ngẫu Bài toán ở dạng chuẩn: f(x) = x1 + 2x2 + 3x3 + 3x4 – Mx7 – Mx8 → Max Các ràng buộc: 2x1 + x2 + x3 + 2x4 + x5 = 20 x1 + 2x2 + 3x3 + 4x4 + x7 = 18 2x1 + x2 + 2x3 + x4 - x6 + x8 = 16 Trong đó: x5, x6 là biến phụ; x7, x8 là biến giả x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0; x7 ≥ 0; x8 ≥ 0
  16. Tìm PATƯ của bài toán đối ngẫu ci xi yi y1 y2 y3 y4 y5 y6 y7 y8 0 x5 20 2 1 1 2 1 0 0 0 -M x7 18 1 2 3 4 0 0 1 0 -M x8 16 2 1 2 1 0 -1 0 1 f(x) 0 -1 -2 -3 -3 0 0 0 0 -34 -3 -3 -5 -5 0 1 0 0
  17. Tìm PATƯ của bài toán đối ngẫu ci xi yi x1 x2 x3 x4 x5 x6 x7 x8 0 x5 14 5/3 1/3 0 2/3 1 0 -1/3 0 3 x3 6 1/3 2/3 1 4/3 0 0 1/3 0 -M x8 4 4/3 -1/3 0 -5/3 0 -1 -2/3 1 f(x) 18 0 0 0 1 0 0 1 0 -4 -4/3 1/3 0 5/3 0 1 1/3 0
  18. Tìm PATƯ của bài toán đối ngẫu ci xi bi x1 x2 x3 x4 x5 x6 x7 x8 0 x5 9 0 3/4 0 11/4 1 5/4 1/2 -5/4 3 x3 5 0 3/4 1 7/4 0 1/4 1/2 -1/4 1 x1 3 1 -1/4 0 -5/4 0 -3/4 -1/2 3/4 f(x) 18 0 0 0 1 0 0 1+M M PATƯ của bài toán mở rộng là : (3,0,5,0,9,0,0,0) Giá trị hàm mục tiêu đạt được là : f(x) = 18 PATƯ của bài toán xuất phát: (3,0,5,0) fmax = 18
  19. Chứng tỏ tính tối ưu của một phương án Vấn đề: Không giải bài toán QHTT xem xét phương án x0 có là PATƯ hay không? Phương pháp: Lập bài toán đối ngẫu, giả sử x0 là PATƯ sau đó dùng tiêu chuẩn tối ưu để tìm phương án tương ứng với x0, nếu tồn tại phương án tương ứng thì x0 là PATƯ còn không tồn tại phương án chứng tỏ x0 không là PATƯ.
  20. Chứng tỏ tính tối ưu của một phương án Ví dụ: Cho bài toán QHTT f(x) = - 8x1 + 6x2 + 4x3 + 5x4 → min Ràng buộc: x1 – 2x3 + x4 ≤ 7 -2x1 + x2 – x3 + 3x4 = -4 3x1 – x2 + 2x3 – 6x4 ≥ 5 x1 ≥ 0; x2 ≥ 0; x4 ≥ 0 a. Viết bài toán đối ngẫu của bài toán trên b. Chứng tỏ x* = (3, 0, -2, 0) là phương án. x* có là PATƯ hay không? Tìm tập PATƯ của bài toán đối ngẫu? c. Tìm tập PATƯ của bài toán xuất phát?

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản