This chapter first presents basic theoretical concepts of linear programming (LP) problems. These include convexity, solution at extreme points or vertices, and charcterization of these through system of equations expressed in terms of basic and nonbasic variables. The KKT conditions are the applied to identify optimal vertex solutions. These theoretical concepts are then applied to derive the Simplex algorithm, which is introduced as an exchange algorithm between basic and nonbasic variables so as to verify optimality at a given vertex, and ensure feasible steps. A small numerical example is presented to illustrate the steps of the Simplex algorithm. Finally, a brief discussion on software such as CPLEX, GUROBI, and XPRESS is also presented.
Review the options below to login to check your access.
Log in with your Cambridge Higher Education account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.