ABSTRACT

Problems which seek to find a “best” configuration to achieve a certain goal are

called optimization problems. Programming problems deal with determining optimal

allocations of limited resources to meet given objectives. They deal with situations in

which a number of resources such as manpower, materials, and land are available to

be combined to yield one or more products. There are, however, restrictions imposed,

such as the total number of resources available and the quantity of each product to be

made. Linear programming deals with the class of programming problems in which

these restrictions and any other relations among the variables are linear. In particular,

the constraints imposed when searching graphs and networks for say shortest paths,

matchings, and maximum flow can be expressed as linear equations.