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 ∈

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.