مسأله برنامه ریزی خطی معکوس تحت فاصله منهتن

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