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

Đâ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
Nội dung trích xuất từ tài liệu:
Các định lý cơ bản về cặp bài toán đối ngẫu 2016 §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. 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 ) 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Ư. 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Ư 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 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: 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= � 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 ...