Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
lượt xem 21
download
Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất trình bày sơ lược về các phương pháp tối ưu, xây dựng mô hình toán học cho các bài toán tối ưu thực tế và bài toán đường đi có trọng số bé nhất.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Báo cáo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
- TIẾP CẬN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH THÔNG QUA BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Trần Ngọc Việt NCS khóa 2010 2014 Đại học Đà Nẵng 1
- Nội dung trình bày Tóm tắt Sơ lược về các phương pháp tối ưu Xây dựng mô hình toán học cho các bài toán tối ưu thực tế Bài toán đường đi có trọng số bé nhất +Bài toán +Định lý +Thuật toán Dijkstra tìm đường đi ngắn nhất +Hướng tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất Kết luận 2 2
- TÓM TẮT Kết quả chính của bài báo là nghiên cứu mối quan hệ giữa bài toán quy hoạch tuyến tính với bài toán đường đi ngắn nhất. Dựa trên cơ sở vận dụng thuật toán Dijkstra cải tiến để tìm đường đi ngắn nhất của cặp đỉnh bất kì trên mạng đồ thị và kết hợp lý thuyết đối ngẫu trong quy hoạch tuyến tính. Bài báo phân tích, chứng minh các kết quả đưa ra. Chương trình tương ứng cài đặt bằng C và cho kết quả chính xác. 3 3
- 1. Sơ lược về các phương pháp tối ưu Trong thực tế sản xuất kinh doanh chúng ta thường phải giải quyết các nhiệm vụ dẫn đến việc tìm giá trị max hoặc min của một hàm nào đó. Chẳng hạn cần lập phương án sản xuất, thi công sao cho có thể đạt được một trong các yêu cầu sau: + Tổng giá trị sản lượng lớn nhất; + Tổng lợi nhuận lớn nhất; + Chi phí thấp nhất; + Cước phí rẻ nhất; + Thời gian thực hiện nhanh nhất; + Tổng vốn đầu tư nhỏ nhất… 4 4
- 2. Xây dựng mô hình toán học cho các bài toán tối ưu thực tế Việc mô hình hoá toán học cho một vấn đề thực tế có thể chia làm bốn bước như sau: Bước 1: Xây dựng mô hình định tính cho vấn đề đặt ra. Bước 2: Xây dựng mô hình toán học cho vấn đề đang xét. Trong bước này việc quan trọng là phải xác định hàm mục tiêu và các ràng buộc toán học. Bước 3: Sử dụng công cụ toán học để khảo sát, giải quyết các bài toán hình thành trong bước 2. Bước 4: Kiểm định lại các kết quả thu được trong bước 3. 5 5
- 3. Bài toán đường đi có trọng số bé nhất 3.1. Bài toán. Cho đồ thị G = (V, E, c) và hai đỉnh a, z. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh z trong đồ thị G. Đồ thị G được gọi là đồ thị có trọng số nếu trên mỗi cạnh (i, j) của đồ thị được gán một số nguyên không âm c (i,j). Nhãn c (i,j) trên cạnh (i,j) của đồ thị thường biểu diễn “chi phí ” thực tế để đi qua cạnh này. Độ dài đường đi ngắn nhất từ đi đỉnh a đến đỉnh z còn được gọi là khoảng cách từ đỉnh a đến đỉnh z trong đồ thị. Nếu không có đường đi từ a đến z thì đặt khoảng cách bằng ∞. 6 6
- 3.2. Định lý. Tại mỗi đỉnh z giá trị nhãn d (z) cuối cùng (nếu có) chính là độ dài của đường đi ngắn nhất từ đỉnh a đến đỉnh z. Chứng minh. Sau khi đã thực hiện xong thuật toán trên, nếu giá trị nhãn d (z) xác định thì ta có đường đi từ đỉnh a tới đỉnh z. Ta khôi phục đường đi từ a đến z như sau: d (i) + c (i,z) = d (z). Đỉnh i như thế chắc chắn phải tồn tại vì xảy ra đẳng thức ở lần gán hoặc giảm giá trị nhãn d (j) cuối cùng. Cứ tiếp tục như thế cho đến khi gặp đỉnh a. Giả sử ta nhận được dãy các cạnh: (a, a1) , (a1, a2) , ... , (ak1, z) Ta có: d (a) + c (a,a1) = d (a1) d (a1) + c (a1,a2) = d (a2) d (a2) + c (a2,a3) = d (a3) .. . .. . . . .. .. .. . . .. .. . . d (ak −1 ) + c(ak −1 , z ) = d ( z ) Cộng lại vế theo vế, ta được: c (a,a1) + c (a1,a2) + c (a2,a3)+ ... + c (ak1,z) = d (z). Vậy nhãn d (z) là độ dài của đường đi ngắn nhất. 7 7
- 3.3.Thuật toán Dijkstra tìm đường đi ngắn nhất Thuật giải tìm đường đi ngắn nhất từ đỉnh nguồn a đến đỉnh đích z trong đồ thị có trọng số, với c (i,j) > 0 và đỉnh x sẽ mang nhãn L(x). Kết thúc giải thuật L(z) chính là chiều dài ngắn nhất từ a đến z. + Đầu vào. Đồ thị G = (V, E, c) có trọng số c (i,j) > 0 với mọi cạnh , đỉnh nguồn a và đỉnh đích z. + Đầu ra. L(z) chiều dài đường đi ngắn nhất từ đỉnh nguồn a đến đỉnh đích z và đường đi ngắn nhất (nếu L(z)
- + Phương pháp gồm các bước sau: x≠a (1)Khởi tạo: Gán L(a):=0. Với mọi đỉnh gán L(x) := ∞ . Đặt T:=V. (2)Tính L(u ) u ∈ T }. m := min{ m=+∞ Nếu , kết thúc và ta nói không tồn tại đường đi từ a đến z. m L (v ) + c ( v, gán L( x) := L(v) + c(v, x) và ghi nhớ đỉnh v cạnh x để xây dựng đường đi ngắn nhất. Quay về bước 2. 9 9
- 3.4. Hướng tiếp cận bài toán quy hoạch tuyếntính thông qua bài toán tìm đường đi ngắn nhất : Xét bài toán quy hoạch tuyến tính dạng tổng quát: { max cT x Ax ≤ b, x ≥ 0 } Bài toán đối ngẫu của nó là: { min bT y AT y ≥ c, y ≥ 0 } Biến đối ngẫu y(i) của độ dài cạnh i length y ( j ) = ∑ i A(i, j ) y (i ) / c( j ) Tìm 1 đường đi ngắn nhất tương ứng với tìm kiếm 1 cột có chiều dài tối thiểu: α ( y ) = min j length y ( j ) Đặt: D ( y ) = bT y 10 10
- Tìm biến đối ngẫu y: là nhỏ nhất D( y ) / α ( y ) Cho q là cột có chiều dài nhỏ nhất từ ma trận A: α ( y k −1 ) = length y k −1 (q) ⇒ f k = f k −1 + c(q)b( p) / A( p, q ) Ta được cấu trúc bài toán đối ngẫu: b( p ) / A( p, q ) y k (i ) = y k −1 (i )1 + ε b(i ) / A(i, q ) Tính biến đối ngẫu y0 (i ) = δ / b(i ) 11 11
- Cho k ≥ 1 : D(k ) = ∑ b(i ) y k (i ) i = ∑ b(i ) y k −1 (i ) + ε b( p ) ∑ A(i, q) y k −1 (i ) i A( p, q ) i = D(k − 1) + ε ( f k − f k −1 )α (k − 1) k ⇒ D(k ) = D (0) + ε ∑ ( f l − f l −1 )α (l − 1) l =1 β = min y D( y ) / α ( y ) thì ta được β ≤ D(l − 1) / α (l − 1) ε k D(k ) ≤ mδ + ∑ ( f l − f l −1 ) D(l − 1) β l =1 12 12
- ε k ⇒ x(i ) = mδ + ∑ ( f l − f l −1 ) x(l − 1) β l =1 ε k −1 ε ⇒ x(k ) = mδ + ∑ ( f l − f l −1 ) x(l − 1) + ( f k − f k −1 ) x(k − 1) β l =1 β ε = 1 + ( f k − f k −1 ) x(k − 1) β ≤ eε ( f k − f k −1 ) / β .x(k − 1) ≤ eε . f k / β .x(0) = mδ .eε . f k / β Dùng BĐT: D (k ) ≤ x(k ) ⇒ D (k ) ≤ mδ .eε . f k / β ε. f / β Vậy, 1 ≤ D (t ) ≤ mδ .e t 13 13
- 3.5.Thử nghiệm chương trình: Kết quả chạy chương trình bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất. Ví dụ: Cho mạng đồ thị gồm 4 đỉnh, 7 cạnh và các nút từ 1 đến 4 14 14
- 4. Kết luận Kết quả của bài báo đã đáp ứng được mục tiêu đề tài là “ Tiếp cận bài toán quy hoạch tuyến tính thông qua tìm đường đi ngắn nhất ” đã đặt ra, đó là nghiên cứu xây dựng mô hình toán học cho bài toán Quy hoạch, trong đó các ràng buộc về khả năng thông qua, mục tiêu tối ưu, phát triển và áp dụng hiệu quả các thuật toán tối ưu. 15 15
- XIN CHÂN THÀNH CẢM ƠN ! 16 16
CÓ THỂ BẠN MUỐN DOWNLOAD
-
TIỂU LUẬN: Cơ sở lý luận để tiếp cận chủ nghĩa xã hội và xây dựng chủ nghĩa xã hội ở việt nam hiện nay
96 p | 558 | 59
-
Báo cáo nghiên cứu khoa học: " TIẾP CẬN CHUỖI GIÁ TRỊ CHO VIỆC NÂNG CẤP NGÀNH DỆT MAY VIỆT NAM"
11 p | 175 | 59
-
Báo cáo nghiên cứu khoa học " TIẾP CẬN PHÒNG CHỐNG UNG THƯ CỔ TỬ CUNG THEO HƯỚNG CỘNG ĐỒNG "
14 p | 149 | 22
-
Báo cáo khoa học: ẢNH HƯỞNG CủA YếU Tố Vị TRí ĐếN GIá ĐấT trình bày ở TạI THị Xã BắC NINH TỉNH BắC NINH
8 p | 122 | 20
-
Báo cáo khoa học: Thách thức trong phát triển nguồn nhân lực dân tộc thiểu số nước ta nhìn từ tiếp cận văn hóa và tâm lý các tộc người
27 p | 136 | 18
-
Luận văn thạc sĩ Khoa học kinh tế: Nâng cao năng lực tiếp cận thị trường của sản phẩm mây tre đan tại HTX mây tre đan Bao La, huyện Quảng Điền, tỉnh Thừa Thiên Huế
136 p | 80 | 17
-
Báo khoa học: Tiếp cận bài toán quy hoạch tuyến tính thông qua bài toán tìm đường đi ngắn nhất
8 p | 154 | 16
-
Báo cáo khoa học: Phương pháp lọc thư rác tiếng Việt dựa trên từ ghép và theo vết người sử dụng
11 p | 129 | 14
-
Báo cáo khoa học: Một số phương pháp hiệu chỉnh góc nghiêng của ảnh và ứng dụng
10 p | 158 | 13
-
Báo cáo khoa học: " CẢI TIẾN CÁC THUẬT TOÁN MƯỢN VÀ KHOÁ KÊNH TẦN SỐ MẠNG DI ĐỘNG TẾ BÀO"
9 p | 84 | 12
-
Báo cáo khoa học: "PHƯƠNG PHÁP LUẬN TIẾP CẬN DỰ BÁO MỨC ĐỘ XUỐNG CẤP CỦA MẶT ĐƯỜNG VÀ ĐỊNH HƯỚNG ÁP DỤNG TRONG NGHIÊN CỨU TÌNH TRẠNG XUỐNG CẤP MẶT ĐƯỜNG CHO CÁC TUYẾN ĐƯỜNG CÓ XE BUÝT NỘI ĐÔ HÀ NỘI"
7 p | 67 | 10
-
Báo cáo nghiên cứu khoa học: " TIẾP CẬN LÝ THUYẾT VÀ THỰC TIỄN LUSTER NGÀNH CHO PHÁT TRIỂN KINH TẾ KHU VỰC"
9 p | 78 | 9
-
Báo cáo khoa học: Bước đầu tìm hiểu quá trình hình thành, phát triển và đặc điểm của bảng chữ cái tiếng Hàn
14 p | 89 | 9
-
Báo cáo nghiên cứu khoa học: "TIẾP CẬN MỚI BẢN CHẤT NĂNG SUẤT VÀ PHÂN TÍCH NÓ"
5 p | 80 | 9
-
Báo cáo khoa học: Hệ cộng dồn mùi cải tiến trong Hệ cộng dồn mùi cải tiến
8 p | 59 | 7
-
Báo cáo khoa học: "TIẾP CẬN ĐA XU HƯỚNG PHÁT TRIỂN CỦA CÁC NGHIÊN CỨU LÍ THUYẾT VÀ THỰC NGHIỆM VỀ BÊ TÔNG HIỆN NAY"
8 p | 85 | 6
-
Báo cáo khoa học: Luân giao và Ggebiplot
7 p | 66 | 5
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