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

Chương 2: Bài toán đối ngẫu - bài 1

Chia sẻ: Lê Văn Nhứt | Ngày: | Loại File: PDF | Số trang:0

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

Tài liệu tham khảo về bài toán đối ngẫu...

Chủ đề:

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

Lưu

Nội dung Text: Chương 2: Bài toán đối ngẫu - bài 1

  1.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.1 BTDN (D) của BT gốc (P) dạng chính tắc: 1  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫu Ví dụ: Viết BTDN D của BTQHTT (P) sau: f ( x )  3 x1  2 x2  5 x3  x4  min 2 x1  4 x2  3 x3  7 x4  9 x  2x  4x  5x  5  1 2 3 4  3 x1  x2  2 x3  2   x  0 i  1,4  i  2 1
  2.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫu Bài toán D được viết như sau: f ( x )  3 x1  2 x2  5 x3  x4  min 2 x1  4 x2  3 x3  7 x4  9 x  2x  4x  5x  5  1 2 3 4  g ( y )  9 y1  5 y2  2 y3  max 3 x1  x2  2 x3  2   x  0 i  1,4  i  2 y1  y2  3 y 3  3   4 y1  2 y2  y3  2  3 y1  4 y2  2 y3  5  7 y1  5 y2  1 3  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1. Định nghĩa bài toán đối ngẫu Bài toán D được viết như sau: g ( y )  9 y1  5 y 2  2 y 3  max  2 y1  y 2  3 y 3  3  4 y  2 y  y  2  1 2 3   3 y1  4 y 2  2 y 3  5   7 y1  5 y 2  1 4 2
  3.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ: Ví dụ: Viết bài toán đối ngẫu của bài toán sau: f ( x)  2 x1  12 x2  7 x3  3 x4  min 2 x1  4 x2  3 x3  7 x4  9 x  2 x  4 x  5x  5  1 2 3 4  3 x1  x2  2 x3  2  x1 , x3  0; x4  0 5  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ:  x2  x2a  x2b   x4   x4 *  a b *  x2 , x2 , x4  0 6 3
  4.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ: f (x)  2x1 12xa2 12x2b  7x3  3x*4  0.x5  0.x6 min 2x1  4xa2  4x2b  3x3  7x*4  x5  9  x1  2x2  2x2  4x3  5x4  x6  5 a b *  3x1  x2  x2  2x3  2 a b  xi  0 i 1,3,5,6; x2 , x2 , x4  0 a b * 7  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 1.2 BTDN (D) của BT gốc (P) ở dạng tổng quát bất kỳ: g ( y )  9 y11  5 y 22  2 y33  max 2 y11  y 22  3 y 33 2  4 y  2 y  y  12 g ( y )  9 y11  5 y 22  2 y33  max  11 22 33 2 y11  y 22  3 y 33 2 4 y11  2 y 22  y33  12 4 y  2 y  y  12   11 22 33 3 y11  4 y 22  2 y33  7 3 y11  4 y 22  2 y33  7  7 y  5 y  3   7 y11  5 y 22  3 11 22  y11  0  y11  0    y 22  0  y 22  0 8 4
  5.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu 9  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu 10 5
  6.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu “Câu thần chú”: Max  Min Ràng D cùng dấu hoặc “bằng” ẩn P; Ẩn D thì trái ràng P hoặc tuỳ. Min  Max Ràng D thì trái hoặc “bằng” ẩn P; Ẩn D cùng dấu ràng P hoặc tuỳ. 11  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu Ví dụ: Lập bài toán đối ngẫu của bài toán sau: f ( x)  4 x2  3 x3  x5  max 2 x1  3 x2  x3  x4  8 5 x  x  2 x  x  5  2 3 4 5  x  4 x  3x  5 x  6  2 3 4 5   x  0 i  1,5  i  12 6
  7.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu Cách 1: Đưa bài toán trên về dạng chính tắc: f ( x)  0 x1  4 x2  3x3  0 x4  x5  0 x6  max 2 x1  3x2  x3  x4  8 5 x  x  2 x  x  5  2 3 4 5  x  4 x  3x  5 x  x  6  2 3 4 5 6   x  0 i  1,6  i  13  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu g ( y)  8 y1  5 y2  6 y3  min 2 y1  0 g( y)  8y1  5y2  6 y3  min  3 y  5 y  y  4  1 2 3  3y1  5y2  y3  4  y1  y2  4 y3  3  y  y  4 y  3   1 2 3  y1  2 y2  3 y3  0 y1  2 y2  3y3  0  y2  5 y3  1  y  5y 1   2 3  y3  0 y1  0, y3  0 14 7
  8.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu Cách 2: g ( y )  8 y1  5 y 2  6 y 3  min  2 y1  0 ( do x1  0 )   3 y  5 y  y  4 ( do x  0 )  1 2 3 2   y1  y 2  4 y 3  3 ( do x 3  0 )   y1  2 y 2  3 y 3  0 ( do x 4  0 )  y  5 y  1 ( do x 5  0 )  2 3  y1 , y 2 tuy y ( do r .b (1) & ( 2 ) dang thuc )   y3  0 ( do r .b ( 3) bat dang thuc ) 15  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu Cách 2: g ( y )  8 y1  5 y2  6 y3  min  3 y1  5 y2  y3  4  y  y  4 y  3  1 2 3  y1  2 y2  3 y3  0  y  5 y  1  2 3  y1  0, y3  0 16 8
  9.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 2. Cách lập bài toán đối ngẫu Trong ví dụ này, ta có các cặp ràng buộc đối ngẫu sau: x1  0 & y1  0 x2  0 &  3 y1  5 y2  y3  4 x3  0 &  y1  y2  4 y3  3 x4  0 & y1  2 y2  3 y3  0 x5  0 &  y2  5 y3  1 y3  0 & x2  4 x3  3 x4  5 x5  6 17  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 3. Các định lý cơ bản 3.1 Định lý 1: Với cặp bài toán P & D, chỉ xảy ra một trong ba trường hợp sau: a) Cả hai đều không có PA. b) Cả hai đều có PA; khi đó, cả hai cùng có PATU và giá trị HMT TU của 2 BT bằng nhau. c) Một trong hai bài toán không có PA và bài toán kia có PA; khi đó, bài toán không có PATU và hàm mục tiêu của nó không bị chặn. 18 9
  10.  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 3. Các định lý cơ bản 3.1 Định lý 1 (Phát biểu khác): Nếu một trong hai bài toán đối ngẫu có lời giải (tức có PATU) thì bài toán kia cũng có lời giải (tức cũng có PATU) và khi đó, với mọi cặp PATU x0 & y0 của (P) & (D) tương ứng, ta có: f(x0) = g(y0). Hệ quả 1) Điều kiện cần & đủ để cặp BTDN giải được là mỗi BT phải có ít nhất một PA. 2) ĐK cần & đủ để cặp PA x0 & y0 của cặp BTDN tối ưu là f(x0) = g(y0). 19  CHƯƠNG 2- BÀI TOÁN ĐỐI NGẪU BÀI 1: CÁC KHÁI NIỆM & ĐỊNH LÝ CƠ BẢN 3. Các định lý cơ bản 3.2 Định lý 2 (Độ lệch bù yếu): Điều kiện cần & đủ để phương án x0 của P và phương án y0 của D tối ưu là:  0 m  i   ji j x  a y 0  c   i0 i  1, n   j 1    0 n y  j   a ij xi 0  b j  0  j  1, m   i 1  Tức là: Trong các cặp ràng buộc đối ngẫu của cặp bài toán P & D, nếu một ràng buộc thoả mãn lỏng (> hoặc
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