Modified Ellipsoid Method and Its Application to Linear Programming Problems

In this paper, we study Ellipsoid method and modified Ellipsoid method in order to find a point which satisfies a system of linear inequalities and apply it to linear programming problems. We first present Ellipsoid algorithm and prove its convergence. After analyzing the shortcomings of the algorithm, we propose a new algorithm called the modified Ellipsoid algorithm and prove its convergence. Then, we present how the methods can be applied to find feasible solutions and optimal feasible solutions of linear programming problems. Finally, some particular examples are given to illustrate the modified Ellipsoid method. The Matlab codes of modified Ellipsoid method as well as the Matlab codes for two numerical examples are also presented in detail