TAILIEUCHUNG - 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. nội dung chi tiết. | 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@, 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 ∈
đang nạp các trang xem trước
