Linear Programming
Linear programming was developed by applied mathematicians and operations research specialists as a means to solve real-world problems using linear methods. Based on the fundamentals of matrix algebra, linear programming seeks to find an optimal solution, using quantitative methods, to a particular problem given a finite number of constraints. It is used extensively in managerial science and has widespread utility to business, government, and industry. It is applied especially to problems in which decision-makers wish to minimize costs or maximize profits under a given operating construct. In many cases, linear programming will affect decisions regarding materials used in manufacturing and construction or even the hiring of personnel or particular skill sets. It is an excellent tool for decisions regarding resource allocation.
Linear programming is based on linear equations—equations of variables raised only to the first power. Many variables--such as x, y, and z) or more generically, x1, x2,..., xk--may be used in a single equation, known as a linear combination. Generally, each variable represents a quantifiable item, such as the number of carpenters' hours available to a business during a week or number of sleds available for sale during a given month. It is important to note that in basic linear programming, the coefficients of the variables neither must equal each other nor equal any particular value--for example, 5x1 - 2.7x2 + 0x3 - (x4 7 is a perfectly valid linear combination. A special subset of linear programming, however, does specify that the solution should contain only zeros and ones for the values assigned to the variables.
Linear programming uses a finite number of linear combinations, combining them into a system of linear equations. Each of the equations is generally referred to as a constraint. Once the constraints are determined, linear programming seeks to find an optimal solution for either maximizing or minimizing the objective function. The objective function is a linear combination of all the variables present in the system of linear equations with pre-determined coefficients. It dominates the linear programming problem. A business manufacturing two types of computer chips, for example, may wish to determine the optimal mix of production that meets customer demand and maximizes profits. Similarly, a fast-food restaurant may wish to determine the optimal number of cashiers and grill cooks that meets customer demand while minimizing labor costs. In the first case, the computer chip manufacturer desires to maximize the objective function, which represents profit. In the second case, the restaurant manager wishes to minimize the objective function, which represents labor cost.
Like all systems of linear equations, linear programming problems will have either one solution, no solution, or many solutions. A problem with no solution is called unfeasible; when this situation occurs, there are no values that can be assigned to the variables in the objective function that meet the criteria established by the constraints. This case is very similar to an over-determined matrix with more variables than equations. In the case of many solutions, there exist at least two sets of values (perhaps infinitely many sets) that either maximize or minimize the objective function while abiding by the constraints. This case is similar to an under-determined matrix that has fewer variables than equations.
Solutions to linear programming problems may have either integer or real-numbered values. Solutions with real-numbered values are the norm. However, these solutions are often impractical to implement, as they may suggest buying 2.7 fishing boats or 10.5 sea kayaks to a marina. In these cases, an "integer-only" constraint is also attached to the linear programming problem. The solution will not be exact, but it will fall within a specified standard of the optimal solution, generally within 90, 95, or 99 percent. The new, "integer-only" solution may closely mimic the real-valued solution, or provide unexpected results--such as a recommendation to buy no fishing boats and 21 sea kayaks.
Oddly enough, nutritionists for large-scale medical facilities—such as retirement centers, nursing homes, extended care facilities, and hospitals--were among the first to extensively use linear programming as a professional aid. Nutritionists working in such centers are charged with ensuring their patients receive a well-balanced diet. This diet contains a minimum and maximum number of calories, as well as a minimum and maximum allowable amount of vitamins (such as B12 or C) and minerals (such as iron and zinc) that must be included daily. The number of calories consumed from proteins, carbohydrates, and fats must also be strictly balanced and may even vary by patient based on unique medical conditions and treatments. Within these constraints, nutritionists attempt to develop meal plans that both vary foods and minimize cost for the facility. Using caloric, vitamin, and mineral intake as constraints and relying on large databases of nutrition and cost data, nutritionists determine an optimal mix of foods and beverages to be served at meals at minimal cost.
This is the complete article, containing 797 words
(approx. 3 pages at 300 words per page).
