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

Phần 2 của bài giảng tiếp tục giới thiệu tới các bạn những nội dung về bài toán vận tải, bài toán vận tải cân bằng thu phát, phương pháp cực biên của bài toán thu phát, lý thuyết mẫu, phương pháp góc Tây - Bắc, bài toán vận tải không cân bằng, thuật toán không quy ước. | Chương 3 Lý thuyết đối ngẫu Ví dụ dẫn đến 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 nguyên liệu i cho như bảng sau SP 7. X1 1 X2 2 . . . Xn n NL dự trữ 1 aii ai2 . . . ain bi 2 Ơ21 a22 . . . a2n b2 . . . . . . . . . . . . . . . . . . m ami am2 . . . amn b m 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. Ví dụ dẫn đến bái toán đối ngẫu 65 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. SP NL xi 1 X2 2 . . . x n NL dự trữ yi 1 aii ai2 . . . ain bi y2 2 a2i a22 . . . a2n b2 yw m ami am2 . . . amn b m Giá bán Ci C2 . . . cn Tìm giá bán nguyên liệu i yi để Người bán không bị thiệt. Người mua được mua với giá rẻ nhất. Ví dụ dẫn đến bái toán đối ngẫu 66 Bài toán đối ngẫu của bài toán max Hai bài toán quy hoạch tuyến tính sau gọi là cặp bài toán đối ngẫu. Bài toán 1 gọi là bài toán gốc bài toán 2 gọi là bài toán đối ngẫu. Một ràng buộc và điều kiện về biến trên cùng một dòng gọi là cặp ràng buộc đối ngẫu. Bài toán gốc 1 Bài toán đối ngẫu 2 z C1X1 cnxn max z biyi C C bmym min aiiXi ai2X2 C C ainXn bi yi 0 aiiXi ai2X2 C C ainXn bi yi 0 aiiXi ai2X2 C C ainXn bi yi 2 R xj 0 aijyi a2jy2 C C amjym Cj Xj 0 aijyi a2jy2 C C amjym Cj Xj 2 R aijyi a2jy2 C C amjym Cj Nhận xét. Quan sát cặp bài toán đối ngẫu trên ta có các nhận xét Trong cặp bài toán đối ngẫu trên hệ số của ràng buộc thứ i của bài toán gốc trở thành hệ số của biến yi trong bài toán đối ngẫu. Ngược lại hệ số của Xj trong bài toán gốc chính là hệ số của dòng j trong bài toán đối ngẫu. Hệ số của hàm mục tiêu của bài toán gốc trở thành hệ số vế phải của ràng buộc và ngược lại. Ví .

• Kinh tế học
• Bài giảng Quy hoạch tuyến tính
• Quy hoạch tuyến tính
• Bài giảng Quy hoạch tuyến tính Phần 2
• Bài toán vận tải không cân bằng
• Bài toán vận tải
• Lý thuyết mẫu
• Lý thuyết quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài tập quy hoạch tuyến tính
• Lập mô hình bài toán
• Ứng dụng quy hoạch tuyến tính
• Bài toán dòng trên mạng
• Bài toán quy hoạch nguyên
• Phương pháp hình học
• Phương pháp đơn hình
• Phân loại bài toán QHTT
• Ôn tập cuối kỳ
• Bài toán kinh tế
• Tính chất bài toán quy hoạch tuyến tính
• Toán chuyên đề 2
• Quy hoạch tuyến tính đối ngẫu
• Quy hoạch tuyến tính về dạng chính tắc
• Bài giảng Bài toán tối ưu tuyến tính
• Bài toán tối ưu tuyến tính
• Tối ưu tuyến tính
• Biểu thức tuyến tính
• Bài toán về lập kế hoạch sản xuất
• Bài toán về khẩu phần
• Bài toán trò chơi
• dự án xây dựng
• kế hoạch sản xuất
• tài liệu về quy hoạch tuyến tính
• các dạng bài toán vận tải
• bài tập tuyến tính
• Quy hoạch tuyến tính dạng chính tắc
• Bài toán đối ngẫu
• Quy hoạch tổng quát
• Giải thuật đối ngẫu
• Bài toán vốn đầu tư
• Bài toán lập kế hoạch sản xuất
• Ma trận cơ sở
• Đối ngẫu trong quy hoạch tổng quát
• Tối ưu hóa
• Bài giảng Tối ưu hóa
• Thiết lập mô hình bài toán
• Dạng bài toán quy hoạch tuyến tính
• Giải bài toán QHTT
• Phương pháp đơn hình giải bài toán QHTT
• Phương pháp đơn hình cho bài toán chính tắc
• Thuật toán đơn hình
• Bài toán chính tắc
• bài toán vận chuyển
• các dạng bài toán quy hoạch tuyến tính
• quy tắc biến đổi
• Giải thuật đơn hình
• Thuật toán đơn hình đối ngẫu
• Thuật toán thế vị
• Phương pháp đồ thị