quy hoạch phát triển hệ thống điện, chương 4
lượt xem 116
download
Trình bày về bài toán vận tải. Lập bài toán vận tải Bản chất của bài toán vận tải là tìm phương án tối ưu để vận tải hàng hóa từ một số nơi phát đến một số nơi nhận. Chỉ tiêu tối ưu ở đây thường là cực tiểu chi phí tổng về vận tải. Bài toán có thể mô tả như sau: có m địa điểm phát , với các lượng hàng hoá tương ứng a1, a2,. . ., am và n địa điểm nhận, với nhu cầu tương ứng b1, b2, . . ., bn. Cần xác...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: quy hoạch phát triển hệ thống điện, chương 4
- Chương 4: Bài toán vận tải là gì, cách giải bài toán vận tải bằng phương pháp góc tây bắc, Hoàn thiện lời giải bằng phương pháp thế vị (Giải bài toán vận tải, hàm mục tiêu, ràng buộc, cách giải thông qua ví dụ). 1. Trình bày về bài toán vận tải. Lập bài toán vận tải Bản chất của bài toán vận tải là tìm phương án tối ưu để vận tải hàng hóa từ một số nơi phát đến một số nơi nhận. Chỉ tiêu tối ưu ở đây thường là cực tiểu chi phí tổng về vận tải. Bài toán có thể mô tả như sau: có m địa điểm phát , với các lượng hàng hoá tương ứng a1, a2,. . ., am và n địa điểm nhận, với nhu cầu tương ứng b1, b2, . . ., bn. Cần xác định phương án vận tải sao cho tổng chi phí là cực tiểu, khi biết giá thành cước phí đơn vị Cij vận tải trên đoạn đường từ nơi phát i đến nơi nhận j. Ký hiệu xij là số lượng hàng cần vận tải từ nơi phát i đến nơi nhận j, khi đó điều kiện của bài toán vận tải được mô tả trong bảng.
- a1 ........................................................................... am Xmn Xm1 X11 X12 Xm2 X1n .......................... b1 b2 bn Mô tả bài toán Nơi nhận Dung Nơi phát B1 B2 ….. Bn lượng ai c11 c12 c1n A1 a1 X11 X12 X1n c21 c22 C2n A2 .a1 X21 X22 X2n ….. ---- cm1 cm2 Cmn Am .am Xm1 Xm2 Xmn Dung m n ai b j lượng bi i 1 j 1 Bài toán vận tải được phát biểu dưới dạng toán học như sau: - Xác định các giá trị xij : i = 1, 2, ..., m ; j = 1, 2, ..., n sao cho: m n C x min ij ij f(X) = i 1 j 1 với các ràng buộc: n j 1 xij ai ; i 1,2,..., m m xij b j ; j 1,2,..., n i 1
- và : xij ≥ 0 (i = 1,2,..., m ; j = 1, 2,..., n ) - Ngoài ra trong trường hợp đơn giản thường giả thiết là tổng dung lượng hàng phát đi cân bằng với tổng dung lượng nơi nhận, nghĩa là: m n a b i 1 i j 1 j 2. Phương pháp góc tây bắc 4.3.2.Xác định phương án cơ bản ban đầu * Phương pháp góc tây bắc xác định giá trị (m+n-1) ẩn cơ bản của phương án ban đầu. - Xuất phát từ góc bên trái trên cùng (x11) ta điền các giá trị của ẩn cơ bản và đi dần xuống góc phải dưới cùng, đồng thời luôn luôn thoả mãn các ràng buộc ở mục trên. Nơi Nơi nhận Dung phát B1 B2 B3 lượng ai 5 3 2 A1 200 150 50 0 2 4 6 A2 300 0 200 100 Dung lượng 150 250 100 500 bi Có hai nơi phát A1, A2 với các lượng hàng tương ứng a1 = 200; a2 = 300 và 3 nơi nhận với nhu cầu tương ứng b1 = 150; b2 = 250; b3 = 100. Cước phí vận tải cij được ghi ở góc phải phía trên trong từng ngăn ở bảng. Xuất phát từ góc tây bắc ta có x11 = 150 (vì b1
- Vậy phương án cơ bản ban đầu là : x11 = 150 ; x12 =50 ; x22 = 200 ; x23 = 100. Khi đó: F1(X) = 150.5 + 50.3 + 200.4 + 100.6 = 2300. Rõ ràng phương án cơ bản ban đầu ở đây chưa đạt min f(X) cần tìm cách giảm giá trị f(x) 3. Hoàn thiện lời giải bằng phương pháp thế vị. Sau khi đã có giá trị của (m+n-1) ẩn cơ bản của phương án ban đầu, cần tìm phương pháp để hoàn thiện lời giải dẫn với phương án ứng với giá trị min f(x). Sau đây sử dụng một trong những phương pháp thường dùng là phương pháp thế vị (còn gọi là phương pháp phân phối cải biên). Nội dung phương pháp thế vị gồm những bước sau: 1.Xác định giá trị thế vị 2.Chỉ tiêu tối ưu theo phương pháp thế vị 3. Nguyên tắc vòng kín hoàn thiện lời giải 1. Xác định giá trị thế vị Ứng với mỗi hàng (nơi phát A1, A2,...,Am) có thế vị 1, 2,..., m và mỗi cột (nơi nhận B1, B2,... Bn ) có thế vị 1, 2,..., n. Như vậy với mỗi phương án của bài toán vận tải ta có một hệ thống (m+n) thế vị 1, 2,..., m, 1, 2,..., n. Giá trị của i, j được xác định như sau: i + j = cij (*); i = 1, 2, ..., m; j = 1, 2,... , n ta cần xác định (m+n) giá trị thế vị, nhưng ở mỗi phương án chỉ có (m+n-1) giá trị cij để tạo thành (m+n-1) phương trình dạng (*) vì vậy một thế vị phải cho giá trị tuỳ ý. Thường cho 1 = 0 và xác định 2,..., mvà 1, 2,..., n theo (*). Thí dụ ở phương án cơ bản ban đầu theo phương pháp góc tây bắc giá trị các thế vị được xác định nhờ hệ phương trình : 1 + 1 = 5; 1 + 2 = 3; 2 + 2 = 4; 2 + 3 = 6 với 1 = 0 ta có: 1 = 5; 2 = 3; 2 = 1; 3 = 5 Nơi Nơi nhận Dung phát B1 B2 B3 lượng α
- ai 5 3 2 A1 150 50 0 200 0 2 4 6 A2 0 200 100 300 1 Dung lượng bi 150 250 100 500 β 5 3 5 2. Chỉ tiêu tối ưu theo phương pháp thế vị: Định lí : Phương án X = xij của bài toán vận tải là tối ưu khi các giá trị thế vị i, j thoả mãn điều kiện sau: i + j = cij ở ngăn có xij > 0 i + j cij ở ngăn có xij = 0 3. Nguyên tắc vòng kín hoàn thiện lời giải 4.3.3. Hoàn thiện lời giải bằng phương pháp thế vị Vậy phương án là tối ưu ,hàm mục tiêu f(x) có giá trị
- F3(X) = 1400 Sơ đồ khối và một số chú ý Trong thực tế nhiều bài toán không có điều kiện đẳng thức như trên mà có: m n ai b j i 1 j 1 hoặc: m n ai b j i 1 j 1 Trong trường hợp đó có thể dựa vào các lượng vận tải xij phụ ứng với các cước phí phụ ứng với cước phí cij =0 để trở về điều kiện cân bằng dung lượng phát và nhận.
- Thành lập bài toán vận tải. Xác định thế vị i : i= 1, 2,...,m ; j : j = 1, 2,...,n Xác định ij = (i + j)-cij ứng với các ngăn xij = 0 Có Tính F(X), In giá Dừng ij ≤0? trị Không Chọn ngăn (AiBj); Có max ij Lập vòng kín +. . . - ; Xác định xij mới xij mới ? Không Bài toán vô nghiệm Không Lập phương án mới
CÓ THỂ BẠN MUỐN DOWNLOAD
-
quy hoạch phát triển hệ thống điện, chương 10
5 p | 354 | 136
-
quy hoạch phát triển hệ thống điện, chương 3
5 p | 364 | 128
-
quy hoạch phát triển hệ thống điện, chương 9
8 p | 312 | 126
-
quy hoạch phát triển hệ thống điện, chương 5
6 p | 373 | 114
-
Hệ thống điện và quy hoạch phát triển: Phần 1
179 p | 310 | 105
-
Hệ thống điện và quy hoạch phát triển: Phần 2
207 p | 281 | 87
-
Quy hoạch cải tạo hệ thống P6
8 p | 163 | 53
-
ĐỀ CƯƠNG ÔN TÂP MÔN QUY HOẠCH PHÁT TRIỂN GIAO THÔNG VẬN TẢI VÀ THIẾT KẾ MẠNG LƯỚI ĐƯỜNG
0 p | 250 | 44
-
cải tạo mở rộng hệ thống cấp nước thị xã Bắc Ninh- tỉnh Bắc Ninh, chương 6
7 p | 120 | 18
-
Quy hoạch lưới truyền tải có xét đến khả năng quá tải bằng phương pháp thu hẹp từng bước
8 p | 91 | 7
-
Giải pháp xây dựng hệ thống điện truyền tải linh hoạt
17 p | 43 | 6
-
Quản lý công trình ngầm đô thị - thách thức cho các đô thị đang phát triển
2 p | 74 | 5
-
Kỉ yêu hội thảo: Quy hoạch và phát triển kè bờ sông sài gòn và sông, kênh nội thành và các giải pháp để hoàn thành cơ bản kè sông sài gòn, sông và kênh nội thành vào năm 2025
412 p | 37 | 5
-
Quản lý xây dựng đồng bộ hệ thống hạ tầng kỹ thuật đô thị
5 p | 64 | 4
-
Nghiên cứu quy hoạch tổng thể các mỏ dầu khí bể Cửu Long
10 p | 68 | 2
-
Một số giải pháp nâng cao hiệu quả trong công tác quản lý và giám sát phát triển mỏ dầu khí tại Việt Nam
7 p | 57 | 2
-
Mạng viễn thông: Quy hoạch và phát triển - Phần 2
212 p | 3 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn