دوگان جریان با مینیمم هزینه در شبکه های مسطح

در شبکه های جریان عبور جریان از کمان های (مسیرها) شبکه دارای هزینه می باشد. در این گونه شبکه ها، مسئله جریان با مینیمم هزینه جریانی است که ضمن انتقال مقدار لازم جریان از گره های تولیدی (منبع) به گره های مصرف (مقصد) دارای حد اقل هزینه نیز باشد. این مسئله در شبکه های معمولی با الگوریتم های متعددی حل گردیده است. اما در شبکه های مسطح نیاز به بررسی و مطالعه بیشتری دارد. شبکه های مسطح به گونه ای طراحی می شوند که اگر روی یک سطح دو بعدی (مثلأ کاغذ) رسم شوند کمان ها همدیگر را قطع نمی کنند. به علاوه هر گراف مسطح به عنوان گراف اولیه دارای دوگان به صورت یک شکل هندسی نیز می باشد. در این مسئله از گراف دوگان به عنوان یک وسیله میانی استفاده می گردد. تابع هدف این مسائل سرجمع کل هزینه های انتقال جریان بین گره ها می باشد. قیود این مسئله تعادل جریان در گره ها است. به این معنی که حجم جریان های ورودی گره ها، حجم جریان های خروجی گره ها و مقدار جریان تولید/ مصرف گره ها دارای تعادل (بالانس) می باشد، می دهد.