Top

Linear Programming

Linear Programming deals with the optimization (maximization or minimization) of linear functions subject to linear constraints. The word 'Linear' implies directly proportionality of relationship of variables and 'Programming' means making schedules of activities to undertake in the future. LP therefore is planning by the use of linear relationship of variables involved.

The basic difference between a maximization and minimization problem in LP is found in the signs of the inequalities of constraints.

 In maximization problems : Constraint expressed by $\leq$ signIn minimization problems: Constraint expressed by $\geq$ sign

In general LPP, the expression ($\leq$, =, $\geq$) means that any specific problem each constraint may take one of the 3 possible forms:

• less than or equal to ($\leq$)
• equal to (=)
• greater than or equal to ($\geq$)

Any LPP involving more than two variables may be expressed as follows:

The general LP problem is to find the variables y$_1$, y$_2$, ............, y$_n$ which maximize (or minimize) the linear form.

Z = b$_1$ y$_1$ + b$_2$ y$_2$ + ...................+ b$_n$ y$_n$

subject to the constraints

c$_{11}$ y$_1$ + c$_{12}$ y$_2$ + ............. + c$_{1n}$ y$_n$ $\leq$ a$_1$

c$_{21}$ y$_1$ + c$_{22}$ y$_2$ + ............. + c$_{2n}$ y$_n$ $\leq$ a$_2$

.................. so on ....................

c$_{m1}$ y$_1$ + c$_{m2}$ y$_2$ + ............. + c$_{mn}$ y$_n$ $\leq$ a$_m$

and meet the non negative restrictions

y$_1$, y$_2$, ..........., y$_n$ $\geq$ 0

Solution to the LP problem is:

• Solutions: A set of values y$_1$, y$_2$, ..........., y$_n$ satisfies the constraints of LPP mentioned above is its solution.
• Feasible Solution: LPP solution which satisfies the constraints.
• Optimal Solution: LPP solution which maximizes (or minimizes) the objective function.

 Related Calculators Linear Programming Calculator Quadratic Equation Calculator Program Linear Calculator Calculating Linear Regression

*AP and SAT are registered trademarks of the College Board.