A Minimum Cost Relaxation Model for Infeasible Flow Networks
Author(s):
Abstract:
In many real systems, it happens that the existing flow network become inconsistent with the new applications or inputs. This means that some of the applicable structural characteristics have been changed so that the flow network has become infeasible or, in other words, obsolete. Therefore, it has to be adjusted to new applications. It is well known how to use a maximum flow algorithm to determine when a flow network is infeasible, but less known is how to adjust the structural data such that the network becomes feasible while the incurred adjustment cost is minimal. This paper considers an infeasible flow network G= (V, A) in which supplies/demands, arc capacities and flow lower bounds are liable to relax. A minimum cost relaxation model for canceling most positive cuts is constructed. Analyzing the model shows that, in order to make the network feasible, it is sufficient to adjust only one component of the structural data. According to this result, a polynomial time algorithm is developed to cancel all positive cuts and convert the infeasible flow network to a feasible one.
Language:
English
Published:
International Journal of Science, Volume:6 Issue: 1, 2005
Page:
107
magiran.com/p636033
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!