بررسی ظرفیت ها در مسیله شبکه جریان چند کالایی باهزینه کمینه

در یک شبکه جریان چندکالایی هدف ارسال چند کالا از مبادی به مقاصد موردنظر برای تامین تقاضای موجود با توجه به محدودیت ظرفیت کمان های شبکه، با کمترین هزینه می باشد. به منظور بررسی امکان پذیر بودن تامین همه تقاضاهای موجود با توجه به محدودیت ظرفیت کمان ها، مساله ای رادر نظر می گیریم که در آن هدف یافتن جریانی است که بیشترین درصد از تقاضای هر کالا را با توجه به محدودیت های ظرفیت، تامین کند. یافتن چنین جریانی معادل با یافتن حداقل نسبتی از تغییر ظرفیت کمان هاست به نحوی که صد در صد تقاضای هر کالا تامین شود. چنین نسبتی را تراکم متناظر باجریان می نامیم.در این مقاله ضمن تشریح مسیله بیشینه سازی تامین تقاضا و مسیله جریان چند کالایی با تراکم کمینه، معادل بودن این دو مسیله را نشان می دهیم. همچنین چگونگی تعیین شدنی بودن مسیله جریان چند کالایی با هزینه کمینه از طریق حل مسیله جریان چند کالایی با تراکم کمینه را بررسی می کنیم.

کلیدواژه ها:

شبکه جریان ، جریان های مسیری ، جریان چند کالایی باهزینه کمینه