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

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪUCÁCH THÀNH LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU (Xem)CÁC ĐỊNH LÝ ĐỐI NGẪU (Xem)THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU (Xem)MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT (Xem)BÀI TẬP (Xem)CHƯƠNG 2THÀNH LẬP BÀI TOÁN ĐỐI NGẪUMục đích và ý nghĩa Với bài toán QHTT, bài toán gốc, ký hiệu là P (Primal), chúng ta có thể thiết lập bài toán QHTT khác, bài toán đối ngẫu, ký hiệu là D (Dual), sao cho từ lời giải của bài toán này ta có thể thu thập được thông tin về lời giải của bài toán kia. Để có thông tin cần thiết về bài toán gốc, có thể nghiên cứu trên bài toán đối ngẫu của nó. Hơn nữa, khi phân tích đồng thời cả hai bài toán gốc và đối ngẫu, chúng ta có thể rút ra các kết luận có giá trị về mặt toán học lẫn về mặt ý nghĩa kinh tế.THÀNH LẬP BÀI TOÁN ĐỐI NGẪUXét bài toán QHTT (P) dưới dạng chính tắcVới x = (x1, x2,..., xn)n, b = (b1, b2,..., bm)mGiả sử bài toán (P) có P.A.T.U là xopt và gọi x0 là một P.A của bài toán (P), ta có ctxopt ≤ ctx0.Gọi x = (x1, x2,..., xn)n, với x ≥ 0 sao cho Ax – b  0Bài toán tương đương: THÀNH LẬP BÀI TOÁN ĐỐI NGẪUGọi g(y) là hàm mục tiêu của bài toán (II), ta cóg(y) = min{ctx + yt(b – Ax)}, với x ≥ 0. ≤ ctx + yt(b – Ax), với x ≥ 0. Nếu x là P.A của bài toán (I) thì b – Ax = 0 và g(y) ≤ ctx. Vậy g(y) là một cận dưới bất kỳ của hàm mục tiêu. Ta tìm cận dưới lớn nhất Max{g(y)}, thật vậyg(y) = min{ctx + yt(b – Ax)}, với x ≥ 0. = min{ctx + ytb – ytAx}, với x ≥ 0. = min{ytb + (ct – ytA)x}, với x ≥ 0. = ytb + min{ (ct – ytA)x}, với x ≥ 0.THÀNH LẬP BÀI TOÁN ĐỐI NGẪUXét Vậy ta được g(y) = ytb Suy ra bài toán đối ngẫu có dạngHay bài toán tương đươngTHÀNH LẬP BÀI TOÁN ĐỐI NGẪUVí dụ 2.1.Bài toán đối ngẫu của bài toán QHTT sau đâylà bài toánTHÀNH LẬP BÀI TOÁN ĐỐI NGẪUVD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 Baøi toaùn goác (P)Baøi toaùn ñoái ngaãu (D)Haøm muïc tieâuHaøm muïc tieâuRaøng buoäc thöù iRaøng buoäc thöù jAÅn thöù jAÅn thöù iVí dụ 2.2. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Các cặp đối ngẫuTHÀNH LẬP BÀI TOÁN ĐỐI NGẪUBài toán đối ngẫuVí dụ 2.3. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Các cặp đối ngẫuTHÀNH LẬP BÀI TOÁN ĐỐI NGẪUBài toán đối ngẫuVí dụ 2.4. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Bài toán đối ngẫu THÀNH LẬP BÀI TOÁN ĐỐI NGẪUCác ràng buộc đối ngẫuVí dụ 2.5. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT THÀNH LẬP BÀI TOÁN ĐỐI NGẪURàng buộc đối ngẫuBài toán đối ngẫuCÁC ĐỊNH LÝ ĐỐI NGẪUĐỊNH LÝ 1.Nếu một trong hai bài toán đối ngẫu nhau có P.A.T.Ư thì bài toán kia cũng có P.A.T.Ư và giá trị hàm mục tiêu của chúng bằng nhau. HỆ QUẢ 1.Điều kiện cần và đủ để cho các bài toán đối ngẫu nhau có phương án tối ưu là mỗi bài toán có ít nhất một phương án. HỆ QUẢ 2.Điều kiện cần và đủ để cho các bài toán đối ngẫu nhau không có P.A.T.Ư là một bài toán có P.A còn bài toán kia không có P.A.CÁC ĐỊNH LÝ ĐỐI NGẪUĐỊNH LÝ 2.(ĐỊNH LÝ ĐỘ LỆCH BÙ YẾU)Điều kiện cần và đủ để cặp bài toán đối ngẫu nhau có P.A.T.Ư. là trong cặp ràng buộc đối ngẫu, nếu ràng buộc này xảy ra với dấu bất đẳng thức ngặt (“>” hoặc “ 0 thì Nếu thì yiopt = 0CÁC ĐỊNH LÝ ĐỐI NGẪUĐỊNH LÝ 3.(ĐỊNH LÝ ĐỘ LỆCH BÙ MẠNH)Nếu cặp bài toán đối ngẫu nhau có P.A.T.Ư. thì tồn tại một cặp phương án sao cho trong các cặp đối ngẫu, nếu ràng buộc này xảy ra với dấu đẳng thức thì ràng buộc kia xảy ra với dấu bất đẳng thức ngặt.Nghĩa là, với Xopt = (x1opt, x2opt, ..., xnopt), Yopt = (y1opt, y2opt, ..., ymopt) lần lượt là P.A.T.Ư. của bài toán gốc và bài toán đối ngẫu, ta có Nếu xjopt = 0 thì tồn tại Nếu thì tồn tại yiopt  0 (> hoặc 0  y1 = 2.Từ (3): x3= 6 > 0  y1 + y2 + 3y3 = 1Từ (4): x4= 5 > 0  6y1 + 2y2 + y3 = 4 Giải hệ phương trình trên, ta có y1 = 2; y2 = -23/5; y3 = 6/5. Vậy, P.A.T.Ư của bài toán đối ngẫu làyopt= (2, -23/5, 6/5) và fD(yopt) = 54.ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪUVí dụ 2.8. Cho bài toán QHTT Xét các vectơ sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), Z = (-4, 2, 0, 10) và T = (1, 2, 1, 2). Vectơ nào là P.A.T.Ư. của bài toán?Cách giải. Kiểm tra các vectơ có phải là P.A hay không? Viết bài toán đối ngẫu, Kiểm tra các P.A có phải là P.A.T.Ư.?ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Kiểm tra trực tiếp, ta thấy X, Y, và T là P.A của bài toán. Vì Z không thỏa mãn các ràng buộc nên Z không là P.A của bài toán. Bài toán đối ngẫu Ta có 7 cặp ràng buộc đối ngẫuÁP DỤNG ĐỊNH LÝ ĐỐI NGẪUx1 ≥ 0 và y1 + y2 – 3y3 ≥ -1 (1)x2 ≥ 0 và 3y1 + y2 ≥ 2 (2)x3 ≥ 0 và y3 ≥ 1 (3)x4 ≥ 0 và – y1 + y3 ≥ 0 (4) x1 + 3x2 – x4 ≤ 5 và y1 ≥ 0 (5) x1 + x2 ≤ 3 và y2 ≥ 0 (6)-3x1 + x3 + x4 ≤ 2 và y3 ≥ 0 (7) Kiểm tra X, Y, T là P.A.T.Ư Giả sử X = (3, 0, 11, 0) là P.A.T.Ư của bài toán.Từ (1): x1 = 3 > 0  y1 + y2 – 3y3 = -1Từ (3): x3=11 > 0  y3 = 1Từ (5): 3 + 0 + 0 + 0 = 3 0  2x1 + x2 + x3 = 6Từ (6): y3= 2 > 0  x1 + 2x2 + 5x3 = 5Giải hệ phương trình, ta có PA.T.Ư của bài toán gốc là xopt = (7/3, 4/3, 0) và f(xopt) = 34.ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪUGHI CHÚ. Chúng ta cũng có thể sử dụng quy tắc sau đây để tìm P.A.T.Ư của bài toán đối ngẫu:Với các ẩn cơ bản xj (j = 1, 2, ..., m) trong P.A.C.B đầu tiên lập thành ma trận đơn vị cấp m tương ứng với các j trong bảng cuối cùng.Trong Ví dụ 2.9, ẩn cơ bản đầu tiên của bài toán đối ngẫu là y4, y5 và y6 thì P.A.T.Ư của bài toán gốc (đối ngẫu của bài toán đối ngẫu) làXopt = (7/3, 4/3, 0) và f(Xopt) = 34.ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Do Lemke G.E đề xuất năm 1954. Đây là thuật giải đơn hình được áp dụng vào bài toán đối ngẫu nhưng để tìm P.A.T.Ư cho bài toán gốc. Thuật giải đơn hình đối ngẫu xuất phát từ một “phương án giả” thỏa các ràng buộc chính của bài toán (nghiệm đúng Ax = b) nhưng không thoả điều kiện ràng buộc về dấu (x  0), nghĩa là bảng đơn hình đầu tiên không có phần tử dương trong dòng mục tiêu (dòng cuối) nhưng lại có phần tử âm trong cột phương án. Thuật giải này thường được áp dụng khi chưa biết P.A.C.B nào của bài toán gốc nhưng lại có sẵn một P.A.C.B của bài toán đối ngẫu.THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUĐúngbi ≥ 0,i?THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUSaiĐúngSaiĐúngLẬP BẢNG ĐƠN HÌNH ĐỐI NGẪUXÁC ĐỊNH PHƯƠNG ÁN MỚIAån ra : Aån vào : P.A.T.ƯKẾT THÚC THUẬT GIẢIaij  0,i?BÀI TOÁN KHÔNG CÓ P.A.T.ƯBIẾN ĐỔI BẢNG ĐƠN HÌNHSỐ BƯỚC LẶP LÀ HỮU HẠNj ≤ 0,j?SaiTHUẬT GIẢI ĐƠN HÌNHVí dụ 2.10. Giải bài toán QHTT trong Ví dụ 2.9 bằng thuật giải đơn hình đối ngẫu.Đưa bài toán về dạng chính tắc, rồi sau đó nhân (–1) cho các ràng buộc đẳng thức, ta có bài toán dạng chính tắc như sauXuất phát từ phương án giả X = (0,0,0,–6,–2,–5). Ta có bảng đơn hình đối ngẫu như sauTHUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUTHUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU10x131½ ½–½000x5703/2–½ –3/2 100x6–20–3/29/2–½ 01f(x)300–3–14–500Heä soáAÅn C.BP.A10819000x1x2x3x4x5x60x4–6–2–1–11000x5–2–3 0–20100x6–5–1–2–5001f(x)0–10–8–19000Vậy, P.A.T.Ư của bài toán là xopt = (7/3, 4/3, 0) và f(xopt) = 34.THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUHeä soáAÅn C.BP.A10819000x1x2x3x4x5x610x17/3102–2/301/30x55004–2118x34/301 –31/30–2/3f(x)3400–23–40–2GHI CHÚ. Đối với thuật giải đơn hình đối ngẫu, để tìm P.A.T.Ư của bài toán đối ngẫu Yopt, ta có biểu thức sauTrong Ví dụ 2.10, ẩn cơ bản đầu tiên của bài toán đối ngẫu là x4, x5 và x6 thì P.A.T.Ư của bài toán đối ngẫu là Yopt = (4, 0, 2) và f*(Yopt) = 34.THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUVí dụ 2.11.Dùng thuật giải đơn hình đối ngẫu để giải bài toán quy hoạch tuyến tính sau đâyXuất phát từ phương án giả X=(-2, 0, 0, -4, 0, 2,6) Ta có bảng đơn hình đối ngẫuTHUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUTHUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪUHeä soáAÅn C.BP.A2–41–1200x1x2x3x4x5x6x72x1–21–200–200–1x4–40411–1000x620 020–1100x760110401f(x)00–4–20–5002x161–10–2–20002x540–4–1–11000x660–41–10100x7–1001754001f(x)200–24–7–5000Do a4j  0, j = 1,..., 7 nên bài toán trên không có P.A.T.Ư. TÌM PHƯƠNG ÁN TỐI ƯU MỚI KHI CÓ THÊM RÀNG BUỘC VÀO BÀI TOÁN (XEM) TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH BẰNG THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG (XEM) Ý NGHĨA KINH TẾ CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU (XEM)MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTTVí dụ 2.12.a) Dùng thuật giải đơn hình đối ngẫu để giải bài toán quy hoạch tuyến tính sau đâyb) Nếu thêm một ràng buộc nữa x1 + x2 + x3  60 vào bài toán trên, tìm phương án tối ưu của bài toán mới.MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTTĐưa bài toán về dạng chính tắc, rồi sau đó nhân (–1) cho các ràng buộc đẳng thức, ta có bài toán dạng chính tắc như saua) Xuất phát từ phương án giả X = (0, 0, 0, –160, –140). Ta có bảng đơn hình đối ngẫuMỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTTMỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪU12x240¾1½–¼00x5–60½0–2–½1f(x)480–60–4–3012x2257/810–3/8¼10x330–¼01¼–½ f(x)600–700–2–2P.A.T.Ư là xopt = (0, 25, 30) và f(xopt) = 600.Heä SoáAÅn C.BP.A15121000x1x2x3x4x50x4–160–3–4–2100x5–140–1–2–301f(x)0–15–12–1000b) Do xopt = (0, 25, 30) không thỏa ràng buộc x1 + x2 + x3  60 nên xopt không phải là phương án của bài toán mới. Để xử lý ràng buộc mới này, ta đưa ràng buộc bất đẳng thức về ràng buộc đẳng thức bằng cách thêm ẩn phụ x6  0, ta được –x1 – x2 – x3 + x6 = –60. Sử dụng bảng cuối cùng trong câu a) và đưa ràng buộc mới –x1 – x2 – x3 + x6 = –60 vào bảng trên. Lưu ý ẩn x6 là ẩn cơ bản trong bài toán mới, còn x4 và x5 là ẩn cơ bản trong bài toán cũ nên trong ma trận hệ số của bài toán mới ta cộng dòng 1 và dòng 2 vào dòng 3 để vectơ cột ứng với x4 và x5 là các vectơ đơn vị.MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTTMỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪU12x2257/810–3/8¼010x330–¼01¼–½ 00x6–5–3/800–1/8–¼1f(x)600–700–2–20Heä soáAÅn C.BP.A151210000x1x2x3x4x5x612x2257/810–3/8¼010x330–¼01¼–½ 00x6–60–1–1–1001f(x)600–700–2–20MỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪUP.A.T.Ư là x/opt = (0, 20, 40) và f(x/opt) = 640.Heä soáAÅn C.BP.A151210000x1x2x3x4x5x612x220½10–½0110x340½01½0–20x5203/2 00½1–4f(x)640–400–10–8Tìm nghiệm không âm của hệ phương trình tuyến tính AX = b, X  0 (1), trong đó A là ma trận mn, bm có thể quy về giải bài toán quy hoạch tuyến tính Bài toán (2) luôn luôn có P.A.T.Ư vì (0,b) là một P.A và hàm mục tiêu bị chặn [f(x)  0]. Giả sử P.A.T.Ư của bài toán trên là (xopt, xgopt), nếu xgopt = 0, j thì xopt là nghiệm của bài toán (1). Ngược lại nếu tồn tại xgj  0 thì bài toán (1) vô nghiệm.TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNHVí dụ 2.1.Tìm nghiệm không âm của hệ phương trình tuyến tínhTa có thể quy bài toán trên về bài toán QHTT Giải bài toán trên, ta được P.A.T.Ư là (xopt, xgopt) = (3, 1, 2, 0, 0, 0). Vậy nghiệm không âm của hệ phương trình tuyến tính trên là x = (3, 1, 2).TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNHXét bài toán gốc là bài toán khẩu phần thức ănChaát dinh döôõng (%)Thöùc aênMöùc dinh döôõng toái thieåu12...j...n1a11a12...a1j...a1nb12a21a22...a2j...a2nb2........................iai1ai2...aij...ainbi........................mam1am2...amj...amnbmGiaù moät ñôn vò thöùc aênc1c2...cj...cnÝ NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪUGọi xj (j = 1, 2, ..., n) là số đơn vị thức ăn trong mỗi bửa, ta có mô hình bài toán QHTT như sauBài toán đối ngẫu Chất dinh dưỡng thay thế: nhà sản xuất thuốc bổ tương ứng với các chất dinh dưỡng trên.Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪUGọi yi là giá bán một viên thuốc bổ có chứa chất dinh dưỡng i (i = 1, 2, ..., m). Người chăn nuôi sẽ phải lựa chọn: Mua thuốc bổ, nếu a1jy1 + a2jy2 +... + anjyn 0 thì ai1x1 + ai2x2 + + ainxn = bi, Nghĩa là, nếu giá một viên thuốc bổ khá cao thì người chăn nuôi sẽ mua các loại thức ăn sao cho thoả nhu cầu tối thiểu của chất dinh dưỡng.Vậy, khi phân tích cặp bài toán đối ngẫu nhau chính là phân tích tính T.Ư của từng bài toán.Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪUBÀI TẬP CHƯƠNG 2LẬP BÀI TOÁN ĐỐI NGẪU[1a] [1b] [2]SỬ DỤNG ĐỊNH LÝ ĐỐI NGẪU[3] [4] [5] [6]PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU[7a] [7b]