Định lý về dấu của bài toán đối ngẫu

ĐỊNH LÝ VỀ DẤU CỦA BÀI TOÁN ĐỐI NGẪU<br /> Trần Văn Sự1<br /> Tóm tắt: Mục đích của bài báo là giới thiệu một số mô hình đối ngẫu của cặp bài<br /> toán đỗi ngẫu (G, D) và thiết lập một số định lý về dấu của chúng.<br /> 1. Mở đầu<br /> Hiện nay các vấn đề về lý thuyết đối ngẫu của các dạng bài toán quy hoạch tuyến<br /> tính cho sinh viên các ngành kinh tế kỹ thuật nói chung mà nhiều giáo trình viết dưới<br /> hình thức rập khuôn, chưa chỉ rõ ràng từng dạng đối ngẫu bằng mô hình cụ thể và hơn<br /> nữa, trong quá trình dạy học, một số vấn đề hiện nay mà sinh viên hay mắc phải là<br /> không tự tin trong khi chuyển đổi bài toán dạng “min” sang bài toán dạng “max” và<br /> ngược lại, một lỗi lớn nhất và dẫn đến một chuyển đổi sai lệch bài toán gốc sang bài<br /> toán đối ngẫu, đó là không xác định rõ ràng dấu của từng biến và từng ràng buộc về<br /> dấu của bài toán gốc và bài toán đối ngẫu tương ứng. Bài báo này theo trình tự đưa ra<br /> cụ thể từng mô hình đối ngẫu bằng sơ đồ đối ngẫu, định lý về dấu cho cặp bài toán gốc,<br /> bài toán đối ngẫu. Hi vọng bài báo này sẽ giúp sinh viên các ngành không chuyên toán<br /> của các trường đại học và cao đẳng sẽ nắm bắt vấn đề một cách hiệu quả, dễ dàng, sâu<br /> hơn, đặc biệt tự tin trong quá trình học tập.<br /> 2. Nội dung<br /> Một bài toán Quy Hoạch tuyến tính dạng tổng quát thường mang nhiều dấu ở các<br /> ràng buộc biến và ràng buộc bất phương trình. Vì vậy, khi chuyển sang đối ngẫu của<br /> chúng sẽ mang nhiều dấu cho ràng buộc biến và ràng buộc bất phương trình. Chúng ta<br /> biết rằng đối ngẫu của bài toán gốc (G) là bài toán (D), và đối ngẫu của bài toán gốc<br /> (D) lại là bài toán (G). Vì vậy các bài toán “max” chúng ta cũng phải xác định dạng<br /> đối ngẫu của chúng mà trong đó các ràng buộc của chúng mang nhiều dấu, vì vậy, bài<br /> toán đối ngẫu “min” tương ứng cũng sẽ có nhiều dấu cho các biến và các ràng buộc<br /> bất đẳng thức. Chính vì vậy, việc xác định dấu chính xác cho bài toán đối ngẫu tương<br /> ứng cũng là một nhiệm vụ cũng có thể xem là khó khăn cho các sinh viên ngành Kinh<br /> tế kỹ thuật. Chính vì lẽ đó chúng ta cần phải thiết lập một quy tắc dấu tương ứng cho<br /> cặp bài toán (G, D). Trong bài báo này, quy tắc dấu được thiết lập dựa vào cách quay<br /> cùng chiều hay ngược chiều với kim đồng hồ bằng 1 góc quay 90<br /> Bây giờ chúng ta ký hiệu các ma trận sau:<br /> <br />   ThS. Khoa Toán, trường ĐH Quảng Nam<br /> <br /> 1<br /> <br /> 97<br /> <br /> ĐỊNH LÝ VỀ DẤU CỦA BÀI TOÁN ĐỐI NGẪU.<br /> với θt là ma trận gồm t hàng, 1 cột và X T là ma trận chuyển vị của ma trận X.<br /> Định nghĩa quan hệ thứ tự “ f ” như sau:<br /> <br /> và<br /> <br /> Xét các bài toán Quy Hoạch tuyến tính tổng quát dạng:<br /> <br /> Ba bài toán trên được gọi theo thứ tự là bài toán gốc (G1) (G2) (G3). Bài toán đối<br /> ngẫu của các bài toán (Gi), i = 1, 2, 3 theo thứ tự ký hiệu bởi (Di), i = 1, 2, 3.<br /> Các dạng bài toán đối ngẫu sẽ được định nghĩa như sau:<br /> Định nghĩa 1.1: Bài toán đối ngẫu (D1) có dạng<br /> <br /> Định nghĩa 1.2: Bài toán đối ngẫu (D2) có dạng<br /> <br /> Định nghĩa 1.3:<br /> <br /> Bài toán đối ngẫu (D3) có dạng<br /> <br /> ở đây ký hiệu " >< 0" chỉ rằng y không mang dấu.<br /> 98<br /> <br /> Trần Văn Sự<br /> Ký hiệu (G, D) hiểu rằng (G) là bài toán gốc và (D) là bài toán đối ngẫu của bài<br /> toán gốc (G). Hơn nữa, khi xem xét một cặp (G, D) ta quy ước bài toán “min” sử dụng<br /> biến x và bài toán “max” sử dụng biến y.<br /> Các mô hình đối ngẫu của cặp bài toán gốc (G), đối ngẫu (D):<br /> A. Mô hình 1: Mô hình đối ngẫu của cặp bài toán (G1, D1)<br /> <br /> B. Mô hình 2:<br /> <br /> Mô hình đối ngẫu của cặp bài toán (G2, D2)<br /> <br /> 99<br /> <br /> ĐỊNH LÝ VỀ DẤU CỦA BÀI TOÁN ĐỐI NGẪU.<br /> C. Mô hình 3: Mô hình đối ngẫu của cặp bài toán<br /> <br /> Nhận xét 1: Đối với bài toán đối ngẫu (D1) dạng “max” khi quay tất cả các dấu<br /> " ≥ " của tất cả các biến ràng buộc x tại chỗ một góc 900 theo chiều ngược kim đồng<br /> hồ thì chúng ta được đồng loạt dấu của ràng buộc bất đẳng thức tương ứng với biến x<br /> là “۸\” của bài toán đối ngẫu (D1). Đối với bài toán gốc (G1) dạng “min” thì dấu của y<br /> cùng chiều với dấu của các ràng buộc bất đẳng thức của bài toán gốc (G1).<br /> Nhận xét 2: Đối với bài toán đối ngẫu (D2) dạng “max” khi quay tất cả dấu " ≥ "<br /> của tất cả các biến ràng buộc x tại chỗ một góc 900 theo chiều ngược kim đồng hồ thì<br /> chúng ta được đồng loạt dấu của ràng buộc bất đẳng thức tương ứng với biến x là “۸\”<br /> của bài toán đối ngẫu (D2). Đối với bài toán gốc (G2) dạng “min” thì dấu của y cùng<br /> chiều với dấu của các ràng buộc bất đẳng thức của bài toán gốc (G2).<br /> Nhận xét 3: Đối với bài toán đối ngẫu (D3) dạng “max” khi quay tất cả dấu<br /> "≥" của tất cả các biến ràng buộc x tại chỗ một góc 900 theo chiều ngược kim đồng<br /> hồ thì chúng ta được đồng loạt dấu của ràng buộc bất đẳng thức tương ứng với biến<br /> x là “۸\” của bài toán đối ngẫu (D3). Đối với bài toán gốc (G3) dạng “min” thì y<br /> không mang dấu.<br /> Định lý về dấu của cặp bài toán gốc - đối ngẫu (G, D) được phát biểu dưới hình<br /> thức ghi nhớ như sau:<br /> Định lý 1: Cho trước cặp bài toán đối ngẫu (G, D). Khi đó dấu của các ràng buộc<br /> về biến của bài toán dạng “min” nếu mang dấu thì khi quay tại chỗ và quay ngược<br /> chiều kim đồng hồ một góc 900 sẽ có dấu trùng với dấu của ràng buộc bất đẳng thức<br /> tương ứng với biến đó, trường hợp ràng buộc biến không mang dấu thì ràng buộc bất<br /> đẳng thức tương ứng với biến đó mang dấu “=”.<br /> 100<br /> <br /> Trần Văn Sự<br /> Chứng minh:<br /> Trong chứng minh này, chúng ta cần chú ý rằng biến x được sử dụng cho bài toán<br /> “min” và biến y được sử dụng cho bài toán “max”. Trong phát biểu tất cả các định lý<br /> thuật ngữ “khi quay tại chỗ” ta hiểu là quay dấu của tất cả các ràng buộc bất đẳng thức<br /> và quay dấu của tất cả các ràng buộc biến xác định x. Chúng ta dễ dàng thấy điều sau<br /> rằng:<br /> Khi dấu của x là " ≥ " thì khi quay ngược kim đồng hồ một góc 90 độ sẽ có<br /> “۸\”. Áp dụng định nghĩa đối ngẫu cho bài toán gốc là bài toán “min”, biến ràng<br /> buộc xj ≥ 0, j ∈ {1,2,...,n} thì ràng buộc bất phương trình mang dấu " ≤ ", nên theo<br /> cách thiết lập sơ đồ đối ngẫu ở trên ràng buộc bất đẳng thức tương ứng với biến đó<br /> sẽ mang dấu “۸\”. Trường hợp bài toán gốc là bài toán “min”, biến ràng buộc xj ≤0,<br /> j ∈ {1,2,...,n} thì ràng buộc bất phương trình mang dấu " ≥ ", nên theo cách thiết lập<br /> sơ đồ đối ngẫu ở trên ràng buộc bất đẳng thức tương ứng với biến đó sẽ mang dấu “<br /> v/ ”. Trường hợp bài toán gốc là bài toán “min”, biến ràng buộc xj >< 0, j ∈ {1,2,...,n}<br /> thì ràng buộc bất phương trình mang dấu “=”, nên áp dụng ký hiệu trên dễ dàng chỉ<br /> ra được kết quả.<br /> Trường hợp bài toán gốc là bài toán “max” thì không cần phải chứng minh.<br /> Định lí 2: Cho trước cặp bài toán đối ngẫu (G, D). Khi đó dấu của ràng buộc bất<br /> đẳng thức của bài toán dạng “max” nếu mang dấu thì khi quay tại chỗ và quay cùng<br /> chiều kim đồng hồ một góc 900 sẽ có dấu trùng với dấu của các ràng buộc về biến<br /> tương ứng với bất đẳng thức đó, trường hợp ràng buộc bất đẳng thức mang dấu “=” thì<br /> ràng buộc về biến tương ứng với bất đẳng thức đó không mang dấu.<br /> Chứng minh:<br /> Dễ dàng có được từ chứng minh định lí 1.<br /> Định lý 3: Cho trước cặp bài toán đối ngẫu (G, D). Khi đó dấu của các ràng buộc<br /> về biến của bài toán dạng “max” cùng dấu với ràng buộc về dấu của bất đẳng thức<br /> tương ứng với biến đó, riêng các ràng buộc về từng biến không mang dấu thì ràng buộc<br /> từng đẳng thức tương ứng với biến đó mang dấu “=”.<br /> Chứng minh:<br /> Điều này hiển nhiên được suy trực tiếp bằng định nghĩa.<br /> Ứng dụng cho một số bài toán cụ thể:<br /> Trong phần này chúng tôi đề xuất chuyển đổi mô hình ban đầu là bài toán “min”<br /> chuyển sang mô hình bài toán đối ngẫu là bài toán “max” và ngược lại, mô hình ban<br /> đầu là bài toán “max” chuyển sang mô hình đối ngẫu là bài toán “min” bằng một trong<br /> các phương pháp trực quan nêu trong các định lí 1,2,3 trên.<br /> 1. Xét bài toán Quy hoạch tuyến tính sau<br /> 101<br /> <br />