ابومسلم محمدی

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