تجزیهی لاگرانژی برای مسئلهی طراحی شبکهی چندکالایی ظرفیتدار شده با شارژ ثابت

مسئله جریان چندکالایی توسط یک مجموعه از کالاها که در یک شبکه با کمترین هزینه در جریان هستند،مشخص میشود.در این نوع مسائل هدف فرستاده همزمان چندین کالا از مبدأها به مقصدها در یک شبکهی جهتدار میباشد بطوریکه مجموع جریان روی هر یال ازظرفیت یال تجاوز نکند.در این مقاله بر روی دو آزادسازی لاگرانژی-کوتاهترین مسیر و کوله پشتی-تمرکز کردیم.کرانهای حاصل از هر دوآزادسازیها برابر با ارزش آزادسازی برنامهریزی خطی Lp است. سپس یک آزادسازی جدید برای MCNDP )مسئله ی طراحی شبکهی چندکالایی ظرفیت دار شده با شارژ ثابت(ارائه نمودیم که مبتنی بر تجزیهی لاگرانژی است و تا اندازهای هر دو ساختارهای شبکه و ظرفیت مسئلهی اصلی را حفظ میکند.در انتها به این نتیجه خواهیم رسید که ممکن است آزادسازی لاگرانژی پیشنهاد شده برای MCNDP کرانهای قویتری از آزادسازی LP را حاصل کند

کلیدواژه ها:

مسئلهی طراحی شبکهی چند کالایی ، شارژ ثابت ، آزادسازی کوتاهترین مسیر و کوله پشتی ، تجزیهی لاگرانژی