Linear Programming Category

Summary

Adds support for linear programming.

Description

Collection adds support for Dual Simplex, Two-Phase Simplex and Gomory's Cutting Plane Algorithm.A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. The constraints may be equalities or inequalities. Not all linear programming problems are so easily solved. There may be many variables and many constraints. Some variables may be constrained to be nonnegative and others unconstrained. Some of the main constraints may be equalities and others inequalities.Terminology: The function to be maximized or minimized is called the objective function. A vector, x for the standard maximum problem or y for the standard minimum problem, is said to be feasible if it satisfies the corresponding constraints. The set of feasible vectors is called the constraint set. A linear programming problem is said to be feasible if the constraint set is not empty; otherwise it is said to be infeasible. A feasible maximum (resp. minimum) problem is said to be unbounded if the objective function can assume arbitrarily large positive (resp. negative) values at feasible vectors; otherwise, it is said to be bounded. Thus there are three possibilities for a linear programming problem. It may be bounded feasible, it may be unbounded feasible, and it may be infeasible. The value of a bounded feasible maximum (resp, minimum) problem is the maximum (resp. minimum) value of the objective function as the variables range over the constraint set. A feasible vector at which the objective function achieves the value is called optimal.

Components

	Name	Summary
	TMtxLP	Interfaces Linear Programming algorithms.

Routines

Name	Summary
CPA	Gomory's cutting plane algorithm for solving the integer programming problem.
SimplexDual	Linear optimization by Dual Simplex algorithm.
SimplexLP	Linear optimization by using Simplex method.
SimplexTwoPhase	Linear optimization by Two-Phase Simplex algorithm.