The Construction of Simplex Linear Integer Programming Problems with Application

Abstract

The development of the Simplex method and its extension to linear integer programming (LIP) represents a significant milestone in optimization theory. Linear integer programming is used for decision-making problems with discrete variables, such as scheduling and resource allocation. This paper provides a historical overview of the Simplex method and discusses the construction of Simplex-based Gomory's approaches for solving LIP problems. It explores the theoretical foundations and practical applications of these methods, highlighting their importance in operational research and optimization. By applying the Simplex method to a real-world LIP problem at an Auto Mechanic and Dealer company, we demonstrate its effectiveness in addressing complex decision-making challenges.