Bài thuyết trình Kỹ thuật ra quyết định kỹ sư - Đề tài: Ứng dụng Exel để giải bài toán Max Flow - Đậu Hùng Cường

ỨNG DỤNG EXEL ĐỂGIẢI BÀI TOÁN MAX FLOWSVTH: ĐẬU HÙNG CƯỜNGMSSV: 41100446KỸ THUẬT RA QUYẾT ĐỊNH CHO KỸ SƯBÀI TOÁN MAX FLOWLà bài toán tính ra số lượng hàng hóa cực đại lưu thông từ điểm đầu tới điểm cuối trong 1 mạng lưới gồm nhiều điểm trung gian.Để hiểu rõ hơn ta sẽ xét 1 ví dụ sau:Tính số lượng hàng hóa lưu thông tối đa từ điểm đầu là điểm S tới điểm cuối là T. Sao cho không xảy ra hiện tượng ứ đọng hàng hóa tại các điểm nằm trong mạng lưới; và số lượng hàng hóa lưu thông qua mỗi đường truyền giữa 2 không vượt quá khả năng của đường truyền đó.Bài toán được cho trong sơ đồ sau:Sơ đồ mạng lưới Đầu tiên ta sẽ gửi 1 lượng hàng là 20 xuất phát từ S tới điểm 1 rồi qua các điểm trung gian sau đó để tới điểm T. Lúc đó số lượng hàng hóa vận chuyển trong mạng lưới được biểu diễn như sau:Tiếp tục, ta sẽ gửi tiếp 1 lượng hàng hóa là 10 từ điểm S tới điểm số 4. Tử điểm số 4 hàng hóa sẽ tiếp tục lưu thông trong mạng lưới, qua các đường truyền còn khả năng, để hàng hóa không bị ứ đọng lại, và tới điểm kết thúc T.Tổng kết lại ta sẽ được sơ đồ lưu thông hàng hóa trong mạng lưới, với điểm bắt đầu là S, điểm kết thúc là T như sau:Vậy cực đại lưu thông trong mạng lưới là MaxZ = 30