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 toán đỗi ngẫu (G, D) và thiết lập một số định lý về dấu của chúng.
1. Mở đầu
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 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 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 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à 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à 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 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ề 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 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, 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 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 hơn, đặc biệt tự tin trong quá trình học tập.
2. Nội dung
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 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 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 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 (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 đố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 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 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 ứ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 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 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 cùng chiều hay ngược chiều với kim đồng hồ bằng 1 góc quay 90
Bây giờ chúng ta ký hiệu các ma trận sau:
1 ThS. Khoa Toán, trường ĐH Quảng Nam
98
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.
Định nghĩa quan hệ thứ tự “ f ” như sau:
và
Xét các bài toán Quy Hoạch tuyến tính tổng quát dạng:
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 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.
Các dạng bài toán đối ngẫu sẽ được định nghĩa như sau:
Định nghĩa 1.1: Bài toán đối ngẫu (D1) có dạng
Định nghĩa 1.2: Bài toán đối ngẫu (D2) có dạng
Định nghĩa 1.3: Bài toán đối ngẫu (D3) có dạng
ở đây ký hiệu " >< 0" chỉ rằng y không mang dấu.
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 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 biến x và bài toán “max” sử dụng biến y.
Các mô hình đối ngẫu của cặp bài toán gốc (G), đối ngẫu (D):
A. Mô hình 1: Mô hình đối ngẫu của cặp bài toán (G1, D1)
B. Mô hình 2: Mô hình đối ngẫu của cặp bài toán (G2, D2)
100
C. Mô hình 3: Mô hình đối ngẫu của cặp bài toán
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
" ≥ " 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ì 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à “۸\” 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 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).
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 " ≥ "
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ì 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à “۸\”
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 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).
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
"≥" 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ì 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à “۸\” 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 không mang dấu.
Đị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 thức ghi nhớ như sau:
Đị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 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 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 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 đẳng thức tương ứng với biến đó mang dấu “=”.
Chứng minh:
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
“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ý 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 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 rằng:
Khi dấu của x là " ≥ " thì khi quay ngược kim đồng hồ một góc 90 độ sẽ có
“۸\”. Á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 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 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 đó 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, 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 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 “
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}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ỉ ra được kết quả.
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.
Đị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 đẳ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 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 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ì ràng buộc về biến tương ứng với bất đẳng thức đó không mang dấu.
Chứng minh:
Dễ dàng có được từ chứng minh định lí 1.
Đị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 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 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 từng đẳng thức tương ứng với biến đó mang dấu “=”.
Chứng minh:
Điều này hiển nhiên được suy trực tiếp bằng định nghĩa.
Ứng dụng cho một số bài toán cụ thể:
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”
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 đầ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 các phương pháp trực quan nêu trong các định lí 1,2,3 trên.
1. Xét bài toán Quy hoạch tuyến tính sau
102
Vận dụng định lí 1, ta có mô hình đối ngẫu của bài toán ban đầu là
Từ mô hình trên dễ dàng suy ra mô hình toán học của bài toán đối ngẫu 2. Xét bài toán Quy hoạch tuyến tính sau
Vận dụng định lí 1, ta có mô hình đối ngẫu của bài toán ban đầu là
Từ mô hình trên dễ dàng suy ra mô hình toán học của bài toán đối ngẫu
3. Kết luận: Trên đây là một trong những phương pháp quay dấu một góc trực
quan và cơ bản nhất nhằm trợ giúp cho sinh viên không thuộc chuyên ngành Toán học học phần “Quy hoạch tuyến tính” của các trường đại học và cao đẳng trên cả nước có một cách nhìn nhận trực quan hơn về cặp bài toán đối ngẫu (G, D).
TàI LIỆU THAM KHẢo
[1] Nguyễn Đức Nghĩa (1999), Tối ưu hóa, NXB khoa học kỹ thuật.
[2] Nguyễn Minh Trí (2001), Tối ưu hóa, NXB khoa học kỷ thuật.
[3] Trần Xuân Sinh (1992), Quy hoạch tuyến tính, NXB giáo dục.
[4] Hadlay G (1963), Linear programming, Addison-Wesley.
[5] Karmanov V.G (1989), Mathematical Programming, Mir Publishers, Moscow.
[6] Yudin D.B (1963), Lineinoe programmirovanie, Moskva, Nauka.
[7] Murtagh A.B., Advanced Linear Programming: Computation and Practice.
Title: THE THEoREM ABoUT THE SIGN oF THE DUAL PRoBLEMS TRAN VAN SU Quang Nam University Abstract: The purpose of the paper is to introduce a lot of dual models of the dual pair (G, D) and to establish some theorems on their sign.
