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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính: Chương 2 - ThS. Nguyễn Văn Phong10/26/2012ĐẠI HỌC TÀI CHÍNH – MARKETINGBỘ MÔN TOÁN – KHOA CƠ BẢNBài giảngQUY HOẠCH TUYẾN TÍNHThS.ThS. Nguyeãn Vaên PhongEmail : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vnChương 2. BÀI TOÁN ĐỐI NGẪU1. KHÁI NIỆM - THÀNH LẬP BÀI TOÁN ĐỐI NGẪU2. CÁC ĐỊNH LÝ ĐỐI NGẪU3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU2NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHKHÁI NIỆM – THÀNH LẬPTù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ư sauGốc(P)min c , xĐốingẫu (D)max b , ya i , x = bi , i ∈ M1Dấuy i töï do, i ∈ M1a , x ≤ bi , i ∈ M2y i ≤ 0,i ∈ M2a i , x ≥ bi , i ∈ M3y i ≥ 0,i ∈ M3x j ≥ 0,RàngBuộcj ∈ N1A j , y ≤ c j , j ∈ N1x j ≤ 0,j ∈ N2Aj , y ≥ c j , j ∈ N2ix j töï do, j ∈ N3DấuAj , y = c j , j ∈ N3RàngBuộcM1 + M2 + M3 = m , N1 + N2 + N3 = nQUY HOAÏCH TUYEÁN TÍNH3NGUYEÃN VAÊN PHONG110/26/2012KHÁI NIỆM – THÀNH LẬPQUAN 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:MINMAXMINRÀNGBUỘCRÀNGBUỘCRÀNGBUỘCDẤUDẤU4NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHCÁC ĐỊNH LÝ ĐỐI NGẪU1. Đị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 , x2. Hệ quả. Giả sử x là một PACNĐ của (P) và y là mộtPACNĐ 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ủahai 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 sauBaøi toaùn (D)Baøi toaùn (P)f = c , x → ming = b, y → maxAx = bx ≥0AT y ≤ cy töï do5NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHCÁ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 bVaø vì x * laø PATU neân∆ k = CB* (B * )−1 Ak − ck ≤ 0, ∀khayTAT CB* (B * )−1  − c ≤ 0TTa ñaët y * = CB * (B * )−1  thì AT y * ≤ c (y* laø ACNÑ cuûa (D))Hôn nöõaT6b, y * =  y *  b = CB* (B * )−1 b = CB * X B* = c , x * NGUYEÃN VAÊN PHONG(ñpcm) QUY HOAÏCH TUYEÁN TÍNH210/26/2012CÁC ĐỊNH LÝ ĐỐI NGẪU4. Đị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 ,xi())7NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTHUẬT TOÁN ĐỐI NGẪU1. Hệ phương trình đối ngẫu. Xét hai hệ sauHệ (I) a11x1 a j 1x1 am1x 1c1x1Hệ (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ÍNH8NGUYEÃN VAÊN PHONGTHUẬT TOÁN ĐỐI NGẪUHệ (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ácphươ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ươngtrì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ươngtrì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àyvới các ẩn cơ sở của hệ kia, như sauQUY HOAÏCH TUYEÁN TÍNH9NGUYEÃN VAÊN PHONG310/26/2012THUẬT TOÁN ĐỐI NGẪU2. Hai bài toán đối ngẫuTừ đị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 địnhnhư 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àitoá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 đốingẫu.10NGUYEÃN VAÊN PHONGQUY HOAÏCH TUYEÁN TÍNHTHUẬT TOÁN ĐỐI NGẪU2. Hai bài toán đối ngẫuTừ định lý đối ng ...