Top

Linear Programming

The analysis of problems in which a linear function of a number of variables is to be minimized or maximized when those variables are subject to a number of restraints in the form of linear inequalities. This technique has found its applications to important areas of blending problems and diet problems. Oil refineries, chemical industries, steel industries and food processing industry are also using linear programming with considerable success.

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

What is Linear Programing?

In short, form can be written as LP, a method to accomplish the best outcome from the situation designed in a mathematical model which is represented by linear relationships. Problem-based on LP may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints. Problems involving only two variables can be effectively solved by a graphical technique which provides a pictorial representation of the solution.

Model

The number of problems, showing how to model them by the appropriate choice of decision variables, objective, and constraints.

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

Find the values of the variable $x_1,\ x_2,\ ............, x_n$ which maximize (or minimize) the objective function

$Z$ = $c_1\ x_1\ +\ c_2\ x_2\ +\ .............. +\ c_n\ x_n$

subject to the constraints

$a_{11}\ x_1\ +\ a_{12}\ x_2\ + ............. +\ a_{1n}\ x_n \leq\ b_1$

$a_{21}\ x_1\ +\ a_{22}\ x_{2}\ +\ ............. +\ a_{2n}\ x_{n} \leq\ b_2$

.............................................................

$a_{m1x1}\ +\ a_{m2x2}\ +\ ..............\ +\ a_{mnxn}\ \leq\ b_m$

and meet the non-negative restrictions

$x_1,\ x_2,\ ...........,\ x_n\ \geq\ 0$

1. A set of values $x_1,\ x_2,\ ......,\ x_n$ which satisfies the constraints is called its solution.
2. Any solution to a problem which satisfies the non negativity restrictions of the problem is called its feasible solution.
3. Any feasible solution which maximizes(or minimizes) the objective function is called its optimal solution.

Rules to Solve

Step 1. Mark the unknowns in the given by x and y.

Step 2. Formulate the objective function.

Step 3. Translate all the constraints in the form of equalities.

Step 4. Solve these equalities simultaneously.

Step 5. Find the values of x and y for which the objective function z = ax + by has maximum or minimum value (as the case may be).

Limitations

Listed out some of the limitations as below:
• Treats all relationship as linear. But it is not true in many real-life situations.
• The decisions variables in LPP would be meaningful only if they are integers.
• The problems are complex if the number of variables and constraints are quite large.
• Factors such as uncertainty, weather conditions etc. are not taken into consideration.
• Parameters are assumed to be constants but in reality, they may not be so.
• LPP deals with only a single objective problem whereas, in real life situations, there may be more than one objective.

Word Problems

Given below are some of the examples on linear programming.

Solved Examples

Question 1: Solve the following linear program maximize 5x1 + 6x2 subject to
x1 - x2 ≥ 3
5x1 + 4x2 ≤ 35
x1 ≥ 0
x2 ≥ 0
Solution:
It is plain that the maximum occurs at the intersection of
5x1 + 4x2 = 35 and
x1 - x2 = 3

Solving simultaneously, rather than by reading values off the graph, we have that

5(3 + x2) + 4x2 = 35

i.e. 15 + 9x2 = 35

i.e. x2 = $\frac{20}{9}$ = 2.222 and

x1 = 3 + x2 = $\frac{47}{9}$ = 5.222

The maximum value is 5($\frac{47}{9}$) + 6($\frac{20}{9}$) = $\frac{355}{9}$

= 39.444

Question 2: A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week. Formulate this problem as a linear programming problem.
Solution:

Let
xT = number of tables made per week
xC = number of chairs made per week

Constraints total work time 6xT + 3xC ≤ 40 customer demand xC ≥ 3xT storage space
($\frac{x_C}{4}$) + xT ≤ 4, and xT , xC ≥ 0

Objective maximize 30xT + 10xC

The solution lies at the intersection of

$\frac{x_C}{4}$ + xT = 4 and 6xT + 3xC = 40

Solve for xT and xC

$\frac{x_C}{4}$ + xT = 4 ................(i)

and 6xT + 3xC = 40 ....................(ii)

From (i), xT = 4 - $\frac{x_C}{4}$, put in (ii)

6( 4 - $\frac{x_C}{4}$) + 3xC = 40

=> 24 - $\frac{3x_C}{2}$ + 3xC = 40

=> 24 + $\frac{3x_C}{2}$ = 40

=> $\frac{3x_C}{2}$ = 40 - 24 = 16

or xC = $\frac{32}{3}$ = 10.667

Plug the value of xC in equation (i)

$\frac{10.667}{4}$ + xT = 4

xT = 4 - $\frac{10.667}{4}$ = 1.333

Solving these two equations simultaneously we get xC = 10.667, xT = 1.333.

And the profit = 30xT + 10xC = 30(1.333) + 10(10.667) = £146.667

 More topics in Linear Programing Simplex Method Graphical Method of Linear Programming Linear Programming Examples
 Related Topics Math Help Online Online Math Tutor
*AP and SAT are registered trademarks of the College Board.