روش بزرگ M اصلاح شده برای به رسمیت شناختن عدم امکان پذیری مدل برنامه ریزی خطی

This paper provides an effective modification to the big-M method which leads to reducing the iterations of this method, when it is used to recognize the infeasibility of linear systems.

The simplex algorithm was conceived by Dantzig for solving linear programming (LP) problems (see [1], [2], [3] and [7]). This method starts with a basic feasible solution (BFS) and moves to an improved BFS, until the optimal point is reached or else unboundedness of the objective function is verified. In order to initialize this algorithm a BFS must be available. In many cases, finding such a BFS is not straightforward and some work may be needed to get the simplex algorithm started. To this end, there are two techniques in linear programming literature: two-phase method and big-M method [1], [2] and [6]. But there may be some LP models for which there are not any BFSs, i.e., the model is infeasible. Both two-phase method and big-M method distinguish the infeasibility. In this paper, we focus on infeasible cases and deal with the behaviour of big-M approach when dealing with infeasibility, and modify one of its end-conditions to strongly reduce the iterations required to distinguish the infeasibility. The rest of this paper unfolds as follows: In Section 2, the big-M technique is reviewed. Section 3 contains the provided modification and in Section 4, to illustrate the ability of the provided modification to reduce the number of iterations, a class of LP models is surveyed. Finally, Section 5 contains a short conclusion.

The big-M method is a known auxiliary technique to start the simplex algorithm using some artificial variables. This technique can also distinguish the infeasibility of linear systems. Reduction in the number of iterations, and hence the computational requirements, of the applied algorithms is one of the crucial topics of applied sciences. In this paper we have modified the big-M technique to this end. In fact, a new condition has been introduced which is necessary for the customary condition and hence the modified technique distinguishes the infeasibility before the customary one.