tailieunhanh - Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu

Chương 2 bài giảng môn Tối ưu hóa do ThS. Nguyễn Công Trí biên soạn cung cấp cung cấp cho người học các kiến thức về cách thành lập bài toán quy hoạch tuyến tính đối ngẫu, các định lý đối ngẫu, giải thuật đơn hình đối ngẫu,. Cuối mỗi chương có bài tập và lời giải chi tiết. | CHƯƠNG 2 BÀI TOÁN ĐÔÌ NGẪU Ths. Nguyễn Công Trí bcoToũn-ĩnóngKê BAI TOÁN QUY HOẠCH TUYEN TÍNH ĐỐI NGAU CHƯƠNG 2 s 1. CÁCH THÁNH LÁP BÁI TOÁN QUY HOẠCH TUYÊNTÍNH ĐỐI NGÁU Con g Xem 2. CÁC ĐỊNH LY đối NGÁU Xem 3. THUÁT GIÁI ĐƠN HÌNH ĐỐI NGÁU Xem 4. MỐT SỐ ƯNG DUNG cUá lY THUYET ĐỐI NGÁU TRONG BÁI TOÁN QHTT Xem B M M LiBhsiJMHByenBoHBiiM 5. BÁI TÁP Copy ghj 20 Xem THÁNH LÁP BÁI TOÁN ĐỐI NGÁU Muc đích va y nghía Với bai toan QHTT bài toán gốc ky hiệu la P Primal chung ta co the thiet lập bai toan QHTT khác bài toán đối ngầu ky hiẹu la D Dual sao cho từlới giai cua bai toan nay ta co thê thu thặp đước thong tin ve lới giải cua bai toan kia. Đẽ co thong tin can thiết ve bai toan goc co the nghien cưu tren bai toan đối ngau cua no. Hớn nưa khi phan tích đong thới ca hai bai toan gốc va đối ngau chung ta co the rut ra cac ket luân co gia trị ve mat toan hoc lan ve mặt y nghía kinh te. THÁNH LÁP BÁI TOÁN ĐỐI NGÁU Xet bai toan QHTT P dưới dang chính tac p fp x clx min Ax b I x 0. Với x X1 eỉRn b bi b2 bmMTm Gia sử bai toan P co la xopt va goi X0 la một cua bai toan P ta co cxopt ctx0. Goi x x1 x2 xn s Rn với x 0 sao cho Áx - b 0 Bai toan tướng đướng L x y c x y b-Ax j min P x 0 II yeRm. THÁNH LÁP BÁI TOÁN ĐỐI NGÁU Goi g y la ham muc tieu cua bai toan II ta co g y min ctx yt b - Áx với x 0. ctx yt b - Áx với x 0. Neu x la cua bai toan I thì b - Áx 0 va g y ctx. Vạy g y la mot cạn dưới bat ky cua ham muc tieu. Ta tìm can dưới lớn nhat Max g y that vay g y min ctx yt b - Áx với x 0. min ctx ytb - ytÁx với x 0. min ytb ct - ytÁ x với x 0. ytb min ct - ytÁ x với x 0. THÁNH LÁP BÁI TOÁN ĐỐI NGÁU xet .í . J_ro khi c y. 0 mini c - y A xj x0 -co khi cl - y A 0 Vay ta đước ___v g y ytb Suy ra bai toan đối ngau co dang D g y ýb max c -ýA ũ ytR . g .y ýb - max ýA c yeRm. Hay bai toan tướng đướng D g y ýb - max Ay c THÁNH LÁP BÁI TOÁN ĐỐI NGÁU Ví du . Bai to an đối ngau cua bai toan QHTT sau đay f x 2xi 8a 4 6jc5 min 2x1 Xj x5 4 2x2 x5 4 x2 2Xj 3x4 13 x7 0 y 1T5