Giáo trình Toán kinh tế (Nghề: Kế toán - Cao đẳng): Phần 2 - Trường Cao đẳng Cộng đồng Đồng Tháp

Giáo trình Toán kinh tế trang bị một số kiến thức về cơ sở lý thuyết, các bài toán cơ bản và các phương pháp giải bài toán trong quy hoạch tuyến tính: Khái niệm và cách thiết lập bài toán quy hoạch tuyến tính, phương án, phương án cực biên, phương án tối ưu của một bài toán quy hoạch tuyến tính;... 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:
Giáo trình Toán kinh tế (Nghề: Kế toán - Cao đẳng): Phần 2 - Trường Cao đẳng Cộng đồng Đồng Tháp CHƢƠNG 3: BÀI TOÁN ĐỐI NGẪU  Giới thiệ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 - Về kiến thức: + Hiểu rõ về bài toán đối ngẫu là gì. + Ý 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. + Hiểu đƣợc 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. - Về kỹ năng: + Lập đƣợc bài toán đối ngẫu từ bài toán gốc. + Từ phƣơng án tối ƣu của bài toán gốc suy ra đƣợc phƣơng án tối ƣu của bài toán đối ngẫu và ngƣợc lại. - Về năng lực tự chủ và trách nhiệm: Có thái độ nghiêm túc, tự giác học tập và chịu trách nhiệm với kết quả thực hiện. 54 1. Khái niệm 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): f (x) cj xj min (max) n (3.1.1) j1 a x  b i 1,m n ij j i (3.1.2) j1 xj 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ó: g(y)  by m i i max (min) (3.1.4) i1 a y  () c m ij i j ( j 1, n) (3.1.5) i1 yi 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) max 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) max (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 a x  b , n i trong ma trận A(aij)mxn xác định ràng buộc thứ i của bài toán gốc ij j i j1 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: a y  () c . m ij i j i1 Ví dụ 1: Bài toán gốc: f (x)  2x1 4x2 3x3 min x1 2x2  x3  2 x 3x 5 2 3 xj 0, j 1,3 Bài toán đối ngẫu của bài toán này là: g(y) 2y1 5y2 max 55 y1  2 2y  y  4  1 2  y1 3y2 3 y1, y2 tùy ý. 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) cj xj max by min n m Hàm mục tiêu f (x)  Hàm mục tiêu g(y)  i i j1 i1     Ràng buộc thứ i: aijxj  bi , i 1, m Ẩn thứ i: yi    0, i 1, m   n j1  tùy ý     Ẩn thứ j: xj   0, j 1, n Ràng buộc thứ j: aij yi  cj , j 1, n m tùy ý i1   Nhận xét: Bài toán đối ngẫu của bài toán đối ngẫu chính là bài toán gốc. Vì vậy ngƣời ta nói cặp bài toán gốc – đối ngẫu là cặp bài toán đối ngẫu nhau.  Cách nhớ max  min Ẩn  Ràng buộc(cùng dấu) Ràng buộc  Ân (ngƣợc dấu) Ẩn  Ràng buộc (ngƣợc Ràng buộc  Ân (cùng dấu) min  max dấu) Ví dụ 2: Tìm bài toán đối ngẫu của bài toán f (x) 2x1 3x2 x3 x4 max 2x1 x2 x3  x4 5 (1) x  x 2x  x  7 1 2 3 4 (2) 5x1  x2 3x3  x4  20 (3)  x1, x2 0, x3 0 x4 tùy ý. ...