Bài giảng Quy hoạch tuyến tính: Chương 2 - ThS. Nguyễn Văn Phong

Chia sẻ: Bình Yên | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

76
lượt xem 2
download

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

Bài giảng "Quy hoạch tuyến tính - Chương 2: Bài toán đối ngẫu" cung cấp cho người học các kiến thức: Khái niệm - Thành lập bài toán đối ngẫu, các định lý đối ngẫu, thuật toán đơn hình đối ngẫu. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Quy hoạch tuyến tính: Chương 2 - ThS. Nguyễn Văn Phong

10/26/2012 ĐẠI HỌC TÀI CHÍNH – MARKETING BỘ MÔN TOÁN – KHOA CƠ BẢN Bài giảng QUY HOẠCH TUYẾN TÍNH ThS. ThS. Nguyeãn Vaên Phong Email : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vn Chương 2. BÀI TOÁN ĐỐI NGẪU 1. KHÁI NIỆM - THÀNH LẬP BÀI TOÁN ĐỐI NGẪU 2. CÁC ĐỊNH LÝ ĐỐI NGẪU 3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 2 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH KHÁI NIỆM – THÀNH LẬP Tùy thuộc vào dạng của bài toán QHTT gốc (P) khi đó ta xây dựng bài toán đối ngẫu (D) như sau Gốc (P) min c , x Đối ngẫu (D) max b , y a i , x = bi , i ∈ M1 Dấu y i töï do, i ∈ M1 a , x ≤ bi , i ∈ M2 y i ≤ 0, i ∈ M2 a i , x ≥ bi , i ∈ M3 y i ≥ 0, i ∈ M3 x j ≥ 0, Ràng Buộc j ∈ N1 A j , y ≤ c j , j ∈ N1 x j ≤ 0, j ∈ N2 Aj , y ≥ c j , j ∈ N2 i x j töï do, j ∈ N3 Dấu Aj , y = c j , j ∈ N3 Ràng Buộc M1 + M2 + M3 = m , N1 + N2 + N3 = n QUY HOAÏCH TUYEÁN TÍNH 3 NGUYEÃN VAÊN PHONG 1 10/26/2012 KHÁI NIỆM – THÀNH LẬP QUAN HỆ GIỮA BT (P) VÀ BT (D) như sau - Mục tiêu của hai bài toán thì đối ngẫu (min ↔ max) - Số ràng buộc của (P) bằng với số ẩn của (D) - Số ẩn của (P) bằng với số ràng buộc của (D) - Dấu của ẩn của (P) và Dấu ràng buộc của (D) thì trái dấu. QUY TẮC: MIN MAX MIN RÀNG BUỘC RÀNG BUỘC RÀNG BUỘC DẤU DẤU 4 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH CÁC ĐỊNH LÝ ĐỐI NGẪU 1. Định lý đối ngẫu (Yếu). Nếu x là một PACNĐ bất kỳ của (P) và y là một PACNĐ bất kỳ của (D), thì b, y ≤ c , x 2. Hệ quả. Giả sử x là một PACNĐ của (P) và y là một PACNĐ của (D), và b, y = c , x . Khi đó x là PATƯ của (P) và y PATƯ của (D) 3. Định lý đối ngẫu (Mạnh). Nếu một bài toán có PATU thì bài toán đối ngẫu của nó cũng có PATU và giá trị TU của hai hàm mục tiêu bằng nhau. Chứng minh. Trước hết ta nhắc lại một số ký hiệu sau Baøi toaùn (D) Baøi toaùn (P) f = c , x → min g = b, y → max Ax = b x ≥0 AT y ≤ c y töï do 5 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH CÁC ĐỊNH LÝ ĐỐI NGẪU * Giaû söû x laø PATU cuûa (P), ta coù { } { } { } B * = Aj , j ∈ J ( x * ) , CB* = c j , j ∈ J ( x * ) , X B * = x *j , j ∈ J ( x * ) Khi ñoù, ta coù X B * = (B * )−1 b vaø fmin = f ( x * ) = CB * (B * )−1 b Vaø vì x * laø PATU neân ∆ k = CB* (B * )−1 Ak − ck ≤ 0, ∀k hay T AT CB* (B * )−1  − c ≤ 0   T Ta ñaët y * = CB * (B * )−1  thì AT y * ≤ c (y* laø ACNÑ cuûa (D))   Hôn nöõa T 6 b, y * =  y *  b = CB* (B * )−1 b = CB * X B* = c , x * NGUYEÃN VAÊN PHONG (ñpcm)   QUY HOAÏCH TUYEÁN TÍNH 2 10/26/2012 CÁC ĐỊNH LÝ ĐỐI NGẪU 4. Định lý độ lệch bù. Giả sử x là PACNĐ của (P), y là PACNĐ của (D). Khi đó x là PATU của (P) và y là PATU của (D), nếu và chỉ nếu   Ax − b, y = 0  T  c − A y,x = 0  Áp dụng. Vì x ≥ 0, y ≥ 0 neân ñònh lyù ñöôïc vieát laïi nhö sau  y i > 0 ⇒ a i , x = bi − bi y i = 0, ∀i ⇔  i  a , x − bi > 0 ⇒ y i = 0   x j > 0 ⇒ Aj , y = c j (II ) : c j − y , Aj x j = 0, ∀j ⇔  c j − y , A j > 0 ⇒ x j = 0  (I ) : ( a ,x i ( ) ) 7 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH THUẬT TOÁN ĐỐI NGẪU 1. Hệ phương trình đối ngẫu. Xét hai hệ sau Hệ (I)  a11x1    a j 1x1    am1x 1  c1x1 Hệ (II)  − a11y 1    − a1i y 1    − a1n y 1   − b1y 1 + ... + a1i x i ... + ... + a1n x n ... + x n+1 = b1 + ... + a ji x i ... + ... + a jn x n ... + x n+ j = bj + ... + ami x i + ... + ci x i + ... + amn x n + ... + cn x n + x n+ m + f = bm = α − ... − a j 1y j − ... − am 1y m + y m +1 = c1 − ... − a ji y j − ... − ami y m + y m +i = ci − ... − a jn y j − ... − b j y j − ... − amn x n − ... − bm y m + y m +n + g = cn = −α QUY HOAÏCH TUYEÁN TÍNH 8 NGUYEÃN VAÊN PHONG THUẬT TOÁN ĐỐI NGẪU Hệ (I), (II) được gọi là đối ngẫu, nếu - Hệ số các ẩn tự do trong phương trình thứ j của hệ (I) và hệ số của ẩn tự do thứ j của hệ (II) (hệ số của yj trong các phương trình của hệ (II)) thì đối nhau. - Số hạng tự do của hệ (I) và hệ số các ẩn tự do của phương trình cuối hệ (II) thì đối nhau. - Số hạng tự do của hệ (II) và hệ số các ẩn tự do của phương trình cuối hệ (I) thì bằng nhau. - Số hạng tự do phương trình cuối trong hai hệ thì đối nhau. Khi đó, ta có sự tương quan giữa các ẩn tự do của hệ này với các ẩn cơ sở của hệ kia, như sau QUY HOAÏCH TUYEÁN TÍNH 9 NGUYEÃN VAÊN PHONG 3 10/26/2012 THUẬT TOÁN ĐỐI NGẪU 2. Hai bài toán đối ngẫu Từ định lý đối ngẫu mạnh, ta có nhận xét sau: - Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU), - Sau đó ta thực hiện một phép biến đổi cơ sở tương ứng trong BT (D) cũng tối ưu. - Khi đó, nghiệm cơ sở TU của BT (D) được xác định như sau : - Giả sử cơ sở tối ưu của bài toán min là {x1, x2, …,xn} , {xn+1, xn+2, …,xn+m}, là các ẩn tự do mà đối với cơ sở này bài toán min đạt cực tiểu. - Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2, …,ym} , {ym+1, ym+2, …,ym+n}, là các ẩn tự do. - Khi đó, hai BT này tạo thành hai hệ phương trình đối ngẫu. 10 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH THUẬT TOÁN ĐỐI NGẪU 2. Hai bài toán đối ngẫu Từ định lý đối ngẫu mạnh, ta có nhận xét sau: - Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU), - Sau đó ta thực hiện một phép biến đổi cơ sở tương ứng trong BT (D) (max) cũng tối ưu. - Khi đó, nghiệm cơ sở TU của BT (D) được xác định như sau: - Giả sử cơ sở tối ưu của bài toán min là {x1, x2, …,xn} , các ẩn {xn+1, xn+2, …,xn+m}, là các ẩn tự do mà đối với cơ sở này bài toán min đạt cực tiểu. - Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2, …,ym} , các ẩn {ym+1, ym+2, …,ym+n}, là các ẩn tự do. - Khi đó, hai BT này tạo thành hai hệ phương trình đối ngẫu. Và các ẩn của chúng có quan hệ như trong phần 1. 11 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH THUẬT TOÁN ĐỐI NGẪU 2. Hai bài toán đối ngẫu Và nghiệm của bài toán (D) được xác định như sau: Chú ý. Ta thấy trong cặp bài toán đối ngẫu nhau chỉ xảy ra một trong ba trường hợp sau : * Trường hợp 1. Cả hai bài toán cùng có phương án thì cả hai bài toán cùng có phương án tối ưu. * Trường hợp 2. Bài toán này có phương án, bài toán kia không có phương án thì cả hai bài toán không có phương án tối ưu. * Trường hợp 3. Cả hai bài toán không có phương án thì hiển nhiên cả hai không có phương án tối ưu. QUY HOAÏCH TUYEÁN TÍNH y1  ... ym    y m +1 ...    y m+n = cn +1 ... ... = cm = c1 ... ... = cn Trong đó, các cj là các hệ số của các ẩn trong hàm mục tiêu ở bảng đơn hình TU 12 NGUYEÃN VAÊN PHONG 4 10/26/2012 THUẬT TOÁN ĐỐI NGẪU 3. Thuật toán đơn hình đối ngẫu Nghĩa là: Ta dùng thuật toán đơn hình trên bài toán đối ngẫu và sử dụng mối quan hệ giữa các ẩn của hai bài toán đê suy ra nghiệm cho bài toán gốc và ngược lại. Ví dụ. Tìm nghiệm của bài toán sau bằng thuật toán đơn hình đối ngẫu. BT (P) BT (D) g = x 1 − x 2 → min f = − y 1 − 2 y 2 − 3 y 3 → max  − y 1 + 2 y 2 − 3y 3  2y 1 − y 2 − y 3 y 1 , y 2 , y 3 ≥ 0.  − x1 + 2 x 2  2 x1 − x 2  −3 x − x 1 2  ≤ 1 ≤ −1 ≥ −1 ≥ −2 ≥ −3 x 1 , x 2 ≥ 0. 13 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH THUẬT TOÁN ĐỐI NGẪU 3. Thuật toán đơn hình đối ngẫu Trước tiên, ta viết hai bài toán này thành hai hệ đối ngẫu. BT (P)  − y 1 + 2y 2 − 3y 3 + y 4   2y 1 − y 2 − y 3  y + 2y + 3 y  1 2 3 1 = = −1 + y5 +f = 0 BT (D) =  x1 − 2 x 2 + x 3  + x4 =  −2 x 1 + x 2  + x5 =  3 x1 + x 2  − x1 + x 2 +g =  1 2 3 0 14 NGUYEÃN VAÊN PHONG QUY HOAÏCH TUYEÁN TÍNH THUẬT TOÁN ĐỐI NGẪU Đối với (D), ta chuyển về dạng chuẩn như sau g = x 1 − x 2 → min ( g − x 1 + x 2 = 0 )  x1 − 2 x 2 + x 3  + x4  −2 x 1 + x 2 3 x + x + x5 2  1 x 1, x 2 , x 3 , x 4 , x 5 ≥ 0. = 1 = 2 = 3 Và lập bảng đơn hình Hệ số CB Cơ sở B Phương án 1 -1 0 0 0 A1 A2 A3 A4 A5 0 A3 1 1 -2 1 0 0 0 A4 2 -2 1 0 1 0 0 A5 3 3 1 0 0 1 g 0 -1 1 0 0 θ 0 QUY HOAÏCH TUYEÁN TÍNH 15 NGUYEÃN VAÊN PHONG 5