zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán kinh tế: Đối ngẫu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

7
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Toán kinh tế: Đối ngẫu" được biên soạn với các nội dung chính sau: Quy tắc viết đối ngẫu; Cặp bài toán QHTT đối ngẫu; Định lí đối ngẫu yếu; Định lí đối ngẫu mạnh; Định lí về độ lệch bù; Định lí tồn tại;... Mời các bạn cùng tham khảo bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán kinh tế: Đối ngẫu

Đối ngẫu Lecturer: Phạm Thị Hoài Department of Applied Mathematics - School of Applied Mathematics and Informatics - Hanoi University of Science and Technology hoai.phamthi@hust.edu.vn 0/8
Nội dung 1 Cặp bài toán QHTT đối ngẫu 2 Các định lí về đối ngẫu hoai.phamthi@hust.edu.vn 1/8
Cặp bài toán QHTT đối ngẫu Quy tắc viết đối ngẫu Gốc (P) min c T x max b T y Đối ngẫu (D) ai x = bi , i ∈ M1 yi tự do, i ∈ M1 Ràng buộc ai x ≤ bi , i ∈ M2 yi ≤ 0, i ∈ M2 Biến ai x ≥ bi , i ∈ M3 yi ≥ 0, i ∈ M3 xj ≥ 0, j ∈ N1 AT j y ≤ cj , j ∈ N1 Biến xj ≤ 0, j ∈ N2 AT j y ≥ cj , j ∈ N2 Ràng buộc xj tự do, j ∈ N3 AT j y = cj , j ∈ N3 ai là các véc tơ hàng, Aj là các véc tơ cột của ma trận A, A ∈ Rm×n |M1 | + |M2 | + |M3 | = m, |N1 | + |N2 | + |N3 | = n hoai.phamthi@hust.edu.vn 2/8
Cặp bài toán QHTT đối ngẫu Viết bài toán đối ngẫu của QHTT chuẩn tắc minimize cT x subject to Ax ≥ b, x ≥0 QHTT chính tắc minimize cT x subject to Ax = b, x ≥0 hoai.phamthi@hust.edu.vn 3/8
Cặp bài toán QHTT đối ngẫu Đối ngẫu của bài toán đối ngẫu chính là bài toán gốc (tại sao?) Ví dụ: viết bài toán đối ngẫu của bài toán sau minimize − x1 + 2x2 + 3x3 − 8x4 subject to 4x1 + 2x2 + x3 − 9x4 = 7, x1 − x2 + 5x3 + x4 ≥ 5, 6x1 − 8x2 + 3x3 + x4 ≤ 10, x1 ≤ 0,x2 tự do, x3 , x4 ≥ 0 hoai.phamthi@hust.edu.vn 4/8
Các định lí về đối ngẫu Định lí đối ngẫu yếu Theorem 1 Nếu x là phương án chấp nhận được bất kì của bài toán gốc (P) và y là phương án chấp nhận được bất kì của bài toán đối ngẫu (D) thì bT y ≤ c T x Hệ quả 1 Nếu hàm mục tiêu của bài toán min (max) không bị chặn dưới (trên) thì bài toán đối ngẫu của nó có tập chấp nhận được bằng rỗng. Giả sử x¯ , y¯ tương ứng là phương án chấp nhận được của bài toán (P) và (D) thỏa mãn c T x¯ = b T y¯ . Khi đó x¯ , y¯ tương ứng là phương án tối ưu của bài toán (P) và (D). hoai.phamthi@hust.edu.vn 5/8
Các định lí về đối ngẫu Định lí đối ngẫu mạnh Theorem 2 Nếu bài toán QHTT có phương án tối ưu thì bài toán đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của hai bài toán bằng nhau. Hệ quả 2 Điều kiện cần và đủ để cặp phương án chấp nhận được {¯ x , y¯ } của bài toán (P) và (D) là phương án tối ưu là c T x¯ = b T y¯ . hoai.phamthi@hust.edu.vn 6/8
Các định lí về đối ngẫu Định lí tồn tại Theorem 3 Xét một cặp QHTT đối ngẫu. Khi đó chỉ xảy ra một trong các trường hợp sau: Cả hai bài toán đều không có phương án chấp nhận được Cả hai bài toán đều có phương án tối ưu và giá trị tối ưu bằng nhau. Hàm mục tiêu của bài toán min (max) không bị chặn dưới (trên) thì bài toán đối ngẫu của nó có tập chấp nhận được bằng rỗng. hoai.phamthi@hust.edu.vn 7/8
Các định lí về đối ngẫu Định lí về độ lệch bù Theorem 4 Giả sử x là phương án chấp nhận được của bài toán gốc (P) và y là phương án chấp nhận được của bài toán đối ngẫu (D). Khi đó x là một phương án tối ưu của (P) và y là một bài toán (D) khi và chỉ khi ( (Ax − b)T y = 0 (c − AT y )T x = 0 Chú ý: Chúng ta có thể áp dụng Định lí về độ lệch bù để kiểm tra xem một điểm có phải là nghiệm tối ưu của bài toán QHTT hay không. hoai.phamthi@hust.edu.vn 8/8

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.