Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

7
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng" được nghiên cứu nhằm mục tiêu: Xây dựng mô hình và thuật toán giải quyết các bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí; Ứng dụng các thuật toán luồng tối ưu phân luồng giao thông tại thành phố Đà Nẵng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HỒ VĂN HÙNG LUỒNG ĐA HÀNG HÓA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 9.48.01.01 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG – Năm 2022
Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA- ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến Phản biện 1: …………………………………………………………… Phản biện 2: …………………………………………………………… Phản biện 3: …………………………………………………………… Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Trường, Trường Đại học Bách khoa Vào hồi … giờ … ngày … tháng … năm 2022 Có thể tìm hiểu luận án tại: - Thư viện quốc gia Việt Nam. - Trung tâm Thông tin - Học liệu & Truyền thông- Đại học Đà Nẵng.
MỤC LỤC MỞ ĐẦU ............................................................................................... 1 CHƯƠNG 1. TỔNG QUAN .................................................................... 3 1.1. Đồ thị ............................................................................................. 3 1.2. Mạng, luồng trên mạng .................................................................... 3 1.3. Bài toán luồng cực đại trên mạng ..................................................... 3 1.4. Bài toán quy hoạch tuyến tính .......................................................... 3 1.5. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ........ 3 1.6. Kết luận chương ....................................................................................................... 3 CHƯƠNG 2. XÂY DỰNG MÔ HÌNH VÀ THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HÓA ĐA CHI PHÍ .......................................................................................... 6 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................. 6 2.2. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................................................................................ 7 2.2.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí................................................................................................... 7 2.2.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................................................................................ 9 2.3. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................ 12 2.3.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................................... 12 2.3.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................ 15 2.4. Mô hình và thuật toán bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu ........................ 18 2.5. Kết luận chương ............................................................................ 20 CHƯƠNG 3. ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG ........................................................................................... 20 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng ................ 20 3.2. Ứng dụng thuật toán MFMM phân luồng giao thông ......................... 21 3.3. Ứng dụng thuật toán CMF phân luồng giao thông ............................ 21 3.4. Ứng dụng thuật toán LMF phân luồng giao thông ........................... 22 3.5. Ứng dụng thuật toán LCMF phân luồng giao thông .......................... 22 3.6. Ứng dụng thuật toán MCMF phân luồng giao thông ......................... 23 3.7. Kết luận chương ............................................................................ 24 KẾT LUẬN ................................................................................................................... 24
1 MỞ ĐẦU 1. Tính cấp thiết của việc nghiên cứu Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế,…. Hiện nay, việc ứng dụng lý thuyết đồ thị để giải quyết các bài toán trong thực tế được các nhà khoa học quan tâm nghiên cứu. Bài toán luồng đa hàng hóa trên mạng là bài toán tối ưu có nhiều ứng dụng trong các lĩnh vực kinh tế xã hội như giao thông, truyền thông, vận tải …, khác với bài toán đơn hàng, trong bài toán mạng đa hàng hóa có nhiều loại hàng hóa được lưu thông trên mạng như các gói tin, các phương tiện giao thông,… tùy thuộc vào loại hàng hóa mà cần nhu cầu lưu chuyển khác nhau. Bài toán đặt ra là tìm luồng vận chuyển có chi phí cực tiểu và lưu lượng trên mỗi tuyến được chia sẽ cho nhiều loại hàng hóa. Bài toán luồng đa hàng hóa trên mạng đã trở nên phổ biến trong các tài liệu học thuật và ngày càng có nhiều nhà nghiên cứu quan tâm đến lĩnh vực này. Các ứng dụng của bài toán luồng đa hàng hóa trên mạng dùng để giải quyết nhiều bài toán trong thực tế trong nhiều lĩnh vực từ mạng lưới truyền thông đến vận tải và năng lượng…. cụ thể ở các lĩnh vực sau (1) logistic, hệ thống giao thông và kỹ thuật giao thông; (2) ngành kinh tế và năng lượng và cuối cùng (3) mạng truyền thông và máy tính. Tuy nhiên, cho đến nay các nghiên cứu chỉ mới giải quyết được bài toán luồng đa hàng hóa đơn chi phí vì ở đó các loại hàng hóa quy về một loại hàng hóa chuẩn cùng một loại chi phí (đơn chi phí). Nhưng trong thực tế có nhiều bài toán mà ở đó chi phí lưu hành ứng với mỗi loại hàng hóa khác nhau, không thể quy đổi chi phí lưu hành của mỗi loại hàng hóa theo hệ số quy đổi của hàng hóa chuẩn. Ngoài ra trên mạng có một số tuyến cấm lưu hành đối với một số loại hàng hóa có chi phí vượt ngưỡng cho phép nào đó. Bên cạnh đó, do yếu tố khách quan khả năng thông hành của tuyến không thể đạt được tối đa, do đó cần xác định một tỷ lệ thông hành hợp lý tùy vào tình hình thực tế. Vì vậy, để mô hình hóa các bài toán trong thực tế một các chính xác và hiệu quả hơn chúng ta cần phải xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chí phí. Xuất phát từ đó, luận án sẽ quan tâm đến vấn đề xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để từ đó xây dựng luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng, đây là vấn đề cần thiết nghiên cứu trong giai đoạn hiện nay nhằm mô hình hóa các bài toán trong thực tế chính xác và hiệu quả hơn. 2. Mục tiêu nghiên cứu Luận án tìm hiểu mô hình mạng, luồng trên mạng, mạng mở rộng đa hàng hóa đơn chi phí để từ đó xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và trên cơ sở đó đề xuất mô hình và thuật toán giải quyết các bài toán luồng tối ưu trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Luận án tập trung vào nghiên cứu các đối tượng sau: - Lý thuyết đồ thị, quy hoạch tuyến tính. - Bài toán tìm đường đi ngắn nhất . - Bài toán luồng cực đại trên mạng truyền thống. - Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. - Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí.
2 3.2. Phạm vi nghiên cứu Luận án nghiên cứu trong phạm vi như sau: mạng, luồng trên mạng, bài toán toán luồng cực đại trên mạng, bài toán luồng cực đại trên mạng đa hàng hóa đơn chi phí. Trên cơ sở đó xây dựng mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để từ đó xây dựng các bài toán luồng tối ưu sau: - Bài toán luồng cực đại. - Bài toán luồng cực đại đồng thời. - Bài toán luồng cực đại với chi phí giới hạn. - Bài toán luồng cực đại đồng thời với chi phí giới hạn. - Bài toán luồng cực đại đồng thời với chi phí cực tiểu. 4. Phương pháp nghiên cứu - Tổng hợp, phân tích các kết quả nghiên cứu trước đây từ đó tìm ra các vấn đề cần phải giải quyết. - Tìm các phương pháp mở rộng bài toán, cải tiến, xây dựng các thuật toán mới để giải quyết các vấn đề đặt ra. - Từ thực nghiệm đến chứng minh bằng phương pháp toán học để đề xuất các thuật toán mới. 5. Các đóng góp của luận án Luận án có những đóng góp sau: - Đề xuất mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại, bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn. - Đề xuất mô hình và thuật toán giải quyết bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu. 6. Bố cục của luận án Luận án bao gồm: Phần mở đầu, nội dung gồm ba chương, phần kết luận và phần phụ lục. Phần mở đầu Chương 1: Tổng quan. Chương 2: Xây dựng mô hình và thuật toán giải quyết các bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. Chương 3: Ứng dụng các thuật toán luồng tối ưu phân luồng giao thông tại thành phố Đà Nẵng. Phần kết luận: Trình bày các kết quả nghiên cứu cũng như hướng nghiên cứu phát triển. Phần phụ lục: Các bảng dữ liệu để cài đặt cho các thuật toán.
3 CHƯƠNG 1. TỔNG QUAN 1.1. Đồ thị 1.2. Mạng, luồng trên mạng 1.3. Bài toán luồng cực đại trên mạng 1.4. Bài toán quy hoạch tuyến tính 1.5. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 1.5.1. Mạng hỗn hợp mở rộng Mạng truyền thống mới chỉ xét đến trọng số của các cạnh và các đỉnh một cách độc lập, độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Trong thực tế nhiều bài toán mà ở đó trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào tuyến đi đến và tuyến đi khỏi đỉnh đó. Ví dụ như ở Hình 1.1 thì thời gian đi qua ngã tư của một phương tiện giao thông phụ thuộc vào hướng di chuyển của phương tiện đó theo hướng rẽ phải, rẽ trái hay đi thẳng. Hình 1.1. Mô hình nút giao thông Vì vậy, để mô hình hóa các bài toán trong thực tế chính xác và hiệu quả hơn, cần xây dựng một mô hình mạng hỗn hợp mở rộng, trong đó ngoài hàm trọng số cạnh còn có thêm hàm trọng số đỉnh cv(v,e,e’), với v là đỉnh của đồ thị và e, e’ là các cạnh liên thuộc của đỉnh v. Khả năng thông hành là trọng số thể hiện khả năng tối đa mà hàng hóa có thể lưu hành qua cạnh hoặc đỉnh. Cho đồ thị hỗn hợp G =(V, E) Cho các hàm sau: Hàm khả năng thông hành cạnh ce:ER*, với ce(e) là khả năng thông hành cạnh eE. Hàm khả năng thông hành đỉnh cv:VR*, với cv(v) là khả năng thông hành đỉnh vV. Bộ G= (V, E, ce, cv) gọi là mạng hỗn hợp mở rộng. 1.5.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí 1.5.2.1. Giới thiệu 1.5.2.2. Mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Mạng đa hàng hóa là mạng trên đó có nhiều loại hàng hóa lưu hành trên mạng. Chi phí có thể hiểu là chi phí về thời gian, chi phí về nhiên liệu, chi phí ô nhiễm môi trường v.v... phải trả để lưu hành một đơn vị hàng hóa trên mạng. Cho mạng hỗn hợp mở rộng G=(V, E, ce, cv) như đã trình bày ở mục 1.5.1.
4 Ký hiệu Ev là tập các cạnh liên thuộc đỉnh vV. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng chia sẻ khả năng thông hành của tuyến. Cho các hàm sau: Hàm chi phí cạnh be:ER*, với be(e) là chi phí phải trả để chuyển một đơn vị hàng hóa qua cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí hai hướng có thể khác nhau. Hàm chi phí đỉnh bv:VEvEvR*, với bv(v,e,e’) là chi phí phải trả để chuyển một đơn vị hàng hóa từ tuyến e qua đỉnh v sang tuyến e’. Bộ G= (V, E, ce, cv, be, bv) gọi là mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Cho p là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1, …, h+1, và các đỉnh vj, j = 1,…, h, như sau: p = v → e1→ v1→ e2→ v2, →,…, eh→ vh→ eh+1→ w. Định nghĩa chi phí lưu hành một đơn vị hàng hóa qua đường đi p, ký hiệu b(p), theo công thức sau: h1 h b( p)   be(e j ) bv(v j , e j , e j 1) (1) j j Vậy, mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí là mạng trên đó có nhiều loại hàng hóa lưu hành nhưng ở đó chi phí lưu hành của các loại hàng hóa được quy về theo chi phí lưu hành của loại hàng hóa chuẩn (đơn chi phí). 1.5.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Cho G=(V, E, ce, cv, be, bv) là mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí như đã định nghĩa ở mục 1.5.2.2. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Giả thiết trên G có k cặp đỉnh nguồn-đích (sj, tj), mỗi cặp được gắn một loại hàng hóa cần chuyển từ đỉnh nguồn sj đến đỉnh đích tj, j=1,...,k. Ký hiệu Pj là tập hợp các đường đi từ sj đến tj trong G, j=1,…, k và đặt k P= P j 1 j (2) Với mỗi đường đi p  Pj, j=1,…,k, ký hiệu biến x(p) là luồng phương tiện đi từ sj đến tj lưu hành dọc theo đường đi p. Ký hiệu Pe là tập hợp các đường đi trong P đi qua cạnh e, eE. Ký hiệu Pv là tập hợp các đường đi trong P đi qua đỉnh v, vV. Tập hợp f={x(p) | pPj, j =1,…,k } gọi là luồng trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí, nếu thỏa mãn các ràng buộc về khả năng thông hành trên cạnh và đỉnh như sau:
5  x( p)  ce(e), e  E pPe (3)  x( p)  cv(v), v V pPv (4) 1.5.4. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí Cho mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí G=(V, E, ce, cv, be, bv) đã định nghĩa ở mục 1.5.2.2. Trên mạng có nhiều loại hàng hóa lưu hành, các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng chia sẻ khả năng thông hành của tuyến. Giả thiết trên G có k cặp đỉnh nguồn-đích (sj, tj), mỗi cặp được gán một loại hàng hóa cần chuyển từ đỉnh nguồn sj đến đỉnh đích tj, j = 1,...,k. Trên G có nhiều phương án phân luồng. Nhiệm vụ của bài toán là tìm luồng f trên G sao cho giá trị luồng f là lớn nhất. Ký hiệu (MSFP) là bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau: fv   x( p)  max pP thỏa mãn các ràng buộc  x( p)  ce(e), e  E pPe (MSFP)  x( p)  cv(v), v V pPv x( p)  0, p  P 1.6. Kết luận chương Trong chương này luận án trình bày các khái niệm cơ bản về đồ thị, mạng, luồng trên mạng, bài toán luồng cực đại trong mạng, thuật toán Ford –Fulkerson tìm luồng cực đại trên mạng, mạng hỗn hợp mở rộng, bài toán quy hoạch tuyến tính, bài toán đối ngẫu trong quy hoạch tuyến tính và bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Cho đến nay, các nghiên cứu chỉ mới giải quyết được bài toán đa hàng hóa đơn chi phí, vì ở đó chi phí lưu hành của các loại hàng hóa quy về theo hệ số của chi phí lưu hành hàng hóa chuẩn. Tuy nhiên, trong thực tế trên mạng có nhiều loại hàng hóa lưu hành ứng với mỗi loại hàng hóa có chi phí lưu hành khác nhau, không thể quy đổi chi phí lưu hành của mỗi loại hàng hóa theo hệ số quy đổi của hàng hóa chuẩn. Vì vậy cần xây dựng một mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí để có thể mô hình hóa được các bài toán trong thực tế hiệu quả hơn. Do đó, để mô hình hóa được các bài toán trong thực tế một cách chính xác và hiệu quả trên cơ sở lý thuyết của Chương 1 luận án đề xuất mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và các bài toán luồng tối ưu trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ở Chương 2.
6 CHƯƠNG 2 XÂY DỰNG MÔ HÌNH VÀ THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HÓA ĐA CHI PHÍ 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.1.1. Giới thiệu 2.1.2. Mạng hỗn hợp mở rộng đa hàng hóa đa chi phí Cho mạng hỗn hợp mở rộng G=(V, E, ce, cv) như đã định nghĩa ở mục 1.5.1. Ký hiệu Ev là tập các cạnh liên thuộc đỉnh vV, rN* là số loại hàng hóa lưu hành trên mạng, qi > 0 là hệ số quy đổi của hàng hóa loại i về hàng hóa chuẩn trên mạng với i =1,...,r. Trên mạng có r loại hàng hóa lưu hành, tương ứng với mỗi loại hàng hóa có chi phí lưu hành khác nhau. Các loại hàng hóa lưu hành trên mạng cùng chia sẻ khả năng thông hành của các tuyến. Các cạnh vô hướng biểu diễn tuyến hai chiều, trong đó các loại hàng hóa lưu hành trên cùng tuyến nhưng ngược hướng lưu hành chia sẻ khả năng thông hành của tuyến. Cho các hàm sau. Hàm hệ số phục vụ cạnh ze:ER*, với ze(e) là tỉ lệ thông hành cạnh eE (khả năng thông hành thực tế của cạnh e là ce(e).ze(e)) Hàm hệ số phục vụ đỉnh zv:VR*, với zv(v) là tỉ lệ thông hành đỉnh vV (khả năng thông hành thực tế của đỉnh v là cv(v).zv(v)) Hàm chi phí cạnh hàng hóa i, i=1,...,r, bei:ER*, với bei(e) là chi phí phải trả để chuyển một đơn vị hàng hóa loại i quy đổi qua cạnh e. Lưu ý rằng với những tuyến hai chiều thì chi phí lưu hành hai hướng có thể khác nhau. Hàm chi phí chuyển nhánh hàng hóa i, i=1,...,r, bvi:VEvEv R*, với bvi(v,e,e’) là chi phí phải trả để chuyển một đơn vị hàng hóa loại i quy đổi từ cạnh e qua đỉnh v sang cạnh e’. Bộ G=(V, E, ce, ze, cv, zv,{bei, bvi, qi |i=1..r}) gọi là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí.  Lưu ý: Nếu hàng hóa loại i có chi phí bei(e)= trên tuyến e thì hàng hóa loại i bị cấm lưu hành trên tuyến e. Nếu hàng hóa loại i có chi phí bvi(v,e,e’)= thì hàng hóa loại i bị cấm lưu hành từ tuyến e qua đỉnh v sang tuyến e’. 2.1.3. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí Cho G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Trên mạng G với mỗi loại hàng hóa loại i với i=1,...,r có ki cặp đỉnh nguồn-đích (sij, tij), j=1,...,ki, tương ứng với mỗi cặp đỉnh nguồn-đích (sij, tij) được gán một lượng hàng hóa loại i cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Ký hiệu Pij là tập hợp các đường đi từ đỉnh nguồn sij đến đỉnh đích tij trên G có thể lưu hành hàng hóa loại i, i=1,...,r, j=1,...,ki. ki Đặt Pi =  P là tập hợp các đường đi Pij của hàng hóa loại i trên G ứng với ki cặp j 1 ij
7 r đỉnh nguồn-đích (sij, tij), i=1,...,r, j=1,...,ki và P = Pi là tập hợp các đường đi của Pi i 1 trên G, i=1,...,r. Với mỗi đường đi pPij, i=1,...,r, j=1,...,ki, ký hiệu biến cfij(p) là luồng hàng hóa loại i quy đổi lưu hành từ đỉnh nguồn sij đến đỉnh đích tij dọc theo đường đi p, i=1,...,r, j=1,...,ki. Ký hiệu Pie là tập hợp các đường đi trong Pi đi qua cạnh e, eE. Ký hiệu Piv là tập hợp các đường đi trong Pi đi qua đỉnh v, vV. Tập hợp f ={cfij(p) | pPij, i=1,...,r, j=1,...,ki } gọi là luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí, nếu thỏa mãn các ràng buộc sau : - Luồng trên eE không vượt quá khả năng thông hành thực tế của mỗi cạnh: r ki   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e), e  E (5) - Luồng trên vV không vượt quá khả năng thông hành thực tế của mỗi đỉnh: r ki  p cfij ( p)  cv(v).zv(v), v V i 1 j 1 P (6) iv Biểu thức fvij   cfij ( p), i  1,..., r, j  1,..., ki pPij gọi là giá trị luồng hàng hóa loại i của cặp nguồn-đích (sij,tij) của f. ki Biểu thức fvi   fvij , i  1,..., r gọi là giá trị luồng của loại hàng hóa i của f. j 1 r Biểu thức fv   fvi gọi là giá trị luồng của f. i 1 2.1.4. Kết luận 2.2. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.2.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.2.1.1. Giới thiệu bài toán 2.2.1.2. Phát biểu bài toán Cho G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Ta gọi f={cfij(p) |pPij, i=1,...,r, j=1,...,ki} là luồng trên mạng G. Tồn tại nhiều phương án phân luồng trên mạng G. r ki Như vậy, nhiệm vụ của bài toán là tìm luồng có giá trị fv    cfij ( p) trên i 1 j 1 pPij mạng G lớn nhất. Ký hiệu (MFP) là bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:
8 r ki fv    cfij ( p)  max i 1 j 1 pPij thỏa mãn các ràng buộc r ki  p cfij ( p)  ce(e).ze(e), e  E i 1 j 1 P (MFP) ie r ki  p cfij ( p)  cv(v).zv(v), v V i 1 j 1 P iv cfij ( p)  0, i  1,..., r, j  1,..., ki , p  Pi Để giải được bài toán (MFP) ta xây dựng bài toán quy hoạch tuyến tính đối ngẫu gọi là bài toán (DM). Trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DM) được xây dựng như sau: r ki Mỗi ràng buộc  p cfij ( p)  ce(e).ze(e), e  E được gán một biến le(e) của i 1 j 1 P ie bài toán đối ngẫu (DM). r ki Mỗi ràng buộc  p cfij ( p) cv(v).zv(v), v V i 1 j 1 P được gán một biến lv(v) của iv bài toán đối ngẫu (DM). Khi đó, bài toán (DM) phát biểu như sau: DM (le, lv)   ce(e).ze(e).le(e)   cv(v).zv(v).lv(v)  min eE vV thỏa mãn các ràng buộc (DM)  le(e)  v lv(v)  1, p  P e p p le(e) ≥ 0, eE, lv(v) ≥ 0, vV Cho pPi, i=1,…,r là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1,...,(h+1) và các đỉnh vj, j=1,…,h như sau: p = v→e1→ v1→ e2→v2,→,…, eh→ vh→ eh+1→w. Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau: h1 h lengthi ( p)   le(e j )   lv(v j ) (7) j 1 j 1 Ký hiệu distij(le,lv) là độ dài đường đi ngắn nhất từ đỉnh nguồn sij đến đỉnh đích tij tính theo hàm độ dài lengthi(p), i=1,...,r, j=1,...,ki. Đặt (le,lv)=min{distij(le,lv) | i=1,...,r, j=1,...,ki}, vậy (le,lv) là độ dài ngắn nhất trong mọi đường đi giữa các cặp nguồn-đích. Việc giải bài toán (DM) tương đương với DM (le, lv) tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu.  (le, lv)  DM (le, lv)    Xét bài toán (DM):   min  le : E  R* , lv : V  R*    (le, lv)   
9  Bổ đề 2.2.1.1. Bài toán (DM) tương đương với bài toán (DM) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.2.1.3. Thuật toán MFMM (a).Thuật toán MFMM  Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}) và tỉ lệ xấp xỉ  .  Đầu ra: Luồng cực đại f biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f ={cfij(e) | eE, i=1,…,r, j=1,...,ki } Luồng cực đại rf biểu diễn dạng tập hợp luồng thực tế tại các cạnh. rf = {rfij(e) | eE, i=1,…,r, j=1,...,ki} Giá trị tổng luồng fv, tổng chi phí của luồng Bf  Các bước: Bước 1: Tính  và  theo hệ số xấp xỉ  1   1  1/ (1  ) và   (1  e) 1/  ; (1   ) 2 (m  n)    Bước 2: Khởi gán: fv =0; eE, le(e)= ; cfij(e)=0; vV, lv(v)= ; Bước 3: Tìm cặp nút nguồn-đích (sij, tij), 1i r và 1 j  ki, có đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi( ). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức là không chứa cạnh có chi phí  hoặc nút có chi phí chuyển nhánh . Giả sử (le,lv)=min{distij(le,lv)|i=1,…,r,j=1,...,ki}=distimin,jmin(le,lv) Ký hiệu: imin và jmin là chỉ số cặp nút nguồn-đích có đường đi ngắn nhất . p là đường đi ngắn nhất;  là độ dài ngắn nhất ; c là khả năng thông hành cạnh, đỉnh tối thiểu của p, tức là c=min{min{ce(e).ze(e)|ep},min{cv(v).zv(v)|vp}}; Bước 4: Điều chỉnh luồng: ep, cfimin,jmin(e)=cfimin,jmin(e)+c; le(e)= le(e).(1+.c/(ce(e).ze(e))); fv= fv +c ;vp, lv(v)= lv(v).(1+.c/(cv(v).zv(v))); Bước 5: Nếu  1 qua Bước 6, ngược lại quay về Bước 3. Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. (b). Độ phức tạp của thuật toán MFMM: O(2.k.n3.(m+n).ln(m+n)) 2.2.1.4. Kết luận 2.2.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí 2.2.2.1. Giới thiệu bài toán 2.2.2.2. Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1,...,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2.
10 Trên G có r loại hàng hóa lưu hành. Giả thiết với mỗi loại hàng hóa i, i=1,...,r, có ki cặp đỉnh nguồn-đích (sij, tij), j=1,...,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Dij là số lượng hàng hóa loại i, i=1,...,r, cần chuyển từ sij đến tij, j=1,..., ki. Đặt dij=qi.Dij là số lượng hàng hóa quy đổi loại i, i=1,...,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1,..., ki. Nhiệm vụ của bài toán là tìm một số  lớn nhất sao cho tồn tại một luồng {cfij(e) |e E, i=1,...,r, j=1,...,ki } chuyển ít nhất .dij đơn vị hàng hóa quy đổi loại i, i=1,...,r cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1,..., ki, tức là:  cf pPij ij ( p)  λ.dij ,  i = 1, ..., r, j = 1, ..., ki (8) Ký hiệu (CMFP) là bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí. Bài toán này được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:   max thỏa mãn các ràng buộc r ki   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e), e  E ki r (CMFP)   cf i 1 j 1 pPiv ij ( p)  cv(v).zv(v), v V  cf ( p)  .d , i  1,..., r, j  1,..., k pPij ij ij i  ≥ 0, cfij(p) ≥ 0, i=1,...,r, j = 1,...,ki, pPij Ký hiệu (DC) là bài toán đối ngẫu của bài toán (CMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DC) được xây dựng như sau: r ki Mỗi ràng buộc   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e), eE được gán một biến le(e) của bài toán đối ngẫu (DC). r ki Mỗi ràng buộc   cf i 1 j 1 pPiv ij ( p)  cv(v).zv(v), vV được gán một biến lv(v) của bài toán đối ngẫu (DC). Mỗi ràng buộc  cf ij ( p )  .d ij được gán một biến zij của bài toán (DC). pPij Khi đó, bài toán (DC) phát biểu như sau: DC (le, lv)   ce(e).ze(e).le(e)   cv(v).zv(v).lv(v)  min eE vV thỏa mãn các ràng buộc  le(e)   lv(v)  z , i  1,..., r, j  1,..., k , p  P e p v p ij i ij (DC) r ki  d .z i 1 j 1 ij ij 1 le(e) ≥ 0, eE, lv(v) ≥ 0, vV, zij ≥ 0, i=1,...,r, j=1,...,ki
11 Cho pP là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1,...,(h+1), và các đỉnh vj, j=1,...,h như sau: p = v → e1→ v1→ e2→ v2, →,…, eh→ vh→ eh+1→ w Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau: h 1 h lengthi ( p)   le(e j )   lv(v j ) (9) j 1 j 1 Ký hiệu disti,j(le,lv) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi (p), i=1,...,r, j=1,...,ki. r ki Đặt (le,lv)=  d ij .dist ij (le, lv), vậy (le,lv) là số lượng hàng hóa vận chuyển i 1 j 1 qua đường đi ngắn nhất giữa các cặp nguồn-đích. Việc giải bài toán (DC) tương đương với tìm hàm le:E R* và hàm lv:V R* sao DC (le, lv) cho đạt cực tiểu.  (le, lv)  DC (le, lv)  Xét bài toán (DC):  = min  le : E  R * , lv : V  R *    (le, lv)   Bổ đề 2.2.2.1. Bài toán (DC) tương đương với bài toán (DC) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.2.2.3. Thuật toán CMF (a). Thuật toán CMF  Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}) và  tỉ lệ xấp xỉ. Giả thiết với mỗi loại hàng hóa i, i=1,....,r, có ki cặp nút nguồn-đích (sij, tij), j=1,..., ki, mỗi cặp được gán một lượng hàng hóa quy đổi dij loại i, cần chuyển từ nút nguồn sij đến nút đích tij.  Đầu ra: Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {fij(e) | e  E, i=1,...,r, j=1,...,ki } Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng thực tế tại các cạnh rf = {rfij(e) | e  E, i=1..r, j=1..ki} Hệ số cực đại đồng thời , fv, Bf .  Các bước Bước 1: Tính các giá trị ,  theo hệ số xấp xỉ  1  1 mn    1 3 và  =   1   1   Bước 2 : Khởi gán i=1,...,r, j=1,…,ki, dij = Dij.qi ; DC(le,lv) = (m+n) ; eE le(e)=  /(ce(e)ze(e)) ; vV lv(v) = /(cv(v)zv(v)) ; i=1,.., r, j=1,..,ki, e  E, cfij(e)=0; //Giá trị luồng cfij(e) lúc đầu t = 0 ;//bước đếm giai đoạn khi (DC(t) < 1) DC(0) = (m+n) ; le0(e) = le(e), eE ; lv0(v) = lv(v), vV;
12 Bf= 0; fv=0; Bước 3 : i=1,...,r, j=1,…,ki, { d'ij = dij ; do { Tìm đường đi ngắn nhất p từ sij đến tij tính theo hàm độ dài lengthi(.). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức không chứa cạnh có chi phí  hoặc nút có chi phí chuyển nhánh . Gán distij(le,lv) là độ dài đường đi ngắn nhất từ si,j đến tij tính theo hàm độ dài lengthi (p). bei(p) là chi phí của một đơn vị hàng hóa loại i quy đổi trên đường đi. Đặt c =min{min{ce(e).ze(e)|ep}, min{cv(v).zv(v)|vp}, d’ij} // Điều chỉnh luồng ep, cfij(e) =cfij(e) + c; le(e) = le(e).(1+.c/(ce(e).ze(e))); vp, lv(v)= lv(v).(1+.c/(cv(v).zv(v))); d’ij = d’ij  c; Bf = Bf + c.bei(p); DC(le,lv) = DC(le,lv) + .c.distij(le,lv); } while (d’ij > 0); }// for … for … Bước 4: Hiệu chỉnh các giá trị t = t + 1; DC(t)=DC(le,lv); let(e) = le(e) e E, lvt(v) = lv(v); vV. if (DC(t)< 1) i =1,…,r; j=1,…,ki ; eE fij(e) = cfij(e);// fij(e) là luồng tối ưu Bước 5: Nếu DC(t) >= 1 qua Bước 6, ngược lại quay về Bước 3 Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. (b). Độ phức tạp của thuật toán CMF: O(2.(cemax/dmax).(+k).m.n3.log2(m+n)) 2.2.2.4. Kết luận 2.3. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 2.3.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 2.3.1.1. Giới thiệu bài toán 2.3.1.2. Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2. Có r loại hàng hóa lưu hành trên G, mỗi loại hàng hóa lưu hành trên mạng G có chi phí khác nhau. Giả thiết với mỗi loại hàng hóa i, i=1,...,r có ki cặp đỉnh nguồn-đích (sij,tij), j=1,...,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ sij đến tij. Cho chi phí giới hạn B. Nhiệm vụ của bài toán là tìm luồng sao cho giá trị luồng là lớn nhất và đồng thời tổng chi phí của luồng không vượt quá B. Ta gọi f =cfij(p) | pPij, i=1,...,.r, j=1,...,k } là luồng trên G.
13 Ký hiệu Bf là tổng chi phí của luồng f trên G. Bf không được vượt quá chi phí B cho trước, tức là: r ki   cf i 1 j 1 pP ij ( p).bi ( p)  B, i  1,..., r , j  1, ..., ki , p  Pij (10) ij Ký hiệu (LMFP) là bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn. Bài toán được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau: r ki fv    cfij ( p)  max i 1 j 1 pPij thỏa mãn các ràng buộc r ki   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e), e  E r ki (LMFP)   cfij ( p) cv(v).zv(v), v V i 1 j 1 pPiv r ki   cf i 1 j 1 pPij ij ( p).bi ( p)  B cfij ( p)  0, i  1,..., r , j  1,..., ki , p  Pij Ký hiệu (DL) là bài toán đối ngẫu với bài toán (LMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DL) được xây dựng như sau: r ki Mỗi ràng buộc   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e),eE được gán một biến le(e) của bài toán đối ngẫu (DL). r ki Mỗi ràng buộc   cf i 1 j 1 pPiv ij ( p)  cv(v).zv(v),vV được gán một biến lv(v) của bài toán đối ngẫu (DL). r ki Mỗi ràng buộc   cf i 1 j 1 pPij ij ( p).bi ( p)  B được gán một biến  của bài toán đối ngẫu (DL). Khi đó, bài toán (DL) phát biểu như sau: DL(le, lv,  )   ce(e).ze(e).le(e)   cv(v).zv(v).lv(v)  B.  min eE vV thỏa mãn các ràng buộc (DL)  le(e)   lv(v)  bi ( p).  1, p  Pij e p v p le(e)  0, e  E, lv(v)  0, v V ,  0 Bây giờ, cho pPi, i=1,…,r là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej với j=1,…,(h+1) và các đỉnh vj với j=1,...,h như sau : p = v → e1→ v1→ e2→ v2, →,…, eh→ vh→ eh+1→ w
14 Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) và  theo công thức sau: h 1 h lengthi (p) =  le(e j )   lv(v j )  bi (p). (11) j 1 j 1 Ký hiệu distij(le,lv,) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi(p), i=1,....,r và j=1,....,ki. Đặt (le,lv,) = min{distij(le,lv,) | i=1,...,r, j=1,...,ki}, vậy (le,lv,) là độ dài ngắn nhất trong mọi đường đi giữa các cặp nguồn-đích. Việc giải bài toán (DL) tương DL(le, lv,  ) đương với tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu.  (le, lv,  )  DL(le, lv, )  Xét bài toán (DL):   min  le : E  R* , lv : V  R* ,   0    (le, lv, )   Bổ đề 2.3.1.1. Bài toán (DL) tương đương với bài toán (DL) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.3.1.3. Thuật toán LMF (a). Thuật toán LMF  Đầu vào: Mạng G=(V, E, ce, ze, cv, zv, {bei, bvi, qi |i=1,...,r}). Cho tỉ lệ xấp xỉ  và chi phí giới hạn B.  Đầu ra: Luồng cực đại f biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {cfij(e) | eE, i=1,…,r, j=1,…,ki } Luồng cực đại rf biểu diễn dạng tập hợp luồng thực tế tại các cạnh. rf = {rfij(e) | eE, i=1,...,r, j=1,…,ki} Tổng giá trị luồng fv, tổng chí phí của luồng Bf  Các bước Bước 1: Tính các giá trị bmin, bmax, ,  Tính bmin là chi phí nhỏ nhất trong các đường đi từ đỉnh nguồn sij đến đỉnh đích tij, bmin = min{bi(p) | i=1,...,r, j=1,...,ki, pPij }. Tính bmax là chi phí lớn nhất trong các đường đi từ đỉnh nguồn sij đến đỉnh đích tij, bmax = max{bi(p) | i=1,...,r, j=1,…,ki, pPij }. Tính  và  theo hệ số xấp xỉ  1 =1 1/(1  ) và  = (1+) ; (1   ) (m  n  b max/ b min)  2 1/  Bước 2 : Khởi gán = /bmin; fv=0; Bf=0; eE, le(e)=;cfij(e)=0; vV, lv(v)=; Bước 3: Tìm cặp nút nguồn-đích (sij, tij), 1i r và 1 j  ki, có đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi( ). Chú ý đường đi p phải hợp lệ với hàng hóa loại i, tức là không chứa cạnh có chi phí  hoặc nút có chi phí chuyển nhánh . Ký hiệu:
15 imin và jmin là chỉ số cặp nút nguồn đích có đường đi ngắn nhất;  là độ dài đường đi ngắn nhất;p là đường đi ngắn nhất; c là khả năng thông hành cạnh, đỉnh tối thiểu của p, tức là c=min{min{ce(e).ze(e)|ep},min{cv(v).zv(v)|vp}}; B’ là tổng chi phí của luồng f qua p, tức là B’ = c.bimin(p); nếu (B’>B) thì {c = c.B / B’; B’ = B} Bước 4: Điều chỉnh luồng ep ta điều chỉnh như sau : cfimin,jmin(e)=cfimin,jmin(e)+c;//Thay đổi giá trị của luồng cfimin,jmin(e). le(e)= le(e).(1+.c/(ce(e).ze(e))); // Thay đổi giá trị của hàm le. vp ta điều chỉnh như sau : lv(v)= lv(v).(1+.c/(cv(v).zv(v))); // Thay đổi giá trị của hàm lv. fv = fv +c ;// Thay đổi giá trị của luồng f ;  = .(1+.B’/B); // Thay đổi giá trị hàm  ; Bf = Bf + B’ ; // Thay đổi chi phí của luồng Bf ; Bước 5: Nếu  1 qua Bước 6, ngược lại quay về Bước 3 Bước 6: Xử lí giá trị kết quả đạt được. Kết thúc. (b). Độ phức tạp của thuật toán LMF: O(2.k.n3.(m+n).ln(m+n+bmax/bmin)) 2.3.1.4. Kết luận 2.3.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn 2.3.2.1. Giới thiệu bài toán 2.3.2.2 Phát biểu bài toán Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1,...,r}) là mạng hỗn hợp mở rộng đa hàng hóa đa chi phí được định nghĩa ở mục 2.1.2 và cho chi phí giới hạn B. Trên G có r loại hàng hóa lưu hành. Giả thiết với mỗi loại hàng hóa i, i=1,…,r, có ki cặp đỉnh nguồn-đích (sij, tij), j=1,…,ki, mỗi cặp được gán một lượng hàng hóa loại i, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij. Dij là số lượng hàng hóa loại i, i=1,...,r, cần chuyển từ sij đến tij, j =1,...,ki. Đặt dij =qi.Dij là số lượng hàng hóa quy đổi loại i, i=1,...,r, cần chuyển từ đỉnh nguồn sij đến đỉnh đích tij, j = 1,..., ki. Nhiệm vụ của bài toán là tìm một số  lớn nhất sao cho tồn tại một luồng chuyển ít nhất .dij đơn vị hàng hóa quy đổi loại i, i=1,…,r, từ đỉnh nguồn sij đến đỉnh đích tij, j =1,…,ki với tổng chi phí không vượt quá B, tức là: r ki   cf i 1 j 1 pPij ij ( p).bi ( p)  B, i  1,..., r , j  1,..., ki , p  Pij (12) Ký hiệu (LCMFP) là bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chí phí với chi phí giới hạn. Bài toán này được biểu diễn bằng mô hình qui hoạch tuyến tính ẩn như sau:
16   max thỏa mãn các ràng buộc r ki   cf i 1 j 1 pPie ij ( p)  ce(e).ze(e), e  E r ki   cf ij ( p)  cv(v).zv(v), v V i 1 j 1 pPiv (LCMF  cf pPij ij ( p)  .dij , i  1,, r , j  1,..., ki r ki   cf i 1 j 1 pPij ij ( p).bi ( p)  B  ≥ 0, cfij(p) ≥ 0, i=1,…, r, j=1,..., ki, p  Pij Ký hiệu (DLC) là bài toán đối ngẫu với (LCMFP), trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính bài toán (DLC) được xây dựng như sau: r ki Mỗi ràng buộc   cf i 1 j 1 pP ij ( p)  ce(e).ze(e), e  E được gán một biến le(e) của ie bài toán đối ngẫu (DLC). r ki Mỗi ràng buộc   cf i 1 j 1 pPiv ij ( p)  cv(v).zv(v), v V được gán một biến lv(v) của bài toán đối ngẫu (DLC). Mỗi ràng buộc  cf ij ( p )   .d ij được gán một biến zij của bài toán đối ngẫu (DLC). pPij r ki Mỗi ràng buộc   cf i 1 j 1 pPij ij ( p).bi ( p)  B được gán biến  của bài toán (DLC). Khi đó, bài toán (DLC) được phát biểu như sau: DLC (le, lv, )   ce(e).ze(e)   cv(v).ze(v)  .B  min eE eE thỏa mãn các ràng buộc  le(e)   lv(v)  zij , i  1,..., r, j  1,..., ki , p  Pij e p v p (DLC) r ki  d .z i 1 j 1 ij ij 1   0, le(e) ≥ 0, eE, lv(v) ≥ 0, vV, zij ≥ 0, i=1,..,.r, j=1,...,ki Cho pP là đường đi từ đỉnh v đến đỉnh w qua các cạnh ej, j=1,....,(h+1), và các đỉnh vj, i=1,...,.h, như sau: p = v → e1→ v1→ e2→ v2, →,…, eh→ vh→ eh+1→ w Ta định nghĩa độ dài đường đi p, ký hiệu lengthi(p), phụ thuộc các biến le(e), lv(v) theo công thức sau:
17 k 1 h lengthi ( p)   le(e j )   lv(v j )  bi ( p). (13) j 1 j 1 Ký hiệu distij(le,lv,) là độ dài đường đi ngắn nhất từ sij đến tij tính theo hàm độ dài lengthi(p), i=1,...,r, j=1,...,ki. r ki Đặt  (le, lv, )   dij .distij (le, lv,  ) , vậy (le lv,) là số lượng hàng hóa vận i 1 j 1 chuyển qua đường đi ngắn nhất giữa các cặp nguồn đích. Việc giải bài toán (DLC) tương DLC (le, lv,  ) đương với tìm hàm le:E R* và hàm lv:V R* sao cho đạt cực tiểu.  (le, lv,  )  DLC (le, lv,  )  Xét bài toán (DLC):   min  le : E  R* , lv : V  R* ,   0    (le, lv,  )   Bổ đề 2.3.2.1. Bài toán (DLC) tương đương với bài toán (DLC) theo nghĩa trị tối ưu của chúng bằng nhau và từ nghiệm tối ưu của bài toán này suy ra nghiệm tối ưu của bài toán kia và ngược lại. 2.3.2.3. Thuật toán LCMF (a). Thuật toán CMF  Đầu vào: Cho G=(V,E, ce, ze, cv, zv,{bei, bvi, qi |i=1,...,r}) Giả thiết với mỗi loại hàng hóa i, i=1,....,r, có ki cặp nút nguồn-đích (sij, tij), j=1,..., ki, mỗi cặp được gán một lượng hàng hóa quy đổi dij loại i, cần chuyển từ nút nguồn sij đến nút đích tij. Cho  là tỉ lệ xấp xỉ cần đạt được và chi phí giới hạn B. ◊ Đầu ra: Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng quy đổi tại các cạnh f = {cfi,j(e) | e  E, i=1,...,r, j=1,…,ki } Luồng cực đại đồng thời biểu diễn dạng tập hợp luồng thực tế tại các cạnh rf = {rfi,j(e) | e  E, i=1,...,r, j=1,…,ki} Hệ số cực đại đồng thời , fv, Bf . 1  ;  =  m  n 1 1  ◊ Các bước: Bước 1: Tính các giá trị ,  ;   1  3   1   1   Bước 2 : Khởi gán DLC(le,lv)=(m+n+1);  =  /B ; i=1,...,r, j=1,…,ki, di,j= Di,j.qi ; eEle(e)=  /(ce(e)ze(e)) ; vV lv(v) = /(cv(v)zv(v)) ; i=1,...,r, j=1,…,ki, e  E, cfij(e)=0;//Giá trị luồng cfij(e) lúc đầu t = 0 ;//bước đếm giai đoạn khi (DLC(t) < 1) DLC(0) = (m+n+1) ; // Giá trị hàm DLC(t) tại giai đoạn t=0 le0(e) = le(e), e E ; lv0(v) = lv(v) ,vV ; 0 =  ; Bước 3: i=1,...,r, j=1,…,ki, { d'ij = dij ; do