Bài giảng Toán kinh tế: Phần 2 - Trường CĐ Cộng đồng Đồng Tháp

Bài giảng Toán kinh tế được biên soạn theo đề cương môn học đã được hội đồng khoa học trường thông qua với 30 tiết bao gồm các chương sau: Một số khái niệm cơ bản trong đại số tuyến tính; Bài toán quy hoạch tuyến tính; Phương pháp đơn hình; Bài toán đối ngẫu; Bài toán vận tải. Bài toán thế vị. Mời các bạn cùng tham khảo nội dung phần 2 giáo trình!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán kinh tế: Phần 2 - Trường CĐ Cộng đồng Đồng Tháp Chương 3 BÀI TOÁN ĐỐI NGẪU  Mục đích yêu cầu Ở chương 2, ta đã xét bài toán quy hoạch tuyến tính min-max như là hai bài toán tách biệt. Nhưng thật sự đối với mỗi bài toán min luôn luôn tồn tại bài toán max tương ứng và ngược lại. Bài toán quy hoạch ban đầu được gọi là bài toán gốc còn bài toán tương ứng của nó được gọi là bài toán đối ngẫu. Trong nhiều trường hợp, nhờ Lý thuyết đối ngẫu mà các vấn đề phức tạp trong khi giải bài toán gốc sẽ trở nên đơn giản và dễ dàng hơn thông qua giải bài toán đối ngẫu của nó. Ta sẽ luôn tìm được phương án tối ưu của bài toán đối ngẫu từ phương án của bài toán gốc và ngược lại. Mục tiêu của chương là: - Giúp ta hiểu rõ về bài toán đối ngẫu, ý nghĩa kinh tế của bài toán đối ngẫu, sự cần thiết phải đưa về bài toán đối ngẫu. - Xét mối quan hệ giữa bài toán gốc và bài toán đối ngẫu từ đó có những phương pháp tìm ra phương án tối ưu nhanh hơn.  Kiến thức chuẩn bị Để học tốt chương sinh viên cần: nắm vững các chương trước và thành thạo các phép tính. - 56 - 3.1 Khái niệm 3.1.1 Bài toán đối ngẫu của bài toán dạng chính tắc Định nghĩa: Cho bài toán gốc (P): n f ( x ) = ∑ c j x j → min (max) (3.1.1) j =1 n ∑a j =1 ij x j = bi i = 1, m (3.1.2) x j ≥ 0, j = 1, n (3.1.3) Bài toán (D) sau đây được gọi là bài toán đối ngẫu của nó: m g ( y ) = ∑ bi yi → max ( min) (3.1.4) i =1 m ∑a i =1 ij yi ≤ (≥ ) c j ( j = 1, n ) (3.1.5) y i tùy ý dấu ( i = 1, m ) (3.1.6)  Nhận xét - Hàm mục tiêu của (P) f ( x ) → min thì hàm mục tiêu của (D) g ( y ) → m ax và ngược lại. - Các ràng buộc ở bài toán (D) đều là bất đẳng thức ≤ nếu f ( x ) → m ax (hoặc ≥ nếu f ( x ) → min ) - Số ẩn của bài toán này là số ràng buộc của bài toán kia và ngược lại. - Các hệ số cj và các số hạng tự do bi ở hai bài toán đối ngược nhau. - Ma trận hệ số các ràng buộc ở hai bài toán là chuyển vị của nhau. Hàng i n trong ma trận A = (aij ) mxn xác định ràng buộc thứ i của bài toán gốc ∑a x j =1 ij j = bi , còn cột j trong ma trận A xác định ràng buộc thứ j của bài toán đối ngẫu: m ∑a i =1 ij yi ≤ ( ≥ ) c j . Ví dụ 1: Bài toán gốc: f ( x ) = 2 x1 + 4 x 2 + 3 x 3 → m in  x1 + 2 x 2 + x 3 = 2   x 2 + 3 x3 = 5 x j ≥ 0, j = 1, 3 - 57 - Bài toán đối ngẫu của bài toán này là: g ( y ) = 2 y1 + 5 y 2 → m ax  y1 ≤ 2   2 y1 + y 2 ≤ 4 y + 3y ≤ 3  1 2 y1 , y2 tùy ý. 3.1.2 Bài toán đối ngẫu của bài toán dạng tổng quát Quy tắc lập bài toán đối ngẫu được cho bởi bảng sau: Bài toán gốc P (D) Bài toán đối ngẫu D (P) n m Hàm mục tiêu f ( x ) = ∑ c j x j → max Hàm mục tiêu g ( y ) = ∑ bi yi → min j =1 i =1 n ≤   ≥  Ràng buộc thứ i: ∑ aij x j  ≥  bi , i = 1, m Ẩn thứ i: yi  ≤  0, i = 1, m  j =1 ...