zunia.vn

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

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu (ĐH Tôn Đức Thắng)

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:18

Báo xấu

162
lượt xem 16
download

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: Lý thuyết đối ngẫu" cung cấp cho người học các kiến thức: Bài toán đối ngẫu quy hoạch tuyến tính (xây dựng bài toán đối ngẫu, các định lý đối ngẫu), phương pháp đơn hình đối ngẫu. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu (ĐH Tôn Đức Thắng)

Chương 2 LÝ THUYẾT ĐỐI NGẪU 20/6/2012 MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính 1
NỘI DUNG 1. Bài toán đối ngẫu quy hoạch tuyến tính 1.1 Xây dựng bài toán đối ngẫu 1.2 Các định lý đối ngẫu 2. Phương pháp đơn hình đối ngẫu 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 2
Bài toán đối ngẫu QHTT 1. Xây dựng bài toán đối ngẫu QHTT Xét bài toán n f ( x ) = ∑ c j x j → min j =1 n ∑ aij x j ≥ bi , i = 1, m (P )  j =1  x ≥ 0, j = 1, n.  j 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 3
Bài toán đối ngẫu QHTT Bài toán đối ngẫu của bài toán trên là m g ( y ) = ∑ bi y i → max i =1 m ∑ aij y i ≤ c j , j = 1, n (D )  i =1  y ≥ 0, i = 1, m.  i 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 4
Bài toán đối ngẫu QHTT Nhận xét: • Cả hai bài toán đều ở dạng chuẩn tắc; • Một bài toán min, một bài toán max; • Số biến của bài toán này là số ràng buộc của bài toán kia và ngược lại; • c j và bi đổi vai trò cho nhau. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 5
Bài toán đối ngẫu QHTT Ví dụ 1 Lập bài toán đối ngẫu của bài toán sau f ( x ) = 3 x1 + 2 x2 + 5 x3 → min −2 x1 + x2 + 4 x3 ≥ 6   x1 − 5 x2 + 2 x3 ≥ 8  x ≥ 0, j = 1,2,3  j 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 6
Bài toán đối ngẫu QHTT f ( x ) = 3 x1 + 2 x2 + 5 x3 → min −2 x1 + x2 + 4 x3 ≥ 6  (P )  x1 − 5 x2 + 2 x3 ≥ 8  x ≥ 0, j = 1,2,3  j 1,2, 3 g ( y ) = 6 y1 + 8 y 2 → max −2y1 + y 2 ≤ 3   y1 − 5 y 2 ≤ 2 (D )   4 y1 + 2y 2 ≤ 5  y ≥ 0, y ≥ 0  1 2 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 7
Bài toán đối ngẫu QHTT Quy tắc lập bài toán đối ngẫu Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc) Biến: x1, x 2 ,..., x n Biến: y 1, y 2 ,..., y m Hàm mục tiêu: Hàm mục tiêu: n m f ( x ) = ∑ c j x j → min g ( y ) = ∑ bi y i → max j =1 i =1 Ràng buộc: Dấu của biến: ≥ bi , i ∈ I1 ≥ 0, i ∈ I1 n ∑a x j =1 ij j = bi , i ∈ I2 y i ∈ ℝ, i ∈ I2 ≤ bi , i ∈ I3 ≤ 0, i ∈ I3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 8
Bài toán đối ngẫu QHTT Quy tắc lập bài toán đối ngẫu (tt) Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc) Dấu của biến: Ràng buộc: ≥ 0, j ∈ J1 ≤ c j , j ∈ J1 m x j ∈ ℝ, j ∈ J 2 ∑a y i =1 ij i = c j , j ∈ J2 ≤ 0, j ∈ J3 ≥ c j , j ∈ J3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 9
Bài toán đối ngẫu QHTT Ví dụ 2 Lập bài toán đối ngẫu của bài toán sau f ( x ) = 2 x1 + x2 + 7 x3 → min 3 x1 + 5 x2 − 4 x3 ≥ 1   2 x1 − x2 + 2 x3 = 4 (P )   x1 + 2 x2 + 6 x3 ≤ 8  x ≥ 0, x ≤ 0, x ∈ ℝ  1 2 3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 10
Bài toán đối ngẫu của bài toán trên: g ( y ) = y1 + 4 y 2 + 8 y 3 → max  3 y1 + 2y 2 + y 3 ≤ 2   5 y1 − y 2 + 2 y 3 ≥ 1 (D )   −4 y 1 + 2 y 2 + 6 y 3 = 7  y ≥ 0, y ∈ ℝ, y ≤ 0  1 2 3 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 11
Bài toán đối ngẫu QHTT 2. Định lý đối ngẫu Định lý 1 (Đối ngẫu yếu) Nếu x là PA của (P) và y là PA của (D), thì c1x1 + c2 x2 + ... + cn xn ≥ b1y1 + b2 y 2 + ... + bm y m =f ( x ) =g ( y ) 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 12
Bài toán đối ngẫu QHTT Định lý 2 (đối ngẫu mạnh) Nếu một QH có PATƯ thì QH đối ngẫu của nó cũng có PATƯ và giá trị mục tiêu của chúng là bằng nhau. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 13
Bài toán đối ngẫu QHTT Định lý 3 (Định lý tồn tại) Đối với mỗi cặp bài toán (P) và (D), một trong ba khả năng sau xảy ra: i) Cả (P) và (D) đều không có PA. ii) Cả (P) và (D) đều có PA. Khi đó, chúng sẽ có PATƯ và giá trị mục tiêu là bằng nhau. iii) Một QH có PA còn QH kia thì không. Khi đó, QH có PA sẽ không có PATƯ. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 14
Bài toán đối ngẫu QHTT Định lý 4 (đk độ lệch bù (yếu)) Một cặp PA x, y của (P) và (D) là những PATƯ khi và chỉ khi chúng nghiệm đúng hệ:   n   y i  ∑ aij x j − bi  = 0 ∀i = 1, m (1)   j =1     m   x j  c j − ∑ aij y i  = 0 ∀j = 1, n ( 2)   i =1  20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 15
Phương pháp đơn hình đối ngẫu Là phương pháp đơn hình áp dụng cho bài toán đối ngẫu nhưng để tìm nghiệm cho bài toán gốc và các bước tính toán đều làm trên bài toán gốc. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 16
Phương pháp đơn hình đối ngẫu Thuật toán: 0 Xuất phát từ “giả PA” x (thỏa mãn ràng buộc và dấu hiệu tối ưu ∆ j ≤ 0, ∀ j nhưng chưa thỏa mãn đk x ≥ 0). - Lập bảng đơn hình đối ngẫu với giả PA x 0 . - Kiểm tra: nếu các phần tử trên cột giả PA đều không âm thì dừng thuật toán. Ngược lại, tìm (giả) PA mới: + Chọn biến ra: là biến nằm trên dòng có phần tử âm nhỏ nhất ở cột giả PA. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 17
Phương pháp đơn hình đối ngẫu + Chọn biến vào: lập tỉ số giữa các phần tử ở dòng ước lượng với các phần tử âm ở dòng quay (dòng chứa biến ra), chọn tỉ số nhỏ nhất. Chỉ số tương ứng với tỉ số nhỏ nhất là chỉ số của biến vào. - Lập bảng đơn hình mới, với các số liệu được tính toán giống như thuật toán đơn hình thông thường. - Quay lại bước Kiểm tra. 20/6/2012 MaMH: 501014 Chương 2: Lý thuyết đối ngẫu 18

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.