tailieunhanh - Quy hoạch tuyến tính Chương 2

Hãy thành lập một phương án vận chuyển hàng hoá sao cho đáp ứng đầy đủ yêu cầu của các trạm thu bằng tất cả hàng hoá có ở các trạm phát với tổng chi phí vận chuyển là nhỏ nhất. | TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH CHƯƠNG II: BÀI TOÁN VẬN TẢI . Dạng của bài toán vận tải . Xây dựng phương án cực biên . Phương pháp thế vị giải bài toán vận tải . Bài toán không cân bằng thu phát . Dạng của bài toán vận tải Ai (i =1, m): các trạm phát Bj (j = 1, n): các trạm thu ai: lượng hàng hoá có ở trạm phát Ai bj: lượng hàng hoá yêu cầu ở trạm thu Bj cij: chi phí vận chuyển một đơn vị hàng hoá từ trạm phát Ai (i = 1,.,m) đến trạm thu Bj (j = 1, 2,., n) (cij > 0) xij: lượng hàng hoá vận chuyển từ trạm phát Ai đến trạm thu Bj , xij ≥ 0 ( i, j) Hãy thành lập một phương án vận chuyển hàng hoá sao cho đáp ứng đầy đủ yêu cầu của các trạm thu bằng tất cả hàng hoá có ở các trạm phát với tổng chi phí vận chuyển là nhỏ nhất. Tìm bộ giá trị sao cho: Nếu thì bài toán vận tải cân bằng thu phát Mô tả bài toán dưới dạng bảng: Thu Phát b1 b2 bn a1 c11 c12 c1n a2 c21 c22 c2n am cm1 cm2 cmn Giao của hàng i và cột j gọi là ô (i, j) đặc trưng cho đoạn đường nối trạm phát Ai và trạm thu Bj , ở ô này ghi cij Một số khái niệm: Vòng: Là một tập hợp các ô đứng vị trí là đỉnh của một đường gấp khúc khép kín có các cạnh song song với các dòng và các cột của bảng, trong đó mỗi ô đều nằm cùng hàng (cùng cột) chỉ với một ô đứng trước nó, đồng thời nằm cùng cột (cùng hàng) chỉ với một ô đứng sau nó. Một hệ vectơ điều kiện {Aij ; (i, j) K} của bài toán vận tải là độc lập tuyến tính khi và chỉ khi tập hợp các ô thuộc K không tạo thành vòng. Vì số vectơ {Aij} độc lập tuyến tính cực đại trong bài toán là m + n – 1 nên số tối đa các ô không tạo thành vòng trong bảng m hàng và n cột cũng là m + n – 1. Phương án cực biên: x = {xij} là phương án cực biên khi và chỉ khi tập hợp các ô (i, j) tương ứng với các thành phần dương của phương án không tạo thành vòng. Một phương án cực biên có tối đa m + n – 1 thành phần dương. Tập hợp m + n – 1 ô không tạo thành vòng bao hàm tập ô tương ứng | TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH CHƯƠNG II: BÀI TOÁN VẬN TẢI . Dạng của bài toán vận tải . Xây dựng phương án cực biên . Phương pháp thế vị giải bài toán vận tải . Bài toán không cân bằng thu phát . Dạng của bài toán vận tải Ai (i =1, m): các trạm phát Bj (j = 1, n): các trạm thu ai: lượng hàng hoá có ở trạm phát Ai bj: lượng hàng hoá yêu cầu ở trạm thu Bj cij: chi phí vận chuyển một đơn vị hàng hoá từ trạm phát Ai (i = 1,.,m) đến trạm thu Bj (j = 1, 2,., n) (cij > 0) xij: lượng hàng hoá vận chuyển từ trạm phát Ai đến trạm thu Bj , xij ≥ 0 ( i, j) Hãy thành lập một phương án vận chuyển hàng hoá sao cho đáp ứng đầy đủ yêu cầu của các trạm thu bằng tất cả hàng hoá có ở các trạm phát với tổng chi phí vận chuyển là nhỏ nhất. Tìm bộ giá trị sao cho: Nếu thì bài toán vận tải cân bằng thu phát Mô tả bài toán dưới dạng bảng: Thu Phát b1 b2 bn a1 c11 c12 c1n a2 c21 c22 c2n am cm1 cm2