مکانیابی تجهیزات جنگی در خط مقدم: مدل و روش حل
آرشیو
چکیده
در این مقاله به مطالعه ی نحوه ی موقعیت یابی تجهیزات جنگی در خط مقدم می پردازیم. در این مسأله هدف تعیین موقعیت مکانی تجهیزات جنگی است به گونه ای که تمام نقاط حساس دشمن پوشش داده شده و ضمنا کمترین تعداد تجهیزات ممکن برای این کار استفاده گردد. این مسأله را به صورت یک مسأله ی برنامه ریزی خطی صفر و یک مدل بندی کرده و در دو حالت آن را بررسی می کنیم (استفاده از یک نوع تجهیزات و استفاده از چندین نوع تجهیزات). در موردی که هدف تعیین موقعیت یک نوع تجهیزات جنگی باشد، نشان داده می شود که مسأله تبدیل به یک نوع خاص مسأله ی کمترین هزینه ی جریان در یک شبکه ی کمکی شده و در نتیجه می توان آن را در زمان چندجمله ای قوی حل کرد. اما در حالتی که انواع تجهیزات مورد استفاده قرار گیرند ثابت می گردد که با استفاده از یک کاهش از مسأله ی کوله پشتی، مسأله NP-سخت است. پس در این حالت نمی توان مسأله را به طور کارا حل کرد.Locating military equipment in forefront: model and approach
In this paper, we study the problem locating military equipment in forefront. In this problem, the goal is how to locate military equipment in such a way that all of the hotspots are covered and the number of the used military equipment are minimized. The problem is formulated as a zero - one linear programming problem. Then, it is investigated in two cases, use of one type and several type of military equipment. In the case that only one type of military equipment is located, it is shown that the problem is transformed into a special instance of minimum cost flow problem and consequently, it can be solved in strongly polynomial time. In the case that various types of military equipment are used, it is proved that the problem is NP-hard due to a reduction from the well-known knapsack problem. Therefore the problem cannot be solved efficiently in this case.
تبلیغات
