BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH_ Chương 2: Bài toán vận tải

Vòng là tập hợp các ô đứng vị trí là đỉnh của một đường gấp khúc kín có các cạnh song song với dòng và cột của bảng, trong đó mỗi ô đều nằm cùng hàng chỉ với một ô đứng trước nó, đồng thời nằm cùng cột 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...
Nội dung trích xuất từ tài liệu:
BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH_ Chương 2: Bài toán vận tảiTrườ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 2: Bài toán vận tải 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ẢNGQUY HOẠCH TUYẾN TÍNHCHƯƠNG II: BÀI TOÁN VẬN TẢI 2.1. Dạng của bài toán vận tải 2.2. Xây dựng phương án cực biên 2.3. Phương pháp thế vị giải bài toán vận tải 2.4. Bài toán không cân bằng thu phát 2.1. Dạng của bài toán vận tảiAi (i =1,…m): các trạm phátBj (j = 1,…n): các trạm thuai: lượng hàng hoá có ở trạm phát Aibj: lượng hàng hoá yêu cầu ở trạm thu Bjcij: 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 đếntrạHãy thành lập một phương án vận chuyển hàng hoá msao cho đáp, ứng ≥ ầy ∀ủ j) cầu của các trạm thu bằng đ 0 ( đ i, yêu thu Bj xijtất cả hàng hoá có ở các trạm phát với tổng chi phí vậnchuyển là nhỏ nhất. ( )Tìm bộ giá trị { xij } i = 1, m; j = 1, n sao cho: m n f ( x) = ∑ ∑ cij xij ⇒ min (1) i =1 j =1 (i = 1, m) n ∑x = ai (2) ij j =1 ( j = 1, n) m ∑x = bj (3) ij i =1 (i = 1, m; j = 1, n) xij ≥ 0 ( 4) m n ∑ a = ∑bNếu thì bài toán vận tải cân bằng thu phát i j i =1 j =1Mô tả bài toán dưới dạng bảng: Thu b1 b2 …… bnPhát 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 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ácdòng và các cột của bảng, trong đó mỗi ô đều nằm cùnghàng (cùng cột) chỉ với một ô đứng trước nó, đồng thờinằ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ánvậ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àitoán là m + n – 1 nên số tối đa các ô không tạo thành vòngtrong 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 khivà chỉ khi tập hợp các ô (i, j) tương ứng với các thành phầndương của phương án không tạo thành vòng. Một phương áncự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 với các thành phần dương của phương án cực biênx (xij > 0) gọi là tập ô cơ sở nó, ký hiệu là S. Ô (i, j)∈S gọi là ô cơ sở, (i, j)∉S gọi là ô phi cơ sở. Một ô phi cơ sở bất kỳ bao giờ cũng tạo thành một vòng duynhất với các ô cơ sở. Một phương án cực biên không suy biến chỉ có một tập ô cơsở duy nhất, đó chính là tập ô tương ứng với các thành phầndương của phương án. Một phương án cực biên suy biến có nhiều tập ô cơ sở khácnhau, phần chung của chúng là tập ô ứng với các thành phầndương. 2.2. Xây dựng phương án cực biên Khi xác định được xịj = α , ta nói là đã phân phối cho ô (i, j)một lượng hàng là α. Nguyên tắc phân phối tối đa: Lấy ô (i, j) bất kỳ củabảng và phân phối cho nó một lượng hàng tối đa có thể,nghĩa là đặt xij = min{ai ,bj}. Ba trường hợp có thể xảy ra: - xij = ai , yêu cầu của trạm phát thỏa mãn, loại hàng i rakhỏi bảng, đồng thời sửa lại yêu cầu của trạm thu: b’j = bj- ai x = b , yêu cầu của trạm thu thỏa mãn, loại cột j ra - ij jkhỏi bảng, đồng thời sửa lại yêu cầu của trạm phát: a’i = ai- bj x = a = b ,yêu cầu của cả trạm thu và phát đều thỏa - ij i jmãn, loại đồng thời hàng i và cột j ra khỏi bảng. Quá trình tiếp tục cho tới khi yêu cầu của mọi trạm thu vàphát đều thoả mãn. Các ô được phân phối có xij > 0, đặt xij = 0 với những ôkhông được phân phối Khi đó sẽ thu được một phương án cực biên của bài toán. Nếu số ô được phân phối là m + n – 1 thì phương án cựcbiên thu được là không suy biến, tập ô được phân phối chínhlà tập ô cơ ...