intTypePromotion=4

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

0
25
lượt xem
1
download

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

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

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản