حسن صالحی فتح آبادی - دانشگاه تهران،دانشکده ریاضی، امار و علوم کامپیوتر
فرشته کوشکی - دانشگاه تهران، دانشکده ریاضی آمار و علوم کامپیوتر

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

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