Meaning of Linear Programming Problem

Meaning of a Linear Programming Problem (L.P.P.). The word "linear" means that every mathematical function involved —

the objective function and every constraint — contains its variables raised to at most the first power (no squares,

products of two variables, or other non-linear terms). An L.P.P. may then be defined as the problem of maximizing or

minimizing a linear function subject to linear constraints, where the constraints may themselves be written either as

equations or as inequations.

Four terms are formally defined and used throughout the remainder of the chapter:

1. Decision variables — the variables involved in the L.P.P. whose values are to be decided; for example, the number

   of units of two different products a factory should manufacture.

2. Objective function — a linear function of the decision variables which is to be optimized, i.e. either maximized

   or minimized; typically this represents total profit (to be maximized) or total cost (to be minimized).

3. Constraints — the conditions under which the objective function is to be optimized, expressed as linear equations

   or inequations; typically these represent limited resources (machine-hours, raw materials, budget) or minimum

   requirements (nutrients, strength, quality).

4. Non-negativity constraints — in many real situations the decision variables can only be positive or zero (a

   negative quantity of a manufactured item or an ingredient has no meaning), so these constraints, written $x\ge0,\ y\ge0$, are imposed in addition to the problem's own stated constraints.

This chapter deliberately restricts its scope in two ways, stated explicitly as notes: (i) only L.P.P.s with at most two …