Tính đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng

Bài viết xây dựng và nghiên cứu một mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng. Đầu tiên chúng đề xuất mô hình đối ngẫu dạng Wolfe và cung cấp một ví dụ để minh họa cho mô hình đối ngẫu. Thứ hai, chúng tôi thiết lập các định lí về tính đối ngẫu mạnh và tính đối ngẫu yếu cho cặp bài toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe (DWLOPEC).
Nội dung trích xuất từ tài liệu:
Tính đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằngUED Journal of Social Sciences, Humanities & Education – ISSN 1859 - 4603 TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC TÍNH ĐỐI NGẪU DẠNG WOLFE CHO BÀI TOÁN TỐI ƯU TUYẾN TÍNH VỚI RÀNG BUỘC CÂN BẰNG Nhận bài: 15 – 10 – 2018 Trần Văn Sựa*, Lê Xuân Hòab Chấp nhận đăng: 25 – 12 – 2018 Tóm tắt: Đối ngẫu có vai trò quan trọng trong nghiên cứu các bài toán quy hoạch toán học vì tính đối http://jshe.ued.udn.vn/ ngẫu yếu cung cấp một chặn dưới đối với hàm mục tiêu của bài toán ban đầu (hay bài toán gốc). Trong bài báo này chúng tôi xây dựng và nghiên cứu một mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng. Đầu tiên chúng đề xuất mô hình đối ngẫu dạng Wolfe và cung cấp một ví dụ để minh họa cho mô hình đối ngẫu. Thứ hai, chúng tôi thiết lập các định lí về tính đối ngẫu mạnh và tính đối ngẫu yếu cho cặp bài toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe (DWLOPEC). Cuối cùng chúng tôi trình bày một ví dụ để mô tả kết quả về tính đối ngẫu mạnh trong giấy. Từ khóa: bài toán tối ưu tuyến tính với ràng buộc cân bằng; đối ngẫu dạng Wolfe; định lí đối ngẫu mạnh; định lí đối ngẫu yếu; ánh xạ tuyến tính. bài toán đối ngẫu “max”. Ma trận ràng buộc bài toán1. Giới thiệu gốc “min” được chuyển thành ma trận chuyển vị của Đối ngẫu là một chủ đề quan trọng trong nghiên cứu bài toán đối ngẫu “max” và ngược lại. Tuy nhiên, môcác bài toán quy hoạch toán học, chẳng hạn tính đối hình đối ngẫu trên lại không phù hợp với lớp bài toánngẫu yếu cung cấp giá trị chặn dưới cho hàm mục tiêu. tối ưu tuyến tính với ràng buộc cân bằng. Đối với môTương tự như trong bài toán quy hoạch tuyến tính tổng hình đối ngẫu dạng Wolfe (xem Wolfe [4]), tính đốiquát, khi thiết lập một mô hình đối ngẫu cho bài toán ngẫu giữa các biến không xảy ra, đây là vấn đề thuậnban đầu (hay còn gọi là bài toán gốc), các định lí về tính lợi để xây dựng các thuật toán với thời gian chạyđối ngẫu yếu và tính đối ngẫu mạnh cho cặp bài toán gốc chương trình nhanh hơn.và bài toán đối ngẫu luôn giữ một vai trò chủ đạo và Gần đây, thông qua các tài liệu trình bày về môthường được nghiên cứu trước tiên, xem, chẳng hạn [1, hình đối ngẫu dạng Wolfe (xem [1,2,3,4,5]), ta thấy2, 3, 4, 5]. rằng khi xây dựng một mô hình đối ngẫu dạng Wolfe Trong bài toán quy hoạch tuyến tính tổng quát, cần công cụ là các đạo hàm theo hướng và dưới vi phântính đối ngẫu được thiết lập phụ thuộc vào biến và dấu, phù hợp để thiết lập mô hình đối ngẫu cũng như cácnghĩa là bài toán gốc chọn biến x, bài toán đối ngẫu định lí đối ngẫu mạnh và yếu. Tuy nhiên đối với cácchọn biến y, dấu của y phụ thuộc vào ràng buộc đẳng hàm tuyến tính, đạo hàm theo hướng đạt được ngay tạithức hay bất đẳng thức của bài toán gốc và ngược lại. phương lấy đạo hàm. Do đó, chúng ta không cần sửCác hệ số của hàm mục tiêu của bài toán gốc được lấy dụng một công cụ đạo hàm nào hay dạng dưới vi phầnlàm chặn trên của bài toán đối ngẫu “max” và chặn nào áp đặt lên bài toán đối ngẫu dạng Wolfe, mà có thểdưới của bài toán gốc “min” được chọn làm hệ số của xây dựng trực tiếp mô hình đối ngẫu dạng Wolfe như trong bài toán quy hoạch tuyến tính tổng quát.aTrường Đại học Quảng Nam Mục đích của chúng tôi trong bài báo này là đềbTrường Đại học Kiến trúc Đà Nẵng xuất mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu* Tác giả liên hệTrần Văn Sự tuyến tính với ràng buộc cân bằng. Tiếp theo chúng tôiEmail: tranuu63@gmail.com Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 8, số 4 (2018), 27-33 | 27Trần Văn Sự, Lê Xuân Hòanghiên cứu các định lí về tính đối ngẫu mạnh và về tính Chúng ta xét bài toán bài toán tối ưu tuyến tính vớiđối ngẫu yếu của cặp bài toán gốc và bài toán đối ...