tailieunhanh - Bài giảng môn Quy hoạch tuyến tính: Phần 2 - Nguyễn Đức Phương

Tiếp nội dung phần 1, Bài giảng môn Quy hoạch tuyến tính: Phần 2 cung cấp cho người học những kiến thức như: Lý thuyết đối ngẫu; bài toán vận tải và một số đề thi mẫu. Cùng tham khảo để nắm chi tiết nội dung phần 2 bài giảng. | Chương 3 Lý thuyết đối ngẫu Mục lục chương 3 Định nghĩa bài toán đối ngẫu . . . . . . . . . . . . . . . . 64 Các định lý về đối ngẫu . . . . . . . . . . . . . . . . . . . . 74 Phương án tối ưu của bài toán đối ngẫu . . . . . . . . . 81 Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . 89 Định nghĩa bài toán đối ngẫu Ví dụ . Có m loại nguyên liệu dự trữ dùng để sản xuất ra n loại sản phẩm. Để làm ra một sản phẩm j cần aij nguyên liệu i cho như bảng sau PP PP SP x1 x2 xn PP PP NL dự trữ NL P 1 2 n 1 a11 a12 a1n b1 2 a21 a22 a2n b2 m am1 am2 amn bm Giá bán c1 c2 cn Trong đó lượng nguyên liệu dự trữ thứ i là bi và giá bán mỗi sản phẩm j là cj Yêu cầu tìm số lượng sản phẩm x1 x2 xn sao cho tổng doanh thu lớn nhất. Trang 65 Chương 3. Lý thuyết đối ngẫu Giải. Tổng doanh thu lớn nhất z D c1 x1 C C cn xn max Khi đó tổng lượng nguyên liệu loại 1 sử dụng phải nhỏ hơn hoặc bằng b1 nghĩa là a11 x1 C C a1n xn b1 tương tự đối với nguyên liệu loại n am1 x1 C C amn xn bm Vậy ta có bài toán tìm x1 xn sao cho z D c1 x1 C C cnxn max Với các ràng buộc 8 lt a11 x1 C C a1n xn b1 ˆ ˆ a x C C a x b m1 1 mn n m xj 0 j D 1 2 n Bài toán được viết dưới dạng ma trận z D cT x max Với các ràng buộc Ax b x 0 trong đó A 2 Mm n .R I b 2 Mm 1 .R I c x 2 Mn 1 .R Ví dụ . Với giả thiết giống như ví dụ giả sử có một người muốn mua lại toàn bộ nguyên liệu trên. PP PP SP x1 x2 xn PP P NL dự trữ NL PP 1 2 n y1 1 a11 a12 a1n b1 y2 2 a21 a22 a2n b2 ym m am1 am2 amn bm Giá bán c1 c2 cn Tìm giá bán nguyên liệu i yi để Định nghĩa bài toán đối ngẫu Trang 66 Tổng giá trị người mua phải trả là nhỏ nhất. Người bán không bị thiệt. Giải. Tổng giá trị người mua phải trả nhỏ nhất được thể hiện 0 z D b1 y1 C C bm ym max Khi sản xuất một sản phẩm 1 người ta cần a11 nguyên liệu 1 . . . am1 nguyên liệu m Khi bán nguyên liệu thì chủ sở hữu nhận được a11 y1 C C am1 ym Mặc khác cùng lượng nguyên liệu trên khi sản xuất ra sản phẩm thì bán được với giá c1 Vậy để người bán .